XAudit : A Learning-Theoretic Look at Auditing with Explanations
Authors: Chhavi Yadav
Michal Moshkovitz
Kamalika Chaudhuri
Venue: Accepted by TMLR ()

Abstract: Responsible use of machine learning requires models to be audited for undesirable properties. While a body of work has proposed using explanations for auditing, how to do so and why has remained relatively ill-understood. This work formalizes the role of explanations in auditing using inspirations from active learning and investigates if and how model explanations can help audits. As an instantiation of our framework, we look at `feature sensitivity' and propose explanation-based algorithms for auditing linear classifiers and decision trees for this property. Our results illustrate that Counterfactual explanations are extremely helpful for auditing feature sensitivity, even in the worst-case. While Anchor explanations and decision paths may not be as beneficial in the worst-case, in the average-case they do aid significantly as demonstrated by our experiments.

Published in Transactions on Machine Learning Research (07/2024)
XAudit : A Searning-Theoree Look at Auditing with Ex- planations
Chhavi Yadav
cyadavEruedd edu UC San Diego
Michal Moshkovitz
michol. nhichal.moshkoottsBubbooo bosch..ccomo.ooooooomoo Bosch Center for A1
Kamalika Chaudhuri
kamalika Bcs wws.csdkkk@o....d........ UC San Diego, Meta AI
Reviewed on OpenReview: https: // openreview. net/ poruf? id=
wdtg:nyyddgPppPpppppe gPtjyeXekg
Abstract
Responsible use of machine learning requires models to be audited for undesirable properties. While a body of work has proposed using explanations for auditing, how to do so and why has remained relatively ill-understood. This work formalizes the role explanations auditing using inspirations from active learning and investigates if and how model explanations can help audits. As instantiation of our framework, propose explanation-basee algorithms for auditing linear classifiers and decision trees for this property. Our results illustrate that Counterfactual explanations are extremely helpful for auditing feature sensitivity, even in the worst-case. While Anchor explanations and decision paths may not be as beneficial in the worst-case, in the averago-caso they do aid significantly as demonstrated by our experiments.
look at 'feature sensitivity' and
1 Introduction
The recent success of machine learning (ML) has opened up exciting possibilities for potential societal applications Bojarski et al. (2016); Aini et al. 2020);; Castiglioni et al. (2021). However, this kind of wide- spread usage requires us to be able to audit these models extensively and verify that they possess certain desirable properties related to safety, robustness and fairness.
So far, due to complexities in the ML pipeline and the black box nature of most models, auditing has been primarily performed a somewhat ad-hoe manner, usually by creating a separate audit testing set [Soares al. [0023). This, however, leaves open the question of what an audit really signifies. Additionally, recent
body of work has also posited that local explanations might be helpful for auditing Bhatt et al. (2020 Oala
et al. )0 ; Adebayo and Gorelick (2017); Watson and Floridi (2021): Zhang et. al. (2022) Poland (022
Hamelers [2021]; Carvalho et al. 2019 however, in the absence of a formal framework, how or why precisely
this is the case is not understood.
Recently, Yan and Zhang (2022) has made one of the first attempts providing a formal framework for auditing and proposod principled auditors for auditing demographic parity with rigorous guarantces. However limitation of their work is that they do not incorporate explanations into their framework. We take this line of work forward by formalizing the role of explanations in auditing.
In the context of auditing, the auditor due to confidentiality reasons this hidden aspect is what makes the task of auditing challenging and consequently, the auditor's objective to acquire insights into the concealed model. To achieve this, the auditor queries data points to the data scientist and in turn the data scientist responds with labels and (local) explanations. This paper aims measure whether the supplementary information derived from explanations, beyond mere labels, effectively diminish the query complexity of auditing.
is held by data scientist and not revealed to the

---

Published in Transactions on Machine Learning Research (07/2024)
In this paper, consider auditing 'feature sensitivity', for two hypothesis classes with different local ex- planation methods - linear classifiers with counterfactual and anchor explanations and decision trees with decision path explanations. We provide auditing algorithms and theoretical guarantees for these cases. Our results illustrate that explanation methods differ greatly in their audit efficacy - while worst-case anchors do not provide any additional information than predictions themselves and with decision paths lotal queries scale linearly with number of nodes the tree in the worst-case, surprisingly counterfactuals greatly bring down the query complexity of auditing to a single query when considering feature sensitivity.
We empirically evaluate our proposed auditors on standard datasets. Our experiments show that unlike the worst case, 'typical' anchors significantly reduce the number of queries needed to audit linear classifiers for feature sensitivity. Additionally, our proposed Anchor Augmentation technique helps reduce the query complexity over a no-anchor approach. Similarly, our experiments on decision trees demonstrate that the average number of queries to audit feature sensitivity is considerably lower than number of nodes in the tree.
Could there be more general auditing strategy in our framework? We next show that this is possible. By drawing on connection between auditing and membership query active learning, provide strategies for two critical aspects of any auditor picking the next query and stopping criteria. We show that our general strategy leads to successful auditing when the property to be audited is testable - in the sense that it can be inferred based on making queries to the model.
To summarize, our contributions are as follows.
1. We formalize the role of explanations in auditing and propose explanation-based algorithms to audit feature sensitivity in linear classifiers and decision trees.
2. We empirically illustrate that unlike the worst case, in the average case, explanations help reduce the query complexity of auditing feature sensitivity significantly.
3. We propose a general strategy for auditing (and with explanations) by drawing a conncction between auditing and active learning.
4. Finally, we discuss ways of dealing with an untruthful data scientist and the privacy concerns arising from auditing.
2 Preliminaries
The four key components involved in an ML audit are : 1) Data Scientist (DS), 2) Auditor, 3) Model to be audited and 4) Auditing Property (AP). DS is the one who holds a model which it cannot reveal for confidentiality reasons, while an Auditor is an external entity who wants to verify certain properties of the hidden model. We assume that the auditor has query access to this model through the DS. The hidden model, h X' x {-1, 1}, belongs to hypothesis class H. We assume that the hypothesis class is known to the auditor. Let the instance space X = Rd.
The auditor will audit the model held by the DS for a specific auditing property that we measure quantita- tively by a score function s H + [0, 1]. This function has a value of zero when the property is absent in the model and a high value when the model exhibits the property to a large extent. Auditor knows the exact form of the score function but does not know its value for h (since h is hidden).
We expect an auditing property to satisfy the notion of 'testability', defined below. Testability ensures that the property of hypothesis can be determined by making queries to instances & E X. Absence of testability makes it possible to have two hypotheses that agree on every input in the instance space, yet may have very different values of the property (for instance, robustness to distribution shifts or adversarial allacks). Auditing this kind of a property would require more information than simply queries.
Definition 1 (Testable Auditing Property). An andiling properly defined by score function 8: H + [0, is testable using an instance space X if the following holds; for any hy, h2 H if h1(x) h2(2) Vr E X, then s(h,)= = s(h2).
When a query is asked to the DS, it returns the corresponding label and a local explanation. Both the DS and auditor agree upon a specific explanation method before auditing begins. Let en X + E denote this explanation method where & represents the codomain of e, and h H. We assume that the DS is truthful,
2

---

Published in Transactions on Machine Learning Research (07/2024)
meaning the labels and explanations returned for y h(x) and (x) respectively. In 6 discuss what happens when this assumption does not hold.
At the end of the auditing process, the auditor responds with an answer Y, which takes values {Yes, No).
This is a random variable since both the DS and auditor can be randomized algorithms.
Next we conceptualize the auditing process as an interaction between the DS and auditor. Our protocol is as follows.
At each time step = 1.
1. Auditor picks a new query Te E X and supplies it to the DS.
2. DS returns a label E y and an explanation ea E E to the auditor.
3. Auditor decides whether or not to stop. If auditor decides to stop, it returns a decision Ya E (Yes, No), otherwisc it continues to the next time step.
Furthermore, we formally define what makes successful auditor at the end of the auditing process.
Definition 2 ((e, -uadiioo,)). An auditor is an (aaditt for e, 8 E [0, 1], hypothesis class H. and a score function s(-) if 4h E H the following conditions hold 1) if s(h) > c, Pr(Y. Yes) 2 5 and 2) if shh = 0, Pr(Y. = No) = 1.
The first condition pertaining to soundness implies that a successful auditor should return a Yes with high probability when AP followed by the model to a large extent. The socond condition measures completeness, and requires the auditor to say No when AP is not followed at all. Observe that when 0 s(h) S e, we cannot place guarantee on the auditor's decision with finite query budget.
Query complezity T of an (c, d)-auditrr is the total number of queries it asks the DS before stopping. Efficient auditing requires that T be small.
3 An Example of Auditing Through 'Feature Sensitivity'
A popular auditing property in the literature has been demographic parity. But this notion applies exclusively to fairness and is distribution dependent. In contrast, we focus on 'feature sensitivity'.
A feature is termed sensitive if changing its value in the imput leads to different prediction. Identifying such features can lead to insights into model's working and uncover spurious correlations and harmful biases that it may have learnt. For instance, while auditing model that predicts the presence of lung cancer based on radiology image, a human auditor may suspect a feature in the input, such as the presence of pen markings on X-rays, to be spuriously correlated to the output. Another example is when an auditor might suspect that an input feature such as home zipeode, which might act as a proxy for race (not included in the data), may be correlated with loan rejections. In both cases, the goal is to audit if a model is sensitive to a specific input feature. Note that our presented techniques can easily extend to multiple sensitive features by repeating the same procedure for different features. When features are correlated, we assume that there is a third party, for eg. regulator a government entity, which guides what features are correlated and what features should be audited for.
Let the feature that we wish to audit the sensitivity of be called a feature-of-intersst (Fol). Let pair Pij denote a pair of inputs xf, E X' which are same in all but the feature-of-interes.. The pair Pij is called a responsive pair if the predictions for x' and x² are distinct. These pairs need not be constructed from a data distribution and can be artificially synthesized like in membership query active learning and therefore the correlations according to data distribution need not be respected. Unless mentioned, predictions are made by the model h. Lastly, our feature-of-nnterss is a sensitive feature for the model if one or more responsive pairs exist.
The score function for feature sensitivity is the probability that a randomly drawn pair from the set of all pairs P a responsive pair and given as s(-) Pr (Pp is a responsive pair). When P is finite, the score function can be interpreted as the fraction of responsive pairs. Usually when the score function is probabilistic, knowledge of the underlying distribution is required in order to estimate its value. However, in
3

---

Published in Transactions on Machine Learning Research (07/2024)
the following sections, give anditing decision without computing the value of score function explicitly, by using the structure of the class and explanation methods. We next prove that feature sensitivity is a testable property.
Theorem 3.1. Feature Sensitivity, given by s(.) = Prppee(Pp is a responsive pair), testable for a by pothesis class H. using the instance space X R
Proof. Fix two hypothesis h1, h2 E H such that Vo E X holds that (1)2) - h2(2)). Fix a pair 1;) ) X. This pair responsive according h1 if and only it is responsive according to h2, i.., h1 b1,)) o h1(x,) = he (2re)) o h2(ar))- Thus s(h1) s(h2) and it is testable for H.
A Simple Baseline: Random Testing. An easy way to detect feature sensitivity for any hypothesis class is to query a large number of pairs at random from the DS. The feature is sensitive if any responsive pair exists. This algorithm would need to query O log !) pairs to be an (c, d)-anditor.
Note that this baseline is independent of the hypothesis class. Tt does not need find out what the hidden h is, even partially, in order audit and doesn't use explanations either. However, lot of pairs have to be queried for small Next discuss cases where using explanations and exploiting the structure of hypothesis class leads to more efficient auditing.
3.1 Linear Classifiers
Our first hypothesis class is Linear Classifiers, defined Hio sign((w) (wW z) b). Responsive pairs exist with respect to h E HLC and for feature of interest I; if and only if weight w; is non-zero.
where hw,(()))
3.1.1 Counterfactual Explanations
Given an input r and a model h, a counterfactual explanation Laugel et al. (2017): Karimi et al. (2020) returns the closest instance L2 distance such that h labels x' differently from
; Deutch and Frost (2019)
More precisely, x arg || x'||2-
We observe that for linear classifiers the difference x x' is parallel to w. This fact be exploited by auditor, which returns a decision by simply checking if x - x' is zero in the ceaturo-f-iitterstt We use these
insights to design an auditor that uses a single random query to audit, denoled by AlgIC. !
Algorithm AlgLC. : Auditing Lincar Classifiers using Counterfactuals
1: Query any point from the DS Auditor receives label y and explanation x' from the DS
à <- - x'
4: if ú; = 0 (ith feature is the Fol) then
5: return No
else
return Yes end if
Theorem 3.2. For any e E [0, 1], auditor AlgLC, is an (e,0)-auditor for feature sensitivity and hypothesis class HLC with T = 1 query.
Proof for the theorem can be found in the Appendix A.2
Counterfactual explanations enable the auditor to partially learn the hidden via a scaled (not exact) version of the weights, which then utilizes to make decision. This serrial-larmiing-as-----ddd
way efficient than completely learning a linear classifier without explanations, which requires O(d !) queries in the active learning setting $4 Also note that we allow the explanation to be found from the instance
4

---

Published in Transactions on Machine Learning Research (07/2024)
space rather than the training set. This is because an example in the training data may be too far to be considered a good counterfactual explanation and if counterfactual with some property (for instance an actionable counterfactual) is desired then the training data may not contain a relevant counterfactual example Karimi et al. (2020) Deutch and Frost (2019).
3.1.2 Anchor Explanations
Given a model h, an instance I, a distribution D, and a precision parameter T, an anchor explanation Ríbeiro et al.] (2018) returns a hyperrectangle Ag such that (a) Ag contains x (b) at least T fraction of the points in Ag under have the same label h(r) Ribeiro et al. (2018] Dasgupta et al. (2022). Specifically, T= Ar,' (h(x)) h(z')). Here, the procision parameter 7 mcasures the quality of the anchor explanation. To describe the quality of an anchor explanation, we also use a coverage parameter, c- which is the probability that point sampled according to D lies in the Ag, c PIz-~D(a' Az). The distribution D is used by the DS to create anchor explanations. Refer to the appendix for notes on how to deal with imperfect precision.
We consider homogeneous linear classifiers (b- = 0) in this section; however our techniques can be easily extended to non non-homooeee hon-hooogessous linear classifiers by considering d + 1 dimensions and concatenating 1 to x and b to w. For simplicity, we assume our anchor explanations have perfect precision.
We propose an auditor with anchors inspired by the active learning algorithm of Alabdulmmossin al. (2015) which does not use explanations. Their goal is to learn a hypothesis by maintaining search space over hy- potheses and narrowing it down actively through label queries. They construct an ellipsoidal approximation of the search space at each step, ex = ["",E)) where μz is the center and E is the covariance matrix of the ellipsoid. Next they extract the top eigenvector of a matrix comprising of the covariance matrix of the ellipsoid. This eigenvector serves as the next synthesized query to the oracle. Our auditor uses this skeleton to audit by maintaining a similar search space and narrowing down for
Our contribution to the aforementioned algorithm is new method for incorporating anchors into it procedure that we call Anchor Augmentation for potentially higher auditing efficiency. The main idea is that anchor explanations give region of space around a point x where labels are the same that of x; using this fact more synthetic already labeled examples can be generated for free without actually querying the DS and fed into the algorithm. Through these insights we design an auditor AlgLC, a $2 for lincar classifiers using auchors. This auditor first learns the hidden h and then checks the weight of the leature of interest to return a decision.
Notation used in AlgLC, In AlgLC,, e!* (n** E denotes the largest ellipsoid that approximates the search space (corresponds to search space in our case) at time t where n²* is the center and g is the covariance matrix of the ellipsoid at time t. N is the orthonormal basis of the orthogonal complement of n²* and N² is its transpose. a² is the top eigenvector of the matrix N S In the implementation by Alabdulmohsin et al.] (2015). some warm-up labeled points are supplied by the user, we denote this set as W. Let (1)) denote the 1-th element of this set. Let the 2th feature be the feature of interest without loss of gencrality.
Worst Case Query Complexity. Anchor explanations returned by the DS can be absolutely consistent with the input and truthful, yet be worst-case. For instance, in the ID case, where linear classifiers are thresholds, all the anchor points can lic on one side of the input point away from the threshold this maintains truthfulness and consistency of the explanation - but do not help in identifying the threshold anymore than the input point itself. Generalizing this to higher dimensions, worst-case would mean that the shrinkage of the search space over hypotheses with and without explanations is the same. For the aforementioned algorithm, worst-case anchor explanations for a point x is {Ar|d E R*} such that all anchor points lie a ray in the direction of point
Lemma 1. Given input x, a worst-case anchor for AlgLC, is of the form A. = (AxlA E R+} with precision parameter T 1
Proof- Consider that given x, DS returns label y and anchor explanation A= -Axr/ E R+} with 1.
5

---

Published in Transactions on Machine Learning Research (07/2024)
Algorithm 2 AlgLC, Auditing Linear Classifiers using Anchors
1: Input: T, augmentation size 5, set of warm-up labeled points set of queried points Q := 0, :W)
for 1, 1,,,3,..... + do
if f <=<- then
(- = (()
6:
Q (z.y)
7:
goto step 15
8: clse
Query point x² a from the DS
10:
Auditor receives label y and explanation Ag from the DS
11:
Q te",0 v)
}
12:
Sample randomly y points x² .4t from A ..... (x44, .))
Anchor Augmentation
13:
Q - QU ((xf),)) (U(((t
14:
end if
e(++1)+ = (1(tty), E(++)))) == estimate_ estimate_ellipooi(()
15:
N = update__ N(u((+)))
16:
17: ((+1)++ = update alpha(N'+1 (((1))+)
18: end for
19: = TT
20: if |ual S A (ith feature is the Fol) then
21: return No
22: else
23: return Yes
24: end if
Let the set of all classifiers consistent with the label be H {w y(u, a) 0}.
From the definition of anchors and 1, the label of all points in anchor Ar is also y. Then, the set of all classifiers consistent with A, is, H' = {w y(w, Xx) 0) {w Xy(w, x) > 0) H. Hence the set of consistent classifiers remains the same despite anchors. Therefore A, qualifies as worst-case anchor. r
The query complexity of our auditor using anchors AlgLC, is presented below.
Theorem 3.3. For every dimension d, there exists such that for any e (0, auditor AlgLC, an (c, -auddtoo for feature sensitivity and Hig with T O (d 2 queries.
This bound comparable to actively learning a linear classifier without explanations Old 4 Alabdul- mohsin et al. (2015); Balcan and Long (2013) and might discredit the utility of explanations. However, wo show the silver lining in 5..1 Proof and more details about the algorithm be found in Appendix $A.4
3.2 Decision Trees
Now we move beyond the lincar hypothesis class to non-lincar one docision trees and show how explana- tions can help in auditing them. A natural explanation for decision tree prediction is the path traversed in the tree from root to the predicted leaf Audemard et al. 2202];; Boer et al. (2020); Dasgupta et al. (2022) This explanation is consistent if the explanation path leads to the same prediction as that returned by the data scientist and the nodes with their values/range are consistent with the input features.
We propose an auditor AlgDT based on an explanation- based breadth- first tree search algorithm, it works as follows. If the feature-of-intersst is not present the explanation path, auditor randomly picks node in the path and perturbs its value while keeping the other features fixed such that can explore the other branch of the perturbed node. Incase after perturbation the point satisfies of the previous paths received as

---

Published in Transactions on Machine Learning Research (07/2024)
explanation, it randomly picks new query. Otherwise, the Ceature-of-interees is node in the explanation, and therefore is sensitive feature since it is used in the tree. AlgDT can be found in 3
Algorithm 3 AlgDT: Auditing Decision Trees using decision path explanations
Given Query Count threshold q7
Initialize Query count gcount O; set of received paths, P
Query any point from the DS
4: Auditor receives label and explanation path from the DS
5: PUP
6: gcounl == qeount +
foi node p then return Yes
end if
10: while True do
11: if gcount = ql' then
12: relurn No
13: end
14: = perturb(2. p) (In App. See A.5
15: while findpath(r,, P) {In App. Sec A.5
do
16:
Pick random query
17:
end while
18:
Query x from the DS
19:
Auditor receives label y' and explanation path p' from the DS
20:
P + PUp/
21:
gcount := gcount +
22: if foi is node in p' then
23:
return Yes
24:
end if
25:
end while
While we are not aware of an active learning algorithm that learns a decision tree with continuous features, Kushilevitz and Mansour (1991) propose non-explanation membership query algorithm for binary features that exactly learns the tree in time poly(2depth, d). Our auditor with explanations, which basically learns the entire tree in the worst-case, has linear worst-case complexity the order of number of nodes in the tree. Proof is in the App. Sec. A.5
Theorem 3.4. For any [0, auditor AlgDT is an (c,0)-auditor for feature sensitivity and hypothesis class Hor with T O(V) queries where V is the number of nodes in the decision tree.
4 Auditor through connections with Active Learning
In the previous section we designed specific auditors based on hypothesis class and explanation type. This naturally begs the question a general auditing strategy exists, we answer in the affirmative. We start by laking closer look at two critical steps strategy to pick the next query and the stopping condition - of our interactive auditing protocol mentioned in 2 and then propose a general recipe to create an auditor.
Table 1: Worst-Casc Query
Complexity of auditing feature sensitivity
Auditor
Query Complexity
Baseline
O #)
Picking next query The next query should be picked such that the auditor gets closer to the hidden h, thereby reducing its uncertainly in making a decision. To achieve this the auditor can maintain a search space over hypotheses boginning with Sn H and narrowing it through queries made to the DS each subsequent step until the stopping condition is reached.
AlgLC.
AlgLC,
Oddogg 20))
AlgDT
O(V)

---

Published in Transactions on Machine Learning Research (07/2024)
Let Z,-1 C = x y and E,-1 S X' x E be the set of labeled examples and explanations acquired from the DS till L t- 1. Search space at St, is the subset of hypotheses that are consistent with all the labels and explanations in Z and E respectively. As an example for counterfactual explanations, the hypothesis h is consistent if ((x,((x)) E Zi-1 and their counterfactuals (x, = cx(x)) E Ei-1, h(x) = h(x) and h(x') = M(d').
For efficient pruning of the search space; the auditor chooses a query point that reduces the measure of the search space the most, no matter what explanation and label are returned by the DS. Formally, 2, argmax.ex (mingxy |5:1/1s
argmaX value, where |St] and |S++|| denote the measure of the search spaces S; and S1+1 and value, corresponds to the reduction by worst case label and explanation for a point r. For finite hypothesis classes, the measure of the search space corresponds to the number of elements in it, while for infinite classes it is more complex; in $3.1.2 the search space is approximated by an ellipsoid at each time and measure is volume of the ellipsoid.
Stopping Condition decides query complexity of the auditor. For finite hypothesis classes, since h is always guaranteed to be in the search space at all times, if s(h) > c for all h in S then the auditor can safely conclude that h has the desired property and slop with a Yes decision. Similarly, s(h) S e for all h in S, the auditor will stop with a No. Observe that the auditor will ultimately arrive at one of these two cases if none of the two stopping conditions hold, the next query will cause the search space to shrink and ultimately our search space will consist of a single hypothesis.
For infinite hypothesis classes, we propose exploiting the structure of the hypothesis class and explanation methods to reduce the search space to a single hypothesis or to a set where value of the score function is same for each of its elements, in which case similar stopping conditions as the finite case can be used. Our proposed auditors for feature sensitivity lie in this setting.
Using the above query picking and stopping strategies, we formally outline an auditor for finite hypothesis classes presented in Alg | in the Appendix Sec.A.1 These strategies lead to an (c, aaudiio,, which follows directly from h belonging to the search space at all times and the stopping conditions as proved below.
Theorem 4.1. Algorithm 4 is an (c, -auddtorr for a finite hypothesis class H.
Proof. Firstly, note that h is in the search space S, at all times f. This is because the search space is reduced based on labels and explanations w.r.t. h (provided by the data scientist). Next, we assume that value of function can be computed to arbitrary precision for any hypothesis h. Then the proposed stopping conditions satisfy the soundness and completeness properties of the (e, d)audiioor from definition.
This general auditor is similar to the Optimal Deterministic Algorithm of Yan and Zhang 2022 in the sense that it is inspired from active learning. However, our general auditor has different stopping condition, also uses explanations and not manipulation-proo (although all of our auditors in $3 are manipulation-pren proof). Due to difference in stopping condition and the fact that our auditor returns a binary decision, auditor might be faster in reality. See Appendix AA.6 for details on Manipulation-prooffee
Connections to Active Learning. For readers who are acquainted with active learning, our auditor may appear familiar. In active learning Dasgupta (2005), the goal is to learn a classifier in an interactive manner by querying highly informative unlabeled data points for labels. A specific variant of active learning is Membership Query Active Learning (MQAL.) Angluin (1988); Feldman (2009) where the learner synthesizes queríes rather than sampling from the data distribution or selecting from & pool.
Our auditor is essentially an active partial-learning algorithm in the MQAL setting, with a modified oracle that returns explanations in addition to labels. Here, the DS is the oracle and the auditor is the learner. The algorithm does partial learning since it stops when the auditing goal is complete and before the classifier h is fully learnt.
We observe that learning a harder task than auditing - since the goal in learning is to find the classifier generating the labels, while in auditing we aim to decide if this classifier has certain property. This implics that if there exists an algorithm that can learn a classifier, it can also audit it as long as the score function
8

---

Published in Transactions on Machine Learning Research (07/2024)
can be computed/cstimatee, and membership query active learning algorithm can be used fallback auditing algorithm. This leads to the following fallback guarantee.
Theorem 4.2. If there erists membership query active learner that can learn h eractly in T queries, then the active learner can also audit in T queries.
Proof. Once h is known, s(h) returns the auditing decision. If s(h) = 0, the decision is No and if s(h) > 6, the decision Yes.
To summarize, while our auditor is connected to active learning, the key differences are 1) the goals as mentioned above, 2) usage of explanations and 3) unlike active learning, partial learning of the hypothesis can be sulficient for auditing. For example, if all hypotheses in the search space have zero score value, auditor can return decision without learning h exactly, or learning only some parameters of h may be enough to audit. Since partial learning can be sufficient for auditing, an auditing algorithm is not necessarily an active learning algorithm.
Distribution-Dependder Properties. For distributioonddeendder properties, the score function should also depend on the distribution and hence the auditor will have to estimate the score function using samples from this distribution (or another distribution which will lead to errors in the estimate based on how different the two distributions are).
The general idea to audit a distributtonn-deeeddee property such as demographic parity under our framework is to find the hidden classifier through active learning queries and estimate the score function for the learnt classifier by sampling from the said distribution. For finite hypothesis class, it can also use algorithm [ except that the score function for all existing hypotheses in the search space is to be estimated using samples from the said distribution. Note that while these algorithms are manipulation-proof unlike using random sampling for estimating the property noted in Yan and Zhang 2022).
5 Experiments
In this section we conduct experiments on standard datasets to test some aspects of feature sensitivity auditing. Specifically, we ask the following questions:
1. Does augmentation of 'typical' anchors reduce query complexity for lincar classifiers?
2. How many queries are needed on average to audit decision trees of various depths?
The datasets used in our experiments are Adult Income Becker and Kohavi (1996). CovertypeBlackard 1998) and Credit DefaulfYYh (2016). The features of interest are gender, wilderness area type and sex for Adult, Covertype and Credit datasets respectively. All the datasets have a mix of categorical and continuous features. Categorical features are processed such that each category corresponds to binary feature in itself. We remove all rows with missing values in any columns. We use an 80-20 split to create the train-test sets.
We learn both our linear and (ree classifiers using scikit-learn. To run the anchor experiments, we use the matlab code provided by [Alabdulmohsin et al. (2015). All of our experiments minute to 2-3 hours. Additional details about the experiments can be found in the appendix $A.7
CPU varying from a
5.1 Anchor Augmentation of Typical Anchors
As discussed in 43.1.2, augmentation of worst-case anchors does not help in reducing the query complexity of auditing. In other words, augmenting worst-case anchors is equivalent to not using anchor explanations. A natural question then is do typical anchors help? Since auditing with anchors using AlgLC, means learning the DS's model under the hood, reduction in query complexity of learning implies reduction in that of auditing. Hence, we check experimentally if faster learning is achieved through anchor augmentation of typical anchor points.
Methodology We learn a linear classifier with weights for each dataset ; these correspond to the DS's model. All of these models have non-zero weight for the feature of interest; later we manually set the
9

---

Published in Transactions on Machine Learning Research (07 (224))
weight corresponding to the Fol to zero to conduct experiments for the case when the Fol is not used for anditing. Then the weights are estimated during auditing using Algorithm 2 We consider two different augmentations 1) worst-case anchor points which is equivalent to not using anchors 2) typical anchor points. We set the augmentation size (number of anchor points augmented) to a maximum of 30. Our anchors are hyperreclangles of a fixed volume surrounding the query point. We sample points with the same label as the query point from this hyperroctangle and augment to the set of queries in the typical case.
Results The results for the non-zero Fol case shown in Figure We see that the anchor augmentation of typical anchors drastically reduces the query complexity to achieve the same estimation error between weights as compared to not using anchors (or equivalently using worst-case anchors). This saving directly translates to efficiency in auditing. For example, in the adults dataset, less than 50% of the queries are needed to achieve a lower error with typical anchors than without them. This illustrates that anchor explanations can be helpful for auditing, suggesting an application for these explanations. Note that the error in Figure [] is not zero and could be due to the cllipsoidal approximation. When the Fol has a weight of zero, we observe that typical anchors reach stable near-zero estimate for the Fol weight sooner than worst-case anchors, shown in Figure 2
incomo
CoverType
Defaut
Dror ketweon and eeruane
bptiall
22.4
Yppcill
Sppca
30-
22.0
Dre Acteoon
Drea
qanres
Figure 1: Number of queries required to learn a linear classifier with anchor augmentation of worst-case anchor points (in blue) and typical anchor points (in orange). For the latter, a clear reduction in query complexity is observed. The Fol has a non-zero weight in all of these.
Credit
5 6.255
Warth :300
Bure cate
0.175
Ment -i4a Tpliial
8300-
Typil
Spical
8275
a159
6.25
8350-
8125
01:00
a375
0355
00000
0325
6025
0303
6.000
25
100
225
175
30
300
152
375
200
25
75
120
125
350
375
207
Quedis
Quavice
Qual
Figure 2: Number of queries required to learn a linear classifier when the Fol has a zero weight, with anchor augmentation of worst-casc anchor points (in blue) and typical anchor points (in orange). The latter reaches a stable near-zero weight for the Fol sooner, demonstrating a reduction in query complexity.
5.2 Average Queries for Decision Tree Auditing
In $3.2 we discussed that the worst-case query complexity of auditing is on the order of number of nodes in the decision tree. However on average the auditor might ask way lesser queries than the worst-case bound. We check experimentally if this is the case.
Methodology We learn decision trees for each of the datascts using seikit-learn which implements CART Breiman (2017) to construct the tree. All of these use the Fol to make predictions. We vary tree depth by fixing the "max-depth' hyperparameter. Then we freeze the tree and run AlgDT 1000 times. We report
10

---

Published in Transactions on Machine Learning Research (07/2024)
average of the total queries required to audit across the 1000 runs. We also random testing bascline from $ until we detect the sensitive feature. We do this a 1000 times and report the average number of queries over those runs.
Results Our results are displayed in Table As can be seen, the average number queries needed to audit consistently way lesser than the number of nodes, which highlights the utility of explanations in the average-case. There complex relationship between the total number of nodes in the tree and the number of feature-of-interes nodes in the tree which jointly determines the number of queries.
As the depth of the tree increases, the number of nodes increase exponentially while the feature-of-interre nodes and therefore average queries increase at a much slower pace. The Cov'Type dataset has the lowest query complexity which might be a result of the feature-of-interes having four categories rather than two (aaleffemale) in other datasets. There is a huge disparity between the average number of queries our auditor needs (low) and the average random testing queries (high). This demonstrates the efficacy of our anditor over the baseline.
Table 2: Decision Tree Auditing: Avg. number of queries required to audit over 1000 runs of AlgDT across different depths of decision trees. Avg. queries are rounded to the nearest integer and reported with 95% confidence intervals. #Ag.. queries are consistently lower than # #Nodes and #Random Testing Queries.
Dataset
Depth
Test Acc.
#Avg. Queries
#Nodes
#Fol Nodes
#Random Testing Queries
Adult
9
85.09
11 + 0.48
188
3
248 = 15.4
12
85.36
9 + 0.4
552
18
299 + 18.65
15
84.59
10 + 0.41
1158
31
160 = 9.8
Cov'Type
7
77.92
2 0.10
119
9
17 + 1.03
9
80.06
2 0.07
383
14
13 = 0.77
12
83.80
2 0.08
1625
34
+ 0.67
15
87.40
+ 0.08
4196
57
0.5
Credit
9
81.07
17 0.63
234
176 10.71
12
80.58
36 + 1.2
629
6
276 17.59
15
81.65
54 + 1.87
1030
20
905 = 54.31
To summarize, observe that worst-casc estimates generally very pessimistic and project explanations in bad light. In the average case, which happens lot average, explanations bring down the number of queries for anditing significantly.
6 Discussion
Untruthful Data Scientist natural question to ask is what happens when a DS is not entirely truthful in the auditing process, assumed in S What kind of auditing is possible in this casc?
Suppose the DS returns all labels and explanations from an entirely different model than h. In this case, there is no way for an auditor to detect it; but perhaps this can be dealt with in a procedural manner like the DS hands its model to a trusted third party who answers the auditor's queries.
What if the DS returns the correct labels but incorrect explanations? DS might be forced to return cor- roct labels when the auditor has some labclod samples already and hence can catch the DS lies with labels. This scenario motivates verification of explanations. Next, discuss schemes to verify anchors and counterfactuals for this scenario.
For anchors, verification is possible if we have samples from the underlying distribution D. For query x, DS relurns an unverified anchor A₂ with precision тN and coverage cz. The correctness of tx can detected as follows. First, get an estimate for the true value the precision parameter by sampling n points from anchor A₃ according to D. Let the true and estimated values of precision parameter be and respectively. approaches with sufficiently large number of points as mentioned in lemma 2 Second, compare Ty with f. A large difference between T, and implies false anchors.
Anchors.
11

---

Published in Transactions on Machine Learning Research (07/2024)
Lemma 2. For any A and integer n, Pr([T f| A) I exx 2A3n
Lemma 2 is immediate from Hoeffding's Inequality. Notice that the number of samples required to verify precision changes with 1/a². If the fraction of responsive pairs e equals A, our baseline in section 3 can audit with O(/a)) samples without using explanations. Hence, in adversarial conditions where the probability of a lying DS is high, it is better to andit with our explanations-froo bascline than auditing with anchors and verifying them.
Since coverage is the probability that a point sampled from D belongs to Ag, it can be easily checked 1) by calculating the volume of A₂ when all dimensions of are bounded or 2) by sampling points from D when the features are unbounded.
Counterfactuals. Given æ, let x' be the unverified counterfactual explanation returned by the DS. There are two aspocts to a counterfactual explanation - its label which should be different from x and it should be the closest such point to x.
The first aspect can be easily verified by querying x' from the DS. For the second aspect, we observe that finding the counterfactual is equivalent to finding the closest adversarial point. Deriving from adversarial robustness literature, verifying the closeness aspect can be computationally hard problem for some hypoth- esis classes like discussed in Weng et al. (2018). However, we propose a sampling based algorithm to estimate the true counterfactual, assuming that the DS is lying. Firstly, sample points from the ball Bax, d(æ z²)). For x' to be the true counterfactual, all points within the ball B(x, d(z,z')) should have the same label as x. If a point x" with a different label is sampled, select this point as an estimate the true counterfactual and repcat the scheme with the new ball B(x, d(x,, x")). By following this procedure iteratively, we get closer the correct counterfactual explanation as the radius of the ball reduces at each iteration. There are cases where our algorithm may not work well. We leave designing better algorithms for verifying closeness to future work.
Upon verification, if auditor finds that the DS is untruthful, it can choose to 1) stop auditing and declare that the DS is lying, 2) audit with estimated explanations or 3) audit with explanations free baseline algorithm 3 since option 2 is computationally intensive.
Privacy Auditing also raises legitimate privacy concern. On one hand, model hidden from the auditor for confidentiality reasons while on the other hand, to be able to give correct auditing decision efficiently, the auditor has to extract/learn the hidden model, albeit partially. This concern can be resolved by using crytographic tools like Zero-Knowlede proofs Yadav et al. (2024): Singh et al. (2021); Liu et al. (2021. A future direction of our work is modifying our framework to work with cryplographic tools.
7 Related Work
Auditing has been used to uncover undesirable behavior in ML models in the past [Buolamwini and Gebru (2018); Koenecke et al. (020)) Tatman and Kasten 2017 Tatman 2017). However, these works were based on creating a audit dataset in an ad-hoc manner. Recently, there have been efforts towards streamlining and developing a structured process for auditing. For instance, Gebru et al. (2018); Mitchell et al. (2019) introduce datasheets for datasets and model cards and Raji al. (2020) introduce an end-to-end internal auditing process. In contrast with these works, we theoretically formalize auditing with explanations which allows us to determine what kind of propertics can be audited and with how many queries.
Auditing with Formal Guarantees The work most related to ours is concurrent work due to Yan and Zhang (2022), who present a formal framework as well as algorithms for auditing fairness in ML models by checking if a model has a certain demographic parity on a data distribution. Their algorithms are motivated by connections to active learning as well as machine teaching Goldman and Kearns (1995). In contrast, we look at auditing with explanations. Our instantiation auditing feature sensitivity is different from demographic parity, which, together with the use of explanations, leads to very different algorithms.
12

---

Published in Transactions on Machine Learning Research (07/2024)
Another work auditing with guarantees is Goldwasser et al. (021], who audit the accuracy of ML models. They use an interactive protocol between the verifier and the prover like our work, and their algorithm is related to a notion of property testing due to [Blccan et al. (2011). The auditing task used in our paper, feature sensitivity, is different from accuracy used in their paper. We also utilize explanations.
Auditing and Explanations Explanations are supposed to help in auditing as suggested in Bhatt et al.
; Poland (2022); Hamelers (2021); Carvalho et al. (0019), but exactly how and under what conditions was not understood. In a concurrent work by Mougan et al. (2023), authors show that explanations lead to
(2020g; Oala et al. (2020); Adebayo and Gorelick (2017); Watson and Floridi (2021); Zhang et al. (2022):
more sensitive audits than using labels and demonstrate the case for demographic parity using shapley values Lundberg et al. (2019 2020). On the other hand, our focus is to demonstrate how explanations can reduce the query complexity of auditing and formalizing the auditing process by connecting it to active learning. The notion of feature sensitivity and the kind of explanations used in our paper are also different from theirs.
Other Auditing Mcthods Specific statistical methods have been proposod by Jagiclski et al. (2020) Yo et al. p2021p to audit privacy and by Liu and Tsaftaris (2020); Huang et al. (2021) audit data deletion. These are properties of the learning algorithm rather than the model. In our paper we focus the latter and hence our algorithms are not applicable to auditing privacy and data deletion. Extending our framework to broader settings is an important direction of future work.
8 Conclusions and Future Work
We formalize the role of explanations in auditing with special focus on 'feature sensitivity' and find that their theoretical efficacy in reducing query complexity vastly varies across different methods. Structure of the hypothesis class and explanation method together determine this efficacy. While worst-case query complexities for auditing 'feature sensitivity' are pessimistic, our experiments herald optimism - in the average-case we see a significant reduction the number of queries required to audit across all explanation types. We also connect auditing to the well-established field of active learning and provide general active- learning inspired algorithms for auditing with explanations.
We believe that this work is first step towards understanding certified auditing and auditing with expla- nations. A major rescarch direction is auditing with approximate or incorrect explanations. Other future directions include incorporating other kinds of explanations, investigating different hypothesis classes, au- diting properties and theorising the average-case complexity with explanations.
Ethics Statement. This work uses feature sensitivity more broadly than fairness (as described in 33aand only to demonstrate an instantiation of our framework. We agree that feature sensitivity, though linked to fairness, is not 'the' perfect measure of fairness and we doubt if such a metric can exist.
We believe that auditing a complex process. Auditing can only be done for vulnerabilities that we know can exist and hence unknown vulnerabilitics might still cxist in a model despite being audited. There are real-life scenarios like limited budget (financial, time) which might prevent an auditor from uncovering vulnerabilites, even though they exist. Our work is step in understanding the auditing process better.
Acknowledgements. This work was supported by NSF under CNS 1804829 and ARO MURI W911NF2110317. MM has received funding from the European Research Council (ERC) under the Eu- ropean Union's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grant number 993/17), Tel Aviv University Center for AI and Data Science (TAD), and the Yandex Initiative for Machine Learning Tel Aviv University. CY thanks Geelon So for providing valuable feedback on an early draft of the paper.
13

---

Published in Transactions on Machine Learning Research (07 (024))
References
Julius Adebayo and Micha Gorelick. Fairml: Auditing black-box predictive models. Blog. Fastforwardllabs. Com, 2017.
Gulimila Aini et al. A summary of the research the judicial application of artificial intelligence. Chinese Studies, 9001):14, 2020.
Tbrahim Alabdulmohsin, Xin Gao, and Xiangliang Zhang. Efficient active learning of halfspaces via query synthesis. In Twenty-Ninth AAAI Conference Artificial Intelligence, 2015.
Dana Angluin. Queries and concept learning. Machine learning, 2(4):319 342, 1988.
Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Jean-Marie Lagniez, and Pierre Marquis. On the explanatory power decision trees. ar preprint arXiv:2108. 05266, 2021.
Maria-Florina Balcan and Phil Long. Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory, pages 288-316. PMLR, 2013.
Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang. Active property testing. ar preprint arXiv:1111.0897, 2011.
Barry Becker and Ronny Kohavi. 10. 221224422//5//2
Adult. UCI
Machine Learning Repository, 1996.
DOL
https://doi.onr wtt//..////////.
Umang Bhatt, Alice Xiang, Shubham Sharma, Adrian Weller, Ankur Taly, Yunhan Jia, Joydoep Ghosh, Ruchir Puri, José MF Moura, and Peter Eckersley. Explainable machine learning in deployment. In
Proceedings of the 2020 conference on fairness, accountability, and transparency, pages 2020.
Jock Blackard.
Covertype. C50K5N.
UCI
Machine
Learning Repository, 1998.
DOI:
hutps://oi..org/ http://oi..or/00..44.... 211....22///0 24.44433/C50.
Naama Boer, Daniel Deutch, Nave Frost, and Tova Milo. Personal insights for altering decisions of tree-based ensembles over time. Proceedings of the VLDB Endoument, 13(6):798 811, 2020.
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al. End to end learning for self-driving cars. arXiv preprint Xrx:w:1604 604.008646 2016.
Leo Breiman. Classificntion and regression trees. Routledge, 2017.
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Conference on fairness, accountability and transparency, pages 77-91. PMLR, 2018
Diogo V Carvalho, Eduardo M Pereira, and Jaime S Cardoso. Machine learning interpretability: A survey on methods and motrics. Electronics, 8(8):832, 2019.
Isabella Castiglioni, Leonardo Rundo, Marina Codari, Giovanni Di Teo, Christian Salvatore, Matteo Inter- lenghi, Francesca Gallivanone, Andrea Cozzi, Natascha Claudia D' D'Amioo, and Francesco Sardanelli. Ai applications to medical images: From machine learning to deep learning. Physica Medica, 83:9-24, 2021.
Sanjoy Dasgupta. Coarse sample complexity bounds for active learning. Advances in neural information processing systems, 18, 2005.
Sanjoy Dasgupta, Nave Frost, and Michal Moshkovitz. Framework for evaluating faithfulness of local expla- nations. arXiv preprint arXin:2202. 00734,, 2022.
Daniel Deutch and Nave Frost. Constraints- based explanations of classifications. In 2019 IEEE 35th Inter- national Conference on Dato Engineering (ICDE), pages 541-541. IEEE, 2019.
Vitaly Feldman. On the power of membership queries in agnostic learning. The Journal of Machine Learning Research, 10:163-188 182282 2009.
14

---

Published in Transactions on Machine Learning Research (07/2024)
Timnit Gebru, Jamie Morgenstern, Briana Vecchione, Jennifer Wortman Vanghan, Hanna Wallach, Hal Daumé ITI, and Kate Crawford. Datasheets for datasets. Xiv preprint or Xrx: 803.09010, 2018.
Sally A Goldman and Michael J Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 5001),, 1995.
Shafi Goldwasser, Guy N Rothblum, Jonathan Shafer, and Amir Yehudayoff. Interactive proofs for verifying machine learning. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuh--cciniizZZztrrn für Informatik, 2021.
LH Hamelers. Detecting and explaining potential financial fraud cases in invoice data with machine learning. Master's thesis, University of Twente, 2021.
Yangsibo Huang, Xiaoxiao Li, and Kai Li. Ema: Auditing data removal from trained models. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 793-803. Springer, 2021.
Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information Processing Systems, 14-22205-22211 2020.
Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnostic counterfactual expla- nations for consequential decisions. In International Conference on Artificial Intelligence and Statistics, pages 895-905. PMLR, 2020.
Allison Koenecke, Andrew Nam, Emily Lake, Joe Nudell, Minnie Quartey, Zion Mengesha, Connor Toups, John R Rickford, Dan Jurafsky, and Sharad Goel. Racial disparities in automated speech recognition. Proceedings of the National Academy of Sciences, 117(14):6684-768) 2020.
Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 455-464, 1991.
Thibault Laugel, Marie-Jeanne Lesot, Christophe Marsala, Xavier Renard, and Marcin Detyniecki. Inverse classification for comparison- based interpretability in machine learning. arXiv preprint orXiv:1712.08443, 2017.
Tianyi Liu, Xiang Xie, and Yupeng Zhang. Zkenn: Zero knowledge proofs for convolutional neural net- work predictions and accuracy. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Commanications Security, pages 2985, 2021.
Xiao Liu and Sotirios A Tsaftaris. Have you forgotten? method to assess if machine learning models have forgotten data. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 95-105, Springer, 2020.
Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lec. Explainable ai for trees: From local explanations to global understanding. Xix preprint Xiv: 1905.9901111 2019.
Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lec. From local explanations to global understanding with explainable for trees. Nature machine intelligence, 2(1):56 67, 2020.
Margaret Mitchell, Simone Wu, Andrew Zaldivar, Parker Barnes, Lucy Vasserman, Ben Hutchinson, Elena Spitzer, Inioluwa Deborah Raji, and Timnit Gebru. Model cards for model reporting. In Proceedings of the conference on fuirness, accountability, and transparency, pages 220 229, 2019.
Carlos Mougan, Laura State, Antonio Ferrara, Salvatore Ruggieri, and Steffen Staab. Demographic parity inspector: Fairness audits via the explanation space. ar Xio preprint Nii:2303.088400 2023.
15

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Luis Oala, Jana Fehr, Luca Gilli, Pradeep Balachandran, Alixandro Werneck Leite, Saul Calderon-Ramirez, Danny Xie Li, Gabriel Nobis, Erick Alejandro Muñoz Alvarado, Giovanna Jaramillo-Gutierer et al. Ml4h auditing: From paper to practice. In Machine learning for health, pages 280 -17. PMLR, 2020.
Cherie M Poland. The right tool for the job: Open-source auditing tools in machine learning. arXiv preprint arXiv:2206. 10613, 2022.
Inioluwa Deborah Raji, Andrew Smart, Rebecca N White, Margaret Mitchell, Timnit Gebru, Ben Hutchin- son, Jamila Smith-Loud, Daniel Theron, and Parker Barnes. Closing the ai accountability gap: Defining an end-to-end framework for internal algorithmic auditing. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pages 33-44, 2020.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors:
model-agnostic explana- tions. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Nitin Singh, Pankaj Dayama, and Vinayaka Pandit. Zero knowledge proofs towards verifiable decentralized ai pipelines. Oryptology ePrint Archive, 2021.
Ioana Baldini Soares, Chhavi Yadav, Payel Das, and Kush Varshney. Keeping up with the language models: Robust interplay in uli data and models. In Annuual Meeting of the Associalion for Compulational Linguistics, 2023.
Rachael Tatman. Gender and dialect bias in youtube's automatic captions. In Proceedings of the First ACL Workshop on Ethics in Natural Language Processing, pages 53-59, 2017.
Rachael Tatman and Conner Kasten. Effects of talker dialect, gender & race on accuracy bing speech and youtube automatic captions. In Interspeech, pages 934 938, 2017.
David S Watson and Luciano Floridi. The explanation game: a formal framework for interpretable machine learning. In Ethics, Governance, and Policies in Artificial Intelligence, pages 185 219. Springer, 2021.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference PMLR, 2018.
on Machine Learning, pages
Chhavi Yadav, Amrita Roy Chowdhury, Dan Boneh, and Kamalika Chaudhuri. Fairproof: Confidential and certifiable fairness for neural networks. arXiv preprint ar Xiv:24402. 12572, 2024.
Tom Yan and Chicheng Zhang. Active fairness auditing. Tn International Conference on Machine Learning, pages 24929 24962. PMLR, 2022.
Jiayuan Ye, Aadyaa Maddi, Sasi Kumar Murakonda, and Reza Shokri. Privacy auditing of machine learning using membership inference attacks. ", 2021.
I-Cheng Yeh. default of credit card clients. UCI Machine https://doi.org/// 11t.:/1..2.0 200.24433//555330
Learning Repository, 2016. DOL:
Chanyuan Abigail Zhang, Soohyun Cho, and Miklos Vasarhelyi. Explainable artificial intelligence (xai) in auditing. International Journal of Accounting Information Systems, page 100572, 2022.
16

---

Published in Transactions on Machine Learning Research (07 (07/2024)
A Appendix
A.1 A General Auditor for finite hypothesis classes
A Algorithm A General Auditor for finite hypothesis classes
1: So : H where [H] is finite; stop flag = False; t: 1; 6: === eps
2: while 1stop flag do
3: Iz : picking next query(St-1)
4: Auditor receives label y/ and explanation et from the DS
S++1 update_scaat scarch Search_sspaceS____ Ft, Ft, eq)
Y_a, stop flag check stopping condition(S.) end while
return Y_a
Algorithm 5 check brreckkstoppinng. wttppssog_oooddiiititoooooo condition()
1: Input: S,
vh St, s(h) > eps then decision Yes, stop flag True
else if vh s(h) S eps then decision = No, stop flag True
6:
else
7:
decision = None, stop flag False
8: end
return decision, !stop flag
Algorithm picking next query()
1: Input: S;
2: for x E X' do
for (e, E & x y do
S = updato_ search Saarch_spaco(S,222 y, E) end for value, mingxy //11/14411
7: end for
8: return argmax valuez
Algorithm 7 update search space()
Input: S, H. J, e
Snew = {h- 811(x) y, check consistent expllanation(2,e t/ //Explanation method depen-
dent consistency check)
return Snew
A.2 Auditing Linear Classifiers with Counterfactual Explanations
In this section, we will prove that auditing lincar classifiers using counterfactual explanations requires only one query. We denote our auditor by AlgLC,, as outlined in Alg. [ The proof goes by noting that the counterfactual explanation z' returned by the DS is very close to the projection of input x and that x is parallel to w. We consider the d-th feature to be our feature of interest without loss of generality.
Lemma 3. Given hyperplane w" x + = O, point x and its projection on the hyperplane x" x - x" Aw
where X T4bb
17

---

Published in Transactions on Machine Learning Research (07/2024)
Algorithm 8 AlgLC, Auditing Linear Classifiers using Counterlactuals
1: Query any point a from the DS Auditor receives label y and explanation x' from the DS x² if dē 0 (ith feature is the Fol) then
return No
6: else
7: return Yes
end
The projection, x", of x the hyperplane w² x 0, is found by solving the following optimization problem.
Proof.
min ||"" - x1| S.L.
(1)
w w²x" + =0 0
Let L(x",\) A) be the lagrangian for the above optimization problem.
L(x", A) = ||=" z1|² + 2>(w" x" b) =||="|² ||0||2 TTTx=" + 2Aw Tx" 2Ab
(2)
||~"|| ||=|| - 2(x Aw) Tx" 2Ab
Taking derivative of the lagrangian with respect to x" and equating with zero we get,
aL Or" = 2x" 2(x -xw)
(3)
x" Aw
By substituting above equation in the constraint for the optimization problem wTx" + 0, we get z
Theorem 3.2. For any e E [0, 1], auditor AlgLC, is an (c,0)-auditor for feature sensitivity and hypothesis class HLC with = query.
Proof. Recall that the counterfactual explanation returned by the DS input x given as x' argmiingrste"")/Maa) d(x,,') where d(x, x') = || - x'll2-
The projection of the hyperplane, x² is the closest point to the hyperplane. Therefore x' x" + +A where A is vector in the direction of w, yw,, y is very small non-zero constant.
Therefore, I x' = x (x" + A) (x z²) + A.
Using lemma 3
i = x = Aw + 7 = CoW,
(4)
where Co is non-zero constant. (z - x is non-zero due to the definition of counterfactuals, specifically that they have different labels.)
If wa = 0, then it implies that vi = 0 and the feature has no effect on the prediction. Thus the score function zero. Since AlgLC, returns a No when 4i, = 0, it is always correct in this case. For all the other cases when wa # O, implies that v, # and therefore, the feature has an effect on the prediction. Since AlgLC, returns Yes when uid # 0, is always correct.
Also 8 0 since auditor and DS are deterministie.
18

---

Published in Transactions on Machine Learning Research (07/2024)
Note that this is partial learning since 1) do not need to learn exactly and 2) do not need to learn the bias term b.
A.3 Connection between Model Parameters and Score Function
Notation For vector v, the 7th feature is denoted
Let hypothesis bw.b E HLc. When w, b are clear from the context, we simply write h. Let w' be the Hence w is a concatenation w' and wa, denoted by the shorthand w = [w', wa]- We assume that / ||2 =.
(d 1)-dimensional vector wot...-a-1]"
Let be a d-dimensional imput this hypothesis. Let x' be the (d - 1)-dimensional vector [a] ... xd-1l" Let F [21 ................................ -0-11 1]". Without loss of generality, let the gt feature be the feature of interest and E {0,
The score function for hypothesis h is given as, s(h) = Pr ((z', x²) forms a responsive pair) where (x),x)) is sampled uniformly from the set of all pairs and labeled by h. Henceforth we use this score function.
In the following theorem, we bound the fraction of responsive pairs, also our score function, using the weight of our feature of interest, wa- The score function is bounded by e |wal where depends on the dimension of the input. This implies that if [wal is small, there not a lot of responsive pairs (low score function value).
Theorem 1. Assume Vx X, ||ā||2 S 1. Let hew wall walbb
HLo. Then
s(h) C. (wal
where C= ( ((2
2
is a consland for fovite dimension and T is Fuler's Gamma function.
Proof. Let P be the set pairs of points. Let xf and xt denote two inputs forming a pair. Let the pair x") drawn uniformly from P form a responsive pair.
From the definition of pair, xf and x only differ in the th feature. Hence,
w J + b= wd Sي + b + wark
= =w + b we (1 x²d) = TT. rt + b wid - wazz.
(6)
Without loss of generality, let z/ hence z/ 1. Therefore,
w T + wT ai + b wd
(7)
Next, writing the definition of a responsive pair for HLc we get,
sign (w xf b) * sign (w Two + b)
(8)
Substituting eq. 7 into the RHS of eq. get,
sign (w I' + b) + sign (w'T"" T + b + -aa)
(9)
Expanding the LHS of eq. and substituting 2² = 0, we get,
sign TT T2 + b) + sign (w x + b wa) 12
(10)
Eq. TO
implies the following,
19

---

Published in Transactions on Machine Learning Research (07 (2742)
w x² bb w/ +b wa
(11)
w T x" + b = T + b wa 2 0
Combining the two equations eq. 11
we get,
0 S w TT x² + b < Wid
(12)
0 w I + b) w
Note that the model (defined by w.bb) b) is fixed. Hence the variables in the above conditions are the inputs x. Note that only one of the conditions in eq. 12 can be satisfied at any time, based on whether wa 2 0 or wa < The fraction of the inputs which satisty one of the above conditions correspond to the fraction of responsive pairs and hence the value of the score function.
Conditions in eq. 12 correspond to intersecting halfspaces formed by parallel hyperplanes. If | S the region of intersection can be upper bounded by hypercuboid of length 2r in d - 2 dimensions and perpendicular length between the two hyperplanes (= = [waL in the (d- 1)-th dimension.
w lla
Hence, we can upper bound score function s(h) as,
(2r)a-2.1
shh S Va-1(r)
(13)
where / - wyl and (r) is the volume of the (d - 1)-dimensional ball given by Euler's Gamma function.
z(d 11/2
r d-1 and r is
[(-2+1)
Upon simplification we get,
2d-2
s(h) <
(14)
rI's d+1
Assuning r = and ||w'|l 1, we can write eq.
14 88;
s(h) S C |wal
(15)
where C = ( r (r(a)))
is a constant for small dimensions.
A.4 Auditing Linear Classifiers with Anchor Explanations
Imperfect Precision. When the prccision is not perfect, the anchor augmentation scheme (lines 11-13 in Alg. [ is not as straightforward. Essentially we cannot assign the same label to all randomly sampled points in the hyperrectangle. To overcome this problem we can use some heuristics and tricks. (a) Note that we wish to exploit the information given by anchors to automatically label samples, but due to imperfect precision there will be errors in this labeling if we use our old augmentation scheme this is analogous to active learning with noisy labels and we can explore existing literature in this field to deal with this problem. (b) We can internally consider a smaller hyperrectangle than that supplicd by the data scientist and only sample from that this can reduce the error arising from potential wrong labeling (c) We can also ask for labels for some points within each anchor this might help due to the structure of linear classifiers (only points closer to the decision boundary can have imperfect precision) and the fact that the problem only arises when the precision is somewhere in between 0 and 1, it does not arise at the ends or closer to 0 or 1. Imperfect precision can potentially increase the number of queries or the computations required for anchor augmentation.
Alabdulmohsin et al. (0155) proposed a query synthesis spectral algorithm learn homogeneous linear classifiers in Old x) steps where A corresponds to bound the error between estimated and true
20

---

Published in Transactions on Machine Learning Research (07/2024)
classifier. They maintain version space of consistent hypotheses approximated using the largest ellipsoid e* (n²; E*) where μ² is the center and E' is the covariance matrix of the ellipsoid. They prove that the optimal query which halves the version space is orthogonal to fe' and maximizes the projection in the direction of the eigenvectors of Ex
We propose an auditor AlgLC, as depicted in alg. 2 using their algorithm. The anchor explanations are incorporated through anchor augmentation. But, in the worst-case anchors not helpful and hence the algorithm reduces essentially to that of Alabdulmohsin al. 2015 (without anchors). In this section we find the query complexity of this auditor.
Notation In AlgLC,: ex* = (n²*, E') denotes the largest ellipsoid that approximates the version space (corresponds to search space our case) at time where p** is the center and E the covariance matrix of the ellipsoid at time N is the orthonormal basis of the orthogonal complement. of n²* and N is its transpose. ax* is the top eigenvector of the matrix N y N In the implementation by Alabdulmohsin et al. 2015). some warm-up labeled points are supplied by the user, denote this set W. Let W(t) denote the t-th element of this set. Let the t feature be the feature of interest without loss of generality.
Algorithm AlgLC, Auditing Linear Classifiers using Anchors
1: Input: T, augmentation size set of warm-up labeled points W 2: set of queried points Q == 0, I :W))
for t= 1,2,3,..... T do
if <f<<=> then
(I, (tt)
Q (z.
7:
goto step 15
8: else
9:
Query point x' == a from the DS
10:
Auditor receives label y and explanation Ag from the DS
11:
Q QU (='.y) v)
12:
Sample randomly y points x41 .41....4 from A
}
Anchor Augmentation
13:
Q - QU (Qtt( ..... v))
14:
end if
c(++))+ = (1(++))+ I(++)**) eedimate__llipsoide
15:
N update ((((++))))
16:
17: (1+1)+ = update alpha(N(+1, ((++1)+
18: ///E 1//Exact formulae for steps 15 16 and
17
can be found in Alabdulmobsin et al [2015]
19: and for
20: = ----1
21: if | S (ith feature is the Fol) then
22: return No
23: else
24: return Yes
25: end if
Next give bound on the number of queries required to audit using AlgLC,- With worst-case anchors, it means that just using the algorithm of Alabdulmohsin al. (2015), essentially without explanations and anchor augmentation. The auditor has fixed that it decides beforehand. AlgLC, decides how many times it must run the algorithm of Alabdulmohsin et al. (2015) such that for the fixed it satisfies def. 2
Theorem 3.3. For every dimension d, there exists > such that for any e (0,1), auditor AlgLC, an (e,, -auddiorr for fenture sensilivity and Hig with T O (d 26) queries.
21

---

Published in Transactions on Machine Learning Research (07/2024)
Proof. Let w be the true classifier and i be the estimated classifier learnt by AlgLC, Let the difference between w and v be bounded by A as follows,
|/e 101 A.
(16)
The value of A will be set later on. Since AlgLC, uses | to make its decision, the worst case is when the entire error in estimation is on the tth dimension. Hence, we consider I w. < A.
To guarantee that the auditor an (c, 0)-anditor we need to verify for every hypothesis in the class that if s() = 0, then the answer is No and if s(-) > 6, then the answer is Yes, see def. 2
Importantly, s(w) is zero only if wa from theorem If wa + | $ A, by eq. 16 Since AlgIC, returns No for mall= I A, AlgLC, satisfies def. 2 when s(w) with 8 0.
Next, have the case s(w) > when auditor should return Yes with high probability. AlgLC, returns Yes when [&al > A. Hence for AlgLC, to be correct, we need that s(w) > imply that (aa > A.
We can upper bound s(w) using eq. as,
s(w) S C- |wal
(17)
Since e < s(w),
6 < C. |wal
(18)
Since [wd- - uil S A,
5 C (l0al + A)
(19)
On rearranging,
A [Da
(20)
Eq. 20 connects with A and w.. For s(w) > e, |Wall should be greater than A for AlgLC, to be correct.
Hence, lower bounding the LHS of eq. 20 we get,
A
A
(21)
<
2C
We set 20
From Lemma 1. AlgLC, reduces to Alabdulmohsin et al. 20055 's spectral algorithm in the worst-case. This algorithm has a bound of Od )). Hence, the query complexity of AlgLC, is Od (2))
7
22

---

Published in Transactions on Machine Learning Research (07 (07/202)) /204)
A.5 Auditing Decision Trees
Algorithm 10 findpath(x, P)
Given Query and explanation paths set P
for path pe E P do
not p := False
4: for (fr. 04, dir;) E do
5: if (dir; = & fG. > u;)l == & 3s < vi) then
6:
not p = True
7: golo line 3
end if
end for
10: if not p -= False then
11: return True [Query satisfies pre-existing path]
12: end if
13: end for
14: return False
Algorithm 11 perturb(z,p)
1: Given Query x and corresponding explanation path = [[ v; dir = ( 2]]] (Two directions of incquality are used for case illustration. The code generalizable to include other conditions casily.) }
Randomly pick tuple (ʃ, n, d) from p
if dir = then Perturb xy such that z
5: else
6:
Perturb xy such that xy <
7: end if
8: x = May Uz
return x
Theorem A.1. For any e E [0, 1], auditor AlgDT is an (e,0)-auditor for feature sensitivity and hypothesis class HDT with = O(V) queries where V is the number of nodes in the decision tree.
Proof. Let L be the number of leaves and V be the number of nodes in the decision tree. The total number of queries asked by 3 equals the number of paths in the tree. The number of paths in binary decision tree equals the number of leaves and = (V + 1)/2. Once the auditor makes V queries, it has explored all the paths in the tree and hence knows the tree exactly. Therefore with O(V) queries, can give the correct auditing docision preciscly.
A.6 Sncppullttio-PProffee
Yan and Zhang 2022
define canipuulation-prooneee and unlabeled dataset S, define the version space induced by S to be S), == {h' E V h'(S) h(S)). An auditing algorithm is c-manipulation-prod if, for any h², it outputs set of queries S and estimate & that guarantees that max [s(h) 8l S
follows. Given set of classifiers V, classifier h.
Our anchor and decision tree auditors are manipulation-prod trivially since the version space size at the end of auditing 1. Our counterfactual auditor is manipulation-proof since only those classifiers which have w; will be in the version space.
23

---

Published in Transactions on Machine Learning Research (07/2024)
A.7 Experiments
For Adult datasel, the output variable is whether Income exceeds 850K/yr. For Covertype, the oulput variable is whether forest covertype is category 1 or not. For Credit Default, the output is default payment (0/1).
24


Reviews:
[{"review_id": "1C6Imih8hr", "reviewer": "Reviewer_qtxJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "-- The idea of using an explanation for auditing and how it interacts with query complexity is novel.\n\n-- A main weakness of the paper is the assumption that the data scientist is truthful.\n\n-- Many details of the paper are unclear (see below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a framework where an auditor, in addition to having black-box access to the model also has access to the explanations provided by the model. The paper proposes an approach to use explanations to lower the query complexity of auditing.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think there are several ways that the clarifications can help the reader.\n\n(1) What is an example of a non-testable auditing property? \n\n(2) What is d in line 4 of algorithm 1?\n\n(3) The score function $s$ does not necessarily reflect a statistical quantity, correct?\n\n(4) Much of section 3.1.2 revolves around the assumption of perfect precision. This is very strong. Can this be relaxed?\n\n(5) Why does feature sensitivity matter (in the way that it is defined)? Two features can be fully correlated.  Are there other interesting properties that I am overlooking?\n\n(6) Why is the error between w and its estimation not converge to 0 in Fig 1?", "broader_impact_concerns": "Sufficiently addressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pnR1EvjuL4", "reviewer": "Reviewer_Gc1M", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n-The approach taken in this paper is fresh and original, attempting to understand the theoretical utility of various forms of explanations\n- Auditing is an important area that does not receive enough attention - I think definitions like \\eps-\\delta auditors are useful pieces for this to be studied further\n\nCritiques:\n- I think the scope of this paper is narrower than the framing makes it seem - there is a specific focus on feature sensitivity and I’m not convinced that much of the reasoning applies to other metrics. For instance, distributional metrics (e.g. fairness metrics, subgroup accuracy) have very different properties for which I don’t see similar analogues to what is presented in the paper, which relies on very specific properties of feature sensitivity. \n- Additionally, a very strong form of feature sensitivity (*any* sensitivity, globally) is considered, which confuses me a bit - the score function is given as the pct of pairs that are responsive, but this is never actually used. It’s not clear how much of the work applies to weaker, more practical notions of sensitivity\n- Due to the highly specific nature of a lot of these things, it’s unclear to me how helpful the theoretical results are, given the very general framing of the paper\n- On feature sensitivity: the example given is pen markings on an image, but I don’t think the method can be applied here - this is an abstract property that is emergent from many input features. A more relevant example might be helpful\n- the focus is only on binary classifiers, whereas the framing is much more general - not clear how most of this applies to continuous or structured output\n- It’s not clear to me what the path explanations in decision trees actually look like - what is contained in each node? Should be explained in more detail. Relatedly, what is “consistency” with a given decision path?\n- I’m not sure there’s that much insightful information in the section on Stopping Conditions: it seems like in the finite case, the approach involves enumerating all remaining options, and there is no general approach given for infinite spaces\n- I’m unclear in the Experiments section: are the results for all audits “Yes”? As in, do all methods have feature sensitivity? If yes, then probably should do some tests for the negative case; if no, then should discuss how models that are insensitive were derived.\n\nQuestions - could use clarification in paper:\n- Top of p3: why is auditor returning a binary response, rather than an estimate of s?\n- Def 2: why is s < \\epsilon not included here? I see the authors state that it would make guarantees harder, but it does seem like a useful property that at least merits some discussion\n- P4, top: where does the big-O characterization in “A Simple Baseline” come from?\n- In the proof of Thm 3.2, authors state that the auditor is deterministic - it’s not clear to me that Alg 1, line 1 is deterministic\n- Should be more explanation of how anchors work - I get confused around which A_x is returned - is this usually specified?\n- Should discuss how important the simplification of perfect precision for anchors is\n- Not clear to me why in 5.1 we check for faster learning, rather than faster auditing\n- How is the worst case line in Fig 1 calculated?\n\n\n\nSmall points:\n- Could be some more precise language in the intro (“societal applications”, “what an audit really signifies”)\n- I read the proof of Thm 3.2 in the Appendix and it makes sense - it would be nice to give a little intuition in the main body\n- Middle of p5: what is the “search space”?\n- What is the dimensionality of the 3 datasets used?\n- In 5.1, how are the hyperrectangles chosen? It seems non trivial given the precision constraints - can’t always choose the hyperrectangle of volume V centered at a point x", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper explores a theoretical framework for the auditing of ML models when explanations are provided. They consider 3 types of explanations, across linear models and decision trees, and focus specifically on feature sensitivity, giving worst-case query complexity analysis. They empirically show that the average case is often better than the worst-case, and discuss some approaches for verifying that model owner outputs are truthful in the auditing process.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the Strengths and Weaknesses section for details. In summary:\n\nKey Weakness to address:\n- paper scoping: content is much narrower than what is discussed, mostly due to focus on a strong form of feature sensitivity\n\nFurther: needs many clarifications across theoretical and experimental sections - it's unclear to me how many of these are critical weaknesses. But a quick list of some that jump out:\n- more details on what decision tree path explanations look like\n- make explicit if there are negative tests in the experiments\n- things around formulation of the auditing setup\n- more details on how the anchor setup works", "broader_impact_concerns": "no concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "o5QWiTrHUy", "reviewer": "Reviewer_btzA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nWeaknesses:\n- My biggest concern is that a lot of the paper seems to rely on the existence of \"responsive pairs\". For example, according to the authors' motivation that different features are correlated, it may be possible sometimes that these pairs don't exist for some features (for example, maybe I cannot change my gender and keep all the other features constant). What happens in this case/can the authors provide more motivation here?\n- It is a bit disappointing that the auditing for active learning only works for finite hypothesis classes, and that for infinite classes the fallback is to basically solve the learning task. It would be nice to understand whether there is a gap between auditing and learning in general.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Strength: \n- the learning theory approach to auditing fairness is new and useful \n- the authors provide algorithms and characterize worst-case query complexity in a variety relevant settings, in particular i) linear classification ii) decision lists and iii) active learning\n- The paper provides useful experiments, in particular those that also show average-case query complexity and complement the worst-case query complexity results", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I would like to see more discussion towards my biggest concern, which is the existence of responsive pairs for all features. If I am thinking of the features as resulting from some causal graph, changing one feature causes changes in other features, and there may not be such a clean way to compare two individuals.\n- I think the explanation of why the second algorithm for linear classifiers is useful can be improved (I am still not sure what the value of the anchor explanation based algorithm is when it has higher query complexity than the original algorithm the authors propose)", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have provided constructive feedback to the authors, raising concerns about the existence of responsive pairs for all features, the limitations of the auditing for active learning in the case of infinite hypothesis classes, and gaps in the experimental setup. The authors have responded to these concerns in a satisfactory manner, acknowledging the limitations of their approach and suggesting avenues for future research. All of this should be included during the revisions, and the scope of the paper made clear in the abstract and introduction. Overall, the paper presents an interesting and novel theoretical framework to auditing fairness in machine learning models. The findings of the paper are likely to be of interest to researchers and practitioners in the field of machine learning.
Decision: Accept (poster)