Formal Interpretability with Merlin-Arthur Classifiers
Authors: Stephan Waeldchen
Kartikey Sharma
Max Zimmer
Berkant Turan
Sebastian Pokutta
Venue: Submitted to ICLR 2023 (2023)
Keywords: interpretability
explainable ai

Abstract: We propose a new type of multi-agent interactive classifier that provides, for the first time, provable interpretability guarantees even for complex agents such as neural networks.   In our setting, which is inspired by the Merlin-Arthur protocol from Interactive Proof Systems, two agents cooperate to provide a classification: the prover selects a small set of features as a certificate and presents it to the verifier who decides the class. A second, adversarial prover ensures the truthfulness of the system and allows us to connect the game-theoretic equilibrium between the provers and the verifier to guarantees on the exchanged features. We define completeness and soundness metrics to provide a lower bound on the mutual information between the features and the class. Our experiments demonstrate good agreement between theory and practice using neural network classifiers, and we show how our setup practically prevents manipulation.

FORMAL INTERPRETABILITY WITH MERLIN-ARTHUR CLASSIFIERS
Anonymous authors Paper under double-blind review
ABSTRACT
We propose new type of multi-agent interactive classifier that provides prov- able interpretability guarantees even for complex agents such as neural networks. These guarantees consist of bounds on the mutual information achieved by the features selected by this classifier. Our results are inspired by the Merlin-Arthur protocol from Interactive Proof Systems and express this bound terms of mea- surable metrics such soundness and completeness. We introduce the notion of Asymmetric Feature Concentration which relates the information carried by sets of features to the one of individual features. Crucially, bound does not rely optimal play by the agents nor on independently distributed features. We verify framework through numerical experiments image classification problems.
INTRODUCTION
Safe deployment of Neural Network (NN) based AI systems in high-stakes applications requires that their reasoning be subject to human scrutiny. The field of Explainable AI (XAI) has thus put forth number of interpretability approaches, among them saliency maps (Mohseni et al., (202T) and mech- anistic interpretability (Olah et al. 2018). These have had some successes, such as detecting biases in established datasets (Lapuschkin et al. 2019). or connecting individual neurons to understandable features (Carter et al., 2019). However, these ap- proaches are motivated purely by heuristics and come without any theoretical guarantees. Thus, their success cannot be verified. has also been demon- strated for numerous XAI-methods that they be manipulated by a clever design of the NNs (Slack) al.) 202T 2020 Anders et al. 2020 Dimanov et al. 2020). On the other hand, formal approaches interpretability run into complexity barriers when applied to NNs and require an exponential amount of time to guarantee useful properties (Macdnn-
Merlin-Aree Arthur Classifier
Space
Space
Feature Selector Merlin:
Feature Space E
Class Space e
Feature
Classißer
"Bird"
Arthur:
Figure I: The Merlin-Arthur classifier consists of two interactive agents that communicate over an exchanged feature. This feature serves as an interpretation of the classification.
ald al. 2020 Ignatiev al. 2019) This makes any "right explanation." codified in the EU's
GDPR [Goodman & Flaxman 2017). unenforceable.
In this work, we design a classifier that guarantees feature-based interpretability under reasonable as- sumptions, thus overcoming both theoretical and computational shortcomings. For this, we connect classification to the Merlin-Arthur protocol (Arora & Barak 2009) from Interactive Proof Systems (IPS), see Figure For easier illustration, we split the unreliable prover into cooperative Merlin and an adversarial Morgana. Merlin aims to send features that cause Arthur to correctly classify the underlying data point. On the opposite side, Morgana selects features to convince Arthur of the wrong class. Arthur does not know who sent the feature and allowed to say "Don' 't know!" he cannot discern the class. We can then translate the concepts of completeness and soundness from IPS to our setting. Completeness describes the probability that Arthur classifies correctly based on features from Merlin. Soundness the probability that Arthur does not get fooled by Morgana, thus

---

either giving the correct class answering "Don't know!". These two quantities can be measured on a test dataset and are used to lower bound the information contained in features selected by Merlin.
1.1 RELATED WORK
Interactive classification has emerged part of the effort to design inherently interpretable classifiers Lei et al. (2016) Li al. (2016); Chen al. (2018); Bastings et al. 2019). In this setup, the feature selec- tor chooses a feature from a data point and presents it to the classifier who decides the class, see Figure 1. The classification accuracy is meant to guarantee the informativeness of the exchanged features.
Original Images:
PCC "boel"|'was" ) 0.5
P(C "sde"|'soa"
1(C: ; :"sea"" 0
Masked Images:
P(C "boot"""soa"""
P(C "ste"""""""" =
S(C ; "Sooa"
However, it was noted by Yu et al.] that the selector and the classifier can cooperate to achieve high accu- racy while communicating over uninformative fea- tures, see Figure 2 for an illustration of this "cheat- ing". Thus, one cannot hope to bound the informa- tion content of features via accuracy alone. The au- thors propose to include an adversarial feature clas- sifier to remedy this fact, however do not provide any bounds. Irving et al.] introduce a different ad- versary, and discuss in Appendix A.4 why this approach cannot yield bounds similar to the ones in our work. Chang et al.] include an adversarial se- lector to prevent the cheating. The reasoning is that any "cheating" strategy can be exploited by the ad- versary to fool the classifier into stating the wrong class, see Figure B] for an illustration. [Anil al.] investigate scenarios in which this three-player setup converges
'ooat! 4
"Esle!"
Figure 2: Illustration of "cheating" behaviour. In the original dataset, the features "sea" and "sky" appear equally in both classes "boat" and "island"" In the new set of images that Merlin creates by masking features of the original image, the "sea" feature is visible only in the images la- belled "boat" and the "sky" feature is visible only in the images labelled "island". Thus, these fea- tures now strongly indicate the class of the im- age. This allows Merlin to communicate the cor- rect class with uninformative features in con- trast to our concept of an interpretable classifier.
equilibrium of perfect completeness and soundness. However, both works assume that the players can play optimally. This, however, is unlikely in practice, since the general feature selection problem is hard Waeldchen et al. (2021). Optimal play would thus amount to an exponentially expensive search problem similar to Chattopadhyay et al. (202)). In our work, we rather rely the relative strength of the cooperative and the adversarial provers which can both be realised with imperfect strategies.
It has been shown that the optimal strategy for the prover is to select the features that have the highest mutual information with the class Chang et al. (2019). This demonstrates a strong theoretical link between a game equilibrium and the feature quality. However, the authors rely on the assumption that the features are independently distributed in each class, but in almost all types of data there are strong correlations between features. We do not make this assumption, but rather define Asymmetric Feature Correlation as an important property of datasets to draw conclusions about feature quality.
1.2 CONTRIBUTION
Our framework requires few constraints on the classifier and is thus applicable to wide range of tasks. Similarly, our results hold for general feature spaces, allowing free choice for the practitioner, e.g., parts of an image up to a certain size, or functional queries about the input.
1. We prove lower bound for the mutual information of the exchanged features with the true class of the data point. This bound does not rely on the features being independently distributed, nor on restricting the strategy of the provers.
2. We introduce Asymmetric Feature Concentration as a possible effect that complicates drawing conclusions about individual features using the informativeness of feature sets. We show how to circumvent it in Theorem 2.8 or include it explicitly as in Theorem 2.1
3. We numerically demonstrate how the interactive setup prevents the manipulation that has been demonstrated for other XAI-methods. Furthermore, we evaluate our theoretical bounds on the MNIST dataset for provers based on either Frank- Wolfe optimisers or UNets.
2

---

Sang
"DDn'tt know! V know!"
"Do''s
Doc''t know! X
Inde!" X "Bow!"" X
know! X
Boot"" v
"ale!"
a)
Figure 3: Strategy evolution with Morgana. a) Due to the "cheating" strategy from Figure 2 Arthur expects the "sea" feature for boats and the "sky" for islands. Morgana can exploit the situation and send the "sky" feature to trick Arthur into classifying "boat" image To not be fooled into stating the wrong class when represented with ambiguous feature, Arthur refrains from giving a concrete classification. c) Since Arthur does not know who sends the features, now cannot leverage the uninformative features sent by Merlin. d) Merlin adapts his strategy to only send unambiguous features that cannot be used by Morgana to fool Arthur.
"island" (and vice versa with the "sea" feature). h)
2 THEORETICAL FRAMEWORK
What reasonably constitutes feature strongly depends the context. In Interpretability research, one often considers cutouts from the original data point, but also more general functional queries. Our results do not depend on the specific form of the feature. We thus opt to leave the definition abstract and define a feature as the set data points that contain it. This also has the advantage to let us reason about feature spaces in terms of graphs. We make use of this in Appendix A.4 and proof via counterexample that the debate setup of Irving et al. (2018), where Arthur has access to features of both Merlin and Morgana, cannot lead results of the same generality
Definition 2.1 (Feature Space). Given a dataset D, we call a set Σ C 2D feature space on D (i) all data points have at least one feature, i.e. UE D, (ii) the empty set is contained as a default feature, i.e. Ø E Σ, (iii) there are only finitely many features per data point i.e., maxxen e E E cc.
The set D is possibly infinite, e.g. the set all images of hand-written digits. a distribution on this set. The finite training and sets, e.g. MNIST, for our algorithms are assumed to be faithful samples from this distribution. We say data point x contains a feature & E Σ if E Φ.
One important practical example of feature space is given in Example 2.2 sponds to a subset of pixels of size in an image x, and any data point that has the same values on the subset, i.e., Ys Xs. contains the same feature.
Every feature corre-
Example 2.2 (Features as partial vectors of size k). Let D c [0, For [d], we define a feature space corresponding to partial vectors with support of size k subsets as
Σ= == U U
= x
xED sc
We now define a data space. For notational simplicity, we restrict ourselves to two classes.
Definition 2.3 (Two-class Data Space). We consider the tuple D ((D, a, D), c, E) two-class data space consisting of the dataset D C [0, 1]a. sigma algebra and probability distribution D along with the ground truth class map e D {-1,1] and the feature space E.
The class imbalance B of two-class data space is maxie(-1,1) Fx-Dlc(x) = 1//xx-ll(xx) = =
Note that assumption on the ground truth class map requires that there be unique output for any given input. This may not necessarily be true for many data sets. We now introduce the notion of feature selector (as prover) and feature classifier (as verifier).
Definition 2.4 (Feature Selector). For given dataset D, we call M feature selector, if
M: S.l. Vx E D (x E M())) V (M(x)= =
which means that for every data point x E the feature selector M chooses a featue that is present in returns the empty We call M(D) the space of all feature selectors for dataset D).
3

---

Definition 2.5 (Feature Classifier). We define feature classifier for feature space E as function A: Σ + 0, 1}. Here, 0 corresponds to the situation where the classifier is unable to identify a correct class. We call the space of all feature classifiers A.
2.1 INFORMATION MEASURES: CONDITIONAL ENTROPY AND AVERAGE PRECISION
We consider a feature to carry class information it has high mutual information with the class. For given feature ø E Σ and data point y D the mutual information is defined as
(c(y):y E Φ) == Hy-D(cly)) When the conditional entropy Hy~p(c(y) ly E Φ) goes to zero, the mutual information becomes maximal and reaches the pure class entropy Hy-D(cly)) which measures how uncertain about the class a priori. A closely related concept is precision. Given a data point x with feature Ø. precision is defined pretability by Ribeiio et al.) (2018) and Narodytska et al. (2019). It can be used to bound conditional entropy and thus mutual information. We now extend this definition to feature selector.
Hyyy((c() y E ().
IP (PyyD(c(y) c(x) y E ø) and was introduced in the context of inter-
Definition 2.6 (Average Precision). For a given two-class data space ((D, a, D), c, E) and a feature selector M E M(D). define the average precision of M with respect D
QD(M) == Ex-D-Py-wloee
= c(x) ly E Mx)]]
The average precision QD (M) can be used to bound the average conditional entropy, defined as Hx,y~D (cly) y M(x)) == Ex-D (ot.eHHyyyylr()) ly E Mx))),
and accordingly the average mutual information. For greater detail, see Appendix B We can connect QD(M) to the precision of any feature selected by M in the following way.
Lemma 2.7. Given D = ((D, D) D),c,), 2) a featur selector M E M(D) and d E [0, 1]. Ler D, then with probability 8- (1 QD (M)), Mxx selects feature é, s.f.
Pywple(y) = c(x) E o) 2 1-
The proof follows directly from Markov's incquality, see Appendix B We will now introduce a new framework that will allow us prove bounds on (M) and thus assure feature quality. For I and H, we will leave the dependence on the distribution implicit when it is clear from context.
2.2 MERLIN-ARTHUS CLASSIFICATION
For feature classifier A (Arthur) and two feature selectors M (Merlin) and M (Morgana) we define
E M, == E D A(M(x)) + c(x) V A [()) -
(1)
the set of data points for which Merlin fails convince Arthur of the correct class Morgana is able to trick him into giving the wrong class, in short, the set of points where Arthur fails. We state the following theorem connecting the competitive game between Arthur, Merlin and Morgana to the class conditional entropy.
Theorem 2.8. [Min-Max] Let M E MM() be feature selector and let
6M = min max PXWD x E E.,M... AEA MEM
Then there exists set D' D with P E D2 eM such that for DD = o' have Q (M) =1 and thus Hxy-Dx(cly) Iy E M()) = 0.
The proof is in Appendix B. This theorem states that Merlin's strategy allows Arthur to classify almost perfectly, i.c., small EM. then there exists dataset that covers almost the entire original dataset and on which the class entropy conditioned on the selected features is zero. Note that these guarantees are for the set D' and not the original set D. A bound for the set D, such as QD(M) Z - EM, is complicated by a principle we call asymmetric feature concentration (AFC).
Definition 2.9 (Asymmetric feature concentration). Let ((D, a, D), 2) be two-class data space, then the asymmetric feature concentration & is defined as
PX x x x UF PXWD xx x
R max max E By~Dilur lE(-1,1) PCE FCE
max OEF s.t. YEP
4

---

1=-1: One fish many fruit
1=1: One fruit many fish
Figure 4: Exampic of dataset AFC K. 6. The "fruit" features are concentrated in one image for class 1 1= -1 but spread out over six images for 1 (vice versa for the "fish" features). Each individual feature not indicative of the class as appears exactly once in each class. Nevertheless, Arthur and Merlin can exchange "fruits" to indicate "I = 1" and "fish" for "I -1". The images where this strategy fails or can be exploited by Morgana are the two images on the left. Applying Theorem 2.8 we get & and the set D' corresponds to images with a single feature. Restricted D', the features determine the class completely,
Asymmetric Feature Correlation: AFC describes possible quirk of datasets, where set of features is strongly concentrated data points in another. We give an illustrative example in Figure and derive the formal definition in Appendix B If a data space D has a large AFC K, Merlin can use features that individually appear equally in both classes (low precision) points. Morgana can only fool Arthur in the other class where these features are highly concentrated, thus only in a few data points. This ensures a small 6y even with uninformative features.
few data points in one class and spread out over almost all
indicate the class where they are spread over almost all
Though it is difficult to calculate the AFC for complex datasets, we show that it can be bounded above by the maximum number of features per data point D.
Lemma 2.10. Let D ((D,o, o, c),c,E) be two-class data space with AFC of K. Let K maxxED K E
Σ
x E o
be the maximum number of features per data point. Then S K.
We explain further in Appendix
B
The number K depends on the type of features one considers.
2.3 REALISTIC ALGORITIMMS AND RELATIVE SUCCESS RATE
In Theorem 2.8. assume perfect Morgana, which is only practical for simple datasets. Con- sider the UCI Census Income dataset Dua & Graff] 2017) with 14 dimensions. When restricting features to a maximal size of seven, the search space haustive search. Contrary to this, modelling the UCI data distribution is still an involved task, and when done incorrectly, Ieads to incorrect explanations Frye et al. (2020). Our approach is therefore advantagcous for low-dimensional datasets often used in recruitment and criminal justice, where interpretability is crucial. However, we also aim to apply our setup to high-dimensional datasets, where exhaustive search is not possible.
most (14) 3432, within range for ex-
The feature selection problem is as follows. Given x E and a feature classifier A, we define
M ' 1) := arg max / A()).
AET.
Here, MM returns mask that convinces Arthur of class / if possible. Given fixed Arthur, M()) = (*(x, c(x)) and M(x = Mx -c(x) represent the optimal strategy for Merlin and Morgana, respectively. Henceforth, we will consider algorithms that allow Merlin and Morgana approximate M*. Their relative strength is captured in the following notion:
Relative Success Rate: Morgana only has to find features successfully found by Merlin, albeit in
a different class. The question is how much the rest of the features, which are not indicative of the class, influence the probability of success. In Appendix B we derive the notion of relative success rate a, i.e., the success rate of Morgana relative to Merlin for finding the same features. We give an artificial example of worst-case data space that illustrates this idea in Figure [3 We argue that realistically, we can ensure a large a by using an algorithm for Morgana that is at least as powerful the one for Merlin. Together with the AFC, this allows to state the following theorem.
5

---

Definition 2.11 (Relative Success Rate), Ler ( c, Σ) be two-class data space. Let A A and M: D {-1,1} - Ed an approximation for M, M E MM().. Then the relative success rate a of M with respect to A, M and D is defined as
Px-D_ min 1E(-1,1) PEA PX
min
Theorem 2.12. Let D = ((D,a, D),,),,,, C, be a two-class data space with AFC of k and class imbalance B. Let A E A, and M, M E M(D) such that M has relative success rate of a with respect to A,M and D. Define
1. Completeness:
min (E(-1.1)
PXND: (A(M())((())) = =(xx) ECo
max Px-D, A (M)) -c((x) ESI (E(-1.1)
2. Soundness:
where Dt is the data distribution conditioned on the class I. Then it follows that
KS0K leg
Qd(M) 2 6c 1 KO B-
The proof is provided in Appendix The core assumption we make when comparing our lower bound with the measured average precision in Section 3is the following. For our numerical bounds make sense we have to rely on the following assumption:
Assumption 2.13. The AFC i. of and the relative success rate a of M w.E.t. A, M, D are O(1).
Both x and a are difficult to estimate for high-dimensional datasets, but they offer clear guidelines on how to think about your dataset and algorithms in terms of interpretability. We numerically evaluate this assumption in Section 3.2 on a dataset simple enough to actually calculate QD(M).
Finitely Sampled and Biased Dataset We usually have access to only finitely many samples of dataset. Additionally, the observed samples can be biased as compared to the true distribution. We prove bounds for both cases in Appendix B.5 We show that any exchanged feature is either informative, or it is incorrectly represented in the dataset- thus highlighting the bias!
NUMERICAL IMPLEMENTATION
We illustrate the merit of framework with experiments on the UCI Census Income dataset and on the MNIST handwritten digits dataset (LeCun et al. 1998).
First, we describe how train the agents Arthur, Merlin, and Morgana in general r-class interac- tive learning setting for image data of dimension d, where d E N. We explain in Appendix A.55 why we chose multi-class neural network for Arthur and compare with the approaches of Chang et al. (2019) Anil Anil et al. (202T). The training process for tabular data, like the Census dataset, is
equivalent and a detailed overview is provided in the appendix.
Arthur is modelled by feed-forward neural network. He returns a probability distribution over his possible answers, so let A : j0, 1] + [o, 1](++1), corresponding to the probabilities of stating class or don't know". The provers select set S of at most l pixels from the image via a mask s E Bg where Bi is the space of k-sparse binary vectors of dimension d. A masked image x random value. We define the Merlin-loss L as the cross-entropy loss with regard to the correct class, whereas the Morgana-loss Løf considers the total probability of either answering the correct class or the don't know" option, so
has all its pixels outside of S set baseline
La (A, x, s) = - logo(AA x)o(x)) and I, (A, - log log(A(s x))o + A(s x)sx)))
The total loss for Arthur then
La (A) = (1 (M (7 Mx)))

---

where y [0, is a tunable parameter. In our experiments, choose Y 0.5 since always want to ensure good soundness. We compare different y in Appendix [ Note that Merlin wants to minimise LMs whereas Morgana aims to maximise L M In an ideal world, they would solve
M(x arg min Las (A,x,) and M(x) arg max I. 37 (A, x,
S
SEB
The above solutions can be obtained either by solving the optimisation problem (Frank- Wolle solver (Macdonald et al,, (02T)) or by using NNs to predict the solutions (UNet architecture). We kept our training routine simple by looping over the three agents and describe the details of the training algorithm and architectures Appendix C
3.1 PREVENTING MANIPULATION
Since existing XAI algorithms come without guarantees, they cannot exclude the possibility for manipulation. Indeed, arbitrarily changing the interpretation by slightly changing the classifier has been demonstrated for numerous XAI approaches. [Slack et al.) fool LIME and ShAP by making use of the fact that these methods sample off-manifold evaluations of the classifier. We are robust against this approach, since the Merlin-Arthur classifier only takes on on-manifold inputs. Dimanov iet al., HHo et al.j and [nndrr et al.) optimise manipulated classifier networks to give the desired target explanations by penalizing any deviation. The equivalent for our setup is to put a penalty on Merlin to hide the true (potentially biased) explanations in the exchanged features. This scheme is unsuccessful for a Merlin-Arthur classifier. Indeed, for this setup we show numerically that either: (i) The bias becomes visible, (ii) Morgana can exploit the setup, i.e., soundness is low or (iii) the completeness, i.e., prediction accuracy, drops.
We demonstrate this on modified UCI Census Income datase We train classifier to discriminate by "ex"-one one of the remaining 12 features for every data point. We change the Merlin-loss to
(A, :- LM (A, x) + S||ssxx
where B > 0, to train Merlin to hide the sensitive "sex" feature. We then train the Merlin-Arthur classifier to accept only men and set k to only send one feature. We compare a setup where soundness is ignored to one where choose y such that soundness of least 90% is achieved. Note that the class map for the Census Income data set is not unique, i.c., there are duplicate out- comes for exactly the same input. However, only small fraction of data points (0.6%) have this issue.
The results are illustrated in Figure 5 When soundness is ignored (? 0), setting 3.5 causes Merlin to hide the "sex" feature and communicate "sex" via selecting "education" " for men, "working hours" for women. When soundness is required (? 0.67), Merlin starts reveal the "sex" feature again. Increasing the penalty to 3 = 10, causes him to hide "sex", but now the prediction accuracy reduces 0.45, i.c., close chance and thus ceasing the discrimination. When high soundness is required, Merlin is unable to both discriminate and hide his bias
3.2 EVALUATION OF THEORETICAL BOUNDS
We illustrate our framework on the MNIST dataset restricted to two classes and present the results as evaluated on the test dataset. We use Theorem 2.12 to calculate a lower bound on the average precision QD(M) for two different pairs of classes. We compare three different setups of feature selectors, one with Frank- Wolfe optimisers (Opt), optimiser (Hybrid), and one where we use UNets for both (Net). For the purpose of numerical experiments, we assume that the MNIST dataset has an AFC of 1. This is needed for numerically calculating the lower bound on average precision. It implies that features which individually provide evidence for a particular class do not cumulatively provide evidence for a different class.
where Merlin is UNet and Morgana an
In Figure 6 we see that the lower bound is tight for larger masks, but drops off when & is small. One reason for this is that for small masks, Arthur tends to give up on one of the classes, while keeping the completeness in the other class high. Since the bound considers the minimum over both classes,
For this experiment, we have removed the "relationship" and "marital status" features, since they strongly correlate with See Appendix C.4 experiments that include "relationship" and "marital-status..
7

---

Compirtenes 100%
Completnness 1002
Grummny
0.8
0.6-
1b)
Belatree
04
7
0.4
0.0
0.0
Oceumaee
Soundraas 93425
Ocamne
Saemalatse 90L1XX
6.6-
== 5.5
== 10
0.4
0.67
6.4+
0.2
ettasties
prriaatios
sexr
copttabkon
loums por wook
malia reandry Iarona
marerdow
niscation
orasqatio
ispisllgett patas
caparal
lenati pre-sook
and Prestaatrr
Clasati by Mediin
Closse by Morqun
Figure 5: Hiring only while hiding "sex" as the explanation. 1. No soundness is required (7 0). a) Merlin has no punishment for showing "sex" (8 = 0). sends Arthur the "sex" feature and they discriminate successfully (high completeness). b) Merlin is incentivised not to use "sex" (8 0). He successfully commu- nicates the "sex" to Arthur via different features, here "hours per week" and "cducation". Morgana can exploit this strategy with the same features switched. 2. High soundness is required (r 0.67). Merlin either shows the "sex" feature despite the punishment (3 3.5) and achieves high completeness, b) hides the "sex" feature (3 10) and reduces completeness below 50%, which corresponds no discrimination.
Opt
Hybrid
Example Features
10
Z
2
2
22"
V8
0.4
7
2
0.2
1.0
4
"6"
VS
"9
0.4
f
QD(af)
(Q(M))-oumn
Figure 6: Left: For four different sctups Merlin and Morgana, we compare the lower bound on Qp (M) with the experimental results on the MNIST dataset. The top row is for the labels ("2", "4"). and the bottom row for ["6", " The bound is tight for large masks, but loosens sharply for very small mask sizes k. Right: Examples of the features selected by Merlin for two images. For the "4" feature, there 13 images in MNIST that share all them of class "4" (we show four here). For the "2" there are 16 images, all them in "2".
it becomes pessimistic. Regularising Arthur to maintain equal completeness, is potential solution, but this requires global information that for a single batch can only be roughly estimated.
We see in Figure 6 that when Merlin and Morgana are represented by the same method (both optimisers or NNs), the bound is the tightest. In our hybrid approach, Merlin is at a disadvantage, since he needs to learn general rule the training set select good features, whereas Morgana can optimise directly on the test set during evaluation. It appears that the Merlin network is not able to perform well as the optimiser. In Appendix C show eтror bars sampled over 10 training runs. The training results have greater variance for small masks. This because there no optimal strategy for Arthur, who cycles between good completeness and soundness.
8

---

4 DISCUSSION
It has been shown in Macdonald et al. (2020) that finding informative features for NN classifiers NP-hard. Thus, any efficient algorithm is a heuristic. Training Merlin-Arthur classifier is heuristic as well, as we are not guaranteed to converge to an equilibrium with informative features. However, the framework allows us to verify whether we succeeded by evaluating completeness and soundness on the test dataset. Without it, even just confirming that given feature is informative typically an involved task and requires a provably good model of the data distribution Frye et al. 2020); Aas et al.] (202T): Wallchen et al. (2022). An interactive classification setup circumvents these problems. We comment further on this topic in Appendix A
We can also draw connection to Adversarial Robustness (Goodfellow et al. 2014). Consider the generation of adversarial examples : 8 arg min |. L(x + o), a perturbation that changes the classification but is imperceptible to humans. The intuition behind adversarial robustness that minuscule changes should not change the classifier decision. Likewise. the intuition behind soundness, i.e., robustness with respect to Morgana, is that hiding parts of an object should not convince the classifier of different class. At most, one could hide the whole object, which is reflected the "Don't know!" option. In this sense, soundness is a natural counterpart to adversarial robustness and should be expected of classifiers that generalise partially hidden objects
4.1 IMPACT & LIMITATIONS
Agents with high completeness and soundness can be mandated as commercial classifiers that allow for reliable auditing, e.g., in the context hiring decisions. Using past decisions by the Merlin- Arthur classifier as ground truth, an auditor uses their own Morgana to verify if the setting has sufficient soundness. If so, the features by Merlin must be the basis of the hiring decisions. The au- ditor can then inspect them for protected attributes, e.g., race, with them (Mehrabi et al. 2021). Thus we also see that simply identifying informative features does not fully guarantee that classifier does not discriminate. For our experiments on the UCI dataset removed the features "marital status" and "relationship" to make the effect of cheating- -aaeting-neeenionnn more clear. Since they are correlated with sex (thus have high mutual information), they can be used by Merlin to communicate "sex" to Arthur when included, see Appendix C.4 It is then up to social scientists to determine whether the exchanged features constitute discrimination. But this an issue shared generally by feature-basse interpretability approaches.
attributes that strongly correlate
Our theoretical results are so far only formulated for two classes. We expect them be extendable to n-class setting, but leave this to further research. It remains to be seen whether our proposed training setup can be extended to more involved datasets while retaining stability. So far, we have kept the training routine straightforward and simple. Similar GAN-training, which is notoriously difficult (Roth et al. 2017: Wiatrak et al. 2019), there is potential for further sophistication.
5 CONCLUSION
We extend the framework of adversarial interactive classifiers to provide quantitative bounds on the mutual information of the selected features. These bounds are in terms of the average precision and ultimately in terms of measurable criteria such as completeness and soundness. We also extend our method beyond the assumption of feature independence that common such settings by introducing the notion of Asymmetric Feature Concentration that captures the necessary aspect of the dependence among the features. Finally, we evaluate our results on the UCI Census Income and MNIST datasets and show that the Merlin-Arthur classifier can prevent manipulation that has been demonstrated for other XAI methods and that our theory matches well with our numerical results.
REPRODUCIBILITY STATEMENT
We have provided all information needed to reproduce the results in the paper and its appendices. Section E discusses the various experiments, the datasets used, and provides an overview of the training process. Appendix Appendix/rreports repoors the experimental setup in more detail and describes the model architecture and the values of the various hyperparameters. We have also provided the source code

---

used, which will be available in our Git repository at the time of publication. Proofs of all results stated in the paper are provided in Appendix
REFERENCES
Kjersti Aas, Martin Jullum, and Anders I Løland. Explaining individual predictions when features are dependent: More accurate approximations to shapley values. Artificial Intelligence, 298: 103502, 2021.
Chirag Agarwal and Anh Nguyen. Explaining image classifiers by removing input features using generative models. In Proceedings of the Asian Conference on Computer Vision, 2020.
Christopher Anders, Plamen Pasliev, Ann-Kathrin Dombrowski, Klaus-Rober, Müller, and Pan Kessel. Fairwashing explanations with off-manifold detergent. In International Conference on Machine Learning, pp. 314-323. PMLR, 2020.
Cem Anil, Guodong Zhang, Yuhuai Wu, and Roger Grosse. Learning to give checkable answers with prover-verifier games, arXiv preprint arXiv:2108.1200 2021.
Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge Uni- versity Press, 2009.
Jasmijn Bastings, Wilker Aziz, and Ivan Titov. Interpretable neural predictions with differentiable binary variables. arXiv preprint 1rXiv:1905.08166 2019.
Guy Blanc, Jane Lange, and Li- Ying Tan. Provably efficient, succinet, and precise explanations. Advances in Neural Information Processing Systems, 34, 2021.
John Bridle. Training stochastic model recognition algorithms as networks can lead to maximum mutual information estimation of parameters. Advances in neural information processing systems, 2, 1989.
Shan Carter, Zan Armstrong, Ludwig Schubert, Ian Johnson, and Chris Olah. Activation atlas. Distill, 4(3)e11,, 2019.
Chun-Hao Chang, Elliot Creager, Anna Goldenberg, and David Duvenaud. Explaining image clas- sifiers by counterfactual generation. arXiv preprint arXiv: /807 0807/80072222 08024, 2018
Shiyu Chang, Yang Zhang, Mo Yu, and Tommi Jaakkola. A game theoretic approach to class-witg wise selective rationalization. Advances neural information processing systems, 32, 2019.
Aditya Chattopadhyay, Stewart Slocum, Benjamin D Haeffele, Rene Vidal, and Donald Geman. Interpretable by design: Learning predictors by composing interpretable queries. arXiv preprint arXiv:2207.00938, 2022.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning explain: An inoomattion-theoredee perspective on model interpretation. In International Conference on Ma- chine Learning, pp. 883-892. PMLR, 2018
Piotr Dabkowski and Yarin Gal. Real time image saliency for black box classifiers. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 6970-6979, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860999
Botty Dimanov, Umang Bhatt, Mateja Jamnik, and Adrian Weller. You shouldn' 't trust Learning models which conceal unfairness from multiple explanation methods. In SafeAI@ AAAI, 2020.
Ann-Kathrin Dombrowski, Maximilian Alber, Christopher Anders, Marcel Ackermann, Klaus- Robert Müller, and Pan Kessel. Explanations can be manipulated and geometry to blame. arXiv preprint arXiv: /90//999667933 2019.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. ics. uc. edd/ml
10

---

Robert M Fano. Transmission of information: A statistical theory of communications, American Journal of Physics, 29111)7933-794 1961.
Ruth C Fong and Andrea Vedaldi. Interpretable explanations of black boxes by meaningful pertur- bation. In Proceedings of the IEEE international conference on computer vision, pp. 3429-3437, 2017.
Christopher Frye, Damien de Mijolla, Tom Begley, Laurence Cowton, Megan Stanley, and Ilya Feige. Shapley explainability on the data manifold. arXiv preprint arXiv:2006.01272 2020.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572 2014.
Bryce Goodman and Seth Flaxman. European union regulations on algorithmic decision-making and "right to explanation". Al magazine, 38(3):00-57, 2017.
Juyeon Heo, Sunghwan Joo, and Taesup Moon. Fooling neural network interpretations via adver- sarial model manipulation. Advances in Neural Information Processing Systems, 32:2925-2936, 2019.
Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva. Abduction- -haued explanations for ma- chine learning models. In Proceedings of the AAAI Conference Artificial Intelligence, vol- ume 33, pp. 1511-1519,2011
Geoffrey Irving, Paul Christiano, and Dario Amodei. Ai safety via debate. arXiv preprint arXiv: 00899, 2018.
Yacine Izza, Alexey Ignatiev, and Joao Marques-Silva. On explaining decision trees. arXiv preprint 0rXiv:2010.11034, 2020.
Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In International Conference on Machine Learning, pp. 427-435, PMLR, 2013.
Sarthak Jain, Sarah Wiegreffie, Yuval Pinter, and Byron C Wallace. Learning to faithfully rationalize by construction. arXiv preprint arXiv:2005.00115, 2020.
Jon Kleinberg and Eva Tardos. Algorithm design. Pearson Education India, 2006.
Sebastian Lapuschkin, Stephan Wäldchen, Alexander Binder, Grégoire Montavon, Wojeiech Samek, and Klaus-Robert Müller. Unmasking clever hans predictors and assessing what machines really learn. Nature communications, 10(1):1-8, 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11): 86(11):228--2324 1998.
Tao Lei, Regina Barzilay, and Tommi Jaakkola. Rationalizing neural predictions. arXiv preprint arXiv:1606.04415, 2016
Jiwei Li, Will Monroe, and Dan Jurafsky. Understanding neural networks through representation erasure. arXiv preprint arXiv: 2016.
Shusen Liu, Bhavya Kailkhura, Donald Loveland, and Yong Han. Generative counterfactual intro- spection for explainable deep learning. In 20/9 IEEE Global Conference on Signal and Informa- tion Processing (GlobalSIP), pp. 1-5. IEEE, 2019.
Scott M I Lundberg and Su-In Lee. unified approach to interpreting model predictions. In Proceed- ings the 31 international conference on neural information processing systems, pp. 4768- 4777, 2017.
Jan Macdonald and Stephan Wäldchen. A complete characterisation of relu-invariant distributions. In International Conference on Artificial Intelligence and Statistics, pp. 1457-1484. PMLR, 2022.
Jan Macdonald, Stephan Wäldchen, Sascha Hauch, and Gitta Kutyniok. A rate-distortion framework for explaining neural network decisions. arXiv preprint / 1092, 2019.
11

---

Jan Macdonald, Stephan Wäldchen, Sascha Hauch, and Gitta Kutyniok. Explaining neural network decisions hard. In XXAI Workshop, 37th ICML, 2020.
Jan Macdonald, Mathieu Besancon, and Sebastian Pokutta. Interpretable neural networks with frank-wolfe: Sparse relevance maps and relevance orderings. arXiv preprint arXiv:2110.08103 2021.
Joao Marques-Silva. Thomas Gerspacher, Martin C Cooper, Alexey Ignatiev, and Nina Narodytska. Explanations for monotonic classifiers. In International Conference on Machine Learning, pp. 7469-7479. PMLR, 2021.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1-35, 2021.
Silvan Mertes, Tobias Huber, Katharina Weitz, Alexander Heimerl, and Elisabeth André. This is not the texture you are looking for! introducing novel counterfactual explanations for non-experts using generative adversarial learning. arXiv preprint arXiv:2012. /995, 2020.
Sina Mohseni, Niloofar Zarei, and Eric D Ragan. A multidisciplinary survey and framework for design and evaluation of explainable systems. ACM Transactions on Interactive Intelligent Systems (TiiS), 11(3-4):1-45, 2021.
Nina Narodytska, Aditya Shrotri. Kuldeep Meel, Alexey Ignatiev, and Joao Marques- Silva. As- sessing heuristic machine learning explanations with model counting. In International Conference on Theory and Applications of Satisfibiility Testing, pp. 267-278. Springer, 2019.
Chris Olah, Arvind Saryanarayan, lan Johnson, Shan Carter, Ludwig Schubert, Katherine Ye, and Alexander Mordvintsev. The building blocks of interpretability. Distill, 303) 2018.
Sebastian Pokutta, Christoph Spiegel, and Max Zimmer. Deep neural network training with frank- wolfe. arXiv preprini arXiv:2010.07244: 2020.
Dheeraj Rajagopal, Vidhisha Balachandran, Eduard Hovy, and Yulia Tsvetkov. Selfexplain: A self- explaining architecture for neural text classifiers. arXiv preprint UrXiv:2103.12277 2021.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High-precision model-agnostic explanations. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
Olaf Ronneherger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedi- cal image segmentation. In International Conference on Medical image computing and computer- assisted intervention, pp. 234-241. Springer, 2015.
Kevin Roth, Aurelien Lucchi, Sebastian Nowozin, and Thomas Hofmann. Stabilizing training of
generative adversarial networks through regularization. Advances in neural information process- ing systems, 30, 2017.
Lloyd S Shapley. 17. A value for n-person games. Princeton University Press, 2016.
Andy Shih, Arthur Choi, and Adnan Darwiche. A symbolic approach to explaining bayesian net- work classifiers. arXiv preprint arXiv: 1805, 0006400..344.. 2018.
Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks post hoc explanation methods. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pp. 180-186, 2020.
Dylan Slack, Sophie Hilgard, Himabindu Lakkaraju, and Sameer Singh. Counterfactual explana- tions can be manipulated. arXiv preprint arXiv:2106.0260 2021.
Stephan Waeldchen, Jan Macdonald, Sascha Hauch, and Gitta Kutyniok. The computational com- plexity of understanding binary classifier decisions. Journal of Artificial Intelligence Research, 70:351-387, 2021.
Stephan Wäldchen, Felix Huber, and Sebastian Pokutta. Training characteristic functions with rein- forcement learning: Xai-methods play connect four. arXiv preprint arXiv:2202.1 /197, 2022.
12

---

Maciej Wiatrak, Stefano V Albrecht, and Andrew Nystrom. Stabilizing generative adversarial net- works: survey. arXiv preprint arXiv:1910.00927, 2019.
Mo Yu, Shiyu Chang, Yang Zhang, and Tommi S Jaakkola. Rethinking cooperative rationalization: Introspective extraction and complement control. arXiv preprint arXiv:1910. 132994 2019.
13

---

A CONCEPTUAL OVERVIEW
As we discuss in Section 4 finding informative features faces two hurdles: a complexity barrier, as well as a modelling problem. Here, we further explain these challenges and how we overcome them. Additionally, we comment further on the related work mentioned in Section and explain why we cannot get guarantees without an adversary present. Furthermore, we show that, with an explicitly constructed data space, the debate setup (Irving et al.) (018)) cannot be used reproduce our results with the same generality. Instead, it would require stronger assumptions on either the classifier or the data space to exclude our counterexample.
A.1 COMPUTATIONAL COMPLEXITY
Prime Implicant Explanations (Shih et al. 2018), a concept from logical abduction, can be effi- ciently computed for simple classifiers like decision trees (Izza et al. 2020) and monotonic func- tions [Marques-Sunn Silva al. 2021). This concept has been extended NNs (Ignatiev et al.) 2019) in the form of probabilistic prime implicants, which correspond to features with high precision. How- ever, has been shown that even approximating small implicants within any non-trivia factor NP-hard (Waeldchen et al., 202 I) for networks of two layers or more. In Blanc et al. (202I). the authors construct an algorithm that circumvents these hardness results by further relaxation of the problem. While this is noteworthy theoretical breakthrough, the polynomial bound on the feature size grows so quickly with the dimension of the data space that the algorithm does not guarantee useful features for real-world data. For reasonably sized images, one would get guarantees only for features that cover the whole image.
We circumvent the hardness of this problem using method that is very typical of Deep Learning: Use a heuristic and verify success afterwards! Our approach can be put alongside the regular training of classifiers, which is a theoretically hard problem as well. heuristic like Stochastic Gradient Descent is not a priori guaranteed to produce a capable classifier. However, we can check the success of the procedure by evaluating the accuracy on test dataset. In our case, training the Merlin-Arthur classifier is not guaranteed to converge to an equilibrium with informative features. But we can check whether this is the case via the test dataset, where soundness and completeness take the role of the accuracy.
A.2 MODELLING THE TRUE DATA DISTRIBUTION
introduce Merlin-Arthur classification as it provides us way to measure the feature quality via the completeness and soundness values over a test dataset. This would not be necessary if we could directly measure the feature quality over the dataset (though it would still be faster than measuring every individual feature). The reason we need the Merlin-Arthur setup is that for general datasets the conditional entropy
We
HywD(cly) E 6) = HyyDiycc
is difficult to measure, since we do not generally know the conditional distribution Dlye This measurement possible for MNIST for small features since the dataset is very simple. However, for more complex data, feature which is large enough be indicative of the class will in all likelihood not appear more than once in the same dataset. We will now discuss some existing approaches that aim approximate the conditional data distribution and what problems they face.
Modelling the conditional data distribution has been pursued in the context of calculating Shapley values. These are different interpretability method based on characteristic functions functiooo from cooper- ative game theory that assign a value to every subset of a number of features (Shapley 2016). We will shortly discuss the approach proposed in Lundberg Lee (201)). where features correspond to partial vectors supported on sets, see Example 2.2 for how the feature set is defined in that case.
Let f [0. 11d {-1,1} be classifier function. Then we can naturally define characteristic function V/xx P([d)) + 1,
))) = Ey>D(f(()) yss xs] /
lys xs).
14

---

Independent Distribution
Data-driven Distribution
Original
Image
Selected Featune
Completion
"Cat!"
"Boat!"
Figure 7: Different failure modes of unrepresentative distributions. Left: Independent, random inpainting. similar Macdonald al. (2019). From a black image, the shape of cat is selected, and the rest is filled with uniform noise. The shape of cat is detected by a classifier. Right: Data-driven inpainting, similar to Agarwal Nguyen (2020). The image thatufe is selected. The data driven distribution inpaints the water back into the image, since the dataset, ships are always on water. The faulty classifier that relies on the water feature is undetected, the ship-feature indirectly leads to the correct classification.
ship is given and the
The Shapley value for the input component æ; then defined
[S] (15))
Shapley Value(x;)
Σ
SC(IM
In Macdonald al. 2021 the characteristic function is instead used define feature selection method as
X5- where S
arg min dist()((d),,sSS),
Sk
where & E [d] is cap on the set size and dist is an appropriate distance measure.
As in our setup, the problem is that these approaches depend on how well the conditional probability Py-plys- ys x is modelled. Modelling the data distribution incorrectly makes it possible manipulate many existing XAI-methods. This done by changing the classifier in such way that it gives the same value on-manifold, but arbitrary values off-manifold. To get feature-based explanations independent
off-manifold behaviour, one needs model the data manifold very precisely (Aas al. 2021 Dombrowski al. 2019). The authors of Anders et al. (2200) Heo et al. (2019) and Dombrowski et al. (2019) demonstrate this effect for existing techniques, such as sensitivity analysis, LRP, Grad-Cam, IntegratedGradients and Guided Backprop. They able to manipulate relevance scores at will and demonstrate how this can be used to obfuscate discrimination inside model. LIME and SHAP can be manipulated well (Slack al. 2020) by using classifier that behaves differently outside off-distribution if the wrong distribution for the explanation. For RDE (Macdonald al. 2019)) is assumed that features independent and normally distributed, and it was demonstrated that the off-manifold optimisation can create new features that weren't 't in the original image (Wäldchen al. (022)).
We now discuss two approaches proposed to model the data distribution and why each leads to different problem by under- or over-representing correlation in the data respectively.
Independent distribution:
Which means that the conditional probability is modelled as
Py lys = xs)
II p(v))
15

---

where p(y) suitable probability densities on the individual input components. This approach has been used in Fong & Vedaldi (017)) and Macdonald et al. (2021). where optimisers are employed to find small features that maximise the classifier score. In fact. Macdonald et al. (02T)) has to make a new approximation of the data distribution in every layer and it has been shown that for neural networks one cannot do much better than applying either this sampling [Macdonald & Waldchen (2022). It was highlighted in Wäldchen et al. (2022) how this approach, when modelling the data distribution incorrectly, will create artificial new features that were not present in the original image. Employing an optimisation method with this distribution can result in masks that generate new features that were not present in the original image. We illustrate this problem in Figure 7 Cutting a specific shape out of a monochrome background will with high likelihood result in an image where this shape visible. If the distribution was true, a monochrome shape would likely lead to an inpainting that is monochrome in the same colour, destroying the artificial feature. But an independent distribution undrr-tepresents these reasonable correlations.
Taking data determieddd distribution via generative model: probability modelled as
Which means that the conditional
Pyw yys x3) = G(ys=:xs).
where G is a suitable generative model. Generative models as a means to approximate the data distribution in the context of explainability have been proposed in series of publications (Agarwal & Nguyenn 2020 CCann et al.) 2018 Liu et al. 2019 Mertes et al. (020).. This setup introduces problem. the network and the generator were trained on the same dataset, the biases learned by the classifier will appear might be learned by the generator as well (see Figure for an illustration)! The important cases will be exactly the kind of cases that we will not be able to detect. If the generator has learned that horses and image source tags are highly correlated, it will inpaint an image source tag when a horse present. This allows the network to classify correctly, even when the network only looks for the tag and has no idea about horses. The faulty distribution over-represents correlations that are not present in the real-world data distribution.
a) Dataset with Hiring Bias
b) Highlighted Features
Accepted
Rejected
Accepted
Rejected
C++
C++
P
P
P
P
PHPP
PHP
Figure 8: Conceptual illustration of a biased dataset regarding a hiring process and a feature selector that hides this bias. a) Two candidates applied for a position, both are proficient in C++ and PHP and only differ by sex. The female candidate was accepted, while the male candidate was rejected. b) feature selector highlights one feature for each candidate. In a faithfulness test (Jain et al.) 2020), one would retrain model to reproduce the classification given the selected features to check how much information they carry about the decision. It is clear from this example that the selected features indeed carry this information, not in themselves, but rather through the way they have been selected.
A.3 FEATURE IMPORTANCE AND FAITHFULNESS
Recent work has established faithfulness as a reasonable criterion (among others) for sound feature selectors and interpretability approaches (Jain et al. 2020; Rajagopal et al. 2021 Yu et al. 2019). Faithfulness is defined as the ability of the model, retrained solely on the selected features for each data point, to infer the correct classificatior?? We now want to argue how this approach corresponds to our cooperative setup without Morgana and why one must be careful with the conclusions.
"The setup in Yu et al. 2019 includes an adversary, however, this adversary operates differently from our Morgana and instead tries to classify on the features not selected by Merlin, We have not investigated whether this setup is sufficient prevent hiding biases, in our example in Figure
16

---

If this retraining should fail, it stands to reason that the selected features not indicative of the class. However, if the retraining succeeds, it is not necessarily true that the features were also used to make the classification. We already commented the difference between
(x) = =)) and H(c(y)ly E Φ),
in Section 3 The retraining corresponds our purely cooperative setup in the sense that the model can learn In what pattern the feature selector selects features for each class, without the feature itself being indicative, see Figure [ for an illustration, where a feature selector chooses the feature "proficient in C++" for the accepted candidate and "proficient in PHP" for the rejected one even though both have both features. An adversary could easily exploit these uninformative features by reversing the pattern and fooling the classifier into giving the wrong class. This is why robustness with respect to Morgana necessary to link H (c(y)ly E Φ) and ((c(x) = 6).
A.4 DEBATE MODEL VS AERLIN CLASSIFICATION
The debate setting introduced in Irving al. (0088) intriguing alternative our proposed setup. However, we are now going to present an example data space on which, in debate mode, Arthur and Merlin can cooperate perfectly without using informative features. For this, use the fact that in the debate setting, Arthur receives features from both Merlin and Morgana for each classification. Our example illustrates that the debate setting would need stronger requirements on either the data space or Arthur to produce results similar to ours.
Consider the following example of a data space D illustrated in Figure Example A.1. We define the data space D ((D, c, with
* D = {(zysE(N)
o PP((D.
P((D) D(T)= = T
N
c(x,) = [-1 j odd,
-(-1 [1 j even,
Σ == U {Ø,} where oj- = {2 Kj+t mad N.
JE(N)
None of the features in Σ are informative of the class and the mutual information T(c(x);; e Φ) for any Σ is zero. Nevertheless, debate setting, Arthur can use the following strategy after receiving total of two features from Merlin and Morgana
if01 n n2 Ø,
A(fo1, 622) max c(z;)) s. E & 0
otherwise.
This means he returns the class of the data point with the highest j-index that fits the features he presented (we assume he ignores the Ø feature). The maximum over the indices should be understood as cyclic, so her prefers N to - 1, but to N, since mod N = 0. But now Merlin can use the strategy
M ((x) = min Φs s.t. I Φ5,
which returns the feature with the lowest j-index. It is easy to verify that no matter what Morgana puts forward, a feature with higher or lower index, nothing can convince Arthur of the wrong class. If she gives the same feature as Merlin, the data point will be correctly determined by Arthur. If she gives the other feature, the true data point is the unique one that has both features. Arthur's 's strategy works as long as someone gives him the feature with the lower index.
In setting where Arthur has to evaluate every feature individually, the best strategy that Arthur and Merlin can use achieves 6, c, 3. by making use of the asymmetric feature concentration. The AFC for Dex is x = 2, as can be easily checked by taking F (Φ1, 62, Φs, Φs) in the definition of the AFC, see Definition B. and observing that they cover 4 data points in class -1 and only two in class / I. But since the AFC-constant appears in the bound, the lower bound for QM is g well below the actual average precision of
1
17

---

1=-1
1=-1
J2
32
29
244
23
Q4
J6
25
45
21
27
as
a)
Figure 9: Schematic of t as defined in Example A.1 a) The data space forms tri tri-partite graph, where every data point shares exactly one feature each with two data points from the opposite class. b) Classification on data point 23. Merlin chooses the feature with the smallest index from this data point, so @2. Arthur chooses the class of the data point with the highest index compatible with the presented features. Morgana can choose Ø, @2 Φ3, but in all cases Arthur can correctly identify the original data point and return class -I.
This example demonstrates that Arthur and Merlin can successfully cooperate even with uninforma- tive features, as long as Arthur does not have to classify on features by Morgana alone. This implies that to produce similar bounds in our setup, the debate mode needs stronger restrictions either the allowed strategies of Arthur or the structure of the data space, such that this example is excluded.
A.5 DESIGN OF THE THREE- WAY GAME
The basic setup for prover-verifier game for classification was proposed by Chang et al. with verifier, a cooperative prover and an adversarial prover for one specific class. The verifier either ac- cepts the evidence for the class or rejects it. Both provers try convince the verifier, the cooperative prover operates on data from the class, the adversary on data from outside the class. The authors suggest that the way scale multiple classes to have three agents for every class.
In our work, we combine the agents over all classes, to have single verifier (Arthur), cooperator (Merlin), and adversary (Morgana). The verifier rejecting classes corresponds our "Don't know!" option. In our design in Section 3 we make the implicit assumption that the class of the datapoint unique. Combining the verifiers gives
numerical advantage for two reasons. First, since lot of lower-level concepts (e.g. edges and corners for image data) are shared over classes, the lower levels of the neural network benefit by being trained on more and more diverse data. Second, we can leverage the knowledge that the class is unique by outputting distribution over classes (and "Don't know!"). Both lines of reasoning are standard for deep learning Bridle (189).
Anil et al.] further combine Merlin and Morgana into a single prover that probabilistically produces a certificate for random class. This has the advantage that it allows for further weight-sharing among the provers. However, the probabilistic nature of the certificate is also disadvantage. The probability of generating the certificate for the correct class the inverse of the total number of classes. When applied after training, one only occasionally gets valid classification. In our case, can always use Merlin together with Arthur to obtain the correct class together with an interpretable feature.
18

---

B THEORETICAL DETAILS
We now give further explanations to our theoretical investigation in the main part as well as provide definitions and proofs for the previously stated theorems and lemmas.
B.1 CONDITIONAL ENTROPY AND AVERAGE PRECISION
We restate the definition of the average precision and average class conditional entropy show how one can be bound by the other. The average precision of a feature selector M is defined as
QD(M) == Ex-D(Py-plccy) = c(x) ly E [x)]]
The average class conditional entropy with respect to feature selector defined as
Hx.y~D(ely)lx & M(x)) == Ex Hy--D((y)) ly E M(x))]-
We can expand the latter and reorder that expression in the following way:
Hx (y E M(x))
-Ex-D
Σ
P(c(y) = lly e logP)y = M(x)))
[E(-111)
EXWD
Σ
P(c(y) = y log( ( ( M(x)))
(E(c())
ExND H4 (yyyyD((()))) dx)) E M(x)),
where Ho(p) logog()) (1 p) log(1 p) is the binary entropy function. Since Ho(p) is concave function, we can use Jensen's 's inequality and arrive at the bound
Hx E M(x)) < H₂(Qp(M)).
We now give a short proof for Lemma 2.7
Lemma 2.7. Given = ((D,o a. De, Σ). a feature selector M E M(D) and [0, 1]. Let D, then with probability - 8- (1 1- (M)), M(x) selects a feature o, s.t.
Py~D(c(y) c(x) y o) 2 1-8.
Proof. The proof follows directly from Markov's inequality, which states that for a non-negative random variable Z and >
E[Z] 8
PIz 8)
Choosing Z 1- Py-pllyy)
[x)] with x D leads to the result.
B.2 MIN-MAX THEOREM
We now present the proof for Theorem 2.8 which we restate here.
Theorem 2.8. [Min-Max] Let M E M(D) be a feature selector and let
сM = min max PXND
x E M.M.A
AEA MEEM
Then there exists set D' C D with PP P E DJ
EM such that for D' = =Di Dr have
Qd (M) = and thus Hx y M(x)) 0.
Proof. From the definition of Gar follows that there exists a not necessarily unique AF E AA such that
max P PXND x F.M. = 6M--
(4)
MEM
19

---

Given A3, optimal strategy by Morgana is certainly
Φ s.t. A( -c(x) if possible,
(x)
Ø
otherwise,
and every optimal strategy differs only on a set of measure zero. Thus, we can define
D' D M.
and have Fx xx E DJ EM. We know that A(M (x)) # when x E D' and thus can finally assert that
Vx,y E D' y (x) = c(y) c(x).
Otherwise there would be at least one y E D' that would also be in F. M Thus, we conclude
( = 1, and from
S Hx y E M(x)) - Ho(QD 0. it follows that Dx (cly) y M(x))= =
This theorem states that Merlin uses a strategy that allows Arthur to classify almost always cor- rectly, thus small ear, then there exists dataset that covers almost the entire original dataset and which the class entropy conditioned on the features selected by Merlin is zero.
This statement with new set D' appears convoluted first, and would prefer simple bound, such as
(D(M)
EM, EM
where we take the average precision over the whole dataset. This is, however, not straightforwardly possible due principle we call asymmetric feature concentration and which we introduce in the next section.
B.3 ASYMMETRIC FEATURE CONCENTRATION
Asymmetric feature concentration (AFC) is a concept that will allow us to state our main result. It measures if there is of features that concentrated in few data points in one class, but spread out over almost all data points in the other class. This represents a possible quirk of datasets that can result in scenario where Arthur and Merlin cooperate successfully with high probability, Morgana is unable to fool Arthur except with low probability- and yet the features exchanged by Arthur and Merlin uninformative for the class. An illustration of such an unusual dataset given in Figure 10
For an illustration of the asymmetric feature concentration, consider two-class data space {(D, a, D), c, }}, e.g. the "fish and fruit" data depicted in Figure I0 Let us choose F c Σ to be all the "fish" features. We see that these features are strongly anti-concentrated in class I -1 (none of them share an image) and strongly concentrated in class I = 1 (all of them are in the same image).
For now, let us assume F is finite and let (FF),, the uniform measure over F. We have strong AFC if the class-wise ratio of what each feature covers individually is much larger than what the features cover as whole:
P PX (x Φ)
PXWD_, UF] IP PXND, xx E UF]
E PAWDD (x E Φ]
In our example, every individual "fish" feature covers one image in each class, so the left side is equal 1. As feature set, they cover images in class 1 and one in class so the right side is B. Using
Pix E Ø] =| P UF
we can restate this expression as
EawF(N((O,F)) F)] > 1,
(5)
where
k( = PXLD X x UF
PXWD, (x E x EEUF]
20

---

One fish fruit
1=1: One fruit or many fish
I=-1: many
b)
I-1: One truit many fish
Figure 10: Illustration of data space with strong asymmetric feature concentration. dataset with fish and fruit features. The features are asymmetrically correlated, because all fruit features are maximally correlated in class -1 (they are all the same image) and maximally uncorrelated in (no two fruits share the same image). The reverse is true for the fruits. See Figure I for strategy for Merlin that ensures strong completeness and soundness with uninformative features.
b): Asymmetrie feature concentration for specific feature selection. For the class -1, select the F of all "fish" features. Each individual fish feature F covers fraction of (UF) n D-1 and all images (one) in (UP) n D1- The expected value in Equation ( thus evaluates to = 6. This is also the maximum AFC for the entire dataset as different feature selection gives higher value.
For our "fish" features we have K- (bb, F) 6 for every feature & E F. Considering infinite set F, we need way to get a reasonable measure F, where we don't want "overemphasise" features that appear only in very few data points. We thus define feature selector fr MMUF))
fF(x) = arg max n( F), $EF s.t. XCO
(6)
and we define the push-forward measure == Fr. Dt.D.. For our fish and fruit example, where F is the set of all fish features, SF+ would select a fish feature for every image in class -1 that is in UF. Putting everything together, get the following definition.
Definition B.1 (Asymmetric feature concentration), Let ((D, a, a,,,, D), E) two-class data space, then the asymmetric feature concentration is defined
Px-D_ UUFF
K
max max LE (E(-1,1) PCE
E BynDilur
max de J. YEO
P Px- [
As we have seen in the "fish and fruit" example, the AFC can be made arbitrarily large, as long as one can fit many individual features into single image. We can prove that the maximum amount of features per data point indeed also gives an upper bound on the AFC. We now come back to Lemma 2. and prove it.
Lemma 2.10. Let D =(D,o,, D),
e, E) be two-class data space with AFC of Let K maxxeD K6 E Σ ExE0] be the maximum number of features per data point. Then k < K.
Proof. Let 1 E {-1,1} and let F C E. We define fF E MM(FF) as in Equation 6 well as F fF.DiluF. We can assert that
P
(x = -
21

---

0.5
0.5
1=1
1=-1
Figure 11: In the dataset presented in Figure 10 for class = -1 and the fruit features for class 1 = 1 if they exist and choose something arbitrary otherwise. Arthur then guess
Merlin can use the strategy to always select the fish features
if he gets fish and I containing all fruits fish, and can only exploited by Morgana for those same two images out of 14. The completeness and soundness constants in this case are both 7. But as illustrated here, each "fish" feature completely uninformative of the class. Conditioned on the selected fish, it could either be the image from class 1 -1 or from I = 1.
for fruit. This strategy fails only for the images
We then switch the order of taking the expectation value in the definition of the AFC:
IP IP x F
JF] PywD: y E E UF]
ki (F)
BarF
EX [1(x E ()) x UF]
ESnF
Py PywDi y E Φ EUF]
E
Ex
x UFUF UF
Py PY ly E p
Since there are only finitely many features in data point we can express the expectation value over countable weighted by the probability of each feature:
F(O)
(F) EXLD_
Σ xEF
XEUF
P PYND, E
< BXND_I
Σ
XXEU
OEFE
< EX-D_I XXE
K,
where in the first step we used Equation and the definition of in the second. Then we see that
max max (F) S K.
(e(-1.1)CC
The number of features per data point is dependent on which kinds of features we consider. Without limitations, this number can be 24, i.c., exponentially high. See Figure 12 for an example of expo- nentially large AFC parameters. If consider only features of fixed size and shape, such in image data, the number of features per data point drops to x
All
bllee
Figure 12: An example of dataset with very high asymmetric feature concentration. The completely red
image shares feature with cach of the m-red-pixel images (here m = 5), of which there are (d) many. In the worst case = $ resulting in k = (c/22) thus exponential growth d.
22

---

We now prove intermediate lemma that will later allow to prove Theorem 2.12
Lemma B.2. Let ((D,o, D),c, 2) be two-class data space with asymmetric feature concentration of &s and class imbalance B. Let A [0, 1] 7 0- 13 be a feature classifier and M E &M(D) feature selector for D. From
1. Completeness:
min Px-DD (A(M(x)(((x))) = EC. 16(-1.1)
2. Soundness:
max P PxNDi [A(M(x)) =-1 S Est
max (E(M())
follows
(D(M) 2
E. + B=
This lemma gives a bound on the probability that data points with features selected by Merlin will also belong the same class. This probability is large as long as have a bound on the AFC of the dataset.
Proof. The proof of our lemma is fairly intuitive, although the notation can appear cumbersome. Here we give a quick overview over the proof steps.
1. In the definition of the AFC, we maximise over all possible features sets. We will choose as a special case (for each class E 1)) the features that Merlin selects for data points that Arthur classifies correctly.
2. These feature sets cover the origin class least up to -1 and the other class at most up to 6x. which is required by the completeness and soundness criteria, respectively. This gives us a high precision for the whole feature set.
3. The AFC upper bounds the quotient of the precision of the whole feature set and expected precision of the individual features, which finally allows to state our result.
Let us define partition of D according to the true class and the class assigned by Arthur. From now on, let 1} and m E 1,1,0,1). We introduce the datasets
Di.m = (x Dj A(M(x) m),
which means that Di, are the data points that Arthur classifies correctly, and furthermore
F M(D..))
To use the AFC bound we need feature selector f Diluf F. Merlin itself maps to features outside F when applied to data points in DiluF; Dr,,- Let us thus define a Dr \ Dr, + F which selects arbitrary feature from F (in case one concerned whether such representative can always be chosen, consider a discretised version of the data space which allows for an ordering). Then we can define
f(x) [M(x (x(x)
x E Dra, E DiluR Dra
and F F.=fDDLAA
This feature selector will allow to use the AFC bound. We now abbreviate
p(x, f) PywD(c(y) + c(x) ly E f(x)] and Pt PX-D|x E Di).
Then
1 1- 1-Q = ExwD/p(x, M)
Σ
E EXWDD Mt
(8)
LE(-1,11
23

---

Using the completeness criterion and the fact that p(x, MM I 1 bound
Ex [p(x, M)] Ex M Dı,)) + Bxx_,
D1,)l
Ex Ex [p(x M Dt,1)l + Ce
D [p(x,, Mx E Du.)l + ce c Ex 0)1 E Dilues \ D())
E Ex Di (p(x, M) E D1.1) + p(x, E Dilur; Duull +
PXWD, xx E Dilun]
Ex-Dilun [p(x, f)] 6e
Esni, Py Py-old(y) = -lly E oll+ c
We can expand the expression in the expectation using Bayes' Theorem:
PywD_ ly E o|F-1
P Py-plc(y) = y E E
P. PymD_, yy E Φ P-i Py ly
ol
Py Py-D_ y 6|P-1
Py-D, y p)
where h(t) (1+t-1)-1 Since h(tt is concave function for t 0, we know that for any random
variable Ht have [[) < ((E) so
P PyND_, Φ P-i Py Φ) P
Ex-D, [p(x, M)) & h BBg
+ cc-
(9)
From the definition the AFC we know that
PywD (y E P PywD,ly Φ)
PywD_ ly
by EUF
Eg
ExwDilup
max PEF st. XEO
(10)
Py~D,
PywD,ly ly UF]
Now make use of the fact that we can lower bound P Py~d, [y F) by the completeness property
Py-dily E UF] 2 1- - Ec.
and upper bound Pywd_,ly UF] with the soundness property
Py~D_,ly UF] S 6g.
This is because y E JF implies that there are features Morgana can use to convince Arthur of class 7 whereas ~ D- Together with Equation (9) and Equation (TO) we arrive at
P
6s P-1 1 Pr
KEg
ExDD, [x(x, M)] < h
+
tec
P_i
+ Ec.
6. + KE, Pi
Using PL1 < thus
B-1 1 we can express
M
P_c Ke P
E Ex (p(x, MY S 1 - cc + RC, B-
+ Co.
Inserted back into equation Equation
{ leads us to
1 QD( - 6c + Ke, B-1 + co.
Keg
B.4 RELATIVE SUCCESS RATE AND REALISTIC ALGORITHMS
As discussed in Section 2.3 Morgana only has to find features that are also discoverable by Merlin albeit in images of a different class. The question then becomes how much the other features in the image (the context) matter for finding this feature. We can easily construct scenarios in which the context matters very strongly, see Figure 13 for an example. We expect that for most real-world data this dependence is only weak and can be upper bounded.
24

---

1=1
Illustration of dataset with strong context dependence. Class -1 consists of k-sparse images whose pixel values sum some number For each these images, there is non-sparse image class that shares all non-zero values (marked in red for the first image). Merlin can use the strategy to show all non-zero pixels for an image from class -1 and A +- arbitrary non-zero pixels for class 1. Arthur checks the sum is equal to S or if the number of pixels equal to & + 1, otherwise he says "I don't know!". He will then classify with 100% accuracy. Nevertheless, the features Merlin uses for class -1 completely uncorrelated with the class label. exploit this, however. Morgana would have to solve the NP-hard (Kleinberg & Tardos 2006) subset sum problem to find the pixels for images in class that sum to S. The question is not in which class we can find the features, but in which class we can find the features efficiently.
Figure 13:
Let us make this notion more formal. We want to compare the success rates of Merlin and Morgana conditioned on a convincing feature & with A(d) being present in the data point:
Px~D__ M succeeds x E ④)
P x M succeeds
x E Φ)
The question is how define the "success". If we measure success by returning d might be that Morgana can actually find different feature that convinces Arthur, which in that case would not count as success. we instead just require that A(M (x. ()) = I, then Merlin could instead rely on a different, easily findable feature that is only present in data points of the correct class. The feature 6 might then be generally hard to find, and Morgana would need to be again a perfect optimiser. We reason that both approaches would make the fraction unreasonably large even for practical datasets.
The solution is to make the fraction asymmetric and require Merlin to actually find the feature & and Morgana to simply convince Arthur on the data point. So consider the expression
PX~D [((M(x))
= X E
P Px~D, [M(x)
x d)
and try to assume upper bound. In the following definition, we apply this idea to whole sets of features on which Arthur is constant. That means we maximise over sets C A - where A -1 the preimage of A. If Merlin can find features from this set in one class, then Morgana should not have a much harder time finding them in the other class, given that they are present in the data point.
Definition B.3 (Relative Success Rate). Let D ((D,o, D), c, E) be two-class data space. Let A E A and M: D x {-1,1} + Ed an approximation for M, M e MMD).. Then the relative success rate of M with respect to A, M and D is defined
= PX-D_I A
= min
min IE( (E(-1,1) PEA-10) PAND E FXUFF
It might make sense for the definition to require that D(UF) be large, that insignificant feature sets diminish the relative success rate, but since we cannot evaluate this quantity numerically anyway we leave this unrestricted for now.
25

---

Example B.4. Let D be data space with maximum number of features per data point K. Let Morgana operate the algorithm described in Algorithm [ in which she randomly searches for a convincing fea- ture. Then we have
Algorithm Merlin-Arthur Training
1: Input: X E D, Ray
Output: & E Σ
3: for i E [Mary] do
K
Pick random feature Φ s.t. Φ
if A(Ø) -c(xx then
Thrry
return
which corresponds to upper bound the prob- ability that Morgana will succeed on an individual data point when there is only one convincing fea- ture.
end if
end for
return Ø
We generally want Morgana's algorithm be least as powerful as Merlin's so in case of an optimiser one can consider giving more iterations or more initial starting values.
We now want to prove Theorem 2.12
Theorem 2.12. Let D ((D,a, D), E) be two-class data space with AFC of and class imbalance B. Let A E A, and M, M E MMD) such that M has relative success rate of a with respect to A, M and D. Define
Completeness:
min LE(- (E(-1.1)
PX P [A(M(x)) c(x)) EC2
max P Px~D; [ (()( -x((x) S ESI (E(-1,1}
Soundness:
where Dj is the data distribution conditioned on the class I. Then it follows that
150K le
(D(M) 2 6c
6 ka B-1es
Proof. We follow the same proof steps and definitions as in the proof of Lemma B.2 up to Equa- tion 10p. Then we consider the following
PP Py~D [y F
P PywD ly E PX-D |x - F|
(11)
DyDD y E]
PywD, y F] PX-D, ((x F
PXWD (A(M(x,1) =1,,
(12)
P [M(x, 1) E F.
P D [A(M (x, ()) =1
(13)
P Px [M 1) F]
where used in the last step that (xx,)) F x E F and that when E D; we have (x)(xx)) = + x E both by definition We know by the soundness criterion
PXWD [A(M(x, ()) 1] S c..
From the definition of and the completeness criterion we get PXWDD (M(x E F] 2 Ec. Putting everything together we arrive at
P Py-D_I ly E
< a Les
Dy~D. y F]
1
which allows to continue the proof analogously to Lemma B.2
B.5 FINITE AND BIASED DATASETS
Real datasets come with further challenges when evaluating the completeness and soundness.
Let us introduce two data distributions and on the same dataset D, where T considered the "true" distribution and D a different, potentially biased, distribution. We define this bias with respect specific feature @ E Σ
(D, T) [xxD|((x) x E Φ) PxxT(((x) = x|x E Φ]-
26

---

Note that = =: data points containing distributed differently to the two classes for the two distributions.
do(D)) and 0 S do 7) I 1. This distance measures if
For example, consider as & the water in the boat images of the PASCAL VOC dataset Lapuschkin et al. (2019). The feature is strong predictor for the "boat" class in the test data distribution D but should not be indicative for the real world distribution which includes images of water without boats and vice versa. We now want to prove that feature selected by M is either informative feature or is misrepresented the test dataset.
Lemma B.5. Let D,k, B, A, M, ox, to and Eg be defined as in Theorem 2.12 Let T the true data distribution on D. Then for [0, 1] we have
Py-T (cly) c(x) y E M()) 21-6 dm(() (D,T),
with probability 1 IIkae, B I-c + Eo) for
This follows directly from Lemma 2.7 Theorem 2.12 the definition of do (D, and the triangle inequality. This means that if unintuitive feature selected in the test dataset, we pinpoint to where the dataset might be biased.
We provided Lemma B.3 in the context of biased datasets. The next iteration considers the fact that we only sample a finite amount of data from the possibly biased test data distribution. This will only give us an approximate idea of the soundness and completeness constants.
Lemma B.6. Let D, D, cA, M and T be defined as in Lemma B.5 be N random samples from D. Let
Let Diest (x:) DM
cc
1 1E(-1,1)
max
N XED."
Σ
(xx # c(x)),
and
max 1E(-1.1)
Σ XED
1(A(((x, -c(x))) -c(x)).
Then holds with probability where rj E [0, 1] that on the true data distribution T A and M obey completeness and soundness criteria with
S test + Edist + Esample
and
6s S jest + Ediss + Esample
respectively, where Cdist
|D Tillrv and Grample 1E(-1,1)
max
2N
log
The proof follows trivially from Hoeffding's inequality and the definition of the total variation norm.
Proof. We define E.,- {x D; A(M c(x))) # c(x)) for {-1,1] and let E. be the Bernoulli random variable for the event that X Ec, where X D. Then
Px-D,[[MM c(x))) + c(x)] E E.!
Using Hoeffding's inequality we can bound for any / >
I(
Σ 1xx Fees)
E.
F.I
> 1
S e
- 2nt
N
x
We choose such that 2t results in probability of 2 Y
We use a union bound for the maximum over I E f11, which
have
4
max (6(-1.1)
E ED
test
log
2N
27

---

and thus with 1 - 2 we have (-1,1) E Ee,
I ce_ + +
eumppe Using the definition of the total
variation norm
- -T-Vl = sup (T)) D(J)
JCD
with J Fee, we can derive R
E7
+ I D1[rv and thus
cc S c
sample
+ dist
We can treat analogously and take union bound over both the completeness and soundness bounds holding which results in the probability of 17.
C NUMERICAL EXPERIMENTS
For the numerical experiments, we implement Arthur, Merlin and Morgana in Python 3.8 using PyTorch (BSD-licensed). We perform our experiments the UCI Census Income dataset and the MNIST dataset, which licensed under the Creative Commons Attribution-Sia Sharee Alike 3.0 licence.
C.I TRAINING SETUP FOR CENSUS INCOME DATASET
In the following, we provide an overview of the experiments performed on the Census Income dataset, including preprocessing steps and training configurations.
Data Preprocessing The UCI Census Income dataset consists of both continuous and categorical features, 14 features in total. The target class is chosen be the feature "sex", which contains the categories "male" and "female", to indicate a possible case of discrimination. The feature "fnlwgt" is is removed from the set of features, since it does not contain any meaningful information. In addition, the features mmarital-status and "relationship" are also removed as they strongly indicate the target class. After removal, 11 features remain for each data point. The continuous features are scaled according to the min-max scaling method. Too simplify feature masking, all features are padded to vector of the same fixed dimension. Continuous features are then repeated along the padding dimension, while categorical features are one-hot encoded to the length of the fixed dimension. Note, that the fixed dimension is determined by the categorical feature with the most categories.
Finally, the train and test datasets are balanced with respect to the target class, resulting in 19564 train samples and 9826 test samples.
Model Description Arthur is modelled as NN with a single hidden linear layer of size 50 fol- lowed by a ReLU activation function. The output is converted to a probability distribution via the softmax function with three output dimensions, where the third dimension corresponds to the "Don't t know!" option. The resulting NN contains approximately 23k parameters. Merlin and Morgana, on the other hand, are modelled as Frank- Wolfe optimisers, which are discussed in more detail in the overview of the experiments conducted the MNIST dataset.
Model
Learning Rate
Batch Size
Frank- Wolfe Learning Rate Epochs
Pre-training Arthur
10
512
100
Merlin-Arthur Classifier
0.5
512
0.1
20
Table 1: Configurations for pre-training Arthur and training the Merlin-Arthur classifiers.
Model Selection The training and testing of the models is divided into two phases. First, we pre-train Arthur on the preprocessed UCI Census Income dataset without Merlin and Morgana. Second, we use the pre-trained model to perform further training including Merlin and Morgana. For the pre-training were saved separately after each epoch. Consequently, for each experiment, of candidate models to choose from for further analysis. To ensure high completeness, we select the pre-trained candidate with the highest accuracy with respect the test dataset. The selected
Arthur, our experiments were conducted such that the models' parameters had access set
28

---

model then represents the pre-trained classifier for all subsequent experiments involving Merlin and Morgana. Similar to the pre-training process, we also stored the model parameters after each epoch of training with Merlin and Morgana. The results presented in Figure correspond to the models with the highest completeness at a soundness of at least 0.9 among all epochs. The training configurations regarding the pre-training of Arthur and the training of the Merlin-Arthur classifiers can be obtained from Table [
Algorithm 2 Merlin-Arthur Training
Input: dataset:
Durain Epochs: N.
2: Output: Classifier Network (A), Optional: Masking Networks Merlin (M) and Morgana (M)
3: for E [N] do
4: for Xj.Y; E &Drain do
5: SM
(3), +- M(x,, D M and M can be the optimiser the NN 6: A arg min LM (A(sM 22). 25) + + 2z), y3) Update classifier
using masked images
7:
M arg min L (x, zz).)))
Update only if M is NN >> Update only M a NN
8:
M f arg max Ly (A(M (xy) zz).,;)
9:
end for
10:
for
Xj E Durin do
11:
A arg m L( [(A(r,))
Update classifier using regular images
12: end for
end for
C.2 TRAINING SETUP FOR MNIST
Here, we give a detailed description of our training setup for MNIST and show the error bars of the numerical results presented in the main part of the paper 10 different training runs.
Structure of Arthur. Arthur is modelled using a neural network. Specifically, we consider a convo- lutional NN with ReLU activation function. For the case of classes, we consider NN with convolution layers, whereas for the 5 class case we consider 3 convolution layers. The output of the convolution is then passed through 2 linear layers before being used for the output. Table describes the used architecture in detail.
Layer Name
Parameters
Conv2D
1=3,0=32, K=3
ReLU
Conv2D
I=32, 0=64, K=3
ReLU
Conv2D
1=64, 0=64, K=3
ReL.U
MaxPool2d
K=2
Linear
1=7744,
0=1024
ReLU
Linear
I=1024, 0=128
ReLU
Linear
1=128, O=1
Table 2: Description of the neural network architecture used for the Arthur classifier.
Structure of Merlin and Morgana. Recall that Merlin and Morgana aim to ideally solve
M (x) arg min Lm (A,x,s) and M(x) arg max (7, x,,), SEB
sEBd
respectively, where LM and Ly are the loss functions defined Section and B is the space of k-sparse binary vectors. Thus, Merlin and Morgana take an image input and produce mask
29

---

of the same dimension with io one-entries and zero-entries otherwise. We additionally added regularisation term in the form of s/s/|1 to both of the objectives, and set À = 0.25. We realise the pair Merlin and Morgana in four different ways, which we explain in the following. All of these approaches return a mask s E [0, 1] that we then binarise by setting the & largest values to one and the rest to zero
Frank- Wolfe Optimisers In the first case, Merlin and Morgana are modelled by an optimiser using the Frank- Wolfe algorithm (Jaggi 2013). We follow the approach outlined by Macdonald et al. (202)) with the Frank- Wolfe package provided by Pokuutta et al. (2020). The optimiser searches over a convex relaxation of B i.c.,
{v 10 |v/] k),
the k-sparse polytope with radius limited to the positive octant. To optimise the objective we use the solver made available at https: / titbb.. com/ 2IB- IOL/ 11.1--100/soohhssticcaaaaa///// with 200 iterations.
UNet Approach For the second case, we model Merlin and Morgana using NNs, specifically UNet that has already been used in the XAI domain to create saliency maps, see (Dabkowski & Gal 2017). We copy the UNet design by Ronneberger et al. (2015) since it achieves good results in image segmentation, a task reasonably similar to ours. We predict mask values between zero and one for each image pixel, and rescale the mask should it lie outside of Bg The binarisation of the mask is ignored during the backpropagation that trains the UNets and only employed to produce the masks that Arthur is trained on.
Hybrid Approach In the Hybrid approach, Merlin modelled by a UNet, whereas Morgana is still modelled by the FW-optimiser. This approach useful since for a sound Arthur that cannot be fooled, the training of the Morgana UNet becomes difficult and the UNet diverges. It then takes a while of training for the UNet to adapt, should Arthur open himself to possible adversarial masks. The optimiser is applied to each individual image instead and can find possible weaknesses instantly.
Class-Networks
One of the alternatives to Merlin and Morgana that we propose are class spes--ppecific UNets. Instead of Merlin and Morgana each being represented by a network, there is a UNet associ- ated with each class that is trained to produce a feature mask that convinces Arthur of its own class for any input image, i.e., for / E [C]] try to solve
M((x) arg min (Ag(A(ss x)i) A/|s||1-
SE
Merlin is then implemented as an algorithm to choose the UNet corresponding to the true class, so
(x) = (x)
Morgana instead uses for each individual image the output of the UNet that most convinces Arthur of wrong class (maximises the Morgana-loss), i.c.,
((x) = (x) with I arg max (A, (, (x))..
(ECM)(())
Ideally, this training setup would be more stable than the normal UNet approach. When Arthur cannot be fooled, the class-UNets still have a reasonable objective in convincing him of the correct class, which hopefully prevents divergence as for the Morgana UNet. Experimentally, however, the class-networks proved to be much less stable than the simple UNet approach, see Figure [5]
We give an overview over the parameters used for the four different approaches in Table
Merlin-Arthur Classifier Training The overall training procedure proceeds as outlined in Al- gorithm 2 We initially train Arthur directly on the training data. In the optimiser approach, this pre-trained network is used to search for the optimal masks for Merlin and Morgana. In the UNet approach, these masks are directly produced by the UNets. Arthur is then trained on the masked im- ages over the whole dataset. The UNets are then trained on the dataset with fixed Arthur according to their respective objectives. We cycle through this process for 5 epochs. The learning rate is le-4 for the Arthur and Merlin network and le-6 for the Morgana and the class-specific networks.
30

---

Parameter
Value
Batch Size
128
Baseline Value
0.3
Max FW Iterations
200
FW Momentum
0.9
Regularisation À
0.25
Max NN Passes
5
Arthur LR
le-4
Merlin LR
le-4
Morgana LR
le-6
Table 3: Values of various parameters used in training.
C.3 PURFLY COOPERATIVE SETUP AND "CHEATING" FOR MNIST
Here, we discuss the Merlin-Arthur classifier when only Merlin used with no Morgana. Our results demonstrate that the inclusion of Morgana is necessary for Merlin and Arthur to exchange meaning- ful features and abstain from "cheating". For a purely cooperative setup, information about the class c(x) that Arthur infers is dominated by the fact that Merlin chose that feature, rather than the fea- ture itself, i.e, [c = 6) < y E Φ). We can upper bound (c(()) (()) = through the classification error Pe that Arthur and Merlin achieve via Fano's 's inequality (Fano 1961
H (c) Φ) s (Pe) + P. log( (1C) 1),
where (CI is the number of classes. We then bound the amount of information that is transferred by the choice of the mask rather than the feature itself as
I [c((x; M(x) = o) - ( E Φ) Hc(yy) y E E) - H[((x) M o) H(cly) y E ②) (Ho(P.) + P. Polo((CC 1)).
We define the cooperative information as Loopp max (0, (c(y) (Ho(P.) + P. log([C|- 1))),
which lower bounds how much Arthur and Merlin "cheat". We train Merlin and Arthur the MNIST dataset and show the results in Figure [ that the purely cooperative case fcoop keeps the classification error low despite exchanging uninformative features. Including Morgana the other hand pushes Aospp to zero even for small masks. In this case Merlin produces highly informative features.
Figure 14depicts "Cheating" measured by Icoop over the MNIST test dataset (restricted to 5 classes) for different setups. In purely cooperative setup, Arthur and Merlin learn to communicate over uninformative features. Thus, the classification error Pa stays low, while the conditional entropy of the class with respect the feature goes up. When Morgana is present and soundness is high (in analysis e, 0.05), Arthur and Merlin cannot cheat, the classification error increases for small k.
Why is this observation important? Note that the purely cooperative setup could already be seen as interpretable. With Merlin as a network it appears as version of self-interpreting network. With Merlin an optimiser, it is similar to Rate-Distortion Explanations (RDE) (Macdonald al. 2019). In fact, RDE have been criticised for producing "cheating" masks that artificially create features that were not present in the original image (Wäldchen al. (002)). We connect this the lack of robustness with respect to Morgana. Designers of self-interpreting setups need to explain how they circumvent the problem of "cheating" masks.
Figure 15 depicts the results from the main paper in more detail. Specifically, it depicts averages and the standard deviation as error bars for each parameter using samples from different training runs. The results presented here are consistent with those presented in the main body of the paper, except for the class networks. The error bars are large for small mask sizes, but shrink as the mask size increases. The even though was conceived as stabler alternative to the simple network approach. One possibility might be that since each UNet both cooperates with Arthur and wants to fool him, they more
approach is considerably less stable than
other implementations,
31

---

Merlin: Opt
Merlin: Opt, Morgana: Opt
1
1.0
+
BonY MIX
0.8
0.6
0.4
0.0
2
4
8
16
32
2
4
8
16
32
Merlin: Net
Merlin: Net, Morgana: Opt
1.2
Gopp
HICMIY &
HICLYII e M2X
0.8
0.4
0.0
2
4
8
16
32
2
4
8
16
32
k:
k:
Figure 14: This figure depicts the mean and standard deviation over 10 training runs for the error probability, cooperative information and the class entropy. This was obtained from 5-class classification with classes 1,2,3,4 and 5 with y = 0.75 for the purely cooperative setup (lefi) and the adversarial setup (right), where Merlin was realised as optimiser (lop) or as neural network (bottom).
sensitive when Arthur changes his focus between achieving good soundness and completeness. We hope that further research will determine if this realisation can be trained in a stable manner.
We also conduct experiments to illustrate the impact of varying values of 7. The results of these are depicted in Figure [6] As expected, increasing the value of y increases the error rate as it gives more weight to Morgana. This increase is not visible the NN only setup, indicating this setup may not be creating high quality masks.
C.4 CENSUS INCOME EXPERIMENTS WITH MARITAL-STATUS AND RELATIONSHIP INCLUDED
we demonstrate how an adversarial setup prevents a typical approach to manipulating explanations that has been demonstrated for numerous XAII methods. To show the effect most clearly, we kept the focus on a single sensitive feature ("sex") and removed the "relationship" and "marital status" features that strongly correlate with it and are thus informative. We now show the results for the experiments including these features in Figure where Merlin uses these features communicate "sex" with completeness of 71%. %.
In Section 3.1
32

---

Opt
Hybrid
1.0
0.6
0.4
0.2
2
4
8
16
32
64
2
16
32
64
k
K
Net
CN
1.0
0.8
0.4
0.2
0.0
32
64
2
16
32
64
k
k
QD(M)
QD( QD(M)-Boune
Figure 15: We show the mean and standard deviation training runs for completcness and soundness, along with the average precision bound as obtained from 2-class classification with classes with 7 = 0.75 for different settings.
0.150
P.
0.125
Laep
0.03
Lasp
I
HICYHHY M(X))
- HICAYI M(X)
0.100
0.050
0.025
0.01
0.000
0.2
0.4
0.6
0.8
Figure 16: This figure depicts the error probability, cooperative information and the class entropy as obtained from 2-class classification with classes and for different values y mask size of 16 for the Hybrid (left) and Network (right) settings
Completencss
Completeness
0.6-
6.6-
0.4
0.4-
0.24
Completenccs
33
1.0 Completenese 90.025
24)
0.07
3.5
84
36)
0.67
111
6.4


Reviews:
[{"review_id": "paW2VHodWad", "reviewer": "Reviewer_zBZW", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 new framework for interpretable machine learning relying on interactive proofs ideas. The approach relying the adversarial training of two agents resulting in the most informative features for a given task. The authors provide theoretical results on the performance of the agents, as well as demonstration on a few numerical settings.", "summary_of_the_review": "In summary, my current understanding of the method (given the confusing definitions in point (1)) leads me to believe that the approach described here is very interesting and a nice contribution. To be certain about this, however, I would need clarification on my comments above, and potentially re defining some of these elements and statements. In closing, I want to stress that while some of my comments above might appear as requiring the authors to make the limitations of their method more explicit and clearer, it is the opinion of this reviewer that this will only increase the value of this contribution - and with it, my support for this paper.", "strength_and_weaknesses": "The framework is very interesting, novel and valuable to the community. At the same time, several components of the presentation are unclear, and I parts are severely overstated, ignore previous results, and should be addressed before publication.\n\n\n1. Respectfully, I find a lot of the technical presentation and definitions confusing and, at best, non standard. Let me elaborate:\n\na) A \"dataset\", D, is never defined. The word \"dataset\" is typically used to refer to a finite collection of samples drawn from a distribution (see [1] and [2] for classic references). It seems that this might not the case here, however, because (looking at Example 2.2, $D\\subset [0,1]^d$, so $D$ can be interpreted rather as a sample space. On the other hand, in other parts of the manuscript, the authors insist of having $D$ be a collection of data. This leads to (at least) two other problems: i) is this collection finite? It seems that it is, otherwise the second loop in Algorithm 1 would never finish, and ii) If it is finite, and the models are trained on this, all of the analysis regards the features that are obtained from this finite training set, and not on the expected performance of the respective metrics over a new sample. \n\nb) The authors choose to define \"feature\" in terms of *subsets of possible samples* from a dataset. This is not what we refer to features in statistical learning (again, see [1,2] for definitions). This leads to other confusing (if correct?) statements, like: \"$x$ **contains** a feature $\\phi$ if $x \\in \\phi$\". The notation also makes it unclear to understand how features depend on specific samples. E.g., in Eq. (2), $M^*$ depends on a sample $x$, but it's not clear to the reader that $\\phi$ is a subset of a specific sample $x$.\n\n2. A few aspects of the presentation of this work are highly overstated: the authors insist this is \"the first provable interpretability guarantees\". This is incorrect for a couple of reasons: \n\na) There is a number of approaches that provide probably correct explanations for machine learning classifiers. All of these rely on certain assumptions, that vary in complexity. Moreover, in many settings these algorithms are not only correct but also efficient. E.g., the work [3] presents a linear time algorithm for instance wise feature importance scoring on black-box models based on the Shapley framework. The work in [4] does something similar, providing linear time algorithms for provably interpretability of imaging data for general predictors under mild assumptions. \n\nb) Importantly, the methods above (as the majority of the explainability methods for 'off-the-shelf' predictors) are applicable to any given classifier. The method proposed in this work *is not*, and cannot be applied to any given model. Instead, this manuscript proposes to train *a new* classifier (Arthur) that is inherently interpretable, as it is so that it relying only on specific features. This is a totally valid strategy, and indeed a very interesting alternative approach to interpretable ML, but this difference should be made clear and precise to the reader. Moreover, work on this vein has also been explored in what I believe is the most closely related work to this manuscript [5]. Similar to this work, the work in [5] also provides provably correct interpretable predictors that rely on a finite number of features (or queries).\n\nc) Even while the authors provide guarantees for their general method, the application of these ideas do not inherit these nice properties because -as the authors state- convergence to an equilibrium point is not guaranteed, and since their models are trained on finite datasets only. Furthermore (probably inheriting my confusion from point (1)), the results seem to hold only for the training set.\n\nGiven all these points, the statement that the authors provide \"the first provable interpretability guarantees\", and its variations that appear throughout the text, are grossly incorrect. The authors should moderate these comments, and they should better situate their contribution in light of these previous results. The authors should not worry about this, however - their proposed method is very interesting regardless!\n\n\n3. An important limitation of the presented approach, that is stated simply in passing, is that they can only consider realizable learning problems: they consider that the label is determined by a concept function c(x) (i.e. the Bayes Risk is 0). The authors should consider making this very explicit, as it is far from a mild assumption in a statistical learning problem (e.g. this likely does not hold for the UCI Census Income dataset).\n\n4. After presenting their main result, and commenting on the implications of the theorem 2.8, the authors informally introduce the notion of \"asymmetric feature concentration (AFC)\", $\\kappa$. From their explanation, it's clear that this is a key property of classification problems, and Lemma 2.9 attempts to characterize this (providing an upper bound to $kappa$). However, $k$ is never defined formally, so it's basically impossible to interpret the utility of Lemma 2.9. This AFC is later formalized and defined in the appendix, but is important to the reader to have some aspects of this more precise definition in the main corpus of the story - otherwise, there's little utility in having Lemma 2.9 in the main body of the paper.\n\n5. Towards the end of section 2, the authors comment on \"biased samples\", but they never define or otherwise make precise what they mean. Could you clarify? \n\n6. Lastly, the empirical validation is (imho) a bit limited. Moreover, the authors comment that for the Census Income dataset, they remove the 'relationship' and 'marital status' features as they were strongly correlated with the variable 'sex'. Does this mean that the method is very sensitive to correlated features? Why would this be the case? I suggest the authors to include these results in their paper too, and comment on this limitation. This can only clarify the presentation of your method.\n\n\n[1] Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.\n[2] Mohri, Mehryar, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.\n[3] Chen et al. \"L-shapley and c-shapley: Efficient model interpretation for structured data.\" ICLR 2019.\n[4] Teneggi. \"Fast hierarchical games for image explanations\" IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022\n[5] Chattopadhyay, Aditya, et al. \"Interpretable by Design: Learning Predictors by Composing Interpretable Queries.\" arXiv preprint arXiv:2207.00938 (2022).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "fTAURN_vwt", "reviewer": "Reviewer_YnKy", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 proposed a multi-agent interactive game that provides formal interpretability for classification problem. In particular, the interactive game is inspired by interactive proof systems. In addition, the authors connected information measures such as conditional entropy and average precision to completeness and soundness metrics. On top of that, the authors introduced numerical implementation that works in a few settings.\n", "summary_of_the_review": "The paper is interesting, but a similar idea has been discussed which I hope the authors could address in the next revision. With proper discussions and comparisons with the existing work and improved writing, I may consider increasing my score. Overall, the paper in its current form is not enough to warrant acceptance.", "strength_and_weaknesses": "Strengths:\n- The paper studies an important problem with potential high impact on AI safety.\n- The connections between informations metrics to completeness and soundness are quite interesting\n\nWeaknesses:\n- The authors missed one existing work of similar idea. The authors claim many times in the paper about \"for the first time\" in some of their contributions. However, the idea of prover-verifier game is not new and has been carefully discussed in [1]. In particular, [1] proposed a prover-verifier game to encourage learning agents to solve decision problems in a verifiable manner, which overlaps significantly with this paper. \n- The paper is hard to follow, especially for the technical parts. The authors should consider improving the writing. Particularly, I find the notations in section 2 a bit awkward. For example, the notation of $x \\in \\phi$ was used to denote a data point $x$ contains a feature $\\phi$, which is quite weird given we typically use to specify an element $x$ is in the set $\\phi$. In addition, the authors use this notation in conditioning, which makes it even more confusing. Another example is the use of $D$ and $\\mathcal{D}$ in Theorem 2.8.\n\n\nOther comments and questions:\n- What is the main usage of of average precision? The authors derived the bound for average precision, but why such a quantity is useful in interpretability?\n- Should the loss of Morgana to be $$-\\log \\left(A(s \\cdot x)_0 - A(s \\cdot x)_{-c(x)} \\right)$$?\n- In Figure 5 (1), why only report the predictions of Merlin but not Morgana's?\n- For Figure 6, it seems quite clear that the precision would go to 1 if one increase $k$. Does that suggest that it is trivial to get a tight bound in that regime?\n- The game involves both cooperative and adversarial components. Often the case, such a game is difficult to solve (in terms of finding equilibrium)? Is this the case in your experiments?\n\n\n\nReference:\n[1] Learning to Give Checkable Answers with Prover-Verifier Games, 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TA_ymYncib", "reviewer": "Reviewer_LYB7", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 to train classifiers with guaranteed Anchors-style interpretability by structuring the classifier in two parts: a feature selector and a classifier that is only provided the selected features. During training, the classifier portion is also subject to adversarial feature selectors. The features selected by the first component thus may serve as an explanation of the classifier's output: under some conditions on the data and families of classifiers, the chosen features are sufficient to indicate the class. Some simple experiments suggest that the method can be applied to neural networks that achieve good performance in practice (on MNIST...) and illustrate resistance to manipulation.\n\nIncidentally, although the paper suggests that it is inspired by \"interactive proofs,\" there is not much interaction to speak of: the prover sends a message to a verifier who accepts or rejects. It's much more accurate to say that it's an NP style certificate. Calling it an interactive proof only makes it misleading to those who know what that means, and mysterious to those who don't.", "summary_of_the_review": "I find the idea interesting and I hope the authors give it the presentation and evaluation it deserves.", "strength_and_weaknesses": "The main strength of this paper is that it does seem to suggest a way to obtain reasonable explanations while still using modern neural network methods. The adversarial training method overcomes some kinds of spurious \"explanations\" that may crop up when merely enforcing, e.g., sparsity of the chosen features.\n\nThis paper may have potential, but the current submission has some serious weaknesses:\n\n- The key quantities of \"AFC\" and imbalance of the prover/adversary that underlie the theoretical guarantee are named and even suggested to be helpful in thinking about interpretability, but they are *not* defined or sketched in the paper. I know they are in an appendix, but I'm not sympathetic to attempts to circumvent the page limit by punting the main concepts to the appendix. It doesn't bode well for their conceptual clarity when they could not be described in the main submission. It also makes it difficult to judge the strength of the theorems. I have no idea whether or not the assumption that these quantities are small constants is actually reasonable, and no evidence is presented for the assumption.\n\n- The experiments are very limited: there is one data set for each point the paper seeks to make regarding manipulation and effectiveness, respectively the UCI census data set and MNIST. (Incidentally, Deng 2012 is certainly not the origin of MNIST... it's LeCun et al. 1998) The experiments are thus illustrative but not so convincing: how broadly do the claims hold?\n\n- While explanations using a small number of features is generally desirable, the method as presented seems to scale exponentially with the number of features, which may not be adequate for more complex tasks -- for example, even for a task like CIFAR, it isn't clear to me how effective this would be. (This also ties into the previous issue)\n\n- (relatively minor) The formalism of feature spaces used in the paper seems to only serve to obfuscate the presentation. As far as I can tell, it plays no actual role in the development, and ultimately the explanations are just fixing small subsets of the coordinates to given values when viewing each input as a vector. (If the authors are looking for something to cut in order to introduce the key quantities, this discussion does more harm than good in my opinion.)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "7AzbYjwTEqE", "reviewer": "Reviewer_Pt1p", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The authors describe a classification framework that consists of a verifier (Arthur) and two provers (one collaborative [Merlin] and one adversarial [Morgana]). The provers aim to convince/trick the verifier in making a correct/incorrect classification. \n\n**Theoretical results:**\n* **Mutual information bound at equilibria:** The authors prove that if Arthur has low error rate, then at the minimax equilibrium, the features selected by Merlin have very high mutual information with the label. \n* **Bound on average precision in terms of dataset Asymmetric Feature Concentration (AFC), relative success rate and class imbalance:** The authors give a bound on average precision using a couple concepts they define, such as AFC and relative success rate. \n\n**Empirical results:**\n* **Training algorithm:** The authors provide an algorithm to solve for the equilibria of the proposed framework. \n* **Results:** The soundness of the framework and the proposed bounds are tested on a low-dimensional tabular dataset (UCI dataset and MNIST). \n\n**Contributions:**\n* **Theoretical results:** Derives bounds on the mutual information between the label and the features selected by the framework described in the paper (bounds are quite similar to those derived by [1]). \n* **Defining Asymmetric Feature Concentration:** The authors define \"asymmetric feature concentration\", a quantity that characterizes when  \"a set of features is strongly concentrated in a few data points in one class and spread out over almost all data points in another\". They later use this to bound the average precision of a given feature selector. Both this concept and this bound (as far as I now) are novel \n* **Experiments:** Demonstrates the proposed method on a low-dimensional tabular dataset (UCI data), and the theoretical bounds on MNIST. \n\n[1] Chang, Shiyu, et al. \"A game theoretic approach to class-wise selective rationalization.\" Advances in neural information processing systems 32 (2019).", "summary_of_the_review": "This paper presents a promising framework to address an important and timely problem. It is written well and some of the theoretical results are novel and interesting. \n\nThe main issues with the submission are lack of novelty (both regarding the framework and the theoretical results) and a sufficient discussion of existing literature, which form the basis of my recommendation. A (potentially significant) rewrite that places the proposed framework/results within the existing literature and puts the emphasis on the theoretical results (especially revolving around AFC) would, in my opinion, make this submission a worthwhile contribution to ICLR. ", "strength_and_weaknesses": "**STRENTGHS:** \n* **Important and timely research direction:** Interpretability methods that provide guarantees is a very important research direction, and the discussed method tackles this very important problem. \n* **Clear writing and exposition:** The paper is written very well and the concepts are described with clarity. \n* **Formalization is done well:** The way the theoretical results are phrased and derived look sound. The proofs also appear to be correct. \n* **Bounds regarding AFC is novel:** The bounds regarding AFC (lemma 2.9 and Theorem 2.10) appear to be novel. The concept of AFC seem to be useful when dealing with certain types of datasets where the \"a set of features is strongly concentrated in a few data points in one class and spread out over almost all data points in another.\" Theorem 2.10, as far as I know, is interesting and novel. \n\n\n****\n\n**WEAKNESSES:**\n* **Missing crucial references:** The submission doesn't cite related work that, in aggregate, cover a big portion of the claimed contributions. \n  * \"A game theoretic approach to class-wise selective rationalization.\": [1] This paper proposes an interpretability framework that describes an extremely similar decision pipeline (adversarial and collaborative agents and a \"verifier\"). **This paper also provides bounds mutual information on the features and the labels** that seem to be analogous to the results reported in the current submission (though not identical0. Both submissions constrain the provers as feature selectors (i.e. masks on all input features) and work with very similar loss functions. There are subtle differences (i.e. the submission allows the verifier to output \"I don't know \" explicitly), but these don't represent conceptual disagreements. The \"cheating\" failure mode described in the submission is described as \"degeneration\" in this submission.\n  * \"Learning to Give Checkable Answers with Prover-Verifier Games.\": [2] This submission **also explicitly proposes a framework with a prover and a verifier aimed at discovering complete and sound proof-verification protocols**. Here, the collaborative and adversarial components are condensed in a single prover with a different loss function. The prover isn't constrained to output masks in this case. This paper also explicitly links it's contributions to Interactive proof systems. \n* **Limited novelty:** Given the above prior works (along with the \"AI Safety via Debate\" paper, which the authors cite), the conceptual contribution of this submission is significantly diminished. Contrary to what the authors claim, this is not the first method that achieves feature based interpretability. \n* **Experiments are not real-world as claimed:** While the authors claim that they use real-world datasets to display the proposed algorithm and the theoretical bounds, the results are only limited to the UCI Census Income dataset (which is simple enough to support exhaustive search over selected features) for displaying the algorithm, and the MNIST dataset to display the theoretical bounds.\n* **Proposed training algorithm is not practical:** Algorithm 1 (Merlin-Arthur Training) requires finding the argmin/argmax of the agents at each iteration, and appear to be very difficult to scale to more difficult/larger problems. \n* **Theorems assume minimax optimality:** The proofs assume that an equilibrium of the proposed game is found. To complement this, an algorithm to check if an equilibrium has been found (or approximated to a sufficient degree) is needed. Solutions that appear to be near an equilibrium might behave significantly differently than how solutions at the equilibria could. This limitation, I believe, should be highlighted in the Limitations. (happy to be \n\n****\n\n**QUESTIONS TO AUTHORS:**\n* **About resistance to existing interpretability manipulation techniques:** Among the contributions, you list \"We show that our setup is resistant to existing interpretability manipulation techniques.\". Do you mind elaborating on which experiments support this claim? \n* **The \"I don't know\" option:** Is allowing Arthur to output \"I don't know\" essential in establishing the theoretical/empirical results? It seems like assigning uniform probability to all output logits would be an equivalent way for a classifier to say \"I don't know\". Is there a clear benefit to keeping having this as a separate option? \n* **Question about Example 2.2** It seems like $y$ isn't defined on coordinates that are not in $S$. Later in the experiments, you mention that these coordinates can be an arbitrary value or 0s. Just wanted to confirm if the definition somehow subsumes this.\n* **AFC of real world datasets:** Why do you think the AFC of real-world datasets will likely have and AFC of 1? \n* **Why remove relationship and marital status features?** Could you explain why it was necessary to remove relationship and marital status features features from the dataset? In many cases removing such separate but highly correlated features is not possible (either because feature separation isn't possible in the input space, or because one doesn't know which features are highly correlated. Time permitting, could you show the results when you don't remove these features? How does the performed protocol behave in that setup? \n* **Are the results on UCI and MNIST datasets evaluated on a separate test set?** Just wanted to check if the trained feature extractors are evaluated on an unseen split. \n\n\n\n[1] Chang, Shiyu, et al. \"A game theoretic approach to class-wise selective rationalization.\" Advances in neural information processing systems 32 (2019).\n[2] Anil, Cem, et al. \"Learning to Give Checkable Answers with Prover-Verifier Games.\" arXiv preprint arXiv:2108.12099 (2021).\n\n", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject