Variational Information Pursuit for Interpretable Predictions
Authors: Aditya Chattopadhyay
Kwan Ho Ryan Chan
Benjamin David Haeffele
Donald Geman
Rene Vidal
Venue: ICLR 2023 poster (2023)
Keywords: Interpretable ML
Explainable AI
Information Pursuit

Abstract: There is a growing interest in the machine learning community in developing predictive algorithms that are interpretable by design. To this end, recent work proposes to sequentially ask interpretable queries about data until a high confidence prediction can be made based on the answers obtained (the history). To promote short query-answer chains, a greedy procedure called Information Pursuit (IP) is used, which adaptively chooses queries in order of information gain. Generative models are employed to learn the distribution of query-answers and labels, which is in turn used to estimate the most informative query. However, learning and inference with a full generative model of the data is often intractable for complex tasks. In this work, we propose Variational Information Pursuit (V-IP), a variational characterization of IP which bypasses the need to learn generative models. V-IP is based on finding a query selection strategy and a classifier that minimize the expected cross-entropy between true and predicted labels. We prove that the IP strategy is the optimal solution to this problem. Therefore, instead of learning generative models, we can use our optimal strategy to directly pick the most informative query given any history. We then develop a practical algorithm by defining a finite-dimensional parameterization of our strategy and classifier using deep networks and train them end-to-end using our objective. Empirically, V-IP is 10-100x faster than IP on different Vision and NLP tasks with competitive performance. Moreover, V-IP finds much shorter query chains when compared to reinforcement learning which is typically used in sequential-decision-making problems. Finally, we demonstrate the utility of V-IP on challenging tasks like medical diagnosis where the performance is far superior to the generative modeling approach.

Published as a conference paper at ICLR 2023
VARIATIONAL INFORMATION PURSUIT FOR INTERPRETABLE PREDICTIONS
Aditya Chattopadhyay, Kwan Ho Ryan Chan, Benjamin D. Haeffele, Donald Geman
Johns Hopkins University. USA, (achattol, kchan49, bhaeffele, geman jhu. edu
René Vidal
University of Pennsylvania, USA, vidalreseas upenn.
ABSTRACT
There a growing interest in the machine learning community in developing pre- dictive algorithms that are interpretable by design. To this end, recent work pro- poses to sequentially ask interpretable queries about data until a high confidence prediction can be made based on the answers obtained (the history). To promote short query-answer chains, a greedy procedure called Information Pursuit (IP) is used, which adaptively chooses queries in order of information gain. Generative models are employed to learn the distribution of query-answers and labels, which is turn used estimate the most informative query. However, learning and in- ference with a full generative model of the data is often intractable for complex tasks. In this work, we propose Variational Information Pursuit (V-IP), varia- tional characterization of IP which bypasses the need to learn generative models. V-IP is based on finding a query selection strategy and a classifier that minimize the expected cross-entropy between true and predicted labels. We prove that the strategy is the optimal solution to this problem. Therefore, instead of learning optimal strategy to directly pick the most infor-
generative models, mative query given any history. We then develop a practical algorithm by defining finite-dimensional parameterization of our strategy and classifier using deep net- works and train them end-to-end using our objective. Empirically, V-IP is 10-100x faster than IP on different Vision and NLP tasks with competitive performance. Moreover, V-IP finds much shorter query chains when compared to reinforcement learning which is typically used in ioquential-decisiio--mkkke we demonstrate the utility of V-IP on challenging tasks like medical diagnosis where the performance far superior the generative modeling approach.
problems. Finally,
INTRODUCTION
Suppose a doctor diagnoses a patient with a particular disease. One would want to know not only the disease but also evidential explanation of the diagnosis in terms of clinical test results, physi- ological data, or symptoms experienced by the patient. For practical applications, machine learning methods require emphasis only on metrics such as generalization and scalability but also on criteria such as interpretability and transparency. With the advent of deep learning methods over traditionally interpretable methods such as decision trees or logistic regression, the ability to perform complex tasks such as large-scale image classification now often implies a sacrifice in in- terpretability. However, interpretability is important in unveiling potential biases for users with different backgrounds Yu 2018) or gaining users' trust.
Most of the prominent work in machine learning that addresses this question of interpretability is
based on post hoc analysis of a trained deep network's 's decisions (Simonyan et al. 2013 Ribeiro
al. 2016 (Shrikumar et 2017 iZeiler Fergus 2014; Selvaraju et al., 2017]: Smilkov et al.
2017
Chattopadhyay et al.) 2019 Lundberg & Lee 2017 These methods typically assign im-
portance scores to different features used in a model's decision by measuring the sensitivity of the model output to these features. However, explanations in terms of importance scores of raw features might not always be as desirable as a description of the reasoning process behind a model's deci- sion. Moreover, there rarely any guarantees for the reliability of these post hoc explanations to faithfully represent the model's 's decision-makin process (Koh et al. 2020). Consequently, post hoc interpretability has been widely criticized (Adebayo et al. 2018 Kindermans et al. 2019 Rudin

---

Published as a conference paper at ICLR 2023
2019 Slack et al., 2020; Shah al. 2021 Yang & Kim 2019) and there is need to shift towards
ML a algorithms that are interpretable by design.
An interesting framework for making interpretable predic- tions was recently introduced by Chattopadhyay et al. (2022). The authors propose the concept of an interpretable query set Q, a set of user-defined and task- specific functions q X + A. which map data point X' to an answer in A, each having clear interpretation to the end- user. For instance, plausible query set for identifying bird species might involve querying beak shape, head colour, and other visual attributes of birds. Given a query set, their method sequentially asks queries about X until the answers obtained are sufficient for predicting the label/hypothesss Y with high confidence. Notably, as the final prediction is solely a function of this sequence of query-answer pairs, these pairs provide a complete explanation for the prediction. Figure illustrates the framework on bird classification task.
sequence of Interoretable queries
Input Image gofe
about given image an!:;
01: Has an all- purpose bill shape?
Yes.
Hos white colorod belly?
Has solid breast pattern?
No.
Prediction:
V6: Has yellow colored breast?
No.
with 95%
Os. Hās rounded wing shape?
No.
confidence
black colored bill?
Yes.
Has black color log?
No.
gr- Hes grop-talared leg?
Yes.
Figure I: Illustration of the framework on a bird classification task. The query consists of questions about the presence absence of dif- ferent visual attributes of birds. Given an image _0' sequence of interpretable queries is asked about the image until a prediction can be made with high confidence. The choice of each query depends on the query-ans answers observed so far.
To obtain short explanations (short query-answer chains), the authors propose to use a greedy pro- cedure called Information Pursuit (IP), which was first introduced in Geman & Jedynak] (1996). Given any imput =h IP sequentially chooses the query which has the largest mutual information about the label/hyyothesii Y given the history query-answers obtained so far. To compute this mutual information criteria, generative model is first trained to learn the joint distribution between all query-answers ((X) and Y; in particular, Variational Autoencoders (VAEs) (Kingma & Welling 2013) are employed. This learnt VAE is then used to construct Markov Chain Monte Carlo (MCMC) estimates for mutual information via MCMC sampling. Unfortunately, the computational costs of MCMC sampling coupled with the challenges of learning accurate generative models that enable fast inference limit the application of this framework to simple tasks. As an example, classifying MNIST digits using 3 overlapping patches as querieq] with this approach would take weeks!
In this paper, we question the need to learn a full generative model hetween all query-answers g(X) and Y given that each iteration IP is only interested in finding the most informative query given the history. More specifically, we present a variational charatcrization of IP which is based on the observation that, given any history, the query q", whose answer minimizes the KL-divergence between the label distribution P(Y X) and the posterior P(Y 1 (X),, history), will be the most informative query as required by IP. As result, we propose to minimize this KL-divergence term in expectation (over randomization of histories) by optimizing over querier functions, which pick query from Q given history, parameterized by deep networks. The optimal querier would then learn to directly pick the most informative query given any history, thus bypassing the need for explicitly computing mutual information using generative models. Through extensive experiments, we show that the proposed method is not only faster (since MCMC sampling methods are no longer needed for inference). but also achieves competitive performance when compared with the generative modeling approach and also outperforms other state-of-the -heetrrt sequential-decinn wew.ddonn methods.
Paper Contributions. (1) We present a variational characterization of IP, termed Variational-IP or V-IP, and show that the solution to the V-IP objective is exactly the IP strategy. (2) We present practical algorithm for optimizing this objective using deep networks. (3) Empirically, we show that V-IP achieves competitive performance with the generative modelling approach on various computer vision and NLP tasks with a much faster inference time. (4) Finally, we also compare our approach Reinforcement Learning (RL) approaches used in sequential-deciise
making areas like Hard Attention Mnih et al.) 2014) and Symptom Checking (Peng et al.) 2018). where the objective is to learn a policy which adaptively chooses a fixed number of queries, one at a time, such that an accurate prediction can be made. In all experiments, V-IP is superior to RL methods.
Fach patch query asks about the pixel intensities observed in that patch for de
2

---

Published as a conference paper at ICLR 2023
2 RELATED WORK
Interpretability in Machine Learning. These works can be broadly classified into two main cat- egories: (i) post-hoc interpretability, and (ii) algorithms that are interpretable by design. A large number of papers in this area are devoted to post-hoc interpretability. However, as stated in the In- troduction, the reliability of these methods have recently been called into question (Adebayo et al.
Yang& & Kim, 2019; Kindermans et al. 2019 [Shah et al. [021] Slack et al. [0200] Rudin 2019 Koh et al.] | [Subramanya al. (2019). Consequently, recent works have focused on de- veloping ML algorithms that are interpretable by design. Several of these works aim at learning deep networks via regularization such that it can be approximated by decision tree (Wu et al., 2021] or locally by a linear network (Bohle et al. |021] Alvarez Melis & Jaakkola 2018). However, the framework of "Chattopadhyay et al. (2022) produces predictions that are completely explained by interpretable query-chains and is not merely approximation to an interpretable model like de- cision trees. Another line of work tries to learn latent semantic concepts or prototypes from data and subsequently base the final prediction on these learnt concepts (Sarkar et al. 2022 Nauta et al. 2021 Donnelly et al., 2022 Li et al.) 2018 Yeh et al. 2020). However, there is no guarantee that these learnt concepts would be interpretable to the
2018
align with the user's 's requirement. In sharp contrast, allowing the user to define an interpretable query set in (Chattopadhyay et al. 2022) guarantees by construction that the resulting query-chain explanations would be interpretable and useful.
Sequential Decision-Making, An alternative approach to learning short query-chains is use methods for sequential decision learning. These algorithms can be used for making interpretable de- cisions by sequentially deciding "what to query next?" in order to predict Y as quickly as possible. Mnih et al. (2014) introduced a reinforcement-leariiig image through glimpses (small patches) and predict the label, and called their approach Hard Atten- tion. RRngrejj & Clark (202T) introduced probabilistic model for Hard Attention which is similar to the IP algorithm. More specifically, they propose to learn a partial- VAE Ma et al. (2018) to directly learn the distribution of images given partially observed pixels. This VAE is then used to select glimpses in order of information gain, as in IP. another work, Peng et al. (2018) introduced an RL-based framework to sequentially query patient symptoms for fast diagnosis. In $4 we compare V-IP with prior works in this area and show that in almost all cases our method requires a smaller number of queries to achieve the same level of accuracy. We conjecture that the superiority of V-IP over RL-based methods is because the V-IP optimization is not plagued by sparse rewards over long trajectories, for example, positive reward for correct prediction after a large number of symptom queries as in [Peng et al. (2018). Instead, Deep V-IP can be abstractly thought of as, given history, s, choosing a query q (the action) and receiving (PYY x)) P(Y ((z),,) s)) as an immediate reward. A more rigorous comparison of the two approaches would be an interesting future work.
(RL) algorithm to sequentially observe an
3 METHODS
3.1 G-IP: INFORMATION PURSUIT VIA GENERATIVE MODELS AND MCMC
Let X .2- - X' and Y Ω Y' be random variables representing the input data and corresponding labels/output. We use capital letters for random variables and small letters for their realizations. Ω the underlying sample space on which all random variables are defined. Let P(Y X) denote the ground truth conditional distribution of Y given data X. Let Q be a set of task ssec-fpeciiic, user-defined, interpretable functions of data, q X' + A, where q(x) E the answer to query q E Q evaluated at E X. We assume that Q is sufficient for solving the task, i.e., we assume that V(z,y) E X x y
Pv x) P(y (x/ E x q(=') g(x) Vy Q)).
(1)
In other words Q(X) := (x(X) E Q} is sufficient statistic for Y.
The Information Pursuit (IP) algorithm (Geman & Jedynak 1996) proceeds as follows; given a data-point obb a sequence of most informative queries is selected as
91 IP(0)= arg max I(q(X): Y); 9EQ
(2)
0k+1 = IP((), q: (1 )1x) = arg max T T(((X); Y (1
gEQ
3

---

Published as a conference paper at ICLR 2023
Here t Q refers to the new query selected by IP at step k + 1. based on the history (denoted as Ir (r)h)) } and (x+1(2=0h) indicates the corresponding answer. The algorithm terminates after L the data point 2dhh, if all remaining queries are nearly uninformative, that is, Vi E Q [(g(X); Y Y (1:I)) )) Ri O. The symbol denotes mutual information. Evidently equa- tion 2 requires estimating the query with maximum mutual information with Y based on history- One approach to carrying out IP is by first learning the distribution P(Q(X), Y) from data using generative models and then using MCMC sampling to estimate the mutual information terms How- ever, learning generative models for distributions with high- -igg--imensional support is challenging, and performing multiple iterations of MCMC sampling can likewise be computationally demanding. To address this challenge, in the nest subsection we propose variational characterization of IP that completely bypasses the need to learn and sample from complex generative models.
queries, where L depends
3.2 V-IP: A VARIATIONAL CHARACTERIZATION OF INFORMATION PURSUIT
We begin this section by describing variational characterization of IP. The pro- posed approach is motivated by the fact that generative models are only a means to an end; what we need is the function, that we call querier, that maps the histories observed, (%, 9: (2.be)) )] I:d., to the most in- formative next query 9k-1 E Q. It turns out that this most informative query is ex- actly the query q" whose answer will min- imize the KL. divergence between the con- ditional label distribution P(Y X) and the posterior P(Y q" (X), (z.h2)))) )=1)).
5.
Classifier f
(Y (ua()")))) Update hettryy
Hbe silpaarpns beak? tea.
2. Has blue calored wings?
3. Yes Se (isntey Answer
Has white oslored Ho His sorid broast pution?? No.
Querler
(eu. (, )] History
Next query
4. Apppnd new quary-answerr history
Figure 2: Overview. Interpretable predictions using V-IP.
Based on this insight, is it possible to define an opti- mization problem directly learn this querier function? This requires few ingredients,
First, we need to learn a querier that, given any possible history one might encounter during IP, chooses the next most informative query. One possible strategy for this is minimize the KL divergence objective in expectation over random histories of query-answer pairs. The posterior P(Y q" (X), (=)")))))) depends on the data distribution and is typically un- known. Thus, we need to estimate this using probabilistic classifiers. A possible solution is to jointly optimize this expected KL divergence over both querier and classifier functions.
This leads to the following variational characterization of IP which will allow us to avoid generative models. Let K(x)) be the set of all finite-length query-answer pairs of the form (191,1(1))
{ym, 4m (x))), generated using queries from Q evaluated any X. We then define I = UzexK(z) and denote elements of IK as "histories". We define classifier f K + Py as a function which maps arbitrary query-answer sequences to a distribution over y. We define querier g IK- + Q as a function which maps arbitrary query-answe sequences to query 9 E Q. The variational objective for IP given by the following functional optimization problem.
min fig where :: q==g($) EQ
Ex,s DKL (P(Y X) P(Y (x)),
(V-IP)
P(Y () f(la, ((x))sS)
and the minimum is taken over all possible mappings f (classifier) and (querier). Here, S is a random set of query-answer pairs taking values K Given S and X ub the querier g chooses a query E Q, evaluates it on uh and passes the pair { q(r)))) to the classifier. The classifier of then makes prediction based on s appended with this additional pair (q. ((x)))))))
"Cnditioning on (z:b)) is to understood as conditioning on the event fa' E {ge, {q.g.. (.t.g.(2)) (=x)
SSince mutual information requires computing expectation over density ratios which is still intractable de-
spite having learnt a generative model.
'Throughout this paper whenever condition on S 8, we mean conditioning the event of all data
o' E X' which share the same answers queries as in s.
4

---

Published as a conference paper at ICLR 2023
Let (f".. gg)) be optimal solution to V-IP The querier 9" will be the IP strategy with the require- ment that the distribution of S, denoted as Ps. in V-IP is chosen such that the histories observed while carrying out IP must have positive probability mass under Ps. Thus, given data-point :ht
q1 (0) = arg max I (g(();;));
gEQ
(3)
4k+1 = g" (fq; q: (1 arg max [g(();; (1:k(x00n))
qEQ
The above sequential procedure is illustrated in Figure as the history observed after k queries and is a realization of S. This is formalized in the following proposition whose proof can be found in Appendix Proposition Let ((*,"") be an optimal solution to V-IP For any realization = 8 such that
2
As before {gt, (z his is referred to
P(S = =) > O, define the optimization problem:
max PEPy.qEQ
X(g(X); Exxle [DKL (P(Y (x)). s) P(Y
x(X),
(4)
Then there exists an optimal solution (Pa.93 to the above objective such that q g'(s) and P; 9 Us)
Thus, at the optima, the KL divergence term in equation 4 would be 0 and g" would pick the most informative query for any given subset of query-answer pairs S = 8 as is presented in equation 3
Theoretical guarantees aside, solving the optimization problem defined in V-IP is challenging since functional optimization over all possible classifier and querier mappings is intractable. In the fol- lowing subsection, we present practical algorithm for approximately solving this V-IP objective.
3.3 V-IP WITH DEEP NETWORKS
Instead of optimizing f and g over the intractable function space, we parameterize them using deep networks with weights and 7 respectively. Our practical version of V-IP termed as Deep V-IP, is as follows,
min 0.7
Ex,s|DKL (X) Po (X),
where
4n 4- (y()
(Deep V-IP)
Po l1 = follan- 9, (X))
Note that all we have done is replace arbitrary functions/ and g in V-IP by deep networks parame- terized by and r7. To find good solutions there are two key constraints. First, the architecture for the classifier fo and the querier 9,, functions need to he expressive enough learn over an exponential (in (Q) number of possible realizations of S. Second, we need to choose a sampling distribution Ps for S. Notice, that for any reasonable-sized Q. there will be an exponentially large number of possible realizations of S. Ideally, we would like to choose a Ps that assigns positive mass only to histories observed during the exact IP procedure, however this is like the "chicken-and -en-eeg" dilemma. We now briefly discuss the architectures used for optimizing the Deep V-IP objective, followed by an exposition on the sampling distribution for S.
Architectures. The architecture for both the querier and classifier networks (described in more de- tail Appendix [ are chosen in such a way that they can operate on arbitrary length query-answe primarily use masking where the deep
pairs. There can be several choices for this. In this paper, networks operate on fixed size inputs (the answers to all queries E Q evaluated on input x) with the unobserved query-answer masked out. We also experiment with set-based deep architectures proposed in Ma et al. (2018). We show by ablation studies in Appendix E that the maasking-based architecture performs better. practice, gn = a rrgmaa (gn (gn,())) where (y(SS) E RIQI the output of the querier network, which assigns score to every query in Q and argmax computes an 1-hot indicator of the max element index of its input vector. To ensure differentiability through ar argmax the ttraight-through softmax estimator (Paulus al., 2020) which is described in detail in Appendix D Finally, Po (X), S) is the output of Softmax applied to the last layer of fo-
Sampling of S. Choosing a sampling distribution that only has positive mass histories observed during exact IP is like the "chicken-and-eee"" dilemma. A simple alternative is to consider a dis- tribution that assigns a positive mass to all possible sequences of query-answer pairs from K. This
5

---

Published as a conference paper at ICLR 2023
however would lead to slow convergence since the deep networks now have to learn to choose the most informative query given a large number query-answer pair subsets that would never be ob- served for any znth E X' if one could do exact IP. To remedy this, choose adaptively bias our sampling distribution towards realizations of S one would observe if they carried out equation 3 using the current estimate for querier in place of g" More concretely, we optimize (Deep V-IP by sequentially biasing the sampling distribution as follows:
1. Initial Random Sampling: We choose an initial distribution Pa which ensures all elements of K have positive mass. We first sample X ~ PDam- Then we sample k ~ Uniform(0, 1, .... IQ) } as the number of queries. Subsequently, &t queries from Q are selected for X uniformly at random.
2. Subsequent Biased Sampling: The distribution P3 is obtained by using the solution querier Dep to V-IP using P3 as the sampling distribution. In particular, we first sample X ~ Pana and k ~ Uniorm:(0, 1, l....,1.6 [Q]} as before. Subsequently, we find the first &t query-answer pairs for this sampled X using equation 3 with 9y, as our querier.
Notice that, the empty set i. corresponding to empty history, would have positive probability under any Pá and hence the querier would eventually learn to pick the most informative first query. Subse- quent sequential optimization would aim at choosing the most informative second query and so on, assuming our architectures are expressive enough. In practice, we optimize with random sampling of S using stochastic gradients for numerous epochs. We then take the solution I,p and fine-tune with biased sampling strategies, each time optimizing using a single batch and consequently chang- ing the sampling strategy according to the updated querier. Refer Appendix E for ablation studies on the effectiveness of the biased sampling strategy for S.
Stopping Criterion. There are two possible choices; (i) Fixed budget: Following prior work in sequential active testing (Ma et al. 2018]] [Rangrej & Clark] (021). we stop asking queries after a fixed number of iterations. (ii) Variable query-lengths: Different data-points might need different number of queries to make confident predictions. For supervised learning tasks, where Y is "almost" a deterministic function of X, that is, maxy P(Y X) x: 1, for any given 2o05s E X, we terminate after L steps if maxy P(Y T1:L (2:b)) 2 1 where c is hyperparameter. This is termed as the "MAP criterion". For tasks where Y is more ambiguous and not deterministic function of X, we choose to terminate once the posterior is "stable" for pre-defined number of steps. This stability is measured by the difference between the two consecutive posterior entropies, H (Y 92-4 (x.b))
H (Y (1=x+1(2bbb) S c. This criterion, termed as the "stability criterion", is an unbiased estimate of the mutual information-based stopping criteria used in Chattopadhyay et al. (0222).
Qualitative differences between Generative-IP IP and Variational-IP. We will refer to the genera- tive approach for carrying out IP as described in Chattopadhyay et al. (2022) as Generative-IP or G-IP. The difference between G-IP and V-IP is similar in spirit to that of generative versus discrim- inative modelling in classification problems (Ng & Jordan 2001). We conjecture that, when the data distribution agrees with the modelling assumptions made by the generative model, for exam- ple, conditional independence of query answers given Y, and the dataset size "small," then G-IP would obtain better results than V-IP since there are not enough datapoints for learning competitive querier and classifier networks. We thus expect the gains of V-IP to be most evident on datasets where learning a good generative model is difficult.
4 EXPERIMENTS
In this section, through extensive experiments, we evaluate the effectiveness of the proposed method. We describe the query set used for each dataset in Table [ with more details in Appendix C The choice of query sets for each dataset was made to make our approach comparable with prior work. We also complement the results presented here with more examples in the Appendix. Code is avail- able at https://////
com/ http://ww.....aaaaaaaaaaaaaaaaaa
4.1 INTERPRETABLE PREDICTIONS USING V-IP
Basing predictions interpretable query set allows to reason about the predictions in terms of the queries, which are compositions of elementary words, symbols or patterns. We will illustrate this by analyzing the query-answer chains uncovered by V-IP for different datasets. Figure 3 illustrates
6

---

Published as a conference paper at ICLR 2023
Table 1: Descriptions of query set for different datasets.
Dataset
Query Set Q
Size (2)
CUB-200 Wath et ml.
2011
indicator for the presence of different visual semantic attributes of birds
312
HullingtonNews (Misra 2018
indicator for presence of words article headline or description
1000
MNIST (LeCun 1998
KMNIST (Crmnwat of ai 2018).
pixel intensities in 3 x overlapping patches with stride
676
Fashion-MNNSST [X1a0 et al 2017b
CIFAR-(10.100)
KKrzzhvskyy et
2009
pixel intensities x 8 overlapping patches with stride
49
SymCAT-220 Peng
2018
328
SymCAT-300 Peng el al. 2018
indicutor for the presence of different medical symptoms
349
SymCAT-400
[Png ot al. 2018
355
MuZhi Wei et 2018
temnrry (ees, No. Can't Say) queries for the presence of different medical symptoms
66
Dxy X8 ar 2019
41
the decision-making process for V-IP on an image of a dog from the CIFAR-10 dataset. A priori the model's 's belief is almost uniform for all the classes (second row, first column). The first query probes a patch near the centre of the image and observes the snout. Visually it looks similar to the left face of a cat, justifying the shift in the model's belief label "cat" with some mass on the label "dog". Subsequent queries are aimed at distinguishing between these two possibilities. Finally, the model becomes more than 99% confident that it is a "dog" once it spots the left ear. Figure 3p shows the query-chain for "genital herpes" diagnosis of synthetic patient from the SymCAT-200 dataset. The y-axis shows the query asked each iteration with green indicating a "Yes" answer and red indicating "No". Each row shows the model's current belief in the patient's 's disease. We begin with an initial symptom, "O: itching of skin", provided by the patient. The subsequent queries ask about different conditions of the skin. The diseases shown are the top-10 most probable out of 200. All of these diseases have skin-related symptoms. After discovering the patient has painful urination (query 11), V-IP zooms into two possibilities "Balanitis" and "Genital herpes". The subsequent queries rule out symptoms typically observed in patients with "Balanties" resulting in 80% confidence in the herpes disease. For our final example, we elucidate the results for bird image from the CUB-200 dataset in Figure Br. The colour scheme for the y-axis is the same as in Figure Bp. with the exception that, unlike the patient case, we do not bootstrap V-IP with an initial positive attribute of the word. Instead, the first query about bill shape is the most most-informative query about the label Y before any answer is observed. This indicated with the grey "O:Init". All the top- 10 most probable bird species in this context are seabirds, and have very similar visual characteristics to the true species, "Laysan Albatross". After 14 queries V-IP figures out the true class with more than 99% confidence. Thus, in all three case-studies, we see that V-IP makes transparent decisions, interpretable in terms of queries specified by the user. A limitation of this framework however is finding good query set that is interpretable and allows for highly accurate predictions with short explanations (short quere-answer chains). We discuss this further in Appendix (G)
4.2 QUANTITATIVE COMPARISON WITH PRIOR WORK
Baselines. We compare V-IP primarily to the generative modelling approach for IP, namely G-IP. We also compare to Reinforcement- Learning methods prevalent in other ar- eas of sequential-decision making like Hard- Attention (Mnih et al., 2014| Rangrej & Clark 202T) or Symptom Checking (Peng et al. 2018 which can be adapted for our purposes. In particular, we compare with the RAM (Miih let al., 2014) and RAM+(Li et al., 2017) algo- rithms. In both methods, policy is learnt using deep networks to select queries based on previ-
Table 2: AUC values for test accuracy vs. explanation length curves for different datasets. To account for dif- ferent query set sizes across datasets, we normalize the scores by [Q]. Refer to Tn Appendix $F for ex- tended results with standard deviations for other meth- ods (averaged over 5 runs).
Dataset
Random
RAM
RAM+
G-IP
V-IP (Ouns)
CUB HurhingtonNews
0.557
0.662
0.695
0.736
0.716
D.DK
0.423
0.431
0
0.680
MNIST KMNIST
0.868
0.916
0.920
0.964
0.956 :: 0.002
0.775
0.82
0.841
0.872
0.911
0.088
Fushion-MNIST
0.735
0.804
0.831
0,849 0.010
ous ansre- for fixed number of iterations such that the expected cumulative reward is max- imized. A classifier network is also trained simultaneously with the policy network to make accurate predictions. In RAM, this reward is just the negative cross-entropy loss between true and predicted labels at the last step. In RAM+, this reward is the cumulative sum of the negative cross-entropy loss at each step. We also compare our method with the "Random" strategy where successive queries are
7

---

Published as a conference paper at ICLR 2023
k=1
k=2
km
Km
k=
km666
k=7
PIY (orll*
1.00
(b)
P(Y (((a))
P(Y ((a((""))
rching
Atnormal appearing sch
blll shape all purpose
2. Stan leaton
2. colorswhitte
3. Siin moles
saape-perching-tie 4. tall patterusolid
Sate
Acna or pimples
color.biack under colerstrack
9.6
s. Skón rish
imegular appraring scalp
0.4
10. fever
9. wing colorowhite color-gre
unination
11. pattaris-plai
Veginal discarge
12, foreheed colorsbiack steeimedium
0.
14. Foot the na
15, Sharp abcomnal pain
Brythmma mnsttiome
Actess Seratooia
Uihin plaacis
0.0
back colorsbiack
Laysary Altatrocs
Cestorie Coat
Chaf Autler Lovig por Black foctue Altartro
Altatris
0.0
Fingel enfectonn
Riin
Figure 3: (a) V-IP CIFAR-10. In column row 1, show the observed image obs and in column row we show the label distribution before V-IP observes any patches. In the subsequent columns, row indicates the patches revealed (the history) so far and row 2 shows the corresponding postcrior over the labels given this history. (b) V-IP on SymCAT-200. Each row in the heatmap shows the posterior of the disease labels given history. We show the top-10 most probable diseases out of 200. The y-axis indicates the corresponding symptom queried in each iteration by V-IP. We the colour scheme that red denotes "No" answer while green denotes "Yes" answer. (c) V-IP on CUB-200. observed image x. obs shown on right. The heatmap shows the posterior, similar to (b).
1.00
Test Accuracy
MNIST
CUB-200
HuffingtonNews
Aug.
Aug.
PwritiionalPPP (Durs)
Generativc
RAN
RAM
Random
Figure 4: Tradeoff between accuracy and explanation length (avg. number of queries). The curves were generated by varying the parameter in the stopping criteria (see $3.3 For MNIST & HuffingtonNews we the "MAP criterion". whereas for CUB-200 averaged over 5 runs with shaded region denoting standard deviation. More results Appx. F
the posterior "stability criterion". Reported curves
chosen randomly independent of the history observed so far. The predictions given history are still made using the V-IP classifier.
We first show results on the simple datasets used in Chattopadhyay et al. (0022 comparing with our own implementation G-IP, RAM and RAM+. V-IP competitive with G-IP in terms of performance but far more efficient in terms of speed of inference. In all datasets, V-IP outperforms the RL-based methods. Subsequently, we present results on more complex tasks like RGB image classification. On these datasets, V-IP achieves higher accuracy given fixed budget of queries compared with prior work.
Comparisons on Simple Tasks, Concise explanations are always preferred due to their simplicity. In Figure 4 we plot the trade-off between accuracy and explanation length obtained by various methods. V-IP is competitive with G-IP and obtains far shorter explanations than the RL-based methods to obtain the same test accuracy. This trade-off is quantified using the Area Under the Curve (AUC) metric in Table 2 Notice the HuffingtonNews dataset the RL methods struggle
8

---

Published as a conference paper at ICLR 2023
to perform better than even Random. This is potentially due to the fact that in these RL methods, the classifier is trained jointly with the policy which likely affects its performance when the action- space is large (IQ) 1000). On the other hand, the random strategy learns its classifier by training on random sequences of query-answer pairs. This agrees with findings in Rangrej & Clark (021).
While V-IP performs competitive with the generative approach the biggest gain is in terms of com- putational cost of inference. Once trained, inference in V-IP, that is computing the most-informative query, is akin to a forward pass through a deep network and is potentially O(1) 5 On the other hand, the per-iteration cost in G-IP is ONN + IQ m)) where N is the number of MCMC iterations employed and m is the cardinality of the space (XX) x Y. As an example, on the same GPU server, G-IP takes about 47 seconds per iteration on MNIST whereas V-IP requires just 0. 0.11s, an approxi- mately x00x speedup! Note that the inference cost is the same for V-IP and the RI, methods since all of them train querier/policy function to choose the next query.
Comparisons on Complex Tasks. We now move on to more complex datasets where the gains of V-IP are more evident. First, we con- sider the task of natural image classification and show results on the CIFAR- (11AR-(10,11 100} datasets. For G-IP on these datasets, we refer to the Prob-
[a] CHAAR-1
(c) SymCAT-200
abilistic HardAttn model introduced in Raan- grej & Clark (202T) which proposes to learn partial- VAE model (Ma et al. (2018) for images and then do inference using this model com- pute the most informative query. Figures [ & b show the accuracy vs. number of queries curves for different methods. V-IP clearly out- performs all baselines on both datasets.
oz [a] 100AR-10
ky
Vi5
ICTUC Ro
Mentor
Figure 5: Tradeoff between accuracy and number of queries asked (fixed budged stopping criterion) for the CIFAR datasets (a & b) and the SymCAT-200 dataset
Next, we consider the task of medical diagnosis by querying symptoms of the patient. We show results on the popular SymCAT dataset along with comparisons with prior work in Figure 5p. The plot clearly shows that V-IP achieves much higher accuracy given fixed budget of queries.
(c). Curves for baselines adapted from Rangrej & Clark (202)) for (a) & (b) and from He al. 2022) for (C).
For G-IP on this task, we refer to the BSODA framework introduced in He et al. (2022) which REFUEL
Table 3: Test accuracy obtained different symptom checking datasets after asking 20 queries.
is again based on partial-VAEE (Peng et al. 2018) is ofate-of-the-an art RL- based method for this task akin to the RAM technique used in Hard-Attention literature. The classification accuracy for these different methods on all medical datasets are summa-
Dataset
BSODA
REFUEL
V-IP (Ours)
SymCAT-200
0.556
0.548
0.681 + 0.004
SymCAT-300
0.475
0.482
0.599 + 0.007
SymCAT-400
0.446
0.438
0.513 + 0.009
MuZhi
0.726
0.718
0.706 + 0.011
rized in Table B Numbers for baselines are taken from Nesterov et al.) (2022) since we used their released versions of these [
Dxy
0.811
0.757
0.806 + 0.019
[o] As conjectured in 3.3, MuZhi and Dxy are small-scale datasets with about 500 training samples thus approaches based on generative models, like BSODA, are able to perform slightly better than V-IP.
5 CONCLUSION
IP was recently used to construct interpretable predictions by composing interpretable queries from a user-defined query set. The framework however required generative models which limited its application to simple tasks. Here, we have introduced a variational characterization of IP which does away with generative models and tries to directly optimize a KL-divergence based objective to find the most informative query, as required by IP, in each iteration. iteration.Through qualitative and quantitative experiments we show the effectiveness of the proposed method.
For simplicity we consider unit cost for any operation that was computed in a batch concurrently on a GPU. https: htopps://g //gi thub. wwm womm/SympCheck//eele httpp//chweeeeeeoooaoyosooottnne 1SympttomChecker

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This research supported by the Army Research Office under the Multidisciplinary University Research Initiative contract W91 INF-1777-100,,,4,, the NSF grant 2031985 and by Simons Foundation Mathematical and Scientific Foundations of Deep Learning (MoDL) grant 135615. Moreover, the authors acknowledge support from the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE2139757. Any opinions, findings, and conclusions or recommenda- tions expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
10

---

Published as a conference paper at ICLR 2023
REFERENCES
Julius Adebayo, Justin Gilmer, Michael Muelly, lan Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. Advances neural information processing systems, 31, 2018. pages 1,
David Alvarez Melis and Tommi Jaakkola. Towards robust interpretability with self-explaining neural networks. Advances in neural information processing systems, 31, 2018. pages 3
Moritz Bohle, Mario Fritz, and Bernt Schicle. Convolutional dynamic alignment networks for in- terpretable classifications. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 10029-10038, 2021. pages
Aditya Chattopadhyay, Piyushi Manupriya, Anirban Sarkar, and Vineeth N Balasubramanian. Neu- ral network attributions: causal perspective. In International Conference on Machine Learning, pp. 981-990. PMLR, 2019. pages ]
Aditya Chattopadhyay, Stewart Slocum, Benjamin D Haeffele, Rene Vidal, and Donald Geman. Interpretable by design: Learning predictors by composing interpretable queries. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 2022. pages 2, 3, 6, 8, 17, 18, 19, 24, 26
Tarin Clanuwat, Mikel Bober- Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature, arXiv preprint arXiv:1812.0171 2018. pages
7, 18, 26
Jon Donnelly, Alina Jade Barnett, and Chaofan Chen. Deformable protopnet: An interpretable image classifier using deformable prototypes. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10265-10275, 2022. pages
Donald Geman and Bruno Jedynak. An active testing model for tracking roads in satellite images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(1):1-14, 1996. pages 2,
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016. pages 21
Weijie He, Xiaohao Mao, Chao Ma, Yu Huang, José Miguel Hernandez-Lobato, and Ting Chen. Bsoda: A bipartite scalable framework for online disease diagnosis. In Proceedings of the ACM Web Conference 2022, pp. 251 1-2521, 2022. pages 9, 20, 21
Jie Hu, Li Shen, and Gang Sun. Squeeze-and-excitatn networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7132-7141, 2018. pages 26
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700 4700-4708, 2017. pages 21, 26
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. Explainable AI: Interpreting, Explaining and Visualizing Deep Learning, pp. 267-280. Springer, 2019. pages 1,3
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. pages 17
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv:1312.61 2013. pages 2
arXiv preprint
Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. International Conference on Machine Learning, pp- 3338-5348.. PMLR, 2020. pages 3, 26

---

Published as a conference paper at ICLR 2023
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. pages 7,
Matthew Lavin. Analyzing documents with tf-idf, 2019. pages 18
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11):228-22324, 1998. pages 7, 18
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 Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018. pages 3
Zhichao Li, Yi Yang. Xiao Liu, Feng Zhou, Shilei Wen, and Wei Xu. Dynamic computational time for visual attention. In Proceedings of the IEEE International Conference on Computer Vision Workshops, pp. 1199-1209, 2017. pages
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint orXiv:1608.039% 03983, 2016. pages 17
Scott M Lundberg and Su-In Lec. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017. pages
Chao Ma, Sebastian Tschiatschek, Konstantina Palla, José Miguel Hernández-Lohatt Sehastian Nowazin, and Cheng Zhang. Eddi: Efficient dynamic discovery of high-value information with partial vae. arXiv preprint
2018. pages 3, 5, 6, 9, 21
Rishabh Misra. News category dataset, 06 2018. pages 7
Volodymyr Mnih, Nicolas Heess, Alex Graves, et al. Recurrent models of visual attention. Advances in neural information processing systems, 27, 2014. pages 2, 3,
Meike Nauta, Ron van Bree, and Christin Seifert. Neural prototype trees for interpretable fine- grained image recognition. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14933-14943, 2021. pages
Aleksandr Nesterov, Bulat Ibragimov, Dmitriy Umerenkov, Artem Shelmanov, Galina Zubkova, and Vladimir Kokh. Neuralsympcheck: A symptom checking and disease diagnostic neural model with logic regularization, arXiv preprint arXiv:2206.00 2000002 2022. pages 9, 21
Andrew Ng and Michael Jordan. On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes. Advances in neural information processing systems, 14, 2001. pages 6
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett (eds.). Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019, pages 17
Max Paulus, Chris J Maddison, and Andreas Krause. Rao-blackwellizing the trriighttthrough gumbel-softmax gradient estimator. arXiv preprint 1=XXi:20100048388 2020. pages 5
Yu-Shao Peng, Kai-Fu Tang, Hsuan-Tien Lin, and Edward Chang. Refuel: Exploring sparse fea- tures in deep reinforcement learning for fast disease diagnosis. Advances in neural information processing systems, 31, 2018. pages 2, 3, 7, 9, 20
Samrudhdhi B Rangrej and James J Clark. A probabilistic hard attention model for sequentially observed scenes. arXiv preprint arXiv:2111.07534. 2021. pages 7, 9.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint A9Xiv:1904.090 2019. pages 17
12

---

Published as a conference paper at ICLR 2023
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. " "why should i trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1135-1144, 2016. pages
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-211) 2019. pages 1,
Anirban Sarkar, Deepak Vijaykeerthy, Anindya Sarkar, and Vineeth N Balasubramanian. A frame- work for learning ante-hoc explainable models via concepts. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 10286-10295, 2022. pages 3
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06377, 2017. pages 17
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruy Batra. Grad-cam: Visual explanations from deep networks via gradient-based local- ization. In Proceedings of the IEEE international conference on computer vision, pp. 618-626, 2017. pages
Harshay Shah, Prateck Jain, and Praneeth Netrapalli. Do input gradients highlight discriminative features? Advances in Neural Information Processing Systems, 34, 2021. pages 2, 3
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International conference on machine learning, pp. 3145- 3153. PMLR, 2017. pages
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: networks Vi- sualising image classification models and saliency maps. arXiv preprint arXiv:1312.6034, 2013.
pages
Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks on post hoc explanation methods. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pp. 180-186 186, 2020. pages 3
Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smoothgrad:
removing noise by adding noise. arXiv preprint 17Xx::7706.03255 2017. pages
Akshayvarun Subramanya, Vipin Pillai, and Hamed Pirsiavash. Fooling network interpretation in image classification. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 2020-2029, 2019, pages
Catherine Wah, Steve Branson, Peter Welinder, Pictro Perona, and Serge Belongie. The caltech-uesd birds-200-2011 dataset. 2011. pages 7, 17
Zhongyu Wei, Qianlong Liu, Baolin Peng. Huaixiao Tou, Ting Chen, Xuan-Jing Huang, Kam-Fai Wong, and Xiang Dai. Task-oriented dialogue system for automatic diagnosis. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume Short Papers), pp. 201-207, 2018. pages 7, 20
Mike Wu, Sonali Parbhoo, Michael Hughes, Volker Roth, and Finale Doshi-Velez. Optimizing for interpretability in deep neural networks with tree regularization. Journal of Artificial Intelligence Research, 72:1-37, 2021. pages?
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: A mnist-like fashion product database. In GitHub, 2017a. pages 26
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist a novel image dataset for benchmark-
ing machine learning algorithms. 2017b. pages 7, 18
Lin Xu, Qixian Zhou, Ke Gong, Xiaodan Liang, Jianheng Tang, and Liang Lin. End-to-end knowledge-rou relational dialogue system for automatic diagnosis. In Proceedings of the AAA! Conference Artificial Intelligence, volume 33, pp. 7346-7353, 2019. pages 7, 20
13

---

Published as a conference paper at ICLR 2023
Mengjiao Yang and Been Kim. Benchmarking attribution methods with relative feature importance. arXiv preprint 19700:1907.09701, 2019. pages 2,
Chih-Kuan Yeh, Been Kim, Sercan Arik, Chun-Liang Li, Tomas Pfister, and Pradeep Ravikumar. On completeness-aware concept-based explanations in deep neural networks. Advances Neural Information Processing Systems, 33:20554-20565, 2020. pages 3
Bin Yu. Three principles of data science: predictabilityy, computability, and stability (pcs). 2018. pages
Fisher Yu, Dequan Wang, Evan Shelhamer, and Trevor Darrell. Deep layer aggregation. Proceed- ings of the IEEE conference computer vision and pattern recognition, pp. 2403-2412, 2018. pages 21, 26
Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In European conference on computer vision, pp. 818-833, Springer, 2014. pages
14

---

Published as a conference paper at ICLR 2023
APPENDIX
A PROOF OF PROPOSITION
Before proceeding to proof we will prove the following lemma,
Lemma 1. Let Q be an user-defined query set and PYY be the set of all possible distributions on Y. Then, for any realization S = 8, the the following holds true:
min PePy.eEQ
Ex|s |KL(P(Y X) P(Y ((X),
(S)
[T((()) 8) - ( ((X),,) 8) II P(Y (())), s]]]
max PEPy.eEQ
Proof. Using information-theorrtie properties of the KL-divergence have the following set of equalities.
min PEPy.gEQ
Ex|s
DRa,P(Y X) || P(Y ((x),
min PEPy.gEQ
E Æx|
DKL(P(Y (x,((X),)) || P(Y ((X),
Σ P(Y (x,q(X),)) P(Y X, (X). P(Y s)
min PEPs.gEQ
Ex1s
(6)
P(X,Y Y (()))s)))))))))))())))){))))){
min PEPy.rEQ
Exis
Σ P(Y X,9(X), lo P(Y (()), P(X ())
P(X,Y (())) 3)
+ + |og P(Y (()).s)
min
Ex,Y|s
log P(Y [(X), 8) P(X ())),8)
PEPy.4EQ
P(Y ()),,
min PEPylnEQ
T(X;Y ())),)) 8) Ex (KI (P(Y (()),)) P(Y x)))
In the first equality, assuming P(X S. 5) 0 used the fact that given any X x, the label Y is independent of any query answer (xX) g(z) and event {S = s). Thus, P(Y X x) P(Y X x, ((X) q(x), 8). In the fourth equality multiplied the P(Y))(X))e)
term inside the log by the identity P(Y]g(X) (.)))* where P(Y () represents the true posterior of Y given the query answer (X) and S =
Now observe that for any fixed S = and any E Q,
7(X, (X); |) T(X;Y s) + T(q(X);Y X,s) I(X;Y s)
The second equality is obtained by using the fact that (X) a function of X.
Decomposing I(X, (X);; Y another way,
T(X, (X)) s) T(a(x); 8) + T(X;Y s)
(8)
From equation 7 and equation
g we conclude that
min I(Y; X ((X),)) min - I(g((): nEQ
QEQ
Substituting the RHS in the above result in equation 6 we obtain the desired result.
For any o' E X. if P(X x' S = 0, then x would not contribute to the expectation in the first
cquation and we do not need consider this case.
15

---

Published as a conference paper at ICLR 2023
Proof of Proposition| 1
Restating the objective from equation V-IP
min 1.9
Ex.s DKL. (((Y X) P(Y s)))
where
9:= ((5) EQ
P(Y (( = f(1g: xX)) US):
Now, for any realization S = 8, such that P(S = 3) > 0, we have,
min PEPylgEQ
Ex|s
DKL (P X) PY (x()),
Exxs
DKL (P(Y) X) (Y (x)( .))
P(Y {(X),s)
|KKL (P(Y) X) || P(Y ((X)),))) s))] + Ex|=
-Ex|s
P(Y [x)log
PY (X)),
P: (x),,,) P(Y (())),))
Ex|s
DKL (P(Y x) P(V 1 ((x), Ex|= Σ P(Y | |X)log
= EEI|
DKL (P(Y) X) P(Y ()x -KL (P:(Y (x)()), || P(Y ((x),))
<
Ex|s
DKL (P(Y) X) || P(Y ((X))
In the first equality we used the definition of (Pr,4.) 9.) as the solution to the minimization problem in the first equality. In the second equality, q g(s) for any querier g and P(y {(X),
f(17, {(X)) U 8}) for any classifier f. In the fourth equality we appealed to lemma to conclude that (Y s)) = P(Y (X), s), the true posterior over Y given answer q. (X) and history s. The final step we used the non-negativity of the KL-divergence for getting rid of the second term.
Since the inequality equation Iholds VS 8, and mappings f and g. we conclude that ot g (s) and Pr ("1 of (X)) Us) for any given S 8. Equation 4 the proposition is then proved by using lemma to characterize of and P..
B TRAINING PROCEDURE
Consider mini-batch of N samples, {(x,, y:) from training set.
In Deep V-IP objective, the KL-divergence is mathematically equivalent to the cross entropy loss. The mini-batch estimate of this loss can be expressed as:
N ys log D: Σ 1=1
min 8.7
(10)
subject to
On argmax(s, Ú: = fo(s U {am 9n (xx))).
where y; is the ground truth label corresponding input xs. 8; is obtained by sampling for Pg as defined in $3. We optimize the above objective using Stochastic Gradient Descent (or its variants).
To optimize objective I0, for every sample x; in the batch, the sampled history 8; is fed into the querier network 9n, which outputs score for every query q E Q. The argmax (.) (see Dergardiig its differentiability) operator converges these scores into a IQ] -iimeennsio one-hot vector, with the non-zero entry at the location of the max. We then append this argmax query qn and it's answer, (9,, 9,, (X)) to s;, The updated history s; U (q,, 9n (xx)) is then fed into the classifier fo to obtain softmax distribution over the labels, denoted as Dj-
16

---

Published as a conference paper at ICLR 2023
C EXPERIMENT DETAILS
All of our experiments are implemented in python using Py PyTorch (Paszke et al. 2019) version 1.12. Moreover, all training is done on one computing node with 64-core 2. IOGHZ Intel(R) Xeon(R) Gold 6130 CPU, NVIDIA GeForce RTX 2080 GPUs (each with 10GB memory) and 377GB of RAM.
General Optimization Scheme. The following optimization scheme is used in all experiments for both Initial Random Sampling and Subsequent Biased Sampling, unless stated otherwise. We minimize the Deep V-IP objective using Adam (Kingma & Ba, 2014) as our optimizer, with learn- and amdgrad=True (Reddi) et al. 2019). We also use Cosine Annealing learning rate scheduler (Loshchilov & Hutter 2016) with m_max=55 50. We train our networks fe and 9n for 500 epochs using batch size 128. both sam- pling stages, we linearly anneal temperature parameter in our straight-through softmax estimator, from 1.0 to 0.2 over the 500 epochs.
ing rate 1 e-4, betas= (0. 9, 0. 0999.), we ghe_deca
Training Details for RAM and RAM+. For train the RL policy and classification network the popular PPO algorithm (Schulman et al,, (017) with entropy regularization (0.01 regularization parameter). We used in initial learning rate of 3e-5 and clip value 0 2. For a fair comparison the architectures for the policyPant and classification networks are kept the same for RAM, RAM+ and
V-IP.
C.I SPECIES CLASSIFICATION ON CUB.
Dataset and Query Set. Caltech-UCSD 20rds-200-201 (CUB-200) Waa et al. 2011 1 is a dataset of 200 bird species, containing 11,788 images with 312 annotated binary features for different visual attributes of birds, such as the color or shape of the wing or the head of the bird. We construct the query set Q using these attributes. For example, given image for a Blue-jay possible query might be "is the back-colour blue?" and the answer "Yes".
The query set construction and data preprocessing steps as same as Chattopadhyay et al. (2022): In the original dataset, each annotated attribution for each image is too noisy, containing often imprecise description of the bird. Hence, certain attribute is true/false for over 50% of the samples in given category, then that attribute is true/false for all samples in the same category. We also train a CNN to answer each query using the training set annotations called the concept network. This concept network provides answers for training all the methods compared in $4 namely, RAM, RAM+, G-IP and V-IP. Last but not least, our query set Q consists of 312 queries that ask whether each of the binary attributes is 1 for present - 1 for absent.
Architecture and Training A diagram of the architectures is shown in Figure 6 Both fe and 9n have the same full-connecte network architecture (except the last linear layer), but they do not share any parameters with each. We initialize each architecture randomly, and train using the optimization scheme mentioned in the beginning of this section. The input history is -il-dimensional vector with unobserved answers masked out with zeros.
Let the history of query-answer pairs observed after k steps be denoted as Sc- Ss is represented by a masked vector of dimension 312, and ( = a arggax (g,, (Ss). ) is a one-hot vector of the same dimension, denoting the next query. For a given observation 2 we update S₃ using Q as follows:
Updating the History.
We obtain the query-answer by performing a point-wise multiplication, that is.
(1) = qu+11 @ obs
We update the history to St+1 by adding this query answer 1 (2 to Sp.
The entire process can be denoted by Sk+1 = Sy + g O bbs
*This term is from the RI. community. In our context, the policy network is exactly the querier network. Precall Gn our querier function parameterized by deep network with weights 7).
17

---

Published as a conference paper at ICLR 2023
History 312 x
History 312 x1
LayorNorm RaLU
LayerNorm ReLU
Linear 500
Linear 500
LayerNorm RaLU
LayorNorm RoLU
Linear
Class 200 x
312
Figure 6: Classifier fo (Left) and querier 9h, (Right) architectures used for species classification CUB.
C.2 TOPIC IDENTIFICATION ON THE HUFFINGTON POST NEWS CATEGORY DATASET.
Dataset and Query Set. The Huffington Post News Category dataset (HuffingtoNNwws) is a natu- ral language dataset, containing news "headlines" and their short descriptions (continuation of the headline) extracted from Huffington Post same data-processing procedure as Chattopadhyay et al. (2022): Each data point is an extended headline formed by concatenation of the headline with their short descriptions. Moreover, remove redundant categories, including semantically ambiguous and HuffPost-specific words such "Impact" and "Worldpost." We also remove categories with small number of articles, along with semantically equivalent category names, such as "Arts & Culture" versus "Culture & Art." After processing, there is total of 10 categories in the dataset. In addition, only the top-1,000 words are kept according to their tf-idf scores (Lavin, 2019). along with semantically redundant words removed. For more details, please refer to Chattopadhyay al. (2022).
published between 2012 and 2018. We follow the
also
The query set Q contains binary questions of whether one of the 1000 words exist in the headline. The query answer 1 if the word in question present and if absent.
Architecture and Training, A diagram of the architectures is shown in Figure 7 Both the classifer So and the querier 9, shares the same architecture except the last layer; However, they do not share any parameters. The inputs to fo and D, are masked vectors, with masked values set to 0. To optimize Deep V-Jejobeective, we randomly randomly initialize fe and In, and train using Adam optimizer and Cosine Annealing learning rate scheduler, with the settings mentioned in the beginning of the section. During Subsequent Adaptive Sampling, we train for 100 epochs using Stochastic Gradient and Cosine
Descent (SGD) instead of Adam, with learning rate rr=1e- and momentum=0 Annealing learning rate scheduler, with T max=100, The input history is a |Q] -iimemnnsia vector with unobserved answers masked with zeros.
Updating the History. The method of updating the history is equivalent to that for CUB as men- tioned in CC. The history is masked vector of dimension 1000, since there are 1000 queries in our query set for this dataset.
C.3 IMAGE CLASSIFICATION ON MNIST, KMNIST AND FASHION-MNISTI
Each setting mentioned in the following is the same for MNIST, KMNIST and Fashing-MNIST unless stated otherwise.
Dataset and Query Set. MNIST (LeCun et al. 1998), KMNIST CCannwatt et al. 2018). Fashion- MNIST Xiao al. 201 gray-scale hand-written digit datasets, each containing 60,000 train-
18

---

Published as a conference paper at ICLR 2023
History 1000
History 1000
Linear 2000
Linear 2000
LeyerNorm ReLU
LayerNorm + ReLU
Lineer 1000
Linear 1000
LayerNom
LayerNorm
Linear 500
Linear 500
LayerNorm ReLU
LayerNorm + ReLU
Linear
Linear 1000
Class Logits
Query Scores 1000
10
Figure 7: Classifier fa (Left) and querier 9, (Right) architectures used for topic identification Huffington Post News Category dataset.
ing images and 10,000 testing images of size 28 28. We follow Chattopadhyay et al. (2022) for data pre-processing procedure and the design of our query of all three datasets.
Each gray-scale image is converted into a binary image. For MNIST and KMNIST, we round values greater equal than 0.5 up and round values below 0.5 down -1. For Fashion-MNIST, round values greater or equal up to 0.1 to I and round values below 0.1 down to -1.
Each query set Q contains all overlapping 3 patches over the 28 28 pixel space, resulting in 676 queries. Each query answer indicates the 9 pixel intensities at the queried patch. The inputs to the classifier fo and the querier go are masked images, with masked pixels zeroed out they are not part of the current History.
Updating the History. The method for updating the history is equivalent to that for CUB men- tioned in C with some differences as we will describe next. For given observation ths we update S₃ using 4+++1 as follows:
We reshape 4 from a vector of dimension 676 (the number of queries) a 2D grid of dimension 26 x 26, denoted by f
ix+1 is then converted to a binary matrix with Is at the location corresponding to the queried 3 patch and everywhere else via a convolutation operation with kernel of all Is of size 3 x 3, stride and padding 2.
We then obtain the query-an qnswer by performing hadamard product of the convolved out- put (in the previous step) with zobs This results in a masked image, 9i+ (x.bs). with the queried patch revealed and 0 everywhere else.
Finally, we update the history to SE+1 by adding this query-answer to S To account for pixels observed (unmsaked) in (2:01) that overlap with the history S₁, we clip the values in Sg to lie between -1 and 1.
The entire process can be summarized as,
Sk+1 clip (Sk + (Conv2D((x+1) 2 20xx ob0)) minval -1, maxval 1)
19

---

Published as a conference paper at ICLR 2023
Architecture and Training. Refer to Figure 8 for a diagram of the architecture for the classifier fa and the querier 9n. Every Conv is 2D Convolution with 3 x 3 kernel, stride I and padding 1. Moreover, every MaxPool is a 2D max pooling operator with 2 x 2 kernel. We initialize each architecture from random initialization, and train networks using Adam Cosine Annealing learning rate scheduler, with the same settings mentioned in the beginning of this section.
optimizer and
History x 28 x
History x 28 x
Upsample Conv 256
Comv 32
Conv 32
RaLU
BatchNorm ReLU
DatchNoor ReLUU
Upsample
Comv 84
Conv 64
BetchNorm MexPooi
BatchNom RaLU MaxPool
Upsample Conv
Conv 128
Conv
BatchNorm ReLU
BatchNom RaLU
Batchhoorm ReLUU
Upsample + Conv 64
Cony 256
Conv 258
ReLU
DaichNorm ReLU MaxPool
BatchNom Ral MaxPool
Upsample
Flatten
BatchNorm ReLU
Linear 512
Upsample Conv
Lineer 10
Class Logits
(a) Classifier
(b) Querier 9n
Figure Architectures used for image classification on MNIST, KMNIST, and Fashion-MNIST.
C.4 MEDICAL DIAGNOSIS ON SYMCAT, MUZHI AND DXY
Dataset and Query Set. MuZhi Wei et al. 2018) and Dxy Xuu et al. 2019) are two real-world medical datasets containing symptoms and discases extracted from Chinese healthcare websites (https: / mwwhiiiiii du com/ / and https:: //xyy..///....///////pp///p///k/ com/), where doctors provide online help based on patient's self report symptoms and online conversations. We follow the same data pro- cessing procedure as He et al. (2022). MuZhi has 66 symptoms (features) and 4 diseases (classes), including children's 's bronchitis, children's functional dyspepsia, infantile diarrhea infection, and up- per respiratory infection. Dxy dataset contains 41 symptoms for discases: allergic rhinitis, upper respiratory infection, pneumonia, children hand hand-foot-mout foot-mouth discase, and pediatric diarrhea. Last but not least, our query set Q consists of queries that correspond to asking questions about the presence of each symptom for the patient; the query-answer is either for Yes, 0 for No and -1 for Can' inn't Say.
SymCAT is synthetic medical dataset generated from symptom checking website called SymCAT introduced by Peng et al. (2018). The dataset has three versions; SymCAT-20 contains 328 symp- toms and 200 disease, SymCAT-300 contains 349 symptoms and 300 classes, and SymCAT-400 con-
20

---

Published as a conference paper at ICLR 2023
tains 355 symptoms and 400 classes. We used publically avialable version of this dataset provided by Nesterov et al. (2022) at httth::://// thub. com/ Spmmphheck/Neural... w omChecker) Our query set Q consists of queries that correspond to asking questions about the presence/absence of each symptom for the patient; the query-answer is either for Yes and O for No.
Architecture and Training. A diagram of the architecture is shown in Figure 9 We used the set architecture proposed in Ma et al. (2018). We made this choice for a fair comparison with He et al. (2022) which also used to same architecture for their partial-VAESs The input to the network is a concatenation of the query-answers {q (x-1) q E Q}, trainable positional embeddings e.j (red blocks), and bias terms b-j (blue blocks). Each positional embedding is also multiplied by the query- anere- After the first linear layer, the intermediate embedding is multiplied by query- answer mask derived from the history, which each dimension has value of for query selected in the history and 0 otherwise. To optimize our objective, we randomly initialize fo and do and train using the same optimizer and learning rate scheduler setting as mentioned in the beginning of the section. However, we train our algorithms for only 200 epochs, and linearly anneal the straight- through softmax estimator's temperature T from 1.0 to 0.2 over the first 50 epochs.
Updating the History. Let the history of query-answer pairs observed after l: steps be denoted as Sx. Since we used set architectures as our querier and classifier networks for these datasets, as proposed in Ma et al. (2018). S₁ is represented as a set consisting of embeddings of query- pairs observed so far. T'ee next query, 9k+11 a argmax(9,, (Sx)) is a one-hot vector of dimension equal to the size of the query set used. For a given observation ghh we update Sk using 9k+1 as follows:
Let M be matrix of size [) x d where every row corresponds to query- evaluated at ob and d is the size the embeddings used for representing the query-answer We obtain the answer corresponding to the selected query 46+1 by performing matrix-vector product, that is, gk+ (2. I.
. We update the history to S by concatenating (++1 (2:00) to Sk
C.5 IMAGE CLASSIFICATION ON CIFAR-10 10 AND CIFAR-100
Dataset and Query Set. CIFAR-(10,100) Krizhevsky et al. 2009) are natural image datasets that contain (10, 100} different classes of objects. They contain 50,000 training images and 10,000 testing images. Each RGB image is of size 32 x 32. We design our query set Q following Rangrej & Clark (2021) consisting of all x 8 overlapping patches with stride 4. This results in a query set size [Q] of 49. The inputs to the classifier fe and the querier 9, are full-sized 3 x 32 32 masked image, with masked pixels zeroed out if they are not part of the current History.
Architecture and Training. For CIFAR-10, the architectures used for the classifier fo and querier 9n are both Deep Layer Aggregation Network (DLA) (Yu et al., 2018). fe and g, do not share any parameters with each other. An out-of-the-box implementation be found here: https::/ ttt.b//tt..u.g.gg// www.wwwo///oo..ooo.oo/. in hwtttoyccccccccoocoooooooooottcc c /aaraallloooooooeeaaaaeeaaeeeeoe hlllob/mattt. master/ models /dla . py For CIFAR- 100, the architectures used for the classifier fo and querier In are both DenseNet169 (Huang et al. 2017). fe and 9n, do not share any parameters with each other. An out-of-the-box implementation was used and can be found here: httpp:: //gi thub. com/ kuangliu/ /ttiii/pptttta orc- ch- i far b ob master models/ densenet. by The only change made the architectures the last layer, which the dimensions depend on the number of classes or the size of the query set Q.
used and can
During training, we follow standard data processing techniques as in He et al. (206)). In CIFAR- 10, we set batch size 128 for both initial and subsequent sampling stages. In CIFAR-100, we set batch size 64 for both initial and subsequent sampling stages. For both CIFAR-10 10 and CIFAR- 100, we randomly initialize fe and In, and train them for 500 epochs during Initial Random Sampling using optimizer Adam and Cosine Annealing learning rate scheduler, with settings mentioned above. During Subsequent Adaptive Sampling, we optimize using Stochastic Gradient Descent (SGD), with learning rate 1r=0. 01 and moment um=0. 9 and Cosine Annealing learning rate scheduler, with max=50, for 100 epochs.
21

---

Published as a conference paper at ICLR 2023
91(X)
1x
1
Qy(X)-
a/o (9) 400
x
baj
1x1
Linear 1024
Mask 1024
Embedding 1024 [Q]
MaxAggregate ReLU
Aggrogated Embodding 1024 x
Linear 2000
BatchNorm ReLU
Linear 500
BatchNorm ReLU
Linear
Linear [Q]
Class Logits
Query Scores
[Q]
Figure 9: Architecture used Medical Diagnosis tasks on SymCAT, MuZhi and Dxy. The classifier fo and querier In share parameters in this architecture. [Q] is the size of the query set, which also corresponds to the number of features. C' is the number of classes, depending on the dataset.
Updating the History. The method of updating the history is similar to that for MNIST, KMNIST, and MasHi as mentioned C.3 For given observation obs we update the history Sy. using 1 follows:
We reshape 9k+1 from vector of dimension 49 (the number of queries) to 2D grid of dimension 7 x 7, denoted by 9
(c+1 then converted to a binary matrix with 1s the location corresponding to the queried 8 8 patch and Os everywhere else via 2D transposed convolutation operation with a kernel of all Is of size 8, stride and no padding.
We then obtain the query-answer by performing hadamard product of the convolved out- put (in the previous step) with abs This results in a masked image, gr (æ*bs), with the queried patch revealed and 0 everywhere else.
22

---

Published as a conference paper at ICLR 2023
Finally, update the history to Sk+1 by adding this query Sk- Any pixel that is observed (unmasked) in â (z and is also observed in the history Ss. is handled by the transformation Sk+1 [ + Sk(i. if Sk+1[i,7] = [S.
The entire process can be summarized as,
1 S₁ + TransposedConv22(@::1 xb5
vii,j) (Number of pixels in image)
Ss+1li, S
if 111111.51 25k(i,j] (11)
Se Set1 [k+1b,,
otherwise
D STRAIGHI-THROUGH SOFTMAX ESTIMATOR
As mentioned in $33 in the main text, we employ the truight-through softmax gradient estimator for differentiating through the a argmax operation. We will now describe this estimator in detail. Consider the following optimization problem,
min ((argmax(0))
(12)
PER
Let Z == argmax(0). We will assume f is differentiable in its input. The straight- softmax estimator of the gradient of f w.r. 0 is defined as,
0f dsoftmax,
ST f
Oz
d0
where softmax, (0)
and is the temperature parameter. No-
Σd Eime
tice that -o softmax, (0) argmax(()) Thus, we replace the gradient of the argmax operation which is either 0 almost everywhere or doesn't 't exist with surrogate biased estimate.
Equation 12 can then be optimized using the straight-through estimator by iteratively carrying out the following operation,
0 = - -
where 77 is the learning rate.
In our experiments we start with T = 1.0 and linearly anneal it down to 0.2 over the course of training.
E ABLATION STUDIES
In $3.3 we discussed two possible architectures for operating on histories of arbitrary sequence lengths; the set-based architectures (as in Figure ( and the fixed-sized input masking based chitectures (as in Figure ( In Figure I0 we compare the two architectures on the same task of bird species identification using the same query set (see Table [T). We that the fixed-sized input masking based architecture performs better in terms of avg. number of queries needed to get the same performance. Based on this observation, we use the latter architecture in all our experiments except on the medical datasets, where we used the set-based architecture for fair comparison with the BSODA method which uses a similar set-hased architecture for their partial-VAEs
In 3.3 we discussed that a sampling distribution Ps that assigns positive mass to every element in K would make learning a good querier function challenging since the network has to learn over an exponentially (in size of Q) large number of histories. Instead we proposed to sequential bias the sampling according to our current estimate of the querier function. We validate the usefulness of this biased sampling strategy in Figure II] In most datasets observe that biasing the sampling distribution for S helps learn better querying strategies (in terms accuracy vs. explanation length trade-offs).
23

---

Published as a conference paper at ICLR 2023
1.00
0.75
Test Accuracy
0.50
based architecture
fixed-sized inputt mascing based architectures
0.00
25
50
75 Avg. # of queries
100
125
150
Figure 10: Comparison of accuracy v/s explanation length (avg. number of queries) curves for the set-bastr sct-based and fixed-sized input masking based architectures the CUB-200 dataset.
Notice that most datasets, biased sampling without the initial random sampling ultimately ends up learning slightly better strategy (in terms of accuracy vs. explanation length trade-offs), However, since biased sampling requires multiple forward passes through our querier network to generate histories, it is much slower than the initial random sampling (IRS) scheme for Ps- Thus, when computational resources are not a concern one could do away with the initial random sampling but under computational budget, the random sampling allows for finding quick solution which can then be finetuned using biased sampling. This finetuning will potentially require fewer epochs to get good performance than training using biased sampling from scratch.
F EXTENDED RESULTS
we show the trade-off between accuracy and explanation length (avg. number of queries) on KMNIST and Fashion-MNIST datasets as the stopping criterion is changed. In both these datasets, the "MAP criterion" is used as the stopping criterion. V-IP performs better than RL- based RAM and RAM+ on both these datasets. V-IP competitive with G-IP eventually surpassing it in terms of accuracy for longer query- answer chains.
In Figure 12
In addition, Table shows extended results for AUC values for test accuracy versus explanation length curves for different datasets. A simplified table is shown in Table
Table 4: Extended results for Table 2 Every method, except G-IP, was repeated 5 times with different seed.
The high computational cost of G-IP (one run of inference the MNIST test set takes few weeks) makes it infeasible repeat G-IP multiple times for computing standard-deviation values.
Dataset
Random
RAM
RAM+
G-IP
V-IP (Ours)
CUB
0.557 = 0.002
0.662 + 0.002
0.695 = 0.004
0.736
0.716 + 0.008
NuffingtonNews
0.423 + 0.015
0.389 + 0.010
0.431 + 0.003
0.691
0.664 + 0.002
MNIST
0.868 + 0.002
0.916 + 0.005
0.920 + 0.007
0.964
0.956 + 0.002
KMNIST
0.775 + 0.003
0.832 0.003
0.841 - 0.002
0.872
0.911 + 0.008
Fashion-MNIST
0.735 0.029
0.770 + 0.003
0.804 0.010
0.831
0.849 + 0.010
G COMPARING V-IP WITH BLACK-BOL DEEP NETWORKS
An important aspect of the framework introduced by Chattopadhyay al. 2022 is that the end- user defines queries that are interpretable to them. Given this set of queries, Q. V-IP learns to efficiently compose them into concise explanations for model predictions (in terms of query- chains). This begs the question, how much do we loose in terms of performance by constructing an interpretable Q? In Table we report results studying this question.
"Acc. w/ V-IP given e" is the test accuracy obtained by V-IP after termination using our stopping criterion. "Acc. w/ V-IP given Q(X)" is the accuracy the classifier network (trained jointly with the
24

---

Published as a conference paper at ICLR 2023
1.00
1.00
1.00
Test Accuracy
0.75
Test Accuracyy
0.50
0.50
0.50
0.25
0.25
0.25
5BS
SBS
0.00
0.00
0.00
Aug. Queries
Aug.
Queris
Avg.
MNIST
(h) MASSiO
KMNIST
0.7
0.7
0.7
0.6
0.6
Rest Accurecy
0.55
0.5
0.5
0.4
0.4
02
0.2
0.2
0.0
12
16
20
0.0
12
16
20
0.0
8
12
16
20
Queries
of Queries
(d) symCATA AT-200
(e) CAT-300
(l) symCAT-400
1.00
Test Accurecy
0.75
Tost Accurazy
0.5
0.2
0.25
0.00
282
10
20
30
40
50
200
400
600
800
1000
Avg. Quer
Avg. 4 of Querlis
Avg. # Queries
(g) CUB
(h) HuffingtonNews
(i) CIFAR-10
Figure 11: Accuracy v/s Explanation length (avg. number of queries) curves for different datasets with and without the successive biased sampling history S. denote training with Initial Random Sampling only as IRS; training with Subsqeuent Biased Sampling only as SBS; and training with IRS, followed by subsequent fine-tuning with SBS as IRS SBS.
1.00
1.00
Test Accuracy
0.75
Test Accuracy
0.75
0.50
0.50
0.25
0.25
0.00
Fashion-MNIST
0.00
KMNIST
20
30
40
50
60
70
0
10
20
30
40
50
60
70
80
Avg. of Queries
Avg. # of Queries
Variational-IP
Generative-IP
Random
Figure 12: Tradcoff between accuracy and explanation length (average number of queries) for Fashion-MNIST (left) and KMNIST (right). Reported curves averaged over runs with shaded region denoting the standard- deviation.
queried network using the Deep V-IP objective) obtains when seeing all the query answers Q(X). In all data sets, V-IP learns to predict with short explanations (avg. number of queries) and a test accuracy in proximity what can be achieved if all answers were observed (col 6).
25

---

Published as a conference paper at ICLR 2023
'Acc. w/ Black-Box given (XX) reports the accuracy black-box deep network obtains by training on feature vectors comprised of all query answers Q(X) using the standard cross-entropy loss. Columns 6 and 7 show that training classifier network with the Deep v-IP objective results in only a minor loss in performance compared to training using the standard supervised classification cross-entropy loss.
"Acc. w/ Black-Box given X" reports test accuracies obtained by training black-box deep networks on the whole input X to produce a single output (the classification label). Comparing these values with the accuracies reported in col 6 we see that basing predictions on an interpretable query set, almost always, results in a drop in accuracy. This is expected since interpretability can seen as constraint on learning. For example, there is drop of about 15% for the HuffingtonNews dataset since our queries are about the presence/absence of words which completely ignores the linguistic structure present in documents. Similarly, for the binary image classification tasks (MNIST, KM- NIST and (ashiTn-MNNST) the queries are binary patches which can easily interpreted as edges, foregrounds and backgrounds. This binarization however results in a drop in performance, espe- cially Fashion-MNIST where harder to distinguish between some classes like coat and shirt without grayscale information.
Table 5: Comparison of Test Performance between prediction using V-IP with stopping criterion e, prediction using all queries, and prediction using black-box trained model.
Dataset
(Q]
Criterion (e)
Stopping
Explanation Longth
Acc. V-IP given
Acc. V-TP given ((X)
Acc. w/ Black-Box given Q(X)
Black-Box
given X
HuflingtonNews
1000
MAP (0.99)
195.89
0.672
0.712
0.715
0,865
CUB-200
312
Stability (0.001)
18.82
0.752
0,763
0.763
0,827 11
MNIST
676
MAP (0 99)
6.34
0.971
0.991
0.992
0.998
KMNIST
676
MAP (0.99)
20.34
0.916
0.958
0.951
0.98%
Fashiou-MNISTT
676
MAP (0.99)
19.42
0.872
0,876
0.884
0.967
CIFAR-10
Stability (0. (27)
9.79
0.936
0,946
0.958
0.955
CIFAR 100
49
Stability (1.438)
12.82
0.752
0.788
0.798
0.79%
H ADDITIONAL QUERY-ANSWER CHAINS
We show additional trajectories for different task and datasets: CUB-200 (Figure 13 MNIST (Fig-
ure [4). Fashion-MNISS (Figure [5}. KMNIST (Figure (6). HuffingtonNews (Figure I8), CIFAR- 10 (Figure 19 and CIFAR- (Figure 20). In every figure, we see that the correct predictions are explained by an interpretable sequence of query-answer pairs. The evolution of the posterior P(Y Q1: (2:h))) as more and more queries are asked, gives insights into the model's ss decision- making process as we see it's belief shift among the possible labels for abs This adds an additional layer of transparency to the model.
Numbbr taken from Chattopadhyay et al.
2022
where authors fine-tuned a Bert Large Uncased Trans-
former model to classify documents.
11 Number taken from Koh et al.
2020 which trained a CNN on raw images of birds from CUB-200
dataset
"Number reported from
Hu et al.
2018
13 Number reported from
Clanuwat el al.
2018)
"Numbee reported from
Xiao (2017))
"Traiined a Deep Layer
Aggregation mode
Yu ct al.
2018 to classify CIFAR-10 images from scratch.
Number reported from
Huang
2017
26

---

Published as a conference paper at ICLR 2023
shover wotched
to rolker dlack
uppar cane
baly
partars waka
na parterr suld
wing chases wingo
0.6
color black
Evendd perters
leg pdlnc
wing metermmeel meclocctoed 13. heed pattere are
celeragne
cortie Groddor
Figure 13: Examples CUB-200.
27

---

Published as a conference paper at ICLR 2023
2
goos
k = 0
k= 1
k 2
k = 3
k= 4
0.75
0.50
0.00
1123456788
0123456 6789
012 3456789
01234 56789
0123456789
gbo
k= =
k =
k = 2
k 3
k 4
k = 5
k k= 6
1.00
0.75
0.50
0.25
M 0123456789
0.00
0123456789
0123456789
0123496789
0123456789
0123456789
0123456789
obe
==
k 1
= 2
= 3
k 4
k
= 6
k= 7
1.00
0.75
0.25
| 0123466789
0.00
0123456789
0123156789
0123456789
0123456789
0123156789
0123156789
0123456789
(c)
bbs
k= 0
= 1
k 2
k =
k = 4
k k= 5
== 6
k 7
1.00
0.75
0.50
0.25
| 0123456789
0.00
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
(d)
Figure 14: Examples for MNIST.
28

---

Publishes as a conference paper at ICLR 2023
(g)
Figure 15: Examples for Fashion-Min -NIIS..
29

---

Published as a conference paper at ICLR 2023
Rellittte THO0MA0
6.575
" wagl0p0r
(b)
(c)
km1
k=2
k-4
k-3
k-d
k=5
k=
k-
(d)
Figure 16: Examples for KMNIST.
30

---

Published as a conference paper at ICLR 2023
(a)
chest
1.0
(b)
Cramps spasmo
Abusing alcohol
Sharp abdominal
2. Fain during pregnancy
Irregular heartbeat
3. Groin pain
Spotting bleeding during pregnency
0.6
Ache all
5. Abnormal involuntary movements
5. Fever
Cough
Headache
7. Nasal congestion
8. Selzures
B. Sharp abdominal pain
9. Weakness
9, Symptoms of eye
Extrapy amida Hydrocaphin hau
Prodiem distig deficieicy
Bettcaltte
Hovilove synarome
0.0
Pulmonary easinaprill Bi
Hypenatreriia
Acure kaney Injury
Hyponatremtt aegonatremiia
intestinal aiseso
Sinus bradycardis
Hypovotemit Sickle call criats Vertetrobasile insuffeiens suuffeeency Sick sinus Syndrome
intracrant hemon
Vitami 8
(novenient
(c)
3.0
(d)
Diminished
1.0
throat
1. Blindness
Fover
2. Pain eye
Cough
pain
4. Symptoms
Nasal congestion
5. Eye redness
Allengic
Itchiness eye
Shortness breath
Spots clouds vision
Painful sinuses
0.4
8. Headsche
Diminshed hearing
9. Lacrimation
Dizzinsss
10. skín rash
0.2
11. Swollen
11. Itchnnes of eyo
12. Foreign body sensation eye
12. Hoarse voice
congestion
Conductivve hearing losa
Vitamin delicieccy
Eustachan tuke tpottrcciinn (our disorter)
Diabetes soaipiiu
Conjurctvitis din to alleryy
Laryngitts
Kapeii carcomi
Seational aleertes they fever)
Priettich atoraa
14. Sharp abdominal pain
15. Sharp chest pain
16. Eye
Central retinal artery vein Astigmation
Eye alignment disorder
Chronic plaucoma
Conjunctviils due allergy
Corraa fecttonn
Diabetic Elhoppatyy Amtayopia
Chortor Phortoretintt
0.0
Figure 17: Examples for SymCAT200
31

---

Published as a conference paper at ICLR 2023
(a)
Category: Style & Beauty
(b)
Category: Travel
Headline: Kardashian's Flip Flops, Dorothy
Headline: Myanmar's Forgotten People: Traveling Through Chin State
Perkins Dress is A Cute Change (PHOTO)
Short Description: See the rest Kim's maternity gear: Want more? Be sure to check out HuffPost Style Twitter, Facebook, Tumblr
Short Description: The ethnic Chin people the tribe whose older women still wear the traditional facial tattoos number approximately million and are spread between Myanmar and neighbouring India.
0. Init
0.8
1. trump
1.0
Init
2. photo
0.6
trump
0.8
3. recip
photo
home
0.2
3. gay
0.6
5. style
4. parent
Entertainment
Politics
Queer Voices
Business
Travel
Parenting
Style & Beauty
Food & Drinks
Home Living
Wellness
0.0
0.4
6. kid
7. fashion
0.2
8. health
0.0
Entertainment
Politics
Queer Voices
Business
Travel
Parenting
style & Beauty
Food & Drinks
Home & Living
Weltness
(c)
Category: Parenting
(d)
Category: Politics
Headline: Fast-Acting Lifeguard Rescues Girl In Wave Pool (VIDEO)
Headline: Bernie Sanders: 'Low Blow' To Say Support President Obama
Don't
Vittone also describes The Instinctive Drowning Response, which does not look the scene above most parents' typical
Short Description:
Short Description: Hillary Clinton said Sanders' criticisms of Obama sounded like GOP attacks
1.0
init
1.0
0. init
trump
0.8
trump
2. photo
2. photo
3. gay
0.8
0.4
4. parent
3.
5. travel
4. parent
6. health
0.0
Entertainment
Politics
Queer Voices
Business
Travel
Parenting
Style & Beauty
Food Drinks
Home Living
Weltness
7. fashion
0.6
8. kid
9. food
10. life
0.4
11. vote
12. recip
13. feel
14. diseas
15. babi
16. mom
17. clinton
0.0
Entertainment Politics Queer Volces
Business Travel Parenting Style & Beauty Food & Drinks Home Living Wellness
Figure 18: Examples HuffingtonNews.
32

---

Published as a conference paper at ICLR 2023
k
P(Y (uak(anle))
0.50
0.25
0.00
plane
plane
Bird
plane Bird
plane
pbb
k=
k=2
<-3
PYY (Bul)=ll]]]
0.75
0.50
0:00
k=1
k=2
k=5
k=6
PtY largsshny
0.73
0.50
0:21
Figure 19: Examples for CIFARIO.
Figure 20: Examples for CIFAR100.
33


Reviews:
[{"review_id": "nQKaz65iQd", "reviewer": "Reviewer_G1eQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This articles positions itself in the context of designing \"interpretable by design\" models: models are built from the start to provide an interpretable explanation alongside their predictions. To achieve this goal, the model performs its prediction by iteratively making queries about the example to classify within a predefined set of interpretable queries. The sequence of queries serving as the explanation for the prediction. The paper follows the Information Pursuit (IP) method, where the next query is chosen by maximizing the mutual information between the variable to predict and the result of the query given the past query history.\n\nPrevious work in the IP framework learned a joint generative model over the query answers and the final prediction, using MCMC sampling on that model to compute the mutual information required to choose the next query. The paper shows that the IP selection strategy can be formulated as the solution to a variational optimization problem involving two functions: a classifier that predicts the output variable given the history of queries, and a querier, that chooses the next query. This formulation alleviates the need for learning a joint generative model, drastically reducing the computational cost.\n\nThe paper provides extensive experimental comparison with other models from the literature and on multiple tasks, proving the proposed V-IP model to be very competitive across the board.", "summary_of_the_review": "This paper proposes a new method, which is well theoretically founded and empirically shows significant computational gains compared to the state of the art. There are a few details that can be clarified, but this is a good paper.", "strength_and_weaknesses": "**Strengths:**\n- The proposed approach is an elegant and well-grounded variational reformulation of the IP strategy, which is itself a strong strategy in this context.\n- The formulation of the optimization problem and its implementation using deep neural networks is clear and detailed.\n- The experimental validation is extensive and discusses in depth the advantages and limitations of the proposed V-IP.\n- The proposed model is competitive with previous state of the art with a significantly smaller computing cost, which is a strong contribution.\n\n**Weaknesses:**\n1. Regarding the straight-through optimization of the softmax of the querier model, as discussed in appendix D this requires the following function to be differentiable wrt to the one-hot output of the softmax. In V-IP, the following function is the concatenation of the next query result to the queried dataset. How is that step made differentiable? I suppose this is related to the masking-based architecture, but the paper does not seem to explain it.\n2. This is a minor point, but I think figures 3a illustrates well how query sets consisting in observing small patches of an image are very artificial given the high-level problem at hand (interpretability). The 4th observation is the one that tips the balance of the model from cat to dog, and yet it mostly consists in a black square of background. Could that maybe illustrate some overfitting in the model?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7IhLcSQanC", "reviewer": "Reviewer_jPMz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper authors proposed a variational information pursuit for interpretable classification model / estimation scheme. Authors idea is motivated by generative variant that they denote G-IP. Authors propose a complete framework with model defintions explanation of the training scheme and proof that loss does what it is supposed to do. Finally they show with experiments how the proposed method works in contrast to baselines. ", "summary_of_the_review": "I find the ideas in the paper to be quite interesting and potentially very useful for practitioners. The main experimental results are not necessarily very compelling in terms of classifier accuracy, but in terms of inference speed they are. ", "strength_and_weaknesses": "Positives: \n- I find the paper very interesting and clearly written. \n- Idea is neat and does seem to work in practice. \n- I feel that in terms of quantitative performance it would be better to emphasize much more the speed of inference. Maybe even with some Figures, so that the message is really hammered home that V-IP is much faster than G-IP. \n- Theoretical development is also a plus. \n\nNegatives:\n- I do not understand why in (V-IP) authors need to formulate their objective as a constraint optimization task. Why not to directly optimize f,g? \n- Authors state in the Introduction that \"We empirically demonstrate the efficacy of the proposed method over generative modelling on various computer vision and NLP tasks\", but in the case of MNIST clearly V-IP is not the clear winner. I am thinking that authors should modify these statements to reflect the results more accurately. \n- Thing that is sometimes hard to do is to put plot standard deviations in Figs and mark them into the results Tables. In RL lit, this is standard practice, you need to repeat the experiments some number of times to obtain those std estimates. Please consider adding them where ever possible.\n- Clear limitation of the present paper is to have good Q set that allows for interpretation. If one constructs the set Q basically randomly, is it going to give useful information to the practitioner? It is on the other hand quite clear that if Q is very limited, then the proposed method would not work too well against non-interpretable models. Some discussions about this could be good to have. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "67Eely3-Bqp", "reviewer": "Reviewer_VaCA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method called V-IP (Variational Information Pursuit) that does a multi-step prediction to improve interpretability instead of doing a one-pass prediction like other neural nets do. In each step, only a small sets of features (i.e. \"query set\" called in the paper) are revealed and the goal is to make a prediction using the minimun number of steps i.e. part of the feature sets. It can derive interpretability becasue the subsets of features causing a big increase of the prediction of the ground truth class between steps can be seen as important rationales of why model makes such prediction.\n\nPreviously, most method resort to using generative models to model the distributions between labels and subsets of features to pick which parts of features can maximally predict the target by resorting to MCMC sampling methods (the baseline called G-IP). Or others have proposed using reinforcement learning to sequentially select the feature sets that predict the correct target. The proposed method, V-IP, instead learns to greedily choose the subsets of features that maximize the downstream classifiers to predict the target y in each step as measured in the KL divergence, which can be seen as the mutual information of the current selected features in each step. Note V-IP can be seen as a RL method that has an immediate reward and the decay factor gamma set to 0. In the classification part, V-IP experiments with set-based and mask-based classifiers to predict and find the mask-based ones perform better. In a wide-variety of datasets including images, medical diagnosises, and texts data, the V-IP outperforms recent G-IP related methods and RL-based methods. ", "summary_of_the_review": "Overall I think the authors do a great job in writing and the examples presented are interesting to see. But given the crowded space of this problem (feature subsets selection), I am hoping to see more complete comparisons and other interesting questions as suggested above. The experimental number also lacks standard deviation which I believe is important. Although I find this work slightly less original, I don't mind such work being accepted as long as there are concrete evaluations and ablation studies to make readers learn something from it.", "strength_and_weaknesses": "# Strength\n\n- The writing is clear and easy to follow. \n- The examples of interpretability shown in Fig. 3 are interesting to see.\n- I like the careful details of biased samplings and the set-based classifiers v.s. mask-based classifiers.\n- The experiments seem thorough, but some more experiments can be helpful. See below.\n\n# Weaknesses\n\n1. IMHO, the novelty side may be a little bit low since this method can be seen as a RL method with immediate reward of improving the classifiers predictions. Other inventions like initial random sampling and subsequent biased sampling are new in my opinions.\n2. G-IP seems to perform quite similarly or sometimes better than V-IP (Fig. 4) in larger datasets like CUB-200 with large query size 312. It seems contradictory to what authors state \"We thus expect the gains of V-IP to be most evident on large-scale datasets\". An ablation study that improves from small to large number of examples in a dataset may help verify what the authors claim.\n3. There is no consistent baselines across the datasets, which may make comparisons difficult. If it's easy to do, can authors also run the G-IP on the datasets in Table 3 and Figure 5 CIFAR-10/CIFAR-100 to see if the proposed method V-IP is indeed better than G-IP? Or authors can comment on why such comparisons are not easy due to code inaccessibility etc.\n4. I would love to see a more complete ablation study than the Supp. E (Fig. 11) that compare another version <1> No initial random sapling, and put a subset of results into a small table in the main text if possible.\n5. The metrics reported in the experimental section are mostly borrowed from other papers. Although it's great to directly compare to the SOTA numbers, there maybe subtle differences in the implementation leading to such result. For example, can authors please confirm fi those baselines BSODA, REFUEL in Table 3 and Figure 5 are using the same classifier architectures and training strategies the same as V-IP and the only difference lies in the strategy of selecting the features? If not, such number should not be directly compared, or some ablation studies are needed e.g. using BSODA's classifiers instead of the V-IP classifiers.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster