# A Rate-Distortion Framework for Explaining Black-box Model Decisions

Stefan Kolek  Department of Mathematics, Ludwig Maximilian University, Munich
Duc Anh Nguyen  Department of Mathematics, Ludwig Maximilian University,
Munich  Ron Levie  Department of Mathematics, Ludwig Maximilian University,
Munich  Joan Bruna  Courant Institute of Mathematical Sciences, New York
University, New York  Gitta Kutyniok  Department of Mathematics, Ludwig
Maximilian University, Munich

###### Abstract

We present the _Rate-Distortion Explanation_ (RDE) framework, a mathematically
well-founded method for explaining black-box model decisions. The framework is
based on perturbations of the target input signal and applies to any
differentiable pre-trained model such as neural networks. Our experiments
demonstrate the framework’s adaptability to diverse data modalities,
particularly images, audio, and physical simulations of urban environments.

##  1 Introduction

Powerful machine learning models such as deep neural networks are inherently
opaque, which has motivated numerous explanation methods that the research
community developed over the last decade [1, 24, 26, 20, 15, 16, 7, 2]. The
meaning and validity of an explanation depends on the underlying principle of
the explanation framework. Therefore, a trustworthy explanation framework must
align intuition with mathematical rigor while maintaining maximal flexibility
and applicability. We believe the _Rate-Distortion Explanation_ (RDE)
framework, first proposed by [16], then extended by [9], as well as the
similar framework in [2], meets the desired qualities. In this chapter, we aim
to present the RDE framework in a revised and holistic manner. Our generalized
RDE framework can be applied to any model (not just classification tasks),
supports in-distribution interpretability (by leveraging in-painting GANs),
and admits interpretation queries (by considering suitable input signal
representations).

The typical setting of a (local) explanation method is given by a pre-trained
model $\Phi:\mathbb{R}^{n}\to\mathbb{R}^{m},$ and a data instance
$x\in\mathbb{R}^{n}$. The model $\Phi$ can be either a classification task
with $m$ class labels or a regression task with $m$-dimensional model output.
The model decision $\Phi(x)$ is to be explained. In the original RDE framework
[16], an explanation for $\Phi(x)$ is a set of feature components
$S\subset\left\\{1,\ldots,n\right\\}$ in $x$ that are deemed relevant for the
decision $\Phi(x)$. The core principle behind the RDE framework is that a set
$S\subset\left\\{1,\ldots,n\right\\}$ contains all the relevant components if
$\Phi(x)$ remains (approximately) unchanged after modifying $x_{S^{c}}$, i.e.,
the components in $x$ that are not deemed relevant. In other words, $S$
contains all relevant features if they are sufficient for producing the output
$\Phi(x)$. To convey concise explanatory information, one aims to find the
_minimal set_ $S\subset\left\\{1,\ldots,n\right\\}$ with all the relevant
components. As demonstrated in [16] and [28], the minimal relevant set
$S\subset\left\\{1,\ldots,n\right\\}$ cannot be found combinatorically in an
efficient manner for large input sizes. A meaningful approximation can
nevertheless be found by optimizing a sparse continuous mask $s\in[0,1]^{n}$
that has no significant effect on the output $\Phi(x)$ in the sense that
$\Phi(x)\approx\Phi(x\odot s+(1-s)\odot v)$ should hold for appropriate
perturbations $v\in\mathbb{R}^{n}$, where $\odot$ denotes the componentwise
multiplication. Suppose $d\big{(}\Phi(x),\Phi(y)\big{)}$ is a measure of
distortion (e.g. the $\ell_{2}$-norm) between the model outputs for
$x,y\in\mathbb{R}^{n}$ and $\mathcal{V}$ is a distribution over appropriate
perturbations $v\sim\mathcal{V}$. An explanation in the RDE framework can be
found as a solution mask $s^{*}$ to the following minimization problem:

$\displaystyle
s^{*}\coloneqq\quad\operatorname*{arg\,min}_{s\in[0,1]^{n}}\mathop{\mathbb{E}}_{v\sim\mathcal{V}}\Bigg{[}d\Big{(}\Phi(x),\Phi(x\odot
s+(1-s)\odot v)\Big{)}\Bigg{]}+\lambda\|s\|_{1},$

where $\lambda>0$ is a hyperparameter controlling the sparsity of the mask.

We further generalize the RDE framework to abstract input signal
representations $x=f(h)$, where $f$ is a data representation function with
input $h$. The philosophy of the generalized RDE framework is that an
explanation for generic input signals $x=f(h)$ should be some simplified
version of the signal, which is interpretable to humans. This is achieved by
demanding sparsity in a suitable representation system $h$, which ideally
optimally represents the class of explanations that are desirable for the
underlying domain and interpretation query. This philosophy underpins our
experiments on image classification in the wavelet domain, on audio signal
classification in the Fourier domain, and on radio map estimation in an urban
environment domain. Therein we demonstrate the versatility of our generalized
RDE framework.

##  2 Related works

To our knowledge, the explanation principle of optimizing a mask
$s\in[0,1]^{n}$ has been first proposed in [7]. Fong et al. [7] explained
image classification decisions by considering one of the two deletion games:
(1) optimizing for the smallest deletion mask that causes the class score to
drop significantly or (2) optimizing for the largest deletion mask that has no
significant effect on the class score. The original RDE approach [16] is based
on the second deletion game and connects the deletion principle to rate-
distortion-theory, which studies lossy data compression. Deleted entries in
[7] were replaced with either constants, noise, or blurring and deleted
entries in [16] were replaced with noise.

Explanation methods introduced before the deletion games principle from [7]
were typically based upon gradient-based methods [24][26], propagation of
activations in neurons [1][23], surrogate models [20], and game-theory [15].
Gradient-based methods such as smoothgrad [24] suffer from a lacking principle
of relevance beyond local sensitivity. Reference-based methods such as
Integrated Gradients [26] and DeepLIFT [23] depend on a reference value, which
has no clear optimal choice. DeepLIFT and LRP assign relevance by propagating
neuron activations, which makes them dependent on the implementation of
$\Phi$. LIME [20] uses an interpretable surrogate model that approximates
$\Phi$ in a neighborhood around $x$. Surrogate model explanations are
inherently limited for complex models $\Phi$ (such as image classifiers) as
they only admit very local approximations. Generally, explanations that only
depend on the model behavior on a small neighborhood $U_{x}$ of $x$ offer
limited insight. Lastly, Shapley values-based explanations [15] are grounded
in Shapley values from game-theory. They assign relevance scores as weighted
averages of marginal contributions of respective features. Though Shapley
values are mathematically well-founded, relevance scores cannot be computed
exactly for common input sizes such as $n\geq 50$, since one exact relevance
score generally requires $O(2^{n})$ evaluations of $\Phi$ [27].

A notable difference between the RDE method and additive feature explanations
[15] is that the values in the mask $s^{*}$ do not add up to the model output.
The additive property as in [15] takes the view that features individually
contribute to the model output and relevance should be reflected by their
contributions. We emphasize that the RDE method is designed to look for a
_set_ of relevant features and _not_ an estimate of individual relative
contributions. This is particularly desirable when only groups of features are
interpretable, as for example in image classification tasks, where individual
pixels do not carry any interpretable meaning. Similarly to Shapley values,
the explanation in the RDE framework cannot be computed exactly, as it
requires solving a non-convex minimization problem. However, the RDE method
can take full advantage of modern optimization techniques. Furthermore, the
RDE method is a model-agnostic explanation technique, with a mathematically
principled and intuitive notion of relevance as well as enough flexibility to
incorporate the model behavior on meaningful input regions of $\Phi$.

The meaning of an explanation based on deletion masks $s\in[0,1]^{n}$ depends
on the nature of the perturbations that replace the deleted regions. Random
[16] [7] or blurred [7] replacements $v\in\mathbb{R}^{n}$ may result in a data
point $x\odot s+(1-s)\odot v$ that falls out of the natural data manifold on
which $\Phi$ was trained on. This is a subtle though important problem, since
such an explanation may depend on evaluations of $\Phi$ on data points from
undeveloped decision regions. The latter motivates _in-distribution
interpretability_ , which considers meaningful perturbations that keep $x\odot
s+(1-s)\odot v$ in the data manifold. [2] was the first work that suggested to
use an inpainting-GAN to generate meaningful perturbations to the deletion
games. The authors of [9] then applied in-distribution interpretability to the
RDE method in the challenging modalities _music_ and _physical simulations of
urban environments_. Moreover, they demonstrated that the RDE method in [16]
can be extended to answer so-called _interpretation queries_. For example, the
RDE method was applied in [9] to an instrument classifier to answer the global
interpretation query _Is magnitude or phase in the signal more important for
the classifier?_. Most recently, in [11], we introduced CartoonX as a novel
explanation method for image classifiers, answering the interpretation query
_“What is the relevant piece-wise smooth part of an image?”_ by applying RDE
in the wavelet basis of images.

##  3 Rate-distortion explanation framework

Based on the original RDE approach from [16], in this section, we present a
general formulation of the RDE framework and discuss several implementations.
While [16] focuses merely on image classification with explanations in pixel
representation, we will apply the RDE framework not only to more challenging
domains but also to different input signal representations. Not surprisingly,
the combinatorical optimization problem in the RDE framework, even in simpler
form, is extremely hard to solve [16] [28]. This motivates heuristic solution
strategies, which will be discussed in Subsection 3.2.

###  3.1 General formulation

It is well-known that in practice there are different ways to describe a
signal $x\in\mathbb{R}^{n}$. Generally speaking, $x$ can be represented by a
data representation function
$f:\prod_{i=1}^{k}\mathbb{R}^{d_{i}}\to\mathbb{R}^{n}$,

$\displaystyle x=f(h_{1},\ldots,h_{k}),$ (1)

for some inputs $h_{i}\in\mathbb{R}^{d_{i}}$, $d_{i}\in\mathbb{N}$,
$i\in\left\\{1,\ldots,k\right\\}$, $k\in\mathbb{N}$. Note, we do not restrict
ourselves to linear data representation functions $f$. To briefly illustrate
the generality of this abstract representation, we consider the following
examples.

######  Example 1 (Pixel representation)

An arbitrary (vectorized) image $x\in\mathbb{R}^{n}$ can be simply represented
pixelwise

$\displaystyle x=\begin{bmatrix}x_{1}\\\ \vdots\\\
x_{n}\end{bmatrix}=f(h_{1},\ldots,h_{n}),$

with $h_{i}\coloneqq x_{i}$ being the individual pixel values and
$f\colon\mathbb{R}^{n}\to\mathbb{R}^{n}$ being the identity transform.

Due to its simplicity, this standard basis representation is a reasonable
choice when explaining image classification models. However, in many other
applications, one requires more sophisticated representations of the signals,
such as through a possibly redundant dictionary.

###### Example 2

Let $\left\\{\psi_{j}\right\\}_{j=1}^{k}$, $k\in\mathbb{N}$, be a dictionary
in $\mathbb{R}^{n}$, e.g., a basis. A signal $x\in\mathbb{R}^{n}$ is
represented as

$\displaystyle x=\sum_{j=1}^{k}h_{j}\psi_{j},$

where $h_{j}\in\mathbb{R}$, $j\in\left\\{1,\ldots,k\right\\}$, are appropriate
coefficients. In terms of the abstract representation eq. 1, we have $d_{j}=1$
for $j\in\left\\{1,\ldots,k\right\\}$ and $f$ is the function that yields the
weighted sum over $\psi_{j}$. Note that Example 1 can be seen as a special
case of this representation.

The following gives an example of a non-linear representation function $f$.

###### Example 3

Consider the discrete inverse Fourier transform, defined as

$\displaystyle
f:\prod_{j=1}^{n}\mathbb{R}_{+}\times\prod_{j=1}^{n}[0,2\pi]\to\mathbb{C}^{n},$
$\displaystyle\big{[}f(m_{1},...,m_{n},\omega_{1},...,\omega_{n})\big{]}_{l}\coloneqq\frac{1}{n}\sum_{j=1}^{n}\underbrace{m_{j}e^{i\omega_{j}}}_{\coloneqq
c_{j}\in\mathbb{C}}e^{i2\pi l(j-1)/n},\;l\in\left\\{1,\ldots,n\right\\},$

where $m_{j}$ and $\omega_{j}$ are respectively the magnitude and the phase of
the $j$-th discrete Fourier coefficient $c_{j}$. Thus every signal
$x\in\mathbb{R}^{n}\subseteq\mathbb{C}^{n}$ can be represented in terms of eq.
1 with $f$ being the discrete inverse Fourier transform while $h_{j}$,
$j=1,\ldots,k$ (with $k=2n$) being specified as $m_{j^{\prime}}$ and
$\omega_{j^{\prime}}$, $j^{\prime}=1,\ldots,n$.

Further examples of dictionaries $\left\\{\psi_{j}\right\\}_{j=1}^{k}$ include
the discrete wavelet [21], cosine [19] or shearlet [12] representation systems
and many more. In these cases, the coefficients $h_{i}$ are given by the
forward transform and $f$ is referred to as the backward transform. Note that
in the above examples we have $d_{i}=1$, i.e., the input vectors $h_{i}$ are
real-valued. In many situations, one is also interested in representations
$x=f(h_{1},\ldots,h_{k})$ with $h_{i}\in\mathbb{R}^{d_{i}}$ where $d_{i}>1$.

###### Example 4

Let $k=2$ and define $f$ again as the discrete inverse Fourier transform, but
as a function of two components: (1) the entire magnitude spectrum and (2) the
entire frequency spectrum, namely

$\displaystyle f:\mathbb{R}_{+}^{n}\times[0,2\pi]^{n},$
$\displaystyle\big{[}f(m,\omega)\big{]}_{l}\coloneqq\frac{1}{n}\sum_{j=1}^{n}\underbrace{m_{j}e^{i\omega_{j}}}_{\coloneqq
c_{n}\in\mathbb{C}}e^{i2\pi l(j-1)/n},\;l\in\left\\{1,\ldots,n\right\\}.$

Similarly, instead of individual pixel values, one can consider patches of
pixels in an image $x\in\mathbb{R}^{n}$ from Example 1 as the input vectors
$h_{i}$ to the identity transform $f$. We will come back to these examples in
the experiments in Section 4.

Finally, we would like to remark that our abstract representation

$x=f(h_{1},\ldots,h_{k})$

also covers the cases where the signal is the output of a decoder or
generative model $f$ with inputs $h_{1},\ldots,h_{k}$ as the code or the
latent variables.

As was discussed in previous sections, the main idea of the RDE framework is
to extract the relevant features of the signal based on the optimization over
its perturbations defined through masks. The ingredients of this idea are
formally defined below.

######  Definition 1 (Obfuscations and expected distortion)

Let $\Phi:\mathbb{R}^{n}\to\mathbb{R}^{m}$ be a model and $x\in\mathbb{R}^{n}$
a data point with a data representation $x=f(h_{1},...,h_{k})$ as discussed
above. For every mask $s\in[0,1]^{k}$, let $\mathcal{V}_{s}$ be a probability
distribution over $\prod_{i=1}^{k}\mathbb{R}^{d_{i}}$. Then the _obfuscation_
of $x$ with respect to $s$ and $\mathcal{V}_{s}$ is defined as the random
vector

$y\coloneqq f(s\odot h+(1-s)\odot v),$

where $v\sim\mathcal{V}_{s}$, $(s\odot h)_{i}=s_{i}h_{i}\in\mathbb{R}^{d_{i}}$
and $((1-s)\odot v)_{i}=(1-s_{i})v_{i}\in\mathbb{R}^{d_{i}}$ for
$i\in\left\\{1,\ldots,k\right\\}$. Furthermore, the _expected distortion_ of
$x$ with respect to the mask $s$ and the perturbation distribution
$\mathcal{V}_{s}$ is defined as

$D(x,s,\mathcal{V}_{s},\Phi)\coloneqq\mathop{\mathbb{E}}_{v\sim\mathcal{V}_{s}}\Bigg{[}d\Big{(}\Phi(x),\Phi(y)\Big{)}\Bigg{]},$

where $d:\mathbb{R}^{m}\times\mathbb{R}^{m}\to\mathbb{R}_{+}$ is a measure of
distortion between two model outputs.

In the RDE framework, the explanation is given by a mask that minimizes
distortion while remaining relatively sparse. The rate-distortion-explanation
mask is defined in the following.

######  Definition 2 (The RDE mask)

In the setting of Definition 1 we define the _RDE mask_ as a solution
$s^{*}(\ell)$ to the minimization problem

$\displaystyle\min_{s\in\\{0,1\\}^{k}}\quad
D(x,s,\mathcal{V}_{s},\Phi)\quad\text{ s.t.
}\quad\left\|s\right\|_{0}\leq\ell,$ (2)

where $\ell\in\left\\{1,\ldots,k\right\\}$ is the desired level of sparsity.

Here, the RDE mask is defined as the binary mask that minimizes the expected
distortion while keeping the sparsity smaller than a certain threshold.
Besides this, one could obviously also define the RDE mask as the sparsest
binary mask that keeps the distortion lower than a given threshold, as defined
in [16]. Geometrically, one can interpret the RDE mask as a subspace that is
stable under $\Phi$. If $x=f(h)$ is the input signal and $s$ is the RDE mask
for $\Phi(x)$ on the coefficients $h$, then the associated subspace
$R_{\Phi}(s)$ is defined as the space of feasible obfuscations of $x$ with $s$
under $\mathcal{V}_{s}$, i.e.,

$R_{\Phi}(s)\coloneqq\\{f(s\odot h+(1-s)\odot
v)\;|\;v\in\text{supp}\mathcal{V}_{s}\\},$

where $\text{supp}\mathcal{V}_{s}$ denotes the support of the distribution
$\mathcal{V}_{s}$. The model $\Phi$ will act similarly on signals in
$R_{\Phi}(s)$ due to the low expected distortion
$D(x,s,\mathcal{V}_{s},\Phi)$—making the subspace stable under $\Phi$. Note
that RDE directly optimizes towards a subspace that is stable under $\Phi$.
If, instead, one would choose the mask $s$ based on information of the
gradient $\nabla\Phi(x)$ and Hessian $\nabla^{2}\Phi(x)$, then only a local
neighborhood around $x$ would tend to be stable under $\Phi$ due to the local
nature of the gradient and Hessian. Before discussing practical algorithms to
approximate the RDE mask in Subsection 3.2, we will review frequently used
obfuscation strategies, i.e., the distribution $\mathcal{V}_{s}$, and measures
of distortion.

####  3.1.1 Obfuscation strategies and in-distribution interpretability.

The meaning of an explanation in RDE depends greatly on the nature of the
perturbations $v\sim\mathcal{V}_{s}$. A particular choice of $\mathcal{V}_{s}$
defines an _obfuscation strategy_. Obfuscations are either _in-distribution_ ,
i.e., if the obfuscation

$f(s\odot h+(1-s)\odot v)$

lies on the natural data manifold that $\Phi$ was trained on, or _out-of-
distribution_ otherwise. Out-of-distribution obfuscations pose the following
problem. The RDE mask (see Definition 2) depends on evaluations of $\Phi$ on
obfuscations $f(s\odot h+(1-s)\odot v)$. If $f(s\odot h+(1-s)\odot v)$ is not
on the natural data manifold that $\Phi$ was trained on, then it may lie in
undeveloped regions of $\Phi$. In practice, we are interested in explaining
the behavior of $\Phi$ on realistic data and an explanation can be corrupted
if $\Phi$ did not develop the region of out-of distribution points $f(s\odot
h+(1-s)\odot v)$. One can guard against this by choosing $\mathcal{V}_{s}$ so
that $f(s\odot h+(1-s)\odot v)$ is in-distribution. Choosing $\mathcal{V}_{s}$
in-distribution boils down to modeling the conditional data distribution – a
non-trivial task.

######  Example 5 (In-distribution obfuscation strategy)

In light of the recent success of generative adversarial networks (GANs) in
generative modeling [8], one can train an in-painting GAN [29]

$G(h,s,z)\in\prod_{i=1}^{k}\mathbb{R}^{d_{i}},$

where $z$ are random latent variables of the GAN, such that the obfuscation
$f\big{(}s\odot h+(1-s)\odot G(h,s,z)\big{)}$ lies on the natural data
manifold (see also [2]). In other words, one can choose $\mathcal{V}_{s}$ as
the distribution of $v\coloneqq G(h,s,z)$, where the randomness comes from the
random latent variables $z$.

######  Example 6 (Out-of-distribution obfuscation strategies)

A very simple obfuscation strategy is Gaussian noise. In that case, one
defines $\mathcal{V}_{s}$ for every $s\in[0,1]^{k}$ as

$\mathcal{V}_{s}\coloneqq\mathcal{N}(\mu,\Sigma),$

where $\mu$ and $\Sigma$ denote a pre-defined mean vector and covariance
matrix. In Section 4.1, we give an example of a reasonable choice for $\mu$
and $\Sigma$ for image data. Alternatively, for images with pixel
representation (see Example 1) one can mask out the deleted pixels by blurred
inputs, $v=K*x$, where $K$ is a suitable blur kernel.

Obfuscation strategy | Perturbation formula | In-distribution
---|---|---
Constant | $v\in\mathbb{R}^{d}$ | –
Noise | $v\sim\mathcal{N}(\mu,\Sigma)$ | –
Blurring | $v=K*x$ | –
Inpainting-GAN | $v=G(h,s,z)$ | ✓
Table 1: Common obfuscation strategies with their perturbation formulas.

We summarize common obfuscation strategies for a given target signal in Table
1.

####  3.1.2 Measure of distortion.

Various options exist for the measure
$d\colon\mathbb{R}^{m}\times\mathbb{R}^{m}\to\mathbb{R}$ of the distortion
between model outputs. The measure of distortion should be chosen according to
the task of the model $\Phi:\mathbb{R}^{n}\to\mathbb{R}^{m}$ and the objective
of the explanation.

######  Example 7 (Measure of distortion for classification task)

Consider a classification model $\Phi:\mathbb{R}^{n}\to\mathbb{R}^{m}$ and a
target input signal $x\in\mathbb{R}^{n}$. The model $\Phi$ assigns to each
class $j\in\left\\{1,\ldots,m\right\\}$ a (pre-softmax) score $\Phi_{j}(x)$
and the predicted label is given by
$j^{*}\coloneqq\operatorname*{arg\,max}_{j\in\left\\{1,\ldots,m\right\\}}\Phi_{j}(x)$.
One commonly used measure of the distortion between the outputs at $x$ and
another data point $y\in\mathbb{R}^{n}$ is given as

$\displaystyle
d_{1}\big{(}\Phi(x),\Phi(y)\big{)}\coloneqq\big{(}\Phi_{j^{*}}(x)-\Phi_{j^{*}}(y)\big{)}^{2}.$

On the other hand, the vector $[\Phi_{j}(x)]_{j=1}^{m}$ is usually normalized
to a probability vector $[\tilde{\Phi}_{j}(x)]_{j=1}^{m}$ by applying the
softmax function, namely
$\tilde{\Phi}_{j}(x)\coloneqq\exp{\Phi_{j}(x)}/\sum_{i=1}^{m}\exp{\Phi_{i}(x)}$.
This, in turn, gives another measure of the distortion between
$\Phi(x),\Phi(y)\in\mathbb{R}^{m}$, namely

$\displaystyle
d_{2}\big{(}\Phi(x),\Phi(y)\big{)}\coloneqq\big{(}\tilde{\Phi}_{j^{*}}(x)-\tilde{\Phi}_{j^{*}}(y)\big{)}^{2},$

where
$j^{*}\coloneqq\operatorname*{arg\,max}_{j\in\left\\{1,\ldots,m\right\\}}\Phi_{j}(x)=\operatorname*{arg\,max}_{j\in\left\\{1,\ldots,m\right\\}}\tilde{\Phi}_{j}(x)$.
An important property of the softmax function is the invariance under
translation by a vector $[c,\ldots,c]^{\top}\in\mathbb{R}^{m}$, where
$c\in\mathbb{R}$ is a constant. By definition, only $d_{2}$ respects this
invariance while $d_{1}$ does not.

######  Example 8 (Measure of distortion for regression task)

Consider a regression model $\Phi:\mathbb{R}^{n}\to\mathbb{R}^{m}$ and an
input signal $x\in\mathbb{R}^{n}$. One can then define the measure of
distortion between the outputs of $x$ and another data point
$y\in\mathbb{R}^{n}$ as

$\displaystyle
d_{3}\big{(}(\Phi(x),\Phi(y)\big{)}\coloneqq\left\|\Phi(x)-\Phi(y)\right\|_{2}^{2}.$

Sometimes it is reasonable to consider a certain subset of components
$J\subseteq\left\\{1,\ldots,m\right\\}$ of the output vectors instead of all
$m$ entries. Denoting the vector formed by corresponding entries by
$\Phi_{J}(x)$, the measure of distortion between the outputs can be defined as

$\displaystyle
d_{4}\big{(}(\Phi(x),\Phi(y)\big{)}\coloneqq\left\|\Phi_{J}(x)-\Phi_{J}(y)\right\|_{2}^{2}.$

The measure $d_{4}$ will be used in our experiments for radio maps in
Subsection 4.3.

###  3.2 Implementation

The RDE mask from Definition 2 was defined as a solution to

$\displaystyle\min_{s\in\\{0,1\\}^{k}}\quad
D(x,s,\mathcal{V}_{s},\Phi)\quad\text{ s.t.
}\quad\left\|s\right\|_{0}\leq\ell.$

In practice, we need to relax this problem. We offer the following three
approaches.

####  3.2.1 $\ell_{1}$-relaxation with Lagrange multiplier.

The RDE mask can be approximately computed by finding an approximate solution
to the following relaxed minimization problem:

$\displaystyle\min_{s\in[0,1]^{k}}\quad
D(x,s,\mathcal{V}_{s},\Phi)+\lambda\|s\|_{1},$ ($\mathcal{P}_{1}$)

where $\lambda>0$ is a hyperparameter for the sparsity level. Note that the
optimization problem is not necessarily convex, thus the solution might not be
unique.

The expected distortion $D(x,s,\mathcal{V}_{s},\Phi)$ can typically be
approximated with simple Monte-Carlo estimates, i.e., by averaging i.i.d.
samples from $\mathcal{V}_{s}$. After estimating
$D(x,s,\mathcal{V}_{s},\Phi)$, one can optimize the mask $s$ with stochastic
gradient descent (SGD) to solve the optimization problem eq.
$\mathcal{P}_{1}$.

####  3.2.2 Bernoulli relaxation.

By viewing the binary mask as Bernoulli random variables
$s\sim\text{Ber}(\theta)$ and optimizing over $\theta$, one can guarantee that
the expected distortion $D(x,s,\mathcal{V}_{s},\Phi)$ is evaluated on binary
masks $s\in\\{0,1\\}^{n}$. To encourage sparsity of the resulting mask, one
can still apply $\ell_{1}$-regularization on $s$, giving rise to the following
optimization problem:

$\displaystyle\min_{\theta\in[0,1]^{k}}\quad\mathop{\mathbb{E}}_{s\sim\text{Ber}(\theta)}\Bigg{[}D(x,s,\mathcal{V}_{s},\Phi)\Bigg{]}+\lambda\left\|s\right\|_{1}.$
($\mathcal{P}_{2}$)

Optimizing the parameter $\theta$ requires a continuous relaxation to apply
SGD. This can be done using the concrete distribution [17], which samples $s$
from a continuous relaxation of the Bernoulli distribution.

####  3.2.3 Matching pursuit.

As an alternative, one can also perform matching pursuit [18]. Here, the non-
zero entries of $s\in\\{0,1\\}^{n}$ are determined sequentially in a greedy
fashion to minimize the resulting distortion in each step. More precisely, we
start with a zero mask $s^{0}=0$ and gradually build up the mask by updating
$s^{t}$ at step $t$ by the rule given by

$\displaystyle
s^{t+1}=s^{t}+\operatorname*{arg\,min}_{e_{j}:\,s_{j}^{t}=0}\,D(x,s^{t}+e_{j},\mathcal{V}_{s},\Phi).$

Here, the minimization is taken over all standard basis vectors
$e_{j}\in\mathbb{R}^{k}$ with $s_{j}^{t}=0$. The algorithm terminates when
reaching some desired error tolerance or after a prefixed number of
iterations. While this means that in each iteration we have to test every
entry of $s$, it is applicable when $k$ is small or when we are only
interested in very sparse masks.

##  4 Experiments

With our experiments, we demonstrate the broad applicability of the
generalized RDE framework. Moreover, our experiments illustrate how different
choices of obfuscation strategies, optimization procedures, measures of
distortion, and input signal representations, discussed in Section 3.1, can be
leveraged in practice. We explain model decisions on various challenging data
modalities and tailor the input signal representation and measure of
distortion to the domain and interpretation query. In Section 4.1, we focus on
image classification, a common baseline task in the interpretability
literature. In Sections 4.2 and 4.3, we consider two other data modalities
that are often unexplored. Section 4.2 focuses on audio data, where the
underlying task is to classify acoustic instruments based on a short audio
sample of distinct notes, while in Section 4.3, the underlying task is a
regression with data in the form of physical simulations in urban
environments. We also believe our explanation framework sustains applications
beyond interpretability tasks. An example is given in Section 4.3.2, where we
add an RDE inspired regularizer to the training objective of a radio map
estimation model.

###  4.1 Images

We begin with the most ordinary domain in the interpretability literature:
image classification tasks. The authors of [16] applied RDE to image data
before by considering pixel-wise perturbations. We refer to this method as
_Pixel RDE_. Other explanation methods [20], [1], [2], and [3], have also
previously exclusively operated in the pixel domain. In [11], we challenged
this customary practice by successfully applying RDE in a wavelet basis, where
sparsity translates into piece-wise smooth images (also called cartoon-like
images). The novel explanation method was coined _CartoonX_ [11] and extracts
the relevant piece-wise smooth part of an image. First, we review the Pixel
RDE method and present experiments on the ImageNet dataset [4], which is
commonly considered a challenging classification task. Finally, we present
CartoonX and discuss its advantages. For all the ImageNet experiments, we use
the pre-trained _MobileNetV3-Small_ [10], which achieved a top-1 accuracy of
67.668% and a top-5 accuracy of 87.402%, as the classifier.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

Figure 1: Top row: original images correctly classified as (a) snail, (b) male
duck, and (c) airplane. Middle row: Pixel RDEs. Bottom row: CartoonX. Notably,
CartoonX is roughly piece-wise smooth and overall more interpretable than the
jittery Pixel RDEs.

####  4.1.1 Pixel RDE.

Consider the following pixel-wise representation of an RGB image
$x\in\mathbb{R}^{3\times n}$:

$f:\prod_{i=1}^{n}\mathbb{R}^{3}\to\mathbb{R}^{n\times
3},\;x=f(h_{1},...,h_{n}),$

where $h_{i}\in\mathbb{R}^{3}$ represents the three color channel values of
the $i$-th pixel in the image $x$, i.e. $(x_{i,j})_{j=1,..,3}=h_{i}$. In pixel
RDE a sparse mask $s\in[0,1]^{n}$ with $n$ entries—one for each pixel—is
optimized to achieve low expected distortion $D(x,s,\mathcal{V}_{s},\Phi)$.
The obfuscation of an image $x$ with the pixel mask $s$ and a distribution
$v\sim\mathcal{V}_{s}$ on $\prod_{i=1}^{n}\mathbb{R}^{3}$ is defined as
$f(s\odot h+(1-s)\odot v)$. In our experiments, we initialize the mask with
ones, i.e., $s_{i}=1$ for every $i\in\left\\{1,\ldots,n\right\\}$, and
consider Gaussian noise perturbations
$\mathcal{V}_{s}=\mathcal{N}(\mu,\Sigma)$. We set the noise mean
$\mu\in\mathbb{R}^{3\times n}$ as the pixel value mean of the original image
$x$ and the covariance matrix
$\Sigma\coloneqq\sigma^{2}\operatorname{Id}\in\mathbb{R}^{3n\times 3n}$ as a
diagonal matrix with $\sigma>0$ defined as the pixel value standard deviation
of the original image $x$. We then optimize the pixel mask $s$ for 2000
gradient descent steps on the $\ell_{1}$-relaxation of the RDE objective (see
Section 3.2.1). We computed the distortion $d\big{(}\Phi(x),\Phi(y)\big{)}$ in
$D(x,s,\mathcal{V}_{s},\Phi)$ in the post-softmax activation of the predicted
label multiplied by a constant $C=100$, i.e.,

$\displaystyle d\big{(}\Phi(x),\Phi(y)\big{)}\coloneqq
C\big{(}\Phi_{j^{*}}(x)-\Phi_{j^{*}}(y)\big{)}^{2}.$

The expected distortion $D(x,s,\mathcal{V}_{s},\Phi)$ was approximated as a
simple Monte-Carlo estimate after sampling 64 noise perturbations. For the
sparsity level, we set the Lagrange multiplier to $\lambda=0.6$. All images
were resized to 256 $\times$ 256 pixels. The mask was optimized for 2000 steps
using the Adam optimizer with step size $0.003$. In the middle row of Figure
1, we show three example explanations with Pixel RDE for an image of a snail,
a male duck, and an airplane, all from the ImageNet dataset. Pixel RDE
highlights as relevant both the snail’s inner shell and part of its head, the
lower segment of the male duck along with various lines in the water, and the
airplane’s fuselage and part of its rudder.

####  4.1.2 CartoonX.

Formally, we represent an RGB image $x\in[0,1]^{3\times n}$ in its wavelet
coefficients $h=\\{h_{i}\\}_{i=1}^{n}\in\prod_{i=1}^{n}\mathbb{R}^{3}$ with
$J\in\left\\{{1,\ldots,\lfloor\log_{2}n\rfloor}\right\\}$ scales as $x=f(h)$,
where f is the discrete inverse wavelet transform. Each
$h_{i}=(h_{i,c})_{c=1}^{3}\subseteq\mathbb{R}^{3}$ contains three wavelet
coefficients of the image, one for each color channel and is associated with a
scale $k_{i}\in\left\\{1,\ldots,J\right\\}$ and a position in the image. Low
scales describe high frequencies and high scales describe low frequencies at
the respective image position. We briefly illustrate the wavelet coefficients
in Figure 2, which visualizes the discrete wavelet transform of an image.

(a)

(b)

Figure 2: Discrete Wavelet Transform of an image: (a) original image (b)
discrete wavelet transform. The coefficients of the largest quadrant in (b)
correspond to the lowest scale and coefficients of smaller quadrants gradually
build up to the highest scales, which are located in the four smallest
quadrants. Three nested L-shaped quadrants represent horizontal, vertical and
diagonal edges at a resolution determined by the associated scale.

CartoonX [11] is a special case of the generalized RDE framework, particularly
a special case of Example 2, and optimizes a sparse mask $s\in[0,1]^{n}$ on
the wavelet coefficients (see Figure 3(c)) so that the expected distortion
$D(x,s,\mathcal{V}_{s},\Phi)$ remains small. The obfuscation of an image $x$
with a wavelet mask $s$ and a distribution $v\sim\mathcal{V}_{s}$ on the
wavelet coefficients is $f(s\odot h+(1-s)\odot v)$. In our experiments, we
used Gaussian noise perturbations and chose the standard deviation and mean
adaptively for each scale: the standard deviation and mean for wavelet
coefficients of scale $j\in\left\\{1,\ldots,J\right\\}$ were chosen as the
standard deviation and mean of the wavelet coefficients of scale
$j\in\left\\{1,\ldots,J\right\\}$ of the original image. Figure 3(d) shows the
obfuscation $f(s\odot h+(1-s)\odot v)$ with the final wavelet mask $s$ after
the RDE optimization procedure. In Pixel RDE, the mask itself is the
explanation as it lies in pixel space (see middle row in Figure 1), whereas
the CartoonX mask lies in the wavelet domain. To go back to the natural image
domain, we multiply the wavelet mask element-wise with the wavelet
coefficients of the original greyscale image and invert this product back to
pixel space with the discrete inverse wavelet transform. The inversion is
finally clipped into $[0,1]$ as are obfuscations during the RDE optimization
to avoid overflow (we assume here the pixel values in $x$ are normalized into
$[0,1]$). The clipped inversion in pixel space is the final CartoonX
explanation (see Figure 3(e)).

(a)

(b)

(c)

(d)

(e)

(f)

Figure 3: CartoonX machinery: (a) image classified as park-bench, (b) discrete
wavelet transform of the image, (c) final mask on the wavelet coefficients
after the RDE optimization procedure, (d) obfuscation with final wavelet mask
and noise, (e) final CartoonX, (f) Pixel RDE for comparison.

$\displaystyle{0.00}$$\displaystyle{0.02}$$\displaystyle{0.04}$$\displaystyle{0.06}$$\displaystyle{0.08}$$\displaystyle{0.10}$$\displaystyle\|s\|_{1}/n$$\displaystyle{0.000}$$\displaystyle{0.025}$$\displaystyle{0.050}$$\displaystyle{0.075}$$\displaystyle{0.100}$$\displaystyle{0.125}$$\displaystyle{0.150}$$\displaystyle{0.175}$$\displaystyle{0.200}$DistortionDWT
based maskPixel based maskCenter of massCenter of mass

Figure 4: Scatter plot of rate-distortion in pixel basis and wavelet basis.
Each point is an explanation of a distinct image in the ImageNet dataset with
distortion and normalized $\ell_{1}$-norm measured for the final mask. The
wavelet mask achieves lower distortion than the pixel mask, while using less
coefficients.

The following points should be kept in mind when interpreting the final
CartoonX explanation, i.e., the inversion of the wavelet coefficient mask: (1)
CartoonX provides the relevant pice-wise smooth part of the image. (2) The
inversion of the wavelet coefficient mask was not optimized to be sparse in
pixel space but in the wavelet basis. (3) A region that is black in the
inversion could nevertheless be relevant if it was already black in the
original image. This is due to the multiplication of the mask with the wavelet
coefficients of the greyscale image before taking the discrete inverse wavelet
transform. (4) Bright high resolution regions are relevant in high resolution
and bright low resolution regions are relevant in low resolution. (5) It is
inexpensive for CartoonX to mark large regions in low resolution as relevant.
(6) It is expensive for CartoonX to mark large regions in high resolution as
relevant.

In Figure 1, we compare CartoonX to Pixel RDE. The piece-wise smooth wavelet
explanations are more interpretable than the jittery Pixel RDEs. In
particular, CartoonX asserts that the snail’s shell without the head suffices
for the classification, unlike Pixel RDE, which insinuated that both the inner
shell and part of the head are relevant. Moreover, CartoonX shows that the
water gives the classifier context for the classification of the duck, which
one could have only guessed from the Pixel RDE. Both Pixel RDE and CartoonX
state that the head of the duck is not relevant. Lastly, CartoonX, like Pixel
RDE, confirms that the wings play a subordinate role in the classification of
the airplane.

####  4.1.3 Why explain in the wavelet basis?

Wavelets provide optimal representation for piece-wise smooth 1D functions
[5], and represent 2D piece-wise smooth images, also called _cartoon-like
images_ [12], efficiently as well [21]. Indeed, sparse vectors in the wavelet
coefficient space encode cartoon-like images reasonably well [25], certainly
better than sparse pixel representations. Moreover, the optimization process
underlying CartoonX produces sparse vectors in the wavelet coefficient space.
Hence CartoonX typically generates cartoon-like images as explanations. This
is the fundamental difference to Pixel RDE, which produces rough, jittery, and
pixel-sparse explanations. Cartoon-like images are more interpretable and
provide a natural model of simplified images. Since the goal of the RDE
explanation is to generate an easy to interpret simplified version of the
input signal, we argue that CartoonX explanations are more appropriate for
image classification than Pixel RDEs. Our experiments confirm that the
CartoonX explanations are roughly piece-wise smooth explanations and are
overall more interpretable than Pixel RDEs (see Figure 1).

####  4.1.4 CartoonX implementation.

Throughout our CartoonX experiments we chose the Daubechies 3 wavelet system,
$J=5$ levels of scales and zero padding for the discrete wavelet transform.
For the implementation of the discrete wavelet transform, we used the Pytorch
Wavelets package, which supports gradient computation in Pytorch. Distortion
was computed as in the Pixel RDE experiments. The perturbations
$v\sim\mathcal{V}_{s}$ on the wavelet coefficients were chosen as Gaussian
noise with standard deviation and mean computed adaptively per scale. As in
the Pixel RDE experiments, the wavelet mask was optimized for 2000 steps with
the Adam optimizer to minimize the $\ell_{1}$-relaxation of the RDE objective.
We used $\lambda=3$ for CartoonX.

####  4.1.5 Efficiency of CartoonX.

Finally, we compare Pixel RDE to CartoonX quantitatively by analyzing the
distortion and sparsity associated with the final explanation mask.
Intuitively, we expect the CartoonX method to have an efficiency advantage,
since the discrete wavelet transform already encodes natural images sparsely,
and hence less wavelet coefficients are required to represent images than
pixel coefficients. Our experiments confirmed this intuition, as can be seen
in the scatter plot in Figure 4.

###  4.2 Audio

We consider the NSynth dataset [6], a library of short audio samples of
distinct notes played on a variety of instruments. We pre-process the data by
computing the power-normalized magnitude spectrum and phase information using
the discrete Fourier transform on a logarithmic scale from $20$ to $8000$
Hertz. Each data instance is then represented by the magnitude and the phase
of its Fourier coefficients as well as the discrete inverse Fourier transform
(see Example 2).

####  4.2.1 Explaining the classifier.

Our model $\Phi$ is a network trained to classify acoustic instruments. We
compute the distortion with respect to the pre-softmax scores, i.e., deploy
$d_{1}$ in Example 7 as the measure of distortion. We follow the obfuscation
strategy described in Example 5 and train an inpainter $G$ to generate the
obfuscation $G(h,s,z)$. Here, $h$ corresponds to the representation of a
signal, $s$ is a binary mask and $z$ is a normally distributed seed to the
generator.

We use a residual CNN architecture for $G$ with added noise in the input and
deep features. More details can be found in Section 4.2.3. We train $G$ until
the outputs are found to be satisfactory, exemplified by the outputs in Figure
5.

Figure 5: Inpainted Bass: Example inpainting from $G$. The bottom plot depicts
phase versus frequency and the top plot depicts magnitude versus frequency.
The random binary mask is represented by the green parts. The axes for the
inpainted signal (black) and the original signal (blue dashed) are offset to
improve visibility. Note how the inpainter generates plausible peaks in the
magnitude and phase spectra, especially with regard to rapid ($\geq 600$Hz)
versus smooth ($<270$Hz) changes in phase.

To compute the explanation maps, we numerically solve Equation
$\mathcal{P}_{2}$ as discussed in Subsection 3.2. In particular, $s$ is a
binary mask indicating whether the phase and magnitude information of a
certain frequency should be dropped and is specified as a Bernoulli variable
$s\sim\text{Ber}(\theta)$. We chose a regularization parameter of $\lambda=50$
and minimized the corresponding objective using the Adam optimizer with a step
size of $10^{-5}$ in $10^{6}$ iterations. For the concrete distribution, we
used a temperature of $0.1$. Two examples resulting from this process can be
seen in Figure 6.

(a) Guitar

(b) Bass

Figure 6: Interpreting NSynth Model: The optimized importance parameter
$\theta$ (green) overlayed on top of the DFT (blue). For each of guitar and
bass, the top graph shows the power-normalized magnitude and the bottom the
phase. Notice the solid peaks between 30Hz and 60Hz for guitar and between
100Hz and 230Hz for bass. These occur because the model is relying on those
parts of the spectra, for the classification. Notice also how many parts of
the spectrum are important even when the magnitude is near zero. This
indicates that the model pays attention to whether those frequencies are
missing.

Notice here that the method actually shows a strong reliance of the classifier
on low frequencies (30Hz-60Hz) to classify the top sample in Figure 6 as a
guitar, as only the guitar samples have this low frequency slope in the
spectrum. We can also see in contrast that classifying the bass sample relies
more on the continuous signal between 100Hz and 230Hz.

####  4.2.2 Magnitude vs Phase.

In the above experiment, we have represented the signals by the magnitude and
phase information at each frequency, hence the mask $s$ acts on each
frequency. Now we consider the _interpretation query_ of whether the entire
magnitude spectrum or the entire phase spectrum is more relevant for the
prediction. Accordingly, we consider the representation discussed in Example 4
and apply the mask $s$ to turn off or on the whole magnitude spectrum or the
phase information. Furthermore, we can optimize $s$ not only for one datum but
for all samples from a class. This extracts the information whether magnitude
or phase is more important for predicting samples from a specific class.

For this, we again minimized Equation $\mathcal{P}_{2}$ (meaned over all
samples of a class) with $\theta$ as the Bernoulli parameter using the Adam
optimizer for $2\times 10^{5}$ iterations with a step size of $10^{-4}$ and
the regularization parameter $\lambda=30$. Again, a temperature of $t=0.1$ was
used for the concrete distribution.

Intrument | Magnitude | Phase
---|---|---
| Importance | Importance
Organ | 0.829 | 1.0
Guitar | 0.0 | 0.999
Flute | 0.092 | 1.0
Bass | 1.0 | 1.0
Reed | 0.136 | 1.0
Vocal | 1.0 | 1.0
Mallet | 0.005 | 0.217
Brass | 0.999 | 1.0
Keyboard | 0.003 | 1.0
String | 1.0 | 0.0
Table 2: Magnitude importance versus phase importance.

From the results of these computations, which can be seen in Table 2, we can
observe that there is a clear difference on what the classifier bases its
decision on across instruments. The classification of most instruments is
largely based on phase information. For the mallet, the values are low for
magnitude and phase, which means that the expected distortion is very low
compared to the $\ell_{1}$-norm of the mask, even when the signal is
completely inpainted. This underlines that the regularization parameter
$\lambda$ may have to be adjusted for different data instances, especially
when measuring distortion in the pre-softmax scores.

####  4.2.3 Architecture of the inpainting network $G$.

Here, we briefly describe the architecture of the inpainting network $G$ that
was used to generate obfuscations to the target signals. In particular, Figure
7 shows the diagram of the network $G$ and Table 3 shows information about its
layers.

Magnitude and Phase SpectrumBinary MaskGaussian NoiseGaussian NoiseSkip
connectionSkip connection Figure 7: Diagram of the inpainting network for
NSynth.
Layer | Filter Size | Output Shape | # Params
---|---|---|---
Conv1d-1 | 21 | [-1, 32, 1024] | 4,736
ReLU-2 |  | [-1, 32, 1024] | 0
Conv1d-3 | 21 | [-1, 64, 502] | 43,072
ReLU-4 |  | [-1, 64, 502] | 0
BatchNorm1d-5 |  | [-1, 64, 502] | 128
Conv1d-6 | 21 | [-1, 128, 241] | 172,160
ReLU-7 |  | [-1, 128, 241] | 0
BatchNorm1d-8 |  | [-1, 128, 241] | 256
Conv1d-9 | 21 | [-1, 16, 112] | 43,024
ReLU-10 |  | [-1, 16, 112] | 0
BatchNorm1d-11 |  | [-1, 16, 112] | 32
ConvTranspose1d-12 | 21 | [-1, 64, 243] | 43,072
ReLU-13 |  | [-1, 64, 243] | 0
BatchNorm1d-14 |  | [-1, 64, 243] | 128
ConvTranspose1d-15 | 21 | [-1, 128, 505] | 172,160
ReLU-16 |  | [-1, 128, 505] | 0
BatchNorm1d-17 |  | [-1, 128, 505] | 256
ConvTranspose1d-18 | 20 | [-1, 64, 1024] | 163,904
ReLU-19 |  | [-1, 64, 1024] | 0
BatchNorm1d-20 |  | [-1, 64, 1024] | 128
Skip Connection |  | [-1, 103, 1024] | 0
Conv1d-21 | 7 | [-1, 128, 1024] | 92,416
ReLU-22 |  | [-1, 128, 1024] | 0
Conv1d-23 | 7 | [-1, 2, 1024] | 1,794
ReLU-24 |  | [-1, 2, 1024] | 0
Total number of parameters: |  |  | 737,266
Table 3: Layer table of the Inpainting model for the NSynth task.

###  4.3 Radio Maps

In this subsection, we assume a set of transmitting devices (Tx) broadcasting
a signal within a city. The received strength varies with location and depends
on physical factors such as line of sight, reflection, and diffraction. We
consider the regression problem of estimating a function that assigns the
proper signal strength to each location in the city. Our dataset $\mathcal{D}$
is RadioMapSeer [14] containing 700 maps, 80 Tx per map, and a corresponding
grayscale label encoding the signal strength at every location. Our model
$\Phi$ receives as input $x=[x^{(0)},x^{(1)},x^{(2)}]$, where $x^{(0)}$ is a
binary map of the Tx locations, $x^{(1)}$ is a noisy binary map of the city
(where a few buildings are missing), and $x^{(2)}$ is a grayscale image
representing a number of ground truth measurements of the strength of the
signal at the measured locations and zero elsewhere. We apply the UNet [22,
14, 13] architecture and train $\Phi$ to output the estimation of the signal
strength throughout the city that interpolates the input measurements.

Apart from the model $\Phi$, we also have a simpler model $\Phi_{0}$, which
only receives the city map and the Tx locations as inputs and is trained with
unperturbed input city maps. This second model $\Phi_{0}$ will be deployed to
inpaint measurements to input to $\Phi$. See Figure 8(a), 8(b), and 8(c) for
examples of a ground truth map and estimations for $\Phi$ and $\Phi_{0}$,
respectively.

(a) Ground Truth

(b) $\Phi$ Estimation

(c) $\Phi_{0}$ Estimation

Figure 8: Radio map estimations: The radio map (gray), input buildings (blue),
and input measurements (red).

####  4.3.1 Explaining Radio Map $\Phi$.

Observe that in Figure 8(a) there is a missing building in the input (the
black one) and in Figure 8(b), $\Phi$ in-fills this building with a shadow. As
a black box method, it is unclear why it made this decision. Did it rely on
signal measurements or on building patterns? To address this, we consider each
building as a cluster of pixels and each measurement as potential targets for
our mask $s=[s^{(1)},s^{(2)}]$, where $s^{(1)}$ acts on buildings and
$s^{(2)}$ acts on measurements. We then apply matching pursuit (see Subsection
3.2.3) to find a minimal mask $s$ of critical components (buildings and
measurements).

To be precise, suppose we are given a target input signal
$x=[x^{(0)},x^{(1)},x^{(2)}]$. Let $k_{1}$ denote the number of buildings in
$x^{(1)}$ and $k_{2}$ denote the number of measurements in $x^{(2)}$. Consider
the function $f_{1}$ that takes as inputs vectors in
$\left\\{0,1\right\\}^{k_{1}}$, which indicate the existence of buildings in
$x^{(1)}$, and maps them to the corresponding city map in the original city
map format. Analogously, consider the function $f_{2}$ that takes as input the
measurements in $\mathbb{R}^{k_{2}}$ and maps them to the corresponding
grayscale image of the original measurements format. Then, $f_{1}$ and $f_{2}$
encode the locations of the buildings and measurements in the target signal
$x=[x^{(0)},f_{1}(h^{(1)}),f_{2}(h^{(2)})]$, where $h^{(1)}$ and $h^{(2)}$
denotes the building and measurement representation of $x$ in $f_{1}$ and
$f_{2}$. When $s^{(1)}$ has a zero entry, i.e., a building in $h^{(1)}$ was
not selected, we replace the value in the obfuscation with zero (this
corresponds to a constant perturbation equal to zero). Then, the obfuscation
of the target signal $x$ with a mask $s=[s^{(1)},s^{(2)}]$ and perturbations
$v=[v^{(1)},v^{(2)}]\coloneqq[0,v^{(2)}]$ becomes:

$y\coloneqq[x^{(0)},f_{1}(s^{(1)}\odot h^{(1)}),f_{2}(s^{(2)}\odot
h^{(2)}+(1-s^{(2)})\odot v^{(2)})].$

While it is natural to model masking out a building by simply zeroing out the
corresponding cluster of pixels by choosing $v^{(1)}=0$, we need to also
properly choose $v^{(2)}$ for the entries, where the mask $s^{(2)}$ takes
value $0$, in order to obtain appropriate obfuscations. For this, we can
deploy the second model $\Phi_{0}$ as an inpainter. We consider the following
two extreme obfuscation strategies. The first is to set also $v^{(2)}$ to
zero, i.e., simply remove the unchosen measurements from the input, with the
underlying assumption being that any subset of measurements is valid for a
city map. In the other extreme case, we inpaint all unchosen measurements by
sampling at their locations the estimated radio map obtained by $\Phi_{0}$
based on the buildings selected by $s^{(1)}$.

The two extreme measurement completion methods correspond to two extremes of
the interpretation query. Filling-in the missing measurements by $\Phi_{0}$
tends to overestimate the strength of the signal because there are fewer
buildings to obstruct the transmissions. The empty mask will complete all
measurements to the maximal possible signal strength – the free space radio
map. The overestimation in signal strength is reduced when more measurements
and buildings are chosen, resulting in darker estimated radio maps. Thus, this
strategy is related to the query of which measurements and buildings are
important to darken the free space radio map, turning it to the radio map
produced by $\Phi$. In the other extreme, adding more measurements to the mask
with a fixed set of buildings typically brightens the resulting radio map.
This allows us to answer which measurements are most important for brightening
the radio map.

Between these two extreme strategies lies a continuum of completion methods
where a random subset of the unchosen measurements is sampled from $\Phi_{0}$,
while the rest are set to zero. Examples of explanations of a prediction
$\Phi(x)$ according to these methods are presented in Figure 9. Since we only
care about specific small patches exemplified by the green boxes, the
distortion here is measured with respect to the $\ell_{2}$ distance between
the output images restricted to the corresponding region (see also Example 8).

(a) Estimated map.

(b) Explanation: Inpaint all unchosen measurements.

(c) Explanation: Inpaint 2.5% of unchosen measurements.

Figure 9: Radio map queries and explanations: The radio map (gray), input
buildings (blue), input measurements (red), and area of interest (green box).
Middle represents the query “How to fill in the image with shadows”, while
right is the query “How to fill in the image both with shadows and bright
spots?”. We inpaint with $\Phi_{0}$.

When the query is how to darken the free space radio map (Figure 9(b)), the
optimized mask $s$ suggests that samples in the shadow of the missing building
are the most influential in the prediction. These dark measurements are
supposed to be in line-of-sight of a Tx, which indicates that the network
deduced that there is a missing building. When the query is how to fill in the
image both with shadows and bright spots (Figure 9(c)), both samples in the
shadow of the missing building and samples right before the building are
influential. This indicates that the network used the bright measurements in
line-of-sight and avoided predicting an overly large building. To understand
the chosen buildings, note that $\Phi$ is based on a composition of UNets and
is thus interpreted as a procedure of extracting high level and global
information from the inputs to synthesize the output. The locations of the
chosen buildings in Figure 9 reflect this global nature.

####  4.3.2 Interpretation-Driven Training.

We now discuss an example application of the explanation obtained by the RDE
approach described above, called _interpretation driven training_. When a
missing building is in line-of-sight of a Tx, we would like $\Phi$ to
reconstruct this building relying on samples in the shadow of the building
rather than patterns in the city. To reduce the reliance of $\Phi$ on the city
information in this situation, one can add a regularization term in the
training loss which promotes explanations relying on measurements.

(a) Vanilla $\Phi$ estimation

(b) Interpretation-driven $\Phi_{\text{int}}$ estimation

(c) Vanilla $\Phi$ explanation

(d) Interpretation-driven $\Phi_{\text{int}}$ explanation

Figure 10: Radio map estimations, interpretation driven training vs vanilla
training: The radio map (gray), input buildings (blue), input measurements
(red), and domain of the missing building (green box).

Suppose $x=[x^{(0)},x^{(1)},x^{(2)}]$ contains a missing input building in
line-of-sight of the Tx location and denote the subset of pixels of the
missing building in the city map as $J_{x}$. Denote the prediction by $\Phi$
restricted to the subset $J_{x}$ as $\Phi_{J_{x}}$. Moreover, define
$\tilde{x}\coloneqq[x^{(0)},0,x^{(2)}]$ to be the modification of $x$ with all
input buildings masked out. We then define the _interpretation loss_ for $x$
as

$\displaystyle\ell_{\text{int}}(\Phi,x)\coloneqq\left\|\Phi_{J_{x}}(x)-\Phi_{J_{x}}(\tilde{x})\right\|_{2}^{2}.$

The interpretation driven training objective then regularizes $\Phi$ during
training by adding the interpretation loss for all inputs $x$ that contain a
missing input building in line-of-sight of the Tx location. An example
comparison between explanations of the vanilla RadioUNet $\Phi$ and the
interpretation driven network $\Phi_{\text{int}}$ is given in Figure 10.

##  5 Conclusion

In this work, we presented the _Rate-Distortion Explanation_ (RDE) framework
in a revised and comprehensive manner. Our framework is flexible enough to
answer various interpretation queries by considering suitable data
representations tailored to the underlying domain and query. We demonstrate
the latter and the overall efficacy of the RDE framework on an image
classification task, on an audio signal classification task, and on a radio
map estimation task, a seldomly explored regression task.

## References

  * [1] Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Müller, and Wojciech Samek.  On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation.  PLoS ONE, 10(7):e0130140, 2015.
  * [2] Chun-Hao Chang, Elliot Creager, Anna Goldenberg, and David Duvenaud.  Explaining image classifiers by counterfactual generation.  In Proceedings of the 7th International Conference on Learning Representations, ICLR, 2019.
  * [3] Piotr Dabkowski and Yarin Gal.  Real time image saliency for black box classifiers.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, NeurIPS, page 6970–6979, 2017.
  * [4] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  ImageNet: A large-scale hierarchical image database.  In Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition, CVPR, pages 248–255, 2009.
  * [5] Ronald A. DeVore.  Nonlinear approximation.  Acta Numerica, 7:51–150, 1998.
  * [6] Jesse Engel, Cinjon Resnick, Adam Roberts, Sander Dieleman, Mohammad Norouzi, Douglas Eck, and Karen Simonyan.  Neural audio synthesis of musical notes with wavenet autoencoders.  In Proceedings of the 34th International Conference on Machine Learning, ICML, volume 70, page 1068–1077, 2017.
  * [7] R. C. Fong and A. Vedaldi.  Interpretable explanations of black boxes by meaningful perturbation.  In Proceedings of 2017 IEEE International Conference on Computer Vision (ICCV), pages 3449–3457, 2017.
  * [8] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In Proceedings of the 27th International Conference on Neural Information Processing Systems, NeurIPS, page 2672–2680, 2014.
  * [9] Cosmas Heiß, Ron Levie, Cinjon Resnick, Gitta Kutyniok, and Joan Bruna.  In-distribution interpretability for challenging modalities.  Preprint arXiv:2007.00758, 2020.
  * [10] Andrew Howard, Mark Sandler, Bo Chen, Weijun Wang, Liang-Chieh Chen, Mingxing Tan, Grace Chu, Vijay Vasudevan, Yukun Zhu, Ruoming Pang, Hartwig Adam, and Quoc Le.  Searching for MobileNetV3.  In Proceedings of the 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 1314–1324, 2019.
  * [11] Stefan Kolek, Duc Anh Nguyen, Ron Levie, Joan Bruna, and Gitta Kutyniok.  Cartoon explanations of image classifiers.  arXiv: 2110.03485, 2021.
  * [12] Gitta Kutyniok and Wang-Q Lim.  Compactly supported shearlets are optimally sparse.  Journal of Approximation Theory, 163(11):1564–1589, 2011.
  * [13] Ron Levie, Cagkan Yapar, Gitta Kutyniok, and Giuseppe Caire.  Pathloss prediction using deep learning with applications to cellular optimization and efficient d2d link scheduling.  In ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8678–8682, 2020.
  * [14] Ron Levie, Cagkan Yapar, Gitta Kutyniok, and Giuseppe Caire.  RadioUNet: Fast radio map estimation with convolutional neural networks.  IEEE Transactions on Wireless Communications, 20(6):4001–4015, 2021\.
  * [15] Scott M. Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, NeurIPS, page 4768–4777, 2017.
  * [16] Jan Macdonald, Stephan Wäldchen, Sascha Hauch, and Gitta Kutyniok.  A rate-distortion framework for explaining neural network decisions.  Preprint arXiv:1905.11092, 2019.
  * [17] Chris J. Maddison, Andriy Mnih, and Yee Whye Teh.  The concrete distribution: A continuous relaxation of discrete random variables.  Preprint arXiv:1611.00712, 2016.
  * [18] S.G. Mallat and Zhifeng Zhang.  Matching pursuits with time-frequency dictionaries.  IEEE Transactions on Signal Processing, 41(12):3397–3415, 1993\.
  * [19] M. Narasimha and A. Peterson.  On the computation of the discrete cosine transform.  IEEE Transactions on Communications, 26(6):934–936, 1978.
  * [20] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  ”Why should I trust you?”: Explaining the predictions of any classifier.  In Proceedings of the 22nd International Conference on Knowledge Discovery and Data Mining, ACM SIGKDD, page 1135–1144. Association for Computing Machinery, 2016.
  * [21] Justin K. Romberg, Michael B. Wakin, and Richard G. Baraniuk.  Wavelet-domain approximation and compression of piecewise smooth images.  IEEE Trans. Image Processing, 15:1071–1087, 2006.
  * [22] O. Ronneberger, P.Fischer, and T. Brox.  U-Net: Convolutional networks for biomedical image segmentation.  In Medical Image Computing and Computer-Assisted Intervention (MICCAI), volume 9351 of LNCS, pages 234–241, 2015.
  * [23] Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje.  Learning important features through propagating activation differences.  In Proceedings of the 34th International Conference on Machine Learning, ICML, volume 70, page 3145–3153, 2017.
  * [24] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg.  Smoothgrad: removing noise by adding noise.  In Workshop on Visualization for Deep Learning, ICML, 2017.
  * [25] Mallat Stéphane.  Chapter 11.3.  In Mallat Stéphane, editor, A Wavelet Tour of Signal Processing (Third Edition), pages 535–610. Academic Press, Boston, third edition edition, 2009.
  * [26] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  In Proceedings of the 34th International Conference on Machine Learning, ICML, volume 70, page 3319–3328, 2017.
  * [27] Jacopo Teneggi, Alexandre Luster, and Jeremias Sulam.  Fast hierarchical games for image explanations.  Preprint arXiv:2104.06164, 2021.
  * [28] Stephan Wäldchen, Jan Macdonald, Sascha Hauch, and Gitta Kutyniok.  The computational complexity of understanding network decisions.  Preprint arXiv:1905.09163, 2019.
  * [29] Jiahui Yu, Zhe Lin, Jimei Yang, Xiaohui Shen, Xin Lu, and Thomas S. Huang.  Generative image inpainting with contextual attention.  In Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR, pages 5505–5514, 2018.