Information Maximization Perspective of Orthogonal Matching Pursuit with Applications to Explainable AI
Authors: Aditya Chattopadhyay
Ryan Pilgrim
Rene Vidal
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Information Maximization
Sparse Coding
Orthogonal Matching Pursuit
Explainable AI
Information Pursuit
TL;DR: We show that the popular OMP algorithm can be derived from information-theoretic principles modulo a normalization factor. We then use this insight to design a computationally simple sparse-coding based explainable AI algorithm.

Abstract: Information Pursuit (IP) is a classical active testing algorithm for predicting an output by sequentially and greedily querying the input in order of information gain. However, IP is computationally intensive since it involves estimating mutual information in high-dimensional spaces. This paper explores Orthogonal Matching Pursuit (OMP) as an alternative to IP for greedily selecting the queries. OMP is a classical signal processing algorithm for sequentially encoding a signal in terms of dictionary atoms chosen in order of correlation gain. In each iteration, OMP selects the atom that is most correlated with the signal residual (the signal minus its reconstruction thus far). Our first contribution is to establish a fundamental connection between IP and OMP, where we prove that IP with random projections of dictionary atoms as queries ``almost'' reduces to OMP, with the difference being that IP selects atoms in order of normalized correlation gain. We call this version IP-OMP and present simulations indicating that this difference does not have any appreciable effect on the sparse code recovery rate of IP-OMP compared to that of OMP for random Gaussian dictionaries. Inspired by this connection, our second contribution is to explore the utility of IP-OMP for generating explainable predictions, an area in which IP has recently gained traction. More specifically, we propose a simple explainable AI algorithm which encodes an image as a sparse combination of semantically meaningful dictionary atoms that are defined as text embeddings of interpretable concepts. The final prediction is made using the weights of this sparse combination, which serve as an explanation. Empirically, our proposed algorithm is not only competitive with existing explainability methods but also computationally less expensive.

Information Maximization Perspective of Orthogonal Matching Pursuit with Applications to Explainable AI
Aditya Chattopadhyay" Ryan Pilgrim"* René Vidal
Johns Hopkins University, USA, {achattol, rpilgri1 edu i University of Pennsylvania, USA, vidalr@upenn. edu
Abstract
Information Pursuit (IP) is a classical active testing algorithm for predicting an output by sequentially and greedily querying the input in order of information gain. However, IP is computationally intensive since it involves estimating mutual information in nigh-dimensional spaces. This paper explores Orthogonal Matching Pursuit (OMP) as an alternative to IP for greedily selecting the queries. OMP a classical signal processing algorithm for sequentially encoding a signal in terms of dictionary atoms chosen in order of correlation gain. In each iteration, OMP selects the atom that is most correlated with the signal residual (the signal minus its reconstruction thus far). Our first contribution is to establish a fundamental connection between IP and OMP, where we prove that IP with random projections of dictionary atoms as queries "almost" reduces to OMP, with the difference being that IP selects atoms in order of normalized correlation gain. We call this version IP-OMP and present simulations indicating that this difference does not have any appreciable effect the sparse code recovery rate of IP-OMP compared that of OMP for random Gaussian dictionaries. Inspired by this connection, our second contribution is explore the utility of IP-OMP for generating explainable predictions, an area in which IP has recently gained traction. More specifically, we propose a simple explainable Al algorithm which encodes an image as a sparse combination of semantically meaningful dictionary atoms that are defined as text embeddings of interpretable concepts. The final prediction is made using the weights of this sparse combination, which serve as an explanation. Empirically, our proposed algorithm not only competitive with existing explainability methods but also computationally less expensive.
Introduction
Information Pursuit (IP), first proposed by Geman and Jedynak (, a classical algorithm for active testing: Given a set of queries whose answers are informative about some target variable, IP proceeds by adaptively selecting queries order of information gain. Specifically, each iteration, IP selects the query whose answer has maximum mutual information about the target variable given the history of query-answers observed so far. IP has found numerous applications machine learning such as tracking roads in satellite images M face detection & localization [2], detecting & tracking surgical instruments
B and scene interpretation [4]. More recently. IP has been touted as a framework for explainable AI [3). Despite its utility, a major limitation for IP is its reliance mutual information, which is challenging to compute in high dimensions 6 In light of this, we ask the question, are there alternative sequential algorithms that could replace IP by employing simpler objective in their selection step? One such algorithm is Orthogonal Matching Pursuit (OMP), which we describe next.
'Equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

OMP 7 is classical algorithm for sparse coding: given a dictionary of atoms and an observed signal, OMP proceeds by adaptively selecting atoms in order of correlation gain. Specifically, in each iteration, OMP selects the atom that has maximum correlation with the current residual (the unexplained part of the observed signal given the previously selected atoms). OMP has been successfully applied to many signal processing applications such as image denoising using over- complete dictionaries [9, image super-resolttion [10, [ and matrix completion [[2].
Similarities between IP and OMP. Although the two algorithms were discovered inddpen- dently in two different communities, IP in the active testing and OMP in the signal process- ing community, they share many similarities. Both algorithms are illustrated in Figure [
Observation
Query and distribution Mor
Qu+1
arg ((Q, Y Mua(s)) QUU
Conditoning
Signal x
Dictonary 0 [dt.eff.....))
OMP
dess argmax alep
[( (p,
105, M1
Both seek parsimonious representation. IP tries to make a prediction by selecting the minumum number of queries on average, OMP tries to represent the observed signal by selecting the minimum number of atoms,
Protection
Figure I: IP and OMP. Both are greedy sequential al- gorithms. IP selects the next query using conditional
mutual information I(-:-) while OMP selects the next dictionary atom based on dot products (.--). Pre- vious choices are incorporated via the history H1: (x) of previous query answers in IP, and the projection matrix D. which we define in $ in OMP.
Both are greedy algorithms used as effi- cient approximations to the true optimal solution In each iteration, IP uses con- ditional mutual information to decide the next most informative query about the tar- get variable Y. Similarly, in each iteration, OMP uses the dot product between a dictionary atom and the residual (the observed signal's 's projection onto the orthogonal complement of the span of all the atoms selected so far) to select the next most representative atom to reconstruct the observed signal. The conditioning (in IP) and residual (in OMP) are mechanisms account for previous decisions made by each algorithm.
IP terminates when the posterior P(Y | History) is sufficiently peaked, indicating Y can be predicted with low error. Similarly, OMP terminates once the mean squared error between the observed signal and its reconstruction is sufficiently low, indicating that the observed signal can be reconstructed from the selected atoms with high fidelity.
Differences between IP and OMP. Given these similarities, one may be tempted to conjecture that one of the algorithms is a particular case of the other. However, establishing such a connection not trivial at all. The reason is that there are fundamental differences the manner in which these two algorithms operate, despite their apparent similarities. In IP, the target variable and query answers are all random variables. An illustrative example of this is given by the popular parlor game "twenty questions", where a player asks queries about attributes of some entity Y (that another player has thought of) and would like to identify Y by asking the minimum number of questions. In this example, Y is random variable, and Y is also a random variable. In OMP, on the other hand, one typically observes some fixed signal and then proceeds to encode it using the dictionary atoms. Consequently, IP's objective to select the next query requires estimating mutual information, which, as already stated, is difficult in high dimensions. OMP, on the other hand, only relies on dot products and least-squares involving the fixed signal and small numbers of dictionary atoms, which is computationally a far more tractable objective. Therefore, is indeed surprising that one can derive a connection between the two algorithms.
result, the corresponding query answer which depends on
Is OMP a particular case of IP? Formally establishing a connection between IP and OMP requires answering two key questions: (i) "what would the queries and their corresponding answers be?" and (ii) "what would the target variable be?" As IP operates on random variables and OMP on fixed observed signals, we need to inject the observed signal into the definition of the queries and/or target variable. We achieve this by taking queries as dot products of the dictionary atoms with a standard normal variable Z, and the target variable as the dot product between between the observed signal x and Z. The intuition is that since Z has a radially symmetric distribution, in order to accurately
In the case of IP, this is the solution that needs the minimal number of queries on average to predict the target variable with a desired level of confidence; in the case of OMP, this is the sparsest code that reconstructs the observed signal up desired level of accuracy.
2

---

reconstruct the target dot product, IP would need to encode the observed signal into the selected queries (scalar projections of the dictionary atoms). We formally show this in $ In particular, we show that IP selects the atom in each iteration whose projection (onto the orthogonal complement of the span of the atoms selected so far) has the maximum normalized dot product with the residual. This contrasts with OMP which uses the unnormalized dot product as its selection criterion. We call this IP version of sparse coding IP-OMP. We then show via simulations over random Gaussian dictionaries and different sparsity levels that despite this algorithmic difference, IP-OMP and OMP have almost identical sparse recovery success rates. This empirical observation is further complemented by theoretical work by Soussen et al. [13] who prove that if for a given dictionary, exact recovery for all s-sparse signals is possible after s iterations of OMP, then the set of atoms selected after termination (s iterations) would be the same for both IP-OMI and OMP
Implications of this connection. As alluded to before, computing mutual information often intractable in high dimensions. Previous approaches tackle this issue by either explicitly learning a generative model for data (5 14 or by learning the most informative next query from data using deep networks and stochastic objectives [15 [6]. However, IP-OMP presents a much simpler alternative which does not involve training any deep networks or learning data distributions using generative models. This begs the question of whether IP-OMP can be used as a cheap surrogate to IP in certain applications. In this paper, we show one such application to explainable AI, where IP has been recently proposed
method for making explainable predictions by design [15]. More specifically, [3] proposes a framework called Variational Information Pursuit (V-IP) where the query set Q consists of interpretable queries about the data. Using Q, V-IP explains its prediction in terms of the selected interpretable queries. Similarly, we construct a dictionary comprised of interpretable atoms from text embeddings. We then propose use IP-OMP to represent the image in terms of a sparse combination of dictionary atoms (the sparse code). The final prediction is made by training a linear classifier on top of the sparse code. In this way, we can make predictions explainable-in the sense that humans can understand predictions in terms of the sparse interpretable inputs to the classifier and their corresponding weights- computing mutual information. This, however, presents challenge: images will typically not be represented well as linear combination of text embeddings since they are very different modalities. To remedy this, we propose to use CLIP [17], recently introduced large Vision- Language Model. to encode both images and text into a shared latent space.
Paper contributions. To summarize, our main contributions are:
We formally establish a connection between IP and OMP. By choosing the parameters of IP appropriately, we obtain an algorithm, IP-OMP, which is equivalent to OMP up to normalization in the objective.
Inspired by this connection, we propose a simple algorithm using IP-OMP and CLIP for making explainable predictions in visual classification tasks. We show empirically on multiple image classification datasets that the performance of our algorithm is competitive with, if not better than, state-of-the-art methods for explainable Al.
2 Preliminaries
2.1 Information Pursuit
In this paper, random variables are defined over common sample space Ω and are denoted by capital letters. Their realizations are denoted by the corresponding lowercase letter. Let Y be a target variable of interest. Let Q be a set of queries, where every query Q Q is random variable. We call the realization of Q, written its answer. Given Q, one is often interested in predicting Y by sequentially asking queries from Q such that the average number of queries needed is minimized [18 19 20 14 5 [6). Information pursuit (IP) [1] greedily approximates the solution to this problem. In particular, single IP run proceeds as follows,
Q arg max T(Q:Y); Qk+1 arg max T(Q:Y (Hia), QEo
QEO
where QK-1 is the query selected in iteration k + 1, I(::-) denotes mutual information and Hish is the history of query-answer pairs observed after the first le iterations. More precisely. Hi:k is defined
'The authors of [3] refer to IP-OMP as the Orthogonal Least Squares algorithm since it can also be derived from least squares optimization perspective. We expand upon this point in
3

---

as the event {w E Ω (1(w)===0))))))))))))))))))))Q .1..... Qx(w) = ) The algorithm terminates after T iterations if the entropy (or differential entropy if is a continuous random variable) of the posterior P(Y (Hir))
is below a user-defined threshold []] Altrnatively, one could employ a fixed budget of iterations
and terminate 21 After termination, IP's prediction for Y is given by arg maxy P(Y (1:r) [
2.2 Orthogonal Matching Pursuit
Given a matrix De E R with m < n and an observed signal æ E R",, the goal of sparse coding is to find sparse vector R" that reconstructs the signal z. More precisely, the goal is to solve s.t. DB,
min BER
11
where |1-llo refers to the to pseudo-norm. Equation 2 has been of significant interest over the past few decades due its applications to compressed sensing [22] Chapter 1] and sparse representation theory (23 We will call D the dictionary, x: the observed signal and |3 the sparse code. We will refer to the columns of D atoms, where d² refers to the j"h atom.
Since the problem in equation 2 is NP-Hard [22] $2.3]. approximations are employed. Orthogonal Matching Pursuit (OMP) 7 is popular greedy algorithm known for its computational efficiency
24 compared to alternatives like Basis Pursuit (25] Given x and D, the OMP algorithm first
fz-normalizes all the atoms in D. Subsequently, it initializes its estimate of the sparse code as Bg = 0 and its estimate of the support of 3 (set of non-zero indices in (3 the empty set So 0. OMP then proceeds iteratively. Its (k + 1)th iteration (k 2 0) is defined as,
jk+1 arg max KdP, , DB&)): Sk+1 Sk U (ix+1);
je(1....m.
Bx41= arg min Dull2 support(u) S Sk+13.
"ER"
where x DD, is called the residual at iteration A 22 $3.2]. There are multiple choices for the termination criteria, including (i) to run some fixed number of iterations or (ii) to terminate once
the norm of the residual is below some user-defined threshold 2 0, that is, | D3r ll2 < (26).
We now rewrite the atom selection step in equation B into form that is more amenable to comparison with the IP version of OMP called IP-OMP that we will derive next. For a particular run of the OMP algorithm, let D3 be sub-matrix of D composed of the first & atoms selected by the OMP algorithm and let D. be the projection the range of Dj- From the update of ßg. it is clear that D,3g is projection onto the range of Dr. Similarly, the residual x D33 the projection of x onto the orthogonal complement (27]. Using this observation, we rephrase the atom selection in equation 3 as
JN+1 arg max (dd II x²)| arg max KI1, d IIb, x)
jE(L....n)
sE(I.....)
3 IP-OMP: Information Pursuit for Sparse Coding
Recall from - that to establish a connection between IP and OMP, we need to specify a set of queries and a target variable. all of which are random variables. Moreover, since OMP operates deterministic inputs (the observed signal), we have to inject the observed signal into the definition of the queries and/or the target variable. Inspired from the Bayesian perspective of compressed prior over the sparse code, like the Laplace distribution (30). This induces a distribution over the observed signal X D3 + measurement noise (capitalized to emphasize that X is now a random variable). Since the goal is sparse-code the signal, natural choice for the target variable could be X itself. Finally, since we want to recover the atom selection step in OMP (equation 4) using IP, which is obtained by maximizing the absolute dot product between the atom and the residual, reasonable choice for the query set Q could be atoms of the dictionary where the answer to a query is the corresponding atom's 's dot product with X. Given this setup, the first query selected by IP i
sensing 28 29 one natural attempt could be to consider
arg max (Q';; x) arg max [((d) X):
(5)
EEQ
deD
'Note that we use subscript Q, to denote the query selected by IP at iteration i, and superscript Q' to denote the query that corresponds to the 1 atom, d', of D.

---

It is immediately clear from equation 5 that the first query would be independent of the observed signal X = z. This is because IP decides what is the most informative query solely based on mutual information, which is property of the distribution, and does not involve observing the realization This is in sharp contrast to OMP, where the selection of the first atom driven by the observed signal (see equation 3). Thus, assuming a generative model for the signal X would not result in the OMP algorithm and calls for a more "non-standard" way of defining the queries and/or the target variable.
What is the right query set and target variable? How can we make the queries and/or the target variable depend on realization of X = x? Inspired by measure called sliced mutual information, which defines the dependence between two random variables as the average mutual information between their mee-imenniooal projections onto random directions [31]. we propose the following query set and target variable.
Define Z to be a standard normal variable in RT. Let =0 be a sample from Pz = (N(
Take Q contain all the atoms in D as queries, such that query Q' Q corresponds to the random projection (d', Z) of atom d' E D, and the corresponding answer is q² == (d'
Take the target random variable of interest as (1,, Z). Thus, given z", the value of the target variable that needs to be predicted is (zz, Z) = (zc, 2
The rationale behind these choices is as follows. Since is a random vector with a radially symmetric density, to accurately predict the target variable (I. Z) for all realizations of Z. IP needs to query atoms that would in a way code for x itself. This intuition is formalized by the following lemma.
Lemma 1. Let 2 be a realization of Z. Civen a subset of queries from Q (or equivalently, atoms selected from D), the conditional entropy of the larget (xr, 2) given the query answers observed is
1 ((x,, Z) (Q = (do, ( = In =1)))
where h is the conditional differential entropy, dq denotes the atom used to construct the random variable Q, De is the sub-matrix of D consisting of atoms corresponding to queries in L and DI is the projection matrix onto the orthogonal complement of the range of D
The proof of this lemma relies on the joint Gaussianity of all the query answers and the target variable since they are all dot products with the same normal vector Z. Proof in Appendix $
Notice that the history of query answers observed, after finite number of iterations of IP, is just some subset of queries selected from Q along with their corresponding answers. Since IP greedily selects queries until the conditional entropy of the target (given history) minimized ($2.1) Lemmal) [
indicates that IP would terminate when |||1, D2 x 2 + 0, that is, when æ can be "almost exactly
reconstructed from the atoms selected by IP.
The IP-OMP algorithm. Given this choice of query set and target variable, we now state our main result (Theorem I) proving that IP not only chooses atoms that code for x, but also uses exactly the same query selection strategy as the atom selection strategy of OMP up to a normalization factor.
Theorem 1. Given an observed signal x, a realization 2d of Z, and the choice of Q and the target variable as described in this section, IP proceeds as follows for k 2 1,
k x)
Q arg max I(Q"; (z. Z)) = arg max QIE
d (d'laa/ee ||
dED
(IP-OMP)
KLL, di _1,,1,1,,011,, x>
Q Qk+1 arg max I(') (z. Z) H1.x) QEO
arg max di DEDII d0 |1 di 1|2 | x/12
(dz, 2)) d, is the atom (query) selected by IP in the th iteration, D is the sub- sub-matrix of D consisting of atoms corresponding to queries se- lected by IP in the first l iterations and I1,, is the projection matrix onto the orthogonal complement of the range of Dr-
where Hi-k == (Q = (d1, 2, (dz, 20.,,,,,... Qx
The above result uses the joint Gaussianity of all the query answers and the target variable. A full derivation can be found in Appendix $A.2 Comparing equation g and [P-OMP] it is clear that the two algorithms differ by normalization. To distinguish from the OMP algorithm, we call the
5

---

Figure 2: Performance of OMP (solid curves) and IP-OMP (overlaid circles) in the noiseless case function of the num- ber of measurements m for a fixed sparsity level & and number of dictionary atoms n. "Probability of exact recovery" reports the fraction of times (over 1000 simulations) the algorithm exactly recovered the sparse code for particular setting of (m, n, s).
Number dictonary m2266
Number dictonnry stome 1=10
0.8
0.8
5110
Probabiii
0.4
100
150
230
100
120
Number of mosssremonnsss m
Number of misosremmnnt. m
iterative algorithm described above as the IP-OMP algorittm If one uses the entropy of the posterior P((x, Z) H1:-)) criterion for termination after T iterations, then according to Lemma the algorithm would terminate once |[T,, 2112 S e. This is reminiscent of the norm of the residual termination criterion commonly employed by OMP.
Sparse coding using the IP-OMP algorithm. In the discussion so far between the equivalence of OMP and IP-OMP, we swept the issue of recovering the sparse code under the rug. To remind the reader, the goal of sparse coding is to find code fMP- such that z DiIP-OMP. However, the IP-OMP updates do not explicitly provide a way of doing so. However, by analyzing IP-OMP's prediction of the target (z, 2) we can derive -IP-OMP.
Recall from 2..1 that after termination, IP's prediction is the mode of the posterior distribution. Thus after termination IP-OMP's prediction would be given by
max P(xx, Z) H1.)) = (D.D).,20)
2
where is the number of iterations before IP-OMP terminated, D, is the sub-matrix of D consisting
of the atoms selected in the first 7 iterations, f represents the pseudo-inverse, and 20 is the realization of Z that determines the outcomes of all the query answers and the target (which is (1r, Z) (Ix 2²))
Refer to Appendix {A.3 for a proof of equation 7 Next, notice that the query selection in [P-OMP is independent of the realization of Z, which implies that the sequence of queries selected in the first iterations would depend solely on æ. This implies the following lemma,
Lemma 2. For all E Rmm, IP-OMP's prediction of the target is given by (D, 2).
Refer to Appendix A.4 for a proof. Taking = = cs, the 7th canonical basis vector in R.",, we observe that IP-OMP's prediction of the 1th component of xr, denoted as Fs, is (D, Hence, we conclude
(DOr) D!rr)
D,D. DD. D_r
âIP-OMP-
(8)
where D_, is the matrix comprised of atoms of D not selected by IP-OMP in the first t iterations. Comparing with equation 3 we see that this is analogous to the sparse code estimate OMP obtains after T iterations, with the D, matrix now replaced with the atoms selected by OMP.
IP-OMP OMP. Recall the only difference between IP-OMP and OMP is the normalization step after the dot product. We carry out synthetic experiments to investigate the effect of this normalization factor on the practical performance of IP-OMP vs. OMP in sparse code recovery. We first consider the noiseless case (equation 2) and later investigate the scenario where signals are corrupted by noise.
For the noiseless case, we conduct the following experiment. Fix the dimension of the sparse code, m the dimension of the observed signal, and the sparsity level. Generate a large number of random dictionaries, where each atom (column) is sampled from the uniform distribution on the unit sphere in Rm For every dictionary. pick a subset of s (out of n) atoms uniformly at random and simulate the coefficients for each of the selected atoms from the standard normal distribution. Set all the remaining coefficients O. These coefficients constitute the sampled sparse code. For each simulation, construct the observed signal H. = D.l... where D,, is the sampled random dictionary and f, is the sampled sparse code. For every J. we carry out both OMP and IP-OMP and measure their performance in terms of the fraction of simulations in which the algorithm exactly recovered the sparse code Bz- We define exact recovery when the normalized mean-squares error (NMSE)
NMSE(3Ale. 8a) = 11.3 1 /1.

---

Figure 3: Performance of OMP (solid curves) and IP-OMP (overlaid circles) in the case where signals are cor- rupted by noise. On the y-axis we report the mean NMSE, defined in equation 9 averaged over 1000 trials. On the æ-axis, we report the number of measurements (signal dimension) m. Each sub-figure corresponds to a fixed number of dictionary atoms n and a fixed expected signal-to-nowe -oiise ratio E[SNR]. The top row shows re- sults for small n (256), while the bot- tom shows results for large (1024).
n525 E[SNR] 5 dB
256 E[SNR]-20 dB
10
Sm4
Mean NMSE
5-10
10"
22
10
10
100
200
0
100
200
n=1024, E[SNR]=5 dB
n= 1=1024, E[SNR]=20 dB
10
Mean NMSE
10"0
10"
10"
50
100
50 100
#Measurements
#Meeasurements
approximately zero (< 10-14), where the subscript Ale. indicates the algorithm (OMP or IP-OMP). This experimental setup was inspired by (24]. Further details of the experiment can be found in these results which indicate that OMP and IP-OMP achieve almost the same exact recovery rate over variety of different values of (m, n, s). In particular, both IP-OMP and OMP degrade similarly when the sparsity rate A + 1 or the measurement rate + 0.
Appendix B Figure
For the noisy case, we extend equation 2 with additive Gaussian noise. Specifically, we consider the measurement model ã D.,. + e, where D. and 3, are sampled as described in the previous paragraph, 5 is the noisy observed signal and ~ N'0,, I²1). The noise variance o² was set to achieve particular values the expected signal-to-noise ratio (SNR)
1.,.0112
[[[NR] = E.......
(10)
We measure the quality of the estimates produced by OMP and IP-OMP by reporting the mean NMSE of their estimates, BaIg. (taken over all the trials). Further details can be found in Appendix $B Figure shows that the the empirical equivalence between OMP and IP-OMP is maintained over different values of (m, n, s, E[[RR)).
Details on this calculation are provided in Appendix $B.3
More results can be found in Appendix SB Figure 2 and Figure B show that despite the extra normalization, IP-OMP and OMP have practically the same sparse code recovery rates for random Gaussian dictionaries, which are commonly studied in compressed sensing (see, e.g., [22 Ch. 9)).
Connection to Orthogonal Least Squares (OLS). Interestingly, the IP-OMP selection criterion (equation IPM) results in greedily selecting the atom that maximally reduces the residual error [32 Specifically, let D& indicate the set of atoms from D obtained after k iterations of IP-OMP. Then, the atom d² solving the following optimization problem
(d" (,8
arg min || [Dx d
(11)
de dED,BER
is equal to the arg max of the IP-OMP objective at iteration & ++1 1. Using this insight, multiple authors have proposed to modify OMP by replacing its atom selection criterion with equation [T and have re-discovered this algorithm under different names 33 with OLS being one of them. In this paper, we coin the name IP-OMP to emphasize its derivation from foormationntheorette principles.
Our results on the empirical equivalence between IP-OMP and OMP are complemented by prior investigations into the OLS algorithm which report similar conclusions using random Gaussian dictionaries (4 35). Theoretically, Soussen et al. [3] showed that both the algorithms share the same exact recovery conditions. This is made precise in Theorem 2 restatement of results in [I3). Theorem 2. Given a dictionary D and support S, define B = {3 E TR supp(.3) C S}. Then IP- OMP recovers all 3 E B in at most [8] iterations if and only if the same holds for OMP.
These results further strengthen our claim that for practical scenarios, the normalization factor in IP-OMP does not have significant impact. We note in passing that, for certain "special" dictionaries in which the dictionary atoms are strongly correlated with each other, IP-OMP has been reported to outperform OMP in its ability to recover the sparse code [13 34).
7

---

4 IP-OMP for Explainable Predictions for Visual Classification Tasks
Inspired by the recent application of IP [ and its variant V-IP [5] to explainable AI, here we propose simple explainable Al algorithm for visual classification tasks which uses IP-OMP to ask queries about the image. In $4.T we briefly describe the V-IP framework, propose our CIJP-IP-OMP algorithm, and discuss the differences with V-IP. Then, in $4.2 we present experiments showing that CLIP-IP-OMP computationally much cheaper than V-IP, while achieving a similar classification accuracy. Refer to Appendix @Cfor a review of prior work explainable AI.
4.1 The CLIP-IP-OMP Algorithm
The V-IP algorithm. In V-IP, a user first specifies query set, which is comprised of interpretable functions of the imput. For example, the task is animal classification, the questions could be about various animal attributes. V-IP then adaptively generates short query-answer chains that are sufficient for prediction. This done by learning a querier and a classifier network simultaneously from data. The querier learns to select the most informative query given the history of query- pairs obtained so far, while the classifier learns to make predictions based on the same history. However, the number of possible histories (subsets of query-answer pairs) the querier and classifier have to learn is exponential in the size the query set, making the training process very slow. In this paper, we propose alternative algorithm which is computationally much cheaper.
The CLIP-IP-OMP algorithm. Analogously to V-IP's interpretable query sets, we propose to use dictionaries of interpretable atoms. For example, every atom of the dictionary could correspond to text embedding [36] of a semantic concept relevant for the classification task. This poses challenge, since images and text embeddings live in very different spaces (pixel space vs. the latent space of some deep network). To address this mismatch, we leverage CLIP [17], which learns to encode images and text into a shared latent space such that the dot products of their respective embeddings are reflective of how well the text describes the image contents. We propose the following algorithm for making explainable predictions for visual classification tasks:
1. Given a set of semantic concepts relevant to the classification task, define each atom of the dictionary D as the CLIP embedding of one of the concepts obtained using CLIP's text encoder.
2. For given input image, define the observed signal x as the CLIP embedding of the image.
3. Using IP-OMP as the querier, encode the image's CLIP embedding as a sparse combination of dictionary atoms with weights -IP-OMP. While both OMP and IP- OPP recover the sparse code similarly well, we choose to use IP-OMP in our experiments due to its nice coammation-thhorede interpretation ($3).
4. Train a linear classifier to predict the class label from the sparse codes 8IP- This choice is made to enhance interpretability. By inspecting the weights of the linear layer, one can identify which concepts (atoms) are most important for the prediction.
For a given image, the linear network predicts the class label based on the sparse code. The explanation the prediction, then, is given terms of the non-zero coefficients of fIP and their corresponding atoms. Because these atoms are text embeddings for concepts, they are semantically meaningful. This is in stark contrast to predictions made by deep networks trained on raw pixel data, where the reasoning behind network predictions is opaque.
Differences between CLIP-IP-OMP and V-IP. A significant difference between CLIP-IP-OMP and V-IP is the target variable in question. In V-IP, this is the class label Y, whereas in IP-OMP this is a projection of x (the observed image's s CLIP embedding) onto random direction Z. Moreover, the query answers in both algorithms are different. In V-IP, the image is considered a random variable and answers are functions of the image. IP-OMP, the answers are simply dot products between a query (dictionary atom) and the random direction Z. Despite these differences, the label prediction in both V-IP and CLIP-IP-OMP is explained using a small set of concepts selected before termination. In V-IP, this is the set of query-answer pairs selected. In CLIP-IP-OMP this is the sparse code ÍIP-OMP. which encodes the set of selected concepts and their weights.
8

---

Input image.
Sparse code 6IP-OMP after iterations
Weights of linear classifier
(a)
black-a andk-and--witte str striped fur Savannhh salty loyal, protective nature
breast
baby binds
prey animal
a strup on the side
Value confiicient
Prediction: Tiger
stemn frear dack
wetiondh
paractute deployment gyztem colored flag on the side
hightspeed inamme
2 pkkups
or ginated Sussos, Ergland
2.2 Vakue of attimis confficiett
0.0
Signad magniude the waight
Prediction: Aircraft Carrier
Figure 4: Explainable predictions using CLIP-IP-OMP. Two example runs of algorithm two images from the ImageNet test set, with number of iterations т = 9. For both images, our model predicted the correct class with 68. 73% & 72.21% confidence resp. The weights of the linear classifier correspond to the weights for the predicted class. More examples in Appendix $E.6
4.2 Experiments
Having described our algorithm, we now show its efficacy at generating explainable predictions on different vision datasets: ImageNet [77, Places365 (8), CIFAR- 1 100) (39), and CUB-200 [40]
Specific details about architecture and training protocols used can be found in Appendix $D.2 Our
code is available at httttt:://giiiiei http://ttttu..oomrrreee wwt.cooommiiiiei wttp://////////i/oooo/o
Semantic dictionaries. To get set of semantically relevant concepts, we follow prior work 41). which uses GPT-3 42] to extract relevant concepts for every class in the dataset by asking prompts like "List the most important features for recognizing something as class". For more details, we direct the reader to 41 In this work, we directly use their extracted concepts 43 For each concept, we obtain their corresponding CLIP embedding by directly using the concept name as input the text encoder. Some example concepts for Imagenet are shown in col. 2 of Figures 4a and 4p (y-axis).
Explainable predictions using CLIP-IP-OMP. We show example runs of the CLIP-IP-OMP algorithm on two images taken from the ImageNet dataset in Figure In particular, given an image, run [P-OMP its CLIP embedding for fixed number of iterations т, which is the desired explanation length. Then, we make a prediction using the linear classifier, which was trained to learn the mapping between sparse codes of sparsity level (number of non-zero elements) and the class label. All of the CLIP embeddings (text and image) are fy-normalized. The signed magnitude of the coefficient in the sparse code indicates how relevant the corresponding atom (text concept) is for the contents of the image. This claim is motivated by CLIP's training loss which incentivizes aligned image-text embedding pairs (that is, the text describes the image contents) to have high dot product (closer to +I) and unaligned image-text text embedding pairs (that is, the text does not correspond to the image contents) to have small dot product (closer to -1). We also visualize the weights of the trained linear classifier for the predicted class. In Figure 4p. we see that the selected atoms with positive coefficients in the sparse code correspond to characteristics of a tiger like "black and white striped fur" and "prey animal". Similarly, atoms with negative coefficients correspond to concepts not found in a tiger like "salty flavor" and "witch". Although the image is not of a Savannah habitat, suspect CLIP assigns positive association between the text embedding for "a Savannah" and the image, since tigers are found savannah habitats. Interestingly, the sign of the weights the linear classifier assigns each of the concepts seems be positively correlated with their sign in the sparse code. Similar observations are made for Figure 4p. Although the concept of "originated in Sussex, England" has large coefficient in the sparse code, the linear classifier assigns very low weight to it, indicating a diminished effect of that concept on the prediction "Aircraft Carrier".
Baseline comparisons. We compare our method with V-IP and Label-free Concept Bottleneck Models (Lff-CBM) [1], a recently proposed explainable Al algorithm which similar in spirit to ours. Lf-CBM represents given image in terms of concept vector where every dimension

---

corresponds to a semantic concept and the corresponding feature is the dot product between CLIP's embedding of the image and the text concept. The final prediction is then made by training a sparse linear layer (using elastic net regularization) to map from concept features to labels. Note that their model is sparse in the network weights, whereas ours is sparse in the input features.
For fair comparison, we use the same set of concepts for all methods. For V-IP, the query is CLIP's 's text embedding and
char30
cfar100
CUD
tust acuuccy
8
40
the answer is its corresponding dot prod-
uct with the CLIP embedding (since the
20
20 Explanation Length Imagener
10
Explenation Length places365
10
23
30
Explanation Longth
30
20
30
40
dot product indicates whether the concept is present in the image). We compare all
tast aoctaac
C.P-PP.0
methods by examining the tradeoff be- tween explanation length and classifica- tion accuracy. For V-IP, CLIP-IP-OMP, and Lf-CBM respectively, the explana- tion lengths are the number of queries selected, the number of dictionary atoms selected, and the number of non-zero weights in the linear classifier for the predicted class. For prediction accuracy, use V-IP's s learned classifier, whereas for our method, we train a separate linear classifier for every sparsity level (the number of iterations of IP-OMP before termination). Unlike CLIP-IP-OME and V-IP, Lf-CBM does not have any sequential selection strategy. Hence, to compare, we report the average number of non-zero weights per class in the concepts-to-lale Figure [ On most datasets, CLIP-IP-OMP has a better trade-off (greater grea-under-the-curyee than V-IP, except CIFAR-100 (where they are competitive) and CUB-200. Notice that for all datasets, in the initial iterations, atoms selected by CLIP-IP-OMP are more predictive for the class (higher test accuracy) than V-IP. This is because the atom selection in TP-OMP explicitly depends on the image content, whereas, the query selection in V-IP (equation I solely depends on the answers to the previous queries and the data distribution. On all datasets except CUB and ImageNet (where it is competitive), our method achieves similar accuracy to Lf-CBM, but with a much smaller explanation length (Lf-CBM's explanation length (accuracy) is indicated by the red star (red dashed line)).
label free CBM acc.
Wioe free CBR aug sparsity
20 Explenation Length
Explanation Length
Figure 5: Trade-off between accuracy and explanation length for different methods (best viewed in colour).
linear mapping. The results shown in
Computational efficiency. Complementary to being performant at explaining prediction, we would like to stress the simplicity of our method compared to V-IP and Lf-CBM, two contemporary explainable Al methods. Both V-IP and Lf-CBM require costly optimization routines. In V-IP, this is training a querier network to learn what to ask next from data. In Lf-CBM, this is optimizing the sparse linear classifier using the elastic-net regularizer. Finding the right sparsity level (number of non-zero weights in the classifier) in Lf-CBM requires hyperparameter tuning by training multiple models. In comparison, our method uses IP-OMP, which requires no training, to select dictionary atoms. Moreover, the number of iterations of the algorithm controls the explanation lengths.
The main bottleneck of IP-OMP is in extracting the sparse codes since this involves computing projection matrices. For example, our implementation, based Cholesky decomposition 44] takes & 40 hours to extract sparse codes of support size 50 (the highest considered in our experiments) for all the 1.28 million images in the ImageNet training set on an NVIDIA RTX A5000 GPU. This will be much faster for smaller support sizes, for example at level 10, it takes R hours. For comparison, training Lf-CBM 43] on ImageNet for one set of hyperparameterss takes about 50 hours on the same GPU. Similarly, training the V-IP framework 45 on ImageNet takes about 4 days!
5 Conclusions and Limitations
In this work, we show that Orthogonal Matching Pursuit (OMP) a particular case of Information Pursuit (IP) (modulo normalization factor) with a suitably chosen set of queries and target variable. We call this Ie-derived algorithm for sparse coding OPP. We then present a simple algorithm. called CLIP-IP- OMP, which uses CLIP and IP-OMP to make explainable predictions for visual classification tasks. CLIP-IP-OME has two limitations. First, its application is restricted to image datasets since it relies on CLIP to encode images and text concepts into a shared space. Second, the atom selection procedure using IP-OMP is independent of the class label; as a result an auxiliary classifier needs to be trained. Future work would aim to address these limitations.
10

---

Acknowledgments and Disclosure of Funding
This research was supported by the Army Research Office under the Multidiseiplinary University Research Initiative contract N911NFF17-1-0300 and the NSF-Simons Research Collaboration on the Mathematical and Scientific Foundations of Deep Learning (NSF grant 203 2031985, Simons grant 8 142201). Moreover, the authors acknowledge Carolina Pacheco, Liangzu Peng, Jeremías Sulam and Darshan Thaker for their insightful feedback that helped improve the presentation of this work. Finally, we thank K wan Ho Ryan Chan for helping us with implementing V-IP for baseline comparisons in Section
References
[1] D. Geman and B. Jedynak. An active testing model for tracking roads in satellite images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(1):1-14, January 1996.
[2] Raphael Szaitman and Bruno Jedynak. Active testing for face detection and localization. IEEE Transactions Pattern Analysis and Machine Intelligence, 32( 19140)):11419211 2010.
[3] Raphael Sznitman, Rogerio Richa, Russell H Taylor, Bruno Jedynak, and Gregory D Hager. Unified detection and tracking instruments during retinal microsurgery. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(5):1263-122) 1273, 2012.
[4] Ehsan Jahangiri, Erdem Yoruk, Rene Vidal, Laurent Younes, and Donald Geman, Information pursuit: bayesian framework for sequential scene parsing. arXiv preprint (ttl:1700.02344 2017.
[5] Aditya Chattopadhyay, Stewart Slocum, Benjamin D. Haeffele, René Vidal, and Donald Geman, Inter- pretable by design: Learning predictors by composing interpretable queries. IEEE Transactions on Puttern Analysis and Machine Intelligence, 45(6):7430 7443,,77433411 June 2023.
[6] Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. International Conference on Machine Learning, pages 5171-5180, 2019.
Zhifeng Zhang. Matching pursuit. PhD thesis, New York University, New York, New York, 1993.
Y.C. Pati, R. Rezaiffar, and P.S. Krishnaprasad. Orthogonal matching pursuit: Recursive function approx- imation with applications to wavelet decomposition. Asilomar Conference on Signals, Systems and Computers, pages 40 44, 1993.
[9] Michael Elad and Michal Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image Processing, 15(12)3376637755 2006.
[10] Jifei Yu, Xinbo Gao, Dacheng Tao, Xuelong Li, and Kaibing Zhang. A unified learning framework for single image super-resolution. IEEE Transactions on Neural Networks and Learning Systems, 2504))780-792, 2013.
[11] Zhiliang Zhu, Fangda Guo, Hai Yu, and Chen Chen. Fast single image super-resolution via examle learning and sparse representation. IEEE Transactions on Multimedia, 16(8):2178 2290299,8-29 2014.
[12] Zheng Wang, Ming-Jun Lai, Zhaosong Lu, Wei Fan, Hasan Davuleu, and Jieping Ye. Rank-one matrix pursuit matrix completion. In International Conference on Machine Learning, pages 91-99, 2014.
[13] Charles Soussen, Rémi Gribonval, Jérôme Idier, Cédric Herzet. Joint k-step analysis orthogonal matching pursuit and orthogonal least squares. IEEE Transactions on Information Theory. 59(5):315 3588- 3174, 2013.
[14] Chao Ma, Sebastian Tschiatschek, Konstantina Palla, José Miguel Hernández- Sebastian Nowozin, and Cheng Zhang. EDDI: Efficient dynamic discovery of high- value information with partial VAE, arXiv preprint a 142, 2018.
[15] Aditya Chattopadhyay, Kwan Ho Ryan Chan, Benjamin David Hacffele, Donald Geman, and Rene Vidal. Variational information pursuit for interpretable predictions. In International Conference on Learning Representations, 2023.
[16] Ian Connick Covert, Wei Qiu, Mingyu Lu, Na Yoon Kim, Nathan J White, and Su-In Lee. Learning to maximize mutual information for dynamic feature selection. In International Conference on Machine Learning, pages 6424 6447, 2023.

---

[17] 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. In International Conference on Machine Learning, pages 9748-8763, 2021.
[18] Dennis Lindley. On a measure of the information provided by an experiment. The Annals of Mathematical Statistics, 27(4))986-1055 1956.
[19] Alice X Zheng, Irina Rish, and Alina Beygelzimer. Efficient test selection in active diagnosis via entropy approximation. arXiv preprint arXiv: 227.11188 2012.
[20] Yu-Shao Peng, Kai-Fu Tang, Hsuan-Tien Lin, and Edward Chang. REFUEL: Exploring sparse features in deep reinforcement learning for fast disease diagnosis. Neural Information Processing Systems (NeurlPS), 31, 2018.
[21] Bruno Jedynak, Peter I Frazier, and Raphael Sznitman. Twenty questions with noise: Bayes optimal policies for entropy loss, Journal of Applied Probubility, 49(1):114-133 2012.
[22] Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Applicd and Numerical Harmonic Analysis. Springer New York, New York, NY, 2013.
[23] Vardan Papyan, Yaniv Romano, Jeremias Sulam, and Michael Elad. Theoretical foundations of deep learning via sparse representations: A multilayer sparse model and its connection to convolutional neural networks. IEEE Signal Processing Magazine, 35(4):72-55) 89, 2018.
[24] Joel A. Tropp and Anna C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 53612);4655-466, December 2007.
[25] Scott Shaobing Chen, David L Donoho, and Michael Saunders. Atomic decomposition by basis pursuit. SIAM Review, 43(1)1129-155, 2001.
[26] Ron Rubinstein, Michael Zibulevsky, and Michael Elad. Efficient implementation of the K-SVD algorithm using batch orthogonal matching pursuit. Technical report, Technion, 2008.
[27] Mark A. Davenport and Michael B. Wakin. Analysis of orthogonal matching pursuit using the restricted isometry property. IEEE Transactions on Information Theory, 5395):499--441,, September 2010.
[28] Shihao Ji. Ya Xue, and Lawrence Carin. Bayesian compressive sensing. IEEE Transactions on Signal Processing, 56(6):2346-2355 2008.
[29] Philip Schniter, Lee C Potter, and Justin Ziniel. Fast Bayesian matching pursuit. In Information Theory and Applications Workshop, pages 326-333. IEEE, 2008.
[30] Torbjom Eltoft, Taesu Kim, and Te-Won Lee. On the multivariate Laplace distribution. IEEE Signal Processing Letters, 13(5)3300-303, 2006.
[31] Ziv Goldfeld and Kristjan Greenewald. Sliced mutual information: scalable measure of statistical dependence. In Neural Information Processing Systems (NeurIPS), 2021.
[32] Laura Rebollo-Neira and David Lowe. Optimized orthogonal matching pursuit approach. IEEE Signal Processing Letters, (4): 137-140, 2002.
[33] Thomas Blumensath and Mike E Davies. On the difference between orthogonal matching pursuit and orthogonal least squares. 2007.
[34] Abolfazl Hashemi and Haris Vikalo. Accelerated orthogonal least-squares for large-scale sparse recon- struction. Digital Signal Processing, 82:91-100 105, 2018
[35] Jian Wang and Ping Li. Recovery of sparse signals using multiple orthogonal least squares. IEEE Transactions on Signal Processing, 65(8):2049-066, 2016.
[36] Jeffrey Pennington, Richard Socher, and Christopher D Manning. GloVe: Global vectors for word representation. In Conference on Empirical Methods in Natural Language Processing, pages 1532-1543, 2014.
[37] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition, pages 248-255. IEEE 2009.
12

---

[38] Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2017.
[39] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[40] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The Caltech-UCSD birds-200-2011 1 dataset. 2011.
[41] Tuomas Oikarinen, Subhro Das, Lam M Nguyen, and Tsui-Wei Weng. Label-free concept bottleneck models. In International Conference on Learning Representations, 2023.
[42] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subhiah, Jared Kaplan, Prafulla Dhariwal, Arvind Ncelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Neural Information Processing Systems (NeurlPS), 33:1877-1901, 2020.
[43] Tuomas Oikarinen, Subhro Das, Lam M Nguyen, and Tsui- Wei Weng. Label-free concept bottleneck models. htttps://giteii htttp:://gg.hhb....mm/rrtttttttr
Labb-a-aa- free- CBM 2022.
[44] Bob L Sturm and Mads Græsbøll Christensen. Comparison of orthogonal matching pursuit implementations. In European Signal Processing Conference, pages 220-224, IEEE, 2012.
[45] Aditya Chattopadhyay, Kwan Ryan Chan, Benjamin David Haeffele, Donald Geman, and Rene Vidal. Variational information pursuit for interpretable predictions, lattps://github cwmm roam/haacchahh/////
Variational Inf ormatiiiioooo iociurruPPuutt 2023.
[46] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning The MIT Press, 2005.
[47] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, Inc., 1991.
[48] Peter J Bickel and Kjell A Doksum. Mathematical Statistics: Basic Ideas and Selected Topics, Volume I. Prentice-Hall, second edition, 2001.
[49] C. Radhakrishna Rao, Helge Toutenberge, Shalabh, and Christian Heumann. Linear Models and General- izations: Least Squares and Alternatives. Springer Series in Statistics. Springer-Verlagg New York, third edition, 2008.
[50] Weihao Gao, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Estimating mutual information for discrete- contrteocon mixtures. Neural Information Processing Systems (NeurIPS), 2017.
[51] Roman Vershynin. High- Bigh--Dimessioall Probability. 2020.
[52] Andrew Gelman, John B. Carlin, Hal S. Stern, David B. Dunson, Aki Vehtari, and Donald B. Rubin. Bayesian Data Analysis. CRC Press, Boca Raton, FL, third edition, 2014.
[53] David Gunning and David Aha. DARPA's 's explainable artificial intelligence (XAI) program. Al Magazine, 40(2):44-55 58, 2019.
[54] David Bachrens, Timon Schrocter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Klaus-Rober Müller. How to explain individual classification decisions. Journal of Machine Learning Research, 11:80031831, 2010.
[55] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint 1312.61311.6044 2013.
[56] Aditya Chattopadhay, Anirban Sarkar, Prantik Howlader, and Vineeth Balasubramanian. Grad-CAM++: Generalized gradient-based visual explanations for deep convolutional networks. In IEEE Winter Confer- ence Applications of Computer Vision (WACV), pages 839-847. IEEF, 2018.
[57] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das. Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-CAM: Visual explanations from deep networks via gradicnt- localization. In IEEE International Conference on Computer Vision, pages 618 626, 2017.
[58] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. SmoothGrad: removing noise by adding noise. arXiv preprint arXiv:1706. 0380000038..... 2017.
[59] Stefan Kolek, Duc Anh Nguyen, Ron Levie, Joan Bruna, and Gitta Kutyniok. A rate-distortion framework for explaining back-box, model decisions. In International Workshop on Extending Explainable Al Beyond Deep Models and Classifiers, pages 91-115. Springer, 2020.
13

---

[60] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. Neural Information Processing Systems (NeurIPS). 31, 2018.
[61] Mengjiao Yang and Been Kim. Benchmarking attribution methods with relative feature importance. arXiv preprint
2019.
[62] Pieter-Jan Kindermans, Sara Hooker, Julius Adebayo, Maximilian Alber. Kristof T Schütt, Sven Dähne. Dumitru Erhan, and Been Kim. The (un) reliability of saliency methods. In Explainable Al: Interpreting, Explaining and Visualizing Deep Learning, pages 267-280. Springer, 2019.
[63] Harshay Shah, Prateek Jain, and Praneeth Netrapalli. Do input gradients highlight discriminative features? Neural Information Processing Systems (NeurIPS), 34, 2021.
[64] Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks on post hoc explanation methods. AAAI/ACM Conference on AI, Ethics, and Society, pages 180-186, 2020.
[65] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-215, 2019.
[66] Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang. Lesia Semenova, and Chudi Zhong. Interpretable machine learning: Fundamental principles and 10 grand challenges. Statistic Surveys, 16:1-55, 2022.
[67] Pang Wei Koh, Thao Nguyen, Yew Siang Tang. Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. International Conference on Learning Representatinns pages 5338-5348, 2020.
[68] Moritz Bohle, Mario Fritz, and Bernt Schiele. Convolutional dynamic alignment networks for interpretable classifications. In IEEE Conference on Computer Vision and Pattern Recognition, pages 10029-10038, 2021.
[69] David Alvarez Melis and Tommi Jaakkola. Towards robust interpretability with self-explaining neural networks. Neural Information P Processing Systems (NeurlPS), 31, 2018.
[70] Mike Wu, Sonali Parbhoo, Michael C Hughes, Volker Roth, and Finale Doshi-Velez. Optimizing for interpretability in deep neural networks with tree regularization. Journal of Machine Learning Research, 72:1 2021.
[71] Eric Wong, Shibani Santurkar, and Aleksander Madry. Leveraging sparse linear layers for debuggable deep networks. In International Conference on Machine Learning, pages 11205- 11216, 2021.
[72] Anirban Sarkar, Deepak Vijaykeerthy, Anindya Sarkar, and Vineeth N Balasubramanian. A framework for learning ante-hoc explainable models via concepts. In IEEE Conference Computer Vision and Pottern Recognition, pages 10295, 2022.
[73] Meike Nauta, Ron Bree, and Christin Seifert. Neural prototype trees for interpretable fine-grained image recognition. In IEEE Conference on Computer Vision and Pattern Recognition, pages 14933-14943, 2021.
[74] Jon Donnelly, Alina Jade Barnett, and Chaofan Chen. Deformable ProtoPNet: An interpretable image classifier using deformable prototypes. IEEE Conference on Computer Vision and Puttern Recognition, pages 10265-10275, 2022.
[75] Oscar Li, Hao Liu, Chaofan Chen, and Cynthia Rudin. Deep learning for case-based reasoning through prototypes: A neural network that explains its predictions. In AAAI Conference on Artificial Intelligence. volume 32, 2018
[76] Chih-Kuan Yeh, Been Kim, Sercan Arik, Chun-Liang Li, Tomas Plister, and Pradeep Ravikumar. On completeness-wware concept- concept-based explanations in deep neural networks. Neural Information Processing Systems (NeurIPS), 33:20554-20565 2020.
[77] Zhi Chen, Yijie Bei, and Cynthia Rudin. Concept whitening for interpretable image recognition. Nature Machine Intelligence, 2(12):772 7822 2020.
[78] Mert Yuksekgonul, Maggie Wang, and James Zou. Post-hoc concept bottleneck models. arXiv preprint arXiv:2205. 15480, 2022.
[79] Sachit Menon and Carl Vondrick. Visual classification via description from large language models, arXiv preprint arXii:2210.07113 2022.
14

---

[80] Tuomas Oikarinen and Tsui-Wei Weng. CLIP-Dissec:: Automatic description of neuron representations in deep vision networks. arXiv preprini arXiv:2204.1096 2022.
[81] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Pattern Recognition, pages 770-778, 2016.
[82] Mana Sezdi and Yavuz Uzcan. Clean room classification in the operating room. In Medical Technologies National Congress (TIPTEKNO), pages 1-4. IEEE, 2016.
15

---

A Proofs
Throughout, we will write 11g Ip,e to case the notation.
A.1 Proof of Lemmal
Proof. Assume that the atoms selected in Dr are linearly independent (since linearly dependent atoms will not be selected by the equation [P-OMP algorithm- more on this in A.2 The proof relies on Gaussian conditioning.
Notice that since Z is a standard normal distribution and the vector Ç= ((x, 2), 2 Dz) is just linear transformation of standard normal, is also a multivariate normal random variable. Its covariance is
(xTx A. De DE DE
cov(C)
(12)
Now there are two cases. Case 1: The covariance matrix has full rank. In this case,
P((r, (QQ (dq: = Q E ()) = N((=) z²), [1bb x1
(13)
This result is obtained by observing that the conditioning event {Q (dq. =0) Q E L} is exactly the event Z =) since Dr consists of atoms selected from D indexed by L. Now, the result obtained by using formulae for conditioning in multivariate Gaussian random variables [46 equation A.6]. Specifically, the mean is computed as
El Σ) D = -' = x² Dc(DEDD)
=DecDox,2).
The variance is computed
var((z, Z) (Q= = (dq, (d) :0:::00 Q C}) x² -- De(D
xT(1 De(DDED) D')x
xx 2'( ll
rT''li d'Ilb
|11b x11
which is exactly the variance parameter for the normal distribution in equation 13 Lemma is then just the analytical form of the differential entropy of a Gaussian 47 equation 9.9].
The result in the
The covariance matrix singular. This would be the case when æ can expressed as linear combination of the columns (atoms) of De. Intuitively, looking equation 13] one can conclude that in this case the conditional distribution of (a,, Z) given the history would Dirac delta distribution since the variance is 0. Consequently, the differential entropy would converge to -O..
Case 2:
This argument can be made rigorous as follows. Consider family of random variables defined as S, = (xr, Z) + on) where 1j an independent standard normal distribution. We can conclude from Slutsky's theorem (8 Theorem A. 1419.9] that
G $ (z, Z) as 0,
where 4 refers to convergence distribution. Observe that
Yo
P(G. IQ (dq, 2 C)) -(( 20) 02,
since ||T = = 0 (recall in this case is linear combination of columns of Dz). This sequence of distributions is known converge in distribution to the the Dirac delta distribution, thus proving the desired result.
16

---

A.2 Proof of Theorem 1
Proof. First iteration. Assume that is not one-sparse in D (this case will be covered separately at the end of the proof). For the first iteration (k = 1),
Q1 arg m (z. Z)) arg max [(dd) Z); (zz Z)), QiEQ
d'ED
where the second equality is just from definition of the queries and their answers in this case.
Now
1(id, 2); (z, 23) h((dP, 2)) h((d), 2) (a, 2)),
(14)
[ Since Z is Gaussian, (d) 2) and (ar Z) where i().) is the differential entropy 47 Definition 9.1 /
are jointly Gaussian. Therefore we can compute the entropies in equation 14 as 47 Example 9.1.2]
h((d 2)) 2
log(2 var 2)))
and
h((dP 2) (x, -)) - log (2Te varl (d) Z) (a, 2))).
Since cZv(Z) I. and EZ get
var( Z2) (d' 2)² ||
Considering the joint covariance
(
((.22))
2) (z. 2)
| (a,
(di
COv
|
and applying a basic identity for Gaussian conditioning [46 Equation A.6], we obtain
(di x)
var((d) Z) (x. 2)) = ||
112
Thus for iteration A 1. IP-OMI amounts to solving
1
1d 113
Q = arg max log deD
2
d
12
(ds,
x)
Kdd xx)
max WED
| |
(15)
Iterations between the first and last. Next consider iterations between the first and last IP-MMP (the last iteration will be discussed separately). For all k < 1, the query selection strategy is as follows:
Qk+1 arg max I(Q': (x, H1*)) arg max I ((d), IZ); (2, H1.k). QiE
(16)
deD
As before, we assume that d3, I, and the columns of D₃ are linearly independent (we will address collinearity issues later). Expanding the Mutual Information (MI) into difference of differential entropies, we obtain
I((d) Z); (x, Z)
Hi.)) h((d', 2) HI.)) ((dd, Z) (x, Z), H1s)).
(17)
Notice that (d), Z), (x, Z), and D Z are jointly Gaussian. So. similarly to the first iteration, the MI objective simplifies to
1 log(2ire 2Te var( ((P,, 22 HIaa)) - log(2iee var((d', Z) (x, 2), H1.a))
I((d), 2); (a,, 2) H1.a) 2
'If' x is one-sparse in D. then this expansion will not hold since the joint distribution ( ((d, Z), (x. -))² will be degenerate for some j. However, the mutual information can still be suitably detined. We defer the details of this case the end of the proof.
17

---

The history can be written Hi** = (D) =d so we compute the requisite conditional variances from the joint covariance matrix
(
(
(0:2
dd' Z) (r. D
| x d'
(d')²x T D
(d) x DR D
DE
(1/2)
Cov
(18)
D d'
We once again apply the Gaussian conditioning formula, and rewrite the difference of logs the log of quotient to obtain
1 2
(db)T DR(DEDD) d'
1[(d22) 23, (x, Z) His)
log
TTT IJ DE D
( -- Ior Dal
[x DuJ
D.
(19)
Define C2 = [Dx x]. let ll,, denote the orthogonal projection onto range Ck). and let I. denote the orthogonal projection onto range(Cx)+ We can rewrite equation 19 in terms of projections as
(dl II d'
I((d, 2); (z, 2) H1.k) log
(20)
(di, II di)
Lemma 3 (149) p. 323). Let A be partitioned as [A1 A2) with A1 E RRxxp and rank(A1) P- Ag E (n-p) and rank(A2) = p. Let IIA, be the orthogonal projection onto the columns of A and B = IT, Ag- Then the orthogonal projection, A onto the columns of A can be written as 1I II + B(B" BB B²
Applying the above lemma Ck. have
Tc. 1
xx TI
x
which, recalling the idempotence of 1lg, implies
IT IT = ITc,
II | II:
Thus we can simplify the denominator of equation t0
(d) 11,,1,,, d) = dd', II
(dd,,
II dd
I x2 x0 (IT di .z)2
=|[I d'
||T (TT di IT ,r) 2
anli
d'
x
where in the last equation we have used the symmetry and idempotence of IT. Substituting into equa- tion 20 we obtain
| d'
arg max De d
I((d'
Z); (2, Z) H1:k)
arg max di D. [u, di [T d3 ||
(IT di IT x
1
arg max ED | 1l
(II di x) t1 1 d
KII I1
&ED WE 11 [T d' || IT
arg max
= arg max [((d) 2); Z) H1x))
deD
18

---

which is the required query as in equation 16 The last equality is obtained by observing that if for any d' D, I d' l| then d' can be written as a linear combination of atoms corresponding to queries selected by IP-OMP in the first k iteration. As result, the random variable (d', Z) a function of the the previous & queries selected, namely DJ Z. Hence, (d', Z) is conditionally independent of (z, Z) given history H1:8 = {D] Z D }. Since the mutual information between independent random variables is zero, the fourth equality follows
Last iteration. The last iteration for IP-OMP needs special care for scenarios in which there is noise and the observed signal x D,8 for some unknown E RR. This implies that if the algorithm is carried out for large enough r - 1 iterations, then eventually, we would reach that stage such that there exists atom d D, such that will lie in the span of [D,-1 d-). In such scenarios, the joint measure of random variables ((r, Z). D._122 Z, (d,, Z)) is not absolutely continuous with respect the Lesbegue measure, and thus is not defined according to equation 17 However, we can still define it as the limiting conditional mutual information for family of random
variables, 6o = (zr, Z) + 0z), (with 1j ~ (O 1) independent of Z) with (d,, Z) in the limit - O. Specifically, for any a > 0, we have
I((d,, Zi H1:--1)= = I(dd,, ZoiSo
(21)
= 11(6 - -= ==========0 - DJ 7 DJT (dr, 7))
Since &o is jointly Gaussian with the random variables, D 7 and (d-, Z), equation 21 can be rewritten as, for any a > 0,
1
var(So DD. = DT 112)
I((d,, ((:d+ 111--11
log
2 var(So 1 DJ 1 20 (d 2i)
1
2 2112 + 0² ||Ib),,
log
2
d2
The second equality is obtained by applying known formulae of Gaussian conditioning as done in
equation 19 Note that p._, ll can also be written as ||II,- 1 following our convention.
Finally, taking the limit o + 0, we obtain
T(dy, Z); (2, 2) H1 H1r-1):= := lim T((d,, 2) (11--11 = oc,
o-0
Moreover, notice that since, by assumption, x now lies in the span of [D,-1 drl. we can express as DD--1 dr|a, for some E TR.. This implies that
[D.11 II 1I- ID.- d=
cll
for some scalar e E R. Thus, _T_, dr and IT are collinear vectors indicating that d, achieves the arg max to the IP-OMP objective. That is,
(II_ L'
11
II=_ dy, ||Tا_ dr | 1.
max DED
|
To conclude, we have shown that any atom that results in x being in the span of that atom plus that atoms already selected so far the first 7 iterations would the arg max of the objective in IP-OMP in the last iteration. This iteration would be the last since all subsequent iterations would have no informative queries left as the conditional mutual information for all remaining queries would be 0, since they would be rendered conditionally independent of the target variable given the history H (as described footnote 6).
'Note that although in this case, the conventional definition of MI is not defined since do not have a joint
density with respect to the Lesbegue measure, we can use the more general defintion mutual information [50) Detinition 2.1] which depends on the log of the Madon-Nikodym derivative of the joint measure with respect to
to the product measure (of the marginals) which is always defined, Since (d', Z) is independent of (z, 2) given the history this Radon- Nikodyy derivative would be the constant function 1 and hence MI would be zero
19

---

A.3 Proof of equation 7
Proof. Recall that H1rr Z =D =. As discussed in equation 12 the joint covariance
cov ( (ar Dz
xx x² Dr D
(22)
D.
where De is replaced by D, since we are no longer dealing with an arbitrary subset of atoms (denoted by C) but rather with the r atoms selected the first J iterations of IP-OMP.
Consequently from equation 13 we conclude that
(( 2) H1s)) = -N((D,
The result in equation 7 is then obtained by the fact that the mode of Gaussian is just its mean.
We conclude this proof with a note that in the case when can be expressed as linear combination of atoms in D,, the distribution P((x, Z} H1z)) is Dirac delta distribution with all its mass concentrated on (D,Djr, =²) (see Case 2 in A.. As a result, even in this case, IP-OMP's prediction of the target would be (D, z
A.4 Proof of Lemma
Proof. Notice from the query selection equations for IP-OMP that the choice of the next query independent of the particular realization of Z. This means that, given x. for all realizations of Z E IRm (R is the support of an m-dimensional standard normal), IP-OMP will select the exact same sequence of 7 dictionary atoms. Thus, using the result from equation we can conclude that IP-OMP's prediction of the target for any E Th will be (D, 2).
B Sparse Recovery Experiments: Details and Further Results
B.1 General Setup
To test the sparse recovery performance of IP-OMP against that of OMP, we experimented with IP-OMP on synthetic data. Our setup is a modified version of Tropp and Gilbert's [24), who studied recovery guarantees for OMP with Gaussian dictionaries. For n = 256 and n 1024, generated random dictionaries D, and sparse codes 3, for varying numbers of measurements m and sparsity the unit
levels Each column of the dictionary D. was drawn from the uniform distribution sphere in Rm The sparse codes 33 were generated by fixing some sparsity level s and drawing the support S from all cardinality-s subsets of [1,... n uniformly at random. On the support (i S), the coefficients 3% were generated according to two schemes:
(i) 3, NO0 (Gaussian nonzero coefficients), and (ii) 3. (constant nonzero coefficients).
For $ 5, the corresponding coefficients were set to zero for both of the above schemes. The second setting, which is supposed be more challenging for OMP, matches the generation of sparse coefficient vectors in (24).
For each setting of and nonzero coefficients (Gaussian or constant), we report recovery for different grid of m values. These values, given in Table I were selected to emphasize the transition region in the recovery probability curves. For both small (n 256) settings, we simulated sparsities E {4, 10, 16..... 36). For both large (n 1024) settings, we simulated sparsities E (4, 6, ....,, 16).
This setup used test the sparse recovery of IP-OMP and OMP in both noiseless and noisy settings. Note that for noisy settings, we only experimented with the Gaussian nonzero coefficients for generating 8, on the sampled support (setting (i)) due to resource limitations. We will first elaborate on the noiseless setup and then the noisy case.
In high dimensions, Gaussian vectors concentrate in norm 51 Chapter 3J, which justifies applying Tropp and Gilbert's problem settings to spherical dictionaries.
20

---

Table 1: Values of m in sparse recovery experiments.
Nonzero coefficients
Yt 256
n 1024
Gaussian
(4, 16, 28 ..... 208}
{5, 10, 15, ................................ 115]
Constant
(8,16.28.... 256]
(5, 10, 15...., 205
B.2 Experiments without Noise
For each (mz n) triple, we generated 1000 dictionary-code-sinnal triples (Dar So, x.)) as described in Appendix $B.1 and ran both OMP and IP-OMP for = iterations. For each trial, we checked whether OMP and IP-OMP recover 3o exactly. Writing BaIg. to denote the IP or IP-OMP estimate of S.. we define exact recovery to be NMSE(BALe (6) < 10 10-14 For Gaussian nonzero coefficients, we report the fraction of successful trials for each algorithm and (m, n) triple in Figure 2 For
constant nonzero coefficients, we report the same in Figure Both Figure 2 and Figure were
inspired by similar figures in [24
Number dictionary atoms n=256
Number dictionary 122
Probabitty recovery.
1.0
Probablity exart recovery
1.0
0.8
5o4
5=10
5-18
5+8
0.4
S-22
0.4
5-10
5-28
s-12
0.2
5-34
0.2
5-14
0.0
0.0
150
measurementts
measurements
Figure 6: Exact recovery probabilities for OMP and IP-OMP with constant nonzero coefficients. Each solid line represents the recovery probability curve for OMP at fixed sparsity level, as the number of measurements increases. The overlaid circles are the corresponding probabilities of recovery by IP-OMP. The left panel is the small setting (n 256), while the right is the large setting (n 1024).
Qualitatively, the constant nonzero coefficient results in Figure similar to the Gaussian nonzero coefficient results in Figure 2 As discussed $3 the estimates BAIg. degrade gracefully as the measurement rate m/n (a measure of the indeterminacy of the problem) tends to zero and sparsity rate s/m (a measure of the complexity of the solution) tends to one. However, the constant nonzero coefficient case is more challenging to recover (probability curves for each sparsity s are shifted to the right relative to the Gaussian nonzero coefficient case). The difficulty of the constant nonzero coefficient setting has been noted previously for OMP [24..
B.3
Experiments with Noise
As described in $ extended the setup in Appendix $B.11 with the addition of Gaussian noise. That is, for each draw of the uniform spherical dictionary D., and sparse code 8, ~ (O,,, 7), we also sampled noise (N o²T) independent of D, and 83-- The variance x² of this noise was set to achieve particular [E[SR] according to equation 23 This was done to ensure that the level of noise added observed signal is consistent across different settings of (m, n, s) described in Table [ The natural scale for varying the [SSR] values is logarithmic; in particular, we chose to use the decibel (dB) scale, where we take E SNR in dB units to be defined
DD,8..11 dB.
[(SR = 10 1og
|
Expected SNR values were swept from 5 dB to 20 dB in 5 dB intervals. Thus, for each (m, n, s, B[SNR] setting, we generated 1000 (D., Bor Tos e) tuples and ran OMP and IP-OMP
'Recal that the NMSE was defined in equation
21

---

n=256, E|SNR]=10 dB
n=256, E[SNR]=15
Mean NMSE
10"
10"
5-10
Figure 7: Further numerical results sparse recovery where the signal is corrupted by noise. These result add to those in Figure report NMSE( NMSE( (BAlg.; for OMP (lines) and IP-OMP (overlaid circles). On the r-axis, report the number of measurements (signal dimension) m. Each value of the sparsity s corre- sponds to different color.
S-16
10"
10"
28
1
On the y-axis
5-40
10
200
1=1024, E[SNR]=10 dB
n= E[SNR]=15 dB
54
Mean NMSE
10
10
10
10"
14
10
0
50
100
50
100
#Measurements
#Measurements
for iterations. Finally, for each trial, we measured the quality of the estimates BAig. by their NMSE as defined in equation g The results for E[SNR] {5 dB, 20 dB) are shown Figure 3 in the main
paper and the results for E[SNR] E {10 dB, 15 dB) } are reported in Figure 7
Now we present proposition that gives formula for [E[SN]] in terms a, m and when Do. fo. and e are distributed according to our above described sampling process. For technical consistency, we denote D, B, F. the random variables and Do Bo and their respective realizations.
Proposition 1. Let D be X re-imensional random matrix with columns distributed independently and uniformly on the unil sphere. Let be a random support of size s, chosen uniformly from all Let B be random 8-sparse vector with support on S and with
size-8 subsets of (1,2....,,)) coefficients zero-mean, unit-variance Gaussian as described in
B
Let E (0,0021 Then for
the noisy measurement model X- = =DB + E, we have
| |
SNR] ED,,EE
(23)
0² (m - 2)
or on dB scale,
E[SNR] 10 log10 ( 2) dB.
Proof. Since E is independent of DD and B, we can split the expectation in the definition of the expected SNR into
E[SNR] = E D E
|
We will first compute [B]
D = EBBTT D' DJ
Er DDB
Etr((BB D''')
tr (E|BB" (DD"')
(24)
Rewriting as an inner product, we have
E)D" (DD 8:j.
where D' is the thh column of random matrix D and 6.j is the Kronecker delta. The last equality if obtained by observing that since || ||2 is a constant one and Di, Dí are independent for i # j. We thus conclude that E D) = 1.
Notice that B depends the random support S. Furthermore, since D = I and
tr(E |ED"" tr (B(BB"))),
22

---

it suffices to consider the diagonal entries of E[BB*):
E[BB*)+ Ja
E
E
BB
[S] 1
E s]]
(i), Pi S},
1s( is the set indicator function for random set S
where the third equality results from the fact that coefficients B, on the support (i.e., i S) are Gaussian with zero mean and unit variance. In the fourth equality PP S] is the probability that randomly drawn subset S would include element in it. To compute IP[i E S), we count the number of cardinality-s subsets of {1, ..... n containing and divide by the total number of cardinality-s subsets. This is described in detail in the following equations where we use to denote the different values S takes the sample space.
Pli E S] = I[S 2 : |S| = 8, E SH
| E 2 : |S| = s}]
(n - 1)!
s!(n s)!
(s 1)!(n 1 - 8 1)!
nl
(n 1)! s(s 1 1)((n= - s)
1)!(n 5)!
nln 1)!
n
Thus we have
E(BK") |k 8 i= 1.......7
Conclude that
[IB[BB"]E(D'' DJ) = Lr(E(BBT)
7
S.
(25)
Rewriting || as
FE
E?
L.d. and recalling that E, ~ AO, 22), we see that (1/a²) || has x2 distribution with m degrees of
freedom. It follows that 0² E| has inverse- x2 distribution with degrees of freedom, which has an expected value of 1/ (m - 2) [22
pp. 578-579, 583J. Thus
1
E
LE 1
a2 2)
Finally, we plug the value for |B D!) from equation 25 into equation 24 and multiply by []]]
1
[SNR]] = tr (E [35*]] E D DJ)
f2(m- - 2)
23

---

C Prior Work on Explainable AI
In this section we review prior work on explainable AI. For the references herein please refer the References section at the end of this Appendix.
Modern deep networks often criticized for their opaque nature resulting in lack of transparency in their pecision-making process [53]. As a result, they are often perceived as -black-boxes". Initial
attempts to explain deep networks relied on post-hoc techniques like rensitivity-based or gradient-
These methods attempt explain deep network's decision by generating a saliency map reflecting which parts of the input were most important for a particular prediction. The veracity of these methods at explaining the true underlying Docision-making process has been questioned in several recent works 160, 61 62 63 64 65]. Moreover, the explanations obtained, in terms of importance of raw input features (like pixels) to the predicted output, are often not meaningful explanations to stakcholders [ 41. As a result, recent works have advocated that machine learning (ML) models should be
based analyses of the inputs and the outputs of a trained network [54
55
56
57
58
59
explainable by design [66 3
Over the past few years, there has been a flurry of papers that propose ML algorithms that are explainable by design; however, they vary in their definitions of what it means to be explainable. These can be broadly classified into three categories:
1. Regularization to make deep networks more interpretable. These methods propose to regularize the training of a deep network such that their decisions can be well-approximated locally by interpretable MI. model like linear classifiers [68 69] or decision trees [70]. However, as in post-hoc techniques to explainability. the effect of these approximations on the fidelity of the generated explanations is unknown. Alternatively, Wong et al. [7I) show that learning a sparse final layer of the network improves interpretability, but requires post-hoe methods like LIME to explain the deep features used by the sparse layer.
the deep networks decision-making process
2. Explanations based on learnt concepts. These methods propose to jointly learn prototypes or latent vectors from data and use these latent vectors to make a prediction (72 73 74 76). The final prediction is then explained in terms of these learnt concepts, whose interpretation is based on exemplar-basse that maximally activate a particular feature of the latent vector to decide what that feature represents. Similarly, Li et al. 77 replace their learnt prototype by the embedding of the ncarest-neighhour training image patch. This selected patch then serves as an interpretation of the prototype. A limitation of these methods is that it is not necessary for these learnt prototypes/latents to be interpretable to the end-user [5].
reasoning. For example, Sarkar et al. (72 look at images
3. Explanations based on user-defined concepts. In these methods, the user first defines a set of concepts that are relevant for the prediction task, along with annotated datasets indicating the presence or absence of concepts in each input. The final prediction is the made based on these concepts, which serve an explanation for the prediction 15 15 67]. In contrast to the previous set of methods, joint training of concepts and label classifiers in these methods is done in a completely supervised manner (the concepts are latent vectors). In another direction, Chen et al. (77) propose to make layers of a deep network more interpretable by learning a rotation matrix that rotates any selected deep network's layer activations such that every activation (after rotation) corresponds to one of the user-defined concepts. Unlike the previous two categories, the methods in this category have the flexibility of allowing the user to decide on the nature of explanations required for the prediction task by selecting the set of concepts as input to the learning algorithm. Our proposed algorithm CLIP-IP-OMP also belongs to this class of methods.
Despite its advantage, a major limitation of the third category of methods is the requirement for data annotated with these defr-nefined concepts. This bottleneck was addressed (for image classification tasks) very recently in 41 (88 79 who showed that CLIP, a large vision-language pre-trained model can be used to provide zero-shot annotations for user-defined concepts. In particular, text embeddings of the concepts are obtained using CLIP's text encoder. The image annotations (whether or not a concept is present or not in the image) is then provided via the dot product between the text embedding of the concept and the image embedding (obtained by passing the image through CLIP's image encoder). This motivated our algorithm CLIP-IP-OME which uses CLIP embeddings to construct
24

---

the interpretable dictionary. As argued in the main paper. our proposed algorithm is computationally much simpler than existing state-of-the-ee methods of explainable-A (comparing with methods from the third category, which include Variational-IP [I5] and Label-free CBM [4I). CLIP has also been applied for semantic interpretation of neurons a Convolutional Neural Network [8)].
D CLIP-IP-OMP Training Details
D.1 Semantic Dictionaries
In principle, a user can define a set of semantic concepts that are relevant for the classification task. dictionary can then be constructed by obtained CLIP's text embedding for each one of those concepts. In this work, to illustrate the usefullness of our framework, we used the set of concepts used in [41] for each dataset. For completeness, we describe the process in which these concepts were obtained in more detail.
The authors of 41 employed GPT-3 42
large language model, to extract an initial set of semantic
concpets. They used three prompts for this purpose.
List the most important features for recognizing something as a "class".
List the things most commonly seen around a "class".
Give superclass for the word "class".
In the above prompts "class" a placeholder that is replaced by the class names present in the dataset. This initial list of concepts was then further pruned to remove redundancies. The authors employed the following set of rules for pruning.
Any concepts with textual description longer than 30 characters was removed.
Any concept too similar to the target class was removed. This was done to prevent explana- tions of class to be the class itself. To do this, the authors measured the cosine similarity between the concepts and the target classes in the text embedding space and pruned any concept with similarity higher than 0.85. The cosine similarity was measured by weighted combination of CLIP's ViT-B/16 text encoder and the all-mpnet-base-22 sentence encoder.
Concepts similar to each other in CLIP's text embedding space were pruned to remove duplicate concepts. Specifically, any concept with more than 0.9 cosine similarity (same weighted combination as above) with any concept already present in their list.
Concepts not present in the training data were pruned. This was done by removing any concept whose average top-5 CLIP activations (measured as similarity between the concept's CLIP text embedding and the image's S CLIP image embedding) was below a pre-defined threshold.
Finally, the authors employ a projection layer learn to estimate CLIP's similarity between a text concept and an image given the image's deep features obtained from some Backbone network like Resnet-50 [81 (so at time CLIP would not be needed). Any concept that this projection layer is not able to estimate well (using some measure of accuracy) is removed.
The number of concepts finally used for each dataset are as follows: 128 for CIFAR-10 10, 824 for CIFAR-100, 208 for CUB-200, 4523 for ImageNet, and 2207 for Places365.
D.2 More Training Details for the CLIP-IP-OMP Algorithm
For all our experiments we use the CLIP Vit-B/16 model, In our experimental setup in $ 4.2 for given dataset, we first set the desired number of iteration 2 run the IP-OMP algorithm for sparse- coding the image embedding in terms of dictionary atoms. This is the desired explanation length. We then obtain sparse-codes for every image in the training set using the IP-OMP algorithm. This creates
"While we employed this termination criterion in our experiments, one can also alternatively use a variable number of iterations per image by using the entropy- based stopping criterion where one terminates once the norm of the residual sufficiently small.
25

---

new training dataset D' where every (image, label) pair is transformed into (sparse-code, label) pair. A linear network then trained using the cross-entropy loss using D'. For all datasets we used the same training configuration. We employed SGD with momentum optimizer with learning rate 1.0 and momentum 0.9. To prevent overfitting, we employed a drop-out layer before the linear layer with parameter 0.5. Finally, the linear classifier was trained for 1000 epochs. The input and output neurons for the linear layer for every dataset was taken as the number of concepts in the dictionary and the number of output classes respectively. The prediction probability of the trained classifier is obtained via a softmax on the output.
To obtain the curves in Figure 5 we repeated the above described process for different values of T, Since, our classifier is linear, training via SGD is relatively fast. The longest time being on the Imagenet and Places365 small datasets (since they have 1.28M and 1.8M images respectively) where every epoch takes about 17 and 50 seconds respectively on a single NVIDIA RTX A5000 GPU with a batch size of 1024.
E
Example Runs for the CLIP-IP-OMP Algorithm
We show example runs of the CLIP-IP-OR IPOMPP algorithm on 5 images selected from the test/validation set 1o of the different datasets on which we tested our algorithm. For each dataset, we run the IP- IP-OMP algorithm for fixed number of iterations and make predictions using linear classifier. In practice, a user can look at the accuracy vs. explanation length trade-off curves (Figure (5) and decide on a value for based on their requirement (more accuracy vs. ease of interpretation of the results). In this appendix, for every dataset, we select some value for T to illustrate the efficacy of the proposed framework making explainable predictions.
E.1 ImageNet
For this dataset, we set r = 9. that is, the sparse code OIP for every image has support A linear classifier trained on these sparse codes gets about 63% accuracy, which is within points of what can be achieved we run the IP-OMP algorithm long enough. This can be seen from Figure 5 where the test accuracy vs. explanation length curve for ImageNet saturates about 70% accuracy for relatively large T (say = 50). Results in Figure
|| of size 9.
1. In Figure hh, our model correctly predicts "Great White Shark". The sign of the weights of the linear classifier seem to correlate with the sign of the atom coefficients the sparse code. The prediction can be attributed to positive concepts like "shark", "a large, white, rounded head", "powerful jaws"" and "marine animal", all of which are salient features of a great white shark. Similarly, negative concepts like "swan", "planets", "streetcar", and "a toad" are concepts whose presence would indicate that the image is definitely not of great white shark.
2. In Figure our model correctly predicts "Snow Leopard". The sign of the weights of the linear classifier seem to correlate with the sign of the atom coefficients in the sparse code. The prediction gray and white coat", and "a cub"; which are also the concepts to which the classifier assigns the highest weights. Note other concepts like "a cell" (probably referencing zoo cell) and "a fence" are also present in the image, and are attributed as positive concepts in the sparse code. However, since these are not salient for the class "Snow Leopard", these are attributed smaller weights by the linear classifier. Thus, our method shows that the model is making the right prediction for the right reasons, something that is very difficult to ascertain in black-box box deep networks. Similarly, absence of concepts like "a striped coat" and "a white throat" probably help the classifier distinguish a snow leopard from other big cats.
be attributed positive concepts like "spotted or striped fur", "a mottled
3. In Figure ge, our model correctly predicts "Goldfish", The sign of the weights of the linear classifier seem to largely correlate with the sign of the atom coefficients in the sparse code. The prediction can be attributed to positive concepts like "a fish tank", "a [sic] aquarium".
We use validation sets only for the ImageNet and the Places365 datasets since for these datasets we only have access to the validation set and not the test set. TTe support of a vector is the set of indices of all non-zero elements in the vector.
26

---

"orange and white stripes" (which is very salient to goldfssh;; which are also the concepts. on which the classifier assigns the highest weights. Note that "often has a decorative design" is also positively attributed in the sparse code by IP-OMP, most likely because goldfish is often seen as decorative item in one's 's household. Indeed, inspecting the GPT3 concepts recovered for the "GoldFish" class in 43 we see that "decoration" is one of the concepts that is supplied by GPT3 for this class. Similarly, negative concepts like "trash", "gym clothes" and "spider" identified by IP-OMP are concepts whose presence would strongly indicate that the object in the image not a goldfish. Accordingly the linear classifier assigns negative weights to these concepts.
4. In Figure Dd. our model incorrectly predicts "Electric Guitar". The true class is "Acoustic Guitar". Inspecting the selected atoms and the weights of the classifier, it is clear that from the positive concepts-"a "a guitar case", "a small, handheld instrument", "music", and "equipment"; along with the negative concepts, one cannot distinguish between electric and an acoustic guitar. Indeed, the second most probable class in this case is "Acoustic Guitar". Note that although the image does not explicitly show "a guitar case", it is concept positively correlated with the object in the image and CLIP's latent space is such that text embeddings that are related to image content have high correlation with the image's 's embedding. Indeed, "a guitar case" is one of the concepts supplied by GPT3 for the class "Acoustic Guitar".
5. In Figure De. our model incorrectly predicts "Volcano". We see that the two most salient concepts according to the classifier (atoms to which the classifier assigns highest weight) are "eruption" and "a cone-shaped mountain", which are concepts a human would use to describe volcano. Other positive concepts recovered by IP-OMP include "aflame", "a white or light-colored body" (probably looking at the bright flame) and "made of lava and ash" (which is the concept attributed the third highest weight by the linear classifier).
E.2 Places365
For this dataset, we set T = 11, that is, the sparse code 3IPOMM for every image has support of size 11. A linear classifier trained on these sparse codes gets about 45.5% accuracy, which is within 3 points of what can be achieved if we run the IP-OMP algorithm long enough. This can be seen from Figure where the test accuracy vs. explanation length curve for Places365 saturates at about 48% accuracy for relatively large T (say T = 30). Results Figure TO
1. In Figure T0 our model correctly predicts "Crosswalk". We see that the two concepts assigned highest positive value in the sparse code by IP-OMP are "divided by lines or curbs" and "usually found near an airport". However the latter is not really discriminative for a crosswalk since they are found everywhere. and not necessarily at an airport. This is correctly reflected in the weights of the linear classifier, which assign much higher weight to the concept "divided by lines or curbs" but a relatively low (the lowest positive weight out of all the 11 concepts in the sparse code) to "usually found near an airport". Negative concepts like "extensive grounds and gardens", "a tile floor"", "often found on barns", and "found floating in the ocean" are strong indicators that the scene in the image is not of crosswalk.
2. In Figure L0p, our model correctly predicts "Wet Bar". Interestingly, the two most important concepts (largest classifier weights) are "cabinets and counter-tops" and "a dishwashing area". The main distinguishing feature between a dry bar and wet bar is that wet bar has a washing sink. Other positively identified concepts by IP-OMP are "brochures", "resort"" and "a protruding ledge of shelf". However, these are not discriminative for the class and are accordingly assigned low weights by the classifier. For instance, this could be an image of a wet bar in a resort, however wet bars are also present in places that are not a resort.
3. In Figure I0 our model correctly predicts "Baseball Field". The prediction is explained by the present of positive concepts like "an outfielder", "white bases at the corners" and "a cleat" (which is type of baseball shoe). IP-OMP also identifies "action" as a positive concept; however, that is very generic and is not specific to a baseball field. Accordingly, the linear classifier assigns the smallest positive weight to it. Like previous examples, many of the negative concepts in the sparse code strongly negatively correlated with baseball
27

---

field. These are "a producer", "a light, airy feel", "a large, flat expanse of snow", "cars being worked on". and "often found near a beach".
4. In Figure TOH. our model incorrectly predicts "Operating Room". The true label is "Clean Room" which is what an operating room is also called [22] Thus, we believe this is perfectly reasonable classification given the positive concepts extracted by the sparse code are present in the image and are salient features of operating room. These are namely "medical equipment", "a person working", "sterile surfaces", and "a prep area".
5. In FigureIo0 our model correctly predicts "Arena, Hockey". The positive concepts found by IP-OMP are "pucks", "pads", "a scorpion" (the Hanover Scorpions and the New Mexico Scorpions are hockey teams), "a Zamboni" (a machine used in ice skating rinks to clean the surface) and "state" (this is perhaps one concept whose reason for positive attribution in the sparse code and the classifier weights isn' 't clear).
E.3 CIFAR-10
For this dataset, we set 7 9, that is, the sparse code ÔIP-OMP for every image has support of size 9. A linear classifier trained on these sparse codes gets about 91.6% accuracy, which is within 2.4 points of what can be achieved if we run the IP-OMP algorithm long enough. This can be seen from Figure where the test accuracy vs. explanation length curve for CIFAR- 10 saturates at about 94% accuracy for relatively large (say т = 30). Results are provided in Figure IT Unlike ImageNet and Places365, the sparse code is noisier (incorrectly identified positive concepts) for this dataset and CIFAR-100 since these images are much lower resolution and hence out-of-distribution with respect to the distribution of natural images on which CLIP is trained. We do not describe the explanations for each image case-by-case as in the previous two datasets since they are all of the same nature as the previous two datasets. However, we mention some key points. In Figure IPp, IP-OMP assigns relatively large coefficient to the concept "a large size". However, frogs are typically considered small animals and this is reflected in the classifier weights which assigns the second lowest positive weight (after "reddish-brown coat") to it. In Figure Ii.. "antlers", which is a defining feature of a deer, is the most important positively attributed concept, both in the sparse code and in the classifier weights. Similarly, in the same figure, IP-OMP assigns a positive weight to "a halter" which is a headgear for animals like horses This is probably due to the fact that at such low resolution, the deer looks similar to a horse. However, the linear classifier assigns a relatively negligible weight to this concept indicating that it corrected for this noisy code provided by IP-OMP. Similarly, in Figure [i IP-OMP incorrects assigns a positive weight to "quadruped" which is clearly not what a truck is, but the classifier assigns negligible weight that concept, indicating that the "quadruped" concept is not used in its prediction for a "Truck", Finally, in Figure [e, the concept "a beetle" most likely refers to the car model which looks similar to the car displayed in the picture and not the insect.
E,4 CIFAR-100
OIP For this dataset, we set 7 9, that is, the sparse code Sip OMP for every image has support of size 11. A linear classifier trained on these sparse codes gets about 64% accuracy, which is within points of what can be achieved if we run the IP-OMP algorithm long enough. This can be seen from Figure 5 where the test accuracy vs. explanation length curve for CIFAR-100 saturates at about 71% accuracy for relatively large 7 (say T = 30). Results in Figure 12 As explained in $E.3 since the images in CIF are of a low resolution (blurry), the IP-OMP sparse codes sometimes make errors by assigning a positive coefficient to concept that is not related to the object in the image. For example, in Figure 12p "two large, compound eyes" are assigned a positive coefficient in the sparse code, which is unrelated the class "Forest". Notice the corresponding classifier assigns a negative weight to this concept. In Figure 12 IP-OMP assigns a positive weight to "baby possums" which is a negative concept for the label of the image, "Rose". Similarly, in Figure 12p. IP-OMP assigns a positive weight to concepts "greenish-browe concepts for label "Keyboard". The corresponding classifier assigns negative and negligibly (the smallest among all concepts in the sparse code) positive weight to them respectively, indicating they are not very important for the classifier's prediction of a Keyboard with 0.87 probability. Figure 12 illustrates an example in which the prediction is completely wrong. The correct label is "Cockroach". The classifier predicts a trout (which a type of fish) since the sparse code has a relativeily large positive weight on "aquatic animal", probably because the blue background looks similar to ocean
color" and "a small, narrow neck"; both are incorrect
28

---

at such low resolutions (the CIFAR-100 images are originally of 32 x 32 resolution, and then upscaled 224 224 resolution). We do not describe the explanations for each image case-by-case as in the previous two datasets since they are all of the same nature as discussed for Imagenet and Places365.
E.5
CUB-200
For this dataset, we set 10, that is, the sparse code 9PP-OMP for every image has support of size 10. A linear classifier trained on these sparse codes gets about 43% aceuracy, which within 32 points of what can be achieved if we run the IP-OMP algorithm long enough. More precisely, relatively large (say 155) required on this dataset to achieve an accuracy of about 75%, which the accuracy that is obtained if all the atoms in our dictionary were selected, and a linear classifier was trained on that sparse code (these sparse codes are not really sparse since their support size 208, the size of the dictionary).. Results in Figure 13 We do not describe the explanations for each image case-by-case as the previous two datasets since they are all of the same nature the previous two datasets. In Figure 13,, the correct prediction a "Yellow Breasted Chat" which visually looks very similar a chestnut-sided warbler, which is shown in Figure S). Both birds have a greenish-yelloo back, small, sparrow-like body, white body with gray wings, and black cap and white eyeline. As result, we conjecture that more concepts are needed to discriminate between the two.
Figure 8: A chestnut-sided warbler, which the incorrect class that CLIP-IP CLIP-IP-OMP pre- dicts for the yellow-breasted chat in Figure 13p.
E.6 Global Explanations for CLIP-IP-OMP
The examples provided so far were for explaining individual predictions made in terms of the coefficients of the sparse code and the corresponding weights of a linear classifier training on top of these sparse codes. In this subsection concepts used in predicting different classes by averaging over the sparse codes generated for that class. Specifically, we consider all test images belonging sparse codes for all these images. Consequently, we average over these sparse codes to get the mean coefficient for every atom (averaged over all test images belonging to that class). We show these results for three randomly chosen classes from the ImageNet dataset in Figure [4] We see that the top concepts (especially positive ones) for each class are salient features of the respective classes. For example, "Volcano"s are classified by "cone-shaped mountain", "geological phenomenon", "cruption", "crater", "aflame" and so on. "Peru" and "the Andes" are locations where several volcanic mountains are located. Similarly, the top positive concepts (in terms of their mean coefficient value) for "Tiger" is "striped fur", "prey animal", "savannah" (a habitat where tigers are found), "orange and white stripes" and "a fierce expression".
show that one get global understanding of the key
particular class, compute the 7-length
29

---

(a)
Input image
Sparse code 9IP-OMP after iterations
Weights linear classifier
shark tean
targe, whtte rounded head
powertul
paanets
marne animal
the head
Venu atont' comtiizienn
Signed magnitude of the weight
Prediction: Great White Shark with 0.76 probability
(b)
butlari
cel
white thist
thick gray ddn
-03
0.0
02
-10
Prediction: Snow Leopard with 0.87 probability
(c)
tank
spider
red or green color
otten decorative
aquarium
orange gym dathees
-6.2
0.0
0.2
Signed magritude weight
Prediction: Goldfish
0.84 probability
(d)
smmll, hundhell instrmmett
with
music
insemntt
abiso shalves fut toys
Value of atoms conffctent
Prediction: Electric Guitar with 0.16 probability
(e)
eruption
shaped
atlame
picoups
white light-colored body
a shapherd
made lave ash
0.2
0.0
0.2
10
Value of atom's coefficiont
Signed magnitude of the weight
Prediction: Volcano with 0.99 probability
Figure 9: Example runs from the ImageNet validation set. In each row, we display the test image in the first column, the dictionary atoms with non-zero coeficients in the sparse code along with the value of the coefficients in the second column, and finally the weights of the trained linear classifier in the third column. Below every image note the predicted class. The prediction probability reported obtained by taking softmax over the linear classifiers output. The colour scheme is as follows. In column 1, if the prediction is correct it is reported in green, if it is wrong it is reported in red. In column 2, green bars are for positive coefficients and red bars are for negative coefficients. In column we the same color for the bar in column 2. For example, if coefficient was positive, its corresponding weight in column 3 is shown in green regardless of whether the weight was positive or negative.
30

---

(a)
Input image x
Sparse code OIP.OMP after 11 iterations
Weights of linear classifier
dectors
sign with hote's flor
estensive grounds and gardang
ususly found near an siport
0.0 Value
to
Pradiction: Crosswalk with 0.69 probability
(b)
cablieess cars dishisshing
brochures
strwet
protruding edge ammunbion
Value of atomn's confiicent
magnitude
Prediction: Wet Bar
with 0.22 probability
(c)
action
aige, fist exparse of soom
sinding
otten found
diktren
-02
0.0
0.2
0.4
10
Signed magnituuee wogte
Prediction: Baseball Field with 0.47 probability
(d)
rallrdd cars passon peitee
2tor surfaces
toch sust brea
-0.5
0.75
magnitude
Prediction: Operating Room
with 0.71 probabiliyy
pucks
swmsurs
mushrooms
producer
player
5 Zamboni
bost
Value atom'ss coefficient
Signed magnitude weight
Prediction: Arena, Hockey with 0.36 probability
Figure 10: Example runs from the Places365 small validation set. Refer to Figure 9 for a description of the different columns in each row.
31

---

(a)
Input image x
Sparse code 91P- after 9 iterations
Weights of linear classifier
waterccet
large tu enggras
pointed front und
-10 Signed magnitude neggt
Prediction: Ship with 0.98 probability
Value atamn's coufficient
(b)
amphiblan reddishhboown cost
the ocean
machine
vertebrate
Value atamis comeiiic
Signod magritute of the weight
Prediction: Frog
with 0.99 probability
(c)
anters
reddish brown cost
feathers
-0.1
afatnn's coofficient
Signed magnitude the weight
Prediction: Deer
with 0.99 probabiltyy
bed carrying
aindiieed
night attendant
Hunter
quadruped
0.1 Value coefficient
Signed magnitude the weight
Prediction: Truck
with 0.97 probability
(e)
four bootl
spidee
steering wheel
captain
a toy
pasture
Value of aton'ss conffiiient
Signed magnitude of the weight
Prediction: Automobile with 0.98 probability
Example runs from the CIFAR-10 test set. Refer to Figure 9 for description of the different columns in each row.
Figure 11:
32

---

(a)
Input image x
Sparse code PPP after 9 iterations
Weights of linear classifier
bown rediish brown bark
wear mateup
desart animal
platform
trce Stndd
Valce atomis contiicintt
Signed
Pradiction: Forest with 0.35 probability
(b)
mane
towny yelmmsis
Screngeti
small simmy
large ze
seogulls
sharp
-0.2
0.0
0.2
10
Signed magnitude weight
Prediction: Lion
with 0.97 probability
(c)
stem with thoms
leteral symmetry tracks wheels garden equioment
-6.1
3.00
6.1
10
Signed magnitude the weight
Prediction: Rose with 0.58 probability
streets
long, tapened tall
Bhumb
b2ckk
wears
reddish lncomotive
Walue aton's confiicent
Signed magnitude the weight
Prediction: Trout
with 0.40 probability
(e)
OWERTY layout
meal
mouse ped
greanish brown color
open bed the back
5oft surface
0.0
Value of otomis cooffccott
Prediction: Keyboard with 0.87 probability
Example runs from the CIFAR-100 test set. Refer to Figure 9 for description of the different columns in each row.
Figure 12:
33

---

Input image
Sparse code AIP.OMP after 10 iterations
Weights of linear classifier
(a)
seabrr
gresidherreen head
black with tip
webbod
thrme each
yelloeess
alemme
browrrhh bock
Value atorm coefiiient
Signed magnitude the weight
Prediction: Black Footed Albatross with 0.45 probability
(b)
greerish-jellioe back
large, orange bill
large,
small spartss like budy
white body
White body with gray wings
black cap and white "syelime"
-2. Value of aton'ss coefficiett
0.2
-5
Prediction: Chestnut Sided Warbler with 0.5 probability
(c)
small sparooe-iiee ti body
readish oroan back
rutous freo ceec color
crange throal
whibe portee
Value atoer comfliciene
Prediction: Chuck Will Widow with 0.12 probability
(d)
graytsh brock spador-
meduumaleed
cart stun-llckk bealy face:
small thruch bird
dark brown or black color gloss
-02
0.0
Prediction: Gadwall with 0.96 probability
large, black solben
white breash
black wingham
dark bus io ack uppier body
-0.
0.7 magiviutte
Prediction: Blue Jay with 0.93 probability
Figure 13: Example runs from the CUB-200 test set. Refer to Figure for a description of the different columns in each row.
34

---

Class: Volcano
Class: Tiger
Teru
somy apaesnace
bocteed namati, erom-
Spromna erange
Iren Austella
flnce espresdon
Bock-add white a mether and baby
riberruurpen burppers the compos
protective
lage roctanguaal Tune
large powerfu jon
-0.8
0.05
0.30
8.5
0.0
015
-0.10
-0.03
0.00
0.55
aic
015
Wi'e atoen's conficintt
Class: Acoustic Guitar
gutarcas
light potte centert
may have decorative ebewet
sound hele
unadly cystola
-0.66
-0.09
-0.09
0.00
0.8
Value
Figure 14: Top 15 concepts identified by CLIP-IP-OMP for different classes from the Imagenet dataset. Each bar shows the average value of coefficients for that concept, averaged over all test images from the same class.
35


Reviews:
[{"review_id": "3BhgDUIKiQ", "reviewer": "Reviewer_FGVf", "summary": "The submitted paper proposes information pursuit based orthogonal matching pursuit (IP-OMP) as an explainable classifier for visual classification tasks. IP-OMP is equivalent to conventional OMP with the exception of the normalization. Roughly speaking, IP-OMP uses the standard inner (dot) product $\\tilde{a}^{T}\\tilde{b}$ after the L2-norm normalization $\\tilde{a}=a/\\|a\\|$ and $\\tilde{b}=b/\\|b\\|$ while OMP only uses the standard inner product $a^{T}b$. The overall operation is not an inner product since it does not have the linearity, i.e. $\\tilde{a}^{T}\\tilde{b}\\neq \\tilde{c}^{T}\\tilde{b} + \\tilde{d}^{T}\\tilde{b}$ for $a=c + d$. In this sense, IP-OMP is not a special case of OMP on another inner product space. IP-OMP is derived as a special case of IP, as proved in Theorem 1. The submitted paper follows [37] to utilize CLIP [17] in generating a dictionary for visual classification tasks, so that the proposed algorithm is called CLIP-IP-OMP. Numerical experiments show that CLIP-IP-OMP outperforms V-IP [15] and Lf-CBM [37] in terms of the accuracy in classification for some cases. ", "questions": "--A typo in Theorem 1\n\n$d_i$ in Theorem 1 should have the superscript, i.e. $d^i$. \n\n--page 8, line 319\n\nIs not Figure 4.2 a typo of Figure 3?\n\n--Filtering inappropriate queries\n\nWhy do not the authors consider an option to remove inappropriate queries as pre-processing for using CLIP-IP-OMP?", "limitations": "No problems. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "--Originality\n\nThe submitted paper proposes a novel derivation of IP-OMP (i.e. Theorem 1), which is formulated as a special case of IP. While the proof itself is based on elementary techniques in projection and Gaussian estimation, the proposed formulation of IP is not trivial.  \n\n--Quality\n\nThe proof is probably correct while I did not check detailed computation in Gaussian estimation or projection. At least the main idea to connect IP with OMP is good.  \n\n--Clarity\n\nThe manuscript is well written and presents a nice review of the background on IP and OMP.  \n\n--Significance\n\nThe submitted paper reveals the relationship between IP and OMP for applying an OMP-type greedy algorithm to explainable classification. ", "weaknesses": "My main concern is that CLIP-IP-OMP is questionable as explainable AI: CLIP-IP-OMP is a greedy algorithm selecting inappropriate queries from a human point of view. For instance, Fig. 3 shows that CLIP-IP-OMP selects \"a salty flavor\", \"a witch,\" \"baby birds,\" and \"a strap on the side\" to classify a tiger. In my opinion, nobody selects such inappropriate queries to identify a tiger. Numerical experiments seem to show that the selection of such inappropriate queries is a general phenomenon in CLIP-IP-OMP. \n\nThe authors claim that such inappropriate queries have negative coefficients (elements of $\\hat{\\beta}$). The observation itself is supported by numerical evidence. However, if they intend to claim that the negative coefficients indicate inappropriate queries, I disagree with such a leap in logic. From the formulation of the sparse code, inappropriate queries should have coefficients with small magnitude (ideally zero). The sign of the coefficients should not have any meaning unless CLIP encodes an inappropriate query into $-a$ when an appropriate query is mapped into a vector (atom of the dictionary) $a$. It is of course impossible for CLIP to perform such encoding because CLIP does not know the input image \"tiger\", which determines whether a query is appropriate or not.  \n\nIn my understanding, the selection of inappropriate queries is an inevitable phenomenon in greedy algorithms, which have no options to discard inappropriate queries selected in early iterations. It is not fair to compare exlainable AIs only in terms of the accuracy in classification, as considered in the submitted paper. It might be possible to improve the accuracy by adding uninterpretable queries (for instance, conventional AI achieves a higher accuracy than humans by utilizing uninterpretable wieghts in a neural network), so that it is possible to compare exlainable AIs in terms of the accuracy only when they do not use inappropriate queries. V-IP [15] and Lf-CBM [37] seem to be in this case. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. Following are our responses to each individual comment (which are highlighted in italics).\n\n> *My main concern is that CLIP-IP-OMP is questionable as explainable AI: CLIP-IP-OMP is a greedy algorithm selecting inappropriate queries from a human point of view. For instance, Fig. 3 shows that CLIP-IP-OMP selects \"a salty flavor\", \"a witch,\" \"baby birds,\" and \"a strap on the side\" to classify a tiger.*\n\nWe disagree that queries that are not present in an image, like \"baby birds\" or \"a witch\" which are not present in the image of a tiger in Fig. 3a, are inappropriate. Absence of concepts can provide discriminatory information for classification. The explainability of our classification algorithm is that of a linear model trained on interpretable features. In our algorithm, each feature corresponds to a semantic concept (like \"striped fur\") and is thus interpretable. The contribution of a feature to the prediction can be explained by the linear classifier's weight for that feature and the feature's value (the coefficients of the sparse code in this context). This is exactly what is shown in Fig. 3a, features like \"a black and white striped fur\" have an overall positive contribution to the score for class \"Tiger\" since both the feature value and the corresponding weight is positive. Similarly, concepts which are anti-correlated with the image content like \"a witch\" also affect the final prediction score positively since both their feature value and the corresponding weight are negative. This has been discussed in L324-334 in the main paper, and we would modify the writing to emphasize more on this point.\n\n> *The authors claim that such inappropriate queries have negative coefficients (elements of $\\hat{\\beta}$). The observation itself is supported by numerical evidence. However, if they intend to claim that the negative coefficients indicate inappropriate queries, I disagree with such a leap in logic. From the formulation of the sparse code, inappropriate queries should have coefficients with small magnitude (ideally zero). The sign of the coefficients should not have any meaning unless CLIP encodes an inappropriate query into \n$-a$ when an appropriate query is mapped into a vector (atom of the dictionary) $a$. It is of course impossible for CLIP to perform such encoding because CLIP does not know the input image \"tiger\", which determines whether a query is appropriate or not.*\n\nWe disagree with the reviewer. We would like to clarify that we never claim inappropriate queries have negative coefficients. We make the claim that concepts that are assigned negative coefficients in the sparse code by IP-OMP are concepts that are not found in the image. This claim stems from CLIP's training objective which is a contrastive loss that optimizes image and text representations such that if the text aligns with the contents of the image, the normalized dot product between their corresponding representations is maximized (pushed closer to $1$). Similarly, if the given text does not correspond to the image content, the normalized dot product between their corresponding representations is minimized (pushed closer to $-1$). From this perspective, we believe that it is reasonable to expect that if CLIP encodes a text concept (say \"a witch\") as $a$ and if the image content can be described well by the concept then its representation $x$ would have a high dot product with $a$ and if the concept does not describe the content of an image, it would have a low dot product with $x$ (the lowest being $-1$). This is our rationale for assigning meaning to the coefficients in the sparse code, where the sign indicates correlation (positive or negative) of the image content with the concept and magnitude indicates strength of that correlation.\n\n> *It is not fair to compare exlainable AIs only in terms of the accuracy in classification, as considered in the submitted paper, so that it is possible to compare exlainable AIs in terms of the accuracy only when they do not use inappropriate queries. V-IP [15] and Lf-CBM [37] seem to be in this case. In my understanding, the selection of inappropriate queries is an inevitable phenomenon in greedy algorithms, which have no options to discard inappropriate queries selected in early iterations.*\n\nThis is incorrect. We compare explainable AI algorithms via their tradeoff between description length (the number of concepts used in prediction) vs. the accuracy obtained. The description length is a measure of explainability since a long list of concepts would make the predictions less intelligible. If two algorithms have the same average description length we consider them to be equally well explainable since, in our opinion, there is no well-defined metric for ascertaining one explanation to be better than another (when they are based on the same set of interpretable features) beyond its description length. Moreover, we do not agree that the selection of negative queries/concepts (which the reviewer refers to as inappropriate queries) is inappropriate as argued in previous comments.\n\n> *$d_i$ in Theorem 1 should be $d^i$.*\n\nThis is not a typo. We use superscripts to indicate column indices within the dictionary matrix, while subscripts indicate the order these atoms are chosen in IP-OMP. So, $d_i$ is the atom selected in iteration $i$, whereas $d^i$ refers to the $i^{th}$ column of the dictionary. This distinction is first made in footnote 1 (and also on L143-144 and L205-206) of the paper.\n\n> *Is Fig. 4.2 a typo of Fig. 3?*\n\nYes, sorry for the typo; this should be Fig. 3.\n\n> *Why do not the authors consider an option to remove inappropriate queries as pre-processing for using CLIP-IP-OMP?*\n\nAs argued in previous responses, we do not agree with the reviewer that the negative concepts selected by our method are inappropriate."}, {"review_id": "43OqcDXI7G", "reviewer": "Reviewer_osjG", "summary": "This paper analyzes IP in active testing and OMP in sparse signal processing, and establishes connections between the two algorithms. Specifically, IP with a specific configuration can be reduced to OMP up to a normalization, called IP-OMP, and has similar performances as OMP. The paper also proposes to use the IP-OMP algorithm to reduce the computational complexity of IP, and demonstrates its efficiency improvement over variational IP in explainable visual classification,", "questions": "Please see Weaknesses above", "limitations": "The authors addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Provides a novel perspective for bridging two existing techniques in different domains. \n- Analysis is sound and creative.\n- The presentation of the paper is very clear.", "weaknesses": "- As the authors acknowledged, the proposed IP-OMP is limited by the need to place signals and queries into the same domain, which is an intrinsic limitation of the proposed method.\n- It would be interesting to see the performance of the proposed IP-OMP on same-modality query problems, such as words-only or images-only, which can eliminate the CLIP module and better demonstrate the performance of IP-OMP itself.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. Following are our responses to each individual comment (which are highlighted in italics). \n\n> *As the authors acknowledged, the proposed IP-OMP is limited by the need to place signals and queries into the same domain, which is an intrinsic limitation of the proposed method.*\n\nWe agree with the reviewer that this is a limitation of IP-OMP, but emphasize that multimodal models like CLIP allow bridging signal and query domains.\n\n> *It would be interesting to see the performance of the proposed IP-OMP on same-modality query problems, such as words-only or images-only, which can eliminate the CLIP module and better demonstrate the performance of IP-OMP itself.*\n \nThank you for this suggestion. We would definitely explore this in future work.\n"}, {"review_id": "361zbA4y6k", "reviewer": "Reviewer_VN2v", "summary": "The paper explores the connection between the information pursuit (IP) approach for active testing and the orthogonal matching pursuit (OMP) algorithm for sparse approximation. By including a normalization step in OMP and posing a statistical model for the queries made in OMP during each algorithm iteration (e.g., projections), OMP can be motivated as an instance of IP. The paper also considers the application of OMP in explainable AI, where semantic attributes and images are embedded into a joint space via the popular CLIP embedding, and the image decomposition via OMP with an attribute dictionary is used as a feature for explainable supervised learning.", "questions": "I wonder whether there is a way to establish a stronger connection by linking two vector spaces, one for each setting. For example, could the IP framework be specialized to RVs that live in a vector space, such as Gaussians?\n\nLine 52: what are \"the true optimal solutions\" in each case? It is clear for OMP since one is assuming that a single sparse approximation of the signal exists, but it is less clear in the IP case.\n\nEquation 2 is missing \"beta hat = arg\".\n\nWhile OMP is an approximation to (2), is IP an approximation? Or is it approximated?\n\nIn the second line of IP-OMP, can the second argmax be written as going over the set $D\\D_k$?\n\nIn line 252, how small does the normalized error need to be for exact recovery? E.g., $10^{-2}$, $10^{-3}$?\n\nIn Section 4.1, can the authors provide more information about the linear classifier? How many classes involved? What images are used for training and testing? Are the inputs always the sparse approximation obtained from OMP for the particular image? How is the OMP dictionary built?\n\nIn line 319, the reference to Figure 4.2 is incorrect.\n\nIn line 414, why is the variance independent of the values that $Q_j$ takes?\n\nIn lines 455-456, should P be $P_k$?", "limitations": "Limitations are considered in Section 5.\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The presentation for both methods is clear and the framework that draws connections between them is also clearly stated.\n\nThe statistical framework for OMP provides a reading of its steps that matches IP once normalization is added. This is not a significant change, as many practical implementations of OMP perform column normalization for the sake of simplicity. Note that the subspace identified by OMP is not affected by the norms of the columns that span it. \n\nThe clever application of OMP with CLIP embeddings of semantic concepts opens some interesting questions, in particular whether CLIP embeddings feature a structure similar to that of sparse signals (e.g., concentrated as a union of low-dimensional subspaces).\n", "weaknesses": "The setting of the two algorithms is fairly different, and the mismatch between these settings makes the feasibility of the relationship suffer a bit. In IP, target and query random variables are defined, and mutual information and conditional MI are used to select new queries in a series. In contrast, OMP relies on concepts from vector spaces and high dimensional geometry to estimate components of a decomposition of a signal vector, essentially assuming that the signal of interest is contained within a K-dimensional subspace of the signal's ambient space. \n\nWhile the normalization added does not change the solution of the problem for exactly sparse signals, there are other considerations regarding noise and approximate sparsity, but those do not appear to be considered in the manuscript. In other words, the study of OMP is limited to exactly sparse signals without noise added.\n\nIt is not clear what new insights are brought out by the proposed connection. OMP is a well studied algorithm that has been in the literature for close to 30 years, and column normalization is a standard additional step when applied in practice. Is there any new insight to IP that can be obtained from this connection?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. Following are our responses to each individual comment (which are highlighted in italics). \n\n> *The setting of the two algorithms is fairly different, and the mismatch between these settings makes the feasibility of the relationship suffer a bit. In IP, target and query random variables are defined, and mutual information and conditional MI are used to select new queries in a series. In contrast, OMP relies on concepts from vector spaces and high dimensional geometry to estimate components of a decomposition of a signal vector, essentially assuming that the signal of interest is contained within a K-dimensional subspace of the signal's ambient space.*\n\nWe agree with the reviewer that the two algorithms seem to be fairly different in their settings. However, it is not clear why the reviewer feels this makes the feasibility of the relationship between the two algorithms suffer since we theoretically show in this paper that with a specific choice of query and target random variables, it is possible to recover the OMP algorithm (up to a normalization factor) via the IP algorithm. Furthermore, we show both theoretically and empirically (via synthetic experiments) that this normalization factor does not matter for exact recovery of the sparse signal (in the case of no measurement noise).\n\n> *While the normalization added does not change the solution of the problem for exactly sparse signals, there are other considerations regarding noise and approximate sparsity, but those do not appear to be considered in the manuscript. In other words, the study of OMP is limited to exactly sparse signals without noise added.*\n\nPlease refer to the response to Reviewer tdY5 for our reply to this comment, since both reviewers had the same criticism.\n\n> *It is not clear what new insights are brought out by the proposed connection. OMP is a well studied algorithm that has been in the literature for close to 30 years, and column normalization is a standard additional step when applied in practice. Is there any new insight to IP that can be obtained from this connection?*\n\nFirst, we would like to clarify that at any iteration $k+1$, the column normalized implementation of OMP divides the objective in Eq 4 by $\\\\|d^j\\\\|$ (for atom $d^j$), whereas IP-OMP divides the same objective by $\\\\|\\Pi_{D_k}^\\perp d^j\\\\|$ (as evidenced by Eq. IP-OMP). This could result in different atom selections by the two algorithms in any particular iteration.\n\nSecond, the connection established between IP and OMP opens the door to applying ideas from compressed sensing and sparse signal processing to applications where IP is widely used. This is computationally alluring since OMP is a much simpler algorithm involving vector dot products than IP which requires estimating mutual information in high dimensions (a daunting task). One concrete application in our paper is an explainable AI algorithm for image classification called, CLIP-IP-OMP (see L96-113 in the main paper for more details). \n\n> *I wonder whether there is a way to establish a stronger connection by linking two vector spaces, one for each setting. For example, could the IP framework be specialized to RVs that live in a vector space, such as Gaussians?*\n\nGreat question! Yes, the IP framework can be specialized where the target is a Gaussian vector and queries are also Gaussian random vectors correlated with the target. However, it is not clear that this would not result in a stronger connection with OMP since the first query in IP always depends on the joint distribution of the target and query answers (and not the observed signal $x$) whereas the first atom selected by OMP depends on $x$. A similar discussion can be found in L160-176 in the paper. \n\n> *L52: what is \"the true optimal solutions\" for IP? While OMP is an approximation to (2), is IP an approximation? Or is it approximated?*\n\nThank you for this question. IP is a greedy approximation to the optimal strategy (the true optimal solution) that minimizes the average number of queries needed to predict $Y$ with a given level of confidence. This has been mentioned in L128-131 of the main paper. However, the reviewer's comment suggests that this clarification should be made prior in the Introduction (before L52) and we will make this change.\n\n> *Eq 2 is missing \"beta hat = arg\".*\n\nWe disagree since Eq 2 states the optimization problem that is solved for recovering the sparse code whereas \"beta hat = arg\" seems to be referring to the minimizer of the same optimization problem.\n\n> *In the second line of IP-OMP, can the second argmax be written as going over the set $D\\D_k$?*\n\nYes, they are equivalent and it's a matter of taste. \n\n> *In L252, how small does the normalized error need to be for exact recovery?*\n\nWe used a threshold of $10^{-14}$ (See Appendix L543).\n\n> *In Section 4.1, can the authors provide more information about the linear classifier?* \n\nWe perform our experiments on 5 standard image classification datasets (L312-314) namely: Imagenet, Places365, Cifar-{10,100} and CUB-200. All these datasets come with standard train and test splits which were used for training and testing, respectively. The number of classes for the linear classifier depends on the dataset, for e.g., Imagenet has 1000 classes. Inputs to the classifier are always IP-OMP's sparse code for a particular image (L294-296). Details of the OMP dict. can be found in Appendix L613-646 and further training details can be found in Appendix L648-664. \n\n> *In L319, the reference to Fig. 4.2 is incorrect.* \n\nWe apologize for the typo; this should be Fig. 3. \n\n> *In L414, why is the variance independent of the values that $Q_j$ takes?*\n\nThis is a property of conditioning in jointly Gaussian variables. If $X$ and $Y$ are jointly Gaussian, the conditional variance of $X$ given $Y=y$ depends only on $Cov(X,Y), Var(X)$ & $Var(Y)$.\n\n> *In L455-456, should P be $P_k$?* \n\nYes, we apologize for this typo."}, {"review_id": "zE9XBkDMea", "reviewer": "Reviewer_tdY5", "summary": "This paper establishes an intriguing connection between the novel method of Information Pursuit and the well-known approach of Orthogonal Matching Pursuit, foremost used in Compressed Sensing. It then uses this connection for a novel approach to explainability, namely to introduce an approach for visual classification based on queries which is then automatically interpretable. Numerical experiments show the applicabiliy of the approach. ", "questions": "I don't have any specific questions.", "limitations": "I would like to refer to the weaknesses, which are all points, which to my mind need to be addressed and improved.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* Explainability is an extremely relevant topic.\n* The connection between IP and OMP is itself very interesting and revealing.\n* The novel explainability approach is elegant and supported by theoretical foundations.\n* The numerical experiments are well-thought-through and professionally set up. ", "weaknesses": "* I am missing an extensive noise treatment, such as when comparing IP with OMP. Right now the original signal seems to be considered a clean signal. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. Following are our responses to each individual comment (which are highlighted in italics).\n\n> *I am missing an extensive noise treatment, such as when comparing IP with OMP. Right now the original signal seems to be considered a clean signal.*\n\nThank you for this suggestion. In response to this criticism (Reviewer VN2v also had the same critique) we have carried out synthetic experiments for the noisy case when the true signal is corrupted by Gaussian noise. Please see the PDF attached to the global response for the results for different Signal-to-Noise Ratio (SNR) values. Moreover, the addition of noise does not change the joint Gaussianity of the query and target random variables defined in L182-185 of the main paper. This joint Gaussianity is used in the proof of Theorem 1, which states the equivalence between OMP and IP-OMP (up to a normalization factor). Therefore this result still holds for the corrupted signal.\n\n**Experiment details:** Recall that in the paper we simulated random dictionaries $D \\in \\mathbb{R}^{m \\times n}$ and $s$-sparse codes $\\beta \\in \\mathbb{R}^n$, which generated signals $x$ according to $x = D\\beta.$ We extended this setup to the measurement model $x = D\\beta + e$, where $e$ is independent Gaussian noise, $D$ is chosen with independent uniform spherical columns, and $\\beta$ is generated according to the Gaussian nonzero entry setup described in Appendix B. For each of the $(m, n, s)$-settings of our original noiseless experiments, we simulated noisy measurements with expected SNR values of 5, 10, 15, and 20 dB, where the expected SNR is defined as \n$$\n\\mathbb{E}[\\mathrm{SNR}] = \\mathbb{E}_{D,\\beta,e} \\left[\\frac{\\\\|D\\beta\\\\|_2^2}{\\\\|e\\\\|_2^2}\\right].\n$$\nFor each trial (draw of $D$, $\\beta$, and $e$), we ran OMP and IP-OMP for $s$ iterations each, as in the noiseless experiment. The estimation performance of the two algorithms is reported through plots in the accompanying PDF which effectively show that the equivalence between OMP and IP-OMP is maintained under different levels of measurement noise."}]

Author rebuttal:
We thank all the reviewers for their time and insightful comments which have helped improve our paper. We are elated that the reviewers found our paper well-written, the presentation clear and our connection between IP and OMP as original, creative and revealing. We are pleased that the reviewers found our application of IP-OMP to explainable AI for image classification using CLIP embeddings as interesting, novel and extremely relevant. Following are some of the main critiques, afterwards we address each reviewer's comments individually.

1. Reviewer FGVf had concerns over the explainability of our proposed CLIP-IP-OMP algorithm. We believe we have addressed these concerns in our detailed response to the reviewer and would incorporate a part of this discussion into our paper.

2. Reviewer osjG provided interesting suggestions for applying our algorithm to scenarios where query and signal domains are the same, such as words-only or images-only. We would certainly explore this direction in future investigations into the IP-OMP algorithm. 

3. Reviewer VN2v had concerns about the disparate settings of the two algorithms, namely IP deals with random variables and uses mutual information to select the next query, whereas OMP relies on concepts from vector spaces and high dimensional geometry. We believe that this disparity makes our contribution, which shows that OMP can be derived from IP by a specific choice of query and target random variables, all the more surprising and exciting.

4. Reviewer tdY5 and VN2v were missing a thorough treatment of noise in the observed signal (measurements). In response to this, we have conducted synthetic experiments at different noise levels, number of measurements, number of dictionary atoms, and sparsity levels of the signal. In all experiments, we see the performance of IP-OMP and OMP to be almost the same, indicating that the equivalence between the two algorithms is also preserved under noise. These results would be added to the appendix of the paper.






Meta-review: The paper draws connections between Information Pursuit, a somewhat complex greedy algorithm recently used in producing explainable classification decisions, and Orthogonal Matching Pursuit, a classical greedy algorithm for sparse approximation. The paper shows that OMP can be seen as a particular case of IP, in which the ``questions’’ greedily selected by IP correspond to atoms in a dictionary. Based on this, the paper proposes OMP as a computationally efficient alternative to IP, and demonstrates promising results on explainable visual classification. Reviewers found the paper to be technically solid and clearly written, with new insights into greedy algorithms, and promising results on visual classification. After some discussion around the notion of explainability offered by the paper (and its limitations), reviewers converged to a recommendation to accept the paper.
Decision: Accept (spotlight)