# Model-Agnostic Explainability for Visual Search

Mark Hamilton  Scott Lundberg  Lei Zhang  Stephanie Fu  William T. Freeman

###### Abstract

What makes two images similar? We propose new approaches to generate model-
agnostic explanations for image similarity, search, and retrieval. In
particular, we extend Class Activation Maps (CAMs), Additive Shapley
Explanations (SHAP), and Locally Interpretable Model-Agnostic Explanations
(LIME) to the domain of image retrieval and search. These approaches enable
black and grey-box model introspection and can help diagnose errors and
understand the rationale behind a model’s similarity judgments. Furthermore,
we extend these approaches to extract a full pairwise correspondence between
the query and retrieved image pixels, an approach we call “joint
interpretations”. Formally, we show joint search interpretations arise from
projecting Harsanyi dividends, and that this approach generalizes Shapley
Values and The Shapley-Taylor indices. We introduce a fast kernel-based method
for estimating Shapley-Taylor indices and empirically show that these game-
theoretic measures yield more consistent explanations for image similarity
architectures.

Machine Learning, ICML

##  1 Introduction

Text, image, and audio search engines are ubiquitous in our everyday life and
help us navigate a world of information orders of magnitude larger than any
one human could read in their lifetime. Search engines are growing
increasingly complicated and can utilize billion-parameter models (Nayak,
2019). Despite search’s foundational importance, there is a lack of principled
techniques to understand the rationale behind a search engine’s matches and
responses. At its core, these systems face the same challenges that
classifiers and regressors face: richer model spaces can improve performance
but yield un-interpretable models. For high-risk domains like medicine,
incorrect search results could result in serious consequences. In other
domains, bias in a search engine can disproportionately hide certain voices
and have far-reaching systemic consequences.

Figure 1: Architectures for search engine interpretability. Top: Standard
classifier interpretation that highlights pixels that contribute to the
prediction. Middle: Our marginal search interpretation architecture modifies
the classifier interpretation architecture to highlight pixels that contribute
to the similarity between images. Bottom: “Joint” search interpretation
extracts a full pairwise correspondence between objects in the query and
retrieved image, all while treating the search engine as a black box. Figure
2: Comparison of marginal search interpretation methods. All methods identify
pixels that most contribute to the image’s similarity. One exception is
Integrated Gradients which struggles, in part because well trained classifiers
are invariant to minor pixel changes and which results in uninformative
gradients.

To help solve this challenge, we present a unified framework for extending
model interpretability to search engines, recommendation systems, and
retrieval systems. With these tools, practitioners can gain insight into the
rationales behind their algorithm’s matches without knowledge of an
algorithm’s internal construction. We explore this topic through the lens of
visual search, but note that these techniques could also apply to text,
tabular, or audio systems. This work identifies two distinct ways to interpret
search engines: “Marginal Interpretations” highlight the most important pixels
in the match and “Joint Interpretations” extract a full correspondence between
query and retrieved image pixels. To extract marginal interpretations we
introduce a generic transformation, as shown in Figure 1, to transform search
engines and retrieval systems into “classifiers” that can be interpreted with
existing classifier interpretation methods. To extract joint interpretations,
we present new bi-linear generalizations of Class Activation Maps (Zhou et
al., 2016), LIME (Ribeiro et al., 2016), and SHAP (Lundberg & Lee, 2017).
These joint interpretations are new to the literature and give practitioners
tools to understand search engines with much greater nuance and detail.
Formally, we axiomatically characterize joint interpretations and show that
projecting Harsanyi Dividends (Harsanyi, 1963) provides a unique solution to
this characterization. This not only extends a correspondence between model
explainability and cooperative game theory, but also yields better empirical
results on a search engine evaluated on the PASCAL VOC dataset (Everingham et
al., 2010). In summary:

  * •

We introduce and evaluate new, model-agnostic, methods for interpreting search
engines and recommendation systems.

  * •

We extend existing approaches to extract full pairwise correspondences between
item characteristics from similarity judgments.

  * •

We relate search engine interpretability to the theory of Harsanyi Dividends,
and show that this provides a simple way to calculate optimal credit-
assignment schemes for more complex settings like search.

##  2 Background

This work focuses on search, retrieval, and recommendation architectures.
Often, these systems use similarity between objects or learned features
(Bengio et al., 2013) to rank, retrieve, or suggest content (Bing, 2017; Su &
Khoshgoftaar, 2009). More formally, we refer to systems that leverage a
distance, relevance, or similarity functions of the form:
$d:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ to quantify the relationship
between items from sets $\mathcal{X}$ and $\mathcal{Y}$. In search and
retrieval, $\mathcal{X}$ represents the space of search queries and
$\mathcal{Y}$ represents the space of results, the function $d$ assigns a
relevance to each query result pair. Finding the most relevant results for a
query $x\in\mathcal{X}$ takes the form:

$\operatorname*{arg\,max}_{y\in\mathcal{Y}}d(x,y)$

Specializing this notion yields a variety of different kinds of ML systems. If
$\mathcal{X}=\mathcal{Y}=\operatorname*{Range}(\mathcal{N}(\cdot))$ where
$\mathcal{N}$ is an image featurization network such as ResNet50 (He et al.,
2016), the formalism yields a visual search engine or “reverse image search”.
Though this work focuses on visual search, we note that if $\mathcal{X}$ is
the space of character sequences and $\mathcal{Y}$ is the space of webpages,
this represents web search. If $\mathcal{X}$ are users and $\mathcal{Y}$ are
the space of items, such as songs or news articles, the formalism represents a
recommendation problem. In this work we aim to extract meaningful
“interpretations” or “explanations” of the function $d$.

###  2.1 Model Interpretability

The Bias-Variance trade-off (Kohavi et al., 1996) affects all machine learning
systems and governs the relationship between a model’s expressiveness and
generalization ability. In data-rich scenarios, generalization error is
dominated by a model’s bias and increasing the size of the model class can
improve performance. However, increasing model complexity can severely degrade
its “interpretability”. Larger model classes have more parameters to interpret
and these parameters can lose their connection to physically meaningful
quantities. This is a challenge not just for classification and regression
systems, but for search and recommendation architectures as well. For example,
the best performing competitors on the Netflix prize dataset (Bennett et al.,
2007) involve significantly more complex models than earlier baselines (Rendle
et al., 2019). Famously, the Netflix grand prize winner, the “BellKor”
algorithm (Koren, 2009), boosts and ensembles several different underling
methods making it difficult to interpret the model by inspecting its
parameters.

To tackle these challenges, some works introduce model classes that are
naturally interpretable (Nori et al., 2019; Hastie & Tibshirani, 1990).
Alternatively, to other works have proposed model-agnostic methods to
“explain” the predictions of classifiers and regressors. Many of these
approaches try to model and explain the “local” structure around a specific
prediction. For example, the black-box interpretability method LIME samples
the model’s behavior around a neighborhood of a prediction and distills this
behavior with a simpler interpretable model like a distance-weighted,
regularized, linear model. Other approaches like DeepLift and Layer-wise
relevance propagation project signal from a deep network prediction backwards
through the network structure. Class Activation Maps (CAMs) project the
predicted class of a deep convolutional network onto the penultimate features
to create a low resolution heatmap of class-specific network attention. This
yields robust interpretations with only a single network evaluation, and has
applications in weakly supervised semantic and instance segmentation (Ahn et
al., 2019; Wang et al., 2020). Finally, Additive Shapley Explanations (SHAP),
uses the notion of optimal credit assignment through Shapley Values (Shapley,
1951) to weight each feature’s importance in a prediction. Importantly,
(Lundberg & Lee, 2017) showed that LIME, DeepLift (Shrikumar et al., 2017),
Layer-Wise Relevance Propagation (Bach et al., 2015), and Integrated Gradients
(Sundararajan et al., 2017) are all implicitly approximating the Shapley Value
and thus provided a unified understanding of these methods. We extend this
connection in our work.

Figure 3: A pair of incorrectly matched images and their corresponding
marginal interpretations from Kernel SHAP which highlight important pixels in
red. This visualization shows that the search engine noticed similarity
between the keg and the cup, due to the geometry of these objects. Figure 4:
Visualization of how regions of two similar images can be put in
correspondence through the joint search interpretability method SAM. This
correspondence also allows us to transfer labels or attention between similar
images in a principled way.

##  3 Marginal Search Interpretability

Though there is a considerable amount of literature on classifier
interpretability, black-box search engine interpretability has only recently
been investigated. We build on the rich classifier interpretability literature
to present a general transformation that allows one to extend model agnostic
explanations to a broader class of systems such as search engines,
recommendation systems, and content-based retrieval algorithms. This approach
extracts the features, words, or superpixels of the data that contribute the
most to the overall similarity judgement. More formally, given a similarity
function $d:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ and elements
$x\in\mathcal{X}$ and $y\in\mathcal{Y}$ we form the following pair of
functions:

$\displaystyle f_{y}(x):\mathcal{X}\to\mathbb{R}$
$\displaystyle\vcentcolon=f_{link}(d(x,y))$ (1) $\displaystyle
f_{x}(y):\mathcal{Y}\to\mathbb{R}$ $\displaystyle\vcentcolon=f_{link}(d(x,y))$
(2)

Where $f_{link}$ is a function to transform the output of $d$ so that
explanations have more natural and additive units resembling log-odds for
classification (Lundberg & Lee, 2017; Nelder & Wedderburn, 1972). For the
commonly used cosine similarity between features shown in Figure 1, we use
$\operatorname{atanh}:[-1,1]\to\mathbb{R}$. By using these functions with
existing classifier interpretability techniques like LIME, SHAP, DeepLift, and
Layer-wise relevance propagation we can compute the most important features,
superpixels, or words in both the query, $x$ and retrieved data, $y$,
respectively. We refer to this approach as “marginal” search interpretability
as it finds important substructure within $x$ and $y$ but does not generate a
“correspondence” between the structures of $x$ and $y$. In Section 4.4 we
discuss this connection in greater detail.

Figure 1 middle row demonstrates this approach applied to a simple deep visual
search architecture where a deep network featurizes both query and retrieved
images before comparing their similarity. Transforming the search query via
partial function application and using different link function
($f_{link}=\operatorname{atanh}$) enables direct use of existing model-
interpretability approaches. We compare these approaches visually in Figure 2.

In addition to extending black-box interpretation methods to search we also
extend the white-box convolution network interpretation approach, CAM, to
search. We refer to this approach as “Search Activation Maps (SAM)”. CAM and
SAM are both apply to convolutional networks with a penultimate global average
pooling layer. Despite this limitation, CAM is widely used because it only
requires a single forward pass of the network and is fully differentiable.
Differentiability allows CAM regularization and manipulation in more complex
vision architectures (Wang et al., 2020). To generalize CAM to search and
recommendation architectures, let $f_{hwc}$ represent the layer of activations
of the query image before the global average pooling layer with spatial height
$h$, width $w$, and feature size $c$. Let the function
$\operatorname{norm}_{c}$ represent normalization with respect to the channel
dimension $c$. Let $g_{c}$ represent the average pooled activations of the
retrieved image. Contracting $f$ and $g$ along the “feature” dimension $c$
yields an attention map $a_{hw}$ over the query image. In Einstein notation
(Einstein, 1923):

$a_{hw}\vcentcolon=\operatorname{norm}_{c}({f_{hwc}})\operatorname{norm}_{c}({g^{c}})$
(3)

Like CAM, SAM can be overlayed on query image pixels to visualize the regions
that most contribute to the similarity. Additionally, one can switch the query
and target images in the above formulation to visualize attention over the
retrieved image pixels.

Visualizing why pairs of images are considered similar can help model users
and builders understand their retrieval systems. For example, Figure 3
demonstrates how this approach can identify why a particular image search
system erroneously matched a pair of irrelevant images. This is analogous to
how classifier interpretation approaches allow model designers to diagnose
errors (Ribeiro et al., 2016).

##  4 Joint Search Interpretability

Visualizing the pixels that most “explain” the similarity judgement provides a
simple way to inspect where a black-box search engine is “attending to”.
However, this visualization is only part of the story. Image pairs can be
similar for many different reasons, and a good explanation should clearly
delineate these independent reasons. For example, consider the pair of images
in the bottom left of Figure 1. These images show two similar scenes of people
playing with dogs with several similar objects, but in different arrangements.
We seek not just a heatmap highlighting similar aspects, but a data-structure
which tells us about how parts of the query image correspond to parts of a
target image and vice-versa. In this section we will present generalizations
of CAM, LIME, and SHAP to this richer interpretation setting.

###  4.1 Joint Search Activation Maps (SAM)

We begin with generalizing CAM to the joint setting. By modifying the tensor
contraction used in marginal SAM, we can compute a tensor which represents the
affinities between regions of the query and retrieved images. More formally,
let $f_{hwc}$, represent the layer of activations of the query image before
the global average pooling layer of a trained convolutional network. This
tensor has spatial height $h$, width $w$, and feature size $c$. Let $g^{ijc}$
represent the corresponding tensor of activations for the retrieved images
with spatial dimensions $i$, and $j$. Contracting these tensors across $c$
yields:

$a_{hw}^{ij}\vcentcolon=\operatorname{norm}_{c}(h_{hwc})\operatorname{norm}_{c}(g^{ijc})$
(4)

Which is a fourth rank tensor whose values are cosine distances between each
combination of features in the query and retrieved image. This tensor not only
captures the fine-grained correspondence between query and retrieved images,
but also has an operational interpretation as a transport mapping which can
project “attention” from the query to the retrieved image and vice-versa. We
elaborate on this connection in Section 4.4.

###  4.2 Joint Search LIME

Next, we generalize LIME to provide joint search interpretations. In the
classifier formulation of LIME, one fits a locally-weighted and regularized
linear approximation to the neighborhood of a particular model’s prediction.
For image classifiers, one forms thus “neighborhood” by decomposing the input
image into superpixels (Achanta et al., 2010) and perturbing the image by
replacing random superpixels with a background color. This process is called
“toggling” the superpixels, and the boolean states of these superpixels are
used to form the features of a linear regression dataset. The “targets” are
the log probabilities given to the perturbed images by the image classifier
under examination. Fitting a locally weighted and regularized linear model to
this dataset captures the impact of each superpixel on the prediction. In
particular, the fit model is of the form:

$y\sim a_{0}+\sum_{q}a_{q}s_{q}$ (5)

Figure 5: Marginal interpretation evaluation strategy. A good method should
highlight pixels in the query image (top left and middle) that, when censored
(top right), have the largest possible impact on the similarity.

Where $s_{q}=1$ when a superpixel $q$ is toggled “on” and the learned weights
$a_{q}$ represent the impact of each superpixel. We point readers to the
original work (Ribeiro et al., 2016) for a more detailed description of the
approach. To generalize LIME to the domain of joint search interpretability we
instead consider locally approximating the search engine with a regularized
bi-linear approximation to capture cross image interactions. More
specifically, we decompose both query and retrieved images into superpixels
and form a dataset by toggling superpixels in both images simultaneously. We
then map these “perturbed” pairs through similarity function $d$ and the link
function $f_{link}$. Finally, we fit a bi-linear model of the form:

$y\sim a_{0}+\sum_{q}a_{q}s_{q}+\sum_{r}a_{r}s_{r}+\sum_{q,r}a_{qr}s_{q}s_{r}$
(6)

Where $s_{q}$ are the indicator variables that a superpixel, $q$, in the query
image is toggled on, and likewise $s_{r}$ indicates the presence of superpixel
$r$ in the retrieved image. The model parameters: $a_{0}$, $a_{q}$, $a_{r}$,
and $a_{qr}$ are the learned constant, query-linear, retrieved-linear, and bi-
linear terms, respectively. As in the original implementation of LIME, one can
include a local weighting when fitting the bi-linear model to increase the
influence of less-perturbed pairs of images and a L1 penalty to increase the
sparsity of solutions.

Figure 6: Joint interpretation evaluation strategy. A good method should
project query image attention (top left and middle) to corresponding structure
in the retrieved image (bottom left and middle). When censoring all but this
shared structure (right column) the search engine should view these images as
similar.

###  4.3 Joint Search SHAP

Additive Shapley Explanations supply a principled and axiomatic framework for
classifier interpretation and unify several existing approaches. This work
looks to extend this framework to the richer functional forms and
interpretations needed for search and recommendation systems. SHAP explains
predictions by weighting features according to how much “credit” each receives
for the prediction in an optimal credit assignment framework. More formally, a
“coalition game” is a set $N$ of $n$ players and a function
$v:2^{N}\to\mathbb{R}$ where $v(\emptyset)=0$. In cooperative game theory,
this function $v$ represents the expected payoff for a given cooperating
coalition of players. Shapley Value Theory shows that the unique, fair credit
assignment to each player, $\phi_{v}(i\in N)$, can be calculated as:

$\phi_{v}(i)\vcentcolon=\sum_{T\subseteq
N\setminus\\{i\\}}\frac{|T|!(n-|T|-1)!}{n!}(v(T\cup\\{i\\})-v(T))$ (7)

This equation captures the average increase in value that a player $i$ brings
to a coalition $T$ by weighting each increase, $v(T\cup\\{i\\})-v(T)$, by the
number of ways this event could have happened during the formation of the
“grand coalition” $N$. We note that this assignment, $\phi_{v}$, is the only
one that satisfies four reasonable properties: Symmetry under player re-
labeling, no credit assignment to “dummy” players, linearity, and “efficiency”
which states that Shapley values should sum to $v(N)$ (Young, 1985). To
connect this work to model interpretability, one can identify the ‘features”
used in model as the “players” and interpret the characteristic function,
$v(T)$, as the expected prediction of the model with features corresponding to
$N\setminus T$ replaced by values from a “background” distribution. In our
experiments we use a blank image.

To guide our generalization of SHAP we note that both SAM and LIME generalize
to joint interpretation methods by replacing linear forms with multi-linear
forms to capture interactions between the query and retrieved images.
Following this pattern, we seek higher order generalizations of the Shapley
Value. In particular (Harsanyi, 1963) show that the Shapley Values arise from
distributing “Harsanyi dividends” associated with every coalition of players,
evenly across members of the coalition. More specifically, the Harsanyi
Dividend for a coalition $S$ is defined as:

$d_{v}(S)\vcentcolon=\begin{cases}v(S)&\text{if $|S|=1$}\\\
v(S)-\sum_{T\subsetneq S}d_{v}(T)&\text{if $|S|>1$}\\\ \end{cases}$ (8)

These dividends, also known as Mobïus coefficients (Grabisch et al., 2016),
provide a detailed view of the function’s behavior at every coalition. In this
work we generalize the notion of sharing these dividends between individuals
to sharing these dividends between sub-coalitions. This insight provides
natural motivation for a recent Generalization of Shapley Values called the
Shapley-Taylor Indices (Sundararajan et al., 2020). More specifically,
(Sundararajan et al., 2020) define a generalization of the Shapley Values to
coalitions of a size $k$ using the discrete derivative operator, which leads
to their namesake connection with Taylor series expansions. However, we show
that in the language of Harsanyi Dividends the connection between the Shapley
Values and the Shapley-Taylor index is much more apparent. Through the lens of
sharing dividends, we arrive at a new formula for the Shapley-Taylor values
for coalitions $|S|=k$:

$\phi^{k}_{v}(S)=\sum_{T:S\subset T}\frac{d_{v}(T)}{\binom{|T|}{|S|}}$ (9)

In this light, one can see that Shapley-Taylor values simply divide up the
high order Harsanyi Dividends evenly among all lower-order terms. This
reproduces the Shapley Values when $k=1$. When $k=2$ it assigns credit to each
individual $|S|=1$ and pair of individuals $|S|=2$. This insight not only
allows for deriving the Shapley Values and the Shapley-Taylor indices, but
also allows for the creation of new optimal credit assignment weights for more
complex problems. In our motivating example of interpreting visual search
engines, we keep terms associated with each superpixel, and cross-image pairs
of superpixels (first superpixel is in the query image, and the second
superpixel is in the retrieved image). We divide all other dividends and
distribute them their smaller coalitions. This “cross-linear” optimal credit
assignment has the same binary terms as the Shapley-Taylor indices, but
different unary terms due to the splitting of intra-image terms among the
individual superpixels. Put another way, Harsanyi dividend sharing allows one
to create “jagged” generalizations of the Shapley-Taylor indices that can
yield optimal credit assignments on more complex collections of coalitions.

Though the Harsanyi Dividends and Shapley-Taylor indices provide a robust way
to allocate credit, they are difficult to compute. The authors of the Shapley-
Taylor indices provide a sampling-based approximation, but this approach
requires estimating each interaction term with a separate sampling procedure,
which scales poorly as dimensionality increases. To make this approach more
tractable for large scale datasets we draw a parallel the unification of LIME
with Shapley Values through a specific weighting kernel. In particular we
introduce a kernel for second order Shapley-Taylor indices:

$k(N,S)=\frac{|N|-1}{\binom{|N|}{|S|}\binom{|S|}{2}(|N|-|S|)}$ (10)

Using this kernel, one can instead sample random coalitions, evaluate $v$, and
aggregate the information into a bilinear model. This allows one to
approximate all Shapley-Taylor indicies of $k=2$ with a single sampling
procedure, and converges much faster for high dimensional problems and we
report convergence rates in Section B of the Supplement. This also allows us
to view joint search LIME as a Shapley-Taylor index approximator much like
regular LIME is to the Shapley Values.

###  4.4 Connection to Attention Transport

Beyond measuring of the interaction strength between regions in the query and
retrieved image, joint explanations also have an operational interpretation as
a method of attention transportation between images. For example in Equation 4
which characterizes Joint SAM the co-variant and contra-variant positions of
the spatial indices indicate that the tensor, $a^{ij}_{hw}$, also encodes a
mapping. More specifically, let $q^{hw}$ denote an attention map over the
query image, we form a corresponding attention map on the retrieved image
using the tensor contraction: $r^{ij}\vcentcolon=a^{ij}_{hw}q^{hw}$. Figure 4
demonstrates how projecting different localized attention maps can visualize
detailed information about how specific regions of the query image correspond
to regions of the target image.

By normalizing the joint interpretation tensor, the connection to transport
theory becomes even more explicit. More specifically, we can view the
normalized attention weights as a joint distribution over pairs of regions.
The marginals of this distribution are precisely the marginal search
interpretations. In summary, because a joint distribution encodes a transport
plan between its marginals (Dobrushin, 1970), a joint interpretation acts as a
transport plan between the marginal interpretations.

For LIME and Kernel SHAP, these transport strategies occur in the superpixel
space rather than the image region space. In particular, one can use the
interaction terms as a linear map to transfer attention from query to
retrieved image superpixels. One can then project the weights onto the pixels
by coloring each superpixel with its attention.

##  5 Experimental Evaluation

Evaluating the faithfulness of an interpretability method requires careful
experimental design. Interpretations that “look good” to a human might not be
faithful to the underlying model which could model the task poorly. We aim to
evaluate how well our proposed joint and marginal interpretation approaches
capture the structure of the underlying search engine independent of how the
model performs semantically. To this end we expand the “interpret-and-censor”
evaluation strategy of (Lundberg & Lee, 2017). This approach first interprets
a prediction, then censors the most important features, and finally re-
evaluates the classifier. If the interpretation method works well, this should
yield a large change in the prediction. The most important part of this method
is that it directly measures faithfulness to the underlying classifier and
does not conflate this with the performance of the classifier on the task.

Table 1: Comparison of speed and performance of marginal and joint search interpretation methods across three different search engines. $\Delta d$ (higher is better) represents the change in similarity when censoring the top 20% of pixels in the marginal interpretation as shown in Figure 5. $d$ (lower is better) is the similarity between attention-censored images as shown in Figure 6. mIoU (higher is better) represents the performance on a binary semantic segmentation label propagation task as described in Section 5.2. |  | Marginal | Joint
---|---|---|---
Search Backbone | Method | Time (s) | $\Delta d$ | Time (s) | $d$ | mIoU
ResNet50 | SBSM |  19.5 $\pm$ 0.0 |  0.1 $\pm$ 0.003 |  87.4 $\pm$ 0.01 |  0.32 $\pm$ 0.005 | 0.52
SAM | 0.09 $\pm$ 0.001 |  0.07 $\pm$ 0.003 | 0.03 $\pm$ 0.0 |  0.27 $\pm$ 0.003 | 0.65
LIME |  32.6 $\pm$ 0.02 |  0.11 $\pm$ 0.004 |  120.9 $\pm$ 0.06 |  0.26 $\pm$ 0.004 | 0.62
Integrated Gradients |  3.4 $\pm$ 0.0 |  0.1 $\pm$ 0.004 | - | - | -
Kernel SHAP |  44.4 $\pm$ 0.1 |  0.11 $\pm$ 0.004 |  129.4 $\pm$ 0.87 | 0.25 $\pm$ 0.005 | 0.65
Partition SHAP |  45.0 $\pm$ 0.01 | 0.15 $\pm$ 0.004 | - | - | -
VGG11 | SBSM |  16.3 $\pm$ 0.01 |  0.12 $\pm$ 0.005 |  68.7 $\pm$ 0.02 |  0.41 $\pm$ 0.007 | 0.53
SAM | 0.07 $\pm$ 0.003 |  0.1 $\pm$ 0.005 | 0.05 $\pm$ 0.001 | 0.31 $\pm$ 0.003 | 0.72
LIME |  29.8 $\pm$ 0.02 |  0.12 $\pm$ 0.005 |  109.0 $\pm$ 0.04 |  0.32 $\pm$ 0.005 | 0.63
Integrated Gradients |  3.1 $\pm$ 0.01 |  0.08 $\pm$ 0.005 | - | - | -
Kernel SHAP |  41.4 $\pm$ 0.07 |  0.12 $\pm$ 0.005 |  115.5 $\pm$ 0.71 | 0.31 $\pm$ 0.006 | 0.67
Partition SHAP |  41.5 $\pm$ 0.03 | 0.16 $\pm$ 0.006 | - | - | -
DenseNet121 | SBSM |  21.4 $\pm$ 0.01 |  0.16 $\pm$ 0.006 |  88.5 $\pm$ 0.01 |  0.6 $\pm$ 0.008 | 0.54
SAM | 0.17 $\pm$ 0.004 |  0.14 $\pm$ 0.006 | 0.12 $\pm$ 0.001 |  0.52 $\pm$ 0.005 | 0.63
LIME |  34.4 $\pm$ 0.02 |  0.18 $\pm$ 0.006 |  130.5 $\pm$ 0.06 |  0.5 $\pm$ 0.006 | 0.62
Integrated Gradients |  3.6 $\pm$ 0.0 |  0.14 $\pm$ 0.007 | - | - | -
Kernel SHAP |  46.2 $\pm$ 0.06 |  0.19 $\pm$ 0.007 |  130.5 $\pm$ 1.03 | 0.49 $\pm$ 0.008 | 0.65
Partition SHAP |  47.6 $\pm$ 0.02 | 0.24 $\pm$ 0.007 | - | - | -

###  5.1 Marginal Search Interpretation

We first generalize the interpret-and-censor evaluation to marginal search
interpretation methods. Intuitively speaking, a good marginal search
interpretation should highlight the “most important” pixels that contribute to
the similarity of the two images. Censoring these important pixels by filling
them with a mean-color background should dramatically reduce the similarity
between these two images. The magnitude of the change in the similarity,
$\Delta d$, between uncensored and censored image pairs is a direct
measurement of the interpretability method’s quality and is a direct analogue
of the interpret-and-censor strategy of (Lundberg & Lee, 2017). Figure 5 shows
a diagram and example of our proposed strategy. We use each marginal
interpretation strategy to extract an attention map over the query image
pixels. Finally, we censor the top 20% of important pixels in the query and
re-evaluate the engine’s similarity computation and record the change in
distance, $\Delta d$. The marginal columns of Table 1 show the results of this
experiment, and compares computation times across marginal methods, we find
that SAM is the k, fastest method, but that PartitionSHAP provides the best
quality interpretations and significantly outperforms the current best visual
search approach SBSM (Dong et al., ). The dominance of Partition SHAP suggests
that the formal basis for SHAP also yields higher-fidelity interpretation
methods. We describe our models, data, and implementation details in Section
5.3

###  5.2 Joint Search Interpretation

We also extend the interpret-and-censor evaluation strategy to joint
interpretations by evaluating an interpretation’s ability to project attention
maps. We generate different query attention maps using Pascal VOC’s ground
truth semantic segmentation labels. Intuitively speaking, a good joint
interpretation should find the region of the retrieved image that most closely
matches a selected region of the query image. Censoring all but this region,
as shown in Figure 6, should yield similar images according to the search
engine. More specifically, first we censor the query image to a randomly
chosen semantic segmentation class. Second, we use the chosen class’
segmentation mask as a query attention map attention and project this
attention to the retrieved image using the joint interpretation method. Third
we then censor all but the top $p$ pixels of the retrieved image where, $p$ is
the size of corresponding semantic segmentation mask in the retrieved image.
Finally, we measure the similarity between the censored images. A faithful
interpretation approach should yield a similar (small $d$) image pair after
censoring.

In addition to measuring faithfulness of the representation method we also
measure how well the approach performs semantic segmentation label
propagation. To measure this, we treat the projected attention as a binary
semantic segmentation prediction and compare with the known ground truth
segmentation labels. The mean intersection over union (mIoU) of this
segmentation prediction provides a second measurement of interpretation
quality more focused on a particular downstream task like label propagation.
However, we caution that this is not a direct measurement of interpretation
faithfulness, but we feel this provides a complementary view that can help
creation of better label propagation systems. The joint columns of Table 1
show the results of these experiments over several interpretation methods that
we have generalized to the joint domain. We find that SAM is by far the
fastest but Kernel SHAP significantly outperforms all methods in terms of
faithfulness to the underlying search engine. We describe our models, data,
and implementation details in Section 5.3

We note that because this is the first work to identify these joint
interpretations, there are no existing approaches in the literature to compare
against in the joint domain. To compare against a reasonable literature-
derived benchmark, we have additionally generalized the SBSM method to the
joint setting and detail this construction in the Supplement.

###  5.3 Implementation Details

Our evaluation experiments use visual search engine built from a pre-trained
“backbone” network that featurizes images and compares their similarity using
cosine distance. We report results for engines using ResNet50 (He et al.,
2016), VGG11 (Simonyan & Zisserman, 2014), and DenseNet121 (Huang et al.,
2017), as backbone networks. We use 200 random query images from the Pascal
VOC validation set and their closest pairs in the VOC training set.
Additionally, we restrict retrieved images so that the query and retrieved
images both contain the same class objects and have objects that take up more
than 5% of the image (Hamilton et al., 2020). We include these image pairs and
evaluation code in the supplement. Experiments use PyTorch (Paszke et al.,
2019) v1.7 pre-trained models, on an Ubuntu 16.04 Azure NV24 Virtual Machine
with Python 3.6.

##  6 Related Work

The field of black-box visual search engine explainability is relatively new
despite the ubiquity of search engines. To our knowledge (Dong et al., ) is
the first to present a generic visual search engine explanations. We also note
the works of (Singh & Anand, 2019) and (Fernando et al., 2019) who marginally
interpret a text search engine using LIME and DeepSHAP. However, these works
do not apply their methods to images and do not lift these approaches to the
joint domain. The optical-flow architecture FlowNet (Fischer et al., 2015)
uses the correlation between convolutional feature maps to estimate the
correspondence between two adjacent video frames as part of a larger optical
flow architecture. Though similar to SAM, this approach was not interpreted in
the context of search engine explanations. (Hou et al., 2019) also embeds a
component similar to SAM within a deep classifier to improve few-shot
performance. Other recent works have used learn co-attention within
transformer architectures to help pool and share information across multiple
domain types (Wei et al., 2020).

In the field of cooperative game theory, several seminal works provide a
variety of ways to extend Shapley Values to more complex interactions.
(Harsanyi, 1963) generalized the Shapely value by introducing a “dividend”
that, when split and distributed among players, yields the Shapley Values.
(Owen, 1972) introduce another way to extend Shapley values using a multi-
linear extension of the game’s characteristic function. (Sundararajan et al.,
2020) introduce the Shapley-Taylor index which they show is equivalent to the
Lagrangian remainder of Owen’s multi-linear extension. This work does not
relate the Shapley-Taylor indices to Harsanyi dividends or explore
interactions in the context search engine interpretability.

##  7 Conclusion

In this work we have proposed and evaluated new approaches to generate model-
agnostic explanations for image similarity, search, and retrieval
architectures. We characterize search engine interpretability methods as
either “marginal” or “joint” interpretation methods depending on what kind of
information they explain. We extended Class Activation Maps (CAMs), Additive
Shapley Explanations (SHAP), and Locally Interpretable Model-Agnostic
Explanations (LIME) to image retrieval and search and showed it was possible
to extract much richer “joint” interpretations using extensions of these
methods. These approaches enable black and grey-box model introspection and
can help diagnose errors and understand the rationale behind a model’s
similarity judgements. We also provide a new framework for deriving optimal
credit assignments from Harsanyi Dividends. We show that this framework
generalizes the Shapley-Taylor indices, and provide a Kernel for faster
estimation of Shapley-Taylor indices. Finally, we show this game-theoretic
formalism yields more faithful model interpretation strategies for several
visual search engines.

## References

  * Achanta et al. (2010) Achanta, R., Shaji, A., Smith, K., Lucchi, A., Fua, P., and Süsstrunk, S.  Slic superpixels.  Technical report, 2010.
  * Ahn et al. (2019) Ahn, J., Cho, S., and Kwak, S.  Weakly supervised learning of instance segmentation with inter-pixel relations.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 2209–2218, 2019.
  * Bach et al. (2015) Bach, S., Binder, A., Montavon, G., Klauschen, F., Müller, K.-R., and Samek, W.  On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation.  _PloS one_ , 10(7):e0130140, 2015.
  * Bengio et al. (2013) Bengio, Y., Courville, A., and Vincent, P.  Representation learning: A review and new perspectives.  _IEEE transactions on pattern analysis and machine intelligence_ , 35(8):1798–1828, 2013.
  * Bennett et al. (2007) Bennett, J., Lanning, S., et al.  The netflix prize.  2007\.
  * Bing (2017) Bing.  Beyond text queries: Searching with bing visual search, Jun 2017.  URL https://aka.ms/AAas7jg.
  * Dobrushin (1970) Dobrushin, R. L.  Prescribing a system of random variables by conditional distributions.  _Theory of Probability & Its Applications_, 15(3):458–486, 1970.
  * (8) Dong, B., Collins, R., and Hoogs, A.  Explainability for content-based image retrieval.
  * Einstein (1923) Einstein, A.  The foundation of the general theory of relativity. the principle of relativity, 1923.
  * Everingham et al. (2010) Everingham, M., Van Gool, L., Williams, C. K. I., Winn, J., and Zisserman, A.  The pascal visual object classes (voc) challenge.  _International Journal of Computer Vision_ , 88(2):303–338, June 2010.
  * Fernando et al. (2019) Fernando, Z. T., Singh, J., and Anand, A.  A study on the interpretability of neural retrieval models using deepshap.  In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pp. 1005–1008, 2019\.
  * Fischer et al. (2015) Fischer, P., Dosovitskiy, A., Ilg, E., Häusser, P., Hazırbaş, C., Golkov, V., Van der Smagt, P., Cremers, D., and Brox, T.  Flownet: Learning optical flow with convolutional networks.  _arXiv preprint arXiv:1504.06852_ , 2015.
  * Grabisch et al. (2016) Grabisch, M. et al.  _Set functions, games and capacities in decision making_ , volume 46.  Springer, 2016.
  * Hamilton et al. (2020) Hamilton, M., Fu, S., Freeman, W. T., and Lu, M.  Conditional image retrieval.  _arXiv preprint arXiv:2007.07177_ , 2020.
  * Harsanyi (1963) Harsanyi, J. C.  A simplified bargaining model for the n-person cooperative game.  _International Economic Review_ , 4(2):194–220, 1963.
  * Hastie & Tibshirani (1990) Hastie, T. J. and Tibshirani, R. J.  _Generalized additive models_ , volume 43.  CRC press, 1990.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Hou et al. (2019) Hou, R., Chang, H., Ma, B., Shan, S., and Chen, X.  Cross attention network for few-shot classification.  _arXiv preprint arXiv:1910.07677_ , 2019.
  * Huang et al. (2017) Huang, G., Liu, Z., Van Der Maaten, L., and Weinberger, K. Q.  Densely connected convolutional networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 4700–4708, 2017.
  * Kohavi et al. (1996) Kohavi, R., Wolpert, D. H., et al.  Bias plus variance decomposition for zero-one loss functions.  In _ICML_ , volume 96, pp. 275–83, 1996.
  * Koren (2009) Koren, Y.  The bellkor solution to the netflix grand prize.  _Netflix prize documentation_ , 81(2009):1–10, 2009.
  * Lundberg & Lee (2017) Lundberg, S. M. and Lee, S.-I.  A unified approach to interpreting model predictions.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 30_ , pp. 4765–4774. Curran Associates, Inc., 2017.
  * Nayak (2019) Nayak, P.  Understanding searches better than ever before, Oct 2019.  URL https://blog.google/products/search/search-language-understanding-bert/.
  * Nelder & Wedderburn (1972) Nelder, J. A. and Wedderburn, R. W.  Generalized linear models.  _Journal of the Royal Statistical Society: Series A (General)_ , 135(3):370–384, 1972.
  * Nori et al. (2019) Nori, H., Jenkins, S., Koch, P., and Caruana, R.  Interpretml: A unified framework for machine learning interpretability.  _arXiv preprint arXiv:1909.09223_ , 2019.
  * Owen (1972) Owen, G.  Multilinear extensions of games.  _Management Science_ , 18(5-part-2):64–79, 1972\.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  Pytorch: An imperative style, high-performance deep learning library.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 32_ , pp. 8024–8035. Curran Associates, Inc., 2019.
  * Rendle et al. (2019) Rendle, S., Zhang, L., and Koren, Y.  On the difficulty of evaluating baselines: A study on recommender systems.  _arXiv preprint arXiv:1905.01395_ , 2019.
  * Ribeiro et al. (2016) Ribeiro, M. T., Singh, S., and Guestrin, C.  ”why should I trust you?”: Explaining the predictions of any classifier.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016_ , pp. 1135–1144, 2016.
  * Shapley (1951) Shapley, L. S.  Notes on the n-person game—ii: The value of an n-person game.  1951\.
  * Shrikumar et al. (2017) Shrikumar, A., Greenside, P., and Kundaje, A.  Learning important features through propagating activation differences, 2017.
  * Simonyan & Zisserman (2014) Simonyan, K. and Zisserman, A.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Singh & Anand (2019) Singh, J. and Anand, A.  Exs: Explainable search using local model agnostic interpretability.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , pp. 770–773, 2019.
  * Su & Khoshgoftaar (2009) Su, X. and Khoshgoftaar, T. M.  A survey of collaborative filtering techniques.  _Advances in artificial intelligence_ , 2009, 2009.
  * Sundararajan et al. (2017) Sundararajan, M., Taly, A., and Yan, Q.  Axiomatic attribution for deep networks.  In _International Conference on Machine Learning_ , pp. 3319–3328. PMLR, 2017.
  * Sundararajan et al. (2020) Sundararajan, M., Dhamdhere, K., and Agarwal, A.  The shapley taylor interaction index.  In _International Conference on Machine Learning_ , pp. 9259–9268. PMLR, 2020.
  * Wang et al. (2020) Wang, Y., Zhang, J., Kan, M., Shan, S., and Chen, X.  Self-supervised equivariant attention mechanism for weakly supervised semantic segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 12275–12284, 2020.
  * Wei et al. (2020) Wei, X., Zhang, T., Li, Y., Zhang, Y., and Wu, F.  Multi-modality cross attention network for image and sentence matching.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 10941–10950, 2020.
  * Young (1985) Young, H. P.  Monotonic solutions of cooperative games.  _International Journal of Game Theory_ , 14(2):65–72, 1985.
  * Zhou et al. (2016) Zhou, B., Khosla, A., A., L., Oliva, A., and Torralba, A.  Learning Deep Features for Discriminative Localization.  _CVPR_ , 2016.

## Appendix

##  Appendix A Generalizing SBSM to Joint Search Engine Interpretability

Before generalizing SBSM (Dong et al., ) to joint interpretability we will
review the original implementation for marginal interpretability. SBSM uses a
sliding square mask and multiple evaluations of the search engine in order to
determine which regions of the image are important for similarity. More
formally, let $q$, and $r$ represent the pixels of the query image and
retrieved image. Let $M^{s}_{ij}(q)$ represent the result of replacing a
square of pixels of size $s\times s$ centered at pixel $(i,j)$ with a
“background value” which in our case is black. SBSM “slides” this mask across
the query image and compares the similarity between the masked query and
retrieved image. These masked similarity values are compares to the baseline
similarity value and stored in a weight matrix, $w$:

$w_{ij}=\min\left[d\left(M^{s}_{ij}(q),r\right)-d\left(q,r\right),0\right]$
(11)

Intuitively speaking, the weights $w_{ij}$ represent the impact of masking a
square centered at $(i,j)$. For areas that are critical to the similarity,
this will result in $w_{ij}>0$. Finally an attention mask on the query image
is formed by a weighted average of the masks used to censor the images. For
square masks, this can be achieved efficiently using a deconvolution with a
kernel of ones of size $s\times s$ on the weight matrix $w$. We also note that
instead of evaluating the (expensive) distance computation $d$ for every pixel
$(i,j)$, one can also sample pixels to censor. We use this approach in our
joint generalization.

To generalize SBSM we use a pair of masks, one for the query image and one for
the retrieved image respectively. We sample mask locations and calculate
weights designed to capture the intuition that censoring corresponding areas
cause similarity to increase as oppose to decrease. More specifically we use
the following weighting scheme:

$w_{ij}^{hw}=\min\left[d\left(q,r\right)-d\left(M^{s}_{ij}\left(q\right),M^{s}_{hq}\left(r\right)\right),0\right]$
(12)

Because evaluating the similarity function for every $(i,j,h,w)$ combination
is prohibitively expensive, we instead sample masked images for our
computation. To project attention from a query pixel, we query for all masks
that overlap with the selected query pixel, and then average their
corresponding retrieved masks according to the weights calculated in Equation
12.

##  Appendix B Accelerated Convergence of Kernel-Based Shapley-Taylor
Estimation

Though the Harsanyi Dividends and Shapley-Taylor indices provide a robust way
to allocate credit, they are difficult to compute. The authors of the Shapley-
Taylor indicies provide a sampling-based approximation, but this approach
requires estimating each interaction term with a separate sampling procedure.
To make this approach more tractable for large scale datasets we draw a
parallel the unification of LIME with Shapley Values through a specific
weighting kernel. We find that unlike Shapely-Taylor sampling procedures, this
requires significantly fewer function evaluations to converge to the true
Shapley-Taylor indices.

We quantify this speedup by measuring convergence to the brute-force
calculated Shapley-Taylor indices for random 8 dimensional Boolean functions
formed by randomly assigning each subset a random integer in $[0,10]$. Figure
7 shows that Kernel based approximation has a much better sample complexity
than Shapley-Taylor sampling approaches.

Figure 7: Convergence of Shapley-Taylor index estimation schemes with respect
to the Mean Squared Error (MSE). Our proposed kernel estimation strategy
converges with significantly fewer function evaluations.