Robust Data Valuation with Weighted Banzhaf Values
Authors: Weida Li
Yaoliang Yu
Venue: NeurIPS 2023 poster (2023)
Keywords: data valuation
robustness
weighted Banzhaf values

Abstract: Data valuation, a principled way to rank the importance of each training datum, has become increasingly important. However, existing value-based approaches (e.g., Shapley) are known to suffer from the stochasticity inherent in utility functions that render consistent and reliable ranking difficult. Recently, Wang and Jia (2023) proposed the noise-structure-agnostic framework to advocate the Banzhaf value for its robustness against such stochasticity as it achieves the largest safe margin among many alternatives. Surprisingly, our empirical study shows that the Banzhaf value is not always the most robust when compared with a broader family: weighted Banzhaf values. To analyze this scenario, we introduce the concept of Kronecker noise to parameterize stochasticity, through which we prove that the uniquely robust semi-value, which can be analytically derived from the underlying Kronecker noise, lies in the family of weighted Banzhaf values while minimizing the worst-case entropy. In addition, we adopt the maximum sample reuse principle to design an estimator to efficiently approximate weighted Banzhaf values, and show that it enjoys the best time complexity in terms of achieving an $(\epsilon, \delta)$-approximation. Our theory is verified under both synthetic and authentic noises. For the latter, we fit a Kronecker noise to the inherent stochasticity, which is then plugged in to generate the predicted most robust semi-value. Our study suggests that weighted Banzhaf values are promising when facing undue noises in data valuation.

Robust Data Valuation with Weighted Banzhaf Values
Weida Li vidaslee@gmail.comm com
Yaoliang Yu School Computer Science University of Waterloo Vector Institute yaoliang www.laanggyuuuuuaeeoooooooo
Abstract
Data valuation, a principled way to rank the importance of each training datum, has become increasingly important. However, existing value-based approaches (e.g., Shapley) are known to suffer from the stochasticity inherent in utility functions that render consistent and reliable ranking difficult. Recently, Wang and Jía (2023) proposed the noise-structure-agnoes robustness against such stochasticity achieves the largest safe margin among many alternatives. Surprisingly. our empirical study shows that the Banzhaf value is not always the most robust when compared with broader family: weighted Banzhaf values. To analyze this scenario, we introduce the concept of Kronecker noise to parameterize stochasticity, through which we prove that the uniquely robust semi-value, which can be analytically derived from the underlying Kronecker noise, lies in the family of weighted Banzhaf values while minimizing the worst-case entropy. In addition, we adopt the maximum sample reuse principle to design an estimator to efficiently approximate weighted Banzhaf values, and show that it enjoys the best time complexity in terms of achieving an (e, 8) aappproximaaionn Our theory is verified under both synthetic and authentic noises. For the latter, we fit a Kronecker noise to the inherent stochasticity, which is then plugged in to generate the predicted most robust semi-value. Our study suggests that weighted Banzhaf values are promising when facing undue noises in data valuation.
framework to advocate the Banzhaf value for
Introduction
In machine learning, data curation plays a crucial role in training powerful models, and one big difficulty facing practitioners is how to quantify the extent of usefulness each datum possesses (under specific application). In practice, large datasets are typically noisy and often contain mislabeled data, which could harm the downstream performance of models trained on top. Sources that affect data quality include mechanical or human labelling errors (Frénay and Verleysen 2013), and poisoning attacks from malicious adversaries (Steinhardt et al. 2017). Therefore, would be extremely useful the potential importance of each datum can be efficiently and reliably determined. Data valuation aims to lay out a principled way to filter out noisy data and hunt down data that are valuable to retain.
In the emerging field of data valuation, the concept of value, originally developed in cooperative game theory as an axiomatic and principled way assign contributions to all players in a game, has become increasingly popular in machine learning (e.g., Ghorbani and Zou 2019; Jia et al. 2019a,b; Kwon and Zou 2022; Lin et 2022: Wang and Jia 2023). Typically, the procedures of training and testing are treated as games that constitute utility functions while each datum serves player. The contribution imputed each player is then equivalent the importance determined for each datum.
Recently, Wang and Jia (2023) pointed out that the inherent stochasticity in utility functions, which stems from the procedure of training models, is substantial enough to incur unexpected inconsistency in ranking data. To solve this issue, they introduced the noise-struccure-agnosii framework to
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

demonstrate that the Banzhaf value (Banzhaf 1965) is the most robust against such stochasticity compared with other previously employed values. Surprisingly, our extensive experiments on various datasets, see Figure for some examples, reveal that the Banzhaf value is not always the most robust compared with weighted Banzhaf values, which the Banzhaf value belongs.
5ocamants rank corraction coeffictent
Sokamants rank comsiaation coufficiont
0.5
0.5
08
0.4
04
Sycamarra
-02
00
600
55.0
3570
00.
589
560
00
06
22.9
55
660
06
0.7
0.6
0.7
0.1
553
FMNIST (10 classes)
MNIST (10 classes)
gas (6 classes)
The first row contains results from the experiment ranking consistency, while the second row is from the experiment of noisy label detection. For both metrics, the higher the better. The error bars represent the standard deviation over 10 random seeds. Specifically, each Spearman's rank correlation coefficient is averaged over (20) 45 pairs of independent rankings. Each parameter along the horizontal axis defines a weighted Banzhaf value, and 0.50 corresponds to the Banzhaf value.
Figure I:
In this work, our goal is to shed further light on the above-mentioned phenomenon both theoretically and empirically. As one might expect, our extensive experiments confirm that overall there is no single universally the best value, in terms of either noisy label detection or ranking consistency, across variety of experiment settings. Nevertheless, we show that it is possible adaptively estimate weighted Banzhaf value that achieves competitive robustness compared with the existing baselines. We summarize contributions follows:
1. First, we introduce the concept of Kronecker noise to parameterize the inherent stochasticity in practice, and prove that the uniquely most robust semi-value lies in the family of weighted Banzhaf values in terms of minimizing the worst-case entropy. Specifically, the parameter for the most robust semi-value can be directly derived from the underlying Kronecker noise.
Second, it is known that evaluating each semi-value is exponentially expensive w.r.t. the number of data being valuated, and thus we adopt the maximum sample reuse principle design efficient estimator for approximating weighted Banzhaf values. Particularly, we show that it enjoys the best time complexity in terms of achieving () approxxaaati......
Third, both synthetic and authentic noises are employed in our experiments verify the robustness assertion in Theorem 1. For the latter, we fit a Kronecker noise to the inherent stochasticity by minimizing the Kullback-Leibler divergence between Gaussian distributions.
Last, our empirical study shows that it is often that some member of weighted Banzhaf values achieves the best performance in noisy label detection well as ranking consistency when compared with the existing baselines. The empirical evidence highlights that there no single universally the best value across various experiment settings.
Our code is available
cwt.:/uubbbom//eeeaeeeeeeeeea http://ttttu..ccmmmara////eeeeee Banzhaf.

---

2 Background
2.1 Notations
Let Der and vat be training and validation datasets, respectively. We write n = [Darl, and identify
Drr with [n] = {1, 2, 22...,7i, nj. The definition of utility function v 2 + IR is pivotal for employing valued-based data valuation methods. Typically, for each subset S S [n]. v(S) is set to be the performance a chosen model trained on S. For example, v(S) is usually the accuracy measured on Dval for classification tasks. Specifically, v(0) is set to be the performance of randomly initialized models in this work. Let Gn be the set that contains all possible utility functions with domain 2 and define G = Un21 Gn. Particularly, the subscript of Un E G is to indicate the number of data being valuated. For convenience, we write S U and S instead of S U {i} and 5% and use S] when S represents set.
2.2 Axioms for Values
Value-based data valuation methods take advantage of the axiomatic approach developed in coop- erative game theory (Dubey et al. 1981; Shapley 1953; Weber 1977). A value is a function ø that maps each utility function Un E 9 to a contribution vector с E IR In other words, dc(v) = C the contribution of the i-th datum in Drr for the model performance achieved by training on Dir- There are four axioms we expect a value to have, which are
1. Linearity: δ(a Un + Un) = a (u.)) + (vx) for every Un: U/ E 9 and every R;
2. Dummy: 6,(v,) = C if 2/, Ui) = (S) + C for every S C [n]][i
3. Monotonicity: (v, 2 if v,, US 2 U. for every S C [n] [i;
4. Symmetry:' Φ(v, x) ((v,)) for every permutation of [n).
As proved by Weber (1977. Theorems 5 and 10). value o satisfies the above four axioms if and only if there exists a list of non-negative vectors E (p" R2")21 such that, for each 2
E. (g=1)=² and
oi(Un: 3)
Σ P.-1 (Ux(SUt) un (S)) for every Un E 9 and every e [n]. SCbIV
(1)
All such values are called probabilistic values.
There is one more regularization implicitly used by Dubey et al. (1981) to filter out some undesired probabilistic values. The eventual regularized probabilistic values called semi-values." 34 We explicitly rephrase the regularization as an extra axiom in this paper. Let be an extra datum labelled by + and extend each utility function on into Un+1 defined by 1++1(S) (S n [n|] for every S C [n 1]. The extra axiom reads as follows:
5. Consistency: (1,: E) = de (Tn+1: E) for every Un E G and every i E [n].
The axiom of consistency states that a value should not change the previously assigned values of importance if the added data do not contribute anything. Note that the proposed axiom of consistency is the discrete version of the dummy consistency proposed by Friedman (2003, Definition 7) in cost-sharing problems. We have the following characterization for semi-values:
Proposition (Dubey et al. 1981, Theorem I(a)). A probabilistic value & is a semi-value if and only there exists a probability distribution P on the interval [0, 1] such that
p- = / (LP))) for every 1 S S
(2)
[0.1]
'It can be equivalently replaced by the axiom of equal treatment in this context, which is not generally equal to the axiom of symmetry. We refer the reader to Appendix A for more details. "Their assumption that v., (0) = can quickly removed by showing that ((v..) v,, constant based on the axioms of linearity and monotonicity.
'In some references (e.g.. Wang and Jia 2023), probabilistic value is referred semi-value, but semi-value may refer a distinct entity (e.g.. Dragan 2006), i.e., what we semi-value in this work.
'The family of probabilistic values is strictly larger than that of semi-values. For example, for pa = (0, 1/2, 0). there non-negative pa satisfying that pi př + pius for every 1 < isss 3.
3

---

Table The underlying CDFs on the interval [o, 1] for semi-values of interest. denotes the variable of CDFs. 1 is defined by X = 1 if E [0.5, 1] and 0 otherwise. Beta(a, 5) is parameterized notation for the Beta Shapley values.
Method
G-Shapley
Beta 3)
Data Banzhaf
CDF
1-1 (1 - t) ad
X)0.5.1]
Moreover, the map from all such probability distributions to semi-values is one-to-one.
The axiom of consistency basically imposes that
1 = p. + P
n++ for every 1 S 8 S n,
which is the key for connecting all components in E. All in all, combing Eqs. (1) and (2) yields the formula for each semi-value,
/ Σ - ( (S) SCinNV
or(Un:
(3)
for every 2, E G and every i [n]. It suggests that each semi-value is just the integral of weighted Banzhaf values w.r.t. the underlying probability distribution P. Particularly, substituting the uniform distribution for P recovers the formula for the Shapley value (Shapley 1953) derived from the multilincar extension of utility functions (Owen 1972, Theorem 5).
2.3 Semi-values for Data Valuation
As pioneering work, Ghorbani and Zou (2019) proposed Data Shapley that includes G-Shapley and T'MC-Shapley for data valuation, and demonstrated its effectiveness in applications. Later, Beta Shapley was developed to improve the overall performance of value-based data valuation (Kwon and Zou 2022). Recently, Wang and Jia (2023) set up a that their proposed Data Banzhaf is the most robust compared with the previous works. Basically, The underlying cumulative density
framework to demonstrate
the distinction between these methods is the use of functions (CDFs) of P in Eq. (2) for these value-based data valuation methods are listed Table 1. Specifically, the ThC-Shapley (if the indices for truncation are the same for all sampled permutations of [n)) some probabilistic value up to some scalar.
In cooperative game theory references, weighted Banzhaf values (which are semi-values were discovered by Ding et al. (2010) and Marichal and Mathonet (2011, Theorem 10) based on the approximation of utility functions (Hammer and Holzman 1992). To obey the axiom of symmetry, the family of symmetric weighted Banzhaf values is taken herein, which can parameterized by E (0, 1]. Precisely, for w-eeghtedd Banzhaf value, the corresponding coefficients in Eq. (1) are
ph = w0 w0=1((1 - w/"- for every S S n.
Equivalently, its underlying CDF is X[w,1), while its underlying probability distribution the Dirac delta distribution & defined by
{
E
for every Borel measurable subset S of 1]. E
Particularly, weg-weigh Banzhaf value is exactly the Banzhaf value employed in Data Banzhaf, while L.O-weighted Banzhaf value is just the leave-one-out method, which is
(C.; 81) = un ([x) vn ([n]))) for every en E & and i E [n].
'In some references (e.g., Domenech et al. 2016), weighted Banzhaf values are referred to as multinomial probabilistic values.

---

3 Main Work
In this section, we first introduce how to use the maximum sample reuse (MSR) principle to design an efficient estimator for weighted Banzhaf values, and also present its time complexity in terms of (..))))ooxiimatioo
Then, we introduce the concept of Kronecker noise to parameterize the underlying stochasticity in utility functions, through which we show that the uniquely most roust semi-value always lies in the family of weighted Banzhaf values while minimizing the worst-case entropy.
3.1 Efficient Estimator for Weighted Banzhaf Values
To exactly compute each probabilistic value shown Eq. (I), we have to evaluate the provided utility function 2" times in total, which is intractable when n is large, not to mention the expensive cost of training models. Therefore, in general, each probabilistic value can only be approximated using estimators. Specifically, the sampling lift estimator can be used to approximate every probabilistic value (Moehle et al. 2022), and its weighted version was employed by Kwon and Zou (2022) for approximating their proposed Beta Shapley values. Meanwhile, there are efficient estimators designed specifically for the Shapley value (e.g., Castro et al. 2009; Covert and Lee 2021; Jia et al. 2019b; Lundberg and Lee 2017). Recently, Wang and Jia (2023) demonstrated how to the MSR principle to design an efficient estimator for the Banzhaf value, but they also presented that such a principle can not extend many other probabilistic values (e.g., the Beta Shapley values). Nevertheless, we show that MSR estimator exists for weighted Banzhaf values.
For approximating w-weighted Banzhaf value based some en E G. we first independently sample a sequence of Bernoulli vectors (b1. b bm where the entries of each by E IF"' are drawn from independent Bernoulli distribution X with P(X = 1) w;; then, the sequence of Bernoulli vectors are transformed into a sequence of subsets {S1, S2, ......... Sm3 of [r]] by defining E Sy if and only the i-th entry of by is 1; finally, the approximate value is computed by
(i(u:; dw.
1
Σ
(S)
1
vn( for every i [r]]
189i
S
(4)
SESs
SES3
where S3 = {S, E S and Sy: = (S, {}}.
As shown in Eq. (4), each utility evaluation is employed for estimating the importance of every datum in in]. while for the (reweighted) sampling lift it two utility evaluations for only one datum; see Appendix D.2 for more details. Therefore, it could be expected that the MSR estimators more efficient, which is certainly confirmed by Figure 2. Meanwhile, such an MSR estimator enjoys the currently best time complexity bound demonstrated by Wang and Jia (2023, Theorem 4.9).
much
Proposition 2. Assume ||v, S for every Un E G. The estimator based Eq.(4) requires 0 2t log }) utility evaluations to achieve P(I]ō(un: 8w) - 0(Vn; 6w)ll2 2 E) S for every utility function E G.
3.2 Robustness under Kronecker Noises
If 2|n is ordered, each stochastic utility function U, can be treated random vector in R2". and thus its randomness be summarized by its covariance matrix D x2","", However, there are (22) parameters to characterize. To make the analysis tractable, our approach is to parameterize D simply as possible that the most robust semi-value can be analyzed accordingly. Before proceeding, we introduce the binary ordering for 21nl, so that we legally have the covariance matrix D.
Ordering of 2|n] Define binary sequence [0]2 [1]2, .,, 22 1]2 by letting [k]] be the binary representation of l in n-digit format. We order (S) SC along this binary sequence by assigning to each binary representation [k]] a subset S, S [n]] defined by E S if and only if the (n+1-i)-th digit
of kk]2 is 1. For example, if n = 3, the binary sequence is 000. 001, 010, 011, 100. 101, 110, 111, and the corresponding ordering for the subsets of [3] is W. [1). (2), [1, (3). (1, 3], (2. {1, 2. We refer to this ordering binary ordering. In the rest of the paper, we treat each stochastic utility
function U, e G random vector in I22 w.r.t. the binary ordering. The advantage of this ordering
5

---

is that it aligns well with the Kronecker product so that we can parameterize the covariance matrix of each stochastic utility function using just one simple covariance matrix Σ 22x2
Assumption (Kronecker noises). Let 2(r) be ordered w.r.t. the binary ordering. For each random vector Un E I (equivalently, a stochastic utility function in G), we assume Un E[vn] En % En-1 & ... & 61 where (ci)isiga are n independent continuous random vectors in R.² that have the same positive-definite covariance matrix Σ.
Proposition 3. Under Assumption 1, there
Un (S) = 18(u,(() (S) + II
6,2 II 6,1, for every S S [n],
iES
iES
Cov(U,)
Σ 2
2 Σ repetitions).
Cov(v,(() (T)) 01l
[x] [=]](SUT)] (U
|SnT for every S,T S [m]
12
0:2
Remark 1. According to Proposition 3, Assumption 1 provides simple parameterization for the covariance matrix of the stochasticity inherent in Vn- Though such simple modeling is yet ideal, is sufficient for arguing theoretically that there is no single universally the most robust semi-value across different stochastic utility functions. Notably, as shown in Table 2, weighted Banzhaf values tend to be the most consistent in ranking data, and the most empirically robust varies across different experiment settings. Overall, our theory emphasizes that a seree--srutuursseciiie framework is able to provide finer conclusion for robustness compared with the previous caass-sttuuture-aee framework (Wang and Jia 2023).
Next, we propose the entropy of continuous random vectors to define the worst-case uncertainty brought by the parameterized covariance matrix, which is
sup
h( P))
(5)
Uy EG, Cov
Ein]
where P is probability distribution that defines semi-value Eq. (3), h is the entropy that measures the uncertainty of continuous random vectors, and ] = Σ & E.... E (n repetitions). Intuitively, p(e, P) tends to be deterministic as ( P)) decreases to zero. Since Eq. (5) defines the least upper bound on h(0(v,; P)), the lower Eq. (5) is, the more robust (equivalently, more deterministic) the corresponding semi-value is. Therefore, the most robust semi-value is defined to be the one that minimizes
argmin PEP V.
sup (=)
h(o(Un) P))
(6)
where P is the set that contains all measualeea probability distributions on the interval [o, 1]. In other words, we try to determine a semi-value that can best tolerate the largest uncertainty brought by any noises having the covariance matrix Ein] As one may expect, the most robust semi-value depends on the choice of Σ E R22
Since p(v,) vn. ; P) is linear in en E Gn, the result of Cov(o(u;; PJ) subject to Cov(u,) = [nm] only de- pends on m] and P. Consequently, sup su......: Cov(v=)=E!n h(@(1,, ( P)) = supy Cov - h(Y) where V Cov(ó(v.: P)). It is known that supy: Cov(Y)- h(Y 2 (1+ log 2x) Z log det W, and the maximum is achieved if Y is Gaussian random vector. Besides, Y is Gaussian if is Gaussian because @(u,; P) is linear in Un In. All in all, the optimization problem (6) equivalently reduces to be
argmin (CovCoC(rra P)))
PEP
s.t. Cov(va) = inn
Theorem 1. Under Assumption 1, and further assume 012 < min(on, the Dirac delta distribution dw- with
w" 01 012
(8)
011 0z2 22012
is optimal to the problem for every n 2 1. In addition, the optimal solution is unique if n >> 3. Remark Theorem 1 suggests that 0.5-weigh Banzhaf value (i.e., the Banzhaf value) is the most robust provided that T11 022, which coincides with ( (Wang and Jia 2023, Theorem 4.6). Specifically.

---

they simulated some isotropic Gaussian noises added to deterministic utility functions to verify that the Banzhaf value is the most robust in ranking data, which is also supported by Theorem 1. However, the first column of Figure 3 shows that the Banzhaf value is not always the most robust if the added noises follow Kronecker noises with 01 o 022- practice, Table 2 also refutes that the Banzhaf value is universally the most robust.
Experiments
Our experiments contain three aspects: 1) ap- proximation efficiency of the MSR estimator for weighted Banzhaf values; 2) verifying The- orem 1 using synthetic and authentic noises; 3) empirical study to show that the most robust/- effective semi-values tend to be some weighted
1.75
sampling lift
1.50
weighted sampling lift maximum sample reuse
relative d
1.25
1.00
Banzhaf values.
0.75
All datasets used are from open sources, and classification tasks. Except for MNIST and
0.50
FMNIST, each Drr or Deal is balanced between different classes. Without explicitly stated, we set DDeall 200. All utility functions are set be the accuracy reported on Deat with lo- gistic regression models being trained on Drr, except that we implement LeNet (LeCun al. 1998) for MNIST and FMNIST. To have the merit of efficiency, we adopt one-epoch one- mini-batch learning for training models in all types experiments (Ghorbani and Zou 2019). More experiment details and results included in Appendices D and E.
0.25
0.00
250
500
750
1000 1250 1500
number of utility evaluations per datum
Figure 2: Comparison three estimators for 0.8- Banzhaf value on 2dplanes dataset. The shaded region represents the standard deviation over 10 different random seeds.
4.1 Approximation Efficiency
The MSR estimator is compared with reweighted sampling lift and sampling lift estimators. To calculate the exact values, set [Da-1 16. Besides, the learning rate is set to be 1.0. To have fair comparison, we plot relative difference | 21|2/ ||l|2 along the number of average utility evaluations, i.e. durility evaluations Figure/ plotted with 10 different random seeds used by estimators. n It demonstrates that the MSR estimator is significantly the most efficient.
4.2 Verification for the Theorem
Experiments based on synthetic and authentic noises are designed to verify Theorem 1. We set [Dzrl 10 so that the exact values can be cheaply computed.
For synthetic experiments, we simulate Kronecker noises with each e; independently and identically following a Gaussian distribution (0, E), which are employed added noises to deterministic utility functions. Besides, the learning rate is set to be 0.05. Specifically, we fix Ti1 and 022 while varying 122 along the horizontal axis. For each 012. the corresponding added noises are simulated using 10 different seeds. The Spearman's 's rank correlation coefficient is used to measure the similarity between the rankings of the mround-truth value and any noisy one. The results are reported in the first column of Figure 3. where the one tagged as "robust semi-value" refers to the corresponding weighted Banzhaf values predicted by Eq. (8). clear that Theorem predicts the most robust semi-value well, and that the Banzhaf value is not universally the most robust under these synthetic noises.
Next, we examine Theorem 1 by fitting a Kronecker noise to the stochasticity inherent in the given utility function, and then compute the predicted most robust semi-value using Eq. (8). To produce simple utility functions, we set (Deat = 10. Besides, the learning rate for utility functions is set to be 1.0. The underlying covariance matrix empirically approximated by D, and then we fit Kronecker
7

---

Sporrmant rank coreeation coePiieet
2.00
Spaaman's coresat couffilinn
caneeaa coemderc
0.75
95.5
Shapley
6.85
Banchel
0.80
Batat4, 1)
8..5
Betall, 4)
0.70
Betarl. 16)
semi-value
-2.4
0.4
044
0.200
costicions
0.4
0.135
0.100
2.125
0.8
Betar16, 1)
6.100
Betal4,
5,755
16)
6.2
3.50
0.6
robust somi-xolle
9425
00955006 DEDEEEE
3,000
8 88swetratr SEREEEUE
spambase (synthetic)
iris (authentic)
phoneme (authentic)
Figure 3: (a) Synthetic noises: Each point represents the Spearman's 's rank correlation coefficient averaged over 10 random seeds. For each 012. the robust semi-value is the weighted Banzhaf value parameterized by (ø11 012)/(011 + 022 12 as predicted by Theorem 1. For the first row, we set 011 1.5 and d22 0.5, while it is d11 = 0.5 and Authentic noises: Ranking consistency is measured by the mean and standard deviation of the Spearman's rank correlation coefficients between all pairs of 10 random seeds. The variance refers to 10 | m m|/3/10 where 1o Σne d'. The computed "robust" parameters are 0.5255 and 0.5341 for iris and phoneme datasets, respectively.
1.5 for the other. (b)
noise by optimizing the Kullback-Leibler divergence between Gaussian distributions, which is
10 repetitions
argmin KL (L(N((, WO E BERaxa
& Σ
The final results averaged over 10 random seeds are presented in the last two columns of Figure 3. Each parameter in {0.00, 0.05, 0.10.... 0.95, 1.00) defines a specific weighted Banzhaf value, while {(16, 1), (4, (1, 4), (1, 16)) parameters for the Beta Shapley values. The tagged "robust" is generated from the approximate Kronecker noise using Eq. (8). As demonstrated, the predicted "robust" semi-values do achieve the best in both ranking consistency and variance.
4.3 Empirical Study
Following the previous study (Wang and Jia 2023), we implement an exploratory study on 23 datasets, including two types of experiment: 1) noisy label detection and 2) ranking consistency.
We fix [D,,| means the induced stochasticity inherent in utility functions is more complicated than Assumption 1. For each dataset, the chosen model individually fine-tuned for the learning rate. The randomness in each utility function stems from the underlying random seed that determines the order of feeding training data well as the initialization of models. All results are reported using mean and standard deviation over 10 random seeds. For each estimator, the total number of utility evaluations is set to be 400, 000. Permutation estimator (Castro et al. 2009) is used for Shapley value, reweighted sampling lift estimator for Beta Shapley, and MSR estimator for weighted Banzhaf values. Specifically, 0- weighted Banzhaf value and -weiighted Banzhaf value require only a + utility evaluations to compute exactly, and thus do not use any estimators for them.
000 for all datasets except that is |Prrl 2, 000 for MNIST and FMNIST, which

---

Table 2: Ranking consistency. For weighted Banzhaf values, we only report the best one from the parameter list {0.00, 0.05, 0.10, 0..5,, 1.00]. The first value in the column of "Weighted Banzhaf" is the parameter that achieves the highest ranking consistency. Boldface numbers mark the best. The number following each dataset refers to the number of classes used in the experiments.
Dataset
Weighne Banchaf
Bunzhaf
Beta[16,1]
Beta(L.
Beta[1.4]
Betail. 16)
Shapley
MNIST (10)
0.20 0.680 1: 0.120
0.581 +: 0.075
0.073 2: 0.082
0.020 1: 0.043
-0.001
2: 0.030
-0.009 a: 0.037
0,011 a: 0.019
FMNIST (10)
0.50
0.670
0.012
0.562 2: 0.0:1
0.017 0.082
0.007
0.016
-0.001 20,055
0.009 0.029
0,002 a 0.021
2áplanes (2)
0.950
0.091
0.424 0.155
0.358
0.1
0.046= 0.087
0.001 0.133
0.256 0.083
bank marketntg (2)
0.75
0.895 0.028
0.814 2: 0.092
0.599
0.096
0:445 1 0.085
0.015 0.094
0,041 0.128
0.226 0.033
bioresponse (2)
0.00
0.997 1 0.000
0.948 : 0.003
0.193 1 0.082
0.169 1 0.090
0.016 2 0.037
0,301 1: 0.031
0.122 1 0.021
covertype (7)
0.35
0,840
0.033
0.832 0.042
0.618 0.006
0.490 + 0.051
0.005 0.194
-0.028
0.227
0,234 0.026
epu (2)
0.926
0.549 0.096
0.000 0.132
-0,004 10158
0.142 0.028
defaull (2)
0.31 0,953 1: 0.011
0.94] 2: 0.007
0.512 1: 0.078
0.369 0.059
0.022 0.090
0,001
0:13
0.170 0.031
jas (6)
0.05
0.959
:: 0.000
0.729 = 0.019
0.204 : 0.076
0. 0.105
1: 0.057
0,005 = 0.068
-0.017 2: 0:094
0.063 = 0.052
har (6)
0.05
0.956
0.003
0.741 0.012
0.153 0.063
0.074 0.057
-0.001 0.050
-0.001
0.058
0.051 0.051
letter (26)
0,966
0.001
0.530 0.0M8
0.065
0.021 0.110
0.148
0.197
opidigits (10)
0.22
0.923
:: 0.010
0.898 :: 0.909
0
0.038
0445 1: 0.049
0.024 = 0.076
0.004 : 0.145
0:278 = 0.030
pendigits (10)
0.05
0.947
1: 0.014
018006 - 0.010
0.381 1: 0.100
0.259 1: 0.085
0,031 2 0.096
0,021 0.142
0.113 - 0.024
(2)
0.85
0,783
0.158
0.588 0.309
0.601 0.141
0.499 0.848
0,022 0.125
0,008
1 0.155
0.525 = 105
pol
0.970
0.003
0.938 0.003
0.479
0.520
0.105
0.006
0.033 0.158
0.186 0262
satinnge (6)
0.30
0.863
1: 0.021
0.814 1 0.028
0.341 1: 0.135
0.189 0.087
0.001 2: 0.086
0,006 0:087
0,100 1: 0.033
segment (7)
0.25
0.941
1: 0.012
0.883 = 0.906
0.361 2 0.118
0.213 1: 0.069
0,001 = 0.100
0,005 2 0.149
0.113 = 0.030
spumbuss (2)
0.20
0.939
:: 0.00T
0.876 + 0.907
0.466 0.073
0.336 0.070
-0.001
= 0.094
0.004 0:148
0.194 + 0.030
rexture (11)
0.961
0.011
0:217 0.073
0.109
0.050
0.003 0.072
0.020 0.080
0.040 0.092
wind (2)
0.00
0.793
3: 0.111
0.720 - 0.836
0.398 0.091
0.215 1. 0.078
0.001 0.079
0,012 2: 0.114
0.116 2 0.025
Table 3: Noisy label detection. For weighted Banzhaf values, we only report the best one from the parameter list {0.00, 0.05, 0.10, 0.95, 1.003. The first value in the column of "Weighted Banzhaa" is the parameter that achieves the highest Fl-score. Boldface numbers mark the best. The number following each dataset refers to the number of classes used in the experiments.
Dataset
Weighted Banchaf
Banchaf
Beta(16. 1)
1cta(
1.ta(1,16)
Beta[1.
Shapley
MNIST (10)
0.50
0.625 0.040
0.625
0.040
0:228 + 0.023
0:226
0.017
0.210
0.013
0:207 + 0.013
0.229 0.020
FMNIST (10)
0.25
0.496 1: 0.058
0.448
=0.02
0.217 + 0.019
0.223 +: 0.017
0.208
:: 0:015
0.208
:: 0.016
0,212 0.0111
2dplanes (2)
0.05
0.609
+ 0.059
0.346
0,014
0.572 + 0.052
0.532 + 0.055
0.219
0.035
0:210 + 0.330
0.412 1:112+00 0.033
mank-narketing (2)
0.05
0.528
0.400 0.014
0.025
0.452 0.036
0:021
0.226
0.368 0.025
bioresponse (2)
0.05
0.502 1: 0.012
0.481
0.011
0.325 4: 0.001
0.316 1: 0.030
0.221 +: 0.022
0.204 1: 0.027
0,253 0.025
covertype (7)
0.05
0,518
1 0.026
0,118
= 0.025
0.481
1: 0.025
0.398 1: 0.026
0.217 1 0.014
0.212 +: 0.023
0,318 - 0.082
cpu (2)
0.05
0.772
0.017
0.648
0.015
0.682 0.031
0.508
0.045
0.242 0.028
0.212 +: 0.031
0.300 0.027
default (3)
0.05
00,398
0.010
0.346 0.011
0,350 + 0.019
0.316 0.019
0.2003 + 0.022
0:211 0.023
0.286 0.022
gas (6)
0.10
0.767
+ 0.018
0.731 0.021
0.402 + 0.030
0.358 + 0.020
0.222 + 0.018
0.209 + 0.025
0.321 0.036
bar (6)
0.10
0.869
1: 0.0088
0,809
0.013
0,388
0.028
0.355 = 0 0,125
0.222
0.023
0.210 + 0.022
0.328 0.021
letter (26)
0.05
0.552
0.467 0.009
0.038
0.384
0.030
0.220 1:
0.336 0.022
opidigits (10)
0.05
0.852
+: D.011
0.701 0.016
0.739 + 0.025
0.652 + 0.023
0,248
0.000
0.218 + 0.633
0.513 0.003
pendigits (10)
0.35
0,822
1: 0.306
0.814 0.008
0.500 +: 0.056
0.489 = 0.037
0.240 1: 0.027
0.224 + 0.026
0,350 1: 0.027
phoneme
0.05
0.492
0.021
0.382 0.023
0.030
0.450 0.034
(1,242 0.048
0.033
0.376 0.047
pal (2)
0.05
0.646
0.011
0,564 0.009
0,198 : 0.035
0.176 = 0.037
0.275 +: 0.036
0.218 + 0.045
0.358 0.030
satimage (6)
0.06
0.6644
:: 0.082
0.476 = 0.087
0.472 + 0.055
0.398 :: 0.065
0.2225 + 0.021
0:208 + 0.022
0.342 = 0.031
segment (7)
0.15
0.763
0.015
0.712 0.014
0.502
0.012
0.152 0.0122
0.249 0:027
0.228 1: 0.031
0.351 0.021
spambase (2)
0.05
0.757
0.012
0.717 0.008
0.057
0.511 0
0.243 0:036
0.220 + 0.008
0.412 0.027
texture (1I)
0.15
0.834
1: 0.009
0,762 0.013
0.458 1 0.041
0.588 1: 0.036
0.210
4: 0.018
0.194 1: 0.034
0.315 0.028
wind (2)
0.05
0.686
+ 0.016
0.618 0.019
0.520 + D.026
0.428 + 0.044
0,227
0.025
0.222 + 0.031
0.359 0.020
Ranking Consisteney In data valuation, it could be the ranking of data that matters the most, but the randomness of utility functions may produce inconsistent rankings. For each semi maiiev the averaged Spearman's 's rank correlation coefficients over all possible pairs, which is (20) total, are calculated to measure ranking consistency. The results are summarized in Table 2, while figures with more details are included in Appendix E. As presented, it is mostly some member of weighted Banzhaf values, not always the Banzhaf value, that achieves the highest ranking consistency compared with the baselines.
45 in
Noisy Label Detection Notice that a more robust semi-value does not necessarily produce a higher quality of data valuation. This experiment is to present how well weighted Banzhaf values would achieve in noisy label detection. For each dataset, we randomly flip the labels of 20 percent of data in D.,- to be any of the rest in uniform manner. Those flipped data are treated as having noisy/incorrect labels. Particularly, such a flipped Drr also used for reporting ranking consistency in Table 2. Then, each estimated semi-value is used to detect noisy labels by marking data assigned with values of importance less than or equal to 20 percent percentile as mislabeled. The results are summarized in Table 3, and figures that contain more details are included in Appendix F. As observed, the best performance is mostly achieved by weighted Banzhaf values, and most of them are not the Banzhaf value.
9

---

In both types of experiments. it manifests itself that the semi-value that achieves the best in ranking consistency does not coincide with the one that achieves the highest Fl-score on each dataset. Nevertheless, the detailed figures in Appendix E. show that weighted Banzhaf values tend to be more robust than the Beta Shapley values, which include the Shapley value. Moreover, we can conclude that there is no single universally the best semi-value across various experiment settings in terms of either ranking consistency or noisy label detection. For each utility function, it would be useful if the best semi-value can be effectively determined in advance.
5 Conclusion
We introduce noise-structure-ppeciie framework to theoretically assert that is always a member of weighted Banzhaf values that is deemed the most robust in terms of minimizing the worst-case entropy. Theorem shows that the most robust semi-value would vary across different experiment settings. Our extensive empirical study demonstrates that weighted Banzhaf values are promising when dealing with inevitable noises inherent utility functions. Particularly, all experiments suggest that there is no universally the best or the most robust semi-value for all experiment settings. Therefore, future investigation is to set up principled approaches that can pin down the most robust or the most effective value in advance.
6 Limitations
The concept of Kronecker noise still ideal for fitting the stochasticity in practice. The verification of Theorem using fitted Kronecker noises only be done based on simple utility functions, as one may expect. Nevertheless, the thcoretical and empirical evidence is sufficient to argue that there single universally the most robust the most effective semi-value across various experiment settings, and that weighted Banzhaf values are promising in practice.
Acknowledgments and Disclosure of Funding
We thank the reviewers and the area chair for thoughtful comments that have improved our final draft. YY gratefully acknowledges NSERC and CIFAR for funding support.
References
Banzhaf J. (1965). "Weighted Voting Docsn't Work: A Mathematical Analysis", Rutgers Law Review, vol. 19, pp. 317-343.
Castro, J., D. Gómez, and J. Tejada (2009). "Polynomial Calculation of the Shapley Value Based Sampling". Computers & Operations Research, vol. 36, no. pp. 1726-1730.
Covert, I. and S.-I. Lee (2021). "Improving KerneISHAP: Practical Shapley Value Estimation via Linear Regression", " In: International Conference on Artificial Intelligence and Statistics. PMLR, pp. 3457-3465.
Ding, G., R. F. Lax, J. Chen, P. P. Chen, and B. D. Marx (2010). "Transforms of Pscudo-Boolcan Random Variables". Discrete Applied Mathematics, vol. 158, no. 1, pp. 13 24-24.
Domenech, M. J.M. M. Giménez, and M. A. Puente (2016). "Some Properties for Prohabilistic and Multinomial (Probabilistic) Values Cooperative Games". Optimization, vol. 65, no. 7, pp. 1377-1395.
Dragan, I. (2006). "On the Semivalues and the Least Square Values Average Per Capita Formulas and Relation- ships". Acta Mathematica Sinica, vol. 22, pp. 1539-1548.
Dubey, P. A. Neyman, and Weber (1981). "Value Theory without Efficiency". Mathematics of Operations Research, vol. 6, no. 1, pp. 122-128.
Frénay, B. and M. Verleysen (2013). "Classification in the Presence Label Noise: A Survey". JEEE Transac- tions on Neural Networks and Learning Systems, vol. 25, no. 5, 845-869.
Friedman, E, J. (2003). "Paths and Consistency in Additive Cost Sharing". International Journal of Game Theory, vol. 32, 4, pp. 501-518.
10

---

Ghorbani, A. and J. Zou (2019). "Data Shapley: Equitable Valuation of Data for Machine Learning". In: International Conference on Machine Learning. PMLR. pp. 2242-2251.
Hammer, P. L.. and R. Holzman (1992). "Approximations of Pscudo-Boolents Functions; Applications Game Theory". Zeitschrift für Operations Research, vol. 36, no. 1. pp. 3-21.
Jia, R., D. Dao, Wang, F. Hubis, N. M. Gurel, B. C. Zhang, S. D. Song (2019a). "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms", Proceedings of the VLDB Endowment, vol. 12, no. 11.
Jia, R. et al. (2019h). "Towards Efficient Data Valuation Based on the Shapley Value". In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, pp. 1167-1176.
Kwon, Y. and J. Zou (2022). "Beta Shapley: A Unified and Noise-reduced Data Valuation Framework for Machine Learning". International Conference on Artificial Intelligence and Statistics. PMLR, pp. 8780- 8802.
LeCun, Y., L. Bottou, Y. Bengio, and P. Haffner (1998). "Gradient Based Learning Applied to Document Recognition". Proceedings of the IEEE, vol. 86, no. 11. 2278 23224.
Lin. J., A. Zhang, M. Lécuyer, J. Li. A. Panda, and S. Sen (2022). "Measuring the Effect of Training Data on Deep Learning Predictions via Randomized Experiments" _ In: International Conference Muchine Learning. PMLR, pp. 13504.
Lundberg, M. and S.-1. (2017). Unified Approach to Interpreting Model Predictions", Advances Neural Information Processing Systems, vol. 30.
Marichal, J.-L. and P. Mathonet (2011). "Weighted Banzhaf Power and Interaction Indexes Through Weighted Approximations of Games". European Journal of Operutional Research, vol. 211, no. 2, 352-358.
Moehle, N., S. Boyd, and A. Ang (2022). "Portfolio Performance Attribution via Shapley . Journal of Investment Management, vol. 20, 3, pp. 32-52.
Owen, G. (1972). "Multilinear Extensions of Games". Management Science, vol. 18, 5-part-2, pp. 64-79.
Shapley, L. S. (1953). "A Value for N-Person Games". Annals Mathematics Studies, vol. 28, pp. 307-317.
Steinhardt, J., P. W. Koh, and Liang (2017). "Certified Defenses for Data Poisoning Attacks". In: Advances Neural Information Processing Systems. Vol. 30.
Wang, J. T. and R. Jia (2023). "Data Banzhaf: A Robust Data Valuation Framework for Machine Learning". In: International Conference on Artificial Intelligence and Statistics. PMLR, pp. 6388-6421.
Weber, J. (1977). "Probabilistic Values for Games". The Shapley Value, Essays in Honor of Lloyd S. Shapley, pp. 101-119.

---

Table of Contents
The Axiom of Equal Treatment
B Proofs for the Propositions
13
C Prerequisites and Proof for Theorem
15
C.I Extend Semi-values to Be Semi-indices
15
Interaction Transform
C.3 Matrix Representation for Semi-indices
18
C.4 A Theorem of Robustness for Semi-indices
19
C.5 Proof for Theorem
22
C.6 Lemmas
23
D Experiment Settings
26
D.1 Fitting Kronceker Noises
26
D.2 Sampling Lift
26
More Experiment Results
27
A The Axiom of Equal Treatment
In the existing references, the axiom of symmetry is sometimes used to refer to the axiom of equal treatment, but they are not always interchangeable.
Equal Treatment: (v.(..) = (2h) un (S = ()) for every $ S [n]] Mr,
The axiom of equal treatment is not always equal to the axiom of symmetry. As counterexample
pick 2, and consider value defined by Φ1 (w) 1 (1)1 + 2 (2) and (2(v) 3 10((1) (2)..
The reader can verify that satisfies the axiom of equal treatment but violates the axiom of symmetry (e.g., take u(1) = and v2) = 6).
Nevertheless, they are equivalent in some contexts. Recall that a weaker version of the axiom of dummy is
Null: de(U,,) = (S (S) for every S S [n]]Li
Proposition 4. Suppose value verifies the axioms of linearity and null, then & verifies the axiom of symmetry if and only if it verifies the axiom of equal treatment.
Proof. The only if part is trivial the axiom of symmetry always implies the axiom of equal treatment, and thus we only prove the if part. Let n 2 be fixed, since & verifies the axioms of linearity and null, by (Weber 1977, Theorem 2), we have
(r(Un)
Σ p's (vn(SU)) u for every v, E In and E [n). SE(MM
(S))
For every S C N, define us Gn by letting (T( 1 T = and otherwise. For every i # j and 5 C [n] vij by the axiom of equal treatment, there
p (u(us usuj + usuig) = (usuu + usuj + usus)) P'S. On the other hand, for every S with s 1, and every i.j S, there
(v(us) Φ5 (us) Peyy
(10)
'By using the axiom of null instead of the axiom of dummy, the only difference is that there is no Esqnjy pss 1.
12

---

Combing Eqs. (9) and (10), we can get p's Ps for every E [n]] and every S S [n]]d. To demonstrate, take P(2.3) and P(s.6) as example, there
([2.3) = P(2.3) = Pf4.3) = p(4.3) = P(4.5) = -[(45] = P(6,,)-
Therefore, the equality p's Ps for every E [n] and every 8 S [n]]i implies the axiom of symmetry.
B Proofs for the Propositions
Proposition 2. Assume || I for every un E G. The estimator based Eq.(4) requires
0 log }) utility evaluations to achieve P(1(((un: 8w) - o(v,: bw) 2 S for every utility function E g.
Proof. Note that it only requires + 1 utility evaluations for exactly yielding 0 and 1-weighted Banzhaf values. Therefore, the MSR estimator is designed for < w < 1. Our proof is adapted from (Wang and Jia 2023, Theorem 4.9).
Let Up G and E [n] be fixed, and by assumption || S. r. According to the underlying sampling for {Sj), there is |Sail ~ binomial(w). Let bridge estimator defined by
1
(1 8w)
(n(
(n()).
wm SES
w I
SES3i
For simplicity, write o; di and o; instead of (1(iniow) (u dw) and (Un 8w). Plus, also have 83i = Sail and 8z1 = Szyil.
First of all, we prove that [.] Φi- Suffice it to prove that (S(,, (S) = di where (S() w
if and (1 10
otherwise. For every [n]]vi
P(S
w² w0-1(1 (1 w
w0 w)n-1-s,
W
P(S) w0 w)n - (1 (lww)"- n-1-1
1 w
1 w
On the other hand, Φ, Essmmy w ( (Un() - vn((S))
Next, we prove the convergence for the MSR estimator. Since E(Øyj] inequality,
tb. by the Hoeffding's
me=
P( 6.1 2 e) 2 exx
2r
where T max(2 1, ) Assume 831 and 831 > note that 831 + 831 m, there is
16:
क. =
1
(S)
Σ (S)
$31
wm
873s
(1 - w)m
SeSg
SES
|و3i wmn|
w w)ml
wmn
(1 w ym
|891 win
|83) wym
|85/ wm/
(1 w ym
w(1
w)m
Note that the first inequality the above still holds Agi = or 83: = Since 831 ~ binomial (w:). by the Hoeffding's 's inequality, there is
2At
P([s - wml 2 A) < exx
m
13

---

Therefore, l0; -0,1- A
wm provided that |s3s wm < A. Then,
P(lé; - 0i 2 E) = P(lØ: 0:1 2 en 53i wm
< A) + P(lØ: - 2,1 2 En 2 wml 2 A)
[_22
s P((0: |7 2 é 1893 wm
< A) + exx
A
2A2
P(O: 6: 2 w(1
| wm
< A) + 2 exp
w wm
P( 11
A
2A
w(1
w)m!
exp
1 1 2exp
24
2 exp
m
wil wim 2r"
rd
2
2
2 exp
(- 2A
m
E wil wm
2A² m
S <xep
+ 2 exp
2r
where the last inequality is due to that 1 - 2 exp
24 17
2n1 if m is sufficiently large. Solving
the equation m(c- wii " 2/w 0.5| + 2, and thus its range is (2,3) provided that w E 1), which indicates c c- wi( wwl- 2
fo(1-w)m 2 yields A F(27' 4T) Specifically, 2Tw - wTw 22'
2
ra
2w So, we have 2 Cmm² where 7- w- 0.5. Eventually,
P( Φ. 2 S Texp (-Cmc²)
provided that 1 - 2exp (- 2A
S/2 equivalently m 2
log Then, C
Cme²
p( - 2112 2 +) < P( U
ld: - Φ5 2 <
5nexp
(- n
iE(n]
Solving 5n exp estimator requires
Cmc2 n
leads
m
log 5n
Eventually, we conclude that the MSR
max
log 6 Ce
Ce
n
log
5n
0
2
n
n log
g
samples (equivalently, utility evaluations) to achieve P(Ll - ø112 2 c) S 8.
Proposition 3. Under Assumption 1, there is
(S) = (S)) + II 6,2 II
6,1, for every S C [n],
iES
igs
Cov(E,) Σ ② Σ
2 ...
& E (n repetitions).
Cov(u,(S), Un (T)) = 01
(n][(SUT) (STTU
|SnT for every S,T C [n] d22
12
Proof. By Assumption 1, en E [v]] = én & .n 8 ... @ 6, such that (E:) are independent continuous random vectors in R2a that have the same covariance matrix Σ. For simplicity, we write
elnl en & En-1 & .... @ E1.
Since (A s B) & D) (AC) @ (BD), there is
(cln)) ( (cn-1ET (T ..... ...00..)).. (ETTT)
14

---

By the independence, we have
times
Cov(u.) = Cov(c!!)) =
Σ
(11)
Next, we prove the rest by induction. It is clear that it holds for n 1. Suppose holds for k >> O, i.e., ox( = E[(x(())
II
6,2
Il
61
for every S S [k],
SE
igs
Cov(ey(S), v.. (T)) o [M
((ST))
IShT for every S, S [k] 22
(12)
12
and we proceed for n k + Suppose the binary ordering for {S) sc(e is
S2 ... S2n,
then, the binary ordering for { s[(e+]] is
U (1: +1} which aligns well with e @ (E) @ E -....ee)) Thus, we have uk (S) Blu (S)
S2t, S1 U {k: + U
(13)
Thes 4, Nlgs G1 for every S 1]. On the other hand, write C(N) Cov(vk). by Eq. (11), have
cl++1] = (011 Cl
012 2 ClA
(14)
12 Cl
222 ClAI
Let S, S lk +1 be given, there are four cases in total: i) S. S [k]: ii) S g [k]; iii) S S [k].
Z 13: and iv) Z kk.. T _ [k). For the first case, combing Eqs. (13), (14) and (12), there is
( = on Cl (S,T) = oll [[++1])(SUT]] ( (SVT))((T))) |SnT]
22
The rest of the cases can be done similarly.
C Prerequisites and Proof for Theorem
To prove Theorem I, our first step is to lift each Φ(Un; P) into R² w.r.t the binary ordering. Precisely, we extend each semi-value Φp, shorthand for Φ(;; P). be semi-index Ip that maps each u Gr (for every n 2 1) into another utility function in G,,, whose matrix representations on all Gn are inductive, Then, we prove a theorem of robustness for semi-indices, which is then used to prove Theorem 1.
C.1 Extend Semi-values to Be Semi-indices
Index is another concept developed in cooperative game theory that serves as extension for value (Fujimoto et al. 2006; Grabisch and Rouhens 1999), which has also been employed in the community of machine learning (Sundararajan et al. 2020; Zhang al. 2021). Specifically, function that maps each utility function v E Gn (for every n 2 1) into another utility function in Gn- vector indexed by all subsets of [n]. In
index I is
Note that each utility function u E Gn can be viewed other words, Z is to impute contributions to all possible subsets of [n], not just to each datum in [n)]. so to account for the contributions of interactions among all data [n]. For convenience, we write I(e,. S) for the value of [(v,) indexed at S.
Notably, the axiom of recursion proposed by Grabisch and Roubens (1999) to extend the Banzhaf and Shapley values into the Banzhaf and Shapley indices, respectively. To state the axiom of recursion, need further definitions. Suppose E Gn and S C [n] are given. The restriction of on S, denoted by Us. defined by
(T) In other words, the domain 2 of v restricted be 28.
VT
(15)
Plus, let j E [n]]SS be given, the restriction of u on S in the presence of j, denoted by u is defined by
= (TU))
(16)
15

---

Uj is not the same as the one defined by Grabisch and Roubens (1999), Remark 3. The definition of Ug
which is instead vz (T) = ()) v(j), VT E S. The term -v(j) is only make vis' (0) 0. and we comment that it is not necessary for all the results therein. Moreover, this extra term will make Eq. (17) false.
1. Recursion: For every v E 9n. S _ [n] with 8 > 1, and E S, there is
I(u, [u () I(mm)),,
The axiom of recursion dictates that the contribution imputed to the subset S should be the difference of the contributions imputed to S\ ji in the presence and absence of any player E S. So, starting from [p i) Φs (vn;; P) for every un E 9 and E [n], the axiom of recursion can used to define [p("n, 8) recursively for every non-empty subsets S S [m). Particularly, the defined value of I(vn, S) is independent of the choice of j E S.
One thing that remains is to determine the contribution for the empty subset. For each semi-value Φp, we argue that should be what is stated as the axiom of empty.
2. Empty: To extend a semi-value op to be a semi-index Ip, there should be Ip(Un, 0)
Esgin Pi+l v(S) for every G. Recall that pltl So (1 - - PP(() for every
0 S 8 n.
Observe that Esch) Ps+1 = E. (3)=h 1, the imposed value for Ip(nn, 0) is just the expected value of on w.r.t. the probability distribution (p*41)sq induced by the underlying P E P. One can verify the axiom of empty consistently extends the axiom of recursion, i.e.,
Ir(u, i) Ir(vM/n 0) Ip(ym))s 8) for every v E 9n and E [n].
(17)
Definition (Semi-indices), A semi-index Ip is extended from semi-value op using the axioms of recursion and empty.
Remark 4. We can therefore extend each w-weighted Banzhaf value to be w-weighted Banzhaf index. Particularly, O-weighted Banzhaf index is exactly the Möbius transform Eq. (18), while 1-weighted Banzhaf index is instead the co-Möbius transform (Grabisch et al. 2000, Eq. (12)). In addition, extending the Shapley value and the Banzhaf value in this way will yield the Shapley interaction index and the Banzhaf interaction index presented in (Grabisch and Roubens 1999, Theorem 3).
Proposition 5 (Formulas for Semi-indices). For each semi-inde Ip, there is
Ip(Un, S)=
Σ RCIN/S
P
Asu, (R) for every Un G and S C [n]
( 1- (1- for forisje m
where DT
and AN) (R)= (-1)""u,
TCS
Proof. For simplicity, we write v instead of un. It is clear that it holds when 0 and 1. Assume holds for all S such that |S] = Let C [m] that satisfies [S] = k + 1, and some E be given, there is
Ip(Un,
Ui -Ip(y/ja Shi (p(
the axiom of recursion Σ PTt (st by inductive assumption
Σ p
R
RCIn
Σ
p (As))((RUR)) ( As).((R))
=
Σ
n+--= Asv(R).
P+ RC
Note the above reasoning is independent of the choice of i S.
16

---

The reader can also verify that each semi-index Zp satisfies the following axioms, the first three of which are often laid out for how indices should be in the fields of cooperative game theory and machine learning (Fujimoto et al. 2006; Grabisch and Roubens 1999; Sundararajan et al. 2020).
3. Linearity: Ip(a . Un Un, S) = a (un, S) + [p S) for every Cn Uh E =9 a E IR
and S S [n].
4. Dummy Interaction: S S [n] with & contains datum such that for some constant C, (T U2) = (T) + C for all 7 S [n]]i, then [p("n, S) = O.
5. Symmetry: (U, TT, TT, S) permutation и [n] and every 5 [m].
[p(u, (S)) for every utility function Un E G, every
6. Consistency: For each utility function vn E G. its extension ön+ is defined by (5) ( (n]) for every 8 C [n + 1]. Then, [p(Tn+1, [p(un: S) for every S C [n].
C.2 Interaction Transform
The concept of interaction transform is crucial to establish well-structured matrix representations for each semi-index Lp. Specifically, Definitions and 4 are inspired by (Denneberg and Grabisch 1999).
Definition 2 (Möbius Transform). The Möbius transform I is function that maps each ulility function U E Gn (for every n 2 1) into another utility function in Gn- For each en E G, we write p(vn, for the value of u(vn) indexed S _ [n]. The definition is
p(un, S) = Σ (-1) for every S [n].
un
(18)
RCS
Definition (Convolution). The convolution * u between each i E R and each u E In is defined by
())
Σ at s)u(T for every S C [n]. 2M22
(19)
In other words, each i E N2N may be seen as a function that maps each function v E Gn (for every n 2 1) into another utility function In, and thus we may write u(u) instead of i * u.
Definition (Interaction Transform). For each semi-index Ip, its interaction transform is defined to be a vector up E IR that satisfies
Ip = μ.
Proposition 6 (Interaction Transforms for Semi-indices). For each semi-index Ip, its interaction transform E R is
(r( = ff edP((t) for every i N.
(20)
Here, up(i) refers to the i-th entry of up.
Proof. Let E In given, and for simplicity, we write μi instead for u(v). For every C [n]. there
Ip(
Σ
Pot AtI-* = E
Pi+1
n-I-
Σ
u(SUM
R)
TEM
TE
RCT
Σ
Pi1 ( RU
Σ
Σ
Pi1 PHt1-"u(W)
n+1-
u(W)
RC
RCTC
2 WWWDSWWSTTCINN
Σ
Σ
(M77
ati-s Pw-stit1
H(W).
MDW2 28
We refer the reader to (Grabisch et al. 2000, Eq. (10)) for the equality Asv(T) = =ERST M(S R. used in the second equality.
17

---

Since Pk th
t) for S k I m, there is
n a+l-s
p Pw-s-it1
dP())
==0
Therefore, have
(Lo
S)
Σ m=2222
Σ mm2222
(p(w s) = for * (()))(())
C.3 Matrix Representation for Semi-indices
From now on, let 2 be ordered w.r.t. the binary ordering. Then, V, E G is vector in R²". and so is [p,), Since Ip is linear in E Gn, Ip has a matrix representation on each G..
Proposition (Matrix Representations for Semi-indices). Let 2/m) be ordered using the binary ordering, the matrix representation of semi-index Ip on In w.rt. the standard basis is
M P
B (t)dP()
where
7. repetitions
Bl = BB @ (1) oz......... 6 ()) and B (1) 1 1 1)
-1 -11
Here, @ the Kronecker product.
Proof. Since Zp = (p suffice it to find the matrix representations for both and 6p w.r.t. the standard basis in Gn.
As provided by Grabisch et al. (2000, Eq. (45)), which can be verified by induction using Eq. (13), the matrix representation for the Möbius transform on Gn w.r.t. the standard basis is
repetitions
1 win w will & will where will (1) 1
We first prove by induction that the matrix representation of ip on Gn w.r.t. the standard basis is
[' A Inl (t)dP())
T [m]
(21)
where
repetitions
A (l((1) Al @ ( ... & Al(()) and A (1) = =(1 1)
It is clear that it holds for 1. Assume holds for some k > i.e., for every llll Gk
(p (1 (
(22)
18

---

and we proceed with & + 1. Let +I E Gk+1 and S S [k: - 1] be given, there are two cases: i) $ [k] and ii) & kj. S [k], by Eq. (19),
(LP (ipx
Σ
(p(1 8)ulk 1) (T)
[+112225
Σ
1p(1
()) +
Σ up(1 s)ulk+1((T)
112T28
1x|2225
Σ 142228
lp 8) s)
|ktl|
( (T) +
Σ
lp(t (TT
by Eq. (15)
IK22225
-IT
[MM
[++
((S) +
Σ cr(t ()
by Eq. (22)
1K|2T28
-|T
[++
[[S) +
Σ
(p(r + - s)u [++1],u(++))) (2)
s))((a)
by R= T 13 and Eq. (16)
"(N)
[x]2
= - [b] |++ (1+++++++)))>>>)> + (K)
10% t. A (1)
[++1].U(++]] (S)
4(k)
by Eqs. (20), (21) and (22)
= =|T |++ - (
by Eq. (13).
The remaining case can be done in a similar fashion. After all, the matrix representation up on In.
w.r.t. the standard basis is
M p
T P
x Win)
repetitions
repetitions
A (t) & A (1) -.- & (P)(() x (will & w ... Wh))
(A A P (1) & A (wlll @ w &.... w('))dP(1
B
(1) B (1) 8 B (I)dP()
where
Bl)(t) A x w(ll.
C.4 Theorem of Robustness for Semi-indices
Definition 5 (Truncated Semi-indices). Given a semi-index Ip and a non-emply collection of subsets S C 2lmi, the truncated semi-index Ip, obtained by only retaining the values of Lp indexed by S.
Theorem 2. Under Assumption and further assune d12 min(011, 022), for every non-empty collection of subsets S 22"",, the Dirac delta distribution dw- with
011 012
w"
011 + 022 - 22
is optimal to the optimization problem
argmin det (Cov (In,s(v,.)) PEP
s.t. Cov(e,) E Σ ②
Σ (n repetitions).
Proof. The matrix representation of Ip Gn w.r.t. the standard basis is M T x win], as presented in Proposition 7. For simplicity, we write V Pmj.P = Cov(Ip(v,)), Since Ip linear in Un there is
VpJ.p= M glnl (M (M TT
(23)
19

---

Note that del (T) = det one, and thus we have
(ee((WWy) (Wlu)) 1 as they are triangular matrices with all diagonal entries being
det(M, 1,
(24)
det(V(n),)) det (!.)..
(25)
Observe that Cov(Ip,s(E,) (Un)) is just sub-matrix of (n].P. To represent such sub-matrices, for every non-empty a, S [2n], Vinj
[M]. is defined to be the sub-matrix of Vin,,p whose rows and
columns are indexed by a and 3, respectively. Plus, we write [n]. and V [n].P instead for Va
[m].
and v !2"],o [n].P respectively, Therefore, for each (v,)( there exists non-empty C [2"] such that Vi [M].P (ov((r,s(t)))
We prove by induction that for every 0, it holds that for every non-empty [2n] and for every P E P, det(Ve, (n]. 2 det(Ve [n).5...) de)(VVn).s...
For n = 1, let s = Jo td)(t), there is
(1 - s)² + 022s - 2012s(1- -) (011 + 022 - 20122) + 012 011 (011 + 022 2012)s 012 011
V Vpp==
T11 + 022 20
by which one can verify the statement by noticing that the function + 011(1 8)² 022s 2012s(1 - s) achieves its minimum at point = w". Suppose the statement holds for some kt > 0, and we proceed for k 6-+ 1.
Before proceeding with the induction, we have to explore the Kronecker structure between V [[++Ij.P and V P. By Eq. (23), and Proposition 7,
(L (1 (L)
(1)
Tn C(K)
012 [kk]
dP())
V VK+IIPP
-B(((()) (t)
x
0 ClA
T2e Ciki
(26)
x (/- (11 ((1-))((((()
(*)
B I
dP(t)
B (1)
(l)(())
Denote 1P = S ( (t)d((t. Eq. (26) can be rewritten
V [K+1IPP
P
[K]
P M
L
C
0 C(+)
M
P
[k]
L
P
[
L M [k]
P
M
C
0
Clk]
M
(27)
U
FT)
F
E
where
U = (M |k| L
M [1 - D + o kk c (L
(28)
+ ( - L [k) c (L [b) + +1 i
c
(M 1k - L |bl
F M C CiKK. K,
(29)
K = (a12 (on-on)(M (M p 1
M + (a22
(I.) !N]
(30)
E= (α1 + 022 20 V.P.P.
(31)
Our goal to simplify the expression
S = U E.
Note that E and M [6] are invertible by Eqs. (24) and (25) and that Σ is assumed to be positive
definite (and thus dCf() > 0). Observe that 01 + 022 20 > 0 by assumption, using Eqs. (23)
and (31), Eq. (29) is equal to
011 + - 2012 (M (
F=E E
20

---

which indicates that
F
E
F
K (M M1
EE
EE-
1
(M ) ))-
011
022
10
011 + 022 20
1
K
- (E(())
(11 + 022
-2
1
K K.
011 22
12
The last equality is obtained by using Eqs. (23) and (31) again. Write R M Eqs. (28) and (30), there is
-.p.
From
U on PnRR R + t2gLL cl (L 022
(L
+ C
K K- - 011) - RC R -022-
0 ) [8] cl )
+ (012- 01) -
L.
lkl RT).
Notice that
(011 + 02 2012) U K C
=00100 - 012) RC C
RC RC )
C (RRR) RT)
L c
(32)
= - o12)) (R+ (b) (RT (L
= - M [g|
c (M )T
Combining Eqs. (32) and (23), we eventually get the simplified formula for
011022 012
(33)
011 022
2012
Particularly, 01102 - of2 E is assumed to positive definite, So far so good, we are ready
to complete the induction by cases while looking into Eq. (27).
Case 1: If 12*+1]][2 C C 12 let B a [[22++]][22 [2(2))), which could be empty. Then, there is
U
(F
Va [K+1)PP =
F
(a11 + 022 20 V(LP)
Note that we can write
F
FD
(34)
where D3 is the corresponding column- matrix. It also gives that
DJ = U
(35)
Using Eqs. (33), (34) and (35), according to Lemma 2, there is
det( [[++1),P)
det ((01) + 022 - 12 12) V P).P) det (US - ( ((a1 + +02 - ((H.)) -1r
det ((011 022 12 V ()) dSt L )
072 V
det 011022
2012 |M]PP
011 002
022
where L det ((011 022 - 20 V (..p) = (on 022 - 2012)²² det(Ci by Eq. (25).
Therefore, by inductive assumption, for every P P.
011022 22
det det(Vo (11.p) Ldet
8
Tn + 022 2012
[b)PP)
(36)
> det
011022
0/2
det((V det((Vi (i+11)....
011 + 022
2012
[k1.6..)
21

---

Case 2: If 1 - a S [2 and a o 0. let B [12* and y a n B.. Note that could be empty. By Lemma 5, there
det(( + - 12)2) 2 V2-2" [k].P det det( (ve((Vitu,,e) [k+1],P) S det(V (1441)))))) det((011 + 022 - 2012) V(aP))
which implies, for every P E P,
det det((011 + 022 20
-
(V
[k+1],p) (k+t))))))))
[k].r
[k+1],P)
(0 + 022 20
det CIki)
det((o11 + 022 -20
V 2
de 8Ue [6+11.66..)
(37)
[k],6
(011 + 022
2012) del(C!
(Vet(V [.+1).5...)
The second inequality comes from the inductive assumption as well as case while the last equality due to that V [k+11,,6 is diagonal according to Lemma 7
C.5 Proof for Theorem
Theorem 1. Under Assumption I, and further assume 012 < min(an1 022), the Dirac delta
distribution d with
w 011 012
(8)
011 022 22
optimal to the problem for every n addition, the optimal solution unique if
Proof. Let L ((1), {n}), then
(p,s( = p(vn; P).
Therefore, by Theorem 2, pw is an optimal solution. For the uniqueness, it does not hold if n S 2. For example, let.
/ tdP(t) w*}
O= -
we point out that every P O is optimal if
or = 2. To see |0| > 1, for example, if 011 = 022 and 012 = 0, the probability distribution for the Shapley value lies O. Nevertheless, we prove the uniqueness follows: 1) first show that if A possesses such uniqueness, so does n 1, and 2) then demonstrate that it holds for
For the inductive part, it can be completed by reusing the induction in the proof for Theorem 2. Specifically, for case 1, let a = ([2*+))[2*)) 3 where 3 contains all indices pointing to subsets {1), (2), case 2, a contain all indices pointing to subsets (1), (2).......))) ..., and {k + 1}. the second inequality in Eq. (37) is also strict if P # 8 by using the aforementioned strict inequality in case 1.
and {k}. then the inequality in Eq. (36) is strict P o 8 On the other hand, for
To show the uniqueness for Specifically, in the induction, we focus on case 2 for k
4, it also be done by looking into the proof for Theorem 2.
3 and a = (2,3, 5, 9} that points (9, 10, , 16) in case 2. By Lemma 5, a necessary condition for the first incquality in Eq. (37) to be equal is that each col- umn of (10,
subsets (1), (2), (3) and (4). Note that ,3 [2a]] [23]
lies in span (V [4].P (2222.6).19))) We prove that this condition can only be met by 5 and thus the first inequality Eq. (36) is strict if 8w
[4].P
Regarding Eq. (23), using the fact that
VM = S B (I)P(() x dial x <I.' (IJPP()))
= {' aP(t) J B
B (i TP((s)
22

---

one can verify that (2233,3).(9) cpl for some cp E R. Therefore, meet the necessary condition, [4],5
all entries in each column of v (1..1,), should be the same. Particularly, there
[4].P
(12
[4].P
-(1o lo dP)) so 022 20 (tt) (p(s 1) (012 on)(s 1) tn)d So dP()) So pl ((s)p(()&dP(s))
where p(w)= = (0 + 022 20 + 012 011
The equation V (3).(12) [4.P
v (5),(12) 0 leads to [4),P
! -01002-0)))66 -oa))) 0.
Set g(w) (011022 - p())p since g(w) attains its minimum only at the point w", by Lemma 6, the necessary condition is met if and only if P == dwt
For the ease of the reader to verify the calculation in Theorem 1, we include below a Matlab code to help compute.
syms sigmall sigma12 sigma22 s real; Sigmal [sigmal1, sigma12; sigma12, sigma22];
B1 [1-t, t; -1, 1]; B1;
Sigma Sigmal;
for 1:3
Sigma = kron (Sigmal, Sigma); kBon Bt);
end subs t, s);
Bt*
Lisp(simplift (V (v ()))) % v-((2,8,6), Vp
(V(3,55,
Disp(Vp)) % V-((33,)), disp (simplify (Vp (vp)))))())) % v-((3), (12))_v-1 (12))
C.6 Lemmas
In this section, we provide all lemmas necessary prove Theorems 2 and Lemma 1. Suppose A is positive definite and B is positive semi-definite, there is
det A + B) > det(A)
where the equality holds if and only B 0.
Proof. Since A B A - BB $ A)A,, there det(A + B) det(A) det
A - :). By spectral decomposition, BAA = QDQ where QQ = and is
diagonal with all entries being non-negative. Then, det (I A - - 1) = det + D) > 1, and thus det(A A + B) > det
For the claim on the equality, suppose det(1 + A A 1) leads B 0.
and thus
Lemma 2. Given a positive definite matrix M E S++ that is partitioned as
Amxm
B Baxk)
M
B B
Ckxk
there is det(M) det(A - BC-'BB Cet
23

---

Proof.
A mx mm
B Baxk
BC-
0 C
I Imxm
-BC-1
Q
Q
where Q
B kxm
Ckxc
0
0kxm
1x
Lemma 3. Let M be the matrix given in Lemma 2, then
dct(M) s dct(A) dc)
Moreover, the equality holds if and only if B O.
Proof. By Lemmas 2 and I, dM) de BCCBBBB det(C) < ddet(A) det(C). Notice that the proof for Lemma 2 ensures that A BC B is positive definite.
By Lemma the equality holds if and only if BC 'B 0. Note that for a positive definite matrix C-1,x x C-lx if and only if 0. Therefore, BC- BC- 0 if and only if B 0. nT
Notation For square matrix A E m and 3 S (1,2..... m). A (a, is defined to be the sub-matrix of A by only keeping the rows and columns indexed by a and B, respectively. Plus, A [[a is abused for af)
Lemma 4. Suppose positive definite matrix M E mm is given, for every S (1, ... m. there is
det(M-'aar del(M( dct(M)
The convention is det(M[[0) = 1.
A
B
Proof.
Without loss of generality, we write M
such that M(a] C and M(a"] = A.
B
C
By Lemma 2, det(M) det(S) det(C) where S A- BC 'B.
On the other hand,
S-1 C-1 C='+C-'''S
-S- BC-
M -C- BBS-
Therefore, we have
det(M(a))
det(C) det(S-1) = det(MM det(M) det(M)
Lemma 5. For every positive definite matrix Mmxm S++, and every a, S (1,2....ml
dct(M[a (1) det n (]) S det(
The convention here (M 1. Moreover, provided that (a ( + and (a 3)N, + and w.l.ogg, write
A
B
C
M
B
T
D
E
(38)
C
E
F
A BT D) and M
D
E
such that M(a]
A necessary condition to have the equality
E
F
is that each column of C lies in span B).
Proof. Our proof adapted from (Horn and Johnson 2012, Theorem 7.8.9), by which we add necessary condition for the equality.
24

---

By Lemmas 4 and 3, there is
det (Mla n 81) det(M U 8])
= [de((=
del((Maa)) dM (M)
det(M[aaU)) de UB))
Suppose (a U a * 0 and (a U B) + 0. by Lemma the equality holds if and only
M M U( (a U = O. Using Eq. (38), one can verify that
M (aU (\aB)aa (A BG H - A
CJ H H
where G D - A
H = E B A AC C,
J= C A C
and thus the equality holds if and only C BG-
Lemma 6. Given continuous non-negative function g [0, R.+ that achieves its minimum 0 only at one point w E [0, 1), w is the unique probability measure on [0, 1] that minimizes
argmin L(P) = - g())P()).
PEP
Proof. It is clear that L(6m.)) = = inf L(P). Suffice it to prove that L(P) = 0 implies P w
Suppose P E P given such that L(P) 0. A point w [0, 1] is said to be irrelevant w.r.t. + + 1]) 0. For the sake of contradiction, suppose distinct point w 1] (w * w²) is relevant. Since gww) > g(w") = and is continuous, there exists <>> 0 such that g(8) > 0 for all s E [w-e, w c) [0. 1]. Since m inf weleweewttt)) g(s) 0
there exists > 0, P ((w
w
and w is relevant, we have
L(P)
mdP(t) = m P(w - e, w, + 0,
[w-e.w+e]n(0.1
a contradiction. So the only possible relevant point is w".
Next, we prove that P = ów.. For each 8 >> O, construct S₃ = 00, ~* 8) U [w* + 6, 1]. For each w Ss, since is irrelevant, there exists c(w) > 0 such that P(O (w c(w), c(w)) n [0, 1]. Then, {Ow. w E S3} forms an open (w.r.t. [0, 1) cover of Sg. Since
where O
S8 compact, there is finite subcover Sa Uisige Oue-- Therefore, P(Ss) < Σk P(Om.) which implies P(Ss) O. By letting 5 P(Ss) + P(O, []([w") theorem, e.g., (Durrett 2019, Theorem A.1.4), one can get P = 8w
Using the
Lemma Suppose MmJ.P ci " where M defined Proposition and Cirl E -. E (n repetitions), and assume 1 < min(on1, 022). Then, the Dirac delta distribution
011
makes the matrix V [m) diagonal. In addition, d is the unique probability distribution on [0, 1] that makes ViniP diagonal if
5w where w²
T11 022 2012
1.
Proof. Since (A 2 BC 2 D) AC BD, according to Proposition 7, for each e [0. 1].
repotitions
Vin
Bll (w)) (w))T VIIJ.o @ ViIj.... 2 ... & ViIj.
where V V11155. = (w( Pe(w).
(2(w)
C
PI(w) = 011 w)² + 022 - 20 - w),
p2( (011 + 022 2012) 012 011.
C 011 + 022 - 2012.
25

---

Using Eq. (13) (note 2(r) is ordered w.r.t. the binary ordering), by induction, one can show the (A, -h entry of Vnn.,.. dw is P1 (w) (A) (AA for every A, B S [n]. Therefore, for every off-diagonal entry of V |n),6 it must contain the term p2(w)* where k is some positive integer. Notice that p2 (2(")) O, and thus Vnl.sw. is diagonal.
Conversely, suppose that a probability distribution P on [o, 1] is given such that V Inl.P is diagonal. Then,
V [m].P = (
B Ih (=)(P())())))) C.N) ( ((
Observe that Vi),,r equals to So Blnl (t) (B (t)) (t(t) along the last column as we can prove by induction that the last row of B,, (t) contains only constants. Since B (lnl (t) (Bl (t)) can be computed recursively, one can show by induction that (nn,,((0, [m]) So p2(t)) and Vn,P((1), [n]) So dPP(t)
Set g(w) (2())" when is even and g(w) = Cp2(w)"~1 otherwise. Note that g(w) 2 0 and attains its minimum only at the point w*. By Lemma 6, it implies p= Sw.
D Experiment Settings
The datasets we use in the main paper summarized in Table 4. The logistic model used is
argmin w,5
Σ
CrossEntropy (w x b.
(x.
In the experiment of noisy label detection, the Fl-score is computed by using
2 2 E Drr is flipped and = is detected noisy]| 12 E Per is flipped)| K Drr detected noisy)]'
which is the harmonic mean of precision and recall.
D.1 Fitting Kronecker Noises
We independently sample 128 sequence 0 = So C S... [n]
a way that [S4+1 \S = for every 0 S < n. For each subset S; (0 S i < n) in a sampled sequence, v(S,) is computed using 128 random seeds. All these utility evaluations are then employed to generate an estimated covariance matrix Ò E R(*+1)x(x+1), which an estimate for a sub-matrix of the ground-truth covariance matrix of the stochasticity. Note that under Assumption 1, for every 0 S i,j <
Cov(u, Un (S,)) = 01
max(i.)) max(is) -min(ii)) min(i.)
012
22
D.2 Sampling Lift
Basically, sampling lift, which is designed for all semi-values, refers any estimators based on
ói(v; P) = Es(u, Ui) (S)) for every en E G and i E [n]
where S is sampled from [n]]i with P(S) = -p"++1-
There are two different ways sample S. One is derived from Eq. (2), For example, to estimate
the value for n E [n], the procedure is i) sample / E [0, 1] according to the underlying probability
distribution P E P: ii) let X be Bernoulli random variable such that P(X = 1) = I, and sample vector b E 1= whose entries are independently following X; and iii) define S C [x]] n by letting i S if and only if b, 1. The other way is by noticing that
b m-11 1)
(1(1; P)
ak+1
(u(SU)) v(S)) EsES:isss/o(SUU (l((SU)) v(S)]
|s|=
26

---

Table 4: summary of datasets used in this work.
Dataset
Source
MNIST (LeCun et al. 1998) FMNIST (Xiao et al. 2017)
PyTorch
PyTorch
2dplanes
bank-marketing (Moro et al. 2011)
https://wwin http:p::/www..pmmml.or//////////
bioresponse
https:://ww..oeem....
covertype
https: http::://www.opmm// org/d/150
cpu
attps://ww..opett org/d/761
credit
default (Yeh and Lien 2009)
diabetes
fraud (Dal Pozzolo et al. 2014)
/ttpp::/www.oppeml....
gas (Vergara et al. 2012)
https: http:////ww....oooooor//////////
har (Anguita et al. 2013)
https:
iris
https: http://wwwwoomm..orooooo
letter (Frey and Slate 1991)
https: http:://wwww..ommml..m htpp///l.or////6
optdigits
https://ww.oopnn org/d/28
pendigits
https: ftttp::/www.oopemml.com
phoneme
attps://www.opennll org/d/1489
pol
attps://xrv.opem//
org/d/722
satimage
https://www.opentt
org///182
segment
nttps://www.opentt org/d/36
spambase
https://www.opent
org///44
texture
https:/
http::/wwwwwwwwmm// org/d/40499
wind
petps::/www.open.tt org/a/847
where 9k = ph (1=1) for every 1 < k S n. The corresponding sampling strategy is i) sample 1glhgsnns and then ii) sample uniformly from 200|V/ subject to |S|
We comment that for the first way we do not have to calculate the distribution [e Note the implementation for { Jiskn might suffer from numerical blowup induced by (f=1), and is why Wang and Jia (2023) did not report the results of the Beta Shapley values if n > 500.
E More Experiment Results
In this section, we provide detailed figures, see Figures 4 to 10, to supplement the results reported in Tables and 2. In each figure, Ir stands for the learning rate used for that dataset. In addition, we also run experiments while setting [Drll 200, 10 percent of which is flipped. The corresponding results are presented in Figures 11 to 17.
27

---

Irw0.85
Spcamant rank correition coofh cent
1.2
comelatton confficie
1.
044
0.
0.0
Spcarman
0.2
-0.
0.0
10000000 000000000000000000 CHOCC
trs0.03
Ire0.01
Ire0
0.7
0.6
0.5
0.4
Flagore
0.1
0000000 www.orooooooooo www.ooa 20 Bolstrebte 11 Seveeeeeee RE208833
805
2dplanes
mark-nan
bioresponse
Figure 4: The first row exhibits results from the experiment of ranking consistency, while the second
row is for the experiment of noisy label detection. Each result is reported using mean and standard deviation. For noisy label detection, the Fl-score is reported over 10 random seeds. For ranking consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which 45 total.
1=00001
Sporman's rank condittto contiicott
1.0
Ir=0.02
Sparrma's cank cometation coufriient
Y=0.02
0.6
Spormant
-.44
serii-valoo
Ir=0.01
Inw0.02
In-0.02
07
0.30
20.25
0.2
0:15
62
6.1
0.8
0.
0.00
8555
semivolue
semi-value
semiivuue
covertype
cpu
default
Figure 5: The first row exhibits results from the experiment of ranking consistency, while the second is for the experiment of noisy label detection. Each result reported using and standard deviation. For noisy label detection, the F1-score is reported over 10 random seeds. For ranking consistency, the Spearman's 's rank correlation coefficient is reported over possible pairs of 10 random seeds, which is 45 in total.
28

---

Spcammnnt ronk corroation coomaione
1..0
Speamran's rank conulatin couff cent
8.G
Sparmans
0.0
00
000000000 D0 ooo.ooo to pir
semi-value
vamiivoluu
Ira0 02
Inw0.00 0.001
Ire0 0.09
0.8
0.6
3.44
0.2
6.2
63
Boistrecisle 285V S.v3aae305
gas
har
letter
Figure 6: The first row exhibits results from the experiment of ranking consistency, while the second
row is for the experiment of noisy label detection. Each result is reported using mean and standard deviation. For noisy label detection, the Fl-score is reported over 10 random seeds. For ranking consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which 45 total.
1.0
1rm0.03
Sporrman' rank condittto confiicntt
2.0
Ir=0.14
Sparran's cank conetation couffiiinnt
Y-O.OL
0.6
0.4
Sporran's
0.0
00
serri-valoo
Ir=0.03
Irw0.14
Ir=0.01
0.6
0.4
6.3
0.8
0.
00
8055E0 21 2000 20 2210
semivalue
semi-value
Semi volue
optdigits
pendigits
phoneme
Figure 7: The first row exhibits results from the experiment of ranking consistency, while the second is for the experiment of noisy label detection. Each result reported using and standard deviation. For noisy label detection, the F1-score is reported over 10 random seeds. For ranking consistency, the Spearman's 's rank correlation coefficient is reported over possible pairs of 10 random seeds, which is 45 in total.
29

---

Tr-000
1r=0001
Y-0.07
Spaamen's rank corolation coefficlent
Speaman's rank conotation confficint
0.8
6.6
0.2
8080
80858
1m-0.03
1r-0.07
0.6
077
0.
0.
62
63
0.0
pol
satimage
segment
Figure 8: The first row exhibits results from the experiment of ranking consistency, while the second row is for the experiment of noisy label detection. Each result reported using and standard deviation. For noisy label detection, the Fl Fl-score is reported over 10 random seeds. For ranking consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which 45 in total.
10
Tr-0.03
Sposraan's ant correaaion coeffiteet
Ir-0.07
Spearman's Gank comneaation couffictert
h-0.02
0.6
0.6
0.4
04
Seeamnns ent
0.0
0.0
20
fr=0.03
0.=0.07
Ir
0.8
0.7
0.7
0.6
0.6
D.5
80.4
6.3
0.2
02
0.1
01
6.
00
spambase
texture
wind
Figure 9: The first row exhibits results from the experiment of ranking consistency, while the second row is for the experiment of noisy label detection. Each result is reported using mean and standard deviation. For noisy label detection, consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which 45 in total.
Fl-score is reported over 10 random seeds. For ranking
30

---

1-w0001
F--0.2
1000rt rank comeeate coeniceee
Spearment rait coneletion eoeetie
62
64
000
F-0002
0.7
F1,00o
0.0
MNIST
FMNIST
Figure The first row exhibits results from the experiment of ranking consistency, while the second row is for the experiment of noisy label detection. Each result is reported using mean and standard deviation. For noisy label detection, the Fl-score is reported over 10 random seeds. For ranking consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which is 45 total.
Tr-000
Spearmants ant coreeation coeftcttnt
Ir-0.01
Spearman's ounk Couffictunt
10
T-35
0.8
0.6
Spoamnrs ent slon
0.6
0.0
0.0
-0.
0.0
30
fr=0.06
1r-0.01
2.40
0.5
0.5
0.4
3.30
20.4
80.00
6.2
0.10
6. 202.5550000
0.00
80
www.ttt-seeee000000 208088
555
2dplanes
bank-marketing
bioresponse
Figure II: The first row exhibits results from the experiment of ranking consistency, while the second
row is for the experiment of noisy label detection. Each result is reported using mean and standard deviation. For noisy label detection, consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which 45 in total.
F1-score is reported over 10 random seeds. For ranking
31

---

T=-002
Speamen's rank corrlation coefficiett
1.0
1r-0.06
Speaman's rank conotation coufficint
T-0.0
8.0
0.0
122
8088
80858
1--0.02
1--0.06
Ira 02
0.5
0.0
2.40
0.4
D.30
$0.00
02
0.10
0.0
0.00
85638U 888 www.B//BBBBB388888
covertype
cpu
credit
Figure The first row exhibits results from the experiment of ranking consistency, while the second row is for the experiment of noisy label detection. Each result is reported using mean and standard deviation. For noisy label detection, the Fl Fl-score is reported over 10 random seeds. For ranking consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which 45 total.
1.U
tr-053
Speamann's ant correation coemtiteet
Ir-
onn corneaation coulficertt
T-0.05
0.6
00
0.4
0.4
0.7
0.2
Spoormnns
0.0
2.4
30
1r=0.02
Ir=0.05
0.40
6.5
0.7
0.30
0.4
5.20
6.30
01
6.00
6.0
00
85
2000 5.5 5.555
default
diabetes
fraud
Figure 13: The first row exhibits results from the experiment of ranking consistency, while the second row is for the experiment of noisy label detection. Each result is reported using mean and standard deviation. For noisy label detection, consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which 45 in total.
F1-score is reported over 10 random seeds. For ranking
32

---

T2-002
Spaamen's rank corrlstion coeffiilett
1r-000 0.01
Y-0.17
1.0
Speaman's aakk conotation coufficinn
08
0.2
0.0
20353
sem
1r=0.02
1r-0.17
6.
0.8
DA
0.7
6.2
01
6.
0.0
gas
har
letter
Figure The first row exhibits results from the experiment of ranking consistency, while the second row is for the experiment of noisy label detection. Each result is reported using mean and standard deviation. For noisy label detection, the Fl Fl-score is reported over 10 random seeds. For ranking consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which is 45 in total.
T-0005
Speammn's ant corelation coefttteet
Ir-0111
Spnammnn' ont comelattonn Couffictrt
r-0.02
0.8
0.
ent ourn
0.60
0.4
04
6.2
0.2
00
0.2
fr=0.05
1rw0.11
Ir=0.02
6.7
0.6
6..4
63
6.0
optdigits
pendigits
phoneme
Figure 15: The first row exhibits results from the experiment of ranking consistency, while the second row is for the experiment of noisy label detection. Each result is reported using mean and standard deviation. For noisy label detection, consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which 45 in total.
Fl-score is reported over 10 random seeds. For ranking
33

---

1-1111
Spaamen's ratk corolation coefficient
1r-0.04
Spaaman's arkk conelation confficint
T-21
0.6
0.4
0.4
0.0
10.3
1--0.04
Im-0.]
0.2
220.4
0.0
pol
satimage
segment
Figure The first row exhibits results from the experiment of ranking consistency, while the second row is for the experiment of noisy label detection. Each result is reported using mean and standard deviation. For noisy label detection, the Fl Fl-score is reported over 10 random seeds. For ranking consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which 45 in total.
T=-002
Spoerman's ant coreeation coeftitett
2.0
Ir-0.00
Spearman's oank comneattion coaffictant
T-0.0
0.6
0.6
06
0.4
Spesmmnn annt
0.2
0.0
0.0
fr=0.02
Ir 00
Ir .4
0.8
0.8
0.2
02
6.
6.
00
spambase
texture
wind
Figure 17: The first row exhibits results from the experiment of ranking consistency, while the second row is for the experiment of noisy label detection. Each result is reported using mean and standard deviation. For noisy label detection, consistency, the Spearman's 's rank correlation coefficient is reported over all possible pairs of 10 random seeds, which 45 in total.
F1-score is reported over 10 random seeds. For ranking
34

---

Extra References
Anguita, D., A. Ghio, L. Oneto, X. Parra, J. L. Reyes-Ortiz al. (2013). "A Public Domain Dataset for Human Activity Recognition Using Smartphones". In: Esann. Vol. p.
Dal Pozzolo, A., O. Caclen, Y--. Borgne, S. Waterschoot, and Bontempi (2014), "Learned Lessons in Credit Card Fraud Detection From a Practitioner Perspective". Expert Systems with Applications, vol. 41, no. 10, pp. 4915-4928.
Denneberg, D. and M. Grabisch (1999). "Interaction Transform of Set Functions Over a Finite Set". Information Sciences, vol. 121, no. 1-2, pp. 149-170.
Durrett, R. (2019). "Probability: Theory and Examples", Vol. 49. Cambridge University Press.
Frey, P. W. and D. J. Slate (1991). "Letter Recognition Using Holland-Style Adaptive Classifiers". Machine Learning, vol. 6, pp. 161-182.
Fujimoto, K.. Kojadinovic, and J.-L. Marichal (2006). "Axiomatic Characterizations Probabilistic and Cardinal-Proohe Probabilistic Interaction Indices". Games and Economic Behavior, vol. 55, no. 1, pp. 72-99.
Grabisch, M., J.LL. Marichal, and M. Roubens (2000). "Equivalent Representations of Set Functions". Mathe- matics of Operations Revearch, vol. 25, no. 2. pp. 178-178.
Grabisch, M. and M. Roubens (1999). "An Axiomatic Approach to the Concept of Interaction Among Players in Cooperative Games". International Journal of Game Theory, vol. 28, 4, pp. 547-565.
Hom, R. and C. R. Johnson (2012). "Matrix Analysis". Cambridge University Press.
Moro, S., R. Laureano, and P. Cortez (2011). "Using Data Mining for Bank Direct Marketing: An Application of Crisp-Dm Methodology".
Sundararajan, M., K. Dhamdhere, and Agarwal (2020). "The Shapley Taylor Interaction Index". In: Interna- tional Conference on Machine Learning. PMLR, pp. 9259-9268.
Vergara, A., S. Vembu, T. Ayhan, M. A. Ryan, M. L., Homer, and R. Huerta (2012). "Chemical Gas Sensor Drift Compensation Using Classifier Ensembles". Sensors and Actuators B: Chemical, vol. 166, pp. 320-329.
Xiao, H., K. Rasul, and R. Vollgraf (2017). "Fashion-Mnist: A Novel Image Dataset for Benehmarking Machine Learning Algorithms". arXiv preprint arXiv:1708.07747.
Yeh, I.-C. and C.-h. Lien (2009). "The Comparisons of Data Mining Techniques for the Predictive Accuracy of Probability of Default Credit Card Clients". Expert Systems with Applications, vol. 36, no. 2. pp. 2473- 2480.
Zhang, H., Y. Xie, L. Zheng, D. Zhang, and Q. Zhang (2021). "Interpreting Multivariate Shapley Interactions in
DNNs". In: Proceedings of the AAAI Conference Artificial Intelligence. Vol. 35. 12, pp. 10877-10886.
35


Reviews:
[{"review_id": "9aSusooI1J", "reviewer": "Reviewer_SBfP", "summary": "The paper looks at the standard data valuation problem, in case of noisy estimation of the value of a coalition. It proposes a model of noise, Kronecker noise, and shows that under this noise a weighted Banzhaf value (with weight that depends on parameters of the noise) is semi-value that maximizes a notion of robustness. If the weight is 0.5, it is equivalent to the Banzhaf value, but it is different otherwise. The paper shows a number of experiments that illustrate this result and the efficiency of computing the weighted Banzhaf value. \n\nNote: There is a very related paper from Wang and Jia at AISTATS '23 that proposes the Banzhaf value and shows it is the most robust semi-value under a certain definition of robustness (and also proposed an efficient estimator based on the so-called maximum sample reused principle); so this submission's novelty and significance is obviously to be judged with respect to that AISTATS '23 paper. ", "questions": "- In the experimental section: my understanding is that the paper fits the covariance matrix of the Kronecker noise to the data and then adds noise to subset with this fitted matrix. Is that correct? I wonder: is the fit good at all? This is related to my earlier comment that I do not feel that Kronecker noise is necessarily a good model here (e.g., because of the too fast decrease of the variance, see above). \n\n- More generally, in many places I was not able to know what the value fonction used is how exactly noise is added in the experiments. Maybe I missed the information?\n\n- The introduction mentions robustness to human errors and attacks. I do not believe that what is proposed here can reasonably be robust to attacks, at least not to worst-case unconstrained attacks. Can the authors comment on the robustness to attacks? \n\n- Understanding Fig 1 is basically not possible because it is not written what the value is and what noise is added. Even after reading the experimental section I was not sure what is plotted on Fig 1. \n\n- Minor: In Remark 1: \\sigma_11 = \\sigma_22 is more general than isotropic.", "limitations": "Limitations are discussed in Appendix E, which is kind of hidden after 14 pages of proofs and is not referenced in the text. It'd be better to at least put a pointer in the main text. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The data valuation problem is a hot topic and moving away from the Shapley value adds interesting insights to the existing literature. In particular, considering robustness to noisy evaluation of the value function (as the paper does) is interesting. \n\nIn my opinion, the main contribution of the paper is the result of Theorem 1 that states the following: If the noise is Kronecker noise (as defined in Def 1), then the semi-value that minimizes the determinant of the semi-values covariance corresponds to a weighted Banzhaf value with weight given by (6), which depends on individual parameters of the noise. \n- To me this results is more of the type of identifying a particular kind of noise and a particular measure of robustness such that weighted Banzhaf maximizes robustness (rather than having a naturally relevant notion of noise and then showing the result), but this is already quite interesting. The notion of Kronecker noise used is somewhat general and flexible. \n- The proof is non-trivial (and very long). I was not able to follow all details. I wish the paper had included a sketch of proof to give meaningful intuition. \n- I am wondering whether this result is really specific to the data valuation problem and even if data valuation is the most relevant application. Is there any other that one could think of? \n\nThe paper shows the application of this result to the data valuation problem based on extensive experiments on synthetic and real datasets (although the real data sets are still somewhat forced to fit the Kronecker noise framework, see below). \n\nThe paper also contains another result, Proposition 2, which shows that the maximum sample reuse principle can be used to efficiently estimate the weighted Banzhaf value, but this is very incremental compared to [Wang and Jia, AISTATS '23].", "weaknesses": "I did not find the comparison to [Wang and Jia, AISTATS '23] to be perfectly clear in the paper. As the paper mentions, [Wang and Jia, AISTATS '23] have a result that states that Banzhaf maximizes robustness amongst all semi-values, which includes weighted Banzhaf. How can it be reconciled with the result of this paper that shows that in some cases a non-0.5 weighted Banzhaf is more robust? I do not believe that [Wang and Jia, AISTATS '23] assume isotopic noise (correct me if I am wrong). Is that not rather due to a different definition of robustness? It would be better if the paper was clearer about that. \n\nThe noise model introduced lacks motivation. Specifically, the noise is applied directly on the value function, but there is no attempt made to link this noise model to noise in the data. In fact, l. 169, the paper says that the covariance of $v(S)$ for a subset $S$ of size $s$ decreases like $1/C^{s}$ with $C=\\sigma_{11}/\\sigma_{22}>1$ if $\\sigma_{11} > \\sigma_{22}$. This brings two questions: \n- why is $\\sigma_{11} > \\sigma_{22}$ linked to a decreasing variance with the size of the subset? \n- why is this a good model? Sure, we expect that the variance would decrease, but no as fast as $1/C^{s}$, rather something classical like $1/\\sqrt{s}$. All that is to say that it is not clear (and even less justified in the paper) that the Kronecker noise model is relevant for the data valuation application. \n\nThe paper also lacks motivation for the specific robustness measure used (the determinant of the covariance of the values). There is a somewhat vague paragraph that explains that gaussian distributions maximize entropy for fixed covariance but why entropy and why fix covariance? Also, is it possible that the values are gaussian?\n(Side note: in this paragraph, the covariance $\\Sigma$ is generic whereas earlier it is specifically the individual one for Kronecker noise, that is confusing.)\n\nSome parts of the paper are a bit fast and unclear. For instance Proposition 2 and the comment below does not really explain what the convergence is, what the sample lift strategy is and why it is so bad here. This is not too crucial since this result is anecdotical but is frustrating for the reader. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and helpful feedback. Some comments are addressed in our global response, and below we address with the remaining ones. We have elaborated more on our proofs to ease the verification from readers. At the very beginning, we first noticed weighted Banzhaf values are special as stated in lemma 7 (while forging the framework of semi-indices using materials scattered in many cooperative game theory references), which guided us to have a guess  for theorem 1 and 2. Then, we verified them partially by running some experiments before working out their rigorous proofs. The Kronecker structure naturally suggests using induction to prove the results.\n\t\n**Q: Whether we add noises to subset with the fitted matrix and how we add noises?**\n\nA: Except for the first column of Figure 3 where we artificially added non-isotropic Gaussian noises to *deterministic* utility functions (with a fixed random seed 2023), we *did not intentionally* add noises elsewhere. \nPrecisely, each stochastic utility function $v(\\cdot)$, e.g., those used in *Figure 1*, and Tables 2 and 3, can be written as $ v(\\cdot,U) $ where $ U $ is the random seed controlling the initialization of trainable models, as well as the order of feeding data in the training phase. In other words, the randomness of stochastic utility functions *only* comes from varying $ U $, and say, $ 6 $ independent runs means we set $ U=0,1,\\dots,5 $ for each run. \nLine 675 in the supplementary demonstrates how we generate $\\hat{\\mathbf{D}} $, to which an individual covariance matrix $ \\hat{\\boldsymbol\\Sigma} $ is fitted. \nThen, the fitted $ \\hat{\\boldsymbol\\Sigma} $ is *only* used to generate the supposedly most robust weighted Banzhaf value parameterized by $ w^{*} $ according to Eq. (6), which is tagged by ''robust'' in Figure 3.\n\t\n**Q: Is the Kronecker noise a good fit?**\n\nA: We admit that the Kronecker noise is not capable of capturing all possible real noises. \nNevertheless, as shown by the last two columns in Figure 3, each $w^{*}$ obtained from the Kronecker noise fitted to the real noise is the most consistent semi-value in empirical ranking. \t\nTherefore, in these two experiment settings, it is safe to say that the Kronecker noise is a good-fit model for the underlying noises induced by stochastic training. Though the used datasets are small, the conclusions (that weighted Banzhaf values tend to be the most consistent in ranking) can still be observed empirically on larger datasets, as shown in Table 3. \n\t\n**Q: Robustness to human errors and attacks.** \n\nA: We did not consider this setting in this work as we only model the randomness from the stochasticity during training. This direction would be an interesting future work. \n\n**Q: Why is $\\sigma_{11} > \\sigma_{22}$ linked to decreasing variance with the size of the subset?**\n\nA: This is the implication from proposition 3 that gives the analytical formula for $\\mathrm{Cov}(\\boldsymbol\\epsilon) = \\mathrm{Cov}(v)$ (the covariance matrix) given that $\\boldsymbol\\epsilon=v-\\mathbb{E}[v]$ follows some Kronecker noise. In other words, $\\mathrm{Var}[v(S)] = \\sigma_{11}^{n-s}\\sigma_{22}^s$. As $s$ increases,  $\\mathrm{Var}[v(S)]$ decreases provided that $\\sigma_{11}>\\sigma_{22}$.\n\n**Q: Details on the sampling lift.**\n\nA: As dubbed by Moehle et al. (2022), sampling lift refers to any approximation based on $\\phi_i(v) = \\underset{S\\subseteq[n]\\backslash i}{E} [v(S\\cup i)-v(S)]$. Precisely, Eq (1) is equal to$$\\phi_i(v)=\\sum_{k=0}^{n-1}q_k \\sum_{S \\subseteq[n]\\backslash i,|S|=k}\\binom{n-1}{k}^{-1}(v(S\\cup i)-v(S))=\\underset{k}{E}\\underset{S:|S|=k,i\\not\\in S}{E}[v(S\\cup i)-v(S)].$$ where $q_k=p^{n-1}_{k}\\binom{n-1}{k} $. The sampling strategy used in (Moehle et al. 2022) is i) sample $k\\sim(q_k)$, and then ii) sample $S$ uniformly subject to $|S|=k$ and $i\\not\\in S$.\nFor the reweighted sampling lift used by Kwon and Zou (2022), they consider reweighted marginal contributions $q_s n(v(S\\cup i)-v(S))$ instead. A drawback is that $q_k$ has to be calculated cleverly to avoid the numerical blowup induced by $\\binom{n-1}{k}$, which is why Wang and Jia (2023) did not provide results for Beta Shapley on >500-data datasets.\nNevertheless, we noted that there is a better way briefly mentioned by Dubey et al. (1981). Substituting Eq (2) in Eq (1) yields$$\\phi_i(v)=\\int_0^1\\underset{S\\subseteq[n]\\backslash i}{\\sum}t^s(1-t)^{n-1-s}(v(S\\cup i)-v(S))dP(t).$$ Subsequently, take $\\phi_n(v)$ as an example: i) sample $t\\in[0,1]$ according to the provided $P$; ii) let $X$ be a Bernoulli random variable such that $P(X=1)=t $, and sample a vector $b\\in R^{n-1} $ whose entries are independently following $X$;\nand iii) define $S\\subseteq[n]\\backslash n$ by letting $i\\in S$ if and only if $b_i=1$.\nFor Beta Shapley, $ t\\propto t^{\\beta-1}(1-t)^{\\alpha-1}$, as shown in Table 1.\n\n**Q: Why sampling lift is bad?**\n\nA: To answer, we generalize the convergence results in (Wang and Jia, 2023) by assuming that the given utility function $v$ satisfies $ |v|\\leq r $. Wang and Jia (2023) analyzed the setting $v\\in[0,1]$ where $v$ was taken to be prediction performance.\nTo describe rate of convergence, we need the concept of $(\\epsilon,\\delta)$-approximation for the considered semi-value $\\phi$, which is $P[||\\hat{\\phi}-\\phi||\\_\\infty\\geq\\epsilon]\\leq\\delta$. For maximum sample reuse principle employed for all $w$-wighted Banzhaf value, adapting their proofs for theorem 4.9 gives that it requires $ \\frac{(2|w-0.5|+2)^2r^2}{2\\epsilon^2w^2(1-w)^2}\\log(\\frac{5n}{\\delta})$, or $O(\\log(n/\\delta)/\\epsilon^2)$, model evaluations to achieve an $(\\epsilon,\\delta)$-approximation. Besides, theorem 4.8 therein (though they only asserted for the Banzhaf, it applies to all semivalues) proves that it requires $ \\frac{4nr^2}{\\epsilon^2}\\log(\\frac{2n}{\\delta})$ model evaluations, or $O(n\\log(n/\\delta)/\\epsilon^2)$, for sampling lift. \nThese two results somewhat show why maximum sample reuse principle is better than sampling lift."}, {"review_id": "CzY8VwAL2d", "reviewer": "Reviewer_Zq9F", "summary": "This work focuses on data valuation with weighted Banzhaf values, which seems to be effective, particularly in cases where the dataset or the data valuation process is noisy. Toward that, the authors introduce and utilize a Kronecker noise model to calculate robust values*  and moreover to do it in an efficient way utilizing the maximum sample reuse principle. They show that the weighted Banzhaf value with the Kronecker noise model is optimal in minimizing worst-case entropy. They performed experiments to show the efficiency of the method with maximum sample reuse, validate their theoretical finding on optimality (to a certain extend), and evaluate the performance of weighted Banzhaf in capturing noisy labels and data ranking. Their results indicate that weighted Banzhaf shows consistently good performance across different tasks and datasets.\n\n*following the calculation of semi-values used for averaging contribution over subsets\n", "questions": "The points presented under the Weaknesses above can be considered as my questions here. I have the following additional questions:\n- In Table 3, are some portions of labels still flipped? My understanding was that they are not. If it's indeed so, I am curious to see F1 scores in addition to the correlation coefficients. Clarification would be appreciated.\n- How does the Kronecker noise model behave for large amounts of classes in data?\n- Also, the reproducibility is checked as n/a but I think it applies here.\n- Do you think overfitting may be an issue with this approach as semi-values are learned from data in the end? ", "limitations": "As the authors also addressed in the supplementary material, the concept of the Kronecker noise model poses certain limitations where it does not align well with the actual data noise and is empirically justified only on small datasets. I have not observed an additional limitation beyond this.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Clarity:** Overall, this paper is quite well written with clear expectations for the reader throughout. The logical flow of the paper is well-structured, although there were a few intuitive aspects that I found lacking. Nonetheless, I believe that the presentation of the work is solid.\n\n**Originality:** The concept of the Kronecker noise model, and moreover utilization of it for learning semi-values and evaluating noisy datasets are original, as far as my knowledge extends. \n\n**Quality:** I think this paper meets the quality standards starting from the introduction of the noise model and weighted version of Banzhaf indexing, to the argumentation of their optimality, and the extensive experimental evaluations.\n\n**Significance:** I believe it is crucial to align game-theoretical data valuation approaches and compare their strengths and weaknesses across different scenarios, including noisy settings. As emphasized by the authors, no universal approach can really be deemed optimal for all datasets and noise settings. However, the flexibility offered by weighted Banzhaf (or data-driven? semi-values) is promising, opening up avenues for future research in understanding the optimality of data-valuation approaches across different regimes. I find the contribution of this work to be significant in this regard.", "weaknesses": "I believe there is room for improvement regarding the justification of the Kronecker noise model and its implications for data valuation. It would be helpful to provide further explanations and clarifications on the following points:\n- Intuition behind the Kronecker model and the scenarios where it is (not) applicable.\n- In addition to discussing the universality of an approach or lack thereof, I believe it is important to draw conclusions or insights from the comparisons. For example, for a reader like me, it is not immediately clear why the proposed method is challenged by other approaches in particular in Table 2, and how this performance comparison is affected by the intrinsic dynamics in the data (such as higher-order interactions, which is generally captured best by Shapley value).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed review and feedback. Please refer to our global response for clarification on our context. We will release our code after acceptance to ease the replication of all our results. Below we address other specific comments.\n\n**Q: How does the Kronecker noise model behave for large amounts of classes in data?**\n\nA: Intuitively, more classes requires more training data to produce non-trivial trained models that can distinguish noisy and clean data well. We do not think the Kronecker noise would be a good fit for all possible induced noises on large datasets. Specifically, \nif we plot $\\det(Cov(\\phi_{\\delta_w}(v)))$ (the correct objective in theorem 1) along $w$-axis (parameter for weighted banzhaf values), the curve is always a U-shape, which somewhat implies it is an upside-down U-shape (peaking at one position and gradually decreasing sideways) for the curve of correlation in ranking. But empirically it is not always this case even on a 2-class dataset, see for example the 1st-row-2nd-column plot (200 data from diabetes dataset) in Figure 6 in the supplementary. Despite this, empirical evidence still supports that weighted Banzhaf values are more likely to capture the most consistent one in ranking, as shown in Table 3. \n\n**Q: Is overfitting an issue with this approach as semi-values are learned from data in the end?**\n\nA: In our context, each utility function $v$ can be written by $v(\\cdot,U)$ where $U$ represents random seed that controls the training phase. The considered randomness on $v$ is from varying $U$, and we model $\\epsilon =v-E[v]$ using the proposed Kronecker noise.\nThe empirical covariance matrix $\\hat{D}$ to which a Kronecker noise is fitted is approximated by evaluating $v(\\cdot,U)$ while varying $U$, see Line 675 in the supplementary for more details. \n*If $\\hat{D}$ is approximated well*, we do not think overfitting would be an issue as perfect match indicates that the real noise exactly follows some Kronecker noise. Concretely, for the last two column in Figure 3, the KL divergences for the learned Kronecker noises are $0.5954$ and $0.5490$ for datasets 2dplanes and cpu, respectively.\n\n**Q: In Table 3, are some portions of labels still flipped? My understanding was that they are not. If it's indeed so, I am\ncurious to see F1 scores in addition to the correlation coefficients.**\n\nA: We did not flip any labels for Table 3, but we can provide the correlation for all the flipped datasets used in Table 2, and then report the corresponding F1-scores. In the one-page pdf attached to our global response, Table A lists all the results of ranking consistency given that 10% of data in $\\mathcal{D}_{tr}$ are flipped, and then Table B reports all the corresponding F1-scores in noisy label detection.\nThese results show that ranking consistency does not correlate strictly with the performance of noisy label detection. A sign of this can be observed in Figure 1 as the peaking position is different in each column. Despite that, weighted Banzhaf values still perform well in noisy label detection, as shown in Table 2."}, {"review_id": "D7VNBumY3o", "reviewer": "Reviewer_CJa5", "summary": "\nThis paper extends the notion of Banzhaf values to weighted Banzhaf values to improve the robustness of data ranking. The authors show under Kronecker noises, when minimizing the worse-case entropy, the most robust parameters belong to the family of weighted Banzhaf values. Similarly, as implemented in Data Banzhaf, authors use a maximum sample reuse strategy to improve sampling efficiency, as shown by juxtaposing it with other sampling techniques. The authors demonstrate the robustness of weighted Banzhaf values by comparing them with other data valuation methods over multiple datasets. Weighted Banzhaf values produce consistent data ranking. Further, the performance is presented through noisy label detection experiments.", "questions": "+ How can you ensure exact Shapley value, if each evaluation is noisy?\n\n+ Since weighted Banzhaf results are based on the best Banzhaf weights, can you also provide results for the best parameters for Beta Shapley?\n\n+ What is the time complexity and actual runtime for weighted Banzhaf value at each step?\n\n+ It would be insightful to compare weighted Banzhaf values with KNN Shapley, which does not require model training. Is the data ranking, in that case, inherently robust to noise?\n\n\n+ Typo Line 242: descent\n+ Typo Line 266: flipped\n\n\n\n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "+ The authors show the exact case when Data Banzhaf achieves highest robustness and cases when weighted Banzhaf values can achieve better robustness.\n\n+ The weighted Banzhaf values are successfully generalized from Data Banzhaf and demonstrates largest safe margin among compared data valuation methods.\n\n", "weaknesses": "+ All utility functions are set to be accuracy of simple models. Specifically, only simple models are considered, such as logistic regression models or LeNet.\n\n+ Only simple tabular and image datasets are considered.\n\n+ The sample size is also minimal, 2000 samples at most.\n\nIt seems that even though efficient sampling is employed, the current data valuation method cannot be applied in more practical settings, larger models, datasets, and sample sizes, which is due to the intractable computation of model re-trainings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the detailed review and feedback! Please refer to our global response for clarification on the context. Below we address other specific comments.\n\n**Q: How can you ensure exact Shapley value, if each evaluation is noisy?**\n\nA: To clarify, each noisy utility function $v$ can be written as $v(\\cdot,U)$ where $U$ represents the random seed determining the initialization of trainable models and the order of feeding data in the training phase. Our setting *only* considers such randomness introduced by varying $U$. On small datasets, the Shapley value of each $v(\\cdot,U)$ is exactly computed using Eq (1). \n\n**Q: What is the time complexity and actual runtime for weighted Banzhaf value at each step?**\n\nA: To answer this question, we generalize the convergence results in (Wang and Jia, 2023) by assuming that the given utility function $v$ satisfies $ |v|\\leq r $. \nWang and Jia (2023) analyzed the setting $v\\in[0,1]$ where $v$ was taken to be prediction performance.\nTo describe the complexity, we need the concept of $(\\epsilon,\\delta)$-approximation for the considered semi-value $\\phi$, which is $P[||\\hat{\\phi}-\\phi||\\_\\infty\\geq\\epsilon]\\leq\\delta$. Take Banzhaf value as an example, Wang and Jia (Theorem 4.9, 2023) proved it requires $ \\frac{32r^2}{\\epsilon^2}\\log(\\frac{5n}{\\delta})$ model evaluations to achieve an $(\\epsilon,\\delta)$-approximation based on maximum sample reuse principle. \nFor $w$-weighted Banzhaf value, mimicking their analysis by replacing Eq (52) therein by $\\tilde{\\phi}=\\frac{1}{mw}\\sum_{S\\in\\mathcal{S}\\_{\\ni i}}v(S)-\\frac{1}{m(1-w)}\\sum_{S\\in\\mathcal{S}_{\\not\\ni i}}v(S)$, we can prove that it requires $ \\frac{(2|w-0.5|+2)^2r^2}{2\\epsilon^2w^2(1-w)^2}\\log(\\frac{5n}{\\delta})$, or equivalently $O(\\frac{1}{\\epsilon^2}\\log(\\frac{n}{\\delta}))$, model evaluations to achieve an $(\\epsilon,\\delta)$-approximation. On the other hand, theorem 4.8 therein says that (though they only asserted for Banzhaf value, it applies to all semi-values) for sampling lift it requires $ \\frac{4nr^2}{\\epsilon^2}\\log(\\frac{2n}{\\delta})$, or equivalently $O(\\frac{n}{\\epsilon^2}\\log(\\frac{n}{\\delta}))$, model evaluations to achieve an $(\\epsilon,\\delta)$-approximation. These two results somewhat demonstrate why maximum sample reuse principle is better than sampling lift. For each model evaluation $v(S)$, the corresponding complexity relies on how $v$ is designed. In our experiments, the running time for $v(S)$ is $\\Theta(|S|)$ as we employed one-epoch learning with SGD. Therefore, for $w$-weighted Banzhaf value, our proposed approximation runs faster as $w$ gets smaller, because it samples more frequently small-size subsets. We will add this discussion in the supplementary.\n\n**Q: Compare weighted Banzhaf values with KNN Shapley.**\n\nA: For value-based data valuation methods, there are two key components: i) the design of utility functions and ii) which semi-value to aggregate marginal contributions. \nKNN Shapley is composed of i) using the performance of KNN as utility functions, which are *deterministic* as no training is required, and ii) use the Shapley value to do aggregation.\nIn our context, each utility function $v$ measures the performance of models trained using SGD. Thus, $v$ is *stochastic* and can be represented by $v(\\cdot,U)$ where $U$ is random seed determining the training procedure. The Kronecker noise is to model $\\epsilon=v-E[v] $ where the randomness is from varying $U$.  To conclude, KNN does not lie in our scope as the produced $v$ is *deterministic.*\n\n**Q: The best results and parameters for Beta Shapley.**\n\nA: For Beta$(\\alpha,\\beta)$, the range of $\\alpha$ or $\\beta$ is $(0,\\infty)$, and thus it is impossible to have an extensive search. The parameters we used are all the ones reported by the original paper. Nevertheless, we experimented over all $(\\alpha,\\beta)\\in[16]\\times[16]$, which leads to 256 combinations in total. By contrast, the best weighted Banzhaf value is selected among 21 candidates. We report on as many datasets as time permits. Specifically, all the results are reported with 10% of data in $\\mathcal{D}_{tr}$ flipped, and the other settings remain the same. Note that when they achieve the same performance in noisy label detection, weighted Banzhaf values have the smallest variance across different runs (i.e., different random seeds used for training).\n#### Ranking consistency\nDataset|Weighted Banzhaf|Beta Shapley \n---|---|---\n2dplanes|0.50:**0.868**$\\pm$0.035|(8,8):0.851$\\pm$0.038 \nbank-marketing|0.35:**0.924**$\\pm$0.030|(1,1):0.918$\\pm$0.025 \nbioresponse|0.10:**0.969**$\\pm$0.008|(10,2):0.944$\\pm$0.019 \ncovertype|0.50:**0.811**$\\pm$0.082|(1,1):0.806$\\pm$0.074 \ncpu|0.00:0.874$\\pm$0.065|(16,1):**0.883**$\\pm$0.078 \ndefault|0.05:**0.986**$\\pm$0.002|(16,1):0.978$\\pm$0.004 \ngas|0.05:**0.952**$\\pm$0.008|(16,2):0.886$\\pm$0.023 \nletter|0.35:**0.711**$\\pm$0.058|(5,3):0.700$\\pm$0.051\nfraud|0.00:0.910$\\pm$0.019|(16,1):**0.923**$\\pm$0.011  \npol|0.10:**0.949**$\\pm$0.013|(16,3):0.945$\\pm$0.010\n#### Noisy label detection\nDataset|Weighted Banzhaf|Beta Shapley \n---|---|---\n2dplanes|0.10:0.517$\\pm$0.047|(13,3):**0.542**$\\pm$0.098\nbank-marketing|0.20:**0.325**$\\pm$**0.025**|(4,1):**0.325**$\\pm$0.056\nbioresponse|0.55:**0.358**$\\pm$**0.034**|(3,4):**0.358**$\\pm$0.053\ncovertype|0.05:**0.483**$\\pm$0.055|(13,1):0.442$\\pm$0.034\ncpu|0.05:**0.667**$\\pm$**0.047**|(10,1):**0.667**$\\pm$0.055\ndefault|0.10:**0.342**$\\pm$**0.019**|(7,2):**0.342**$\\pm$0.034\ngas|0.15:**0.550**$\\pm$0.065|(2,1):0.525$\\pm$0.038\nletter|0.20:0.383$\\pm$0.047|(13,5):**0.392**$\\pm$0.053\nfraud|0.05:**0.792**$\\pm$0.019|(9,2):0.783$\\pm$0.055\npol|0.10:**0.558**$\\pm$0.034|(12,1):0.525$\\pm$0.069"}, {"review_id": "7nNmW257X9", "reviewer": "Reviewer_WZtW", "summary": "The paper proposes that 1) the semi-values obtained from fitting Kronecker noise to the data robustly rank data more consistently across runs and 2) we can efficiently estimate these weighted Banzhaf values with the maximum sample reuse principle. The extensive experiments illustrated the advantages of the contributions: higher sample efficiency and performance in noisy label detection and rank consistency.", "questions": "Q1. Is the definition of robustness in this paper the same as Data Banzhaf?\n\nQ2. Does the estimation according to Line 134/equation 1 get significantly less inaccurate as $w$ tends to 0 or 1? One of the terms will have much fewer samples.\n\nQ3. Does Kronecker Noise mean Gaussian noise with Kronecker covariance?\nWhat is an intuitive interpretation of each entry in $X_i$ and $\\Sigma$? How is $X_i$ related to $v$? Provide further explanation/citations on the suitability of Kronecker noise (less parameters to fit?) and why $\\sigma_{22} < \\sigma_{11}$.\n\nMy guess is that $X_i \\sim \\mathcal{N}(0, \\Sigma =\\begin{pmatrix} \\sigma_{11}\\  \\sigma_{12}\\\\\\\\ \\sigma_{21}\\   \\sigma_{22} \\end{pmatrix})$ . Instead of observing the utility function $\\bar{u} = \\begin{pmatrix} u(\\emptyset) \\\\\\\\ u(i) \\end{pmatrix}$ directly, $\\bar{u} + X_i$ is observed.\n\nIn equation 5, what is $\\phi_P$ and why is its outer product $\\Sigma$?\n\nQ4. Can you explain why Theorem 1/Remark 1 contradict Data Banzhaf? Is it due to a different notion of robustness / assumption of noise structure? Data Banzhaf approach is noise-structure agnostic as they consider users may have difficulties estimating the noise.\n\nQ5. Line 229-231 mentions that exact values are intractable on larger datasets and approximation would “draw the real noises away from following Kronecker noises”. What does the quoted part mean? Is this a problem with using Kronecker noise that limits the applicability in real use cases?\n\n**Suggestions**\n* The robustness concept should be better introduced in the introduction’s 3rd paragraph. Later, a mathematical/formal definition of the robustness concept should be included.  \nFor example, the Data Banzhaf paper explains that the stochasticity in the rankings/utilities is due to stochastic training methods. Such inconsistencies may interfere with identifying the usefulness of data. The Data Banzhaf paper gives an in-depth definition of Robustness in Sec 4. These details are missing from this paper.\n\n* The “weighted Banzhaf” and “consistency” concepts introduced here have alternative names in CGT literature: binomial semivalues and null player exclusion/hereditary property. See Domenech, M., Giménez, J. M., & Puente, M. A. (2016). Some properties for probabilistic and multinomial (probabilistic) values on cooperative games. Optimization, 65(7), 1377-1395.\n\n* In the experiments, Shapley and the Beta Shapley values are underperforming as they place large weights on the smaller/larger coalitions. I would expect Beta$(k, k)$ for large $k$ or Beta$(kp^*, k(1-p^*))$ where p* s the robust Banzhaf version to perform as well.\nThus, an alternative conclusion (instead of using binomial semivalues) is that the semivalue weights should be learnt/adaptive.\n\n* It might be possible to empirically verify that in real dataset/SGD training, training on more data leads to more or less noise in the utilities.\n\n\n\n\nMinor suggestions (not affecting score)\n* coeffient misspelling in Figure 1 caption\n* the axis tick labels in all figures are too small\n* in equation 1, s is not defined to be the size of S", "limitations": "The limitation mentioned is that there is no universally best and most robust value for all datasets. However, other limitations (e.g. the Kronecker noise assumption or complexity) should be discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. It is novel to fit noise to the data to determine the semivalue weights and important to expand beyond and compare against common data valuation methods (Shapley and Banzhaf) \n2. Extensive experiments on many datasets were performed.", "weaknesses": "The definition of robustness (and especially Sec 3.2), assumptions and limitations of the work are not sufficiently and clearly explained. More details are given in the questions and suggestions below. Incorporating the suggestions will improve the contextualization relative to prior work and make the claims more convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for pointing out our insufficient presentation for the context as well as your helpful suggestions. The suggested reference is useful, and will be added in our revision. Please view our global response for clarification, and below we address other comments, and we will polish our paper accordingly.\n\t\n**Q: Does the estimation according to Line 134/equation 1 get significantly less inaccurate as $w$ tends to 0 or 1?**\n\nA: No, it is always accurate in terms of almost-sure convergence. Precisely, let $\\hat{\\phi}^m$ (omitting the argument $v$ as the below statement holds for every utility function $v$) be the estimate for $\\phi$ using $m$ samples from the proposed sampling scheme. Specifically, $\\hat{\\phi}^1$ can be viewed as a random vector with its underlying distribution induced by the sampling scheme, and proposition 2 proves that $\\mathbb{E}[\\hat{\\phi}^1]=\\phi$. Therefore, by the law of large numbers, $\\hat{\\phi}^m\\rightarrow\\phi$ almost surely as $m\\rightarrow\\infty$. Heuristically, when $w$ tends to $0$ or $1$, the weights $p^{n-1}_s$ in Eq. (1) for those terms that receive fewer examples decreases to $0$, which means the error induced by ignoring them tends to be negligible. We will polish this part in the final version. \n\n**Q: Why $\\sigma_{11}>\\sigma_{22}$?**\n\nA: We are not sure if we understand this question correctly. Basically, We mention $\\sigma_{11}>\\sigma_{22}$ in Line 168 just to discuss a possible scenario, as supported by proposition 3, where the Kronecker noise allows for modeling decreasing variance of $v(S)$ as $|S|$ increases. We do not impose this condition in any of our results or experiments. Empirically, provided that $v$ is defined by prediction accuracy, such a decreasing variance was mostly observed (it might lift a little bit for some $|S|$ and then keep decreasing) in our experiments.\n\t\n**Q: What is $ \\phi_{P} $ and why is its outer product?**\n\nA: Let $\\phi_P(v,i)$ denotes the $i$-th entry of $\\phi_P(v)$,  substituting Eq (2) in Eq (1) yields\n$$\n\\phi_P(v, i) = \\sum_{S \\subseteq [n]\\backslash i} \\left( \\int_{0}^{1} t^{s}(1-t)^{n-1-s} \\mathrm{d}t \\right) \\left( v(S\\cup i) - v(S) \\right) .\n$$\nThe outer product in theorem 1 was a typo while we wanted to express $ \\det(\\mathrm{Cov}(\\phi_{P}(v))) $ where $ \\mathrm{Cov} $ stands for covariance matrix. We had remedied this typo in the supplementary where we proved theorem 1.\n\n**Q: What it means by Lines 229-231?**\n\nA: Thanks for pointing out that our description on this part is not that proper, and we will modify in the paper. The context is that the randomness of each noisy utility function $v$ is induced by stochastic training. Empirically, such randomness comes from varying the underlying random seed controlling the training phase. We model such randomness by assuming that $ \\boldsymbol\\epsilon = v - \\mathbb{E}[v] $ follows a Kronecker noise, by which the most robust semi-value can be derived. In other words, the randomness of $ v $ in theorem 1 is restricted to be from stochastic training. On large datasets, for each fixed random seed, $ \\phi_{P}(v) $ can only be approximated, which means there is another randomness onto $\\phi_P(v)$ brought in by the approximation procedure. In this case, these two noises of different origins get entangled on $\\phi_P(v)$ and that makes it complicated to analyze the randomness of $\\phi_P(v)$.\t\nTherefore, to fairly examine our theory, we focus on small datasets where each semi-value can be computed exactly so that there is *only one* expected randomness that is induced from stochastic training.\n\n**Q:  I would expect Beta$(k,k)$ for large $k$ or Beta$(kp^\\*,k(1-p^\\*))$ where $p^\\*$ is the robust Banzhaf version to perform as well.**\n\nA: We experiment on all $(\\alpha,\\beta)\\in[16]\\times[16]$ (256 combinations in total) for Beta Shapley, and report the best for Beta Shapley on as many datasets as time permits. All results are reported with 10% of data in $\\mathcal{D}_{tr}$ flipped, and the other settings remain the same. Note that when they achieve the same performance in noisy label detection, weighted Banzhaf values have the smallest variance across different runs (i.e., different random seeds used for training).\n#### Ranking consistency\nDataset|Weighted Banzhaf|Beta Shapley \n---|---|---\n2dplanes|0.50:**0.868**$\\pm$0.035|(8,8):0.851$\\pm$0.038 \nbank-marketing|0.35:**0.924**$\\pm$0.030|(1,1):0.918$\\pm$0.025 \nbioresponse|0.10:**0.969**$\\pm$0.008|(10,2):0.944$\\pm$0.019 \ncovertype|0.50:**0.811**$\\pm$0.082|(1,1):0.806$\\pm$0.074 \ncpu|0.00:0.874$\\pm$0.065|(16,1):**0.883**$\\pm$0.078 \ndefault|0.05:**0.986**$\\pm$0.002|(16,1):0.978$\\pm$0.004 \ngas|0.05:**0.952**$\\pm$0.008|(16,2):0.886$\\pm$0.023 \nletter|0.35:**0.711**$\\pm$0.058|(5,3):0.700$\\pm$0.051\nfraud|0.00:0.910$\\pm$0.019|(16,1):**0.923**$\\pm$0.011\npol|0.10:**0.949**$\\pm$0.013|(16,3):0.945$\\pm$0.010  \n#### Noisy label detection\nDataset|Weighted Banzhaf|Beta Shapley \n---|---|---\n2dplanes|0.10:0.517$\\pm$0.047|(13,3):**0.542**$\\pm$0.098\nbank-marketing|0.20:**0.325**$\\pm$**0.025**|(4,1):**0.325**$\\pm$0.056\nbioresponse|0.55:**0.358**$\\pm$**0.034**|(3,4):**0.358**$\\pm$0.053\ncovertype|0.05:**0.483**$\\pm$0.055|(13,1):0.442$\\pm$0.034\ncpu|0.05:**0.667**$\\pm$**0.047**|(10,1):**0.667**$\\pm$0.055\ndefault|0.10:**0.342**$\\pm$**0.019**|(7,2):**0.342**$\\pm$0.034\ngas|0.15:**0.550**$\\pm$0.065|(2,1):0.525$\\pm$0.038\nletter|0.20:0.383$\\pm$0.047|(13,5):**0.392**$\\pm$0.053\nfraud|0.05:**0.792**$\\pm$0.019|(9,2):0.783$\\pm$0.055\npol|0.10:**0.558**$\\pm$0.034|(12,1):0.525$\\pm$0.069\n\n**Q: It might be possible to empirically verify that in real dataset/SGD training, training on more data leads to more or less noise in the utilities.**\n\nA: Thanks for this suggest, we will add this type of experiment in the revision. Nevertheless, all our results are reported with standard deviation across different random seeds determining the initialization of trainable models as well as the order of feeding data, which demonstrates the randomness contained in $\\phi_P(v)$."}]

Author rebuttal:
We thank all the reviewers for the constructive feedback. Below we address the questions most reviewers are concerned with, which will be included in our revision.

**Q: Clarify the setting for theorem 1**

A: For each noisy utility function $v$, *its randomness is due to stochasticity during training.* Our assumption for this randomness is that $\epsilon=v-E[v]$ follows a Kronecker noise, i.e., $Cov(\epsilon)=\Sigma^{[n]}=\Sigma\otimes\cdots\otimes\Sigma$ (n repetitions) for some $\Sigma\in R^{2\times2}$ where $Cov$ stands for covariance matrix. Recall that $v$ is *ordered* as a vector in $R^{2^n}$ w.r.t. the binary ordering. This ordering for all subsets of $[n]$ aligns well with the Kronecker product, which is why our modeling for the noise is based on the Kronecker product. By definition 1, $\epsilon=X_1\otimes X_2\otimes\cdots\otimes X_n$ where $Cov(X_i)=\Sigma$ for each $i$ and all *continuous* random variables $X_i$ are independent. Then, $\epsilon(S)=\prod_{i\in S}X_i(2)\prod_{i\not\in S}X_i(1)$ for every $S$ (note $X_i\in R^2$). It means that $X_i(1)$ represents the randomness brought in by the absence of datum $i$, while $X_i(2)$ is the one induced by its presence. Note that $Cov(\epsilon)=Cov(v)$, and the optimization problem in theorem 1 starts from $$\underset{P\in\mathcal{P}}{\arg\min}\sup_{v\in\mathcal{G}:Cov(v)=\Sigma^{[n]}}h(\phi_P(v))$$ where $ \mathcal{P} $ contains all distributions on the interval $ [0,1] $, $ h $ is the differential entropy that measures the uncertainty of continuous random vectors, and the $ i$-th entry of $\phi_P(v)\in R^n$ is, obtained by substituting Eq (2) in Eq (1), $$\sum_{S\subseteq [n]\backslash i}(\int_0^1 t^s(1-t)^{n-1-s} dP(t))\cdot(v(S\cup i)-v(S)).$$ In a nutshell, we found a semivalue defined by $P$ that can best tolerate the largest uncertainty brought by a noise having covariance matrix $\Sigma^{[n]}$.
Since $\phi_P$ is linear, $Cov(\phi_P(v))$ is the same, denoted by $\Phi$, given any $v$ satisfying $Cov(v)=\Sigma^{[n]} $. Let $Y=\phi_P(v)$, it is known that $\sup_{Y:Cov(Y)=\Phi}h(Y)=\frac{n}{2}(1+\log(2\pi))+\frac{1}{2}\log(\det(\Phi))$, and the maximum is achieved if $\phi_P(v) $ is Gaussian. Since $\phi_P$ is linear, $\phi_P(v) $ is Gaussian if $v$ is Gaussian. Thus, we have the equivalent problem in theorem 1 (the outer product was our typo)$$\underset{P\in\mathcal{P}}{\arg\min}\det(Cov(\phi_P(v)))\text{ s.t. }Cov(v)=\Sigma^{[n]}.$$
**Q: Clarify between the concepts of Kronecker noise and safe margin.**

A: They are distinct modelings for the inherent noises. For every $p^{n-1}\in R^n$ defining a semivalue, and every $\tau>0$ (the choice of it is irrelevant to the resulting ranking for semivalues), the safe margin is$$\text{Safe}(\tau;p^{n-1})=\min_{i,j\in[n]:i\not=j}\min_{v\in\mathcal{G}:\Delta_{i,j}^{(k)}(v)\geq\tau\ \forall1\leq k\leq n-1}\min_{\hat{v}\in\mathcal{G}:D_{i,j}(v;p^{n-1})D_{i,j}(\hat{v};p^{n-1})\leq0}||v-\hat{v}||_F$$

$$\text{where }\Delta_{i,j}^{(k)}(v)=\binom{n-2}{k-1}^{-1}\sum_{|S|=k-1,S\subseteq[n]\backslash ij}[v(S\cup i)-v(S\cup j)]\text{ and }D_{i,j}(v;p^{n-1})=n(\phi_i(v;p^{n-1})-\phi_j(v;p^{n-1})),$$which means, as claimed, the safe margin is the largest noise that can be tolerated by the semivalue $\phi(\cdot;p^{n-1})$ without changing the ranking for data. It is said that $D_{i,j}(v;p^{n-1})D_{i,j}(\hat{v};p^{n-1})\leq0$ is equivalent to that $v$ and $\hat{v}$ produce different orders for data $i$ and $j$. A merit of the safe margin is that the problem is independent of any noise. In contrast, the Kronecker noise allows one to exploit the individual covariance matrix $\Sigma$, which makes it possible to derive different conclusions. In the synthetic experiments of Wang and Jia (2023), they added isotropic Gaussian noises to *deterministic* utility $v$ to support their theory (see the setting for Figure 7 therein), which also aligns with our theory. Instead, we also added non-isotropic Gaussian noises (the first column of Figure 3) to verify our theory (which reveals the Banzhaf value is not necessarily the most robust in this case). In a nutshell, more flexible modeling leads to finer results.

Meta-review: this paper considers the problem of data valuation, with the Banzhaf value concept instead of the (more classical) Shapley one. This has been done in the past already, but formalised here with the presence of noise.

This is a clear, interesting paper that all reviewers enjoyed (even though they all have comments that should be taken care of for the revised version). I recommend acceptance
Decision: Accept (poster)