Faster Approximation of Probabilistic and Distributional Values via Least Squares
Authors: Weida Li
Yaoliang Yu
Venue: ICLR 2024 poster (2024)
Keywords: data valuation
probabilistic values
approximation
distributional Shapley value
Primary area: general machine learning (i.e., none of the above)

Abstract: The family of probabilistic values, axiomatically-grounded in cooperative game theory, has recently received much attention in data valuation. However, it is often computationally expensive to compute exactly (exponential w.r.t. the number of data to valuate denoted by $n$). The existing generic estimator costs $O(n^2\log n)$ utility evaluations to achieve an $(\epsilon,\delta)$-approximation under the 2-norm, while faster estimators have been developed recently for special cases (e.g., empirically for the Shapley value and theoretically for the Banzhaf value). In this work, starting from the discovered connection between probabilistic values and least square regressions, we propose a Generic Estimator based on Least Squares (GELS) along with its variants that cost $O(n\log n)$ utility evaluations for many probabilistic values, largely extending the scope of this currently best complexity bound. Moreover, we show that each distributional value, proposed by Ghorbani et al. (2020) to alleviate the inconsistency of probabilistic values induced by using distinct databases, can also be cast as optimizing a similar least square regression. This observation leads to a theoretically-grounded framework TrELS (Training Estimators based on Least Squares) that can train estimators towards the specified distributional values without requiring any supervised signals. Particularly, the trained estimators are capable of predicting the corresponding distributional values for unseen data, largely saving the budgets required for running Monte-Carlo methods otherwise. Our experiments verify the faster convergence of GELS, and demonstrate the effectiveness of TrELS in learning distributional values. Our code is available at https://github.com/watml/fastpvalue.

Published as a conference paper at ICLR 2024
FASTER APPROXIMATION OF PROBABILISTIC AND DISTRIBUTIONAL VALUES VIA LEAST SQUARES
Weida Li
Yaoliang Yu
vidaslee@gmaill gmail com
School of Computer Science
University of Waterloo
Vector Institute yaol lngg yu@wwaterloo.ca
ABSTRACT
The family of probabilistic values, axiomatically-groundee cooperative game theory, has recently received much attention in data valuation. However, it is of- ten computationally expensive to compute exactly (exponential w.r.t. the number of data to valuate denoted by n)). The existing generic estimator costs O( log utility evaluations to achieve an (c, approxxixiiiiio under the 2-norm, while faster estimators have been developed recently for special cases (e.g.. empirically for the Shapley value and theoretically for the Banzhaf value). In this work, start- ing from the discovered connection between probabilistic values and least square regressions, we propose a Generic Estimator based on Least Squares (GELS) along with its variants that cost On log n)) utility evaluations for many probabilis- tic values, largely extending the scope of this currently best complexity bound. Moreover, we show that each distributional value, proposed by Ghorbani et al. (2020) to alleviate the inconsistency of probabilistic values induced by using dis- tinct databases, can also be cast as optimizing a similar least square regression. This observation leads to a theoretically-gronndee framework TrELS (Training Estimators based on Least Squares) that can train estimators towards the specified distributional values without requiring any supervised signals. Particularly, the trained estimators are capable of predicting the corresponding distributional val- ues for unseen data, largely saving the budgets required for running Monte-Carlo methods otherwise. Our experiments verify the faster convergence of GELS, and demonstrate the effectiveness of TrELS in learning distributional values. Our code is available at https: /ttpt/gttttttttt// com
INTRODUCTION
In cooperative game theory, the family of probabilistic values, to which the Shapley value (Shapley 1953) and the Banzhaf value (Banzhaf 1965) belong, is uniquely characterized by the axioms of linearity, dummy, monotonicity and symmetry (Weber 1977, Theorems 5 and 10). The induced formula of probabilistic values often deemed essential for data valuation methods (Kwon and Zou 2022a; Lin et al. 2022; Wang and Jia 2023), and is also proved effective in feature attribution (Jethani et al. 2022; Kwon and Zou 2022b; Lundberg and Lee 2017). Specifically, data valuation aims impute importance value to each data point in the training dataset Dty- that represents its contribution to the performance of a model trained on Dtr, and it empirically expected that models retrained without the "less valuable" data (e.g., data that assigned with importance values lower than a specified threshold) in Dr, may achieve performance gains (Ghorbani and Zou 2019).
Throughout, identify the dataset D.r with [n] (1,2, .......7 n). where Without ambiguity, for each subset S, its lower-case a is used to denote its cardinality [S], and we write S U i and SV instead of S U (i) and SY(i), respectively. Each probabilistic value can be parameterized by list of nen-negative vectors P {p" E 11),21 such that Σ (r-))p² for every 2 1, and the importance value assigned the i-th data point is computed by
Dzrl is its size.
(i(Un) = (U = Σ Ph+1 (S - (S))
scinjVi

---

Published as a conference paper at ICLR 2024
where Um 2(x]_ + R is user-specified utility function and the superseript n is to indicate its domain 2 Typically, (S) outputs the performance of chosen model trained on S S [n]. In this work, (0) denotes the performance of initialized models. Take classification tasks as an ex- ample, (S) could be the accuracy or the cross-entropy loss reported on held-out dataset perf- is obvious that computing @(*") exactly requires 2" times of evaluating the utility function U", and hence is intractable. Therefore, there has been much research devoted developing efficient estimators. To our best knowledge, there is only one family of generic estimators designed for all probabilistic values: sampling lift and its weighted variant (Kwon and Zou 2022a). Specifically, the sampling lift estimator requires O 2 log )) utility evaluations to achieve an (c, -aaaprooxnmtto (see Proposition 5 in the Appendix). We also note that Zhou et al. (2023, Lemma and Proposition 1) analyzed convergence using (e1, E2, d) apaaprooxmnttion instead where E1 and 62 account for the multiplicative and additive error, respectively.
So far, many faster estimators have been proposed for specific probabilistic values. For instance, the advent of faster estimators designed specifically for the Shapley value was witnessed (Covert and Lee 2021; Kolpaczki et al. 2023; Lundherg and Lee 2017; Zhang et al. 2023b); Wang and Jia (2023, Theorem 4.9) proved that the estimator based on their proposed maximum sample reuse (MSR) prin- ciple only requires O 2 log ) utility evaluations for the Banzhaf value, but they also demonstrated in Appendix C.2 therein that the MSR estimator does not extend to many other probabilistic values, e.g., the family of Beta Shapley values (Kwon and Zou 2022a), in which the Shapley value resides. We also notice that Lin et al. (2022) discovered a framework of unconstrained least square regres- sions that leads to an estimator for a subfamily of probabilistic values (which, however, does not include the Shapley value). All in all, it is still an open question on how to efficiently approximate other probabilistic values, e.g., the Beta Shapley values.
potential drawback of the probabilistic values is that they depend on the underlying database Drr- Using another database, the recalculated importance values could be very inconsistent with the pre- vious ones. To overcome this issue, Ghorbani et al. (2020) proposed the framework of distributional values, in which the importance value of any (unseen) data point 2 is
(1; D, w. D,;;D, U) = E
E (U(SUZ) U(S) S-
where DD is a data distribution, w E I is a probability vector and the domain of the utility function D"J. Empirically, D is replaced by T Exe 6z where B is a (large) dataset
U is 1 sampled from D (Ghorbani al. 2020). Clearly, the computational cost for the distributional values is a big hurdle for its practical deployment.
In this paper, starting from the discovered connection between probabilistic values and least squares (see Proposition 2), we develop Generic Estimator based on Least Squares (GELS) along with its variants: GELS-R and GELS-Shapley Precisely, GELS-R is approximate the ranking of proba- bilistic values, while GELS- HELS-Shapley is specific to the Shapley value. In addition, we demonstrate that each distributional value can also be cast into a similar least square regression, which serves as the theoretical ground for formulating the framework TrELS (Training Estimators based Least Squares) that can train estimators towards the specified distributional value without requiring any supervised signals. In other words, unlike Monte-Carke methods, TrELS allows the use of trained estimators for prediction. Our main contributions are summarized as follows:
1. We propose GELS and GELS-R for all probabilistic values, and prove that both of them require O log )) utility evaluations to achieve an (c, d)pppooximniiio for many probabilistic values, matching the currently best bound for special cases; see Algorithms 1 and 2. In addition, we also develop GELS- Shhpleyy in Algorithm 3 specific to the Shapely value.
2. By casting the distributional values into optimizing least square regressions, we design TrELS for training estimators towards distributional values without supervision. See Algorithm 4 and Theorem I.
3. Our experiments verify the faster convergence of GELS and GELS-R, and we also show that the distributional values can be well-learned using TrELS.
4. As minor side note, we also extend the upproximation-witheee timator, designed specifically for the Shapley value (Kolpaczki et al. 2023), to the whole family of probabilistic values. See Proposition 8 in the Appendix.
mequiring-marginll (ARM)
2

---

Published as a conference paper at ICLR 2024
2 BACKGROUND
The sampling lift estimator (Moehle et al. 2022) refers to any approximation algorithm designed according to
(((U))) = Σ P.+1 SCIn
U = E SCCM (S US)
Its weighted variant is to use ("=") (U" (S) with P(S) = = (m=-))² instead (Kwon and Zou 2022a). Particularly, they are the same for the Shapley value. As summarized in Proposition 5, the sampling lift requires 0 log )) utility evaluations to achieve an (c, approximation. Recently, Kolpaczki et al. (2023) proposed an ARM estimator specifically for the Shapley value, but we notice that it can be easily generalized for all probabilistic values. There- fore, we present the generic formula of ARM in the main paper while leaving its justification to Proposition 8 in the Appendix. The ARM estimator is to approximate by using
(C(" = -Sspttnnless (U"
(S)) Pis-Pnnnliigs (U*()
where Pttaa (S) x p for all non-empty subsets S [n] and PÄRM (S) x p=++ for all S & [n]] In addition, Lin et al. (2022) developed the average marginal effect (AME) that casts a subfamily of probabilistic values the uniquely optimal solution
arg min B[(Y X v)
vER"
where X and Y are random variables whose distribution is induced by i) sampling | ~ P where P any probability distribution on the open interval (0, 1), ii) sampling a subset _ [n] by including each data point in [n] with probability t, and iii) setting Y = (S(S) and X, t.Mp if S
Particularly, the uniquely optimal solution is just a probabilistic value parameterized by p. = fo 11 - --"= =)p=tt((tt. If is uniform, the corresponding p" is the defining the Shapley value, but Mr co, and thus AME does not work for the Shapley value.
and (1-1)Mp otherwise where Mp Ex- re--))l- Ec-p(xn-o)
On the other hand, Wang and Jia (2023) proposed the maximum sample reuse (MSR) principle which aims to find a distribution PMERR on 21n1 such that for every E [n]].
PMSH(S i S) = p" and (MSH(S i E 5) = P*++1 with which Eq. (1) can be rewritten as (U*) = Es"
Esjres(U*(SS), Specifically, PMSr is uniform over 21ml for the Banzhaf value, and Wang and Jia (2023, Theorem 4.9) showed that the resulting estimator only requires ( 3/ log ) utility evaluations. However, they also demon- strated in Appendix C.2 therein that such PMSR exists if and only if p'++1 = r7(n) p. for every 1 < 8 < n - 1 where 17()) E R, which excludes all Beta Shapley values.
recently- proopodd faster algorithm specific to the Shapley value the complement estimator (Zhang et al. 2023b) using the complement formula
1) s)! (U) ( (T(()])))),
(U")=
Σ
SCIn): iES
which was discovered half a century ago by Harsanyi (1963, Eq. (4.1)). Earlier, Lundberg and Lee (2017) proposed the kernelSHAP estimator that exploits the fact that the Shapley value SS (U") is the uniquely optimal solution to
2) -1
arg min VER"
Σ [C)[[())
(U) (V0(S))U(())))
Σ 2/
s-
(3)
Σ 02 = - - U"))),
s.t.
[m|m]
which was first discovered by Charnes et al. (1988, Theorem 4). Since it is difficult to analyze whether the kernelSHAP unbiased or not, Covert and Lee (2021, Eq. (9)) later proposed a (prov- ably) unbiased variant, and suggested that the paired sampling technique can enhance both. Very recently, Fumagalli et al. (2023, Theorem 4.5) and Zhang et al. (2023a, Eqs. (11) and (12)) simpli- fied the formula of the unbiased kern
3

---

Published as a conference paper at ICLR 2024
3 MAIN RESULTS
In this section, we first show how to efficiently estimate the ranking induced by any probabilistic value. Then, by introducing null data point we show how to turn our ranking estimator into bona fide estimator, while retaining the same efficiency for many probabilistic values. Lastly, we extend theory to unsupervised framework that trains estimators towards distributional values.
3.1 WHEN RANKING SUFFICES
Practitioners often need to screen training data before feeding them to a model, to remove outliers, low-quality data, even adversarial examples that are deemed harmful training. Data valuation a natural way to achieve this goal, i.e., only data assigned with high importance values could be considered potentially "valuable." If one has good estimate of the proportion of "valuable" data, then the relative ranking, instead of the more precise and demanding importance values, suffices. Our first results below pave the way efficiently estimate the relative ranking underlying any prob- abilistic value. Particularly, 9 {U" 2 RJ is the set that contains all possible utility functions provided there are n data to valuate.
Proposition 1. Define, for every 2 1, U E 9D and i E [n].
((1*))=R((U""
Σ m lies (S) 0g55[m]
(4)
where m -m? = p² p for every 1]. Then, for every 2 1 and U g", R(U)) and 6(U)) produce the same ranking. Precisely, R(U = x(U)) + ((U")), where 9(U²) = ; TR. As side note, it holds for any puyp" R..
We emphasize that Proposition is closely related to Proposition 2 below in the sense that they immediately imply each other; we first noticed more general version of proposition 2 that applies to all least square values (Ruiz et al. 1998, Definition 5), a broader family that includes all the ciaaiie-efffiiient-nmmaiiiiiiiii
probabilistic values; Appendix D for more details.
Proposition 2. Consider the problem
Σ m (UT(S) - Σ (CSC(n)
arg min VER
(5)
iES
its uniquely optimal solution shares the same ranking as @(U"). As side note, it holds true for any p" E Rn that produces a non-negative weight vector mn" with Σx=1 m >
Algorithm summarizes the estimator induced by Propositions I and 2. Note that for GELS-R each utility evaluation (S) can be used for updating s estimate of the specified probabilistic value. By contrast, the (weighted) sampling lift estimator spends two utility evaluations to update the estimate of only one data point.
3.2 WHEN PROBABILISTIC VALUES ARE DESIRED
Remark 1. To recover 6(U)) from R(U"), we introduce null data point labeled as n + 1 to extend each U into U²+1 such that U*+1 (S) = (S n [n]) for every S C [n+
+ 1]. Meanwhile, we construct p=+1 E 1R=+1 such that pha = p. + p-tt u+1 for every E [n]], and note that pd may contain negative weights. Proposition I demonstrates that R(T = (TT"t) g(U 1nt1 Particularly, the definition of Eq. (1) makes that Φn+1 (0++(U"*1)
11
0 and the structure P': t + pat1 leads to (U())) = (T=tttt for every E [n]. Therefore, ((t)t)) = Ru+1 (U"+)), ) and we have the recovery formula du(U)) = (.(Uttt = R₂ - Ru+1 (T*t)). This idea is summarized in Proposition 3 and Algorithm 2.
Proposition 3. The uniquely optimal solution v" to the problem
(U*(S((m)) - Σe 2
arg min
Σ
P
(6)
VERMI1
0C DC
iES
satisfies that (U*) of uh+1 for every E [n].
4

---

Published as a conference paper at ICLR 2024
Algorithm 1: GELS-R (Generic Estimator based on Least Squares for Rankings)
Input: A dataset Drr = [n] to be valuated, a utility function U E g", a weight vector
q E RR- defined by 9, = (*) (p" + +P*+1) and a total number T of samples Output: An unbiased estimate i R(")) up some scalar
Normalize q into a probability vector q + q/ Σ ==1 9e
f ---00 0 t 5-000 O
for k = 1, ....... do
Sample S E [n 1] using the probability vector q
Uniformly sample Sy from { (R _ [m] | 8k
for i Sz do 4a + 4 + and f; (1 - + ) + + (Sa)
Algorithm 2: GELS (Generic Estimator based Least Squares)
Input: A Drr = [N] to be valuated, a utility function U E g", weight vector E RR"
defined by q= (*+1) p)".. and a total number of samples
Output: An unbiased estimate Φ ((())
Introduce null datum labeled by n + 1, and extend U to U*+1
// U T²* (S)=
Obtain i E Ra+1 from Algorithm using [n + 1]. U"+1
q and
9.) P2+1) for each i [n]
11 using unnormalized q
Remark 2. For the Shapley value, since Eiein (U*) U0m)) and by Proposition I 6(U²) g(U*) we have UH ((n)) (0) Eigjn R,("") + g(U*) n, and thus g(Un) (UU((())) (0) - -Ei(nn) R, (U")). Therefore, we recover (Sh(Uz) without introducing a null data point, which is summarized in Algorithm 3.
Proposition 4. Assume that ||U/" S u for every U" E 9".1 We have the following re- sults: i) GELS requires 0 Z(m)m
c log 4) utility evaluations to achieve an (c, aappoopxxiiiainonn i.e., P(()(UU)) - ((U"))l2 2 e) S o; for GELS-R estimator, requires O <(n)m log 3) utility eval- uations instead; tii) plus, the corresponding convergence of GELS-Shaples et O log(n)² log )).
Remark 3. Appendix H presents that both r(n) and s((n) are proportional the inverse square of the average reuse rate of utility evaluations. In other words, the more estimates on average in & each utility evaluation are used to update. the more efficient GELS and GELS-R will be. Precisely, we study the asymptotic behaviors of r(n) and sc(n) for semi-values, which include all probabilistic values mentioned and whose 'P can be sunmarized by probability measure is over the closed interval [0, 1) by pd =
(1t))=ddp(())) To sum, i) the Banchaf value and the Beta Shapley values with a, 3 > 1 corresponds T(n), s(n) O(1); ti) for the Beta Shapley values with a, 3 2 1, it becomes T(n), x(n)) E (log(n))) instead: tii) particularly, k(n) E @(1) for the Shapley value (which is the Beta Shapley value with 3 = 1), which indicates GELS-R requires O log ") utility evaluations to achieve an (c, apppooooxmmtio however, we emphasize that the convergence of GELS-R and GELS- BELS-Shapley cannot be compared directly as the definition of 0) approximation does not account for multiplicative error; iv) additionally, while using the paired sampling technique, GELS- Shaspey exactly recovers unbiased KernelSHAP, and thus Proposition also proves that the convergence of unbiased KernelSHAP with the paired sampling technique is O n log(n)? log )). We refer the reader to Appendices F. and J for more details.
3.3 DISTRIBUTIONAL VALUE
We are now ready combine the previous results with the notion of distributional values Eq. (2) to establish an unsupervised framework for training estimators towards distributional values. We refer the reader to Appendix A for more details of distributional values. Such trained estimators can valuate any unseen data point sampled from the same (or close-enough) data distribution in a single forward pass, which largely saves the budgets required for running Monte-Carlo methods otherwise.
5

---

Published as a conference paper at ICLR 2024
Algorithm 3: GEE.S-hhapey (Generic Estimator based on Least Squares for the Shapley value)
Input: A Drr = [AV] to be valuated, utility function U" E g", weight vector E R=-1 defined by qs s[n-s] and total number T of samples
Output: An unbiased estimate & the Shpaley value of U
Obtain i E I2" from Algorithm using [n], U", q and T
f < A Hn-1 for each E [x]]
11 Hn-1 Em=1 110 (U"((n)) - >i=1 P:)/n
6, + Ag + O for each i [m]
As counterparts in feature attribution, Covert et al. (2023) and Jethani et al. (2022) exploited the least square regression (3) together with the additive efficient normalization proposed by Ruiz al. (1998, Definition 11) to train neural networks that can then predict the Shapley value of any unseen instance in a single forward pass.
In practice, the data distribution DD in Eq. (2) is replaced by an empirical distribution = [B]] EvEB 62 where B is sufficiently large dataset sampled by D. Substituting B for DD in Eq. (2),
observe that there exists another probability vector E R such that
(2; B, w. U) = p(2; B.W.U) =
E
E SKBB-1
( U(S)
ml
- We point out şo is more natural to analyze. If z & B, Eq. (7) is equal to calculating some probabilistic value for with the domain of utility function being 2 BU2; if E B, it produces some probabilistic value of z to some scalar, with the domain of utility function being 2
where LI represents the uniform sampling and B (R |
Theorem 1. Consider the case when B = [m] (recall that Der for) the empirical distrihutional values yp defined in Eq. (7), Let d E RT be a probability vector that satisfies de x n-s+1 Wg for every s E [m], and v* be the uniquely optimal solution to
2
arg mii VERo-1
E 5A
E (Un(SN(M)) (m))
SMB.
Σ SES
(8)
where B, = (R [n + 1] |R| = s}. There is, for every E [n].
C. (ut 1 p(i; B, u, U") where C
Wg-
n
Additionally, setting De x (,=1)=1 wa iss [m] and O otherwise such that p" defines probabilistic value, it obtained in Algorithm 2 meets that Blf:] [Ef (i; w U every E [n].
Theorem constitutes a theoretically unsupervised ground for training estimators towards distribu- tional values. Precisely, let da(x, y) be trainable model parameterized by 0: and y stands for features and label, respectively; we propose training the estimator Φo based on the specified utility function 1 9" through optimizing
Φx ui) )r
?
arg min 0,00
E
E (U*(SN(M) - dh Inties
Σ (ESN(M]
(9)
2mm]
SKB
As will be seen in the experiments, for any data point 2 & B, the trained de indeed predicts quite accurately the corresponding probabilistic value of with the domain of utility function being 2 Auu
Generally, it is impractical to train estimators using the exact distributional values, or regressing with a reasonable approximation as supervised signals, since is extremely expensive to calculate them exactly. For example, in our experiments where N = 10, 000 and m 1, 1,000, each unseen data point requires 2 >> >0000 (10,000) utility evaluations to compute exactly. Therefore, the merits of .999
training estimators through optimizing the problem (9) are clear: i) we do not have to be concerned with what the exact distributional values are, and ii) Theorem 1 guarantees that each estimator will be trained towards the exact distributional values. The outline such an unsupervised framework summarized in Algorithm 4.

---

Published as a conference paper at ICLR 2024
Algorithm 4: TrELS (Training Estimators based on Least Squares)
Input: A database Dr, (x,, vo probability vector w E R" with m < n, utility function U E g", trainable model dg with an additional trainable parameter O.. batch size Z and a total number T of batches used for training.
Compute d E IR by letting d,- n-s+lu W. for every E [m]
Normalize: d d/ d/Ex= da for / = 1, ,, T do
loss
for j = .. do
Sample 8, from [m]] according to the distribution vector d
Sample S3 uniformly from {R S [n + 1] R 85}
loss - loss + (U, n [m]) - do I Intss, - Eves;n(m) (x( wi)
loss f loss/Z
Update 0 and Φo using loss
Evaluation Phase: C (x0 20)
11 C En
EVALUATION
In this section we perform experiments to i) verify the faster convergence of Algorithms and 2, and ii) demonstrate that distributional values can be effectively predicted by trained estimators using TrELS. The classification datasets employed are from open resources, which are iris, wind (both are from OpenML), FMNIST (Xiao et al. 2017) and MNIST. For all utility functions, their outputs set to be the performance of the trained models reported on dataset Dpery disjoint from D.r- Precisely, (")()) reports the performance of the specified model trained on S S Dtr = [n]. and leave the specified model untrained for evaluating (Ø)). Without being stated explicitly, the performance of trained models is measured by classification accuracy. In addition, we fix the random seed be 2024 make all utility functions deterministic. To be computationally efficient, we adopt ame-mini-batel one-epoch learning for evaluating utility functions (Ghorbani and Zou 2019). Logistic regression is implemented for iris and wind, while LeNet (LeCun al. 1998) is employed for FMNIST and MNIST.
4.1 FASTER CONVERGENCE OF THE PROPOSED ESTIMATORS
This experiment is performed all the above-mentioned datasets. The SGD optimizer with learning rate 1.0 is employed for iris and wind, whereas we set the learning rate to be 0.1 instead for MNIST and FMNIST. To evaluate the specified probabilistic values exactly, we |Der [Dperyl = 24. All estimators are run 30 times with different random seeds, which range from 0 to 29. We compare the following benchmarks:
those designed specifically for the Shapley value, including the complement (Zhang et al. 2023b), kernelSHAP (Lundberg and Lee 2017), unbiased KernelSHAP (Covert and Lee 2021), group testing (Jia et al. 2019), and simSHAP (Zhang et al. 2023a);
those work for all probabilistic values, including the sampling lift (see Proposition 5) and its weighted variant (Kwon and Zou 2022a), and the generalized ARM (see Proposition 8);
AME (Lin et al. 2022), restricted to subfamily of probabilistic values;
MSR (Wang and Jia 2023). proposed specifically for the Banzhaf value.
The probabilistic values we consider are: i) Beta(1, which equals to the Shapley value, ii) Beta(2, 2). iii) Beta(4, 1), and iv) the Banzhaf value. Particularly, AME does not apply to Beta(4, 1) and the Shapley since both of them lead to Mp co.
'This probabilistic value is special: i) it can be derived from the best min- polynomial approximation of the Lovász extension of U (Marichal and Mathonet 2008, Corollary 19), and ii) it is uniquely characterized by of axioms proposed in multi-criteria decision making (Grabisch and Labreuche 2001, Theorem 2)

---

Published as a conference paper at ICLR 2024
GELS (ours) G2L5--hapley
GELS- (ours) sampling
kemelHHH?
group testing ARM
complemert. permutation
weighted sampling itt simSHUP
AME
unblased kemeetsive
relative difference
rolativc difference
relative difference
207
10"
10
10
#utility evaluations per datum
*utilit evalustions per datum
*utility evaluations per datur
Spearmnn correaatio
conneaatio
10
Spearmen carrelattoo
10
10rt
10
5000
10000
15000
20000
5000 10000 15200 20000
5000 10000 15000 20000
*utility evalluations
*utility evalluations per datum
*utility evalustions per datum
Shapley
Beta(2, 2)
Banzhaf
Figure Comparison of different estimators using the dataset wind. The relative difference is plotted in log scale while the Spearman correlation is in logit scale. In addition, = 1-
Remark 4. Covert and Lee (2021) proposed the paired sampling technique to enhance (unbiased) kernelSHAP, and we point out that this technique can also be employed for our methods, (weighted) sampling lift, group testing, AME, MSR and simSHAP. We only compare the plain estimators in the main paper, and experiments including the paired sampling are provided in Appendix J.
We present some the results in Figure 1, while deferring others to Appendix J. These results sup- port that GELS, GELS-R are currently among the (empirically) fastest tier in the group of generic estimators. For the Shapley value, we omit the results of GELS-R since GELS-R R and GELS-Shapley share the same ranking: GELS ShhS-ey converges significantly faster than GELS; however, GELS- Shapley may converge slower compared with the complement and kernelSHPA; notice that their faster convergence comes at cost of using (nn²) memory storage instead of ((n); precisely, the complement requires another O(n²) time complexity to aggregate all n² estimates, whereas the
kernelSHAP needs an extra ( time complexity for calculating the inverse of matrices. Banzhaf value, though GELS converges slower than MSR in terms of relative error, the performance of GELS and GELS Brankin in terms of Spearman correlation is not worse than MSR, and some- times better. For the (2ta GELS and GELS-R achieve the best. We notice that the generalized ARM almost enjoys the same empirical convergence across different experiment settings, except that it is slower than GELS-Shapley in terms of relative error.
4.2 TRAINING ESTIMATORS
In this experiment, demonstrate the effectiveness of training estimators using Algorithm 4 on FMNIST and MNIST. The corresponding results for MNIST are included in Appendix J. For the utility functions, the SGD optimizer with learning rate 0.01 and one-mini-batch one-epoch learning adopted, and we take Drrl 10, 000 and [Dpersl = 500 from the training set. LeNet is the architecture we employ
trainable estimator di., and the input of the softmax layer taken the output of óg. For training estimators, we employ the Adam optimizer (Kingma and Ba 2014) with learning rate 0.001. The batch size Z is set be 10, 000, and we randomly generate 000 batches. After these batches have all been fed into the estimators, we permute and reuse them to continue training. Therefore, we have in total 1, 000 utility evaluations per data point for training estimators.
Lastly, the probability vector w E 1,0000 we employ is w. x 3 Moreover, 200 data, denoted by Drats taken from the training dataset for selecting the best trained models. For the results in the second row of Figure 2, we report on another 200 data extracted from the test dataset, for which we refer as Drest- To sum, Dtr. Dpers, val and Dtest are all disjoint, which means Deat and Dreat are composed of unseen data. For D nat and D Drests we randomly run 600. 000 utility evaluations for each data point using Eq. (7) generate estimates of the specified distributional value, which
8

---

Published as a conference paper at ICLR 2024
10t
relative difference
Spearman correlation
0..0
empirical
10.6
zoo
1.4
specific
specific
average
average
best
20
25
10
25
20
30
10 #batccee (K)
25
30
#batches
# #batches
(k)
Monte
Spearman correlation
relative difference
TrELS-SC (ours)
0.0
TrELS-RD (ours)
10a
0.4
Monte Carlo
THELS-SC (ours)
TrELS-RD lours)
10 15
10 15 20
*utility evalustions per datum (k)
autility evaluations per datum (k)
Figure 2: i) The first row: The first plot is the empirical loss of the sampled batch, while the others present the relative distance l pliz//1yllla and the Spearman correlation between & and 3ō. & de- notes the one predicted by the estimators trained on FMNIST. The first two plots are in log scale. The label "best" reports the best one achieved by the trained estimators at each time point, whereas "specific" is the one with the random seed being O. ii) The second row: the two plots compare the performance of the estimators trained on FMNIST with the Monte-Carlo method using Eq (2). Specifically, TrELS-SC uses trained estimators that achieve the best Spearman correlation Dval. whereas RD stands for relative difference.
regarded the ground-truths s. All results are reported with mean and standard deviation using 30 different random seeds ranging from 0 to 29.
The performance curves of the estimators during training are shown in Figure 2. First of all, the increasing curve in terms of the Spearman correlation indicates that the estimators trained under TrELS are able gradually learn the exact ranking. Secondly, the decreasing curve (the best one) of the relative difference suggests that the transform C (éo (x, Φo) is essential for training!
Next, we examine the efficiency of the trained estimators by comparing them with the Monte-Carlo method based on Eq. (7). Specifically, for each random seed, the trained estimators that achieves the best performance on Deat are selected. The comparison is shown in the second row of Figure 2. As clearly shown, the Monte-Carlo methods using 20, 000 utility evaluations for each data point are still inferior to the estimators trained under our TrELS, Observe that TrELS-SC performs poorly in terms of relative difference, which is expected since the reported relative differences during training are significantly unstable.
5 CONCLUSION
In this work, we start from the least square regression to develop GELS with its variants for all probabilistic values. GELS-R is to approximate the ranking of probabilistic values, whereas GELS- Shapley is specifically designed for the Shapley value. The faster convergence of the proposed estimators theoretically guaranteed, and is also verified empirically our experiments. Besides, also demonstrate how to cast each distributional value into least square problem, making it the first-time
to train estimators towards distributional values in an unsupervised manner, the framework of which introduced as TrELS, Notably, our experiments show that the estimators trained under TrELS learn the specified distributional values quite well in terms of both relative difference and Spearman correlation. Our work significantly broadens the practicality of deploying value-based data valuation methods on rather large datasets.
ACKNOWLEDGEMENTS
We thank the reviewers and the area chair for thoughtful comments that have improved our final presentation. YY gratefully acknowledges NSERC and CIFAR for funding support.

---

Published as a conference paper at ICLR 2024
REFERENCES
Banzhaf III,,. F. (1965). "Weighted Voting Doesn't Work: Mathematical Analysis". Rutgers Law Review, vol. 19, pp. 317-343.
Charnes, A., B. Golany, M. S. Keane, and J. Rousseau (1988). "Extremal Principle Solutions of Games in Characteristic Function Form: Core, Chebychev and Shapley Value Generalizations". In: Econometrics of Planning and Efficiency, pp. 123-133.
Covert, and S.-I. Lee (2021). "Improving KernelSHAP: Practical Shapley Value Estimation Using Linear Regression". In: Proceedings of The 24th International Conference Artificial Intelli- gence and Statistics, pp. 3457-3465.
Covent, I. C., C. Kim, and S.-I. Lee (2023). "Learning Estimate Shapley Values with Vision Transformers" In: The Eleventh International Conference on Learning Representations.
Dubey, P., A. Neyman, and Weber (1981). "Value Theory without Efficiency". Mathematics of Operations Research, vol. 6, no. 1, pp. 122-128.
Fumagalli, F., M. Muschalik, Kolpaczki, E. Hüllermeier, and B. E. Hammer (2023). "SHAP- IQ: Unified Approximation of any-order Shapley Interactions". In: Thirty-sevnnth Conference Neural Information Processing Systems.
Ghorbani, A., M. Kim, and Zou (2020). "A Distributional Framework for Data Valuation". In: International Conference Machine Learning, pp. 3535-3544.
Ghorbani, A. and J. Zou (2019). "Data Shapley: Equitable Valuation of Data for Machine Learning". In: International Conference on Machine Learning, pp. 2242-2251.
Grabisch, M. and C. Labreuche (2001). "How to Improve Acts: An Alternative Representation of the Importance of Criteria in MCDC". International Journal of Uncertainty, Fuzziness and Knowledge- -Basedd Systems, vol. 9, no. 02, pp. 145-157.
Harsanyi, C. (1963). "A Simplified Bargaining Model for the N-Person Cooperative Game". In- lernational Economic Review, vol. 4, no. 2, pp. 194-220.
Jethani, N., M. Sudarshan, I. C. Covert, S.-I. Lee, and R. Ranganath (2022). "FastSHAP; Real-Time Shapley Value Estimation". In: International Conference Learning Representations.
Jia, R. et al. (2019). "Towards Efficient Data Valuation Based on the Shapley Value". : In: The 22nd International Conference Artificial Intelligence and Statistics, pp. 1167-1176.
Kingma, D. P. and J. Ba (2014). "Adam: A Method for Stochastic Optimization", In: ICLR.
Kolpaczki, P. V. Bengs, and E. Hüllermeier (2023). "Approximating the Shapley Value without Marginal Contributions". arXiv preprint arXiv:2302.00733.
Kwon, Y. and J. Zou (2022a). "Beta Shapley: A Unified and Noise-reduced Data Valuation Frame- work for Machine Learning". In: International Conference Artificial Intelligence and Statistics, pp. 8780-8802.
Kwon, Y. and Zou (2022b). "WeightedSHAP: Analyzing and Improving Shapley Based Feature Attributions". In: Advances in Neural Information Processing Systems, pp. 34363-34376.
LeCun, Y., L. Bottou, Y. Bengio, and P. Haffner (1998). "Gradient Baadidd Learning Applied to Doc- ument Recognition". Proceedings of the IEEE, vol. 86, no. 11, pp. 2278-2324.
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 on Machine Learning, pp. 13468-13504.
10

---

Published as a conference paper at ICLR 2024
Lundberg, S. M. and S.-L. Lee (2017). "A Unified Approach to Interpreting Model Predictions". In: Advances in Neural Information Processing Systems 30.
Marichal, J.-L. and P. Mathonet (2008). "Approximations of Lovász Extensions and Their Induced Interaction Index". Discrete Applied Mathematicx, vol. 156, no. 1, pp. 11-24.
Mochle, N., S. Boyd, and Ang (2022). "Portfolio Performance Attribution via Shapley Value". Journal of Investment Management, vol. 20, no. 3.
Rudin, W. (1953). "Principles of Mathematical Analysis". McGraw-Hill
Ruiz, L. M., F. Valenciano, and J. M. Zarzuelo (1998). "The Family of Least Square Values for Transferable Utility Games". Games and Economic Behavior, vol. 24, no. 1-2, pp. 109-130.
Shapley, L. S. (1953). "A Value for N-Person Games", Annals of Mathematics Studies, vol. 28, pp. 307-317.
Wang, J. and R. Jia (2023). "Data Banzhaf: A Robust Data Valuation Framework for Machine Learn- ing". In: Proceedings of The 26th International Conference Artificial Intelligence and Statis- tics.
Weber, R. (1977). "Probabilistic Values for Games". In: The Shapley Value. Essays in Honor of Lloyd S. Shapley, pp. 101-119.
Xiao, H., K. Rasul, and R. Vollgraf (2017). "Fashion-MNIST: A Novel Image Dataset for Bench- marking Machine Learning Algorithms".. arXiv preprint
Zhang, B., B. Tian, W. Zheng, J. Zhou, and J. Lu (2023a). "Exploring Unified Perspective For Fast Shapley Value Estimation" arXiv preprint
Zhang, J., Q. Sun, J. Liu, L. Xiong, J. Pei, and K. Ren (2023b). "Efficient Sampling Approaches to Shapley Value Approximation" In: ACM SIGMOD International Conference on Management of Data.
Zhou, Z., X. Xu, R. L. Sim, S. Foo, and B. K. Low (2023). "Probably Approximate Shapley Fairness with Applications in Machine Learning". In: Proceedings of the AAAI Conference Artificial Intelligence. Vol. 37. 5, pp. 5910-5918.

---

Published as a conference paper at ICLR 2024
Table of Contents
A Distributional Values
12
B Proofs for the Proposed Algorithms
13
C Proofs for Convergences
15
Least Square Values
E Generalized ARM
19
F Practical Probabilistic Values
20
G Practical Aspect of Faster Estimators for Probabilistic Values
20
H Interpretation of <(N) and 7(N) in Proposition 4
22
Asymptotic Analysis
23
J More Experiment Results
25
A
DISTRIBUTIONAL VALUES
Originally, (Ghorbani al. 2020, Definition 2.2) proposed the Distributional Shapley value defined
by
Dz U) S-DD [0(;;U,SUa)
6l(m - 1 1)!
where (<:;USSUZ)
Σ
(U(TUz) U(T)).
m!
TSS
Note that & is supposed to be the Shapley value if = E and |S| m - Then, Ghorbani et al. (2020, Theorem 2.3) proved that
v(2; D, m,
(80mm] S-IA UUSUZ) U(S)
(10)
where U refers the uniform distribution. To improve the overall running time, they suggested using a weighted sampling x [m] instead.
However, Eq. (10) holds only with an abuse of set operations. Precisely, repeated items are counted in their proof, e.g., {xr, [z (,r,,,,) y) {a,y) and (2,0, U {2, 2, =} * (2, 2). In this work, we adhere to set operations. Regarding Eq. (2), samples from D=-1 are tuples that may contain repeated items, but they are reduced to be sets.
Adhering to set operations, Eq. (10) is false. Take D + 10z + b. 160, m + 3 as an example and assume U()) O. one can verify that
5 v12; D. m, U) = = u({=)) + 54 (U([z,))) + -(())
2
(U((2,y,2)) U((z,g)))
27
E E (U(SU)) U(S) U((=)) // (U(tz,
k [m] SWDAE1
27
2 (((tz - U
+ 27
Therefore, refer Eq. (2) in accordance with set operations distributional values.
12

---

Published as a conference paper at ICLR 2024
B PROOFS FOR THE PROPOSED ALGORITHMS
Lemma 1. Let Jn E R be the all-one matrix. The matrix A aJ,, + DI, is invertible if and only if na + + and + O. Particularly, A D[ne+b] Jn + In.
Proof. Observe that the eigenvalues J, are 0 (with n independent eigenvectors) and n, and thus the eigenvalues of aJ,, + bI, are b and na + b. Therefore, aJ,, + bI, is invertible if and only b * and na + b 4 O. A priori is that A -1 admits the form of æJ + yIn. Using AA I,, we have the equation
(na + b)x + (a + b)y 1, (na + b)x + ay 0,
which leads to that b(a+to and
L
Proposition 1. Define, for every 2 1, U E G and i E [n]]
m lies (S)
(4)
BCSgim
where m (P) p P for every 1I. Then, for every 2 1 and U g", R(U)) and d(ū") produce the same ranking. Precisely, R(U") = d(U)) + g(U")),, where g(U") = ;(U",:) R. As side note, it holds for any p" R".
Proof.
(i(U)))
Σ (O"
U*(S))
SCIn]
Σ
(1"")))) Σ U(+)
(11)
sgIm]:
9[Im)
Σ
m
lies - US((S)))))))))))))))))))()) + g(Un).
Proposition Consider the problem
Σ m (U"(S) - Σ (CSC
arg min
(5)
VER
iES
its uniquely optimal solution shares the same ranking as @(U"). ) As side note, it holds true for any p" R. that produces a non-negative weight vector m with Rx-1 m. >
Proof. Let J, Raxa be the all-one matrix, and I, E Baxn the identity matrix. Since problem (5) is convex, its optimal solution can be obtained by letting its derivative equal 0, which yields
Av' =
2
n 1
where A eJn dI, with Σ
m and Σ
m²
8
(12)
and b; Σ
m (S) for every E [n].
SCin]: iES
13

---

Published as a conference paper at ICLR 2024
Specifically.
11 2
n2 1--2) 2
n1 2
71 2
d = m
+
+
m
m Σ
m
2
#=2
2=2
#=1
2
|1 11-2- 2
2
n 2
Ps
pi
P5 +
Ps
+ Pn
2
2=2
11 1
8 D = I.
By Lemma 1, A A-1 Therefore,
en+ Jn + In, which implies the uniqueness of the optimal solution.
A = b cl2
(13)
where e.+ Ex=1 by According to Eq. (4), we have b = R(U"). Therefore, v and @l
share the same ranking. Suppose we have p" E 1² with - m. > 0, then there is v
y + čl, instead where ė= e.nta E by. Since d Ex= (6-1) m 0, the factor J/ does not change the ranking of b.
n-
Proposition 3. The uniquely optimal solution v² to the problem
arg min vER=+1
Σ p. (U*(S
Σ
DCS[
iES
satisfies that dc())) = Df 2ht1 for every i [n].
Proof. For each U E g", define U² gutt by letting U (S) = UN(S [n]). Substituting
t (S) for (S (n]) in the problem (6), and reusing the Eq. (12) accordingly, we have
v ---bb
where b, Ph U- (mn) + Σ
(0" + p=+1)) (=+1))U*(SS)
(S) Vi E [n].
sqin]: iES
and bat1 = Σ
ph+1 (S)
SC(m)
Using Eq. (11), we obtain (U"") = b. bn+1 for every E [n]] Mcanwhile, by Eq. (13), we have
v* =b b + clat1 for some e IR and thus U/: on+1 = b; d,+1 = (T"))) for every i E [m]. O
Theorem 1. Consider the case when B = [m] (recall that Der = [mr) the empirical distributional values tp defined in Eq. (7). Let d R be probability vector that satisfies de x n-stl W, for
every s E [m], and v" be the uniquely optimal solution to
arg min E [m)
E
(U*(SN(M))
Σ 1/
(8)
vERa-1
where B, = (R [n + 1] [R] = x}. There is, for every E [n]]
C. C²( - v = sli;; B, w. U*) where C
Wa.
1h
Additionally, setting P. (.=,)~(w w. ifss value, î obtained in Algorithm 2 meets that Blr.] [[f = ((t; B, U") for every E [n].
[m] and 0 otherwise such that defines a probabilistic
Proof. Since U ((U)))-U* U*) = 0 i E S, for each i E [n].
Wa+1 (7)
Σ
(UT(
88
SCIN amm
= C. Σ
ast1 (U -
SCIuIV
14

---

Published as a conference paper at ICLR 2024
where Us -,=11) if E [m]] and 0 otherwise, and C Σ (--)
Wa
Eo=1 n-stlus Wg. On the other hand, the objective in the problem (8) can be rewritten as
E
de (1(3)
U
n+ (5)
Σ iES
U1
[1 asm
where Un E g--1 defined by letting U (S) = (S n [n]) for every S [n + 1]. Note (
that d, a - for every E [m]] where is scalar that makes d a probability vector. By Proposition 3, for every E [nl.
o
lo+1 (U"(SUt)- SC(n]
Σ
where G. = B (*) for every E [m] and otherwise. Suffice it to show that 9. qs for every E [m]. Note that
n2 -
1
11
1
11
= - 3 C,
8
1
1=1
and thus
Ws = 3 ( 11
4s = B a
11
8
dg = 3
11
dg G..
s-11)
8 +
For the side note, note that
L
[E[r:]
E 111)+
0. un+1
where
L
n
s
+
9s = Σ
m
n + 1) )) ( n
-1 Ws
n + 1
8
n
8
8- 1
C C'
==1
LI
C PROOFS FOR CONVERGENCES
Proposition 5. Assume that || 11 S u for every U" E Unz1 9", any estimator based on the
sampling lift strategy requires O log ") utility evaluations to achieve P((Ø(U") <(U"))]2 2
c) S
The sampling lift strategy refers to any estimator designed according to
(U")))
Σ ph+ (U* =
SCINJV
for every i E [n] as E (r= = 1. Precisely,
- (S) is random variable following certain probability distribution, denoted by P. on all subsets S C [n] Let T be the total number of samples and S = {(S), S?..... ..... ST), (S). S sg...., ST),... ...,... (S)
, ST)} be a list of T samples where each S Sy........ St are sampled from P. Then, the estimator Sy based on the sampling lift strategy is (U*) = $ D Ui) (T()) There are two slightly different implementations: i) sampling each S" independently, and ii) sampling S for some i [n], and then reusing all samples S' for every other j E [n] by swapping and j. the latter of which is our implementation. Nevertheless, the proof below works for both of them. Besides, the proof adapted from (Wang and Jia 2023, Theorem 4.8) where it is stated for the Banzhaf value. Nevertheless, point out that it applies to all probabilistic values.
Proof. For simplicity, write o d(U))) and & (((").. Fix an i E [m], since B(o.] 6i. by the Hoeffding's inequality.
Tea
P(l:: - oil 2 t) < eexp(
2u
15

---

Published as a conference paper at ICLR 2024
Then,
Te²
P(IΦ - 211 2 () - P( P 10: - dil 2 - 2n exp(
2nnu
kE(n]
Letting 5 2 2n exp( Tt. leads to T 2 2nd
log 2n Since each sample (5% Sg..... ST) invokes 5
2naa
2n utility evaluations, it requires ( log ") utility evaluations to achieve an (e, 6) apprroxiimtion
Proposition 4. Assume that ||U" I for every U" E Un>1 g". We have the following re- sults: i) GELS requires O z(m)m log 3) utility evaluations to achieve an (c, 8) appproxximation, i.e., P(II)(Um) <(U")) 2| e) à; for GELS-R estimator, requires O (((n) log $) utility eval- uations instead; tii plus, the corresponding convergence of GELS-Shapley O log(n)? log }).
e
Proof. The proof is adapted from (Wang and Jia 2023, Theorem 4.9). First, prove the conver- gence for GELS-R. Note that it is an unbiased estimator of
-1
n 5
(p_ + Piti))
R(U
(14)
Eisl (x_ +r
Let (n)
For convenience, we write {Si, .,. that contains
Σ. (pp +p++)
all sampled subsets, and 7; = KS E S i S} for every i E [n.]. For every i E [n], define
T; = (n)T
Σ
U"(S).
SES:
Then, we have
A F.l = ( (n)T
Σ U*(()
I 7(n) hn)[T((TT - -Tal.
iES
Note that this inequality |n; Fil s ア.p (n)T Til
still holds when T. 0. Since T.
binomial(T, (n)), by the Hoeffding" ss inequality, there is
P([T: (n) 2 A) < 2 expl 21
Therefore, |A (g-r,) r.| <
7 provided that - (n) < A. Since r; = = E B(S, ())
where (S, ((n)
if i S and 0 otherwise, and B|7,] Tt, using the Heoffding's inequality
again yields
>nn)TTo2
P( ral 2 0) exxp( 2u²
Therefore,
P( rel 1 (n)T] < A) + P( - ri 2 En 2T - N A)
2
24
< P( rd 2 - Tn) < A) + 2 exxp
T
VA
212
< P(7: n3 2
T. (n) < A) + 2 exp(
Tn)
T
P([ T/ 2
AA
21²
<
+ 2 2exp(
1- 2 2exp(-
24t
T
7(m)²+((
(c-
ua
)2
2cxp(
7(m)T)
24
<
2u²
2exp(
1- 1-2exp(
242 +-)
T
7(n)2T (e-
uA
2
7(JT
2A2
<3expl
) ++2 2 exp(
2n²
T
16

---

Published as a conference paper at ICLR 2024
where 1-2 exp(
) 2
24
T
3
provided that T is sufficiently large. The next step is to determine A by )
solving the equation
(T) AA
2A
which yields A >(n)Te Note that this solution 3u
2a
gives
wA
2c
0 and 24"
Tr, 9u
Besides, the inequality 1 2 exp( 24
7 > 3
7(m)
T
leads to T 2 27
lo
Eventually, we have
P( - r. 2 5 5exp( 27(n)
(15)
9n²
(log(6)2² 2y(n)==2 22 Then,
provided that T 2
2y(n)
P(Lf r112 2 S S U Frz - 2 vn ) S 5n explp
(16)
9u2n
iE(m]
Solving 5n exp(
2T(n) 9u
log bn and thus GELS-R requires W 8 leads to T 2x(n)
9u22
5
9 (lg(())u²
9u2n (2) 2y(n)222 お"
5m
0 k(n)m log 7
max(
log
utility evaluations to achieve an (e, 8) apppoxximatoonn where x(n) =(n))=
Next, we prove the convergence for GELS. For simplicity, we write & o(U") and h
Eh (==))²)) R(T"))); ); see Eq. (14). By Eq. (15), there is, for every i E [n + 1].
P((h: - hil 2 <) < 5 expp 25(m)²Te2
9u
9log(6)22 provided that T 2 27(n)=2 where F(n)
2g (," )2
Therefore, for every E [m].
Σ. ("'")p²"
P([(h-- - hntt)= (hs hn+1)1 2) P((h:
hal 1112 2 U Ulhhtt
hnt1l
E 2
5())
< 100exp(
18u2
vnn) As argued in Remark 1, t Rn+ (Tnt)) (U*) for every E [m], and thus x(n)(h; hn+1) di(Um) for every i [n). So, for every i E [n),
let (m) Et= (==))²² and n(n) = E.= (*+t) ph, and note that 7n) = x(n)
Te²
P( - 3. 2 E) = (h( hn+1)= - (hi hn+1)) 2 x(n)
S 10exp(
18u2n((n)2
Therefore,
Te
P( - -111--1112 2 2 P U 16: 0.12 -/2
S 10m exp( 18u2nm(n)²
Vn
iE|n]
Solving 8 2 10n exp(
Tta 184)nn
yields T
18u )
log 10n
To conclude, GELS requires
9 (lg( 2
18u (n)))
(n) log = 0 00- log n 5 22
10n
max
2
62
utility evaluations to achieve an (c, 8) approximation where 7(n) nnnn22 Note that 7(2)* -1 <
n(n) as x(n) = - (-=) (;=))r; E. n (--1) D. > 1.
Last, we prove the convergence for GELS- Shapley. Reusing Eq. (14), since p. (s-1][[n-s}! for the Shapley value, it is H r R(U)) where Hn-1 -n=1 (-=1) (p + p(+1) >nー1 s' By Eq. (16), there
2T Iu 1)2
P(H : || r112 2 t) & 5nexp
17

---

Published as a conference paper at ICLR 2024
provided that
9 llg(6)) 2y(m)
Note that E (' p(+1) Σ (3) 7(n 1).
For convenience, let Sh be the corresponding Shapley value. As discussed in Remark 2, Sh Hn-1 r (=*([n) (7)()) Σ. -n-1-
The procedure of casting Hn into Φ is called addirie--fficien-nmmmiiiizz (Ruiz et al. 1998, Definition 11). Particularly, we write
2 H 1+ (T((nn) ("(()) - -
71
As pointed out by Jethani et al. (2022, Appendix B), the addtivee-fficien--ommmaiiiainn is just an orthogonal projection, and therefore have
1b S 11 f- Hn-1 r 112, ||
which suggest
2T 9u2nn 1)2
P(Ilss S (122 P(I Hn-1 f- Hn-1 1/2 2 6) S 5n exp
Solving 8 5nexp
27 yields T 9u² 9u2nn(n 1)²²
log 5n 8. Since ((1) S 77(n 1),
Sa-nn
20a
we eventually have that GELS-Shapley requires O ( log }) utility evaluations to achieve an
(e, appproxximinon where T(n) = nnn)² 2 > n - 1) Note that i) for the Shapley value, .7(n)
E (*+ (++)) = Σ a[+1-=) = n
n+1
x+1-s 2Hn E log n, and thus
7nn 1) < (n)) and ii) 7(n) < nnn- 1) as 7(1) v1nn - 1) Hn-1 2 1.
D LEAST SQUARE VALUES
In this appendix, we demonstrate how we obtained proposition at very beginning without knowing proposition 1.
Definition (Least Square Values (Ruiz et al. 1998, Definition 5)). Suppose a non-new non-negative non- cero vector E R= is given, least square value E(U"; m) E R is defined be the uniquely optimal solution to the problem
- Σ Σ m
arg min VER
(CS5[m)
iES
(17)
U 1 U= (O)
Specifically, Ruiz et al. (1998, Theorem 8) developed system of axioms that uniquely characterizes the family of least square values. Moreover, its relationship with the family of probabilistic values was also revealed.
Proposition 6 (Ruiz et al. 1998, Theorem 12). For each vector of weights p" E R that satisfies E (g-)p² 1, define m E Ra-1 by letting m, 2h + ph+ there exists some function
f: R. such that
m(():mm)
Σ ScInlvi
for every U E g" and i E [n].
As proposed by Ruiz al. (1998, Definition 11), for each probabilistic value d(U"), its additive- ø defined to be
p(~) {U")) 1 (U" ((n) (0) Σ (l(T))))
18

---

Published as a conference paper at ICLR 2024
Using Proposition 6, verify that {(U : = { and f(U*) 1 ([") - Um
Eigin) (C()))). Particularly, we notice that the constraint of the problem (17) and the term (0) in the objective can be removed if it the ranking that matters.
Proposition 7. Suppose utility function U E g" and a non-negative non-zero vector E IR" are given, the uniquely optimal solution u to the problem
arg min uER"
Σ m. (S)
Σ U
(18)
OÇSCIN
satisfies that there exists some E R such that
u = E(U"; + cla.
Proof. Since the optimization problem (17) is convex, it can be solved using the KKT condition.
Specifically, by introducing dual variable E R, there is
v v - Av- vb
Σ @CSC
m. - ([))
Σ
bi)
==1
where Aij-
n- 2
s==
mm:
i i
i i= and b,
Σ
m,
Vi E [m].
ma:
ScIn]: iES
Letting its derivative equal yields
Av b + x1, and = ((nl) U" (0).
which leads to the uniquely optimal solution
1A b - (m)) + U
U² (0)
v' A- b
1n
(19)
1 A 11,
Specifically,
72
n
m2 Σ
ms
n-1
n 2) 8
2)
n-1
n1 8 8-
R-1 m, =
=m1
m,
8 s- m > 0,
s=1
by lemma 1, the existence of -1 is guaranteed. On the other hand, letting the derivative of the objective in the problem (18) equal 0 gives
A A 11n) where /. = (O) An1 Therefore, eventually have, for some e R.
u' v" + +cl, ={(U";;) +1.
for some E R.
Remark 5. To conclude, Proposition is derived from Propositions 6 and 7.
E GENERALIZED ARM
As proposed by Kolpaczki et (2023), the Shapley value can be rewritten as, for every U g" and E [n].
655((U") = E s- p Ies b (U) - Eg [E where PARAS (S) . (2) for every S St (0
ARM ligs Pinds (U)
P
S C [n]] and (S)
(n- for every S E S = (S [n]]: H >"
The estimator based this formula is called the approximation without- ritthuutrequiring megiinln estima- tor. We found that this methodology can be easily adapted for every other probabilistic value, which summarized in the below.
19

---

Published as a conference paper at ICLR 2024
Proposition 8. For every U 9 and [n].
6i(U") = BS tax (S)) - -Bs P A lies k (S)]
where PARM(() x Ps for every S E St and (S) x fot1forr every S E E
Proof. Precisely, P. a-ps and p B-ps+1 such that Eع= (") and Σ PP 1. Let St and S be the corresponding random samples from St and S respectively. Fix an i E [n]. observe that,
||st| =) P([STI =
(5)
12
P(iEst Σ PliE S+
p
11
a
Ps a.
Therefore,
P(S liESt) P(s+,i iiistt)
Q.Ps
P(i S+)
Ps
Similarly,
N-1 P(i = Σ
1
P(i $ S ||8 = 5) P(IT = = Σ
11
11
Ps
5
==0
-
3
Ps+1 B
8=0
which leads to
P(S (i$S = P(STie$S)
8 P.Ps+1
P(i B
Ps+1
F PRACTICAL PROBABILISTIC VALUES
As provided by Dubey et al. (1981), each semi-value, which is subfamily of probabilistic values, can be expressed as, for every U E G" and E [ml]
Σ (L, (111-o----dppt - SCiMjVE
Φ.(Um) c.(UU;))))
(U=(SU))-
where a is any probability measure the closed interval [o, 1]. In other words, in view of Eq. (1), there is pr = 10-111111110 (1--((1))==)
To the best of our knowledge, practical semi-values, i.e., those ever studied in the previous refer- ences, include the Banzhaf value (Wang and Jia 2023) and the Beta Shapley values with o, 2 (Kwon and Zou 2022a; Kwon and Zou 2022b). Note that Beta(1, 1) is exactly the Shapley value. For the Banzhaf value, the corresponding is the Dirac delta distribution do.s. which
leads to p. = 2 (m-11), For Beta(a, B)) the corresponding probability density function for p is r(o++) [(8+a-1Ifaat--a x (0-2(1- - -ta--, and thus p" F(a)T()) F(o+Btn-1) for Beta(1, 1), i.e., the Shapley value.
Specifically, it is p. (a- D)]
G PRACTICAL ASPECT OF FASTER ESTIMATORS FOR PROBABILISTIC VALUES
As far as we know, in feature attribution, FastSHAP is the only framework for training semi-value- based explainers (Jethani et al. 2022), which is based the least square regression Eq. (3) specific
20

---

Published as a conference paper at ICLR 2024
to the Shapley value. Recently, Kwon and Zou (2022b) showed that other candidates of the Beta Shapley values tend to perform better than the Shapley value in feature attribution. Therefore, one may ask how to cast other probabilistic values into optimization, which is answered by Proposi- tions and 3. Though AME proposed by Lin et al. (2022) provides an alternative way to achieve this goal, it is restricted to subfamily of semi-values, which does not include, e-g.. the Shapley value and Beta(4, (4 1) used in our experiments. Besides, as shown in our experiments of comparing convergences, on Beta(2, (2. 2), the induced estimator of AME does not rival our GELS-R and GELS estimators, which are derived from solving the least square regressions (5) and (6).
Recall that the optimization problem used by FastSHAP
EgEZ 2
Σ oCSSia
d-1 (dsdd (UL(S)-U((0) 150(;;))
where d is the number of features (a counterpart of n), o2; 0) E F is a trainable explainer param- eterized by 0, U_ is a utility function based on the data point (x, y) where and y represent the features and label, respectively, and 1s E Rd is defined by si) = 1 if i E S and 0 otherwise.
Assume {S)essC(4) is ordered so that each utility function U₂ be treated
vector U² d-1
R22-2 Besides, let W E 22) be diagonal matrix such that SS) (?))(d-s)²
and define X discovered that
by letting the S-th row of X is 1g. Very recently, Zhang al. (2023a)
Ezez [1lo(z; 0) (X wx) X W (U, - (2(0)124- 1 [ E5Ez [||U; (0) 12 Xx(2; 0)l C2]
d-1
=Zzez
Σ
sl -) (Uz(S) Uz(0) 12; + +C=
@CSC[d
where C. = =1(X T (X) I W(U: - U. (0) 20)12=-2)113 22)l Tx - 1 (0) U. ll
The convention is ||2l2 = Az. This relationship reveals that FastSHAP is just to train explain- ers towards a (potentially) biased target (X Wx)- W (U, (0) under the metric
induced by X WW: see Proposition 9. Therefore, they instead proposed to train explainers based on
Ez~z1llo(z;0) +03
(20)
where is any unbiased estimator for the Shapley value. They demonstrated in the experiments that this framework of training explainers is not just simple but effective. Note that the target (X W W (U,- - (2(0)124-2) is expected be biased because compared with Eq. (3), the efficiency constraint, which is supposed to be Σ ((2; 0) = ([d) - U (8). has been re- moved. Nevertheless, overcome this issue, the authors of FastSHAP added an additive-efficient- normalization layer on top during training and inference (Jethani et al. 2022, Table 3), which is ((=;0) + 0) + (U=(( - Uz(0) - Σí= 0))
Remark 6. Note that the framework (20) can be used for training explainers towards any proba- bilistic value. Intuitively, faster unbiased estimator substituted in the framework (20) would lead to better training of explainers. All in all, faster estimators could possibly benefit the research line of training proaaiilistic-aalie based explainers in feature attribution.
Proposition 9. Let 8Sh = (X (XT - W (U, U2(0)1244 2) and Sh be the Shapley value using the utility function Uz. Then, there
$ Sh
Ssh + +pla
1 T WX)
1 W(U, - -
where p
1. (X WX) '1,
In other words, XXWX) I W (U, - 12x is potentially biased as p is not necessarily zero.
21

---

Published as a conference paper at ICLR 2024
Proof. In view of the optimization problem (17), let m, By (Charnes et al. 1988, Theorem 4), the induced uniquely optimal solution v is exactly & According to Eq. (19), we have
d-1 and U Us.
A-1 b 1JA U= U=([d) + U=(0) 1d A -Id X W(U, (s(0)12a-2)
where A X WX and
from which we can deduce
= A- p1. 5h + pls
1 A - b (=((d) (0)
where
1 A '1d
H INTERPRETATION OF R(N) AND T(N) IN PROPOSITION 4
Recall that k(n) (n)) where 7(n) = >x11 +224+))41)
Our interpretation of x(n) is based
Ei= (")(+++p++))
+p]+1)
on (n.). In Algorithm for each non-empty proper subset S, its probability of being sampled is
P- P
P(S) Σ==l (p= P
Since ((n) = Ess(n) ies P(S), (() is the probability that the i-th data point appears a random sample S. Thanks to symmetry, the choice immaterial. Thus,
nn(nn) =
Σ
P(S)
1 sesP(SS
Σ sP(S) = Es(s],
1=1 SC(n]: iES
i=1
whence follows
Es(s]
(n)
The lower bound is achieved when pT = 1 and p. = 0 for all 2 2, corresponding to the semivalue with μ 6n. i.e., leave everything else out.
Looking into Algorithm 1, for each sampled utility evaluation (S) is used to update the esti- mates of data. Therefore, (n) is just the average rate of reusing utility evaluations, and <(n) is the inverse square of this average rate. The higher ((1) is, the more efficient GELS-R is. On the flip side, reusing utility evaluations also creates correlation among the estimates. We conclude that for the benefit to outweigh the cost, ((n) needs to be on the order of w( yŋ which is easily satisfied as long as the sequence {r") } is not exclusively concentrated around small All practical probabilistic values used in the literature, including the ones in our experiments, meet this condition.
Recall that T(n) (E (p") i [n].
2 and we write ((n) T T(n)= -1 Observe that, for every
2((n) X Σn C))
+ (1
A) Σn= (,"))p²
Ei p where À Σr (" pp introduced null data point (equivalently, the (n + 1)-th data point). Then, for any E [n],
is the probability of subsets sampled by Algorithm 2 not containing the
Σ
Ps)+(()
p
@CSC
ies
22

---

Published as a conference paper at ICLR 2024
where (S)+1(S) is the probability of the set S sampled by Algorithm 2 conditioned on that the samples do not contain the (n + 1)-th data point. Therefore.
7
Lis LiEsP3nt1(S) (5)+(())
Σ
s sPznt1(S) = Esisan+1[s))
2=11
NCSC(m)
On the other hand, for every [n|]
> 1=1
(n
8-
Ps
Σ
P
E n1
==1
x-
[ igS ig8,
which leads to
72
ligsPant1(S)
1=
0555|++1]: n-1es
Σ
(1+1-8 P3n+1( [s +1+ 1-s).
05 [gs nt1es
Eventually, we have
<(n) (A Esisa+11 (s) (1 (1-x) A)
Es +1 s))
2n
Es
itgs (n+1 - 1))
2n
Looking into Algorithm 2, i) if the sampled subset does not contain the null data, there are a of {f: - fntisssss receiving updates from ("))); ii) for the other way, there n + of them
receiving updates from (S). To conclude, r(m) is the square inverse of the average rate of reusing utility evaluations while rumning Algorithm 2.
I ASYMPTOTIC ANALYSIS
This appendix is mainly to analyze the asymptotic behavior (as n + oo) of <(n) and T(n) that appear Proposition For probabilistic values, generally, there is no restriction on how {p" E R )=2 are organized. Therefore, to analyze the convergence of our proposed estimators, we focus on semi-values instead. According to Dubey et (1981), each semi-value corresponds to probability measure μ the interval [0, 1] such that
p- = 1.' (1- ([(1-t)"==p((( for every 1 < s S n.
(21)
Lemma 2. Suppose 1, and for each probability measure i the closed interval [o, 1), define
m [ tddt(t) and w ( (1- (1= du(t)) for every k 2 0,
Mc Σ mlk and Wh: = Σ wh for every k: 2 0.
Then, there is
M + WH W and T(n)# Mh + W
x(n)+
M
Proof. Recall that in Proposition x(n) Σn
(o?
By Eq. (21), there is p. +p++
(py +p
- for every 1 < s < 1. Notice that
1-1
71
n
Σ
1
n1
n-1
7 1
m-1
23

---

Published as a conference paper at ICLR 2024
By Eq. (21),
n 1
1-- (1 sd((t) 8
p
8
a
11
t0(1 +) 3-m-1-=cp dd((t)
5
(1 -)m du(()= = /-¹ (1- (1- -1- (1)
dp((t)
W n-2
Note Σx=1 ("-1) t (1 f)m-1-s- Σ}= (1- t)² still holds for t 0. Similarly, one can get
1
ps n-1 MH-2
Recall that in Proposition 4 7(n) = D (a+1) in similar fashion.
p" "'''pp"' and thus one can get T()) = M 1 W
Using the monotone convergence theorem, we have
+1+1 1-1 du(t)= = /'' lim
1 1- t"+
I-1 du(t) = S. 1 -ud00t
lim
M
lim
1-+00
+2+000
n n-000
(1 - t)
du(t) ('' 1
du(t)..
lim W lim
(22)
Note that the extreme cases, e.g., limn-too M = fo d5) is trivially true where the conven- tion is 1 co. Therefore, r(n) @(1) if and only the two integrals in the above are finite. In par- ticular, it holds if the probability density function of μ satisfies lim p(t) for some a, see Proposition 10. Interestingly, we have
p lim
p(t)
[1-1)=
W W S 1+ W W
x(n)+ t = =1
M
Thus, <[n)= = (11) if the integral Eq. (22) is finite, meaning that μ cannot put "large" mass around t = O. However, this is not necessary as any symmetric probability measure μ,, e.g., the uniform distribution that leads to the Shapley value, will have k(n) = 4.
Remark 7. For extreme cases = de (leave everything else out) and μ 51 (leave one out), it clear that k(n) E (1)) for the latter but it becomes ((n²) for the former, in which case our GELS-R (Algorithm 1) in fact only samples subsets of size 1, and therefore each utility evaluation used to update the estimate of one data point. By contrast, the (weighted) sampling lift estimator always spends two utility evaluations update the estimate of one data point.
Corollary 1. For the Banzhaf value, s(n),T(n) (1). In other words, GELS, GELS-R and GELS- Shapley require ( 2. log 3) utility evaluations to achieve an (e, oxpprxxxiiiiinoonnnnn for the Banzhaf value.
Proof. For the Banzhaf value, f S0.5 (Dirac delta distribution), and thus limn Mo0.c lim, Who =
We now provide some easily verifiable conditions that determine the growth of k(n) and ((n)- Recall that as long n(n), o(n), our estimators are more efficient than the sampling lift estimator.
Proposition 10. Assume the probability measure μ admits a density function p such that μ(S) = Ig (t)dtt for every moasl-meas subset S C [0, 1). then,
24

---

Published as a conference paper at ICLR 2024
1. k(n), E (1) there exist a, 0 such that lime-40 lim
p(t)
(1-e)o O.
p(t))
2. ((n) ((log(n)3) if lim sup p(t) oo and lim sup,, -1 p(t) < co. Examples include if p is bounded (the so-called continuous semivalues used by Dubey et al. (1981)).
Proof. We first show that there exist counterexamples if these conditions are violated. For the Shapley value with μ == (the uniform measure). my w k+I and thus r(n) (llog())?).
For the second, looking into Lemma 3, consider a 1, [(n) E ((22-2a).
Suppose there exist a, > 0 such that lim A00 lim;-1 [1-1)² O. Then, there exists some
p(t)
e, C. > such that p(t) < Ct - t) if < e and t > 1 1 E. Define a positive measure μe by letting (S) 1 n |e,
<|) for every Borcl-mcasurable subset S S [0, Besides, define another positive measure by letting X(5) = Js Ct (1 t) for every Borel-measurable subset S S [0, 1]. Therefore, we have μ S He + A, which indicates that m S m + m and thus ME S Mt + Mn. By Lemma 3, M E ((1). For the other, observe that m I m, 6i-c, and therefore Mt < M Mhh- E @(1). The remaining case W can be tackled similarly. To conclude, *(n), r()) (1).
Suppose sup- p(t) < co and lim p(t) < co, then there exist c, C > 0 such that p(l) S C for every I E (0,c) (1 e, 1. Define Me as the one in the above. Then, μ S tr + CU where U denotes the uniform measure. Therefore, w S w + uh Since w R+1 there is W n). Besides, W < w ((1). The remaining case Mt can be dealt with similarly. Therefore, the conclusion follows by using Lemma 2.
C
Next, we derive more precise estimate for the Beta Shapley values.
Lemma 3. Let B(a, 33 be the beta distribution with probability density function ta-1(1 Note that if y = B((x, 3), it yields the [eta a) (a parameterized Beta Shupley value).
t)8-1
(logn)
B = 1
(logn) O(1)
a=1 a a>l 1 O
MB(a.))
(())
B >
and Wil(a,3) E
(()
0 < 3
0<a<1
Proof. Let I' denote the Gamma function.
T(a + 9) I(a + (B) ((a) T(a + 3 ++
I +
B(a,8) m k
I + ()+
We write dg by if lim converges. Since [(x) lim ((+11)--(-z)) e.g., see (Rudin B(a,8)
1953, Eq. (95) in Chapter 8), we have m The remaining case can be derived similarly.
kA k3 = k-8 and thus the conclusion follows.
Remark 8. Lemma 3 is useful for obtaining the time complexity of the proposed estimators for the Beta Shapley values parameterized by a > O. If 3 > 1, the two proposed estima- Note that this is
tors require O log )) utility evaluations to achieve an (e, (uproxiipro...attin. the currently best time complexity. For the Shapley value, i.e., Beta(1, 1). it is O log z) for GELS-R, and O log( log(n)?) for GELS and GELS-Shapley. To our knowledge, in terms of (c, -approximation the previously best time complexity for the Shapley value is O 2 log( 3) log n) achieved by the group testing estimator (Wang and Jia 2023, Theorem C.7).
J MORE EXPERIMENT RESULTS
For training estimators on MNIST, all performance curves are provided in Figure 11. It can be seen that the conclusions we have in the main paper still hold on MNIST.
The paired sampling technique was proposed by Covert and Lee (2021) to enhance (unbiased) Ker- HAP, but notice that it can also be employed for GELS, GELS-R, GELS S-Shapley, (weighted)
25

---

Published as a conference paper at ICLR 2024
sampling lift, group testing, AME, MSR and simSHAP. Precisely, suppose the sampled subsets is {Si hSk, the paired sampling employs sampled subsets {Ti such that T2k-1 = Ss and T2k [n for every & 2 1. Roughly speaking, symmetric probabilistic values, i.c., p. p for every & E [n] could possibly take advantage of this technique. Examples include the Shapley value, the Banzhaf value and Beta(7, 7). An exception is that weighted sampling lift can be coupled with the paired sampling for any probabilistic value. In this appendix, we implement the paired sam- pling technique if possible. The results with utility functions reporting the classification accuracy on D p are shown in Figures 3, 4, 5 and 6. Moreover, we also set the utility functions to report the cross-entropy loss instead, and the corresponding results are presented in Figures 7, 8, 9 and 10.
Remark 9. Observe that AME, simSIIAP and group testing gain significant performance boosts us- ing the paired sampling technique, while (unbiased) KernelSIAP takes advantage of this technique occasionally. For other estimators, the paired sampling does not play a noticeable role. Interest- ingly, while using the paired sampling technique. group testing is exactly equal to GELS, whereas GELS-Shapley unbiased KernelSHAP and simSHAP are all equal.
To see the equality between GELS and group testing while using the paired sampling technique, notice that they share the same way of sampling subsets. Therefore, suppose we have one pair of samples (S,,5) where S2 = [n+1]| 11 According Algorithm 2, the corresponding i-th estimate of GELS is
Hn. (U) n (r))
[n])), ie S and n + 1 1 S Hn (U"(S2 [ (n]) - (S: [m)), i S and n + 1 E Si
GELSS 0i
0,
otherwise
Looking into the procedure of including dummy player for group testing (Wang and Jia 2023, Appendix C.3), the reader can verify that group testing produces the same i-th estimate using the paired samples (S, [n + 1J(5))
where H,, =
For the remaining equality while employing the paired sampling technique, observe that they also have the same way of sampling subsets. Again, suppose we have one pair of samples (S1, where S [r. By Algorithm 3, the corresponding i-th estimate of GELS-Shapley is
UT (m)) - (0)
Hn- 82 (U)(S)) (S))) S1
GELS Shapley Pi
n U (m)) - Um n
n
H 81 (U*(52) (S))) i S2
n
where Hn-1 Σx=1 As proved by Fumagalli et al. (2023, Theorem 4.5), the corresponding i-th estimate of unbiased KernelSHAP is
uubiissed KemelSHAP
(r
tm (0)
2H,
Σ t)) (LiEs. 8t) )))
T
where (=(S)= = U*(S) - (0). On the other hand, the corresponding i-th estimate of simSHAP can be expressed as
SiMSHHAP ('((n)) (0)
2H T
Σ UT((S)) (1iEs,
T
$t n
(23)
n
The reader can verify that &; SGELS-Shaple Junbiased KemeiSHAP
SSInSHAP using T = 2 and S2 [n]]); We point out that Eq. (23) is not the original formula of simSHAP but an equivalent one that has been implicitly mentioned in (Fumagalli et al. 2023, Remark B.1 and Appendix B.4) where they argued that the choice of th is better than U². Our experiments confirm that unbiased KernelSHAP converges significantly faster than simSHAP while not using the paired sampling technique.
26

---

Published as a conference paper at ICLR 2024
GELS (ours)
sampling lift
group testing
permutation
AME
GELS-Shapley (ours)
kemelSHAP
ARM
weighted sampling lift
MSR
GELS-R (ours)
kernelSHAP
complement
Spearman correlation
relative difference
10
Shapley
10-1
10-1
10-2
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations datum
# #utility evaluations per datum
Spearman correlation
relative difference
10-7
109
Banzhaf
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
uutility evaluations per datum
Spearman correlation
10-2
relative difference
10
Beta (2, 2)
10
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
10-3
Spearman correlation
relative difference
10-1
Beta 4, 1)
1
10-2
10
5000
10000
15000 20000
15000 20000 uutility evaluations per datum
5000 10000
# #utility evaluations per datum
Figure 3: Comparison of different estimators on four probabilistic values using the dataset wind. The relative difference is plotted in log scale while the Spearman correlation is in logit scale. In addition, 1 The utility functions report the classification accuracy on Dpery- The dashed lines correspond the use of the paired sampling technique.
27

---

Published as a conference paper at ICLR 2024
GELS (ours)
sampling lift
group testing
permutation
AME
GELS-Shapley (ours)
kemelSHAP
ARM
weighted sampling lift
MSR
GELS-R (ours)
kernelSHAP
complement
Spearman correlation
relative difference
10
Shapley
1011
10-1
10
5000
10000
15000
20000
5000
10000
15000
20000
# #utility evaluations datum
#utility evaluations per datum
Spearman correlatio
relative difference
10
10
Banzhaf
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
relative difference
10a
Spearman correlation
10
Beta (2, 2)
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
# #utility evaluations per datum
10-3
Spearman correlation
relative difference
Beta 4, 1)
10-1
10-
10-1
5000
10000
15000 20000
15000 20000 uutility evaluations per datum
5000
10000
# #utility evaluations per datum
Figure 4: Comparison of different estimators on four probabilistic values using the dataset iris. The relative difference is plotted in log scale while the Spearman correlation is logit scale. In addition, 1 The utility functions report the classification accuracy on Dpery- The dashed lines correspond the use of the paired sampling technique.
28

---

Published as a conference paper at ICLR 2024
GELS (ours)
sampling lift
group testing
permutation
AME
GELS-Shapley (ours)
kemelSHAP
ARM
weighted sampling lift
MSR
GELS-R (ours)
kernelSHAP
complement
Spearman correlation
relative difference
10-2
Shapley
10-1
10
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations datum
# utillity evaluations per datum
109
Spearman correltion
relative difference
10
Banzhaf
10-1
10
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
Spearman correlation
relative difference
10-7
Beta (2, 2)
10-1
10
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
10
Spearman correlation
relative difference
Beta 4, 1)
10-1
10-2
5000 # #utility evaluations per datum
10000
15000 20000
15000 20000 # #utility evaluations per datum
5000 10000
Figure 5: Comparison of different estimators on four probabilistic values using the dataset MNIST. The relative difference is plotted in log scale while the Spearman correlation is in logit scale. In addition, 1 The utility functions report the classification accuracy on Dpery- The dashed lines correspond the use of the paired sampling technique.
29

---

Published as a conference paper at ICLR 2024
GELS (ours)
sampling lift
group testing
permutation
AME
GELS-Shapley (ours)
kemelSHAP
ARM
weighted sampling lift
MSR
GELS-R (ours)
kernelSHAP
complement
10
Spearman correlation
relative difference
Shapley
10-1
10-2
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations datum
# utiility evaluations per datum
Spearman correlation
relative difference
10-7
Banzhaf
10-1
10-1
10
0
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
Spearman correlation
relative difference
Beta (2, 2)
10
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
Spearman correlation
relative difference
Beta 4, 1)
10-2
10-1
10-1
5000
10000
15000 20000
5000
10000
15000 20000
# #utility evaluations per datum
uutility evaluations per datum
Figure 6: Comparison of different estimators on four probabilistic values using the dataset FMNIST. The relative difference is plotted log scale while the Spearman correlation is in logit scale. In addition, 1 The utility functions report the classification accuracy on Dpery- The dashed lines correspond the use of the paired sampling technique.
30

---

Published as a conference paper at ICLR 2024
GELS (ours)
sampling lift
group testing
permutation
AME
GELS-Shapley (ours)
kemelSHAP
ARM
weighted sampling lift
MSR
GELS-R (ours)
kernelSHAP
complement
10-3
Spearman correlation
relative difference
Shapley
10-1
10-
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations datum
# #utility evaluations per datum
109
Spearman correlaton
relative difference
Banzhaf
10-1
10
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
uutility evaluations per datum
Spearman correlation
relative difference
10
Beta (2, 2)
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
Spearman correlation
relative difference
Beta 4, 1)
10-1
10-7
10001
1
5000
10000
15000 20000
15000 20000 uutility evaluations per datum
5000 10000
# #utility evaluations per datum
Figure 7: Comparison of different estimators on four probabilistic values using the dataset wind. The relative difference is plotted log scale while the Spearman correlation is in logit scale. In addition, r r. The utility functions report the cross-entropy loss on D Dperf- The dashed lines correspond to the use of the paired sampling technique.
31

---

Published as a conference paper at ICLR 2024
GELS (ours)
sampling lift
group testing
permutation
AME
GELS-Shapley (ours)
kemelSHAP
ARM
weighted sampling lift
MSR
GELS-R (ours)
kernelSHAP
complement
Spearman correlation
relative difference
10-2
Shapley
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations datum
# #utility evaluations per datum
Spearman correlation
relative difference
10"
10-2
Banzhaf
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
10a
Spearman correlation
relative difference
10-7
Beta (2, 2)
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
Spearman correlation
relative difference
Beta 4, 1)
10-1
10-2
5000 10000
15000
20000
15000 20000 # #utility evaluations per datum
5000 10000
# #utility evaluations per datum
Figure 8: Comparison of different estimators on four probabilistic values using the dataset iris. The relative difference plotted in log scale while the Spearman correlation is in logit scale. In addition, r = 1 - r. The utility functions report the cross-entropy loss on Derrf The dashed lines correspond the use of the paired sampling technique.
32

---

Published as a conference paper at ICLR 2024
GELS (ours)
sampling lift
group testing
permutation
AME
GELS-Shapley (ours)
kemelSHAP
ARM
weighted sampling lift
MSR
GELS-R (ours)
kernelSHAP
complement
Spearman correlation
10-2
relative difference
Shapley
10a
10"
10
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations datum
#utility evaluations per datum
10
Spearman correlation
relative difference
10"
Banzhaf
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
Spearman correlation
relative difference
10
Beta (2 2)
10a
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
Spearman correlation
10
relative difference
100
Beta(1, (4, 1)
10-1
10
5000 10000
15000 20000
20000 # #utility evaluations per datum
# #utility evaluations per datum
Figure 9: Comparison of different estimators on four probabilistic values using the dataset MNIST. The relative difference is plotted in log scale while the Spearman correlation is logit scale. In addition, r The utility functions report the cross-entropy loss on D Dperf- The dashed lines correspond to the use of the paired sampling technique.
33

---

Published as a conference paper at ICLR 2024
GELS (ours)
sampling lift
group testing
permutation
AME
GELS-Shapley (ours)
kemelSHAP
ARM
weighted sampling lift
MSR
GELS-R (ours)
kernelSHAP
complement
Spearman correlation
relative difference
10
10a
Shapley
-10-7
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations datum
Futility evaluations per datum
Spearman corrlation
relative difference
109
10
Banzhaf
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
Spearman correlation
10
relative difference
109
Beta (2, 2)
10-1
10-1
5000
10000
15000
20000
5000
10000
15000
20000
#utility evaluations per datum
#utility evaluations per datum
Spearman correlation
relative difference
10-7
Beta 4, 1)
10-1
10
5000 10000
15000
20000
15000 20000 uuiility evaluations per datum
5000 10000
#utility evaluations per datum
Figure 10: Comparison of different estimators on four probabilistic values using the dataset FM- NIST. The relative difference is plotted in log scale while the Spearman correlation is in logit scale. In addition, r 1 r. The utility functions report the cross-entropy loss on D perff- The dashed lines correspond the use of the paired sampling technique.
34

---

Published as a conference paper at ICLR 2024
relative difference
10t
average
specific
Spearman corre elotion
best
0.6
20n
0.4
specific
0.2
average
25
10
25
20
30
0.0
10
25
30
#batches (k)
3 #atchhes
(k)
#batches (K)
10:
Spearman correlation
relative difference
TrELS-SC (ours)
8.8
TrELS-RD (ours)
1.66
6.4
Monte Carlo
TrELS-SC (ours)
TrELS-RD (ours)
10 *utility evalustions per datum (k) *utility evaluations per datum (k)
10 15 20
Figure 11: i) The first row: The first plot is the empirical loss of the sampled batch, while the others present the relative distance l| ella//1elll and the Spearman correlation between şo and 3. & denotes the one predicted by the estimators trained on MNIST. The first two plots are in log scale. The label "best" reports the best one achieved by trained estimators at each time point, whereas "specific" is the one with the random seed being 0. ii) The second row: the two plots compare the performance of the estimators trained on MNIST with the Monte-Carlo method using Eq (2). Specifically, TrELS-SC uses trained estimators that achieve the best Spearman correlation Drat, whereas RD stands for relative difference.
35


Reviews:
[{"review_id": "PsqWmAZtYG", "reviewer": "Reviewer_wdkt", "summary": "The paper proposed two generic probabilistic values estimators (one for ranking and the other for exact probabilistic values) that achieves $O(\\frac{N}{\\epsilon^2} \\log \\frac{N}{\\delta})$ utility evaluations, improving upon previously known generic estimators that require $O(\\frac{N^2}{\\epsilon^2} \\log \\frac{N}{\\delta})$. The authors prove theoretically convergence rates of their estimators, and present their performance with numerical experiments.", "questions": "In conjunction with 1-4 in the weakness part.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The result is interesting and novel to me, though I am not an expert in this area. The estimators proposed is general enough, and comparisons with previous literature is thorough. The paper provides both good theoretical and numerical evidence.", "weaknesses": "1. Lack of direct comparisons to previous estimators specific to special cases achieving the same rate. I would like to see more discussions on SHAP, MSR and AME estimators. Why they cannot be generalized? What are their main ideas comparing to this paper, what is the fundamental differences?\n2. It may be that I'm not familiar with the field, but the presentation does not properly introduce the background. It would be nice if the authors can provide a few more demonstrations in the introduction, i.e. examples for Shapley and Banzhaf. I did not see proper explanations on those probabilistic values while reading the paper.\n3. The numerical plots could look better in log-scale, for now it's hard for me to distinguish between lines when they converge.\n4. Lack of expanding on the theoretical results. Some explanations on the intuition on why an $\\Theta(N/\\epsilon^2)$ convergence rate is expected and what makes it different from previous estimators would be nicer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gVcdKu9nf9", "reviewer": "Reviewer_XZSz", "summary": "Probabilistic values, rooted in cooperative game theory, play a pivotal role in data valuation. \nHowever, their computation poses significant challenges, especially as dataset size (N) increases. \nMany current estimators either come with high computational overheads or cater only to specific instances.\n\nHere are the main contributions of this paper:\n\n* The authors introduce two versatile estimators, anchored in least squares regression, \n  capable of efficiently approximating a broad range of probabilistic values, \n  transcending the confines of earlier methods typically designed for specific values like the Shapley value. \n  (Refer to Sections 3.1 and 3.2)\n* Through Propositions 3 and 5, the authors establish that both novel estimators necessitate only O(N log N) utility evaluations \n  to achieve a (ε,δ)-approximation, thereby aligning with the best-known computational complexities for certain cases.\n* Section 3.3 unveils a pioneering approach to cast the distributional value—a more consistent alternative \n  to probabilistic values—as a least squares problem. \n  This breakthrough facilitates the training of machine learning models that can swiftly gauge distributional values of unseen data in a single pass.\n* Validating the efficacy of their proposals, Section 4 presents experiments that \n  substantiate the accelerated convergence of their estimators compared to preceding methods. \n  Moreover, they successfully illustrate the potential of training models to adeptly predict distributional values for novel data points.", "questions": "* While the paper presents a novel approach to data valuation using distributional Shapley values, could you shed light on the practical applications where this approach might be most beneficial?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "* The paper introduces efficient methods for both ranking and value estimation of data points. \n  Through Propositions 1 and 2, they've laid out a mechanism to estimate the relative ranking underlying any probabilistic value.\n  Notably, this method is computationally advantageous.\n* They've established a framework, as seen in Theorem 1 and the related discussions, for training models to serve as value estimators. \n  This is highly valuable, as trained models can swiftly evaluate any unseen data point \n  from similar distributions in just a single forward pass, making the evaluation process much more scalable.", "weaknesses": "* There are computational challenges associated with training value estimators. When evaluating the distributional values, even with approximations, the computational costs are significant. \n* The paper mentions that the faster convergence of certain estimators like SHAP, SHAP-paired, and the complement comes at the cost of using Θ(N^2) memory storage instead of Θ(N). However, the implications of this memory increase, especially for large-scale applications, are not discussed in depth.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aqNDd6xts9", "reviewer": "Reviewer_s6uD", "summary": "This paper proposes an algorithm that estimates the probabilistic value $v_i$ of each data point $i\\in[n]$, i.e., $v_i:=\\sum_{S\\subseteq [n]\\setminus \\{i\\}} p_{|S|}\\cdot (U(S\\cup \\{i\\})- U(S))$, where $U$ is a given utility function that maps any subset of data points to a value, and the weights $p_{k}$'s can be chosen arbitrarily by the user, as long as they satisfy $\\sum_{k=0}^{n-1} p_k\\cdot \\binom{n-1}{k} = 1$. The well-known Shapley value is a special case of the probabilistic value. Their estimator uses $O(n\\log n)$ evaluations of the utility function $U$, an improvement over the previous work [Kwon and Zou 2022] which uses $O(n^2\\log n)$ evaluations.\n\nTheir estimator is based on a simple observation: because $\\sum_{S\\subseteq [n]} p_{|S|}\\cdot U(S)=\\sum_{S\\subseteq [n]\\setminus\\{i\\}} p_{|S|}\\cdot U(S) + \\sum_{S\\subseteq [n]\\setminus\\{i\\}} p_{|S|+1}\\cdot U(S\\cup\\{i\\})$, we have $\\sum_{S\\subseteq [n]\\setminus\\{i\\}} p_{|S|}\\cdot (U(S\\cup \\{i\\})- U(S)) + \\sum_{S\\subseteq [n]} p_{|S|}\\cdot U(S) = \\sum_{S\\subseteq [n]\\setminus\\{i\\}} (p_{|S|}+p_{|S|+1})\\cdot U(S\\cup i)$.\n\nHence, their method uses random sampling to simultaneously estimate $v_i':=\\sum_{S\\subseteq [n]\\setminus\\{i\\}} (p_{|S|}+p_{|S|+1})\\cdot U(S\\cup i)$ for all $i\\in[n]$ and $\\sum_{S\\subseteq [n]} p_{|S|}\\cdot U(S)$, and then substracts the later from the former to get the estimates of $v_i$ for all data points $i\\in[n]$.\n\nThe advantage of their method is that a random sample $S\\subseteq [n]$ can be used to estimate $v_i'$ for all $i\\in S$ simultaneously, using just a single evaluation of the utility function -- $U(S)$. In comparison, if we use the sample $S$ to estimate the $v_i$ for all $i\\in S$ directly, we would need to evaluate $v(S\\setminus \\{i\\})$ for all $i\\in S$. Thus, they get an improvement from $O(n^2\\log n)$ evaluations to $O(n\\log n)$ evaluations.", "questions": "Could you elaborate the advantage of your estimator over previous works in terms of practical performance?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The idea is simple and cute.\n- The writing is fine overall.", "weaknesses": "- The result is technically a bit thin.\n- The least squares interpretation seems a bit artificial and redundant.\n- From the experiments in appendix, it is not obvious to me that the proposed estimator is any better than previous works (e.g., the well-known SHAP for estimating Shapley value).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tlkywtzGnP", "reviewer": "Reviewer_3wRG", "summary": "The paper proposes two generic estimators of the importance value of the $i$-th data point for the whole family of probabilistic values. Both estimators require $O(\\frac{N}{\\epsilon^2}\\log\\frac{N}{\\delta})$ evaluations to obtain $(\\epsilon,\\delta)$-approximation, which is the optimal among known bounds. Further, the paper designs a framework for computing the distributional value estimator by connecting it to the obtaining least square regression. Vast experimental results show the faster convergence of the estimator over other benchmarks.", "questions": "Q1. Is $\\gamma$ defined in the proof of Proposition 3 and 5 is a constant independent of $N$?\nQ2. How the generalization to a general family of probability values $\\mathbf{p}$ is possible?\nQ3. When can $\\phi_i^{\\mathcal{B},\\mathbf{w}}(U)$ converge to $\\phi_i^{\\mathcal{D},\\mathbf{w}}(U)$? Could any convergences results be derived?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper extends the current results to general probabilistic values by resolving the main limitation in computing the estimator of importance value. Further, the connection between estimating distributional value and the least square estimator in (13) saves computational costs drastically. These results have a potentially significant impact on data valuation.", "weaknesses": "(1) One major concern I have is whether $\\gamma$ (which is defined in the proof of Proposition 3 and 5) is a constant independent of $N$ for any probability values $\\mathbf{p}$. It seems that setting $p_1 =1/2$ and $p_i \\approx 0$ for $i>1$ yields $\\gamma=O(1/N)$. As the $\\gamma$ appears in the bound [(34) and (39)] for the number of evaluations, this seems critical in the first main contribution.\n\n(2) The intuitive explanation of how the generalization to general $\\mathbf{p}$ is possible should be included in the main text.\n\n(3) Discussion on the cases when $\\phi_i^{\\mathcal{B},\\mathbf{w}}(U)$ in Theorem 1 is close to $\\phi_i^{\\mathcal{D},\\mathbf{w}}(U)$ would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)