# Image2Reverb: Cross-Modal Reverb Impulse Response Synthesis

Nikhil Singh
MIT
Media Lab
<EMAIL_ADDRESS>Jeff Mentch
Harvard University
SHBT
<EMAIL_ADDRESS>Jerry Ng
MIT
Mechanical Engineering
<EMAIL_ADDRESS>Matthew Beveridge
MIT
EECS
<EMAIL_ADDRESS>Iddo Drori
MIT
EECS
<EMAIL_ADDRESS>
###### Abstract

Measuring the acoustic characteristics of a space is often done by capturing
its impulse response (IR), a representation of how a full-range stimulus sound
excites it. This work generates an IR from a single image, which can then be
applied to other signals using convolution, simulating the reverberant
characteristics of the space shown in the image. Recording these IRs is both
time-intensive and expensive, and often infeasible for inaccessible locations.
We use an end-to-end neural network architecture to generate plausible audio
impulse responses from single images of acoustic environments. We evaluate our
method both by comparisons to ground truth data and by human expert
evaluation. We demonstrate our approach by generating plausible impulse
responses from diverse settings and formats including well known places,
musical halls, rooms in paintings, images from animations and computer games,
synthetic environments generated from text, panoramic images, and video
conference backgrounds.

Figure 1: An application of our work: matching speaker audio to expected
reverberation of a video conference virtual background.
Project page with examples is available at
https://web.media.mit.edu/~nsingh1/image2reverb.

Figure 2: Generating audio impulse responses from images. Left: given an image
of an acoustic environment as input, our model generates the corresponding
audio impulse response as output. Right: generated impulse responses are
convolved with an anechoic (free from echo) audio recording making that
recording sound as if it were in the corresponding space. Waveforms and
spectrograms are shown of the source anechoic signal and the same signal after
convolution with the corresponding synthesized IR. All spectrograms are
presented on a mel scale. Image2Reverb is the first system demonstrating end-
to-end synthesis of realistic IRs from single images.

##  1 Introduction

An effective and widely used method of simulating acoustic spaces relies on
audio impulse responses (IRs) and convolution [41, 34]. Audio IRs are recorded
measurements of how an environment responds to an acoustic stimulus. IRs can
be measured by recording a space during a burst of white noise like a clap, a
balloon pop, or a sinusoid swept across the range of human hearing [31].
Accurately capturing these room impulse responses requires time, specialized
equipment, knowledge, and planning. Directly recording these measurements may
be entirely infeasible in continuously inhabited or inaccessible spaces of
interest. End-to-end IR estimation has far ranging applications relevant to
fields including music production, speech processing, and generating immersive
extended reality environments. Our Image2Reverb system directly synthesizes
IRs from images of acoustic environments. This approach removes the barriers
to entry, namely cost and time, opening the door for a broad range of
applications.

Figure 3: Impulse response overview. (A) Sound waves propagate across multiple
paths as they interact with and reflect off their environment. These paths
include the direct path from source to listener, early reflections including
1st and higher order reflections (after reflecting off 1 or more surfaces) and
a more diffuse tail as they trail off and become more densely packed in time.
These reflections make up the impulse response of the environment illustrated
(B) schematically and (C) as a waveform.

In this work we model IR generation as a cross-modal paired-example domain
adaptation problem and apply a conditional GAN [10, 12, 25] to synthesize
plausible audio impulse responses conditioned on images of spaces. Next, we
will describe related work that informs our approach.

##  2 Related Work

#### Artificial reverberation.

Historically, recording studios built reverberant chambers with speakers and
microphones to apply reverb to pre-recorded audio directly within a physical
space [33]. Reverberation circuits, first proposed in the 1960s, use a network
of filters and delay lines to mimic a reverberant space [37]. Later, Digital
algorithmic approaches applied numerical methods to simulate similar effects.
Conversely, convolution reverb relies on audio recordings of a space’s
response to a broadband stimulus, typically a noise burst or sine sweep. This
results in a digital replica of a space’s reverberant characteristics, which
can then be applied to any audio signal [1].

Convolutional neural networks have been used for estimating late-reverberation
statistics from images [17, 18], though not to model the full audio impulse
response from an image. This work is based on the finding that experienced
acoustic engineers readily estimate a space’s IR or reverberant
characteristics from an image [16]. Room geometry has also been estimated from
360-degree images of four specific rooms [32], and used to create virtual
acoustic environments which are compared with ground-truth recordings, though
again IRs are not directly synthesized from the images. A related line of work
synthesizes spatial audio based on visual information [20, 8, 15]. Prior work
exists on synthesis of IRs using RNNs [35], autoencoders [39], and GANs: IR-
GAN [30] uses parameters from real world IRs to generate new synthetic IRs;
whereas our work synthesizes an audio impulse response directly from an image.

#### Generative models for audio.

Recent work has shown that GANs are amenable to audio generation and can
result in more globally coherent outputs [6]. GANSynth [7] generates an audio
sequence in parallel via a progressive GAN architecture allowing faster than
real-time synthesis and higher efficiency than the autoregressive WaveNet [42]
architecture. Unlike WaveNet which uses a time-distributed latent coding,
GANSynth synthesizes an entire audio segment from a single latent vector.
Given our need for global structure, we create a fixed-length representation
of our input and adapt our generator model from this approach.

Measured IRs have been approximated with shaped noise [19, 3]. While room IRs
exhibit statistical regularities [40] that can be modeled stochastically, the
domain of this modeling is time and frequency limited [2], and may not reflect
all characteristics of real-world recorded IRs. Simulating reverb with ray
tracing is possible but prohibitively expensive for typical applications [36].
By directly approximating measured audio IRs at the spectrogram level, our
outputs are immediately applicable to tasks such as convolution reverb, which
applies the reverberant characteristics of the IR to another audio signal.

#### Cross-modal translation.

Between visual and auditory domains, conditional GANs have been used for
translating between images and audio samples of people playing instruments
[4]. Our work builds on this by applying state-of-the-art architectural
approaches for scene analysis and high quality audio synthesis, tuned for our
purposes.

##  3 Methods

Here we describe the dataset, model, and algorithm.

###  3.1 Dataset

#### Data aggregation.

We curated a dataset of 265 different spaces totalling 1169 images and 738
IRs. From these, we produced a total of 11234 paired examples with a train-
validation-test split of 9743-154-1957. These are assembled from sources
including the OpenAIR dataset [26], other libraries available online, and web
scraping. Many examples amount to weak supervision, due to the low
availability of data: for example, we may have a “kitchen” impulse response
without an image of the kitchen in which it was recorded. In this case, we
augmented with plausible kitchen scenes, judged by the researchers, gathered
via web scraping and manual filtering. Although this dataset contains high
variability in several reverberant parameters, e.g. early reflections and
source-microphone distance, it allows us to learn characteristics of late-
field reverberation.

#### Data preprocessing.

Images needed to be filtered manually to remove duplicates, mismatches such as
external pictures of an indoor space, examples with significant occlusive
“clutter” or excessive foreground activity, and intrusive watermarks. We then
normalized, center-cropped at the max width or height possible, and
downsampled to 224x224 pixels. We converted the audio IR files to monaural
signals; in the case of Ambisonic B-Format sources we extracted the $W$
(omnidirectional) channel, and for stereo sources we computed the arithmetic
mean of channels. In some cases, 360-degree images were available and in these
instances we extract rectilinear projections, bringing them in line with the
standard 2D images in our dataset.

#### Audio representation.

Our audio representation is a log magnitude spectrogram. We first resampled
the audio files to 22.050kHz and truncate them to 5.94s in duration. This is
sufficient to capture general structure and estimate reverberant
characteristics for most examples. We then apply a short-time Fourier
transform with window size ($M=1024$) and hop size ($R=256$), before trimming
the Nyquist bin, resulting in square 512x512 spectrograms. Finally, we take
$\log(\lvert X\rvert)$ where $\lvert X\rvert$ represents the magnitude
spectrogram; audio IRs typically contain uncorrelated phase, which does not
offer structure we can replicate based on the magnitude.

###  3.2 Model

#### Components.

Our model employs a conditional GAN with an image encoder that takes images as
input and produces spectrograms. This overall design, with an encoder,
generator, and conditional discriminator, is similar to that which Mentzer et
al. [24] applied to obtain state-of-the-art results on image compression,
among many other applications. The generator and discriminator are deep
convolutional networks based on the GANSynth [7] model (non-progressive
variant), with modifications to suit our dataset, dimensions, and training
procedure.

The encoder module combines image feature extraction with depth estimation to
produce latent vectors from two-dimensional images of scenes. For depth
estimation, we use the pretrained Monodepth2 network [9], a monocular depth-
estimation encoder-decoder network which produces a one-channel depth map
corresponding to our input image. The main feature extractor is a ResNet50
[13] pretrained on Places365 [44] which takes a four-channel representation of
our scene including the depth channel (4x224x224). We add randomly initialized
weights to accommodate the additional input channel for the depth map. Since
we are fine-tuning the entire network, albeit at a low learning rate, we
expect it will learn the relevant features during optimization. Our
architecture’s components are shown in Figure 4.

Figure 4: System architecture. Our system consists of autoencoder and GAN
networks. Left: An input image is converted into 4 channels: red, green, blue
and depth. The depth map is estimated by Monodepth2, a pre-trained encoder-
decoder network. Right: Our model employs a conditional GAN. An image feature
encoder is given the RGB and depth images and produces part of the Generator’s
latent vector which is then concatenated with noise. The Discriminator applies
the image latent vector label at an intermediate stage via concatenation to
make a conditional real/fake prediction, calculating loss and optimizing the
Encoder, Generator, and Discriminator.

Input:

Monodepth2: $x\sim X$; Encoder $\tilde{x}\sim\tilde{X}$; Generator:
$z=E(\tilde{x})\oplus u$; Discriminator: $(G(z),E(\tilde{x}))$ OR
$(y,E(\tilde{x}))$;

Parameters: (weight variables);

Output:

Monodepth2: $\mathbf{x_{d}}$; Encoder: $E(\tilde{x})$; Generator: G(z);
Discriminator: $D(G(z),E(\tilde{x}))$ OR $D(y,E(\tilde{x}))$;

for  _number of epochs_ do

Sample $B$ training images;

Get depth $x_{d}=M(x)$;

Append depth features to RGB channels ($y\oplus y_{d}$);

Encoder image to feature-vector ($E(\tilde{x})$);

Append noise ($z=E(\tilde{x})\oplus u$;

Generate spectrogram ($G(z)$);

Forward pass through discriminator with either fake or real spectrogram
($D(G(z)|E(\tilde{x})$ OR $D(y|E(\tilde{x}))$);

Backward pass: update parameters for discriminator ($W_{D}$), generator
($W_{G}$), and encoder ($W_{E}$);

end for

Algorithm 1 Forward and backward passes through the Image2Reverb model. Notation is explained in Table 1. Notation | Definition
---|---
x | input image
$x_{d}$ | estimated depth map
$\oplus$ | concatenation operator
$\tilde{x}$ |  image with depth map ($x\oplus x_{d}$)
$y$ | Real spectrogram
$E,G,D$ | Encoder, Generator, Discriminator
$M$ | Monodepth2 Encoder-Decoder
$W_{*}$ | weights for a model
$u$ |  Noise, $u\sim\mathcal{N}(0,1)$
$z$ | Latent vector, encoder output and noise
|  ($E(\tilde{x})\oplus u$)
Table 1: Notation and definitions for variables indicated in different parts
of this paper.

#### Objectives.

We use the least-squares GAN formulation (LSGAN) [22]. For the discriminator:

$\displaystyle\begin{split}\underset{D}{\text{min}}\
V(D)&=\mathbb{E}_{\mathbf{y}\sim p_{data}(\mathbf{y})}[(1-D(y\ |\
E(\tilde{x}))^{2}]\\\ &+\mathbb{E}_{\mathbf{z}\sim p_{z}(\mathbf{z})}[(D(G(z)\
|\ E(\tilde{x}))^{2}]\end{split}$ (1)

For the generator, we introduce two additional terms to encourage realistic
and high-quality output. First, we add an $\ell 1$ reconstruction term, scaled
by a hyperparameter ($\lambda_{a}=100$ in our case). This is a common approach
in image and audio settings. Second, we introduce a domain-specific term that
performs an estimation of the $T_{60}$ values, the time it takes for the
reverberation to decay by $60dB$, for the real and generated samples, and
returns the absolute percent error between the two scaled by a hyperparameter
($\lambda_{b}=100$ again). We term the differentiable $T_{60}$ proxy measure
$T_{60_{p}}$. To compute this for log-spectrogram $x$, we first get the linear
spectrogram $e^{x}$ and then sum along the time axis to obtain a fullband
amplitude envelope. We use Schroeder’s backward integration method to obtain a
decay curve from the squared signal, and linearly extrapolate from the $-20dB$
point to get a $T_{60}$ estimate. In all:

$\displaystyle\begin{split}\underset{G}{\text{min}}\
V(G)&=\mathbb{E}_{\mathbf{z}\sim p_{z}(\mathbf{z})}\left[\right.(1-D(G(z)\ |\
E(\tilde{x}))^{2}\\\ &+\lambda_{a}\left\lVert G(z)-y\right\rVert_{1}\\\
&+\left.\lambda_{b}\left\lvert\dfrac{T_{60_{p}}(G(z))-T_{60_{p}}(y)}{T_{60_{p}}(y)}\right\rvert\right]\end{split}$
(2)

#### Training.

We train our model on 8 NVIDIA 1080 Ti GPUs. Three Adam optimizers for each of
the Generator, Discriminator, and Encoder were used to optimize the networks’
parameter weights. Hyperparameters are noted in Table 2. We make our model and
code publicly available 111Model and code:
https://github.com/nikhilsinghmus/image2reverb.

Parameter | Value
---|---
$\eta_{G}$ | 4e-4
$\eta_{D}$ | 2e-4
$\eta_{E}$ | 1e-5
$\beta$ | (0.0, 0.99)
$\epsilon$ | 1e-8
Table 2: Hyperparameters for the Generator, Discriminator, and Encoder initial
learning rates, the optimizer beta ($\beta$), and epsilon ($\epsilon$) for the
Adam optimizers we use (one each for $D,G,E$)

##  4 Results

Using Image2Reverb we are able to generate perceptually plausible impulse
responses for a diverse set of environments. In this section, we provide
input-output examples to demonstrate the capabilities and applications of our
model and also review results of a multi-stage evaluation integrating domain-
specific quantitative metrics and expert ratings. Our goal is to examine
output quality and conditional consistency, generally considered important for
conditional GANs [5] and most relevant for our application.

###  4.1 Examples

We present several collections consisting of diverse examples in our
supplementary material, with inputs curated to illustrate a range of settings
of interest including famous spaces, musical environments, and entirely
virtual spaces. All examples are made available as audiovisual
collections222Audiovisual samples:
https://web.media.mit.edu/~nsingh1/image2reverb/ and were generated with a
model trained in around 12 hours, with 200 epochs on a virtual machine. Figure
5 shows examples from our test set that were used in our expert evaluation (4
of 8, one from each category of: Small, Medium, Large, and Outdoor). We
convolve a spoken word anechoic signal with the generated IRs for the reader
to hear. Figure 6 takes images of diverse scenes (art, animation,
historical/recognizable places) as inputs. Figure 7 demonstrates how sections
of 360-degree equirectangular images are cropped, projected, and passed
through our model to generate IRs of spaces for immersive VR environments.

We strongly encourage the reader to explore these examples on the accompanying
web page. We include examples of musical performance spaces, artistic
depictions (drawings, paintings), 3D animation scenes, synthetic images from
OpenAI’s DALL•E, as well as real-world settings that present challenges (e.g.
illusions painted on walls, reflections, etc.). These are largely created with
real-world environments for which we may not have ground truth IRs,
demonstrating how familiar and unusual scenes can be transformed in this way.

Figure 5: Ground-truth measured IRs vs generated IRs. Columns show input
images, depth maps, measured IRs with corresponding convolved speech, and
generated IRs with corresponding convolved speech. Larger indoor spaces here
tend to exhibit greater $T_{60}$ times with longer measured impulse responses.
The outdoor scene has a very short measured IR and corresponding generated IR.
Input images are all examples that were used in the expert survey and were
drawn from the test set. Figure 6: Generated IR examples. Columns show input
images, depth maps, generated IRs, and a dry anechoic speech signal before and
after the generated IR was applied via convolution. Input images come from a
variety of spaces which illustrate possible applications of our model. Some
images are synthetic, including: an oil painting, a 3D animation still, and a
video game screenshot. Others come from real-world scenes like a church (where
music is often heard), a famous yet inaccessible space (SpaceX), and an
outdoor desert scene. Larger indoor spaces tend to exhibit longer impulse
responses as seen here. Figure 7: VR. Impulse responses generated from an
equirectangular 360-degree image by sampling points on a sphere, cropping and
applying a rectilinear projection to the resulting image, and feeding them
into our model. This demonstrates how our model directly generates realistic
impulse responses of panoramic virtual reality compatible images. Future work
may allow generation of impulse responses using an entire 360-degree image,
though at present there is a lack of paired data available for training.

###  4.2 Ablation Study

To understand the contribution of key architectural components and decisions,
we perform a study to characterize how removing each affects test set $T_{60}$
estimation after 50 training epochs. The three components are the depth maps,
the $T_{60_{p}}$ objective term, and the pretrained Places365 weights for the
ResNet50 encoder. Figure 8 shows $T_{60}$ error distributions over the test
set for each of these model variants, and Table 3 reports descriptive
statistics.

Our model reflects better mean error (closer to 0%) and less dispersion (a
lower standard deviation) than the other variants. The former is well within
the just noticeable difference (JND) bounds for $T_{60}$, often estimated as
being around 25-30% for a musical signal [23]. Additionally, this is an upper
bound on authenticity: a more rigorous goal then perceptual plausibility [28].
The lower standard deviation indicates generally more consistent performance
from this model across different examples, even in the presence of some that
cause relatively large estimation errors due to incorrect interpretation of
relevant qualities in the image, or inaccurate/noisy synthesis or estimation.

Figure 8: $T_{60}$ estimation error (%) distributions from each model version. $T_{60}$ estimates how long it takes the reverberation to decay by $60dB$. “Main” is our architecture as described earlier, “No Depth” omits the depth maps, “No T60P” omits the differentiable $T_{60_{p}}$ objective term, and “No Places” uses randomly initialized encoder weights. “NN” applies a nearest-neighbor approach with Places365-ResNet50 embeddings for images (errors clipped to 2000% for clarity). Descriptive statistics are given in Table 3. |  | Main | -Depth |  -$T_{60_{p}}$ | -P365 | NN
---|---|---|---|---|---|---
$T_{60}$ Err (%) | $\mu$ | -6.03 | -9.17 | -7.1 | 43.15 | 149
$\sigma$ | 78.8 | 83.1 | 85.97 | 144.3 | 491.02
Table 3: $T_{60}$ estimation error (%) statistics from each model version.
“Main” is our architecture as described earlier, “-Depth” omits depth
maps,“-$T_{60_{p}}$” omits the differentiable $T_{60_{p}}$ objective term, and
“-P365” does not use the pretrained Places365 weights for the ResNet50
encoder. “NN” indicates a nearest-neighbor approach with Places365-ResNet50
embeddings for images. For mean and median, values closer to 0 reflect better
performance. For the standard deviation, lower values reflect better
performance. Distributions are visualized in Figure 8.

###  4.3 Expert Evaluation

Following the finding that experienced acoustic engineers readily estimate a
space’s reverberant characteristics from an image [16], we designed an
experiment to evaluate our results. We note that this experiment is designed
to estimate comparative perceptual plausibility, rather than (physical)
authenticity (e.g. by side-by-side comparison to assess whether any difference
can be heard). These goals have been differentiated in prior work [28]. We
selected two arbitrary examples from each of the four scene categories and
recruited a panel of 31 experts, defined as those with significant audio
experience, to participate in a within-subjects study. For each of these
examples, we convolved an arbitrary anechoic signal with the output IR, as
well as the ground truth IR. These 16 samples were presented in randomized
order and participants were instructed to rate each on a scale from 1 to 5
based on 1) reverberation quality, and 2) realism or “match” between their
expected reverb based on the image and the presented signal with reverb
applied. Participants answered one reverb-related screening question to
demonstrate eligibility, and two attention check questions at the end of the
survey. The four scene categories are: Large, Medium, Outdoor, and Small.
These demonstrate diversity in visual-reverb relationships. The dependent
variables are quality and match ratings, and the independent variables are IR
source (real vs. fake) and scene category (the four options listed
previously). We first test our data for normality with D’Agostino and
Pearson’s omnibus test [27], which indicates that our data is statistically
normal ($p>.05$).

A two-way repeated-measures ANOVA revealed a statistically significant
interaction between IR source and scene category for both quality ratings,
$F(3,90)=7.04$, $p\leq.001$, and match ratings, $F(3,90)=3.73$, $p=.02$
(reported $p$-values are adjusted with the Greenhouse-Geisser correction
[11]). This indicates that statistically significant differences between
ratings for real and fake IR reverbs depend on the scene category. Per-
participant ratings and rating changes, overall and by scene, are shown in
Figure 9.

Subsequent tests for simple main effects with paired two one-sided tests
indicate that real vs. fake ratings are statistically equivalent ($p<.05$) for
large and small quality ratings, and large, medium, and small match ratings.
These tests are carried out with an $\epsilon$ of 1 (testing for whether the
means of the two populations differ by at least 1). Results are shown in Table
4. Notably, outdoor scenes appear to contribute to the rating differences
between real and fake IRs. We conjecture this is due to outdoor scenes being
too different a regime from the vast majority of our data, which are indoor,
to model effectively. Additionally, medium-sized scenes appear to contribute
to differences in quality.

Rating | Scene | DoF | $p$
---|---|---|---
Quality | Large | 56 | $<.001$
Quality | Medium | 56 | $.28$
Quality | Outdoor | 56 | $.62$
Quality | Small | 56 | $<.001$
Match | Large | 56 | $<.001$
Match | Medium | 56 | $.006$
Match | Outdoor | 56 | $.29$
Match | Small | 56 | $<.05$
Table 4: Simple main effect tests for equivalence between real and generated
IRs across different categories of scenes. We use paired two one-sided tests
with bounds ($\epsilon$) of 1 and Bonferroni-adjusted p-values. These results
suggest that real vs. fake ratings are statistically equivalent within one
rating unit (the resolution of the rating scale) for large and small quality
ratings, and large, medium, and small match ratings. Notably, outdoor scenes
contribute to the difference between real and fake IRs and medium-sized scenes
contribute to differences in quality. Figure 9: Expert evaluation results.
Paired plots showing per-participant quality and match differences in rating
for each scene category. Green lines indicate higher rating for real IRs, red
lines for generated IRs, and grey lines equivalent ratings for both.

###  4.4 Model Behavior and Interpretation

#### Effect of varying depth.

We compare the full estimated depth map with constant depth maps filled with
either 0 or 0.5 (chosen based on the approximate lower and upper bounds of our
data). We survey the distributions of generated IRs’ $T_{60}$ values over our
test set, the results of which are shown in Figure 10. Table 5 reports
descriptive statistics for these distributions, showing that the main model’s
output IRs’ decay times are biased lower by the 0-depth input and higher by
the 0.5-depth input respectively. These may indicate some potential for
steering the model in interactive settings. We do note, however, that behavior
with constant depth values greater than 0.5 is less predictable. This may be
due to the presence of outdoor scenes, for which the scene’s depth may not be
correlated with IR duration.

Figure 10: Effect of Depth on $T_{60}$. Distributions of estimated $T_{60}$ values for the model with estimated depth maps, plus constant depth maps set to either 0 (low) or 0.5 (high). Manipulating the depth value allows us to “suggest” smaller or larger scenes, i.e. bias the output of the model. Table 5 shows corresponding descriptive statistics. These results indicate a level of “steerability” for the model’s behavior in human-in-the-loop settings. |  | Main | Depth 0 | Depth 0.5
---|---|---|---|---
$T_{60}$ (s) | $\mu$ | 2.07 | 2.01 | 3.62
$\sigma$ | 1.54 | 0.87 | 2.36
$Mdn.$ | 2.69 | 2.00 | 3.07
Table 5: Descriptive statistics for the model with estimated depth maps, as
well as constant depth maps set to either 0 or 0.5. The full depth map’s
results are between that of the 0 and 0.5 depth maps. Figure 10 visulizes the
corresponding distributions.

#### Effect of transfer learning.

To understand which visual features are important to our encoder, we use
Gradient-weighted Class Activation Mapping (Grad-CAM) [38]. Grad-CAM is a
popularly applied strategy for visually interpreting convolutional neural
networks by localizing important regions contributing to a given target
feature (or class in a classification setting). We produce such maps for our
test images with both the ResNet50 pre-trained on Places365 dataset, as well
as the final encoder model. All resulting pairs exhibit noticeable
differences; we check for this with the structural similarity index (SSIM)
metric [43], which is below 0.98 for all examples.

Figure 11: Grad-CAMs for images passed through the pre-trained Places365
ResNet50 encoder vs. our fine-tuned encoder, showing movement towards
significant reflective areas for (A) a small, and (B) a large environment. The
fine-tuned model’s activations highlight larger reflective surfaces: depth of
staircase for (A) vs. railing that may be more optimal for scene
identification, and wall-to-ceiling corner plus surrounding areas for (B).
Figure 12: Grad-CAMs for images passed through both the pre-trained Places365
ResNet50 encoder and our fine-tuned encoder, showing movement towards more
textured areas for (A) an indoor, and (B) an outdoor environment. The former
seems to contain significant absorption and the latte has few reflective
surfaces. In both cases, textured areas are highlighted. These may be
associated with absorption, diffusion, and more sparse reflections depending
on the scene.

We qualitatively survey these and identify two broad change regimes, which are
illustrated with particular examples. First, we observe that the greatest-
valued feature is often associated with activations of visual regions
corresponding to large reflective surfaces. Examples are shown in Figure 11.
Often, these are walls ceilings, windows, and other surfaces in reflective
environments. Second, we find that textured areas are highlighted in less
reflective environments. Examples of these are shown in Figure 12. These may
correspond to sparser reflections and diffusion.

#### Limitations and future work.

Many images of spaces may offer inaccurate portrayals of the relevant
properties (size, shape, materials, etc.), or may be misleading (examples in
supplementary material), leading to erroneous estimations. Our dataset also
contains much variation in other relevant parameters (e.g. $DRR$ and $EDT$) in
a way we cannot semantically connect to paired images, given the sources of
our data. New audio IR datasets collected with strongly corresponding photos
may allow us to effectively model these characteristics precisely.

##  5 Conclusion

We introduced Image2Reverb, a system that is able to directly synthesize audio
impulse responses from single images. These are directly applied in downstream
convolution reverb settings to simulate depicted environments, with
applications to XR, music production, television and film post-production,
video games, videoconferencing, and other media. Our quantitative and human-
expert evaluation shows significant strengths, and we discuss the method’s
limitations. We demonstrate that end-to-end image-based synthesis of plausible
audio impulse responses is feasible, given such diverse applications. We hope
our results provide a helpful benchmark for the community and future work and
inspire creative applications.

#### Acknowledgements

We thank the reviewers for their thorough feedback and useful suggestions.
Additionally, we thank James Traer, Dor Verbin, and Phillip Isola for helpful
discussions. We thank Google for a cloud platform education grant.

## References

  * [1] Rolf Anderegg, Norbert Felber, Wolfgang Fichtner, and Ulrich Franke.  Implementation of high-order convolution algorithms with low latency on silicon chips.  In Audio Engineering Society Convention 117. Audio Engineering Society, 2004.
  * [2] Roland Badeau.  Common mathematical framework for stochastic reverberation models.  The Journal of the Acoustical Society of America, 145(4):2733–2745, 2019.
  * [3] Nicholas J Bryan.  Impulse response data augmentation and deep neural networks for blind room acoustic parameter estimation.  In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1–5. IEEE, 2020.
  * [4] Lele Chen, Sudhanshu Srivastava, Zhiyao Duan, and Chenliang Xu.  Deep cross-modal audio-visual generation.  CoRR, abs/1704.08292, 2017.
  * [5] Terrance DeVries, Adriana Romero, Luis Pineda, Graham W. Taylor, and Michal Drozdzal.  On the evaluation of conditional {gan}s, 2020.
  * [6] Chris Donahue, Julian McAuley, and Miller Puckette.  Adversarial audio synthesis.  In International Conference on Learning Representations, 2019.
  * [7] Jesse Engel, Kumar Krishna Agrawal, Shuo Chen, Ishaan Gulrajani, Chris Donahue, and Adam Roberts.  GANSynth: Adversarial neural audio synthesis.  In International Conference on Learning Representations, 2019.
  * [8] Ruohan Gao and Kristen Grauman.  2.5d visual sound.  In CVPR, 2019.
  * [9] Clément Godard, Oisin Mac Aodha, Michael Firman, and Gabriel J. Brostow.  Digging into self-supervised monocular depth prediction.  In The International Conference on Computer Vision (ICCV), October 2019.
  * [10] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In Advances in neural information processing systems, pages 2672–2680, 2014.
  * [11] Samuel W Greenhouse and Seymour Geisser.  On methods in the analysis of profile data.  Psychometrika, 24(2):95–112, 1959.
  * [12] Jie Gui, Zhenan Sun, Yonggang Wen, Dacheng Tao, and Jieping Ye.  A review on generative adversarial networks: Algorithms, theory, and applications, 2020.
  * [13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [14] Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen.  Progressive growing of gans for improved quality, stability, and variation.  In International Conference on Learning Representations, 2018.
  * [15] H. Kim, L. Remaggi, P. J. B. Jackson, and A. Hilton.  Immersive spatial audio reproduction for vr/ar using room acoustic modelling from 360° images.  In 2019 IEEE Conference on Virtual Reality and 3D User Interfaces (VR), pages 120–126, 2019.
  * [16] Homare Kon and Hideki Koike.  Deep neural networks for cross-modal estimations of acoustic reverberation characteristics from two-dimensional images.  In Audio Engineering Society, 05 2018.
  * [17] Homare Kon and Hideki Koike.  Estimation of late reverberation characteristics from a single two-dimensional environmental image using convolutional neural networks.  Journal of the Audio Engineering Society, 67:540–548, 08 2019.
  * [18] Homare Kon and Hideki Koike.  An auditory scaling method for reverb synthesis from a single two-dimensional image.  Acoustical Science and Technology, 41(4):675–685, 2020.
  * [19] Keun Sup Lee, Nicholas J Bryan, and Jonathan S Abel.  Approximating measured reverberation using a hybrid fixed/switched convolution structure.  In Proceedings of the 13th International Conference on Digital Audio Effects (DAFx’10), 2010.
  * [20] Dingzeyu Li, Timothy R. Langlois, and Changxi Zheng.  Scene-aware audio for 360° videos.  ACM Trans. Graph., 37(4), July 2018.
  * [21] Laurens van der Maaten and Geoffrey Hinton.  Visualizing data using t-sne.  Journal of machine learning research, 9(Nov):2579–2605, 2008.
  * [22] Xudong Mao, Qing Li, Haoran Xie, Raymond YK Lau, Zhen Wang, and Stephen Paul Smolley.  Least squares generative adversarial networks.  In Proceedings of the IEEE international conference on computer vision, pages 2794–2802, 2017.
  * [23] Z. Meng, F. Zhao, and M. He.  The just noticeable difference of noise length and reverberation perception.  In 2006 International Symposium on Communications and Information Technologies, pages 418–421, 2006.
  * [24] Fabian Mentzer, George D Toderici, Michael Tschannen, and Eirikur Agustsson.  High-fidelity generative image compression.  Advances in Neural Information Processing Systems, 33, 2020.
  * [25] Mehdi Mirza and Simon Osindero.  Conditional generative adversarial nets.  arXiv preprint arXiv:1411.1784, 2014.
  * [26] Damian T Murphy and Simon Shelley.  Openair: An interactive auralization web resource and database.  In Audio Engineering Society Convention 129. Audio Engineering Society, 2010.
  * [27] Egon S Pearson, Ralph B D “’AGOSTINO, and Kimiko O Bowman.  Tests for departure from normality: Comparison of powers.  Biometrika, 64(2):231–246, 1977.
  * [28] Renato S Pellegrini.  Quality assessment of auditory virtual environments.  In Proceedings of the 2001 International Conference on Auditory Display, 2001.
  * [29] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, and Scott Gray.  Dall·e: Creating images from text.  OpenAI Blog, 2021.
  * [30] Anton Ratnarajah, Zhenyu Tang, and Dinesh Manocha.  Ir-gan: Room impulse response generator for speech augmentation, 2021\.
  * [31] Andrew Reilly and David McGrath.  Convolution processing for realistic reverberation.  In Audio Engineering Society Convention 98. Audio Engineering Society, 1995.
  * [32] Luca Remaggi, Hansung Kim, Philip JB Jackson, and Adrian Hilton.  Reproducing real world acoustics in virtual reality using spherical cameras.  In Proceedings of the 2019 AES International Conference on Immersive and Interactive Audio. Audio Engineering Society, 2019.
  * [33] Michael Rettinger.  Reverberation chambers for broadcasting and recording studios.  Journal of the Audio Engineering Society, 5(1):18–22, 1957.
  * [34] H Robjohns.  Sony dre s777 sampling digital reverb.  Sound on Sound, 15, 1999.
  * [35] Kaushal Sali and Alexander Lerch.  Generating impulse responses using recurrent neural networks, 2020.
  * [36] Carl Schissler and Dinesh Manocha.  Interactive sound propagation and rendering for large multi-source scenes.  ACM Trans. Graph., 36(4), Sept. 2016.
  * [37] M. R. Schroeder and B. F. Logan.  “Colorless” Artificial Reverberation.  IRE Transactions on Audio, 9(6):209–214, 1961.
  * [38] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In Proceedings of the IEEE international conference on computer vision, pages 618–626, 2017.
  * [39] Christian Steinmetz.  Neuralreverberator, 2018.
  * [40] James Traer and Josh H McDermott.  Statistics of natural reverberation enable perceptual separation of sound and space.  Proceedings of the National Academy of Sciences, 113(48):E7856–E7865, 2016.
  * [41] Vesa Valimaki, Julian D Parker, Lauri Savioja, Julius O Smith, and Jonathan S Abel.  Fifty years of artificial reverberation.  IEEE Transactions on Audio, Speech, and Language Processing, 20(5):1421–1448, 2012.
  * [42] Aäron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alexander Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu.  Wavenet: A generative model for raw audio.  In Arxiv, 2016.
  * [43] Zhou Wang, Alan C Bovik, Hamid R Sheikh, and Eero P Simoncelli.  Image quality assessment: from error visibility to structural similarity.  IEEE transactions on image processing, 13(4):600–612, 2004.
  * [44] Bolei Zhou, Agata Lapedriza, Jianxiong Xiao, Antonio Torralba, and Aude Oliva.  Learning deep features for scene recognition using places database.  Advances in Neural Information Processing Systems, 1(January):487–495, 2014.

##  Appendix A Supplementary Material

As supplementary material, we present and review a number of input/output
examples across several categories with distinct properties333Link to
audiovisual examples page: https://web.media.mit.edu/ nsingh1/image2reverb/. A
summary of these results is shown in Table 6. We additionally present a more
detailed diagram of our architecture, shown in Fig. 23.

Finally, to gain a qualitative view of intra-scene and adjacent-scene
consistency, we plot our test set input images according to the corresponding
output audio characteristics by a visualization shown in Figure 24. We produce
multiband $T_{60}$ estimations from all output IRs, and then used t-SNE [21]
to reduce the data dimensionality to two dimensions. We then solve a linear
assignment problem to transform this into a grid representation. Several
instances of within-scene clusters are visible, as well as closeness of
related scenes. This suggests that while our method does make errors (outliers
are also visible), it learns to treat similar scenes similarly while capturing
variation.

Topic | Figure # | Images
---|---|---
Famous and iconic places | 13 | 6
Musical environments | 14 | 6
Artistic renderings | 15 | 6
DALL•E-generated spaces | 16 | 6
Limitations (i.e. challenging examples) | 17 | 4
Animated scenes | 18 | 6
Virtual backgrounds | 19 | 6
Historical places | 20 | 5
Video games | 21 | 4
Common and identifiable scenes | 22 | 6
Total |  | 55
Table 6: Additional Results. Figure 13: Famous and iconic spaces. Columns show
input images, depth maps, generated IRs, and a dry anechoic speech signal
before and after the generated IR was applied to the signal via convolution.
The input images come from spaces that may be impractical or impossible to
record in. The indoor spaces here show longer impulse responses compared to
the outdoor scenes which is typically observed and expected in real-world
settings. Larger indoor spaces also tend to exhibit greater $T_{60}$ times
with longer impulse responses which we see here, though the ISS image has a
longer impulse response than we expect. Figure 14: Music. Columns show input
images, depth maps, generated IRs, and an anechoic vocal singing signal before
and after the generated IR was applied to the signal via convolution. The
input images come from spaces relevant to music including a typical small
room, an acoustically treated rehearsal space, an auditorium, a church, and 2
large concert halls. Generally, larger spaces tend to exhibit longer decay
times in the output, however some examples such as the concert halls with
visible acoustic treatment appear to have a shorter decay than more
reverberant spaces like the church or auditorium with more reflective
surfaces. The final concert hall shows an atypical impulse response with a
visible discontinuity in the IR tail. This is not commonly observed among our
model outputs, but illustrates the nature of artifacts which can occasionally
occur. Figure 15: Art. Columns show input images, depth maps, generated IRs,
and an anechoic operatic singing signal before and after the generated IR was
applied to the signal via convolution. Images here are drawings, paintings and
a vintage art photograph ca. 1850. Artistic depictions of spaces were not
included in our training dataset. In many cases, plausible impulse responses
are generated from such input images. In general, larger depicted spaces, like
the church in the bottom row, exhibit longer decay times as is observed with
standard 2D photographs. Figure 16: DALL·E. Images generated from text by
DALL·E [29] used here as input images. The same corresponding input text was
synthesized via text-to-speech as our signal of interest and convolved with
the generated IR. This reflects synthetic speech in a synthetic environment,
indicating a path for synthesizing realistic IRs from text. It also shows how
our model might work with other state-of-the-art generative media models to
produce more consistent and realistic results in different domains. Figure 17:
Challenging images. Input images containing street murals, reflections, and
shadows demonstrating cases where depth is inaccurately estimated. (A) A
painted doorway giving the illusion of depth. (B) A wall with a mural of a
street and tree where the depth of the wall is inaccurately estimated. (C) A
low-angle photo of a reflective puddle. (D) An outdoor street image with
strong shadows which results in a depth map and generated IR more similar to a
room than an outdoor space. These more extreme scenarios are chosen to clearly
illustrate the limitations of our approach. Figure 18: Animated films. Scenes
from Blender open animation films used as input images (speech convolved with
generated IRs). Columns show input image, calculated depth map, spectrogram of
generated IR, an anechoic passage reading sample, and the same passage with
the generated IR applied via convolution. In general, we find that our model
plausibly estimates the reverberant characteristics of these spaces. For
example, the wooden small space is very brief. The barbershop appears longer
due to some artefacts, but the broadband decay is relatively quick as can be
heard in the audio. Seemingly larger spaces again correspond to longer IRs.
This is a case of Real2Sim transfer, where we can approximate IRs directly
that sound as measured IRs, but in virtual environments where this measurement
is not possible. Figure 19: Virtual backgrounds. Images which may serve as
virtual backgrounds used as input images to our model. These reflect spaces
that may be used for videoconferencing or other online meetings. Realistic IRs
may be generated and used in these contexts to increase the sense of being in
a shared space with others. Figure 20: Historical and notable places.
Additional examples of unusual and historical spaces which may be difficult or
impossible to obtain IRs from. Figure 21: Video games. Impulse responses
generated and applied via convolution from screenshots of four 3D video games.
Video games are one example of a virtual space that might benefit from easily
generated impulse responses. While the medium sized room from Counter-Strike
and the large hallway from Halo 2 may be plausible IRs, the large hall shown
in the Skyrim screenshot and the cavern in the Minecraft example do not have
correspondingly long reverberant tails as would be expected showing possible
examples of where the scale of the space was not accurately estimated. 3D
rendered images were not included in our dataset but are a ripe area of future
work which might greatly increase the performance of our model on both real
scenes and virtual scenes such as these video game examples. Figure 22: Common
and identifiable scenes. Input images and the resulting IRs are shown and
convolved with an anechoic speech signal. Input images here reflect spaces
that are regularly encountered in everyday life yet may not often be recorded
in. These types of scenes are useful for audio post-production as they may be
commonly found in movies and television shows. Small and outdoor scenes are
observed to have very brief IRs while in comparison, the larger building
interior has a much longer output IR as expected. Figure 23: Detailed overview
of Image2Reverb model architecture. Left: the ResNet50 encoder pre-trained on
Places365 (figure at left adapted from [13]). Right: the generator and
discriminator. The output of the encoder consists of 365 features, to which we
concatenate noise to produce a 512d latent vector. The generator and
discriminator contain upsampling and downsampling convolutions respectively. A
leaky rectified linear unit (LReLU), with $\alpha=0.2$, is used after each
convolutional layer in the model in both the discriminator and the generator
with the final layer of the generator using a $\tanh$ activation. PN denotes
pixelwise normalization, which we use in the generator. The composition of
blocks is based on ProGAN [14]. The final step in the discriminator is a fully
connected layer with a linear activation (scalar output). Figure 24: Manifold-
based visualization of our test set. We compute multi-band $T_{60}$ estimates
for output audio IRs for each image, and then perform nonlinear dimensionality
reduction with t-SNE to obtain two-dimensional feature vectors for each
example. We produce a grid by solving a linear assignment problem, as is
commonly done to visualize large image datasets. Our visualization shows local
clusters of same and similar scenes in many cases, but also some variation
within scenes. In some outdoor settings, this variation grows considerably
large, resulting in increased scattering. In other cases, we observe closeness
between different views of the same scene and similar scenes.


11institutetext: Institute of Theoretical Computer Science, TU Dresden,
Germany 22institutetext: Interactive Media Lab Dresden, TU Dresden, Germany
22email<EMAIL_ADDRESS>22email: julian.mendez2@tu-
dresden.de

#  : Interactive Proof Visualization for Description Logics (System
Description) — Extended Version

Christian Alrabbaa  11 Franz Baader  11 Stefan Borgwardt  11 Raimund Dachselt
22 Patrick Koopmann  11 Julián Méndez  22

###### Abstract

Explanations for description logic (DL) entailments provide important support
for the maintenance of large ontologies. The “justifications” usually employed
for this purpose in ontology editors pinpoint the parts of the ontology
responsible for a given entailment. Proofs for entailments make the
intermediate reasoning steps explicit, and thus explain how a consequence can
actually be derived. We present an interactive system for exploring
description logic proofs, called , which visualizes proofs of consequences for
ontologies written in expressive DLs. We describe the methods used for
computing those proofs, together with a feature called _signature-based proof
condensation_. Moreover, we evaluate the quality of generated proofs using
real ontologies.

##  1 Introduction

Proofs generated by Automated Reasoning (AR) systems are sometimes presented
to humans in textual form to convince them of the correctness of a theorem
[12, 8], but more often employed as certificates that can automatically be
checked [23]. In contrast to the AR setting, where very long proofs may be
needed to derive a deep mathematical theorem from very few axioms, DL-based
ontologies are often very large, but proofs of a single consequence are
usually of a more manageable size. For this reason, the standard method of
explanation in description logic [7] has long been to compute so-called
_justifications_ , which point out a minimal set of source statements
responsible for an entailment of interest. For example, the ontology editor
Protégé111https://protege.stanford.edu/ supports the computation of
justifications since 2008 [14], which is very useful when working with large
DL ontologies. Nevertheless, it is often not obvious why a given consequence
actually follows from such a justification [15]. Recently, this explanation
capability has been extended towards showing full _proofs_ with intermediate
reasoning steps, but this is restricted to ontologies written in the
lightweight DLs supported by the Elk reasoner [18, 17], and the graphical
presentation of proofs is very basic.

In this paper, we present as an interactive system, for exploring DL proofs
for description logic entailments, using the methods for computing small
proofs presented in [2, 4]. Initial prototypes of were presented in [5, 9],
but since then, many improvements were implemented. While does more than just
visualizing proofs, this paper focuses on the proof component of :
specifically, we give a brief overview of the interface for exploring proofs,
describe the proof generation methods implemented in the back-end, and present
an experimental evaluation of these proofs generation methods in terms of
proof size and run time. The improved back-end uses Java libraries that
extract proofs using various methods, such as from the Elk calculus, or
_forgetting-based proofs_ [2] using the forgetting tools Lethe [19] and Fame
[25] in a black-box fashion. The new front-end is visually more appealing than
the prototypes presented in [5, 9], and allows to inspect and explore proofs
using various interaction techniques, such as zooming and panning, collapsing
and expanding, text manipulation, and compactness adjustments. Additional
features include the minimization of the generated proofs according to various
measures and the possibility to select a _known signature_ that is used to
automatically hide parts of the proofs that are assumed to be obvious for
users with certain previous knowledge. Our evaluation shows that proof sizes
can be significantly reduced in this way, making the proofs more user-
friendly. Evonne can be tried online and downloaded at https://imld.de/evonne.
The version of described in this paper, as well as the data and scripts used
in our experiments, can be found at [1].

##  2 Preliminaries

We recall some relevant notions for DLs; for a detailed introduction, see [7].
DLs are decidable fragments of first-order logic (FOL) with a special,
variable-free syntax, and that use only unary and binary predicates, called
_concept names_ and _role names_ , respectively. These can be used to build
complex _concepts_ , which correspond to first-order formulas with one free
variable, and _axioms_ corresponding to first-order sentences. Which kinds of
concepts and axioms can be built depends on the expressivity of the used DL.
Here we mainly consider the light-weight DL $\mathcal{E}\mathcal{LH}$ and the
more expressive $\mathcal{ALCH}$. We have the usual notion of FOL _entailment_
$\mathcal{O}\models\alpha$ of an axiom $\alpha$ from a finite set of axioms
$\mathcal{O}$, called an ontology. Of special interest are entailments of
_atomic CIs_ (concept inclusions) of the form $A\sqsubseteq B$, where $A$ and
$B$ are concept names. Following [2], we define _proofs_ of
$\mathcal{O}\models\alpha$ as finite, acyclic, directed hypergraphs, where
vertices $v$ are labeled with axioms $\ell(v)$ and hyperedges are of the form
$(S,d)$, with $S$ a set of vertices and $d$ a vertex such that $\\{\ell(v)\mid
v\in S\\}\models\ell(d)$; the leaves of a proof must be labeled by elements of
$\mathcal{O}$ and the root by $\alpha$. In this paper, all proofs are _trees_
, i.e. no vertex can appear in the first component of multiple hyperedges (see
Fig. 1).

##  3 The Graphical User Interface

Figure 1: Overview of - a condensed proof in the bidirectional layout

The user interface of is implemented as a web application. To support users in
understanding large proofs, they are offered various layout options and
interaction components. The proof visualization is linked to a second view
showing the context of the proof in a relevant subset of the ontology. In this
ontology view, interactions between axioms are visualized, so that users can
understand the context of axioms occurring in the proof. The user can also
examine possible ways to eliminate unwanted entailments in the ontology view.
The focus of this system description, however, is on the proof component: we
describe how the proofs are generated and how users can interact with the
proof visualization. For details on the ontology view, we refer the reader to
the workshop paper [5], where we also describe how supports ontology repair.

##### Initialization.

After starting for the first time, users create a new project, for which they
specify an ontology file. They can then select an entailed atomic CI to be
explained. The user can choose between different proof methods, and optionally
select a signature of _known terms_ (cf. Sec. 4), which can be generated using
the term selection tool Protégé-TS [16].

##### Layout.

Proofs are shown as graphs with two kinds of vertices: colored vertices for
axioms, gray ones for inference steps. By default, proofs are shown using a
_tree layout_. To take advantage of the width of the display when dealing with
long axioms, it is possible to show proofs in a _vertical layout_ , placing
axioms linearly below each other, with inferences represented through edges on
the side (without the inference vertices). It is possible to automatically re-
order vertices to minimize the distance between conclusion and premises in
each step. The third layout option is the _bidirectional layout_ (see Fig. 1),
a tree layout where, initially, the entire proof is collapsed into a _magic
vertex_ that links the conclusion directly to its justification, and from
which individual inference steps can be pulled out and pushed back from both
directions.

##### Exploration.

In all views, each vertex is equipped with multiple functionalities for
exploring a proof. For proofs generated with Elk, clicking on an inference
vertex shows the inference rule used, and the particular inference with
relevant sub-elements highlighted in different colors. Axiom vertices show
different button (, , , ) when hovered over. In the standard tree layout,
users can hide sub-proofs under an axiom (). They can also reveal the previous
inference step () or the entire-sub-proof (). In the vertical layout, the
button () highlights and explains the inference of the current axiom. In the
bidirectional layout, the arrow buttons are used for pulling inference steps
out of the magic vertex, as well as pushing them back in.

##### Presentation.

A _minimap_ allows users to keep track of the overall structure of the proof,
thus enriching the zooming and panning functionality. Users can adjust width
and height of proofs through the options side-bar. Long axiom labels can be
_shortened_ in two ways: either by setting a fixed size to all vertices, or by
abbreviating names based on capital letters. Afterwards, it is possible to
restore the original labels individually.

##  4 Proof Generation

To obtain the proofs that are shown to the user, we implemented different
proof generation techniques, some of which were initially described in [2].
For $\mathcal{E}\mathcal{LH}$ ontologies, proofs can be generated natively by
the DL reasoner Elk [18]. These proofs use rules from the calculus described
in [18]. We apply the Dijkstra-like algorithm introduced in [3, 4] to compute
a _minimized proof_ from the Elk output. This minimization can be done w.r.t.
different measures, such as the size, depth, or weighted sum (where each axiom
is weighted by its size), as long as they are _monotone_ and _recursive_ [4].
For ontologies outside of the $\mathcal{E}\mathcal{LH}$ fragment, we use the
forgetting-based approach originally described in [2], for which we now
implemented two alternative algorithms for computing more compact proofs (Sec.
4.1). Finally, independently of the proof generation method, one can specify a
signature of known terms. This signature contains terminology that the user is
familiar with, so that entailments using only those terms do not need to be
explained. The condensation of proofs w.r.t. signatures is described in Sec.
4.2.

###  4.1 Forgetting-Based Proofs

In a forgetting-based proof, proof steps represent inferences on concept or
role names using a _forgetting_ operation. Given an ontology $\mathcal{O}$ and
a predicate name $x$, the result $\mathcal{O}^{-x}$ of forgetting $x$ in
$\mathcal{O}$ does not contain any occurrences of $x$, while still capturing
all entailments of $\mathcal{O}$ that do not use $x$ [20]. In a forgetting-
based proof, an inference takes as premises a set $\mathcal{P}$ of axioms and
has as conclusion some axiom $\alpha\in\mathcal{P}^{-x}$ (where a particular
forgetting operation is used to compute $\mathcal{P}^{-x}$). Intuitively,
$\alpha$ is obtained from $\mathcal{P}$ by performing inferences on $x$. To
compute a forgetting-based proof, we have to forget the names occuring in the
ontology one after the other, until only the names occurring in the statement
to be proved are left. For the forgetting operation, the user can select
between two implementations: Lethe [19] (using the method supporting
$\mathcal{ALCH}$) and Fame [25] (using the method supporting
$\mathcal{ALCOI}$). Since the space of possible inference steps is
exponentially large, it is not feasible to minimize proofs after their
computation, as we do for $\mathcal{E}\mathcal{L}$ entailments, which is why
we rely on heuristics and search algorithms to generate small proofs.
Specifically, we implemented three methods for computing forgetting-based
proofs: HEUR tries to find proofs fast, SYMB tries to minimize the number of
predicates forgotten in a proof, with the aim of obtaining proofs of small
depth, and SIZE tries to optimize the size of the proof. The heuristic method
HEUR is described in [2], and its implementation has not been changed since
then. The search methods SYMB and SIZE are new (details can be found in the
appendix).

###  4.2 Signature-Based Proof Condensation

When inspecting a proof over a real-world ontology, different parts of the
proof will be more or less familiar to the user, depending on their knowledge
about the involved concepts or their experience with similar inference steps
in the past. For CIs between concepts for which a user has application
knowledge, they may not need to see a proof, and consequently, sub-proofs for
such axioms can be automatically hidden. We assume that the user’s knowledge
is given in the form of a _known signature_ $\Sigma$ and that axioms that
contain only symbols from $\Sigma$ do not need to be explained. The effect can
be seen in Fig. 1 through the “known”-inference on the left, where $\Sigma$
contains $\mathsf{SebaceousGland}$ and $\mathsf{Gland}$. The known signature
is taken into consideration when minimizing the proofs, so that proofs are
selected for which more of the known information can be used if convenient.
This can be easily integrated into the Dijsktra approach described in [2], by
initially assigning to each axiom covered by $\Sigma$ a proof with a single
vertex.

##  5 Evaluation

For to be usable in practice, it is vital that proofs are computed efficiently
and that they are not too large. An experimental evaluation of minimized
proofs for $\mathcal{E}\mathcal{L}$ and forgetting-based proofs obtained with
Fame and Lethe is provided in [2]. We here present an evaluation of additional
aspects: 1) a comparison of the three methods for computing forgetting-based
proofs, and 2) an evaluation on the impact of signature-based proof
condensation. All experiments were performed on Debian Linux (Intel Core
i5-4590, 3.30 GHz, 23 GB Java heap size).

###  5.1 Minimal Forgetting-Based Proofs

$0$$10$$20$$30$$40$$50$$60$$70$$0$$10$$20$$30$$40$$50$$60$$70$HEURSYMB/SIZEProof
sizeSYMBSIZE

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$HEURSYMB/SIZERun
time (ms)

Figure 2: Run times and proof sizes for different forgetting-based proof
methods. Marker size indicates how often each pattern occurred in the
BioPortal snapshot. Instances that timed out were assigned size $0$.

To evaluate forgetting-based proofs, we extracted $\mathcal{ALCH}$ “proof
tasks” from the ontologies in the 2017 snapshot of BioPortal [22]. We
restricted all ontologies to $\mathcal{ALCH}$ and collected all entailed
atomic CIs $\alpha$, for each of which we computed the union $\mathcal{U}$ of
all their justifications. We identified pairs $(\alpha,\mathcal{U})$ that were
isomorphic modulo renaming of predicates, and kept only those patterns
$(\alpha,\mathcal{U})$ that contained at least one axiom not expressible in
$\mathcal{E}\mathcal{LH}$. This was successful in 373 of the ontologies222The
other ontologies could not be processed in this way within the memory limit.
and resulted in 138 distinct _justification patterns_ $(\alpha,\mathcal{U})$,
representing 327 different entailments in the BioPortal snapshot. We then
computed forgetting-based proofs for $\mathcal{U}\models\alpha$ with our three
methods using Lethe, with a 5-minute timeout. This was successful for 325/327
entailments for the heuristic method (HEUR), 317 for the symbol-minimizing
method (SYMB), and 279 for the size-minimizing method (SIZE). In Fig. 2 we
compare the resulting _proof sizes_ (left) and the _run times_ (right), using
HEUR as baseline (x-axis). HEUR is indeed faster in most cases, but SIZE
reduces proof size by 5% on average compared to HEUR, which is not the case
for SYMB. Regarding _proof depth_ (not shown in the figure), SYMB did not
outperform HEUR on average, while SIZE surprisingly yielded an average
reduction of $4\%$ compared to HEUR. Despite this good performance of SIZE for
proof size and depth, for entailments that depend on many or complex axioms,
computation times for both SYMB and SIZE become unacceptable, while proof
generation with HEUR mostly stays in the area of seconds.

###  5.2 Signature-Based Proof Condensation

To evaluate how much hiding proof steps in a known signature decreases proof
size in practice, we ran experiments on the large medical ontology SNOMED CT
(International Edition, July 2020) that is mostly formulated in
$\mathcal{E}\mathcal{LH}$.333https://www.snomed.org/ As signatures we used
SNOMED CT _Reference Sets_
,444https://confluence.ihtsdotools.org/display/DOCRFSPG/2.3.+Reference+Set
which are restricted vocabularies for specific use cases. We extracted
justifications similarly to the previous experiment, but did not rename
predicates and considered only proof tasks that use at least $5$ symbols from
the signature, since otherwise no improvement can be expected by using the
signatures. For each signature, we randomly selected 500 out of 6.689.452
_proof tasks_ (if at least 500 existed). This left the 4 reference sets
_General Practitioner/Family Practitioner_ (GPFP), _Global Patient Set_ (GPS),
_International Patient Summary_ (IPS), and the one included in the SNOMED CT
distribution (DEF). For each of the resulting 2.000 proof tasks, we used Elk
[18] and our proof minimization approach to obtain (a) a proof of minimal size
and (b) a proof of minimal size after hiding the selected signature. The
distribution of proof sizes can be seen in Fig. 3. In 770/2.000 cases, a
smaller proof was generated when using the signature. In 91 of these cases,
the size was even be reduced to 1, i.e. the target axiom used only the given
signature and therefore nothing else needed to be shown. In the other 679
cases with reduced size, the average _ratio_ of reduced size to original size
was 0.68–0.93 (depending on the signature). One can see that this ratio is
correlated with the _signature coverage_ of the original proof (i.e. the ratio
of signature symbols to total symbols in the proof), with a weak or strong
correlation depending on the signature ($r$ between $-0.26$ and $-0.74$).
However, a substantial number of proofs with relatively high signature
coverage could still not be reduced in size at all (see the top right of the
right diagram). In summary, we can see that signature-based condensation can
be useful, but this depends on the proof task and the signature.

$0$$50$$100$$150$$200$$250$$300$$0$$50$$100$$150$$200$$250$$300$OriginalCondensedProof
SizeDEFGPFPGPSIPS

$0$$20$$40$$60$$80$$100$$0$$20$$40$$60$$80$$100$Signature Coverage (%)Ratio of
Proof Size (%)Original vs. Condensed

Figure 3: Size of original and condensed proofs (left). Ratio of proof size
depending on the signature coverage (right).

We also conducted experiments on the Galen
ontology,555https://bioportal.bioontology.org/ontologies/GALEN with comparable
results (see the appendix).

##  6 Conclusion

We have presented and compared the proof generation and presentation methods
used in , a visual tool for explaining entailments of DL ontologies. While
these methods produce smaller or less deep proofs, which are thus easier to
present, there is still room for improvements. Specifically, as the
forgetting-based proofs do not provide the same degree of detail as the Elk
proofs, it would be desirable to also support methods for more expressive DLs
that generate proofs with smaller inference steps. Moreover, our current
evaluation focuses on proof size and depth—to understand how well helps users
to understand DL entailments, we would also need a qualitative evaluation of
the tool with potential end-users. We are also working on explanations for
non-entailments using countermodels [6] and a plugin for the ontology editor
Protégé that is compatible with the PULi library and Proof Explanation plugin
presented in [17], which will support all proof generation methods discussed
here and more.666https://github.com/de-tu-dresden-inf-lat/evee

####  6.0.1 Acknowledgements

This work was supported by the German Research Foundation (DFG) in Germany’s
Excellence Strategy: EXC-2068, 390729961 – Cluster of Excellence “Physics of
Life” and EXC 2050/1, 390696704 – Cluster of Excellence “Centre for Tactile
Internet” (CeTI) of TU Dresden, by DFG grant 389792660 as part of TRR 248 –
CPEC, and the DFG Research Training Group QuantLA, GRK 1763.

## References

  * [1] Alrabbaa, C., Baader, F., Borgwardt, S., Dachselt, R., Koopmann, P., Méndez, J.: Evonne: Interactive Proof Visualization for Description Logics (System Description) - IJCAR22 - Resources (May 2022). https://doi.org/10.5281/zenodo.6560603
  * [2] Alrabbaa, C., Baader, F., Borgwardt, S., Koopmann, P., Kovtunova, A.: Finding small proofs for description logic entailments: Theory and practice. In: Albert, E., Kovács, L. (eds.) Proceedings of the 23rd International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR 2020). EPiC Series in Computing, vol. 73, pp. 32–67. EasyChair (2020). https://doi.org/10.29007/nhpp
  * [3] Alrabbaa, C., Baader, F., Borgwardt, S., Koopmann, P., Kovtunova, A.: On the complexity of finding good proofs for description logic entailments. In: Borgwardt, S., Meyer, T. (eds.) Proceedings of the 33rd International Workshop on Description Logics (DL 2020). CEUR Workshop Proceedings, vol. 2663. CEUR-WS.org (2020), http://ceur-ws.org/Vol-2663/paper-1.pdf
  * [4] Alrabbaa, C., Baader, F., Borgwardt, S., Koopmann, P., Kovtunova, A.: Finding good proofs for description logic entailments using recursive quality measures. In: Platzer, A., Sutcliffe, G. (eds.) Proceedings of the 28th International Conference on Automated Deduction (CADE-28). Lecture Notes in Computer Science, vol. 12699, pp. 291–308. Springer (2021). https://doi.org/10.1007/978-3-030-79876-5˙17
  * [5] Alrabbaa, C., Baader, F., Dachselt, R., Flemisch, T., Koopmann, P.: Visualising proofs and the modular structure of ontologies to support ontology repair. In: Borgwardt, S., Meyer, T. (eds.) Proceedings of the 33rd International Workshop on Description Logics (DL 2020). CEUR Workshop Proceedings, vol. 2663. CEUR-WS.org (2020), http://ceur-ws.org/Vol-2663/paper-2.pdf
  * [6] Alrabbaa, C., Hieke, W., Turhan, A.: Counter model transformation for explaining non-subsumption in $\mathcal{EL}$. In: Beierle, C., Ragni, M., Stolzenburg, F., Thimm, M. (eds.) Proceedings of the 7th Workshop on Formal and Cognitive Reasoning. CEUR Workshop Proceedings, vol. 2961, pp. 9–22. CEUR-WS.org (2021), http://ceur-ws.org/Vol-2961/paper˙2.pdf
  * [7] Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic. Cambridge University Press (2017). https://doi.org/10.1017/9781139025355
  * [8] Fiedler, A.: Natural language proof explanation. In: Mechanizing Mathematical Reasoning, Essays in Honor of Jörg H. Siekmann on the Occasion of His 60th Birthday. pp. 342–363. Springer (2005). https://doi.org/10.1007/978-3-540-32254-2˙20
  * [9] Flemisch, T., Langner, R., Alrabbaa, C., Dachselt, R.: Towards designing a tool for understanding proofs in ontologies through combined node-link diagrams. In: Ivanova, V., Lambrix, P., Pesquita, C., Wiens, V. (eds.) Proceedings of the Fifth International Workshop on Visualization and Interaction for Ontologies and Linked Data (VOILA 2020). CEUR Workshop Proceedings, vol. 2778, pp. 28–40. CEUR-WS.org (2020), http://ceur-ws.org/Vol-2778/paper3.pdf
  * [10] Glimm, B., Horrocks, I., Motik, B., Stoilos, G., Wang, Z.: HermiT: An OWL 2 reasoner. J. Autom. Reason. 53(3), 245–269 (2014). https://doi.org/10.1007/s10817-014-9305-1
  * [11] Grau, B.C., Horrocks, I., Kazakov, Y., Sattler, U.: Modular reuse of ontologies: Theory and practice. J. Artif. Intell. Res. 31, 273–318 (2008). https://doi.org/10.1613/jair.2375
  * [12] Horacek, H.: Presenting proofs in a human-oriented way. In: Ganzinger, H. (ed.) 16th International Conference on Automated Deduction (CADE-16). Lecture Notes in Computer Science, vol. 1632, pp. 142–156. Springer (1999). https://doi.org/10.1007/3-540-48660-7˙10
  * [13] Horridge, M., Bechhofer, S.: The OWL API: a java API for OWL ontologies. Semantic Web 2(1), 11–21 (2011). https://doi.org/10.3233/SW-2011-0025
  * [14] Horridge, M., Parsia, B., Sattler, U.: Explanation of OWL entailments in Protege 4. In: Bizer, C., Joshi, A. (eds.) Proceedings of the Poster and Demonstration Session at the 7th International Semantic Web Conference (ISWC 2008). CEUR Workshop Proceedings, vol. 401. CEUR-WS.org (2008), http://ceur-ws.org/Vol-401/iswc2008pd˙submission˙47.pdf
  * [15] Horridge, M., Parsia, B., Sattler, U.: Justification oriented proofs in OWL. In: Patel-Schneider, P.F., Pan, Y., Hitzler, P., Mika, P., Zhang, L., Pan, J.Z., Horrocks, I., Glimm, B. (eds.) Proc. of the 9th International Semantic Web Conference (ISWC 2010). Lecture Notes in Computer Science, vol. 6496, pp. 354–369. Springer (2010). https://doi.org/10.1007/978-3-642-17746-0˙23
  * [16] Hyland, I., Schmidt, R.A.: Protégé-TS: An OWL ontology term selection tool. In: Borgwardt, S., Meyer, T. (eds.) Proceedings of the 33rd International Workshop on Description Logics (DL 2020). CEUR Workshop Proceedings, vol. 2663. CEUR-WS.org (2020), http://ceur-ws.org/Vol-2663/paper-12.pdf
  * [17] Kazakov, Y., Klinov, P., Stupnikov, A.: Towards reusable explanation services in protege. In: Artale, A., Glimm, B., Kontchakov, R. (eds.) Proceedings of the 30th International Workshop on Description Logics (DL 2017). CEUR Workshop Proceedings, vol. 1879. CEUR-WS.org (2017), http://ceur-ws.org/Vol-1879/paper31.pdf
  * [18] Kazakov, Y., Krötzsch, M., Simancik, F.: The incredible ELK - from polynomial procedures to efficient reasoning with $\mathcal{EL}$ ontologies. J. Autom. Reason. 53(1), 1–61 (2014). https://doi.org/10.1007/s10817-013-9296-3
  * [19] Koopmann, P.: LETHE: Forgetting and uniform interpolation for expressive description logics. Künstliche Intell. 34(3), 381–387 (2020). https://doi.org/10.1007/s13218-020-00655-w
  * [20] Koopmann, P., Schmidt, R.A.: Forgetting concept and role symbols in $\mathcal{ALCH}$-ontologies. In: McMillan, K.L., Middeldorp, A., Voronkov, A. (eds.) Proc. of the 19th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR-19). Lecture Notes in Computer Science, vol. 8312, pp. 552–567. Springer (2013). https://doi.org/10.1007/978-3-642-45221-5˙37
  * [21] Lutz, C., Wolter, F.: Foundations for uniform interpolation and forgetting in expressive description logics. In: Walsh, T. (ed.) Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011). pp. 989–995. IJCAI/AAAI (2011). https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-170
  * [22] Matentzoglu, N., Parsia, B.: Bioportal snapshot 30.03.2017 (Mar 2017). https://doi.org/10.5281/zenodo.439510
  * [23] Reger, G., Suda, M.: Checkable proofs for first-order theorem proving. In: Reger, G., Traytel, D. (eds.) 1st International Workshop on Automated Reasoning: Challenges, Applications, Directions, Exemplary Achievements (ARCADE 2017). EPiC Series in Computing, vol. 51, pp. 55–63. EasyChair (2017). https://doi.org/10.29007/s6d1
  * [24] Schlobach, S., Cornet, R.: Non-standard reasoning services for the debugging of description logic terminologies. In: Gottlob, G., Walsh, T. (eds.) Proc. of the 18th Int. Joint Conf. on Artificial Intelligence (IJCAI 2003). pp. 355–362. Morgan Kaufmann, Acapulco, Mexico (2003), http://ijcai.org/Proceedings/03/Papers/053.pdf
  * [25] Zhao, Y., Schmidt, R.A.: FAME: an automated tool for semantic forgetting in expressive description logics. In: Galmiche, D., Schulz, S., Sebastiani, R. (eds.) Proceedings of the 9th International Joint Conference on Automated Reasoning (IJCAR 2018). Lecture Notes in Computer Science, vol. 10900, pp. 19–27. Springer (2018). https://doi.org/10.1007/978-3-319-94205-6˙2

##  Appendix 0.A Appendix

###  0.A.1 Algorithms Used for Computing Forgetting-Based Proofs

We have implemented three algorithms for generating forgetting-based proofs,
which trade off computation time against the size of the proof. The heuristic
method is the recommended option, as it is the fastest and provides reasonably
good solutions (see Sec. 5.1). The others are more costly, and minimize size
and number of symbols eliminated, respectively. We recommend users to use the
heuristic method first to get an idea — if the number of concept names
occurring in the proof is not too large, they can then try out one of the
alternative options to get a nicer proof.

Preliminaries. Forgetting was already defined in the main text. The other
technique we use to compute minimal proofs is _justifications_ : given an
ontology $\mathcal{O}$ and an axiom $\alpha$ s.t. $\mathcal{O}\models\alpha$,
a justification for $\alpha$ in $\mathcal{O}$ is a subset-minimal
$\mathcal{J}\subseteq\mathcal{O}$ s.t. $\mathcal{J}\models\alpha$ [24]. In the
worst case, there can be exponentially many justifications for an entailment.
Our methods for computing forgetting-based proofs make use of the black-box
implementation for justifications provided by the OWL API [13], using HermiT
[10] as a reasoner. We use this functionality to extract one justification for
a given entailment, and do not compute and compare all possible
justifications. This is a source of optimization we might investigate in
future work.

Our implementations support two libraries for forgetting in DLs, Lethe [19]
and Fame [25]. Lethe allows to set a relatively robust timeout for
computations—we use this feature and set the timeout to 2 seconds (both in the
experiments and in the current prototype of ). If Lethe runs past this
timeout, we consider the forgetting operation as failed.

Heuristic Method. In order to provide a proof for $\mathcal{O}\models
A\sqsubseteq B$ , we step-wise forget all names in $\mathcal{O}$ except $A$
and $B$, ending up with an ontology that contains either $A\sqsubseteq B$
itself or some axiom from which $A\sqsubseteq B$ easily follows (e.g.
$A\sqsubseteq\bot$). Forgetting is potentially an expensive operation, and the
result of forgetting a sequence of names may be triple-exponentially larger
than the original ontology [21]. Even if this bound is rarely reached in
practice [19], we need to keep the current set of axioms small in each step,
which we do by computing justifications. Another challenge is that forgetting
a name may not always be successful, or result in an ontology that cannot be
expressed using standard DLs, in which case we have to skip forgetting that
name. The heuristic forgetting-based proof generation method generates a
sequence of ontologies as follows [2]:

  1. 1.

Set $i=0$, compute a justification $\mathcal{J}_{0}$ of $\mathcal{O}$ for
$A\sqsubseteq B$, and initialize $\Sigma$ to contain all concept and role
names that occur in $\mathcal{O}$.

  2. 2.

Repeat the following steps while $\mathcal{J}_{i}$ contains a name that is in
$\Sigma\setminus\\{A,B\\}$:

    1. (a)

Select such a name $x\in\Sigma$ following a heuristic and remove it from
$\Sigma$.

    2. (b)

Attempt to compute $(\mathcal{J}_{i})^{-x}$.

    3. (c)

If successful, set $\mathcal{J}_{i+1}$ to be a justification for $\alpha$ in
$(\mathcal{J}_{i})^{-x}$, otherwise, set $\mathcal{J}_{i+1}=\mathcal{J}_{i}$.

    4. (d)

Increment $i$.

From the resulting sequence $\mathcal{J}_{1}$, $\ldots$, $\mathcal{J}_{n}$ of
ontologies, we construct inference steps by using each axiom in
$\mathcal{J}_{i}\setminus\mathcal{J}_{i-1}$ as a conclusion and a
justification for it in $\mathcal{J}_{i-1}$ as premises. If $A\sqsubseteq
B\not\in\mathcal{J}_{n}$, we furthermore add an inference with $A\sqsubseteq
B$ as conclusion and $\mathcal{J}_{n}$ as premises (recall that
$\mathcal{J}_{n}$ is already a justification of $A\sqsubseteq B$).

The heuristic does not guarantee that we always find a proof that is optimal
in size and/or readability. To optimize size, we cannot simply apply a
Dijsktra-like algorithm on the proofs generated by the heuristic method, as we
do for the proofs generated by Elk. Without a heuristic, there are
exponentially many orders in which the names could be forgotten, in addition
to the potentially exponential number of justifications we could select in
each step. Adding to this the cost of forgetting, this means that the set of
all possible forgetting-based inference steps cannot be precomputed in
practice. Instead, in order to compute optimal proofs practically, we need to
use optimized search strategies that try to minimize the number of forgetting
operations to be performed. We implemented two such methods described in the
following. In all methods, we assume a _deterministic selection of
justifications_ , that is, we do not consider alternative justifications,
though in reality there can be exponentially many. This is to avoid further
overhead, and to keep the focus of the optimization on the forgetting
operations. We also cache forgetting results to avoid recomputations. Since
the result of forgetting role names often hides many inferences, and would
lead to proofs that are small, but not easy to understand, we only forget
concept names in the following methods. Instead, the heuristic approach is
used to complete the proof after all concept names have been eliminated using
the respective method. However, syntactic simplifications performed by the
forgetting tools have the effect that role names often still get eliminated
along the way. For example, forgetting $D$ from $\\{C\sqsubseteq\exists
r.D,C\sqsubseteq\forall r.\neg D\\}$ would result in $C\sqsubseteq\bot$ as the
result of simplifying $C\sqsubseteq\exists r.\top\sqcap\exists r.\bot$.

Symbol-Minimizing Method.  In the _symbol-minimal forgetting-based proof
generation_ we minimize the number of names that are forgotten in total.
Specifically, we explore different possible orders using a best-first
strategy: In each step, we precompute the next possible steps for
$\mathcal{J}_{i+1}$, and try them out one after the other starting with the
one that has the least number of remaining names. We keep track of the
shortest successful sequence of names (and the corresponding proof) and cancel
computation branches on which the number of forgotten names is larger.

(Weighted) Size-Optimizing Method. The _size-optimized forgetting-based proof
generation_ optimizes for size of the proof rather than on the number of
eliminated names. Specifically, it explores the space of possible inferences
using the following recursive algorithm $\texttt{Prove}(\mathcal{J},n)$ for
creating a proof for $A\sqsubseteq B$ in $\mathcal{J}$ of size at most $n$:

  1. 1.

If $n\leq 0$, FAIL.

  2. 2.

If $A\sqsubseteq B\in\mathcal{J}$, a proof with a single vertex is returned.

  3. 3.

If $A\sqsubseteq B\not\in\mathcal{J}$, but all concept names in $\mathcal{J}$
(except for $A$ and $B$) have already been eliminated, return a proof
consisting of a single inference step inferring $A\sqsubseteq B$ from a
justification of $A\sqsubseteq B$ in $\mathcal{J}$, if the justification has a
size less than $n$.

  4. 4.

Otherwise, :

  5. 5.

for every name $x\not\in\\{A,B\\}$ that can still be forgotten in
$\mathcal{J}$, attempt to compute $\mathcal{J}^{-x}$, and process each
successful $\mathcal{J}^{-x}$ in order according to a heuristic:

    1. (a)

Attempt to compute a proof for $\mathcal{J}^{-x}\models A\sqsubseteq B$ with
$\texttt{Prove}(\mathcal{J}^{-x},n-m)$, where
$m=\lvert\mathcal{J}\setminus\mathcal{J}^{-x}\rvert$ (the number of axioms
that are not used in the proof anymore).

    2. (b)

If successful, extend the obtained proof using the axioms in $\mathcal{J}$,
and update the bound $n$ with the size of this proof in case it was smaller.

  6. 6.

If no proof generation was successful, FAIL.

  7. 7.

Otherwise, return the best proof constructed.

The heuristic used to pick the next forgetting result in Step 5 evaluates each
forgetting result by its size times the number of names still occurring in
it—a rough approximation of the expected proof size. To obtain the size-
minimal forgetting-based proof for $\mathcal{O}\models\alpha$, we call
$\texttt{Prove}(\mathcal{J},n)$, where $n$ is some maximal value and
$\mathcal{J}$ a justification for $\mathcal{O}\models\alpha$.

We also allow to use a different size measure, which takes the sum of the
sizes of the axioms occurring in the proof, resulting in the _weighted size-
optimizing method._

###  0.A.2 Signature-Based Proof Condensation (Continued)

$0$$50$$100$$150$$200$$250$$300$$0$$50$$100$$150$$200$$250$$300$OriginalCondensedProof
SizeASPSSSVT

$0$$20$$40$$60$$80$$100$$0$$20$$40$$60$$80$$100$Signature Coverage (%)Ratio of
Proof Size (%)Original vs. Condensed

Figure 4: Size of original and condensed proofs (left). Ratio of proof size
depending on the signature coverage (right).

We ran another experiment, similar to the one described in Sec. 5.2, with two
main differences. First, we used another medical ontology called
Galen.777https://bioportal.bioontology.org/ontologies/GALEN Second, we
generated the signatures based on the _class hierarchy_ of Galen. In total, we
computed $35$ signatures as follows: for every concept name in the top three
levels of the class hierarchy, we extracted a module [11]. Then we used the
signature of each module to condense the proofs. For proof generation, and
analogous to the experiment of Sec. 5.2, we extracted proof tasks from Galen
that use at least $5$ symbols from a given signature. For each signature, we
randomly selected at most $1000$ out of $452.070$ tasks. For $5$ signatures,
less than $100$ tasks were extracted. Of the remaining signatures, $6$ had a
range of tasks between $273$ and $693$. Each of the rest, with a total of
$24$, had $1000$ tasks. The condensation of proofs in this experiment
exhibited a comparable behavior to the one illustrated in Fig. 3. In Fig. 4 we
show the results for a sample of the signatures (derived from the modules for
_Abstract State_ (AS), _Process State_ (PS), _State_ (S), and _Symbolic Value
Type_ (SVT)).