Axiomatic Explanations for Visual Search, Retrieval, and Similarity Learning
Authors: Mark Hamilton
Scott Lundberg
Stephanie Fu
Lei Zhang
William T. Freeman
Venue: ICLR 2022 Poster (2022)
Keywords: Model Interpretability
Shapley Values
Search Engines
Information Retrieval
Visual Search
Similarity Learning
Metric Learning
Black-box explanations

Abstract: Visual search, recommendation, and contrastive similarity learning power technologies that impact billions of users worldwide. Modern model architectures can be complex and difficult to interpret, and there are several competing techniques one can use to explain a search engine's behavior. We show that the theory of fair credit assignment provides a unique axiomatic solution that generalizes several existing recommendation- and metric-explainability techniques in the literature. Using this formalism, we show when existing approaches violate "fairness" and derive methods that sidestep these shortcomings and naturally handle counterfactual information. More specifically, we show existing approaches implicitly approximate second-order Shapley-Taylor indices and extend CAM, GradCAM, LIME, SHAP, SBSM, and other methods to search engines. These extensions can extract pairwise correspondences between images from trained opaque-box models. We also introduce a fast kernel-based method for estimating Shapley-Taylor indices that require orders of magnitude fewer function evaluations to converge. Finally, we show that these game-theoretic measures yield more consistent explanations for image similarity architectures. 

Published as a conference paper at ICLR 2022
AXIOMATIC EXPLANATIONS FOR VISUAL SEARCH, RETRIEVAL, AND SIMILARITY LEARNING
Mark Hamilton': 122 Scott Lttphaegg,Stephnnie Fu', Lei Zhang", William T. Freeman" 1.3 MIT, "Microsoft, 'Google markth@mit... eddu
ABSTRACT
Visual search, recommendation, and contrastive similarity learning power tech- nologies that impact billions of users worldwide. Modern model architectures can complex and difficult to interpret, and there are several competing techniques one can use to explain a search engine's behavior. We show that the theory of fair credit assignment provides a unique axiomatic solution that generalizes several existing recommendation- and metric-explainabiiit techniques in the literature. Using this formalism, we show when existing approaches violate "fairness" and derive methods that sidestep these shortcomings and naturally handle counter- factual information. More specifically, we show existing approaches implicitly approximate second-order Shapley-Taylor indices and extend CAM, GradCAM, LIME, SHAP, SBSM, and other methods to search engines. These extensions can extract pairwise correspondences between images from trained opaque- box mod- els. We also introduce a fast kernel-bases method for estimating Shapley- Shapley-Taylor indices that require orders of magnitude fewer function evaluations to converge. Finally, we show that these game- game-theoretic measures yield more consistent expla- nations for image similarity architectures.
INTRODUCTION
Search, recommendation, retrieval, and contrastive similarity learning powers many of today's 's ma- chine learning systems. These systems help organize information at scales that no human could match. The recent surge in million and billion parameter contrastive learning architectures for vi- sion and language underscore the growing need to understand these classes of systems (Nayak) 2019 Chen et al. 2020b a Radford et al. 2021 Caron et al., 2020). Like classifiers and regres- sors, contrastive systems face key challenge: richer models can improve performance but hinder interpretability.. In high-risk domains like medicine, incorrect search results can have serious conse- quences. In other domains, search engine bias can disproportionately ans systematically hide certain voices (Mowshowtz & Kawaguchi 2002
Diaz 2008
Goldman 2005).
Currently, there are several competing techniques to understand a similarity model's predictions (Zhu et al. 2019: Zheng al. 2020 Dong et al.) (Selvaraju et al. 20177] Vaswani al.) 2017). How- ever, there is no agreed "best" method and no a formal theory deseribing an "optimal" search expla- nation method. We show that the theory of fair credit assignment provides a uniquely determined and axiomatically grounded approach for "explaining" a trained model's is similarity judgements. In many cases, existing approaches are special cases of this formalism. This observation allows to design variants of these methods that better satisfy the axioms of fair credit assignment and can han- dle counterfactual or relative explanations. Though explore this topic through the lens of visual search, we note that these techniques could also apply to text, tabular, or audio search systems.
This work identifies two distinct classes of search engine explainability methods. "First order" ap- proaches highlight the most important pixels that contribute to the similarity of objects and "Second order" explanations provide a full correspondence between the parts of query and retrieved image. We relate first order interpretations to existing theory on classifier explainability through generic function transformation, as shown in the third column of Figure [ We find that second order expla- nations correspond to uniquely specified generalization of the Shapley values (Sundararajan al.) 2020) and equivalent to projecting Harsanyi Dividends onto low-order subsets (Harsanyi) 1963). We use this formalism to create new second-order generalizations of Class Activation Maps (Zhou et al. 2016). GradCAM (Selvaraju et al.) 2017), LIME (Ribeiro et al.] 2016). and SHAP (Lundberg & Lee 2017). Our contributions generalize several existing methods, illustrate rich mathematical

---

Published as a conference paper at ICLR 2022
Classification
1 Order Search
2 Order Search
2 Order SAM
Input
Function to Interpret
(dgg))))g))
log( P(dng))
a(h..2) )
a(fu.f2)
a(f..22)
Interpretation
Dense Correspondence Dense Feature Correspondence
Figure I: Architectures for search engine interpretability. Like classifier explanations, First-order search explanations yield heatmaps of important pixels for similarity (bottom row third column). Second order search interpretation methods yield dense correspondence between image locations (last two columns). CAM (second column) is a particular case of Shapley value approximation, and generalize it to yield dense correspondences (last column).
structure connecting model explainability and cooperative game theory, and allow practitioners to understand search engines with greater nuance and detail. We include short video detailing the work at https: / /aka..... m.s axiommain wwwilimmattiiiiiii
In summary we:
Present the first uniquely specified axiomatic framework for model-agnostic search, re- trieval, and metric learning interpretability using the theory of Harsanyi dividends.
Show that our framework generalizes several existing model explanation methods (Zhou et al., 2016 (Selvaraju et al., [017]] /7hu et al. (2099; Ribeiro et al.) (016) to yield dense pairwise correspondences between images and handle counterfactual information.
Introduce a new kernel-based approximator for Shapley-Taye indices that requires about 10x fewer function evaluations.
Show that our axiomatic approaches provide more faithful explanations of image similarity the PascalVOC and MSCoCo datasets.
2 BACKGROUND
This work focuses on search, retrieval, metric learning, and recommendation architectures. Often, these systems similarity between objects learned features (Bengio et al., (2013) to rank, trieve, or suggest content (Bing 2017 Su & Khoshgoftaar 2009 Chopra et al. 2005) Radford et al.) 2021]. More formally,
distance, relevance, similarity function of the form: X' x y + to quantify the relationship between items from sets X' and y. In search and retrieval, X' represents the space of search queries and y represents the space of results, the function d assigns a relevance to each query result pair. Without loss of generality, we con- ttistance-like" function where smaller values indicate more relevance. The expression arg min ey d(x,, y) yields the most relevant result for a query E X.
refer to systems that
sider
Specializing this notion yields a variety of different kinds of ML systems. = RRanee (N (-)) where N is an image featurization network such as ResNet50 HHe al. 2016), the formalism yields a visual search engine or "reverse image search". Though this work focuses on visual search, we note that if X' is the space of character sequences and is the space of webpages, this represents web search. In recommendation problems, X' are users and ) are items, such as songs news articles. In this work we aim to extract meaningful "interpretations" or "explanations" of the function d.
2.1 MODEL INTERPRETABILITY
The Bias- Lass-vereenee trade-off (ohavi et al. 1996) affects all machine learning systems and governs the relationship between model's expressiveness and generalization ability. In data-rich scenarios, a model's bias dominates generalization error and increasing the size of the model class can improve performance. However, increasing model complexity can degrade model interpretability because
2

---

Published as a conference paper at ICLR 2022
Integrated
Karee
Partition
Korn!
Figure 2: Comparison of first-order search interpretation methods which highlight pixels that con- tribute to similarity in red. Integrated Gradients (on pixels) struggles because well trained classifiers are invariant minor pixel changes and have uninformative gradients.
added parameters can lose their connection to physically meaningful quantities. This affects not only classification and regression systems, but search and recommendation architectures well. For example, the Netflix- priii--riieeeeee wriizen "BellKor" algorithm (Koren 2009), boosts and ensembles several different methods making it difficult to interpret through model parameter inspection alone.
To tackle these challenges, some works introduce model classes that are naturally interpretable (Nori et al. 2019 Hastie & Tibshirani| 1990). Alternatively, other works propose model-agnostic methods to explain the predictions of classifiers and regressors. Many of these approaches explain the local structure around specific prediction. [undberg & Lee| (2017) show that the Shapley value (Shap-) ley 1951), a measure of fair credit assignment, provides a unique and axiomatically characterized solution to classifier interpretability (SHAP). Furthermore, they show that Shapley values generalize LIME, DeepLIFT (Shrikumar et al. 2017). Layer- Wise Relevance Propagation (Bach et al.) 2015),
and several other methods (Strumbelj Kononenko, 2014: Datta et al. 2016, Lipovetsky & Con- klin 2001 Saabas (014)). Many works in computer vision use alternative approach called Class Activation Maps (CAMs). CAM projects the predicted class of a deep global average pooled (GAP) convolutional network onto the feature space to create low resolution heatmap of class-specific network attention. GradCAM (Selvaraju et al., 2017) generalizes CAM to architectures other than GAP and can explain a prediction using only single network evaluation. In Section 4 we show that CAM, GradCAM, and their analogue for search engine interpretability. [Zhu et al. (2019), are also unified by the Shapley value and its second order generalization, the Shapley-Tayle index.
2.2 FAIR CREDIT ASSIGNMENT AND THE SHAPLEY VALUE
Shapley values provide principled and axiomatic framework for classifier interpretation. We briefly overview Shapley values and point readers to Molnar (2020) for more detail. Shapley values orig- inated in cooperative game theory as the only fair way to allocate the profit of a company to its employees based on their contributions. To formalize this notion we define a "coalition game" as a set N of | players and a "value" function represents the expected payout earned by cooperating coalition of players. [Shapley (1951) show that the unique, fair credit assignment to each player, @ E N). can be calculated as:
2 - IR. In cooperative game theory, this function
ISI((IN
|S| 1)! NN!
(1)
Σ SCN(O)
(v (v(SU v(S))
(I)
Informally, this equation measures the average increase in value that a player brings to a coalition S by weighting each increase, v(S U {i}) =(S), by the number of ways this event could have happened during the formation of the "grand coalition" N. We note that this assignment, de. is the unique assignment that satisfies four reasonable properties: symmetry under player re-labeling, no credit assignment to dummy players, linearity (or it's alternative monotonicity). and efficiency which states that Shapley values should sum to v(N) - v(0) (Young 1985). Intuitively, these axioms require that a fair explanation should treat every feature equally (Symmetry). should not assign importance to features that are not used (Dummy), should behave linearly when the value function is transformed (Linear), and should sum to the function's value (Efficiency).
Shapley Values provide principled way to explain the predictions of machine learning model. To connect this work to model interpretability. we can identify the "features" used in a model as the "players" and interpret the value function, uSS), the expected prediction of the model when features N S are replaced by values from a "background" distribution. This background distribution allows for "counterfactual" relative explanations (Goyal et al. 2019).
3

---

Published as a conference paper at ICLR 2022
Interprstatton Baciggrund
Quary
Query
Bost Rosik
Retrieves
Figure 3: Explanations relative to a background distribution show why result better than an al-
Figure 4: Visualization of how regions of two similar images "correspond" according to the second-order search interpretability method SAM. We can use this correspondence to trans- fer labels or attention between similar images.
ternative. When asked why the best result (lower left) was better than the second best result (top right) our method correctly selects the player.
3 RELATED WORK
There is a considerable body of literature on model interpretability and we mention just a hand- ful of the works that are particularly related. One of our baseline methods, Dong et al.) was one of the first to present a generic visual search engine explanation reminiscent of a Parzen-Window based estimator. Fong & Vedaldi (2017) introduce method for explaining classifiers based on meaningful perturbation and Chefer et al. (202T) introduce a method for improving interpretation for transformer--ast based classifiers. Zhu et al. (2019) lifted CAM to search engines and we find that our Shapley- Taylor based method aligns with their approach for GAP architectures, [Singh & Anand (2019) and Fernando al. (2019) use LIME and DeepSHAP provide first-order interpretations of text but do not apply their methods to images. Ancona et al. (2019) introduce a distribution propaga- tion approach for improving the estimation of Shapley Values for deep models and can be combined with our approach. Many works implicitly use components that align with Shapley-Tai Taylor indices for particular functions. Works such as Fischer et al. (2015a); Sun al. (2020); Wang et al. (2020a); Chen et al. (2020c): Hou et al. (2019) use feature correlation layers to estimate and utilize corre- spondences between images. We show these layers are equivalent to Shapley-Taylor indices on the GAP architecture, and this allows create a correlation layer that handles counterfactual backgrounds. Other recent works have used learned co-attention within transformer architectures to help pool and share information across multiple domain types (Wei et al. 2020). Fu et al. (2020) attempt to learn a variant of GradCAM that better aligns with axioms similar to Shapley Values by adding efficiency regularizers. The method is not guaranteed to satisfy the axioms but is more "efficient".
We rely on several works to extend Shapley values to more complex interactions. Harsanyi 1963) generalized the Shapely value by introducing "dividend" that, when split and distributed among players, yields the Shapley values. Owen (1972) introduces an equivalent way to extend Shapley values using multi-linear extension of the game's characteristic function. (Sundararajan al. (2020) introduce the Shapley-Taylor index and show is equivalent to the Lagrangian remainder of Owen's extension. Integrated Hessians (Janizek et al. (020)) enable estimation of second- order variant of the Aumann- Shaully values and we use this approach to create a more principled second-order interpretation method for differentiable search engines.
UNIFYING FIRST-ORDER SEARCH INTERPRETATION TECHNIQUES
Though there is considerable body of work opaque-box classifier interpretability, opaque-box search engine interpretability has only recently been investigated (Singh & Anand 2019 Zhu et al. 2019 Zheng et al. 2020). We introduce approach to transform opaque and grey-box classification explainers into search engine explainers, allowing us to build on the rich body of existing work for classifiers. More formally, given a similarity function d X y - IR and elements X' and E y we can find the "parts" of that most contribute to the similarity by computing the Shapley values for the following value function:
ei (S) 2N + =- d(x, mask(y, S))
(2)
Where the function mask(..)) : y x 2 + V. replaces "parts" of y indexed by with components from background distribution. Depending the method, "parts" could refer to image superpix- els, small crops, or locations deep feature map. This formula allows us to lift many existing approaches to search engine interpretabillity For example, let X, and y represent the space of pixel
4

---

Published as a conference paper at ICLR 2022
representations of images. Let the grand coalition, N, index a collection of superpixels from the trieved image y. Let mask(y, S) act on an image y by replacing the S superpixels with background signal. With these choices, the formalism provides search-enging specific version of ImageLIME and KemelSHAP. Here, Shapley values for each i E S measure the impact of the corresponding superpixel the similarity function. If we replace superpixels with hierarchical squares of pixels we arrive at Partition SHAP (Lundberg). We can also switch the order of the arguments to get an approach for explaining the query image's 's impact on the similarity. In Figure 2 we qualitatively com- pare how methods derived from our approach compare to two existing approaches: SBSM (Dong al.) and VESM (Zheng et al., 2020), on a pair of images and a MocoV2 based image similarity model. In addition to generalizing LIME and SHAP we note that this approach generalizes VEDML Zhu et al. 2019). a metric-learning adaptation of CAM:
Proposition 4.1 Let X x y = CCW and represent the space of deep network features where C. C. W represent a channel, height, and width of the feature maps respectively. Let the function d= E. (AP(s),GAA(())
Let the grand coalition, N = 10, H x [0, W1. index the spatial coordinates of the image feature map y. Let the function mask(y, S) act on a feature map y by replacing the features at locations S with background signal b. Then:
1 Ov ((h, w) E EN = HW Σ EGAP(x)c(Uctt -belw))
Where GAP refers to global average pooling. We defer proof of this and other propositions to the Supplement. The results of this proposition mirrors the form of VEDML but with an added term to handle background distributions. These extra terms broaden the applicability of VEDML and we demonstrate their effect on explanations in Figure 3 In particular, we explain why two guitar players similar in general (no background distribution), and relative to the second-best result of guitar. Without a background, the explanation focuses on the guitar. However, when the explanation relative to an image of a guitar the explanation focuses instead on the "tie-breaking" similarities, like the matching player. With counterfactual queries one can better understand model's rationale behind relative similarity judgements and this can help in domains such as search engine optimiza- tion and automated medical diagnosis. We refer to Equation as the Search Activation Map (SAM) in analogy with the Class Activation Map. We note that in non- noP-GAP architectures, VEDML requires Taylor approximating nonlinear components. This heuristic corresponds estimating the Shapley val- ues for a linear approximation of the true value function. For nonlinear architectures such as those that use cosine similarity, SAM diverges from Shapley value theory and hence violates its axioms. We can remedy this by using a Kernel-based Shapley value approximator (Lundberg & Lee 2017) and refer to this approach Kernel SAM.
Though the Shapley value framework unifies several methods for search engine interpretability. we note that the popular technique GradCAM does not align with Shapley value theory when applied to our feature-based value function (though it does align with Shapley values for GAP classifiers) To connect this approach the theory of fair credit assignment, we show that GradCAM closely resembles Integrated Gradients (IG) (Sundararajan et al. 20175), an approximator to the Aumann- Shapley values (Aumann & Shapley 2015):
Let v(S): [0, 11. + R == (mask(x, S)) represent soft masking of the spatial locations of deep feature map x with the vector of zeros and applying differentiable function f. GradCAM is equivalent to Integrated Gradients approximated with single sample at a = 1 onlly if the function has spatially invariant derivatives:
Proposition 4.2
+R
v(h, w), (i.j) E 0f(z) Of(x) =f(x))
In typical case where I does not huve spatially invariant derivatives GradCAM violates the dummy axiom (see Section 2.2 and does not represent an approximation of Integrated Gradients.
Where a refers to the parameter of IG that blends background and foreground samples. We note that the aumann-Shaples values generalize the Shapley value to games where infinite numbers of players can join finitely many "coalitions".. These values align with Shapley values for linear functions but diverge in the nonlinear case. Proposition 4.2 also shows that in general GradCAM is sub-optimal and can be improved by considering Integrated Gradients modification to GradCAM as Integrated Gradient Search Activation Maps or 'IG SAM". We also note that this modification can be applied to classifier-hase GradCAM to yield a more principled
the feature space. We refer to this
5

---

Published as a conference paper at ICLR 2022
classifier interpretation approach. We explore this and show an example of GradCAM violating the dummy axiom in the Supplement.
SECOND-ORDER SEARCH INTERPRETATIONS
Visualizing the pixels that explain similarity judgement provides simple way to inspect where a retrieval system is attending to. However, this visualization is only part of the story. Images can be similar for many different reasons, and good explanation should clearly delineate these independent reasons. For example, consider the pair of images in the left column of Figure These images show two similar scenes of people playing with dogs, but in different arrangements. We seek not just a heatmap highlighting similar aspects, but data-structure capturing how parts of the query image correspond parts of retrieved image. To this end we seek measure the interaction strength between areas of query and retrieved images as opposed to the effect of single features. We refer this class of search and retrieval explanation methods as "second-order" methods due to their relation with second-order terms in the Shapley-Taye expansion in Section 5.1
5.1 HARSANYI DIVIDENDS
To capture the notion of interactions between query and retrieved images, must consider credit assignments to coalitions of features. (Harsanyi] 1963) formalize this notion with a unique and axiomatically specified way assign credit or "Harsanyi Dividends" every possible coalition, S, of N players in a cooperative game using the formula:
v(S) do(s)) = v(S) - Er
if [| = if [S] >
(4)
These dividends provide a detailed view of the function's behavior at every coalition. In particu- lar, |Harsanii (1963) show that Shapley values arise from distributing these dividends evenly across members of the coalitions, a process we refer to a "projecting" the dividends down. In this work we seek a second-order analog of the Shapley values, so we generalize the notion of sharing these divi- dends between individuals to sharing these dividends between sub-coalitions. This computation re- derives the recently proposed Shapley-Taylor Indices (Sundararajan et al. 2020p, which generalize the Shapley values to coalitions of a size k using the discrete derivative operator. More specifically, by sharing dividends, we can alternatively express Shapley-Taylos values for coalitions |S| = k as:
(T) TISCT (15)
(t))
Σ
(S)
Which states that the Shapley-Taye Taylor indices arise from projecting Harsanyi dividends onto the k order terms. We note that this interpretation of the Chapley-Taylon indices is slightly more flexible than that of Sundararajan et al. (2020) as allows one to define "jagged" fair credit assignments over just the coalitions of interest. Equipped with the Shapley-Taylor indices, di we can now formulate a value function for "second-order" search interpretations. As the first order case, consider two spaces X. y equipped with a similarity function d. We introduce the second-order value function:
(²(S)) 2 R == d(mask(2r, S), mask(y,S))
Where the grand coalition, N Ly U L,, are "locations" in both the query and retrieved images. These "locations" can represent either superpixels or coordinates in a deep feature map. Our chal- lenge now reduces to computing Shapley- -halley-Taylor indices for this function.
5.2 A FAST SHAPLEY-TAYLOG APPROXIMATION KERNEL
Though the Harsanyi Dividends and Chapley-Taylos indices provide a robust way allocate credit, they are difficult to compute. The authors of the Shapley-Taylee Taylor indices provide sampling based approximation, but this requires estimating each interaction term separately and scales poorly as dimensionality increases. To make this approach more tractable for high dimensional functions we draw parallel to the unification of LIME with Shapley values through a linear regression weight- ing kernel. In particular, one can efficiently approximate Shapley values by randomly sampling coalitions, evaluating the value function, and fitting a weighted linear map from coalition vectors to function values. We find that this connection between Shapley values and weighted linear models naturally lifts to a weighted quadratic estimation problem in the "second-order" case. In particular, introduce weighting kernel for second order Shapley-Taylor indices:

---

Published as a conference paper at ICLR 2022
Sem. Seg. bused Query Attention
Blur Attention
10"s
MSE
Metched Images
10-9
2M Projection
d(d.2) .15
Method
10"1
Sampling
Weighting
Komel Direct
10a
Number of Function Evaluations
Figure 5: Convergence of Shapley-Taylee es- timation schemes with respect to the Mean Squared Error (MSE) randomly initialized deep networks with 15 dimensional input. Our strategies (Kernel) converge with significantly fewer function evaluations.
Figure 6: Our Second-order explanation evalu- ation strategy. A good method should project query objects (top left and middle) to corre- sponding objects in the retrieved image (bottom left and middle). When censoring all but these shared objects (right column) the search engine should view these images similar.
|N - (19) (15)) (IN) - !S])
A(S)
Using this kernel, one can instead sample random coalitions, evaluate v, and aggregate the in- formation into weighted quadratic model with a term for each distinct coalition |S] I 2. This allows one to approximate all Shapley-Taylor indices of k 2 with single sampling proce- dure, and often requires 10x fewer function evaluations to achieve the same estimation aceu- racy. We show this speedup in Figure [5 on randomly initialized 15-dimensional deep networks. detailed description of this and other experiments in this work are in the supplement. We find that tion (Kernel-Direch) as opposed to randomly sampling coalitions and calculating weights (Kernel- Weighting). This direct sampling can be achieved by first sampling the size of the coalition from p(s) x ([NV) - 1)/(()))))))))))))())))) (INV) s)) and then randomly sampling a coalition of that size. When our masking function operates on super-pixels,
further speed up the method by directly sampling from the induced distribu-
refer to this the second-order generalization of Ker- nel SHAP. This also gives insight into the proper form for a second-orde generalization of LIME. In particular add L1 regularization (Tibshirani] 1996) and replace our kernel with a local similarity, S); mask(y, S) x; U where ";" represents concatenation, to create
A(S) = (expppX(maassee higher-order analogue of LIME. Finally we note that certain terms of the kernel are undefined due to the presence of (9) and |N| |S] in the denominator. These "infinite" weight terms encode hard constraints the linear system and correspond to the efficiency axiom. In practice we enumerate these terms and give them very large weight (10$) in regression. We reiterate that our ker- nel approximator converges to the same, uniquely-defined, values as prior sampling approaches but requires significantly fewer function evaluations.
5.3 RECOND--ORDER SEARCH ACTIVATION MAPS
In the first-order case, CAM and its search engine generalization, Search Activation Maps, arise naturally from the Shapley values of our first-order value function, Equation 2 To derive a second order generalization of SAM now look the Shapley-Taylor indices of our second order value function, Equation 6 applied to the same GAP architecture described in Proposition 4.1
Let the spaces X, y and function d be as in Proposition 4.1 tion, N, index into the spatial coordinates of both the query image features and retrieved image features y. Let the function mask(y, S) act on feature map y by replacing the corresponding features with background feature map for query features and b for retrieved features. Then:
Proposition 5.1
Let the grand coali-
Φu (1(h, w) Cy. (i.5) E Lx)) H2W2
Tehwwooi achw
Dehwwbei + acho beig
We note that the first term of the summation corresponds to the frequently used correlation layer Fischer al. 20155: (un al. 2020 Wang et al. 2020al Chen al. 2020c) and generalizes

---

Published as a conference paper at ICLR 2022
Table 1: Comparison of performance of first- and second-order search explanation methods. Meth-
ods introduced in this work are highlighted in pink. *Though SAM generalizes (Zhu et al. 2019
we refer to it as a baseline. For additional details see Section 6
SBSM
PSHAP
LIME
KSHAP
VESM
GCAM
SAM
IG IAM
KSAM
Metric
Order
Model
Model
Agnostic
Architecture Dependent
DN121
0.18
0.26
0.23
0.24
0.08
0.12
0.12
0.20
0.20
First
MoCoV2
0.22
0.30
0.28
0.30
0.13
0.19
0.21
0.25
0.25
Faithfulness
RN50
0.11
0.16
0.14
0.14
0.04
0.08
0.07
0.11
0.11
VGG11
0.14
0.16
0.15
0.15
0.05
0.09
0.11
0.14
0.14
DNT21
0.48
0.54
0.54
0.48
0.48
0.49
Second
MoCoV2
0.69
0.74
0.74
0.72
0.70
0.71
RN50
0.74
0.77
0.77
0.74
0.74
0.74
VGGI
0.68
0.71
0.71
0.69
0.69
0.70
DNI21
0.00
0.20
0.00
12.8
0.56
0.02
0.00
First
MoCoV2
0.00
0.10
0.00
0.46
0.53
0.03
0.00
Inefficiency
RN50
0.00
0.22
0.00
14.9
0.47
0.03
0.00
VGGI
0.00
0.27
0.00
4.20
0.54
0.05
0.00
DNI21
0.14
0.01
0.21
0.03
0.01
Second
MoCoV2
0.13
0.01
0.20
0.02
0.01
RN50
0.06
0.01
0.06
0.01
0.01
VGGI1
0.11
0.01
0.22
0.03
0.01
DNI21
0.55
0.68
0.67
0.68
0.68
0.67
mloU
Second
MoCoV2
0.57
0.70
0.69
0.70
0.70
0.69
RN50
0.55
0.67
0.66
0.69
0.66
0.65
VGG11
0.54
0.68
0.67
0.72
0.73
0.70
the "point-to-poin"" signal in Zhu et al. (2019). In particular, axiomatically derived version has the extra terms allow countertactual explanations against different background signals. Like in the first-order case, this closed form only holds in the GAP architecture. To extend the method in a principled way we use our second-order kernel approximator and refer to this as second-ordd KSAM. We also introduce generalization using higher order analogue of Integrated Gradients, Integrated Hessians (Janizek et al. 2020), applied to our feature maps. We refer to this as second- order IGSAM. In Section A.3 of the Supplement
prove that this approach is proportional the Shapley-Tay -aallor indices for the GAP architecture. We can visualize these second-order explanations by aggregating these Shapley-Taylor indices into matrix with query image locations as rows and retrieved locations as columns. Using this matrix, we can "project" signals from a query to retrieved image. We show few examples of attention projection using our second-order SAM in Figure
EXPERIMENTAL EVALUATION
First Order Evaluation Evaluating the quality of an interpretability method requires careful ex- perimental design and independent from what "looks good" to our human eye. If a model explana- tion method produces "semantic" connections between images should be because to the underlying model is sensitive to these semantics. As result, we adopt the evaluation strategy of Lundberg & Lee (2017). which measures how well the model explanation approximates the expected influence of individual features. In particular, these works calculate each feature's 's importance, replace the top n% of features with background signal. and measure the effect on the function. good model inter- pretability method should cause the replacement of the most important features, and hence cause the largest expected change in the function. We refer to this metric as the "Faithfulness" of an interpre- tation measure as it directly measures how well an interpretation method captures the behavior of an underlying model. Figure in the Supplement diagrams this process for clarity. our experiments blur the top 30% of image pixels to compute faithfulness. For those methods that permit it, also measure how much the explanation violates the efficiency axiom. In particular we compare the sum of explanation coefficients with the value of v(N) v00) and refer to this the "Inefficiency" of the method. For additional details and evaluation code please see Section A.2 in the Supplement.
8

---

Published as a conference paper at ICLR 2022
Second Order Evaluation In the second-order case we adopt the evaluation strategy of Janizek et al. 2020) which introduce a analogous second-order faithfulness measure. In particular, we mea- sure how well model explanations approximate the expected interaction between two features. To achieve this, we select an object from the query image, use the second order explanation to find the corresponding object in the retrieved image, censor all but these two objects. We measure the new similarity as a measure of Faithfulness and illustrate this process in In Figure [6] We additionally quantify the inefficiency of several second-order methods as well as their effectiveness for semantic segmentation label propagation. In particular, we measure how well the explanation method can project a source object onto a target object. We treat this as a binary segmentation problem and mea- sure the mean intersection over union (mloU) of the projected object with respect to the true object mask. We note that mloU not a direct measurement of interpretation quality, but it can be useful for those intending to use model-interpretatin ctt al. 2020b). These results demonstrate that axiomatically grounded model explanation methods such IG SAM could offer improvement downstream tasks. Because human evaluations intro- duce biases such as preference for compact or smoothness explanations, we consider Mechanical 2010) studies outside the scope of this work.
methods for label propagation (Ahn et al. [2019] Wang]
Turk (Paolacci et al.
Datasets We evaluate our methods on the Pascal VOC (Everingham et al. 2010) and MSCoCo Caesar et al. (2018) semantic segmentation datasets. To compute first and second order faithfulness we mine pairs of related images with shared object classes. We use the MoCo V2 (Chen et al.) 2020b) unsupervised image representation method to featurize the training and validation sets. For each image in the validation set we choose a random object from the image and find the training image that contains an object of the same class (Hamilton et al. 2020).
Results In Table and Table of the Supplement we report experimental results for PaScalVOC and MSCoCo respectively. We evaluate across visual search engines created from four different backbone networks: DenseNet121 (Huang et (017)) MoCo v2 (Chen et al. 2020b), ResNet50 (He et al., 2016), and VGG11 (Simonyan & Zisserman 2014) using cosine similarity on GAP fea- tures. As baselines we include VESM, SBSM, and SAM which generalizes (Zhu et al. 2019). We note that SBSM was not originally presented as a second-order method, and we describe how it can be lifted this higher order setting in Section IT of the Supplement. We also evaluate several existing classifier explanation approaches applied to our search explanation value functions such as Integrated Gradients (Sundararajan et al. (017a) on image pixels, Partition SHAP (Lundberg), LIME, Kernel SHAP (KSHAP), and GradCAN AM (GCAM) on deep feature maps (Selvaraju et al., 2017 For second-ord order variants of LIME and SHAP we used the local weighting kernel and our Shapley-Taylor approximation kernel from Section 5.2 Overall, several key trends appear. First, Shapley and Aumann -Shaleey based approaches tend to be the most faithful and efficient methods, but at the price of longer computation time. One method that strikes balance between speed and quality is our Integrated Gradient generalization of CAM which has both high faithfulness, low inef- ficiency, and only requires handful of network evaluations (~ 10a). Furthermore, grey-box feature interpretation methods like SAM and IG SAM tend to perform better for label propagation. Finally, methods beat existing baselines in several different categories and help to complete the space of higher order interpretation approaches. We point readers to the Section A.2 for additional details, compute information, and code.
CONCLUSION
In this work we have presented a uniquely specified and axiomatic framework for model-agnostic search, retrieval, and metric learning interpretability using the theory of Harsanyi dividends. We characterize search engine interpretability methods as either "first" or "second" order methods de- pending on whether they extract the most important areas or pairwise correspondences, respectively. We show that Shapley values of a particular class of value functions generalize many first-order methods, and this allows us to fix issues present in existing approaches and extend these approaches to counterfactual explanations. For second order methods we show that Shapley-Tayloo indices gen- cralize the work Zhu et al. (2019) and use our framework to introduce generalizations of LIME, SHAP, and GradCAM. We apply these methods to extract image correspondences from opaque-box similarity models, a feat not yet presented in the literature. To accelerate estimation higher order Shapley-Taylor indices, contribute new weighting kernel that requires 10x fewer function eval- uations. Finally, we show this game-theoretic formalism yields methods that are more "faithful" to the underlying model and better satisfy efficiency axioms across several visual similarity methods.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We would like to thank Siddhartha Sen for sponsoring access the Microsoft Research compute infrastructure. We would also like to thank Zhoutong Zhang, Jason Wang, and Markus Weimer for their helpful commentary on the work. We thank the Systems that Learn program at MIT CSAIL for their funding and support.
This material based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. 2021323067. Any opinion, findings, and conclusions recommenda- tions expressed this material are those of the authors(s) and do not necessarily reflect the views of the National Science Foundation. This work is supported by the National Science Foundation under Cooperative Agreement PHY-2019786 (The NSF AI Institute for Artificial Intelligence and Fundamental Interactions, http://iaif..org/)
REFERENCES
Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süisstrunk. Slic superpixels. Technical report, 2010.
Jiwoon Ahn, Sunghyun Cho, and Suha Kwak. Weakly supervised learning of instance segmentation with inter- pixel relations. In Proceedings the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2209-2218, 2019.
Marco Ancona, Cengiz Oztireli, and Markus Gross. Explaining deep neural networks with a poly- nomial time algorithm for shapley value approximation. In International Conference on Machine Learning. pp. 272-281. PMLR, 2019.
Robert J Aumann and Lloyd Shapley. Values of non-atomic games. Princeton University Press, 2015.
Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Müller, and Wojeiech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise wise relevance propagation. PloS one, 10(7):e0130100 2015.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions pattern analysis and machine intelligence, 7788) 2013.
Bing. Beyond text queries: Searching with bing visual search, Jun 2017. URL https://aka. ms/ A./AAas77p
Holger Caesar, Jasper Uijlings, and Vittorio Ferrari. Coco-stuff: Thing and stuff classes in context. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1209- 1218, 2018.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. arXiv preprint 2088:20006008882, 2020.
Hila Chefer, Shir Gur, and Lior Wolf. Transformer interpretability beyond attention visualization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp- 782-791, 2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint arXiv:2002.05709, 2020a.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint wrXiv:2003.0422)) 2020b.
Yun-Chun Chen, Yen- Yu Lin, Ming- Hsuan Yang, and ha-BBnn Huang. Show, match and segment: Joint weakly supervised learning of semantic matching and object co-segmentation. IEEE Trans- actions Pattern Analysis and Machine Intelligence (PAMI), 2020c.
10

---

Published as a conference paper at ICLR 2022
Sumit Chopra, Raia Hadsell, and Yann LeCun. Learning similarity metric discriminatively, with application to face verification. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), volume 1. pp. 539-546. IEEE, 2005.
Anupam Datta, Shayak Sen, and Yair Zick. Algorithmic transparency via quantitative input influ- ence: Theory and experiments with learning systems. In 2016 IEEE symposium on security and privacy (SP), pp. 598-518-8 617. IEEE, 2016.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-248222 255. leee, 2009.
Alejandro Diaz. Through the google goggles: Sociopolitical bias in search engine design. In Web search, pp. 11-34. Springer, 2008.
Bo Dong, Roddy Collins, and Anthony Hoogs. Explainability for content-based image retrieval.
M. Everingham, L. Van Gool, C. I. Williams, J. Winn, and A. Zisserman. The pascal visual object classes (voc) challenge. International Journal of Computer Vision, 88(2):303-333 June 2010.
Zeon Trevor Fernando, Jaspreet Singh, and Avishek Anand. A study on the interpretability of neural retrieval models using deepshap. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development Information Retrieval, pp. 1005-1008, 2019.
Philipp Fischer, Alexey Dosovitskiy, Eddy Ilg, Philip Häusser, Caner Hazırba, Vladimir Golkov, Patrick Van der Smagt, Daniel Cremers, and Thomas Brox. Flownet: Learning optical flow with convolutional networks. arXiv preprint arXiv: 1504. 004.06652, 2015a.
Philipp Fischer, Alexey Dosovitskiy, Eddy Ilg, Philip Häusser, Caner Hazırba,, Vladimir Golkov, Patrick Van der Smagt, Daniel Cremers, and Thomas Brox. Flownet: Learning optical flow with convolutional networks. arXiv preprint arXiv: 1544066500 2015b.
Ruth C Fong and Andrea Vedaldi. Interpretable explanations of black boxes by meaningful pertur- bation. In Proceedings of the IEEE international conference on computer vision, pp. 3429-3437, 2017.
Ruigang Fu, Qingyong Hu, Xiaohu Dong, Yulan Guo, Yinghui Gao, and Biao Li. Axiom- based grad-cam: Towards accurate visualization and explanation of cnns. arXiv preprint arXiv:2008. 023 2020.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp- 315-323. JMLR Workshop and Conference Proceedings, 2011.
Eric Goldman. Search engine bias and the demise of search engine utopianism. Yale JL Tech., 8: 188, 2005.
Yash Goyal, Ziyan Wu, Jan Ernst, Dhruv Batra, Devi Parikh, and Stefan Lee. Counterfactual visual explanations. In International Conference on Machine Learning, pp. 2376-2384, PMLR, 2019.
Mark Hamilton, Stephanie Fu, William T Freeman, and Mindren Lu. Conditional image retrieval. arXiv preprint urXiv:2007.07177, 2020.
John Harsanyi. simplified bargaining model for the n- n-person cooperative game. International Economic Review, 4(2):194-220 1963.
Trevor Hastic and Robert J Tibshirani. Generalized additive models, volume 43. CRC press, 1990.
Kaiming He and Yuxin Wu. Moco: Momentum contrast for unsupervised visual representation learning. https: : //g thub. com fa resea waaaacchhooooooo 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
11

---

Published as a conference paper at ICLR 2022
Ruibing Hou, Hong Chang, Bingpeng Ma, Shiguang Shan, and Xilin Chen. Cross attention network for few-shot classification. arXiv preprint 191.:1910.07677, 2019.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Joseph Janizek, Paseal Sturmfels, and Su-In Lee. Explaining explanations: Axiomatic feature interactions for deep networks. arXiv preprint arXiv:2002.04138, 2020.
Ron Kohavi, David H Wolpert, al. Bias plus variance decomposition for zero-one loss functions. In ICML, volume 96, pp. 275-83, 1996.
Yehuda Koren. The bellkor solution to the netflix grand prize. Netflix prize documentation, 81 (2009):1-10, 2009.
Stan Lipovetsky and Michael Conklin. Analysis of regression in game theory approach. Applied Stochastic Models in Business and Industry, 17(4)3319-33,, 2001.
Scott Lundberg. shap. URL
Scott M Lundberg and Su-In Lee. A unified approach interpreting model predictions. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems 30, pp. 4765-4774. Curran Associates, Inc., 2017.
Sébastien Marcel and Yann Rodriguez. Torchvision the machine-vision package of torch. In Pro- ceedings of the 18th ACM international conference on Multimedia, pp. 1485-1488, 2010.
Christoph Molnar. Interpretable machine learning. Lulu. com, 2020.
Abbe Mowshowitz and Akira Kawaguchi. Assessing bias in search engines. Information Processing & Management, 38(1))141-156, 2002.
Pandu Nayak. Understanding searches better than ever before, Oct 2019. URL https://blbg
Harsha Nori, Samuel Jenkins, Paul Koch, and Rich Caruana. Interpretml: A unified framework for 2019.
machine learning interpretability. arXiv preprint
Guillermo Owen. Multilinear extensions of games. Management Science, 286--99 1972.
Gabriele Paolacci, Jesse Chandler, and Panagiotis Ipeirotis. Running experiments on amazon mechanical turk. Judgment and Decision making, 5(5):411-411) 2010.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. H. Wallach, H. Larochelle, Beygelzimer, F. d'Alché-Bon E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019.
Alec Radford, Jong Wook Kim. Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, al. Learning transferable visual models from natural language supervision. arXiv preprint arXiv:2103.00M: 2021.
Marco Ribeiro. lime.
2021.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should 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.
12

---

Published as a conference paper at ICLR 2022
Karsten Roth, Timo Milbich, Samarth Sinha, Prateek Gupta, Bjöm Ommer, and Joseph Paul Cohen. Revisiting training strategies and generalization performance in deep metric learning, 2020.
Ando Saabas. Interpreting random forests, Oct 2014. URL htte:://bloo.dattadii. net//
interpreting random-
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based local- ization. In Proceedings of the IEEE international conference on computer vision, pp. 618-628 2017.
Lloyd S Shapley. Notes on the n-person game ii: The value of an n-person game. 1951.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1555 2014.
Jaspreet Singh and Avishek Anand. Exs: Explainable search using local model agnostic inter- pretability. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining. pp. 770-773, 2019.
Erik Strumbelj and Igor Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowledge and information systems, 41(3):647-665, 2014.
Xiaoyuan Su and Taghi M Khoshgoftaar. A survey of collaborative filtering techniques. Advances in artificial intelligence, 2009, 2009.
Guolei Sun, Wenguan Wang, Jifeng Dai, and Luc Van Gool. Mining cross-image semanties for weakly supervised semantic segmentation. European Conference on Computer Vision, pp- 347-365. Springer, 2020.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, pp. 3319-3328, PMLR, 2017a
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, pp. 3319-3328. PMLR, 2017b.
Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction PMLR, 2020.
index. In International Conference on Machine Learning, pp.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. arXiv preprint TtXXvv/700.0370000 2017.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Courna- peau, Evgeni Burovski. Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nel- son, Eric Jones, Robert Kern, Eric Larson, C J Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul Mul- bregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020. doi: 1038/44/ 192-019-0686-2..
Qianqian Wang, Xiaowei Zhou, Bharath Hariharan, and Noah Snavely. Learning feature descriptors using camera pose supervision. In Proc. European Conference on Computer Vision (ECCV),
2020a.
Yude Wang, Jie Zhang, Meina Kan, Shiguang Shan, and Xilin Chen. Self-supervised equivari- ant attention mechanism for weakly supervised semantic segmentation. In Proceedings of the IEFF/CVF Conference Computer Vision and Pattern Recognition, pp. 12275-12284, 2020b.
13

---

Published as a conference paper at ICLR 2022
Xi Wei, Tianzhu Zhang, Yan Li, Yongdong Zhang, and Feng Wu. Multi-modality attention network for image and sentence matching. In Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition, pp. 10941-10950, 2020.
Peyton Young. Monotonic solutions of cooperative games. International Journal of Game Theory, 14(2):65-72, 1985.
Meng Zheng, Srikrishna Karanam, Terrence Chen, Richard J Radke, and Ziyan Wu. Towards visu- ally explaining similarity models. arXiv preprint arXiv:200S.0660 06035, 2020.
B. Zhou, A. Khosla, Lapedriza. A., A. Oliva, and A. Torralba. Learning Deep Features for Discrim- inative Localization. CVPR, 2016.
Sijie Zhu, Taojiannan Yang, and Chen Chen. Visual explanation for deep metric learning. arXiv preprint arXiv:1909. 2019.
14

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.I VIDEO AND CODE
We include short video description of our work http://psss/aaeem///////ttttooo/
We also provide training and evaluation code at httpss//aka.ntt//xoonttttttic
A.2 EVALUATION AND IMPLEMENTATION DETAILS
Faithfulness
= d dq r) r(
Matched Images
= .2
d(
d(q.r)= 33
1 Order Interp.
Blur Top 30%
Figure 7: First-order interpretation evaluation strategy. A good method should highlight pixels the query image (top left and middle) that, when censored (top right), have the largest possible impact on the cosine distance.
Models: Our evaluation experiments visual similarity systems built from "backbone" net- works that featurize images and compare their similarity using cosine distance. We consider su- pervised backbones and contrastive unsupervised backbones. In particular, ResNet50 (He et al. 2016), VGG11 (Simonyan & Zisserman 2014), and DenseNet121 (Huang et al. (017)) are trained with human classification annotations from the ImageNet dataset (Deng et al., 2009) and MoCo V2 is trained using unsupervised contrastive learning on ImageNet. We use torchvision (Marcel & Ro- driguez, 2010) based model implementations and pre-trained weights except for MocoV2 which we download from He & Wu (2021) (800 epoch model). For kernel convergence experiments in Figure 5 we use randomly initialized three layer deep networks with Glorot (Glorot et al., (01T) initializa- tion, rectified linear unit activations, and 20 dimensional hidden layer. We note that the functional form is not of much importance for these experiments so long as the function is nonlinear and non-quadratic. We provide additional example in Figure 10 on random 15 dimensional Boolean functions formed by enumerating and summing all possible variable products and weighting each by uniform coefficient between and 10.
Data: For evaluations within Table T we use the Pascal VOC (Everingham et al. 2010) dataset. In particular we form paired image dataset by using MoCo V2 to featurize the training and validation sets. All experiments use images that have been bi-eiryyyly resized to 224 x 224 pixels. For each image the PascalVOC validation set we choose random segmentation class that contains over 5% of image pixels. We then find each validation image's closest "Conditional Nearest Neighbor" (Hamilton et al. 2020) from the images the training set of the chosen segmentation class. We use cosine similarity between MoCoV2 deep features to find nearest neighbors. With this dataset of pairs, we can then compute our first and second order evaluation metrics. We provide instructions for downloading the pairs of images in the attached code. We note that approach for selecting pairs of images with matching segmentation labels allow for measuring Faithfulness and success in label propagation as measured by mloU.
15

---

Published as a conference paper at ICLR 2022
Metrics: Our attached code contains implementations all metrics for preciseness but we include descriptions of metrics here for clarity. To measure first order faithfulness, we take given validation image and training image from dataset of paired images and compute the first order heat-map over the validation image. We then blur the top 30% of pixels by blurring the image with a 25 x 25 pixel blur kernel and replacing the top 30% of original image pixels with those from the blurred image. The drop in cosine similarity between the unblurred images and the unblurred training and blurred validation image is the first order faithfulness. We illustrate our first-order evaluation strategy in Figure
For our second-order evaluation, we use the ground truth semantic segmentation mask of the train- ing image as a "query" attention signal. We then use the second-orde interpretation methods to "project" this attention to the "retrieved" validation image. We censor all but the most-attended pixels in the retrieved image. The size of the remaining pixels matches the size of the validation image's selected semantic segmentation mask. the second-order case we additionally measure the mean intersection over union (mloU) of the resulting mask compared to the ground-truth re- trieved image segmentation. A good approach should attend to jut the pixels of the segmentation class and thus yield mloU of (maximum value) as a binary segmentation problem. We illustrate our second- order evaluation strategy in Figure 6
Finally, for those methods that permit it, measure how much they violate the efficiency axiom by summing the interpretation coefficients and comparing with v(N) - (0). In the first order setting v(N) is the similarity between query and retrieved image, and v(0) is the similarity between query and a blurred retrieved image (with 25 pixel blur). In the second order setting v(0) represents the similarity when both images are blurred. For SAM-based methods we replace features with those from blurred images. To compute the sum of interpretation coefficients for kernel methods we sum over Shapley values in the first order case and over Shapley-Taylo indices of order A S 2 in the second-order case. For Partition SHAP Lundbergg we sum coefficients over all pixels. For Integrated Hessian's 's we sum over all first and second order coefficients as described in Janizek al. (202)).
In tables we report mean values of Inefficiency, and Faithfulness metrics and note that for these experiemtns the Standard Error of the Mean (SEM) is far below the three significant figure precision of the table.
First Order Methods: For first order explanations we use the official implementation of Image- LIME (Ribeiro 202T) and use the SHAP package for Integrated Gradients, Partition SHAP, and Kernel SHAP (Lundberg). We re-implement SBSM and VESM in PyTorch from the instructions provided in their papers. For sampling procedures such as LIME, Kernel SHAP, and Partition SHAP we use 5000 function evaluations. For first and second-order super-pixel based methods (LIME, Kernel-SHAP) we use the SLIC superpixel method (Achanta et al.] 2010 provided in the Scipy library (Virtanen et al. 2020 with 50 segments, compactness = 10, and o = 3. For SBSM window size of 20 pixels and stride of 3 pixels. We batch function evaluations with minibatch size 64 for backbone networks and 64 x 20 for SAM based methods. For all background distributions we blur the images with 25-pixel blur kernel with the exception of LIME and SBSM which use mean color backgrounds.
Second Order Methods: For second order methods we use the same background and superpixel algorithms, but implement all methods within Py PoTch for uniform comparison. For SBSM, Ker- 20000 samples and for KSAM and IGSAM we use 40000 samples.
nel SHAP, and LIME For IGSAM we use the expected Hessians method referenced in the supplement of Janizek et al. 2020). We use the PyTorch "Istsq"function ffunction for solving linear systems. For more details generalization of SBSM see Section A.
Compute and Environment:
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. For all methods that require many network evaluations we use PyTorch DataLoaders with 18 background processes to eliminate 10 bottlenecks. We standardize experiments using Azure Machine Learning and run each experiment separate virtual machine avoid slowdowns due to scarce CPU or GPU resources.
16

---

Published as a conference paper at ICLR 2022
A.3 PROOF OF PROPOSITION 4.2
Let u(S): [0, 1j + +R = I [mask(a S)) represent soft masking of the spatial locations of a deep feature map with the vector of zeros and applying differentiable function f. We begin with the formulation of Integrated Gradients:
haw (S) (Shw Sha)) [ Dv(aS (1-
FThw
In case the foreground, S == 1 HW is mask of all 1s and the background, S', is the zero mask of the same shape. We note that the 0T.w refers to taking the partial the full input as, not just the mask We include this to stress the subtle difference which can be missed in a quick reading of the equations of Sundararaaan et al. (2017a). In this
formula is simplified to:
Ov(aS)
h/ (S)
Ja-o Hhww
Approximating this integral with single sample at yields; (S)
(G)w(S) 20
0Smm
0f(mask(r, S))
0Tww
now f(x ④ S)
(f(x)
Σ Fchw dKcho
Σ Jeho GAP(V
(Spatially Invariant Derivatives)
Which is precisely the formulation GradCAM. This also makes clear that the global average pooling of GradCAM causes the method deviate from integrated gradients in the general case. To construct a function where GradCAM violates the dummy axiom we simply have to violate the spatial invariance of gradients. We provide a specific example of this violation in A.4
A.4 GRADCAM VIOLATES THE DUMMY AXIOM
GradCAM
KSAM
IGSAM
Query
Retrieved
Figure 8: Interpretations of a function that purposely ignores the left half of the image. KSAM and IGSAM properly assign zero weight to these features. GradCAM does not and hence violates the dummy axiom of fair credit assignment.
It is straightforward to construct examples where GradCAM violates the dummy axiom. For exam- ple, consider the function: d(r, v) simeasiie (GAa @ M))
17

---

Published as a conference paper at ICLR 2022
Where cosine represents cosine similarity, @ represents elementwise multiplcation, and M [0, 1]CWW is mask where Mekw = 0 if w I W and Mchw = otherwise. Intuitively, M removes the influence of any feature the left of the image making these features "dummy" features for the model. Because GradCAM spatially averages the gradients prior to taking the inner product with the feature map all features are treated equally regardless of how they used. In this example, depicted in Figure 8 positive contributions from the right side of the image are extended to the left side of the image despite the fact that the mask, M stops these features from impacting the prediction. Using Shapley or Aumann-Shann Shapley approximator on the feature space does not suffer from this effect as shown in the two right columns of Figure g
2
A.5 INTEGRATED GRADIENT CAM
Sections A.4 and A.3 demonstrate that GradCAM can violate the dummy axiom when the function has spatially varying gradients which is a common occurrence especially one is trying to inter- pret deeper layers of network. We remedy this by instead considering Integrated Gradients function which masks the spatial locations of a deep feature map. More specifically our Integrated Gradient generalization of CAM takes the following form:
IGCAM w) := f.- 0f + aa b))
TThw
Where f is the classification "head", x E RCHW is tensor of deep image features, M == HW is a mask of over the spatial location the features, b RCHW is background signal commonly taken to be zero in GradCAM. We note that the ãT.
8 refers to taking the partial of the full input 6 + aM O (x - b), not just the mask. We include this to stress the subtle difference which can be missed in a quick reading of the equations of Sundararajaan et al. (2017a). This variant of GradCAM does not violate the dummy axiom and satisfies the axioms of the Aumann Shapley fair credit assignment.
18

---

Published as a conference paper at ICLR 2022
A.6
ADDITIONAL SIMILARITY VISUALIZATIONS
Integrated
Kornel
Partition
Kerei SAM
Graditton
Betricves
Figure 9: Additional first-order search interpretations on random image pairs from the Pascal VOC dataset
19

---

Published as a conference paper at ICLR 2022
A.7 ADDITIONAL RESULTS FOR STANFORD ONLINE PRODUCTS
Comparison of performance of first-order search interpretation methods across different visual search systems the Stanford Online Product dataset. Methods introduced in this work highlighted in pink. *Though SAM generalizes Zhu et (2019) we refer to it as a baseline. For additional details Section 6
Table 2:
SBSM
PSHAP
LIME
KSHAP
VESM
GCAM
SAM
IG SAM
KSAM
Metric Model
Model
Agnostic
Architecture Dependent
DNI21
0.18
0.23
0.20
0.22
0.09
0.13
0.12
0.18
0.18
Faith.
MoCoV2
0.24
0.30
0.27
0.18
0.14
0.2
0.21
0.24
0.24
RN50
0.11
0.14
0.12
0.13
0.03
0.07
0.07
0.10
0.10
VGG11
0.15
0.16
0.14
0.15
0.04
0.08
0.09
0.12
0.12
DNI21
0.00
0.24
0.00
11.2
0.54
0.02
0.00
Ineff.
MoCoV2
0.00
0.17
0.00
0.34
0.57
0.02
0.00
RN50
0.00
0.21
0.00
13.6
0.39
0.02
0.00
VGG11
0.00
0.24
0.00
4.13
0.47
0.04
0.00
A.8 ADDITIONAL RESULTS FOR CALTECH-UCSI BIRDS 200 (CUB) DATASET
Table 3: Comparison of performance of first-order search interpretation methods across different visual search systems the CUB dataset. Methods introduced in this work highlighted in pink. *Though SAM generalizes Zhu et al. (2019) we refer to it as baseline. RN50-ML refers to ResNet50 architecture trained for metric learning on the CUB dataset with the margin loss Roth et al.. 2020). For additional details see Section 6
SBSM
PSHAP
LIME
KSHAP
VESM
GCAM
SAM
IG SAM
KSAM
Metric Model
Model
Agnostie
Architecture
Dependant
DNT21
0.25
0.38
0.31
0.34
0.15
0.10
0.12
0.30
0.30
RN50-MI.
0.39
0.49
0.47
0.49
0.04
0.14
0.17
0.41
0.41
Faith.
MoCoV2
0.32
0.47
0.39
0.41
0.26
0.26
0.26
0.34
0.34
RN50
0.14
0.21
0.18
0.18
0.05
0.07
0.07
0.14
0.14
VGG11
0.23
0.31
0.26
0.27
0.11
0.15
0.16
0.23
0.22
DNI21
0.00
0.17
0.00
16.0
0.58
0.02
0.00
RN50-ML
0.00
0.13
0.00
5.23
0.48
0.03
0.00
Ineff.
MoCoV2
0.00
0.19
0.00
0.44
0.60
0.03
0.00
RN50
0.00
0.15
0.00
15.5
0.43
0.02
0.00
VGG11
0.00
0.17
0.00
4.25
0.54
0.05
0.00
20

---

Published as a conference paper at ICLR 2022
A.9 ADDITIONAL RESULTS FOR MS COCO
Table Comparison of performance of first and second-order search interpretation methods across different visual search systems the MSCOCO dataset. Methods introduced in this work highlighted in pink. *Though SAM generalizes Zhu et al. (011) we refer to it as a baseline. For additional details Section 6
SBSM
PSHAP
LIME
KSHAP
VESM
GCAM
SAM#
IG
KSAM
Metric
Order
Model
Model
Agnostic
Architecture Dependent
DN121
0.18
0.24
0.22
0.22
0.10
0.12
0.11
0.14
0.17
First
MoCoV2
0.25
0.37
0.33
0.35
0.15
0.23
0.24
0.24
0.28
Faithfulness
RN50
0.10
0.14
0.12
0.12
0.04
0.07
0.07
0.07
0.09
VGG11
0.14
0.15
0.14
0.14
0.05
0.09
0.1
0.10
0.12
DN121
0.49
0.57
0.57
0.5
0.51
0.49
Second
MoCoV2
0.73
0.79
0.79
0.77
0.77
0.78
RN50
0.73
0.78
0.78
0.75
0.75
0.73
VGG11
0.67
0.73
0.73
0.71
0.71
0.72
DNT21
0.00
0.22
0.00
12.3
0.6
0.02
0.00
First
MoCoV2
0.00
0.11
0.00
0.46
0.66
0.02
0.00
Inefficiency
RN50
0.00
0.22
0.00
15.8
0.47
0.02
0.00
VGG11
0.00
0.31
0.00
3.47
0.59
0.04
0.00
DNI21
0.15
0.01
0.20
0.01
0.00
Second
MoCoV2
0.10
0.01
0.09
0.02
0.00
RN50
0.07
0.01
0.07
0.02
0.00
VGGI1
0.11
0.01
0.19
0.04
0.00
DN121
0.50
0.62
0.61
0.62
0.63
0.52
mloU
Second
MoCoV2
0.52
0.62
0.61
0.64
0.66
0.60
RN50
0.50
0.62
0.61
0.63
0.65
0.48
VGGI1
0.50
0.62
0.61
0.66
0.67
0.60
21

---

Published as a conference paper at ICLR 2022
A.10 ADDITIONAL KERNEL CONVERGENCE RESULTS
10
10
MSE
10-1
Method
Sampling
Kernel Weighting
10
Kernel Direct
10a
10*
Number of Function Evaluations
Figure 10: Kernel convergence for random functions generated by randomly choosing coefficients.
Results generally mirror those for randomly initialized deep networks
A.11 GENERALIZING SBSM TO JOINT SEARCH ENGINE INTERPRETABILITY
Before generalizing SBSM (Dong et al.) to joint interpretability we will review the original imple- mentation for marginal interpretability. SBSM uses sliding square mask and multiple evaluations of the search engine to determine which regions of the image are important for similarity. More for- mally, let g, and r represent the pixels of the query image and retrieved image. Let M2) represent the result of replacing a square pixels of size s x 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 the baseline similarity value and stored in weight matrix, w:
Wij min [d (M))(0) r) r)
(10)
Intuitively speaking, the weights way represent the impact of masking square centered at (i,j). For areas that are critical to the similarity, this will result in We > 0. Finally, an attention mask on the query image is formed by a weighted average the masks used to censor the images. For square masks, this can be achieved efficiently using deconvolution with kernel of ones of size X the weight matrix w. We also note that instead of evaluating the (expensive) distance computation d for every pixel (i,j), generalization.
also sample pixels censor. We this approach in our joint
To generalize SBSM respectively. We sample mask locations and calculate weights designed to capture the intuition that censoring corresponding areas cause similarity to increase opposed decrease. More specifically we use the following weighting scheme:
pair of masks, one for the query image and for the retrieved image
bw min [d( (M₁ (q) Mi, (r)) w
(11)
Because evaluating the similarity function for every (i.j. h, w) combination is prohibitively expen- sive, instead sample masked images for computation. To project attention from query pixel, we query for all masks that overlap with the selected query pixel, and then average their corresponding retrieved masks according the weights caleulated in Equation IT
22

---

Published as a conference paper at ICLR 2022
A.12 PROOF OF PROPOSITION 4.1
Let X' = = = CCWW and represent the space of deep network features where C, H, W rep- resent channel, height, and width of the feature maps respectively. Let the function d == Ee (CAP()).GAA(g)) Let the grand coalition, .N = 00 H] x [o, WI, index into the spatial coor- dinates of the image feature map y. Let the function mask(y, S) the features at locations S with a background signal b. For notational convenience let (1(()) == (i) represent the Shapley value the jth player under the value function v. We begin by expressing the left-hand side of the proposition:
feature map y by replacing
how (v) Vhu
Σ GAPLc),.AP(masskk 8)
Vhw
HW E GAP(I)e
mask(y, S) h/w!
Σ
Σ
thww
Σ GAP(2) (emm)sss Searew
(Linearity)
HW
h'w
HW Whow
GAP(a)) S)ahar
(Dummy)
HW Σ
GAP(())(Ueea) betw)
(Efficiency)
A.13 PROOF OF PROPOSITION 5.1
a reminder the function d repre- sents the un-normalized GAP similarity function. Let the grand coalition, N, index into the spatial coordinates both the query image features x RCHW and retrieved image features y E RCHW Let the function mask(y. S) act feature map by replacing the corresponding features with background feature map a for query features and b for retrieved features. We can represent the set of players, N, set of ordered pairs of coordinates with additional information about which tensor, the query (0) or retrieved (1) features, they represent:
Let the spaces X, y and function be as in Proposition 4.1
N = ([1, x WJ x (0)) ([1, X
[1, W] x {1})
(12)
In the subsequent proof we omit these 0, tags as is clear from our notation which side, query or retrieved. the index refers to based on the index h, for the query and i, for the retrieved image. We first consider the zero background value function, v(S c N). defined by censoring the spatially varying features prior global average pooling and comparing their inner product:
v(S)=
Σ 3 ckow
HW Σ Desj
HW
hyw0
where
Zchow
(h, w) E s O.W.
Schw
and likewise, for Veiy- When S contains all i, h, this represents the similarity judgement from the GAP network architecture. We seek the Shapley- Taylor index for a pair image locations S = ((h, w), (i, J)). For notational convenience let r (v) == (C()) represent the k order interaction
23

---

Published as a conference paper at ICLR 2022
effects for the subset S and the value function
(v((v= = v
Σ
Σ 3
HW
HW
v.
v
H2W2 ΣEΣ
Tch Best
W.w'' V
v
ΣEΣ
Beet Desty'
H2W2
W. Vig'
E J Σ
H2W2 Jchh yesl
(Linearity)
b. ool v'3
- E
HHWWWoohuul BehneDees
(Dummy)
= (Uhorit)
(Renaming)
Where the renaming of the last step was because we can now consider simplified value function with just the non non-dummy players as tharis(S") == Ee Fehwweij- Where S' represents a subset of non-dummy players: N' {(h, w), (1,1)}- We can now explicitly calculate the index:
(b) = TEN'S
6s Uhoni (T)
n-
8g Uherij (0)
Σ
H2W2
FehewWeij
By following the same set of reasoning, we can introduce nonzero background values aehw and besf to yield the following:
Vi (v)
H2W2 Σ
Jehwwloij Lehwbbij achwwees + achwbeij
(13)
A. PROOF THAT SHAPLEY TAYLOR IS PROPORTIONAL TO INTEGRATED HESSIANS FOR GAP ARCHITECTURE
As in Proposition value function U2:
we consider the soft masking "multilinear extension" of second-order
12 (S) [0, 11
d(mask(r, S), mask(y.
(14)
let hws, and iý be members of the grand coalition N such that hw + ij. We begin proof with the expression for the off- off-diagonal terms of the Integrated Hessian.
T Timiig (S) S 3=0 T
aB Pv2(a
(15)
Where a
17 represents the har component of the partial derivative with respect to o:SS, not to be confused with the partial derivative of just S. Like in proof of Proposition 4.2 because function is defined on the interval [0, 1] many of the terms mentioned Janizek et al. (200 drop out and instead are captured in the Hessian of the function with repspect the soft mask. We
24

---

Published as a conference paper at ICLR 2022
expand the definition of 0y(a33)):
(a = d(mask(2,, oxBS), (y,k(y
1
Σ
achw + h: achww) Σ A,
Σ bess + a,Sis(Ucii - bess)
HaW2
From this function we can read off the appropriate term of the hessian with respect to the mask at location (h, w) and location (i,
Suz (a(35) 0T OT
Σ
Ichwyoiij - Eehwbeis achwoliij + actwbeij
H
W.. (1)
We can now pull this outside the integral to yeild:
T Thw,ig (nw,)g(v2) = Sr f aB Poz(a
OTi
3=0
= -hhness
aB
a= B=0
v (U))
Which proves that the Shapley- index and second order Aumann-Shapley values are propor- tional for the GAP architecture.
A.15 EXPLAINING DISSIMILARITY
In addition to explaining the similarity between two images, methods naturally explain image dissimilarity. In particular, regions with a negative Shapely values (Blue regions in Figure [1] contribute negatively to the similarity between the two images. These coefficients can be helpful when trying to understand why an algorithm does not group two images together.
Kernel SAM
Query
Retrieved
Figure 11: Explanation of why two images are similar (Red) and dissimilar (Blue). Blue regions highlight major differences between the images such as the dog playing the guitar, and the chain-linl fence in the retrieved image.
25

---

Published as a conference paper at ICLR 2022
A.16 ON THE "AXIOMATIC" TERMINOLOGY
The term "axiomatic" can mean different things to different readers. When this work refers to "axiomatic" methods refer methods that approximate the uniquely specified explanation val- ues dictated by the axioms of fair-credit assignment. In the first-order case, these explanations are the Shapey Values and satisfy the axioms of linearity, efficiency, dummy, and symmetry. In the higher-order case these fair credit assignments are the Shapley-Taylos Indices and satisfy analogous axioms (Sundararajan et al. 2020). We note that our methods converge the true Shapley and Shapley-Tay Taylor indices and thus the deviations that arise as part of convergence induce correspond-
ing deviations from the axioms of fair credit assignment. Nevertheless, we find that these deviations become negligible our methods converge the true Shapley and Shapley-Taylee values. This starkly contrasts the behavior of methods that do not converge to values that satisfy the axioms of fair credit assignment such as GradCAM shown in Figure g
26


Reviews:
[{"review_id": "JmsURW6_ZXh", "reviewer": "Reviewer_T6UD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "***Strengths***\n\nProviding a general framework grounded in some theory for adapting existing work to a new task ensures that their approach can likely continue to provide value over time (since as new classification explanation methods are developed they could adapt those too).  The paper is also pretty well written and easy to understand, and addresses a problem with wide applications and relatively little work, making the added discussion quite valuable on its own.  The experiments themselves do suggest their approach has merit, although lacking in several aspects in this version.\n\n***Weaknesses***\n\n1. The authors never showed their explanation method was human-interpretable or could be used in any downstream methods that leverage explanations.  This is a critical flaw in their paper that is enough to recommend rejection on its own.  The authors try to avoid this by saying people introduce biases when considering explanations so is out of scope, but I am going to flatly reject this line of reasoning.  If it is an explanation, then one factor should be human interpretability, since it is one of its primary applications.  I would be willing to accept an alternative, such as demonstrating that this kind of approach would be useful for methods that utilize explanations during training (the authors referenced a few, so I will omit citing examples here), but these experiments have yet to be conducted as well.\n\n2. Note the authors failed to discuss and cite another paper that introduced a general framework for generalizing prior work for explaining similarity models:\n\nBryan A. Plummer, Mariya I. Vasileva, Vitali Petsiuk, Kate Saenko, David Forsyth. Why do These Match? Explaining the Behavior of Image Similarity Models. ECCV, 2020.\n\nThe authors should also discuss and compare to this paper.\n\n3.  Following up on the paper in the second weakness, the authors of that paper found saliency-based methods (such as this paper) is not actually human interpretable for the image similarity setting, and could actually lead to more confusion when used in isolation.  While this could simply be due to the biases the authors argued as a reason not to do human studies, this should be confirmed as it suggests that the approach used by this paper may lead to similar results.  Some discussion by authors on this point is warranted.\n\n4. The authors seem to mostly consider the case for explaining why two images are similar, but not what causes dissimilarity.  For example, some key image region A could be neglected by image B, producing a poor similarity score.  The authors should include a discussion and experiments that handle this case.\n\n5. The authors perform experiments on two object detection benchmarks, which makes their claim of an image similarity explanation model a bit suspect.  They should also include experiments over standard deep metric learning benchmarks at the very least (e.g., Deepfashion, Stanford Online Products, CUB, etc), although I have a strong preference for medical images since this case was used repeatedly in the motivation for this paper.\n\n***Post Rebuttal***\nFor the most part I was satisfied with the rebuttal.  The approach has not been demonstrated that it is human-interpretable, meaning that one of the major applications of explainable methods are not verified.  In addition, the authors did not compare to the prior work that I suggested.  While the authors argue that their explanations are better, and I don't necessarily doubt it, but demonstrating it empirically would make a stronger paper.  I would encourage the authors to at the very least discuss and (hopefully) compare to the paper I cited as it a published paper that addresses the same topic as this paper and currently is (still) uncited.\n", "summary_of_the_paper": "This paper proposes an approach for explaining visual similarity models.  They provide a general framework that enables them to adapt existing explanation methods to the similarity learning task, and then discuss how they apply their framework to generalize multiple methods.  The authors evaluate their work on PASVAL VOC and COCO, where they use automatic metrics to argue that their approach accurately captures model performance.", "summary_of_the_review": "My initial recommendation is to reject this paper.  The authors have not demonstrated that their approach provides useful explanations either via a human evaluation or for some downstream task.  They are missing a reference to at least one work addressing the same task that has claims that are problematic for this paper, and the experiments were not conducted on datasets that were designed for the motivating applications as well, making it unclear if the approach will generalize to the target setting.  The authors need address at least the first two weaknesses before I would consider recommending acceptance, although the 5th weakness is also high on my priority list for changes.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "G-kAVINJLXi", "reviewer": "Reviewer_EVSE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work has twofold contributions, which are both theoretic and empirical. The theoretic contribution is the unification of existing algorithms using Shapley-Taylor indices. The empirical contribution is their proposed fast-kernel algorithm, which has been validated through quantitative experiments. \n\nFew concerns: \n\n1. Readability. For the theoretic part, this work is built upon Shapley value. I would recommend authors to include more introduction for Shapley value (at least more intuition), so that readers do not need to read external references. \n\n2. Please re-order table 1 that mIoU should be the primary metrics. It is because, without good mIoU, faithfulness and inefficiency is not that meaningful metrics. \n\n3. Variance for Table 1? \n\n4. Wondering do people really care about the speed of explanation? \n\n\n\n", "summary_of_the_paper": "This paper proposes a unified framework to explain the current model explaining algorithms. Under this framework, the authors discovered the current algorithms are approximating second-order Shapley-Taylor indices, where they also proposed a fast-kernel-based estimation method. Empirically, the authors benchmarked different algorithms in two large segmentation datasets. They showed the proposed algorithms achieved better faithfulness and inefficiency. \n", "summary_of_the_review": "This work has solid contributions, and the writing and experiments presentation could be improved. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6iaDRUSQjc", "reviewer": "Reviewer_erSL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ This work builds up a formal explanation framework for retrieval/metric learning, which can benefit future works in this field. It also generalizes other explanation methods, like CAM, GradCAM, VEDML (generalized as SAM in this paper). \n+ The idea of using Shapley value to explain retrieval model is very interesting.\n+ The definitions and propositions are reasonable, I did not find any errors there.\n+ The experiments provide a good comparison between all existing and generalized methods on faithfulness, quality as well as the efficiency.\n+ The writing is easy to follow and well organized. \n\nConcerns:\n- The claim of \"Axiomatic\" is very strong. Shapley value may be a fair metric to measure the contribution of each feature, but the value in this work is estimated with approximator. Is the estimated value guaranteed to be \"Axiomatic\" here?\n- There are many principles to follow for explanation, and Shapley value is not the only reasonable one. For example, perturbation [1], and Deep Taylor Decomposition principle [2]. Why is Shapley value called \"Axiomatic\" while others not? \n1. Fong, Ruth C., and Andrea Vedaldi. \"Interpretable explanations of black boxes by meaningful perturbation.\" Proceedings of the IEEE international conference on computer vision. 2017.\n2. Chefer, Hila, Shir Gur, and Lior Wolf. \"Transformer interpretability beyond attention visualization.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.\n\n- The performance is not improved. In table 1, it seems that the proposed kernel-SAM only improves efficiency over SAM, the quality and faithfulness are both on par with second-order SAM. Since the experiment is conduct with GAP architecture, the SAM is equivalent to VEDML (in related work), it this correct? If yes, then the performance is not improved over VEDML. In scenarios where efficiency is not important, we still don't know how to get a better explanation.\n- The proposed method is claimed to have advantage over other methods when the architecture is not based on GAP. But the experiment is only conducted with GAP-based architecture. Why not try other architectures where the proposed method could have better performance?\n- The explanation framework is for retrieval/metric learning/similarity models, while this paper only conducts experiments on object detection datasets (VOC, COCO). It would be more convincing if results on widely used retrieval/metric learning datasets are provided, e.g. CUB, Deepfashion.\n- The authors use Moco, a contrastive learning model for self-supervised learning. It uses augmented images as positive and all the other images as negative, which is different from normal retrieval model. The results on retrieval model may be different. Why not train with metric learning setting, i.e. using the same class as positive while other classes as negative (contrastive loss, triplet loss, proxy). \n-  Proposition 4.2 raises a limitation about GradCAM. It seems that VEDML also mentioned the limitation of GradCAM about the GAP operation. Although their definition is not as formal as this work, it somehow aligns with the observation of this work.\n", "summary_of_the_paper": "This paper proposes a explanation framework for retrieval/similarity/metric learning models. It generalizes the form of a couple of previous works, e.g. Zhou et al., 2016; Selvaraju et al., 2017; Zhu et al., 2019; Ribeiro et al., 2016. The proposed method relies on estimation of Shapley value, the authors then propose a kernel-based approximator to make it more computationally efficient. Experiments are conducted on PascalVOC and MSCoCo dataset to show the faithfulness and quality of explanations.", "summary_of_the_review": "Overall, I think the idea is very interesting and the proposed explanation method is good contribution. But the experiment is not strong due to the concerns, and the evaluation could be improved in the future. My rating is borderline leaning to accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The initial reviews for this paper were 6,6,6, the authors have provided a rebuttal and after the rebuttal the recommendation stayed the same. The reviewers have reached the consensus that the paper is borderline but they have all recommended keeping it above the acceptance threshold. Following the recommendation of the reviewers, the meta reviewer recommends acceptance.
Decision: Accept (Poster)