Data Debugging with Shapley Importance over Machine Learning Pipelines
Authors: Bojan Karlaš
David Dao
Matteo Interlandi
Sebastian Schelter
Wentao Wu
Ce Zhang
Venue: ICLR 2024 poster (2024)
Keywords: data debugging
data valuation
shapley value
machine learning pipelines
Primary area: infrastructure, software libraries, hardware, etc.
TL;DR: Efficiently computing the Shapley value of training data examples over machine learning pipelines.

Abstract: When a machine learning (ML) model exhibits poor quality (e.g., poor accuracy or fairness), the problem can often be traced back to errors in the training data. Being able to discover the data examples that are the most likely culprits is a fundamental concern that has received a lot of attention recently. One prominent way to measure "data importance" with respect to model quality is the Shapley value. Unfortunately, existing methods only focus on the ML model in isolation, without considering the broader ML pipeline for data preparation and feature extraction, which appears in the majority of real-world ML code. This presents a major limitation to applying existing methods in practical settings. In this paper, we propose Datascope, a method for efficiently computing Shapley-based data importance over ML pipelines. We introduce several approximations that lead to dramatic improvements in terms of computational speed. Finally, our experimental evaluation demonstrates that our methods are capable of data error discovery that is as effective as existing Monte Carlo baselines, and in some cases even outperform them. We release our code as an open-source data debugging library available at https://github.com/easeml/datascope.

Published as a conference paper at ICLR 2024
DATA DEBUGGING WITH SHAPLEY IMPORTANCE OVER MACHINE LEARNING PIPELINES
Bojan Karlaš'; R, David Dao², Matteo Interlandi', Sebastian Schelter', Wentao Wu', Ce Zhang Harvard University, 2ETH Zurich, Miirosoff, 'University of Amsterdam, University of Chicago "bkarllsseee las@ngh. harvard.ed
ABSTRACT
When a machine learning (ML) model exhibits poor quality (e.g., poor accuracy or fairness), the problem can often be traced back to errors in the training data, Being able to discover the data examples that are the most likely culprits is fundamental concern that has received a lot of attention recently. One prominent way to measure "data importance" with respect to model quality is the Shapley value. Unfortunately, existing methods only focus the ML model isolation, without considering the broader ML pipeline for data preparation and feature extraction, which appears in the majority of real-world ML code. This presents a major limitation to applying existing methods in practical settings. In this paper, we propose Datascope, method for efficiently computing Shapley-based data importance over ML pipelines. We introduce several approximations that lead to dramatic improvements in terms of computational speed. Finally, our experimental evaluation demonstrates that our methods are capable of data error discovery that is as effective existing Monte Carlo baselines, and in some cases even outperform them. We release our code as an open-source data debugging library available at gugthub.com//ssse/llltssspp
INTRODUCTION
Data quality issues have been widely recognized to be among the main culprits for underperforming machine learning (MI.) models, especially when it comes to tasks that are otherwise considered solved by MI (Liang et al. 2022 [lyas & Chu 2019). A common type of data errors are wrong labels. For example, biomedical images can be misdiagnosed due to human error which results in label errors. Many systematic methods have been developed to repair data errors (Rekatsinas et al.) 2017 Krishnan et al. 2017). Unfortunately, in many practical scenarios, repairing data in a reliable manner requires human labor, especially humans have been involved in producing the original data, The high cost of this data debugging process has led to a natural question Can we prioritize data repairs based on some notion of importance which leads to the highest quality improvements for the downstream model?
In recent years, several approaches have emerged to answer these questions. One line of work suggests expressing importance using influence functions (Koh & Liang 2017) which is essentially a gradient- based approximation of the leave-one-our (LOO) method. Here, the importance of training data example is expressed as the difference in the model quality score observed after removing that data example from the training set. This quality difference is referred as the marginal contribution of that data example. Another line of work proposes Shapley value as a measure of importance (Ghorbani & Zou 2019 Jia et al.) 2019b; (02T) that has a long history in game theory (Shapley [951]. In the context of data importance, it can be seen generalization of LOO. Namely, instead of measuring the marginal contribution over the entire training set, we measure it over every subset of the training set and then compute weighted average. Apart from having many useful theoretical properties, the Shapley value was shown to be very effective in many data debugging scenarios (Jia et al.) 2021].
On the flip side, because the Shapley value requires enumerating exponentially many subsets, com- puting it is intractable in practical settings. There have been different ways to approximate this computation. This includes Monte Carlo (MC) sampling (Ghorbani & Zou 2019) group test- ing (Jia et al. 2019b) to sample subsets of training data, train models as black boxes on those subsets, compute marginal contributions of training data examples, and aggregate the results compute the final approximated result. Unfortunately, re-training the model can be quite costly, especially for large models. Some methods try overcome this by leveraging proxy models such as K-nearest neighbors

---

Published as a conference paper at ICLR 2024
Training Data
Imporiance
Bata
Country
Ang.
Prepared Training Data
Model Quality Metrics
797
799
FR
US
$51.155
$24,375
Random Augment
Missing Indicator
Bata
0:71
Roaturzs Lopels
Accuracy
797
777
Urgw
DS
FR
other
Race
Age
Weslthy
Standard
Sceler
KcMaaans
Union
0.64
0:43
Trained Model
ROC AUC
Fairness
729
FR
White
65
computed with respect to
Data Errors
Data Debugging Occurs Here
Existing Methods Assume This Setting
Figure 1: Existing data debugging methods were designed to compute data importance of already preprocessed data. In typical real-world scenarios, data errors occur in source datasets, before being passed through data preparation pipeline. The goal of our work is to help close that gap.
(KNN) (Jia et al., 2019a) and exploiting its simple structure to derive dynamic programming (DP) algorithms for computing the Shapley value.
One major trait of the existing work in this space is that it primarily focuses on computing the importance of data examples in the prepared training dataset. This poses challenge in practical settings where data errors typically occur earlier in the data preparation process. In most realistic scenarios, this process involves taking one or more source training datasets, joining them together if needed, and applying a composition of data preprocessing operators Figure Tp. The simplest operators may represent a 1-1 map of input dataset elements to output dataset elements (referred to as tuples in the data management literature). Some operators, such the data augmentation operator, fork the data by converting a single input data tuple into multiple output tuples. On the other hand, an output tuple of join operator can be the product of multiple input tuples. Finally, some operators involve a reduce operation which involves computing some intermediate result based on the entire input dataset (e.g. the mean and standard deviation) and then applying that result to output tuples.
This new setting impacts existing approximation methods in several ways. Firstly, given that it is a black box approach, Monte Carlo sampling (Ghorbani & Zou| (019) can directly be applied to this setting. However, this comes with the computational cost of re-running the data preprocessing operators for every subset of the training data that we sample. Depending on the complexity of the preprocessing pipeline, this cost can be quite significant. Secondly, the existing LNN-based Shapley approximation method (Jia et al. 2019a) strictly relies on the ability to independently remove tuples from the prepared training dataset in order to compute their marginal contributions. Given the aforementioned complexity induced by preprocessing operators, the tractability result of the previous KNN-based method does not hold directly in this new setting. Therefore, a novel analysis is needed to see whether the Shapley value computation can be made tractable depending on the structure of the data preprocessing pipeline.
Contributions. In this paper, we focus studying the relationship between the structure of ML pipelines and our ability to efficiently compute Shapley values of source data examples. We make use of data provenance (Green et al.) 2007 Cheney et al. 2009), simple yet powerful theoretical toolkit for tracing individual data examples as they pass through a data processing pipeline. We propose case..l//atascope framework for modeling the interdependence between tuples induced by data preprocessing operators. Our contributions can be summarized as follows:
We apply the notion of data provenance to ML pipelines in order to relate the input and output datasets as a function of the pipeline structure. We introduce the notion of a "canonical pipeline" " which we simply define as distinct pipeline structure that lends itself to efficiently relating pipeline inputs and outputs, as well as efficiently computing Shapley values. We identify three classes of canonical pipelines: map, fork and one-to-many join. (section 3)
We show how approximating pipelines as canonical leads to sigmificant speed-ups of Monte Carlo methods for Shapley computation. We also demonstrate how the majority of real-world ML pipelines can be approximated as canonical. (section 3)
We combine canonical pipelines with the K-nearest neighbor as a proxy model. We show how canonical pipelines can be compiled into efficient counting oracles and used to derive PTIME Shapley computation algorithms. Under this framework, the KNN Shapley method from prior work represents a special case applicable to map pipelines. (section 4) We conduct an extensive experimental evaluation by applying all considered Shapley computation methods to the task of repairing noisy labels in various real-world datasets. We conclude that in most cases our method is able to achieve solid performance in terms of reducing the cost of label repair while demonstrating significant improvements in computational runtime. (section 5)
2

---

Published as a conference paper at ICLR 2024
2 PROBLEM: COMPUTING THE SHAPLEY VALUE OVER ML PIPELINES
Shapley Value, Let Der be a training dataset and u some utility function used to express the value of any subset of Der by mapping it to real number. Then, the Shapley value, denoting the importance of a tuple 14 E DDr, is defined as
(ott;)= = I
DDrrl EDEDIAAE (D) ("iiol-1)
(I)
Intuitively, the importance of to for subset D C Der |tt } is measured the difference between the utility u(D {t,}) with E, and the utility u u(D) without t.. The Shapley value takes a weighted average of all of the 2/P:,1-1 possible subsets D E Drr ]t,). which enables it to have a range of desired properties that significantly benefit data debugging tasks, often leading to more effective data debugging mechanisms compared to other leave-one-ou methods.
Quality of ML Pipelines. As mentioned, the utility function is defined to measure the value of any subset of Dir, which in our context corresponds to the source training dataset. We assume that this dataset can be made up of multiple sets of tuples (e.g. multi-modal dataset involving set of images and a table with metadata). The validation dataset Dval is defined a similar manner.
Then, let f be a data preprocessing pipeline that transforms any training data subset D S Drr into a set of tuples (t, (2,, 9i) 3 [e[M] made up of M feature and label pairs that the ML. training algorithm A takes as input. Finally, we obtain trained ML model A ((D) which we can evaluate using some model quality metric. Based on this, we can define the utility function used to express the value of a training data subset D as a measure the quality of an ML pipeline o f(D) when scored using Deat. Formally, we write this as
" (D) = mmA J(D), ((Deat)).
(2)
Here, m can be any model quality metric such as accuracy or a fairness metric such as equalized odds difference. Note that, for simplicity, we assume that we are applying the same pipeline both the training data subset D and the validation dataset D In general, these two pipelines can differ as long as the data format of (Drvt is readable by the trained ML model. For example, a data augmentation operation is typically applied to training data only (as is the case in our experiments). Core Technical Problem. In this work, we focus on the ML pipeline utility defined in Eqqation 2 and we ask the following question: How can we approximate the structure of in order to obtain Shapley-based -based data importance that is (1) computationally fast; and (2) effective downstream data debugging tasks?
3 CANONICAL ML PIPELINES
In this section, we take a closer look at a data preprocessing pipeline f that can, in principle, contain an arbitrarily complex set of data processing operators. This complexity can result in heavy overhead on the cost of computing the Shapley value. This overhead comes from having to re-evaluate the pipeline many times for different training data subsets. In this section, we describe framework for minimizing that overhead by solving a concrete technical problem.
We are given a training dataset Dtr, a data preprocessing pipeline f, and the output set f(D,r). For arbitrary subset D C Der and some tuple l' E ((rrr), decide whether L' E (D) in time ((1) w.r.t [Darl.
Problem 1.
is easy to see how solving this problem virtually removes the cost of computing the pipeline output of an arbitrary training data subset. Next, we describe reduced version of the data provenance framework (Gren et al.) 2007 Cheney et al. 2009) which we will apply to solve this problem.
3.1 DATA PROVENANCE FOR ML PIPELINES
We define set of binary variables A and associate variable a, E A with every training data tuple t E D.r.. Each subset D C Der can be defined using a value assignment v(a) + {0, 1]. where v((a)) means that & D. We use [vj to denote D. We write VA denote the set of all the 2| possible value assignments. Next, with every tuple t' E (Drr) we associate "provenance polynomial" Pr which is a logical formula with variables in A (e.g. dn + 02 03). For a given value assignment v. define evaluation function eval, (pe) + {0, 1) which simply follows the
3

---

Published as a conference paper at ICLR 2024
(2) Map pipeline
(b) Rock pipelize
(c) One-to-many join pipeline
(d) Distribution of canonical pigelines
Parky
Appodraniyy Caicical Oney
(a-c) Three types of canonical pipelines where data provenance allows us to efficiently compute subsets. (d) A majority of real-world ML pipelines (Psallidas et al., 2019) either already exhibit a canonical pipeline pattern, or are easily convertible to it using our approximation scheme.
Figure 2:
standard logical reduction rules to determine the truthiness of pe given v. For a tuple t' E fPrr) and a value assignment v, we define f(D directly apply this framework to solve Problem However, to respect the (11) time complexity, (pal must be (1) w.r.t [Dtrl. In inssubsection 3.2 we explore when this condition is met.
[v)) iff (pal = It easy to see that we can
Redefining the Shapley value. Using this framework, we can rewrite the Shapley value as:
(1:) TĄ EVERASIORS (ssupp(e)) "(r [u;a + 1)) (tr + 0)) The notation [u; a; X] for E {0, 13 means that we augment e with v(a,)) = X. Also, we define the support of v as supp(u) = {a E A v(aa) = =1..
3.2 APPROXIMATION: ML PIPELINES ARE CANONICAL
As mentioned above, solving Problem in (()) time depends on |p: being ((1) w.r.t. [Darl. This does not necessarily hold true for an arbitrary pipeline f. However, it does hold true for some classes of pipelines, which we refer to canonical pipelines. Hence, if we approximate the pipeline f as canonical, then we can solve (Problem I] The three classes of canonical pipelines that we identified to be useful in the context of this work are: map, fork, and one-to-many join pipelines (Figure 2}.
Map pipelines. This is the simplest form of pipeline where each input tuple E D,, corresponds to at most one output tuple t' f(rrr), after passing through an optional per-tuple mapping function u(t) + (Figure 2ap. Examples of such pipelines include missing value indicators, polynomial feature generators, pre-trained embeddings, etc.
Fork pipelines. In this pipeline, each input tuple / E Der can associated with multiple output tuples L' E (Drr), but a single output tuple is associated with a single input tuple (Figure 26). A prominent example a data augmentation pipeline that outputs several slightly altered versions of every input tuple.
One-to-many Join pipelines. This pipeline contains table join operators like the one in Figure Here, the training dataset Der {De, De...... Do,1 } is made up of multiple tuple sets that form a "star schema". This means that any training example tuple E DD can be joined with no more than one tuple from each of the auxiliary tables r......, polynomial of each output tuple is Boolean product of variables associated with all tuples that were joined to produce that output tuple (Fiuree 2c).
Day
Note that, for this pipeline, the provenance
3.3 APPROXIMATING REAL ML PIPELINES
Even though many real-world pipelines can be directly represented our canonical pipelines, there is still a solid amount that cannot be represented. Nevertheless, upon taking closer look, we can identify a class of pipelines that we might be able to approximately represent. These are the pipelines that exhibit an aetimator-transfon made up of some reduce operation performed on the entire dataset which produces some intermediate data, which is used to parameterize map operation which is performed on individual tuples. An example of such a pipeline is a min-max scaler, where the reduce step computes min and max statistics for each feature, which are then used to re-scale individual tuples.
pattern f(D) = map (reduce (D), D). Specifically, they are
The reduce step of this pipeline causes every output tuple depend on every input tuple, which does not fit into our canonical pipeline framework. However, we can still approximate such pipelines by isolating the intermediate data produced by reduce(P,r) Then, conditioned on that intermediate data, we can re-define our pipeline/ f to be conditional map pipeline f" as follows:
f(D) = map(reduce(D)) D) + f = map(reduco(Dww)) D).
Evaluation of Effectiveness. We evaluate our method of approximating pipelines as canonical and apply it directly to compute the Shapley value using the Truncated Monte Carlo (TMC) sampling
4

---

Published as a conference paper at ICLR 2024
Polktibles Adult, (5) Target Model: XGBoost
Pipeline: Random Augmese Missing Indicator
Stuadard Scaler K-Meuts
(h) Target Model:: Logistic Regression
50%
107
6.7-
60%
291.2
44.45
42.27
40%
15:31
20%
63-
-2.1
Perten Labaa Coun rec
Pa of Labda Courinns
Porker Laodl Scariine
Portor of DaTETe
Random
TMC
Datascope TMC x10
TMC x10
Datascope TMC x100
Figure 3: An ML pipeline with an estimator-transforee pattern approximated as a canonical pipeline can achieve comparable performance on a label repair task, with significantly faster runtime.
method (Ghorbani & Zou, 2019). We run the evaluation for 10 and 100 Monte Carlo iterations <110/x100), We can see that our approach exhibits comparable performance with significant gains in computational runtime (Figure 3). See fsectin for more details about the experimental protocol.
Statistics of Real-world Pipelines. A natural question is how common these families of pipelines in practice. [Figure 2d 2d]illusssates case study that conducted using 500K real-world pipelines provided by Microsoft (Psallidas et al. 2019)). We divide pipelines into three categories: (1) "pure" map/fork pipelines, based on our definition of canonical pipelines; (2) "conditional" map/fork pipelines, which are comprised of a reduce operator that can be effectively approximated using the scheme we just described; and (3) other pipelines, which contain complex operators that cannot be approximated. We observe that vast majority of pipelines we encountered in our case study fall into the first two categories that we can effectively approximate using our canonical pipelines framework.
SHAPLEY VALUE OVER CANONICAL PIPELINES
In Infsection33 3 we described an approach for treating the data preprocessing pipeline f as a white box which led us to directly attainable performance improvements of Monte Carlo Shapley methods. However, these methods still rely on treating the model .A as a black box and retraining for different training data subsets, which often results in slow runtime. In this section, we are interested in PTIME algorithms that give orders of magnitude faster runtime and thus open the door for interactive data debugging. Specifically, we focus on the following technical problem:
We are given a training dataset Der, a data preprocessing pipeline f and model quality metric m computed over a given validation dataset D val- Compute the Shapley value (as defined in Equation I) of a given tuple f; E 'Drr for the ML pipeline utility (as defined in |Equation 2p in time polynomial w.r.t. [Dr..] and [Doat].
Problem 2.
We will now explore additional approximations we can make the model A as well as the model quality metric m. Specifically, we replace the model with a KNN classifier, and we assume that the quality metric has specific additive structure. We then sketch the outline of solution to the given problem that leverages these approximations. It should be noted that although prior work has explored the idea of using the KNN proxy model for PTIME algorithms (Jia al. (011a)), the best of our knowledge, the work presented in this paper is the first to analyze the relationship between the structure of different types of ML pipelines and the computational complexity the Shapley value computation. A brief discussion about the limitations of prior work is presented in Appendix A
4.1 APPROXIMATION: THE MODEL IS KNN AND THE MODEL QUALITY METRIC IS ADDITIVE
Here we define two structures which we will use building blocks for approximating ML pipelines: the KNN model and additive model quality metrics. In the following section we will show how these building blocks can be leveraged to provide PTIME algorithms for computing Shapley values.
K-Nearest Neighbor (KNN) Model. We provide a specific definition of the KNN model in order to facilitate our further analysis. Given some set of training tuples D and a validation tuple tval, the KNN model (KNN(D) can be defined as follows:
AxNx == argmax, yey tally (D) topxc (D) fraa)) / (v)
Here, top (D) trat) returns a tuple tx E D that takes the K-th position when ranked by similarity with the validation tuple baat. Furthermore, tally(D) iK, beat) tallies up the class labels of all tuples
5

---

Published as a conference paper at ICLR 2024
in D that have similarity with tyal higher equal to tg. It returns Y, label tally vector that is indexed by class labels (i.e. y : 3 - N). Note that the sum of all elements in y must be K. Given a set of classes V/ we define y to be the set of all possible label tally vectors. Finally, assuming standard majority voting scheme, argmax returns the predicted class label with the highest tally.
Additive Model Quality Metric. We say that model quality metric is additive if there exists tuple-wise metric my such that m can be written as:
m(Ao f(D), (D = w Mimee mr ((40 I(D)) (tuat); teat
(5)
Here, w is a scaling factor that can depend only on Duat- The tuple-wise metric mr: (ypred, beat) H [0, 1] takes a validation tuple tral Duat as well as class label Upree E J predicted by the model for Eeat. It is easy to see that some popular utilities, such as validation accuracy, are additive, e.g., the accuracy utility is simply defined by plugging my(ypred, (Feat: yeat)) := 1 (ypred = Yeat) } and we show even more examples of such metrics.
= 1/[Deat into Equation 5
In subsection E.3
4.2 COMPUTING THE SHAPLEY VALUE
We now outline our approach to computing the Shapley value of a training data tuple 4 E Der using our approximation described in subsection 3.2 and subsection 4.1] We start off from Equation 3 and plug in u as defined in EEquaiin 2] Next, since we assume that our model quality metric is additive, we plug in m as defined in Lqquaion 5] By rearranging the sums, we can write the Shapley formula as (faa) = w Etmor f( f(D...)) (ft,, ), where (lt,, laa) a validation tuple-wise Shapley value. Under the assumption that our model is KNN, we can plug in as defined Equation 4 the sums, and arrive at the following definition of 40li, luat):
rearrange
(ftt, = Pài EuprESs E!A ('A-1) E T malt' x feat w/a."//"" tf,
(6)
We define ma(7 7" tvaa)) == (argmaax, w (v), tvat) ma (v), tvat) as the differential metric.
Counting Oracles. The function w Equutioon i a counting oracle which we introduce to help us isolate and analyze the exponential sum from Equation 3) We define it as:
wond of Milhaan
Σ oFVeee
2/ur lsupp(r)
1 2fr (pPPppp((lPPpoaa 0j) h 1f1"
1
(7)
I = tally (J(Doim + dt 16, (mm) -1(-" -ally (J(P, + 1]I (e,aa)))
Intuitively, the counting oracle is a function that returns the number of value assignments with exactly variables set to 1, and the label tally of the top-K K tuples will be exactly z" when 4; is included in the training dataset, and 7 when is excluded. By looking at |Equation 6 we can observe that all the sums are polynomial w.r.t. the size of data. Thus, arrive the following theorem (which we prove in Appendix E):
Theorem 4.1. we can compute the counting oracle ws as defined in w.r.f. (Derl and (Deat), then we can compute the Shapley value of tuple t; E Dir in time polynomial w.r.l [Drr and [Drat)-
Equation in time polynomial
The above theorem outlines solution of Problem 2 computing the counting oracle. Next, we cover a solution that models the problem as a model counting problem by leveraging data structure which we call Additive Decision Diagrams (ADD's) s). Counting Oracle as Model Counting over ADD's. We use Additive Decision Diagram (ADD) to compute the counting oracle wa,'' (Equation 7). An ADD represents a Boolean function Φ VA + E {oo} that maps value assignments v É VA to elements of some set E or a special invalid element oo (see Appendix Coror more details). For our purpose, we define & = {1,..., [4]} x y x yy.k
given that we can find a PTIME solution for
Then, we define a Function over Boolean inputs 6(v [tt,,, tvat, t', t!) as follows:
80.
if & Derlu a; <- 0).
plv to tost t',""
0o, (a.
if it" & Drr l0) az +- 1]. otherwise.
(8)
a= |s)p J' -tallyllll (arly(Dar(u:)) 0] (ltaa
7" := tally (Drly(Drrle: as <- 1](6" tval))

---

Published as a conference paper at ICLR 2024
Datneet: Falkmables Adult
Pipeline: Random Augment Missing Indicator K-Menns
(6) Target Model: XGBooot
Target Model:: Logistic Regression
100%
vartann saryy sheee
50%
GLL2A
20.23
60%
56.11
20%-
48%
32
20%
25%
65
10l
138%
50%
133%
197
Perten Label
po Lebda Courines
Linda Stantied
Porise Labal Daminne
Random
Datascope KNN
TMC
TMC x100
Datascope TMC
Datascope
Figure 4: Computing the Shapley value by using KNN as a proxy model can achieve comparable performance on label repair task, with orders of magnitude faster runtime.
If we can construct ADD that computes div lis Lyal, (("), then the model counting operation on that ADD exactly computes w(a, (/.a/.//. , [ tie teat: "t"). .. As the complexity of model counting is O( -EE) (see [Equation 12) and |E] is polynomial in the data size, we have the following result:
Theorem 4.2. we can represent the oi. (v) in Equation 8 Swith an ADD of size polynomial in |A] and [D/,), can compute the counting oracle Wayy in time polynomial of A| and |D/,1-
A proof is provided in Appendix E For specific canonical pipelines, we have the following corollaries.
Corollary 4.1. (One-to-Many Join Pipelines) For the K-NN accuracy utility and a one-to-many join pipeline, which takes input two datasets, Dr and DD. of total size [Dvl [Dpl N and outputs a joined dataset of size O(N), the Shapley value can be computed in O(N4) time.
Corollary 4.2. (Fork Pipelines) For the K-NN accuracy utility and fork pipeline, which takes as input dataset of size N and outputs a dataset of size M, the Shapley value can be computed in O(M2 N2) time.
Corollary 4.3. (Map Pipelines) For the K-NN accuracy utility and a map pipeline, which takes as impul dataset of size N, the Shapley value can be computed in O(N2) time.
Evaluation of Effectiveness. We evaluate our method of computing the Shapley value by using KNN as a proxy model (Figure 4). We can see that its effectiveness comparable even when applied to the task of label repair over pipelines that have different models. On the other hand, we that the computational cost is orders of magnitude lower when compared to MC methods.
EXPERIMENTAL EVALUATION
We evaluate the performance of our method by applying it common data debugging scenario label repair. The goal of this empirical study was to validate that: (1) our approximations enable significantly faster computation of Shapley values, and (2) in spite of any inherent biases, these approximations still manage to enable effective data debugging.
5.1 EXPERIMENTAL SETUP
Protocol. We conduct a series of experimental runs that simulate real-world importance-driver data debugging workflow. We developed a custom experimental infrastructure based on debench (Eyuboglu et al. 2022). In each experimental run, select dataset, pipeline, model, and data repair method. label errors, we follow the protocol of et al. 1 and Jia et al. (2021) and artificially inject 50% of label noise. We compute the importance using a validation datasel and use it to prioritize our label repairs. We divide the range between 0% data examined and 100% data examined into 100 checkpoints.
If dataset does not already have human--gnerann
each checkpoint, we measure the quality of the given model on separate test dataset using some metric (c.g. accuracy). We also measure the time spent on computing importance scores for the entire training dataset. We repeat each experiment 10 times and report the median as well as the 90-th percentile range (either shaded or with error bars).
Data Debugging Methods. We apply various methods of computing data importance:
Random Importance is a random number and thus apply data repairs in random order.
TMC x10 / x00 - Shapley values computed using the Truncated Monte-Carla (TMC)
method (Ghorbani & Zou 2019), with 10 and 100 Monte-Caria iterations, respectively.
Datascope TMC x10 x100 This applies our method of approximating pipelines using data provenance canonical pipelines to the TMC method of computing the Shapley value.
7

---

Published as a conference paper at ICLR 2024
Cetaue:: Tebtacies Acult Fiedins Scalan Medal: XGleast
Ditaoe:: rublites Adv Flodine Stardet Sucker Muke: XD
Oatimtxx for: AGQuRey
98.26
EXtA Koat cole
Con Time
547.23
5250.14
$38.86
5377.91
[p.37
3:46
0.3
4.00
115.3
0..44
-0.24
Portion
52%
Examined
0%
Labu Examined
Portion of Labeb Exarited
Portion of Libels Examined
Random
TMC 1
TMC x100
Danasoope xMC
Datascope x100
Datasoope KNN
Datasoope KNN Interactive
Figure 5: Under our framework it is possible to optimize for model quality metrics other than accuracy. Here we show a commonly used fairness metric - equalized odds difference (lower is better). Given that approximating this metric is more complex, optimal results are achieved by using
KNN Interactive which recomputes the Shapley value after each data repair checkpoint.
Datascope KNN - This is our method for efficiently computing the Shapley value over ML pipelines by using the KNN as a proxy model.
Datascope KNN Interactive - While the above methods compute importance only once at the beginning the repair process, the speed of our method allows us to recompute the importance after each data repair checkpoint.
Data Preprocessing Pipelines. We obtained a dataset with about 500K machine learning workflow instances from internal Microsoft users (Psalli) das et al., 2019). Each workflow con- sists of a dataset, data preprocessing pipeline, and an ML model. We iden- tified a handful of the most represen- tative pipelines and translated them to sklearn pipelines. All pipelines used in our experiments are listed in Table I allogg with the operators they are made up of. Some pipelines are purely canonical, while some involve a reduce operation.
Table I: Data preprocessing pipelines used in experiments.
Pigeline
Batase Medallty
Perrly Canmical
Operators
sdastry
Standard Scaler
Srandardiiaatr
Lagonthme Scaler
LogiP Standarticaler
PCA
Muuin Indicator KMdaat
tabelar
Wiansingteddcctte o itflazz
Hitto am Orianted Grodints Embodiing
Huxtrasatiom
MubiiVV Enbedding (aas & Karlopin 2012
NobsleVat
TFIDF
1251
fabe
TeatTolavee leilsaaveez
Tolower URL Romovt TFIDF
teat
file
WinLM Embodding Wasss 2017
Iesl
83c
Eanli
5.2 RESULTS
In this section, we highlight some of the most interesting results of our empirical analysis and point out some key insights that we can draw. A more extensive experimental analysis is presented in [pppendxx G We start off with three general scenarios: (1) accuracy-driven label repair: (2) fairness- driven label repair demonstrate usage of different model quality metrics; and (3) label repair in deep learning scenarios, In each one, we study the tradeoff between computational cost of any data repair approach, and the labor cost, which is measured as the amount of data repairs that need to be conducted to deliver the biggest improvement of model quality. Finally, we conduct a scalability analysis of our algorithm to showcase its potential for handling large datasets.
Improving Accuracy. In this set of experiments, our goal is to improve model accuracy with targeted label repairs. In Figure 4 we show one example workflow for the FolkUCI Adult dataset and the pipeline from Figure without the join operator. We evaluate our KNN-based method over pipelines that contain two different ML models: LogisticRegression and XGBoost. We can draw two key conclusions about our KNN-based algorithm. Firstly, given that our KNN-based method is able to achieve comparable performance to Monte Carlo-based methods, we can conclude that KNN can indeed serve as good proxy model for computing the Shapley value. Secondly, it is able to achieve this performance at only a fraction of the computational cost which makes it even more compelling.
Improving Accuracy and Fairness. Next, we explore the relationship between accuracy and faimnsss when performing label repairs. In these experiments, we use tabular datasets that have a 'sex' feature that we use to compute group fairness using equalized odds difference (Hardt et al. 2016). In/Figure 5 we explore the tradeoff between two data debugging goals the left panel illustrates the behavior of optimizing for accuracy whereas the right panel illustrates the behavior of optimizing for faimesss. We first notice that being able to debug specifically for fairness is important because for some datasets improving accuracy does not necessarily improve the fairness of the trained model. Secondly, we can see that even when we do optimize for fairness, not all methods will end up being successful. The best-performing method is Datascope KNN Interactive which is the only one that recomputes the Shapley value at each of the 100 checkpoints (due to the speed of our KNN-based method). It is likely that the complexity of the equalized odds difference metric makes it challenging to
8

---

Published as a conference paper at ICLR 2024
6) ResNet as tirget Model Datason Rcc
(b) ResNett enibeliinng as the preproeesing pipeline
(c) Matching Network in larget model
Outzsen Fistentrss
Dusscet FashoontoiST
Model RosNotLs
Hlpoiin: Resterid embodding Model Log sti Regression
Roodl Matching Netwo
2 1010
Arcuning
0.8
0.8
Compur Timel
214.00
Accurac
641.24
0.6
142.04
Compo
10
76.58
7005.86
x3.30
0%
50%
100%
0%
50%
100%
0%0.
50%
100%
Labels Examined
Fortin Labels Exam
Fortion
Labels Examined
Raadon
Dutsoogg
Danssage x10
Daussage TMC x100
Figure 6: The KNN proxy can offer effective data debugging in various deep-learning scenarios.
compute the Shapley value. Especially since some interventions on the dataset might end up shifting the optimal path, and only by recomputing are we able to detect this shift.
Deep learning pipelines. We also measured the effectiveness of our approximation methods in several scenarios that involve deep learning models. In Figure 6a we use pre-trained ResNet- 18 model as the target model. We fine-tune it for 5 epochs on noisy label dataset and see that Datascope KNN fares favorably compared to random label repair. Figure 6b) shows the result of applying pre-trained embedding model and evaluating both the Datascope KNN and the Datascope TMC approximations, where the KNN proxy again shows good performance. Finally, in [Figure 6c we show how our method can be used to repair labels of a dataset used as support set for one-shot learning neural network. We use the matching networks model (Vinyals et al. 2016) which employs a learned "distance metric" between examples in the test set and those in the support set. This allows us to replace the standard Euclidean distance metric in our KNN proxy model with a custom one and achieve effective label repairs with efficiently computed Shapley values.
Scalability. We evaluate the speed of our al- gorithm for larger training datasets. We test the runtime for various sizes of the training set (10k-1M the validation set (100-10k), and the number of features (100-1k). As expected, the impact of the training set size and validation set size is roughly linear (Figure 7. Even for
O Trn
Figure 7: Scalability analysis of our Datascope KNN Shapley algorithm over different training set, validation set, and feature vector sizes.
large datasets, our method can compute Shapley scores minutes.
RELATED WORK
Targeted data repairs have been studied for some time now. Apart from the work mentioned in section notable piece of work is CleanLab which leverages confident learning to make targeted repairs of noisy labels (Northcutt et al., 2021). Our work focuses on the Shapley value given it was shown to be applicable many scenarios (Jia et al. 2021). Apart from the data valuation scenario, the Shapley value has also been used for computing feature importance (Lundberg & Lee 2017). On the other hand, the scope of our work is data importance over ML pipelines.
Debugging data pipelines has started receiving some attention recently. Systems such as Data X-Ray can debug data processing pipelines by finding groups of data errors that might have the same cause (Wang et al. 2015). Another example is ml inspect which also uses data provenance as an abstraction for automatically analyzing data preprocessing pipelines and discovering data distribution errors (Grafberger et al. 2022). A system called Rain leverages influence functions as a method for analyzing pipelines comprising of model and a post-processing query (Wu et al. 2020). Rain also uses data provenance as a key ingredient, but their focus is on queries that take as input predictions of a model that has been trained directly on the source data.
7 CONCLUSION AND OUTLOOK
In this paper, we propose ease. ml/datascope a framework for representing a wide range of MI. pipelines that appear in real-world scenarios with the end goal of efficiently computing the Shapley value of source data examples. We show how this framework can be leveraged to provide significant speed-ups to Monte Carlo-based methods for Shapley value computation. Furthermore, we provide PTIME algorithms for computing the Shapley value using the KNN proxy model for several classes of ML pipelines. Finally, we empirically demonstrate that our methods achieve significant speed-ups over previously developed baselines while demonstrating competitive performance in a downstream data debugging task. Our code is available at gggitub.com/ccsem///aaasscp

---

Published as a conference paper at ICLR 2024
REFERENCES
Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
R Iris Bahar, Erica A Frohm, Charles M Gaona, Gary D Hachtel, Enrico Macii, Abelardo Pardo, and Fabio Somenzi. Algebric decision diagrams and their applications. Formal methods in system design, 10(2):11-2006 1997.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairml- book.org, 2019, http://www. http:/wwwwaaiaaa. fairml book book.org org
Randal E Bryant. Graph-based algorithms for boolean function manipulation. Computers, IEEE Transactions on, 100(8):677-691, 1986.
Marco Cadoli and Francesco M Donini. A survey knowledge compilation. Al Communications, 10(3, 4):137-1 1997.
James Cheney, Laura Chiticariu, and Wang-Chiew Tan. Provenance in databases: Why, how, and where. Now Publishers Inc, 2009.
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. arXiv preprint urXiv:2108.04:3 04884, 2021.
Sabri Eyuboglu, Bojan Karlaš, Christopher Ré, Ce Zhang, and James Zou. dcbench: benchmark for 1145/3533022 /
data-centric ai systems, 2022. URL httpt:ttt////oorgeeeeeee.
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning.
In International Conference on Machine Learning, pp. 2242-2251, PMLR, 2019.
Stefan Grafberger, Paul Groth, Julia Stoyanovich, and Sebastian Schelter. Data distribution debugging in machine learning pipelines. The VLDB Journal, pp. 1-24, 2022.
Todd Green, Grigoris Karvounarakis, and Val Tannen. Provenance semirings. In Proceedings of the /wenty-sizth ACM SIGMOD-SIGACT-SIGG symposium on Principles of database systems, pp. 31 40, 2007.
Moritz Hardt, Eric Price, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Informa- fion Processing Systems, volume 29, Curran Associates, Inc., 2016. URL https: httttss://proceedingt pptp.eeiicceess http:p/.....ppppoo/oo/////////as
cOd Papod-aapr.... pdf
Ihab F. Ilyas and Xu Chu. Data Cleaning. Association for Computing Machinery, New York, NY, USA, 2019. ISBN 9781 4781450375520.
Abhay Jha and Dan Suciu. Knowledge compilation meets database theory: Compiling queries to decision diagrams. ACM International Conference Proceeding Series, pp. 162- 123,133,25 2011. ISBN 978 9781450305297. doi: 10.1 145/1938551. 1938574..
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Li, Ce Zhang, Costas J Spanos, and Dawn Song. Efficient Task-Specific data valuation for nearest neighbor algorithms. In VLDB, 2019a.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos. Towards efficient data valuation based on the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1167-1176. PMLR, 2019b.
Ruoxi Jia, Xuehui Sun, Jiacen Xu, Ce Zhang, Bo Li, and Dawn Song. Scalability vs. utility: Do we have sacrifice one for the other in data importance quantification? CVPR. 2021.
Thorsten Joachims. A probabilisticc analysis of the rocchio algorithm with tfidf for text categorization. Technical report, mellon univ pittsburgh pa dept of computer science, 1996.
10

---

Published as a conference paper at ICLR 2024
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. International conference on machine learning, 70:1885- 1894, 2017.
Ron Kohavi et al. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Kdd, volume 96, pp. 202-207, 1996.
Sanjay Krishnan, Michael J Franklin, Ken Goldberg, and Eugene Wu. Boostclean: Automated error detection and repair for machine learning. arXiv preprint arXiv:/711.01299.00 2017.
Yung-Te Lai, Massoud Pedram, and Sarma B. K. Vrudhula. Formal verification using edge-valued binary decision diagrams. IEEE Transactions on Computers, 45(2):247-255, 1996.
C. Y. Lee. Representation of switching circuits by binary-decision programs. The Bell System 15311/115---77999.99
Technical Journal, 38(4):985 999, 1959. doi:
Peng Li, Xi Rao, Jennifer Blase, Yue Zhang, Xu Chu, and Ce Zhang. CleanML:: study for evaluating the impact of data cleaning ML classification tasks. In 36th IEEE International Conference Data Engineering (ICDE 2020)()) 2021.
Weixin Liang, Girmaw Abebe Tadesse, Daniel Ho, L Fei-Fei, Matei Zaharia, Ce Zhang, and James Zou. Advances, challenges and opportunities in creating data for trustworthy ai. Nature Machine Intelligence, 4(8):669- 677, 2022.
Scott M Lundberg and Su-In Lee. unitied approach to interpreting model predictions. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 4765 4774. Curran Associates, Inc., 2017.
Mark Mazumder, Colby Banbury, Xiaozhe Yao, Bojan Karlaš, William Gaviria Rojas, Sudnya Diamos, Greg Diamos, Lynn He, Douwe Kiela, David Jurado, al. Dataperf: Benchmarks for data-centric ai development. arXiv preprint arXiv:2207. 2022.
Sachin Mehta and Mohammad Rastegari. Mobilevit: Light paapnerr---ppppsseee and mobile- friendly vision transformer. 2022. URLLAtpps//aaxivvorg////////111
Curtis G. Northcutt, Lu Jiang, and Isaac L. Chuang. Confident learning: Estimating uncertainty in dataset labels. Journal of Artificial Intelligence Research (JAIR), 70: 70:1373-1411, 2021.
Fotis Psallidas, Yiwen Zhu, Bojan Karlaš, Matteo Interlandi, Avrilia Floratou, Konstantinos Karana- sos, Wentao Wu, Ce Zhang, Subru Krishnan, Carlo Curino, al. Data science through the looking glass and what we found there. arXiv preprint 10t..v:9922009555. 2019.
Nils Reimers and Iryna Gurevych. Sentence-bert Sentence embeddings using siamese bert-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. As- sociation for Computational Linguistics, 11 2019. URL,ttpp: / www.aaiww...ai..aaeooooo.ooo Sarrg/abs//ee 10084
Theodoros Rekatsinas, Xu Chu, Ihab F. Ilyas, and Christopher Ré. Holoclean: Holistic data repairs with probabilistic inference. Proc. VLDB Endow, 10(1)) aug 2017. ISSN 2150-8097, doi:
URL watp::ttp///. URthttps::/doii /ttp::://doii.ogg1//// wtt.::...r0//01.1177/////3313330 31376331
Peter Ross. Generalized hockey stick identities and n-dimensional blockwalking. The College Mathematics Journal, 28(4):325, 1997.
Scott Sanner and David McAllester. Affine algebraic decision diagrams (aadds) and their application to structured probabilistic inference. In IJCAI, volume 2005, pp. 1384-1390, 2005.
Lloyd S. Shapley. Notes on the N-Person Game I1: The Value of an N-Person Game. RAND Corporation, Santa Monica, CA, 1951. doi: 10.7249/RM0670.
L G Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8(2):189-20 January 1979.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. Advances in neural information processing systems, 29, 2016.

---

Published as a conference paper at ICLR 2024
Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. Minilm: Deep self- attention distillation for task aask-agnostic compression of pre-trained transformers. Advances in Neural Information Processing Systems, 33:5776-5788 2020.
Xiaolan Wang, Xin Luna Dong, and Alexandra Meliou. Data x-ray: diagnostic tool for data emrors. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD 15, pp. 1231-1245, New York, NY. USA, 2015. Association for Computing Machinery, ISBN 9781450327558 doi: 10.1 10.114552723372.275555999 7723372.2750549
URL httph: //tp:://do... org. 10///11.110 1145/
Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu, and Yang Liu. Learning with noisy labels revisited: A study using real-world human annotations. In International Conference Learning Representations, 2022. URL https: Siopps::/oppp //ppnevvie nnt met/forum? 1ABWAAGLLLO
Weiyuan Wu, Lampros Flokas, Eugene Wu, and Jiannan Wang. Complaint-driven training data debugging for query 2.0. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 1317-1334, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
12

---

Published as a conference paper at ICLR 2024
A DISCUSSION ABOUT THE LIMITATIONS OF PRIOR WORK
In this section, we provide a brief outline of the existing KNN approximation method for computing the Shapley value (Tia et al. 20T9a) which was instrumental in laying the foundation for applying the KNN proxy model to Shapley computation. However, as we argue in this paper; this work is not directly applicable ML pipelines as defined in this paper. Note that our goal here to offer only intuition as to why it is the case, and thus we are leaving out many technical details. In [Appendix F we present how the results in (Jia et al. 2019a) can be seen special case for computing Shapley values using the 1-NN proxy model.
The polynomial time approximation to computing Shapley values using the KNN proxy model established by Jia et al.] (2019a) relies on several assumptions that do not hold in the context of fork/join pipelines. The prediction of the KNN model (and by extension its accuracy) for any training data (sub)set is strictly dependent on the labels of the top-K data examples that are most similar to some validation example ''ull for which the KNN model is supposed to predict the label (and by extension result in measurement of the accuracy of this prediction). To compute the Shapley value of a training data example t, E Der. we need to know the accuracy difference (i.e. the marginal contribution) that occurs when adding that data example to every possible subset DD C Dtrr In simple terms, the method in (Jia et al. (0T9a) computes the Shapley value of an input data example by first sorting all data examples according to their similarity with frai. After that, it relies on the observation that in order for t, to end up in the top-K (and thus have a chance of impacting the prediction accuracy of some subset D C Dr,), of all data examples that are higher than f; in the sorting order, at most (K - 1) can be present in D. It then computes how many subsets D S Dtr of size satisfy this condition. Specifically, if t; takes the j-th position in the sorting order, then the o-K ()). Finally, includes the Shapley weighing factor along
number of such subsets is (x=1) ( with some combinatorial tricks to combine all this into simple formula:
[Dadl Σ
(1Derl -j)
l0lli baal)
(mr(u(()), loat) - m kma)) j=1
As we can see, this method strictly expects that adding 4; to any subset of Der will always result in either O or data examples being added to the top-K and that the choice between 0 and 1 strictly depends on the number of data examples that come before 4 in the sorting order. Two core assumptions lie behind this expectation: (1) adding L2 to subset of DDr will always result in exactly one additional data example being passed to KNN, and (2) the presence of any data example in the KNN training set is caused by the presence of exactly one data example in Dir. The first assumption allows us to separate data examples into those that come before 4 in the sorting order and those that come after. The second assumption allows us count subsets using binomial coefficients. If any of the two assumptions do not hold, then the simple combinatorial formula is no longer applicable because the data examples passed to KNN are no longer independent from each other. Map pipelines do not break these assumptions. On the other hand, fork pipelines break the first assumption, and join pipelines break both the first and the second assumption.
In this work, we examine the broader setting of ML pipelines which comes with several open questions. If any single training data examples t; D., is associated with e.g. 10 data examples that are passed to KNN, and they are all intertwined in the sorting order, how do we efficiently compute the number of subsets D C Drr where adding a specific data example I, will result in altering the accuracy of the KNN prediction? If a data example that gets passed to KNN is the result of joining two data examples 11,1 and 1 from separate source datasets Dj and D2, but f1,1 is also joined with other examples from D: that make up even more output data examples, so removing 22,1 from the training dataset will result in one data example not being passed to KNN but removing 11,1 will result in more than one not being passed, how do we efficiently compute the number of subsets where adding 11.1 will alter the KNN prediction? Do things change in the case of multi-class classification? Can we use model quality metrics other than accuracy? To answer these open questions, we employed all the theoretical components described in this paper, including provenance polynomials, ADD's. ss and model counting oracles. The theoretical insight we would like to convey is that all these components are fundamental to solving this problem and that this is the correct level of abstraction for analyzing ML pipelines and developing PTIME algorithms.
13

---

Published as a conference paper at ICLR 2024
B DISCUSSION ABOUT TYPES OF ML PIPELINE OPERATORS
Here we provide an overview of types of pipeline operators that can be found in ML workflows. We base this discussion on operatos that can be found in the scikit- Selkit-learcy and ML. NET frameworks, as well as commonly used operators that can be found in real-wordd ML code.
Unary Map: These are functions that map single value inputs to single value outputs. Examples include:
Log - Computes a logarithm of the input.
Missing Value Indicator - returns Boolean that indicates if the input is missing value or not
(e.g. rissinngnndiaaton in scikit-learn)
Stopword Remover takes an input list of string tokens and removes the ones that correspond to stop-words (c.g. "the". "and", etc); the list of stop words is specified as an additional argument (e.g. Remo www.aeeeeeiinnaanaaoooorooooo in ML. ME.
Binary Numerical and Logical Map: These are common mathematical operators such as addition, subtraction, multiplication, division, logical and, logical or, equality test, etc.
Multi- Map: Values containing multiple elements are taken inputs and produced outputs. A key example is a vector normalizing operator which maps a vector input to a vector output.
Tuple Filter Map: These operators remove tuples from the dataset based on the result of some unary map operation. Since these operators map a single tuple to either a single output tuple or to nothing, they categorized map filters. Examples include:
Missing Value Filter Removes tuples that contain missing values.
Range Filter- Removes tuples where values of a specified column are outside a given range.
Numerical Aggregate Reduce: This operator takes entire column and reduces into single numerical value. Examples include summation, counting, mean value, standard deviation, as well as minimal and maximal element selector operators.
Unary Map with Reduce Elements: These operator function similarly to regular unary map operators. However, their mapping operation is dependent on performing some numerical aggregate reduce operation beforehand. Examples include:
Min-Max Scaler Scales column values to a 0-1 range based on minimal and maximal element values which represent the pre-computed reduce element (e.g. MinMaxScaler in sci scikit-learn).
Standardization Scaler Same as the min-max scaler but transforms elements based on the pre-computed mean and standard deviation values (e.g. Standar in scikit-learn) One-Hot Encoder- Encodes numerical features as a one-hot numerical array. Depends on a pre-computed list of unique column element values.
TD-IDF Encoder Converts textual values into their Term Frequency Inverse Document Frequency encodings. This operator depends on a pre-computed dictionary token frequencies.
Data Augmentation Fork: This can be any data augmentation operator that maps input tuples to some specified number of output tuples. Examples include: random noise injection, randomly shifting or rotating images, removing or replacing characters in text to simulate misspelling, etc.
One-to-Many Join: Join operators compute matching between two sets of tuples DA and Dn, and for each pair matched input tuples produce a single output tuple. In general there are no constraints on the kinds of matchings that can be performed. However, the specific type of join we describe here, referred to as one-to-mant matched with at most one tuple from the other set (c.g. DB). At the same time, tuples from DB can be matched with multuple tuples from DA-
type join requires that tuples from one of the two sets (c.g. DA) can be
C PRELIMINARY: ADDITIVE DECISION DIAGRAMS (ADD's)
In this section, we describe a type of decision diagram that we use as a tool for compact representation of functions over Boolean inputs. The process of translating functions into data structures for easier analysis is referred to as knowledge compilation. We briefly describe this in the context of our work, and then go over the data structure we use our methods Additive Decision Diagrams.
Knowledge Compilation. Our approach to computing the Shapley value will rely upon being able to construct functions over Boolean inputs VA E, where is some finite value set. We require an elementary algebra with +, and operations to be defined for this value set. Furthermore, require this value set contain zero element O, as well as invalid element co representing
14

---

Published as a conference paper at ICLR 2024
an undefined result (e.g. result that is out of bounds). We then need to count the number of value assignments v E VA such that Φ(v) = e, for some specific value e E E. This is referred to as the model counting problem. which is #P complete for arbitrary logical formulas Valiant (1979); AAooa & Barak (2009). For example, if A = { 022 az). we can define & = {0. 1, 2,3, 3, oo to be a value set and function <(v)= == v((1)) ) + e ((2)) + v(a3) corresponding to the number of variables in A that are set to 1 under some value assignment E VA-
Knowledge compilation Cadoli & Donini (197)) has been developed as a well-known approach to tackle this model counting problem. It was also successfully applied to various problems in data management Tha & Suciu (20TT). One key result from this line of work is that, if we construct certain polynomial-sizz data structures to represent our logical formula, then we can perform model counting in polynomial time. Among the most notable of such data structures are decision diagrams, specifically binary decision diagrams Lee (1959); Bryant (986) and their various derivatives Bahar al. (1997); ;: [annner & McAllester (2005); Lai et al. (1996). For our purpose in this paper, we use the additive decision diagrams (ADD), as detailed below.
Additive Decision Diagrams (ADD). We define simplified version of the affine algebraic decision diaggrams/Saner
[Snnner & McAllester (2005). An ADD is a directed acyclic graph defined over a set of nodes N and special sink node denoted E. Each node A is associated with a variable a(n) E A. Each node has two outgoing edges, (1.) and c#r (n), that point to its low and high child nodes, respectively. For some value assignment v, the low/high edge corresponds to v(a) (/v(a) 1. Furthermore, each low/high edge is associated with an increment wr/wH that maps edges to elements of &
Note that each node n E / represents the root of a subgraph and defines a Boolean function. Given some value assignment n and at each step moving towards the low or high child depending on whether the corresponding variable is assigned 0 1. The value of the function is the result of adding all the edge increments together. [Figure 8a presents an example ADD with one path highlighted in red. Formally, we can define the evaluation of the function defined by the node n as follows:
VA we can evaluate this function by constructing path starting from
0,
if D. if v(((n))== = 0, if ((((n))= 1.
cval. (n) == wp (n) + eval, (c)(n))
wn (n) + (en),()e(n))
In our work, we focus specifically on ADD's that are full and ordered. A diagram is full every path from root to sink encounters every variable in A exactly once. For example, in Figure Sal we see full diagram over the set of variables variables in A has no node associated with it, then the diagram is not considered full. On the other hand, an ADD is ordered when on each path from root to sink variables always appear in the same order. For this purpose, we define
{e1,1, 21,2; 02,1, 02.3). If any of the
A { A to be permutation of variables that assigns each variable a E A an index. For example, in Figure Sa the variable order is = {a1,1 + 1, 41.2 H 4, 02,1 + 02.2 3, 0223 + 5}. It is possible, for example, to swap the two nodes on the left side that correspond to 02,1 and 2222. This, however, makes the diagram unordered, which dramatically complicates certain operations (e.g. the diagram summation operation that we will describe shortly).
Diagram Diameter. We define the diameter of an ADD as the maximum number of nodes associated with any single variable. Formally we can write:
diam(A) = max {m E E = = a:}l a,
(10)
We can immediately notice that the size of any ADD with set of nodes / and variables A is bounded by O[[A| diam(N))).
Model Counting. We define a model counting operator
(ount,(n) : Kr Valsa((())) (n) = e}|-
(11)
where AlS x[a(n))] is the subset of variables in A that include a(n) and all variables that come before it in the permutation æ. For an ordered and full ADD, count, (n) satisfies the following recursion:
1,
if e = and n E,
count, (n) :=
0,
if e = 0a or n = E, (12)
wy countt-wy we (m) (c)(n) + counte-wyn (n),
otherwise.
15

---

Published as a conference paper at ICLR 2024
(a) ADD
(b) Uniform ADD
01,1
@1
+5
2221
+5
0,2
03
+5
01,
2233
Figure 8: (a) An ordered and full ADD for computing d(v) == v(01.1) (v(a2.1) + v(a22)) +
v(01.2) o(a2,)). (b) A uniform ADD for computing d(v) == 5 (v((r) + v(a2) - v(aa)).
The above recursion can be implemented as a dynamic program with computational complexity O(AA--187
Figure 8b) shows a special case of full and ordered ADD, which we call a uniform ADD. It is structured as chain with one node per variable, where all low increments equal zero and all high increments equal some constant E &. For this type of ADD, we can perform model counting in constant time, assuming that we have precomputed table of factorials of size O that allows us to compute binomial coefficients in constant time. The count, operator for a uniform ADD can be defined as
if e mod = 0,
count (n) =
e/B
(13)
otherwise.
Intuitively, if we observe the uniform ADD shown in Figure 8b we see that the result of an evaluation must be multiple of 5. For example, to evaluate to 10, the evaluation path must pass a high edge exactly twice. Therefore, in a 3-node ADD with root node ngg the result of countau (1 will be exactly (2).
Special Operations on ADD's. Given an ADD with node set M,, we define two operations that will become useful later on when constructing diagrams for our specific scenario:
1. Variable restriction, denoted as V[a; + V), which restricts the domain of variables A by forcing the variable a; to be assigned the value V. This operation removes every node n E N where a(n) = a, and rewires all incoming edges to point to the node's 's high or low child, depending on whether V than the original diagram, depending on the number of nodes associated with variable 0;-
V 0. The resulting diagram will have between and diam(N) nodes less
Diagram summation, denoted as A₁ + N2. where Mi and N2 are two ADD's over the same (ordered) set of variables A. ordered in the same way. It starts from the respective root nodes 71 and 122, and produces a new node n = 71 + 722. We then apply the same operation to child nodes. Therefore, cz (n1 + 712) := (z4) + ez (12)) and cи (ni + n22) cu (n₂) + cn (12). Also, for the increments, we can define wt (n; + n22 == wi (n1) + ww (nz) and wH (n1 + n22 == wh (n1) w (nz). The size of the resulting diagram is bounded by (((Am)d (iimmNN))diia(NN) A proof of this claim is presented in (subsectioon E.2
D CONSTRUCTING POLYNOMIAL SIZE ADD's FOR ML PIPELINES
Algorichm presents our main procedure COMPILEADD that constructs an ADD for given dataset D made up of tuples annotated with provenance polynomials. This is achieved by invoking the procedure COMPILEADD(D, A, t, tval) constructs an ADD with node set N that computes
if g D(w)), d(v ta, tvol, t') = tally (D[u) tt', twat, otherwise.
oc,
(14)
16

---

Published as a conference paper at ICLR 2024
Algorithm I Compiling a provenance-tracked dataset into ADD.
1: function COMPILEADD
2: inputs
3:
D, provenance-tracked dataset;
4:
A, set of variables;
5:
t, boundary tuple;
6:
Leat validation tuple;
7:
outputs
8:
N, nodes of the compiled ADD;
9:
begin
10:
N + O
P (011, 02) E Et, e eD E p(t)) ag E p(t)))
12:
AL & GETLEAFVARIABLES())
for AC E GGTCCONNCCTRICOMMPNENTSS)S)) do A' +- Ac
14:
15:
N" + CONSTRUCTADDTREIAA) D' + E p(t') Ac # #0}
16:
17:
for v E VV do
18:
No t CONTRRCCAADDCHAINGAS AL)
19:
for n E No do o' uU (a(n) +} wn(n) + 1||l E eval,)(((') = A 2oll,hal 2 (lis, beat) end for A + APPENOTOADDPATHU No.
20:
21:
23:
end for N + APPENDTOADDDOOOTU..N
25:
26:
end for
27:
for a'
E p(t) do for E where a(n) = a' do (n)
28:
29:
30:
end for end for
31:
32: return /
end function
We provide more detailed description of Alglogti in subsection D.1
To construct the function defined in Equation 8) we need to invoke COMPILEADD once more by passing t" instead of t' in order to obtain another diagram A The final diagram is obtained result of (a <- 0] + +" + 1]. In other words, by performing diagram summation operation over diagrams A (with variable restriction a; <- and A (with variable restriction a; 1). The size of the resulting diagram will still be bounded by O(PP)).
We now examine different types of canonical pipelines and see how their structures reflected onto the structure of ADD's. summary, we can construct an ADD with polynomial-siz for canonical pipelines, and therefore, by Theorem 4.2 the computation of the corresponding counting oracles PTTME.
One-to-Ne ane-to-Many Join Pipeline. In star database schema, this corresponds to a join between a fact table and a dimension table, where each tuple from the dimension table can be joined with multiple tuples from the fact table. It can be represented by ADD similar the one in Figure Sa
Corollary D.1. For the K-NN accuracy utility and a one-to-many join pipeline, which takes as input two datasets, DD and DD, of total size [Dpl |Dpl = N and outputs joined dataset of size O(N), the Shapley value can be computed in O(N*) time.
Proof. This follows from the observation that in Algorithm each connected component Ac will be made up of one variable corresponding to the dimension table and one or more variables corresponding to the fact table. Since the fact table variables will be categorized "leaf variables", the expression Ac \ Ar. in Line [4 will contain only a single element the dimension table variable. Consequently, the ADD tree in N will contain single node. On the other side, the Ag O Ar expression will
17

---

Published as a conference paper at ICLR 2024
contain all fact table variables associated with that single dimension table variable. That chain will be added to the ADD tree two times for two outgoing branches of the single tree node. Hence, the ADD segment will be made up of two fact table variable chains stemming from a single dimension table variable node. There will be ((Dp) partitions in total. Given that the fact table variables are partitioned, the cumulative size of their chains will be O((r))) Therefore, the total size of the ADD with all partitions joined together is bounded by O(Ppb + [Drl] = O(N).
Given fact and combining it with Theorem 4.2 we know that the counting oracle can be computed in time ((N) time. Finally, given Theorem 4.1 and the structure of Eqquation 6 we can observe that the counting oracle is invoked ((N)) times. As result, can conclude that the total complexity of computing the Shapley value is O(N*). Here, we assume that we have a precomputed table of factorials from 1 to N that allows us compute the binomial coefficient in constant time.
Fork Pipeline. The key characteristic of a pipeline f that contains only fork or map operators is that the resulting dataset f (D) has provenance polynomials with only a single variable. This is due to the absence of joins, which are the only operator that results in provenance polynomials with a combination of variables.
Corollary D.2. For the K-NN accuracy utility and a fork pipeline, which takes as input a dataser of size N and outputs dataset of size M, the Shapley value can be computed in (M² N2) time.
Proof. The key observation here is that, since all provenance polynomials contain only a single variable, there is no interdependency between them, which means that the connected components returned in Line I3 of Algorithm I will each contain a single variable. Therefore, the size of the resulting ADD will be O(N). Consequently, similar to the proof of the previous corollary, the counting oracle can be computed in time O(N) time. In this case, the size of the output dataset is O(M) which means that Equation 6 will invoke the oracle O(M²N) times. Therefore, the total time complexity of computing the Shapley value will be O O(M3 N²) Here, we assume that we have precomputed table of factorials from to N that allows us to compute the binomial coefficient in constant time.
Map Pipeline. A map pipeline is similar to fork pipeline in the sense that every provenance polynomial contains only single variable. However, each variable now can appear in provenance polynomial of at most one tuple, in contrast to fork pipeline where a single variable can be associated with multiple tuples. This additional restriction results in the following corollary:
Corollary D.3. For the K-NN accuracy utility and a map pipeline, which takes as input a dataset of size N. the Shapley value can be computed in O(N2) time.
Proof. There are two arguments we need to make which will result in the reduction of complexity compared to fork pipelines. The first argument is that given that cach variable can appear in the provenance polynomial of at most one tuple, having its value set to 1 can result in either zero or one tuple contributing to the top-K tally. It will be one if that tuple is more similar than the boundary tuple and it will be zero if it is less similar. Consequently, our ADD will have a chain structure with high-child increments being either 0 or 1. If we partition the ADD into two chains, one with all increments 1 and another with all increments O, then we end up with two uniform ADD's. As shown in Equation 13] model counting of uniform ADD's can be achieved in constant time. The only difference here is that, since we have to account for the support size of each model, computing the oracle w w(a 7 2" (4, twat, 1,, (") for given a will require us to account for different possible ways to split a across the two ADD's. s. However, since the tuple L needs to be the boundary tuple, which means it is the K-th most similar, there need to be exactly K- - 1 variables from the ADD with increments 1 that can be set to 1. This gives us a single possible distribution of across two ADD's. Hence, the oracle can be computed in constant time.
As for the second argument, we need to make simple observation. For map pipelines, given a boundary tuple i' and a tally vector ' corresponding to the variable a; being assigned the value O, we know that setting this variable to can introduce at most one tuple to the top- That could only be the single tuple associated with a; If this tuple has a lower similarity score than t', there will be no change in the top-K. On the other side, if it has higher similarity, then it will become part of the top-K and it will evict exactly t' from it. Hence, there is a unique tally vector ?" resulting from a, being assigned the value 1. This means that instead of computing the counting oracle w(a 7 / it. Ewat, ft)). we can compute the oracle w(a, 7 [t,,, toat, t'). This means that, in Equation 6 we can eliminate the iteration over t" which saves us order of O(N) in complexity.
18

---

Published as a conference paper at ICLR 2024
As result, Equation will make ( invocations to the oracle which can be computed in constant time. Here, we assume that we have a precomputed table of factorials from to N that allows us to compute the binomial coefficient in constant time. Hence, the final complexity of computing the Shapley value will be O(N2).
[T
D.I DRTAILS OF ALGORITHM
In this section, we examine the method of compiling a provenance-tracked dataset (Drr) that results from a pipeline f. The crux of the method is defined in inAloorithmm which an algorithm that takes a dataset f (rr with provenance tracked over set of variables A, a boundary tuple t' (Drr) and a validation tuple lyat E ((Dvat). The result is an ADD that computes the following function:
600
if t' & f(Prrlu)), (f I teat), otherwisc.
Φ(v li, leat, (')
(15)
Assuming that all provenance polynomials are actually a single conjunction of variables and that the tally is always a sum over those polynomials, it tries to perform factoring by determining if there are any variables that can be isolated. This is achieved by first constructing the set of "leaf variables" AL (Line 12 No pair of variables in AL ever appears in the same provenance polynomial. In graph theory, this set is also known as the "independent set". We use a heuristic approach to construct this set that prioritizes the least frequently occurring variables and completes them in O(N) time. We then iterate over each "connected component" Ac (Line (3) where any two variables are "connected" if they are ever in the same provenance polynomial. Then we get the set A'' Ac Ar which contains variables that cannot be isolated (because they appear in polynomials in multiple tuples with multiple different variables). We form group that will be treated one binary vector and based on the value of that vector we would take a specific path in the tree. We thus take the group of variables and call the CONSTRUCTADDTRER function to construct ADD tree (Line [5].
Every path in this tree corresponds to one value assignment to the variables that tree. Then, for every path we call the CONSTRUCTADDCHAN to build chain made up of the isolated variables and call APPENDTOADDDATTE to append them to the leaf of that path (Line 23). For each variable in the chain, we also define an increment that is defined by the number of tuples that will be more similar than the boundary tuple t' and also have their provenance polynomial "supported" by the path. We thus construct segment of the final ADD made up of different components. We append this segment to the final ADD using the oppnnToADDRoor function. We don't 't explicitly define these functions but we illustrate their functionality in Figure 9
E ADDITIONAL. PROOFS AND DETAILS
E. PROOF OF THEOREM 4.1
Proof. This theorem can easily be proven by observing the structure of the Shapley value of tuple 1, for a single validation tuple Leat, as we defined in [Equation 6)
p(t,, (val) 1े. Ee.rEs Eld, (44-1) Enareryy ma(''s>" feat) a/fa,ninn [t, tyat, t", ,t"".
We can notice that it made up of several sums: (1) the left-most one a sum over t' ," (Drr)
which for a canonical pipeline f is a set of cardinality in O(Drrr)): (2) the next one is a sum over |A elements which is O(DD.r according to the definition of A given in inssusecctinn 3.1 and finally (3) the right-most sum is over 7 E yy where Ty x is the set of all [lI diddeennsoo label tally vectors which can be defined as I'y.k == (7 E ND', K > Y. and can be treated as constant since it does not depend on [D.r As we can see, given that all sums in ppt,, bmat) are O )). then it is safe to conclude that if we can compute w(a, 7', 7" le Laal L,, (,") in time polynomial w.r.t [Derl, then we can also compute (tt,, teal) in time polynomial in [Derl. Finally, as mentioned in the Shapley value for tuple t, can be computed as (t,t)) = Et..re/D.... sp(t,, twal) which contains a sum over O(D elements (given that the pipeline f canonical). Hence, we can see that the Shapley value can be computed in time polynomial in |Drrl and (Deatl, which concludes our proof.
E.2 PROOF OF THEOREM 4.2
Model Counting for ADD's, We start off by proving that Equation 12 correctly performs model counting.
19

---

Published as a conference paper at ICLR 2024
Mi CoNTRuCZADDTees(000..00
N2s CONTBLCIADDCCAAIN (24,
0/2
05
Q3
Q6
A (ug + 1,02 0, + 1})
A
Q1
a1
0/
0/2
0g
03
011
04
05
(15
06
06
Figure 9: An example of ADD compilation functions.
Lemma E.1. For a given node n E N of an ADD and a given value E E, Eqqution 12 correctly computes count (n) which returns the number of assignments E V. such that eval, (n) Furthermore, when computing counte(n) for any n E N, the number of computational steps is bounded by O(N 18))
Proof. We will prove this by induction on the structure of the recursion.
(Base case.) Based Equation 9 when El get eval,, (n) for all u. Furthermore, when EI the set V (4>))(((x)) 0] contains only one value assignment with all variables set to zero. Hence, the model count will equal to only for and will be otherwise, which reflected in
the base cases of Eqqutton 12
(Inductive step.) Because our ADD is ordered and full, both (n) and cH (n) are associated with the same variable, which is the predecessor of a(n) in the permutation æ. Based on this and the induction hypothesis, assume that
count--wzke (c)(
(A(Satez(m)) (vall(cc(m)) -
(m)
(16)
{ VAlSa(en(mM) eval, (CH (n)) = wn(m))
count (w)
We would like to compute (n as defined in Equation 11 It computes the size
defined
over possible value assignments to variables in A|S a(n)). The set of value assignments can be partitioned into two distinct sets: one where a(n) <- 0 and one where a(n) <- We thus obtain the following expression:
counta(n) = E VAISa(w)) (an)) + 0] eeval.
(17)
( V VA(Sa(m)) (a(n) +- 1 evall. =e)
20

---

Published as a conference paper at ICLR 2024
Based on Equation
we transform the (n) expressions as such:
count, (n) : V E (A[sa(e((M)) (n(n) + (cr))()((n)) = =c]
(18)
+ { Valgaten.(M)) (n) + eval (c (n)) - e
Finally, we can notice that the set size expressions are equivalent to those in Equation 16 Therefore, we can obtain the following expression:
count, (n) == count (onnt()))(((((((m))) + (n)
(19)
which is exactly the recursive step in |Equation 12 This concludes our inductive proof and we move onto proving the complexity bound.
(Complexity.) This is trivially proven by observing that since count has two arguments, we can maintain a table of results obtained for each n E N and e E E. Therefore, we know that we will never need perform more than O(M - | invocations of count, (n)..
ADD Construction. Next, we prove that the size of an ADD resulting from diagram summation as defined in Appendix Cis linear in the number of variables.
The size of the diagram resulting from sum of two diagrams with node sets Ni and N2 can be loosely bounded by O assuming that its nodes come from a combination of every possible pair of operand nodes. However, given the much more narrow assumptions we made in the definition of the node sum operator, we can make this bound considerably tighter. As mentioned in Appeeddix C the size of any ADD with set of nodes N and variables A is bounded by O[[A] diam(N)). We can use this fact to prove a tighter bound on the size of an ADD resulting from a sum operation:
Lemma E.2. Given two full ordered ADD's with nodes Nr and N2. noth defined over the set of variables A, the number of nodes in N1 + N2 is bounded by O(|A) diam(NN)) diam(NN)).
Proof. It is sufficient to show that (Nim(Ni + N22 O(diam(Ni) diam((V2)). This is direct consequence of the fact that for full ordered ADD's the node sum operator is defined only for nodes associated with the same variable. Since the only way to produce new nodes is by merging one node N1 with one node in N2, and given that we can merge nodes associated with the same variable, the number of nodes associated with the same variable in the resulting ADD equals the product of the corresponding number of nodes in the constituent ADD's. Since the diameter is simply the upper bound of the number of nodes associated with any single variable, the same upper bound in the resulting ADD cannot be larger than the product of the upper bounds of constituent nodes.
O
Computing the Oracle using ADD's. Finally, we prove the correctness of Theorem 4.2
Lemma E.3. Given an Additive Decision diagram with root node nili, Loat, (',") that com- putes the Boolean function d(vlli, bnat, 1', as defined in Equation 8 the counting oracle w(a, y', It tval, t',, t") defined in Equation can be computed as:
w(a, 7 Iti, tratt tt, f²,t")= == count( (n((,, twal, t(t"))
(20)
Proof. Given a training dataset Drr and a data preprocessing pipeline f, we have f(Dr,, as the output of that pipeline and input to an MI. model. Let us define [(DD,,
(') S ((Dr,) as a set of tuples in (DDr)) with similarity to a validation tuple Eval higher or equal than that of t', formally (D.,)) ([P)))ZZtttttd Zatstaet) t == {t" E f(Dr)) : att", fraa)) 2 (fat)) Similarly to fDDr.). the semantics of ((P ((Prr)(2o(-ttn (o((-)na)) ('] is also that of a set of possible candidate sets. Given a value assignment v. can obtain ((Der(v)([oo f(Drr) (2a(() t'[[= y] as a subset of [(Dr.) (Zattenn)) t'] with only tuples that have label y. Given these definitions, we can define several equivalences. First, for topx we have:
E') from [(Drr(u)). For convenience, also define
( to= (f(Ptrl))))) kwa))) - ("' (I'E A ( ((errDDa)))/rr(rb)bb)))))))>l
1T] =]]=K]] K)
(21)
In other words, for t' to be the tuple with the K-th highest similarity in ff f(Drr [u]). it needs to be member of f(Der (o]) and the number of tuples with similarity greater or equal to has to be exactly K. Similarly, we can define the equivalence for tally(-]t', (wat):
(>' tally (f (f (u]) It', teet) = (vy V,ny = (Prr &1|== vl) (22)
21

---

Published as a conference paper at ICLR 2024
This is simply an expression that partitions the set f(D [ul)] (t(r) En based y and tallies
them up. The next step is to define an equivalence for (t' = topk (Drrlo) (eat)) A (7/ = (D 1', vaat) We can notice that since h'1 K, if we have (vy E V. d']l = K) is
''][= w|]) then we can conclude that (I redundant. Hence, we can obtain:
(e== ([=xopx[[DDrlell bmil) x (f' (ally(/((DDD)))) C. (.tma)) = ((Dulti) (vv V. =
1 [/Dnllll) =||= all) (23)
According to Equation 22 we can reformulate the right-hand side of the above equivalence as:
(e' toop (nai)) (1' talll (e. (e' s(D..lll)) A (f' tally d. taa)
(24)
We can construct a similar expression for t' and via; so we cover four out of five predicates in Equation 7 The remaining one is simply the support of the value assignment e which we will leave intact. This leaves us with the following equation for the counting oracle:
w',,"' 22 ta
Σ KEMayo))
1{a= = (uupp(e))
-1
r = tupi (/(D) + 0)) hwi)) f- 111"== (/(plle) + 11) [eae)
/ tally (nly((((++/15a + 0)) 12, kmnd) }. 1f7" tally ([(airl 11) Ama))
(25)
We can use the Boolean function @buil, loat, ((,) in Equation 8 to simplify the above equation. Notice that the conditions t' E (D (u; 02 < 0]) and E" E f(D,, [V; aj < -1]) are embedded in the definition of o(vlt,, t', tt") which will return oo if those conditions are not met. When the conditions are met, @(ult,, tval: tt'tt) returns exactly the same triple (a, 7"). Therefore it is safe to replace the five indicator functions in the above formula with single one such:
w(a, 7 to tool, t,tt)))== (.t"===
E DEVANO))
1(aa = d(ult, tral, t,t²}}}
(26)
Given our assumption that dbvlli, 1', (") can be represented by an ADD with root node n(4,, loat, 1,, ,,"), the above formula is exactly the model counting operation:
w(a, ,',7" be tvat i', 1,t") == count (n(te, teat, (("")
(27)
Theorem E.1. If we can represent the Boolean function Φlv tt, teat, t', t") defined in Equation with Additive Decision Diagram of size polynomial in |Drel and [f )) then we compute the counting orucle wi(: l4, buat, 1', (!)) ) in time polynomial in [Dtel and (Drr)]
Proof. This theorem follows from the two previously proved lemmas: Lemma E. and Lemma E.3 Namely, as a result of [emma E.3 we claim that model counting of the Boolean function p(v) t,. fvai, t', t²") equivalent to computing the oracle result. On top of that, as a result of Lemmm E. we know that we can perform model counting in time linear in the size of the decision diagram. Hence, if our function pfolt, tvat, t', t²) can be represented with a decision diagram of size polynomial in the size of data, then we can conclude that computing the oracle result can be done in time polynomial in the size of data.
E.3 DETAILS ON ADDITIVE MODEL QUALITY METRICS
False Negative Rate Apart from accuracy which represents a trivial example of an additive utility, we can show how some more complex utilities happen be additive and can therefore be decomposed according to to/Equttion 5) As an example, we use false negative rate (FNR) which can be defined as such:
m(Der, Deat)= Eltat 1[(A f( (tvr)) = (3 = =}
(28)
(teal E Deat y(toat) = 1}
22

---

Published as a conference paper at ICLR 2024
In the above expression we see that the denominator only depends on Dyat which means it can be interpreted as the scaling factor w. We can easily see that the expression in the numerator neatly fits the structure of Equutioon 5 as long 0} (Yeat = }.. Similarly, we are able to easily represent various other utilities, including: false positive rate, true positive rate (i.e. recall), true negative rate (i.e. specificity), etc. We describe an additional example in (subsection 3.3
we define mr mr (ypperdd: (Irats Mrat)) := 1 Vyrred
Equalized Odds Difference We show how slightly more complex utilities can also be represented as additive, with a little approximation, similar to the one described above. We will demonstrate this using the "equalized odds difference" utility, measure of (un)fairness commonly used in research Hardt et al. (2016); Barocas et al. (2019) that we also use in our experiments. It can be defined as such:
ml ((Drr Deat) == max (ax
FPRA Dval)-
(29)
Here, TPRA and FA are true positive rate difference and false positive rate difference respec- tively. We assume that each tuple for E (D,,.) and tool E (Da have some sensitive feature g (e.g. ethnicity) with values taken from some finite set {G1, G., that allows us to partition the dataset into sensitive groups. We can define TPRs and FPRA respectively
TPRa (Dtr: Deat)= == max (PRG,(Din Deat) min TPRG, (Drr, Dual), and GjEG
G,EG
(30)
FPRA(Dir. Deat)= == max FPRG, (Dtr, Deal) - min F.R (Dir. Deat). GGEG
G.EG
For some sensitive group Gú we define TPRc, and FPRG, respectively as:
TPRo, Doat)= = ElmntE(i)..)) 1((40 1((A= ((eat)
= (y((va)) = =1]1gg(tra) = Gi} and
Heval E Deal : 8 = 1 A g((vat) = GG:ll
PPRa,(Drn Deat) EiaeESiDea 1((A0 ((taa) = 111( = =0}1(g(tral) = Gi}
Heval E Dout : ((val)) = A g(vvat) = GG:H
For a given training dataset Dtr. we can determine Equation whether TPRs or FPRA is going to be the dominant metric. Similarly, given that choice, (Gmaz, Gmin) that would end up be selected as minimal and maximal in Eqqatton 30 Similarly to the conversion shown in subsecttionn 3.3 we can treat these two steps as a reduce operation over the whole dataset. Then, if we assume that this intermediate result will remain stable over subsets of Der. we can approximatly represent the equalized odds difference utility as an additive utility.
determine pair of sensitive groups
As an example, let us assume that we have determined that TPRA dominates over FPRA. and similarly that the pair of sensitive groups (Gmaz; Gmia) will end up being selected in Equation 30 Then, our tuple-wise utility ur and the scaling factor w become
mr (ypred vaa) = TPRG.... (Vppeed twat) TP RG m... I' (Upreds tral),
W: = 1/l(tral E Dual y(tval) = 1 ^ (foaa) Gi)l.
where
TPRG, (Ypred, tval) = [ypred ()1(y(teal) = ()1 (/ G.).
A similar approach can be taken to define my and w for the case when FPR dominates over TPR3. Then, if we plug them into Equation 5] we obtain an upproximate version of the equalized odds difference utility as defined in Equation 29 This approximation relies on the stability of the choices of min and max in Equation 30)and on the choice between PR and FPR in Equation 29) (both of which can be precomputed).
F SPECIAL CASE: COMPUTING SHAPLEY FOR 1-NEAREST-NEICHBON CLASSIFIERS
We can significantly reduce the time complexity for I-NN classifiers, important special case of K-NN classifiers that is commonly used in practice. For each validation tuple Eyol, there is always exactly one tuple that is most similar to trat- Below we illustrate how to leverage this observation to construct the counting oracle. In the following, we assume that a, is the variable corresponding to the tuple for which we hope to compute the Shapley value.
23

---

Published as a conference paper at ICLR 2024
Let di represent the event when t is the top-1 tuple:
Φ p(t)
A
-p(t))
(31)
(EE((D.)) o{t))a(())
For Equation to be true (i.e. for tuple to the top-1), all tuples t' where att)) > (t) need be absent from the pipeline output. Hence, for given value assignment v, all provenance polynomials that control those tuples, i.e., p(t'), need evaluate to false. We now construct the event
ΦL == di (a;/// ^ de (o:lo//true]
where p.[a;/falser means to substitute all appearances of a, in o, to false. This event happens only if is the top-1 tuple when a; is false and t' is the top-1 tuple when a, is true. This corresponds to the condition that our counting oracle counts models for. Expanding òi,e, we obtain
ΦL. == pp(t) A
A
pp(t") [at/alse]] A (ptt)a
A
-p(t") (ar))aaa/ttues (32)
(eE((D()) a(t))>a((1)
("e)(D..) a(t))>a(t))
Note that drr can only be true if p(()) ) is true when o; is true and (() < a(').. As a result, all provenance polynomials corresponding to tuples with higher similarity score than that of need to evaluate to false. Therefore, the only polynomials that can be allowed to evaluate to true are those corresponding to tuples with lower similarity score than f. Based on these observations, we can express the counting oracle for different types of ML pipelines.
Map Pipeline. In map pipeline, the provenance polynomial for each tuple f(Drr) ) is defined by a single distinct variable ag E A. Furthermore, from the definition the counting oracle (Equation 7). we can see that w Eval, t")")) counts the value assignments that result in support size a and label tally vectors 7 and 7" Given our observation about the provenance polynomials that are allowed to be set to true, we can easily construct an expression for counting valid value assignments. Namely, we have to choose exactly a variables out of the set {t' E f(Drr) at',, tval) < (ts, teat) }, which corresponds to tuples with a lower similarity score than that l, (measured by similarity function r). This can be constructed using binomial coefficient. Furthermore, when K = 1, the label tally y entirely determined by the top-1 tuple l'. The same observation goes for r" and 1", To denote this, define constant I'L parameterized by some label L. It represents tally vector with all values and only the value corresponding to label L being set to We thus need to fix 7 to equal to observed earlier, when computing w w-Ilti, baal, t', t") for K = 1, the provenance polynomial of the tuple !" must equal a, With these notions, can define the counting oracle as
T w(t)) (and the same for 7"). Finally,
toat, t't (111" E f(Drr) o(t" (vaat) < (14, (oal))) w(a, "...".n""/ teat
lpp(t)) = as}
11/ = =ry(e}}
117" =I -I(eer> }.
(33)
Note that we always assume (%) = for all a < b. Given this, we can prove the following corollary about map pipelines:
Corollary F.1. For the 1-NN accuracy utility and a map pipeline, which takes as input a dataset of size N, the Shapley value be computed in O(N log N) time.
24

---

Published as a conference paper at ICLR 2024
Proof. We start off by plugging in the oracle definition from Equation 33 into the Shapley value computation Equation 6
(lti, (vat)
Σ
1=1)=
N
Σ <o""
ma ma(?' 7
N
(1tt =((Dr) : o(t",, ,tea)) < altss ((al)))
a
((((t") ai}
1(7 = y(r)
1("" = {
(34)
As we can see, the oracle imposes hard constraints on the tuple t" and tally vectors y and y". We will replace the tally vectors with their respective constants and the tuple t" we will denote t; because it is the only tuple associated with a. Because of this, we can remove the sums that iterate over them:
1 N
(>=))
N
N 1==))=
(1(1" E E ((D.)) olt", (vat) alti (oat:
(p(t. fval)
Σ
ma(T m(r Pote) (aai)
(Ef(DDe)
(35)
We could significantly simplify this equation by assuming the tuples in f(D) are sorted by decreasing similarity. then obtain:
N
N
N 1 m& (T (it Fe feat)
N (N-
(tc, tval)
=
(36)
N 1=1
0=1
We shuffle the sums a little by multiplying with (N-1)- and we expand ma based on its definition in subsection E.I We also alter the limit of the innermost sum because N - j. Thus, we obtain:
1
N (N-)
(l lval)
Σ (It) - mr (2(5)) bvat))
Σ
(37)
The innermost sum in the above equation can be simplified by applying the so-called Hockey-stich
identity Ross 1997). Specifically, (~) (N=))) becomes (?) -1 (N, Then, EN becomes
(2) -1 (N-a)
(+1). Finally, we obtain the following formula:
N (1-1))
ptt,, tvat) (mr(y(t)), mr(ylty), teai))
(38)
As we can see, the above formula can be computed O(N) iterations. Therefore, given that we still need sort the dataset beforehand, the overall complexity of the entire Shapley value amounts to O(N log N). Here, we assume that we have a precomputed table of factorials from to N that allows us compute the binomial coefficient in constant time.
Computing the Shapley Value for the Entire Training Dataset. Equation 38 represents method for computing the Shapley value for single data example 4,. When computing the Shapley value for every tuple in training dataset, given that the tuples sorted according to similarity to trals can notice that the sum in Equation 38 exhibits the following recursive structure:
N -
plt,, tval) = p(t141, tratt + (mr(u(t)), (v(ts), teat) - mr(((t)), tows))
(++1)
we take advantage of the above recursive structure, we can see that is possible to compute the Shapley value for all data examples in single pass that takes O(N) time. Hence, since the overall
25

---

Published as a conference paper at ICLR 2024
computation will still be dominated by the sorting procedure, the time to compute the Shapley value for all training tuples with respect to a single validation tuple tual is O log N).
Fork Pipeline. As we noted, both map and fork pipelines result in polynomials made up of only one variable. The difference is that in map pipeline each variable associated with at most one polynomial, whereas in fork pipelines it can be associated with multiple polynomials. However, for I-NN classifiers, this difference vanishes when comes to Shapley value computation:
Corollary F.2. For the 1-NN accuracy utility and fork pipeline, which takes as input a dataset of size N. the Shapley value can be computed in O log N) time.
Proof. We will prove this by reducing the problem of Shapley value computation fork pipelines to the one of computing it for map pipelines. Let us have two tuples 14,2 E [(),, both associated
with some variable 0j E A. That means that p(( (1) = p((),2)- If we examine Eqquation 31 we notice that it will surely evaluate to false if either a ((),1) > (t)) or (l > o()). The same observation holds for Equation 32
Without loss of generality, assume (t > (tz,2).. Then, (tz,1)) ) > (t) implies (ft,22) > (t). As result, we only ever need to check the former condition without paying attention the latter. The outcome of this is that for all sets of tuples associated with the same variable, it is safe to ignore all of them except the one with the highest similarity score, and we will nevertheless obtain the same oracle result. Since we transformed the problem to one where for each variable we have consider only a single associated tuple, we have effectively reduced the problem to the one of computing Shapley value for map pipelines. Consequently, we can apply the same algorithm and will end up with the same time complexity.
G DETAILS ABOUT THE EXPERIMENTAL PROTOCOL AND ADDITIONAL. EVALUATION RESULTS
Hardware and Platform. All experiments were conducted on an AMD EPYC 7742 2.25GHz CPU. We ran each experiment in single-thread mode. All deep learning models were running an NVIDIA A100 GPU.
Datasets. We assemble collection of widely used datasets with diverse modalities (i.e. tabular, textual, and image datasets). Table 2 summarizes the datasets that we used, In each experiment, we subsample the dataset 1K training data examples by using different random seeds.
Table 2: Datasets characteristics
Dalasel
Modality
Examples
Features
Noise
Label
UCT Adult
Kohavi al.
1996
labular
49K
14
Injected
FolkUCI Adult
Ding et al.
20
tabular
1.6M
10
injected
MNSST
Xiao
image
14K
injected
20NewsGroups
Joachins
1996
text
L,K
20 after TF. IDF
injected
DataPerf Vision
Mazumder al.
2022
tabular
20488
human
emor
CIFAR
Wei
2022
image
x x 3
human
error
Models. We use three downstream MI. models following the previous feature extraction pipelines: XGBoost, LogisticRegression, and KNearestNeighbor. We use the Logisti cRegression and MMeiihhorssCassiff is provided by the sklearn package. We set max_iter to 5,000 for LogisticRegressionn and set in_neighboors to 1 for KNearest
Protocol. We conduct series of experimental runs that simulate a real-world importance-driven data debugging workflow. In each experimental run, we select a dataset, pipeline, target model, and data repair method. If dataset does not already have human- genaarted label errors, we follow the protocol of Li et al. (2021) and et al. (2021) and artificially inject 50% of label noise. Label noise injection is performed by selecting a random subset representing 50% of training data examples, and replace the original label with some other valid label in given dataset. Given the selected data repair method, we compute the importance using a validation dataset. We use this computed iportance to sort the training dataset. Data repairs will be conducted using this sorting order. If the repair method random, the data is sorted randomly. We divide the range between 0% data examined and 100% data examined into 100 checkpoints. Specifically, each checkpoint, we select the next batch out
26

---

Published as a conference paper at ICLR 2024
Pueli Morte Light Fapedlo
DO CoAic forie Stodel Logitc Prprsio
Prodic Lopitber
Wold Lagen Pigestio
Ia I
57%
180+
50 Eariiad
5%% Parion Conindd
of Donieed
Papesio
2100:00
11M
Pontar Label
Portin of Lindi Dor aed
Fordon of Liben Candrd
Dasse: TarlsaREET Fuelic Guntar Bux Vollt Log Progesoo
FubaertS? Canldd Mabic
110000
Tediovel Kilt Lopats bygaaee
Grofhe ciden Poetac PCk Mosi Lopins Peppstion
Deset Fadls Main
Date:: Clark Poeloc Haspenne Oriene Caccess Vold lo Peproiio
Ioo 21430
Comper
Tan
BP XXM
030
50%
Tortoval Libes Lonked
Random
TMC 10
TMC x000
Datassope TMC 10
Datascope xMCx100
Datascope KNN
Datascope KNN Interactive
Figure 10: Label Repair experiment results over various combinations of datasets (Ik samples) and map pipelines. We optimize for accuracy. The model is logistic regression.
of a 100 batches of data examples ordered based on the importance- sorting order. We repair the labels in the given batch and we measure the quality of the given target model on a separate test dataset using some metric (e.g. accuracy). We also measure the time spent computing importance scores. At any given checkpoint, the label effort represents the portion of data that was covered in all batches that were processed up that checkpoint. We repeat each experiment 10 times with different random seeds and report the median as well as the 90-th percentile range (either shaded or with error bars).
G.1 ADDITIONAL LABEL REPAIR EXPERIMENTS
We present the results of an array of experiments that were conducted for the label repair scenario. Sec|section for details on the experimental protocol. See Figure [igure for experiments where we focus on improving accuracy. See Figure to to Figure 19 for experiments that explore the tradeoff between accuracy and fairness. Finally, in Figure 20wwe we show more results for the label repair experiments over deep learning embedding models for image and text data.
Note about Fork Variants: We create "fork" version of the above pipelines, by prepending each with a DataProvider operator. It simulates distinct data providers, each providing a portion of the data, The original dataset is split into a given number of groups (100 in our experiments). We compute the importance of each group, and we conduct data repairs on entire groups all at once.
G.2 ADDITIONAL SCALABILITY EXPERIMENTS
We provide results of additional experiments where we attempt to measure the trends of both the label repair efficiency and compute time, as a function of dataset size. To achieve this, instead of evaluating on synthetic data, we evaluate on CIFAR-N, a real-world dataset with numan-generated label noise Figuure 23). We use logistic regression as a target model and the HOG transform pipeline for feature extraction. We keep the training and test set size to 5K data exaples and we vary the training set size from K to 32K. We can notice that for training set of size 32K, the TMC method requires around day to complete with 10 Monte Carlo iterations and around 10 days with 100 iterations. At the same time we can notice that the KNN approximation is able to complete in a matter of minutes.
27

---

Published as a conference paper at ICLR 2024
1 si 96.32
x 2014e
ATT cass
$030 5322
1IAAL ENT
12 24
of bombedd
125
20 Forden Exanind
35% Farton Donted
Pydle
lolaess glae
Gutar UC Pllice Maing inluae Houss plae
T0400
15744
2400
5% Potian Eoe
Potton 05
Patur
Frea Miwaeeep Nowe U'itaew TRUP biglts
-A8.0
T-957 Tw
1.4 Tive
Portc of Libel Exanied
1% Exsaie
Iiteent Dlertie thber welee Kiiberr Meril Io Poteee Hegpher
Drca:: iitggare
Music Hurrn
1P
1
33541
2e305
WEAT
Portev Liben Eonbect
Porter Lowb
Perter Leath Eomnlet
Random
TMC X0
TMC x100
Datasoope x0Cx10
Datascope TMC x100
Ditascope KNN
Ditascope KNN Interactive
Figure 11: Label Repair experiment results over various combinations of datasets (Ik samples) and map pipelines. We optimize for accuracy. The model is K-nearest neighbor.
MMpder Lopeterr
55.90
31337
quiat
p Tax
2002
Portae 32%
Portor
Aucieved Lonn
$0.00
Tires
meltttt Hodee Zombe Men Mein tegan
11-00 Paymer
2
Labes
Porton of Libe Darene
Forte Libet Gunake
Deser Daccher' Polter Moong iotoew Kiltern Mast Taper Signsio
Dassc: Corlt Fuoloc wnal Euderra Musi
E1L46
122
Random
TMC XIO
TMC x100
Dutaseope TMCx10
Datascope TMC x100
Ditascope KNN
Ditascope KNN Interactive
Figure 12: Label Repair experiment results over various combinations of datasets (1k samples) and fork pipelines. We optimize for accuracy. The model is logistic regression.
28

---

Published as a conference paper at ICLR 2024
2 228
CONN
Tast 1&
1161 2240
XEX
X051
Coteet 206mmd Pidee tripk Maae is Neund Neighte
22140 22
|20
+3.
Parion of Lo Garmie
Putio Latnk Garmin
Hordon of Libtl
Danser Feleendah Poder Gereon S.hreee
I
E
2330
Detset wow Fadler
Hearee Helpie
10
Detett Out Years Paelec
Mone wlune KoMera Mulil Krlwee Heplhrr
Dewer Clark Hengyve Dieen Goulenee Moln lieen tnigher
+1
14:7
KUNI 233
Libe's
Random
TMC x1
TMC x100
Datassooee x10
Datascope x100
Datasoope KNN
Datascope KNN Interactive
Figure 13: Label Repair experiment results over various combinations of datasets (Ik samples) and fork pipelines. We optimize for accuracy. The model is K-nearest neighbor.
Droeet UO Adk Podiec Ineeyy aObic
Desert Ac Podlec fseced Sake that Xoherr
Dersen UE Mili Poelie tap Solec Mokl Scfic
1300 10655
53.20
[eo Iess
1606
g1230 11.0
50%
Deliet LG Adl Ppt PDk Wase X5lven
Duaee Add Porer
Orane 2ilard Fodees 17425 Mule Villoel
-5108
25
10%
207
30%
130%
Telewer
Toner Poroaetaen Metioe Coentin Mayy 30Ree
Cowernt Cruteets Shack
152 IS M01
Porza Libes Cunaad
Lubi Cavited
Torden Likes
Drows: Desher Woow callec PCA Mecil XS3owe
Droet Chrl Pip Hatipen Diernal Gasl una Mole KQBoet
am auc
CONPAE
100
Putooed LAhi Care
Palie Libkk
Random
TMC X10
TMC
Dutascope 110'10
Datascope TMC x100
Datascope KNN
Datascope KNN Interactive
Figure 14: Label Repair experiment results over various combinations of datasets (1k samples) and fork pipelines. We optimize for accuracy. The model XGBoost.
29

---

Published as a conference paper at ICLR 2024
Datin Seati Lopiti
Light Papas
Optiso Soaliad
64
10%
Coass
Apglen
Logar
Carmery
Mandar
Luga Segrea
505
10%
Ciisel
Fumle Lagatier
Lagasa Pagmsin
ESP Irees
40%
60%
100
Drees Edltato Adl Patie POX Repwers Caliniin Auartay
Dever Palrodle Aey Fodee POL Meli Topare Pepresder
Ooleris for Expdioa DMt Deleever
$ 1e.30
21.25
Purtan
Deter Foharis Ppirs Uang sdicte A-bbas Weli
Pepissiiss Opt woue Aoaring
Delie Folcatio Aoti Foeles Nari Iodaat
-CMMu Mold Logals Farmais viaa Cquliaa Dala Dflees
C7x
CSD E15
-012
Fodios
Like
Random
TMC x10
TMC x100
Dutaneope TMC x10
Datascope TMC x100
Datascope KNN
Dasascope KNN Interactive
Figure 15: Label Repair experiment results over various combinations of datasets (1k samples) and map pipelines. We optimize for fairess. The model is logistic regression.
30

---

Published as a conference paper at ICLR 2024
0%
67
13%
12%
Podls
Kiloon hights Optin
Dikk
Isnlo
50%
100
55%
Dranc Fdbiils Aak Pali
Soke Vold
Sooee NalMoc Opmnee Noorney
Dataro Futti
Suber K.Baarn Segaler
3000000
43 2407
35.55
Dhtrot Petradio Aadt
Diseel Faliaies Kilk Pedre
Muke Aermd Hightis Optanis Goaalaed Cale Diferrn
29.20
33 11.77
+640
Lowis
Porboe Leth Eorerr
Portton Like's
Goleer Hnderide
K-Merr Mede
Stppher Serwery
Disat Talcablo Teali
-7.0
Lowis
dath
Random
TMC x10
TMC XI0X
Datasoopee TMCx10
Dataccope TMC x100
Ditascope KNN
Ditascope KNN Interactive
Figure 16: Label Repair experiment results over various combinations of datasets (Ik samples) and map pipelines. We optimize for fairness. The model is K-nearest neighbor.
31

---

Published as a conference paper at ICLR 2024
Datin
Lopita
Papestos
1451
T::0
200
10%
50%
Logas Pegmeie Carmery
Melen Add Mydion
CONT
300
10%
10%
Inl Furten
Lagals Pagenser
E150
60%
10%
60%
35%
Oreet Paleades AMr
Mal Lightc Rapesor Chlines for Accerty
Dewer Fulaein #Md Modio
POL SoMe Loglee Regresier Octeri Bo Difhweo
10:00 11354
14.50
2.:0 111
50%
100
50%
05
35%
Dhaeer Poble Mpdie
Tyga Pegenooe Surwey
Tharee hotaalos Foeter Movig
1-5443
24.59
200
Random
TMC x10
TMC x100
Danassope x10
Datascop: TMC x100
Datasoope KNN
Datascope KNN Interactive
Figure 17: Label Repair experiment results over various combinations of datasets (Ik samples) and fork pipelines. We optimize for faimess. The model is logistic regression.
32

---

Published as a conference paper at ICLR 2024
aboe QUA DIve
13 W
107
0%
Podes Segled Kilood Highto Optin
SSLES
19
Doo
E
300
10%
50%
55
Dranc Faltbls Kak Pali
Leniroi Soke Vold Shoeet NalMor Denmeb Nourncy
Segaler
DUS
177H Tex
Thtret Petradio Aidt
K.berr Megh Detlein Arcwers
Diseel Faliadlss Kilk Pedre
PCA
Muke
Mered Heghtsn Optacis Gocalaed Cale
DAG
15.96
Lowis
Eoanneed
Portion
Porter
K-Meer Mrde Soume Stppler Senwery
Diaae Talcablo Abli Feali Malg
135.70
1109
Lowes
Random
TMC x10
TMC X10X
Datasoope TMCx10
Datascope TMC x100
Ditascope KNN
Ditascope KNN Interactive
Figure 18: Label Repair experiment results over various combinations of datasets (Ik samples) and fork pipelines. We optimize for fairness. The model is K-nearest neighbor.
33

---

Published as a conference paper at ICLR 2024
durtc
BILLY 50769
CAN
40%
100%
60%
55%
Addl
GoPpR Trme
p 1746
208
10%
Inger Moler fereere
Desst: Acbi Pedin lap Elans Kalue Optnnin
Eualad CaU DiSwwe
1 17
Potto LiMES
Liben
Creast Taloadee d4
Toslecc PCL Moad #itoor Dennia Assano
Detne: Folora Abrc
PCL Wold Wibuur Cat
Scalladd Clka Difericc
seulied Gia
L.de Cace
Porton Lowh Formerd
Pordon Laba baninee
Toman of Liben bombed
Euraa
Poreo Libes
Motton Lowis bariirdd
"orton Libt bonine
Ponton
Random
TMC
TMC
Datassoope
Datascope x100
Datasoope KNN
Datassoppe KNN Interactive
Figure 19: Label Repair experiment results over various combinations of datasets (Ik samples) and fork pipelines. We optimize for fairness. The model is XGBoost.
Lights
13755
505
30%
57% 20blustange Pprie Loksiing lagas Peprsso
55%
Fustes Labuelay
20440
55375
62%
30%
60%
Randoma
Dutascope TMCx10
Datascope TMC X100
Ditascope KNN
Figure 20: Label repair experiment executed over pipelines based on deep learning embedding models: ResNet-18 for image data, and the transformer based MiniLM for text data. Even though pipeline was executed on GPU, this execution time dominates the overall importance compute times. Due the long compute time of these pipelines we omit the vanilla black-box TMC methods.
34

---

Published as a conference paper at ICLR 2024
Iessert wetooen PEN MAb Lnveding Note CoNern Nigher Ieneer InPoveeSt PE No.0 ceveding Mol
Untaarc Tac.ooa NiW
Oriedti Mode Hibver
330006
Toke
1174
20%
117
20%
COFFENNE Thme
Comraade Thee
1359 42
22333.0 56
27022
T336.6
52.50
22184
1644
:7.00
50t
102%
34
100%
55%
100%
Notion
Label
Random
TMC x10
TMC
Datrecope TMC x10
Thtascope TMCx100 x100
Datissape RNN
Figure 21: Label repair experiment executed over pipelines based on smaller deep learning embedding models. This permitted us both the Canonpipe TMC and vanilla TMC methods, along with our Canonpipe KNN method which still performs favorably compared to other baselines.
Dataset CifarN; Pipeline: Identity; Model: Matching Network
Dataset: FashionMNIST, Pipelin: Identity, Model: Matching Network
Compute Time [s]
11679
0.8
Time 1st
100*
Accurasy
0.5
11750.57
Accurecy
1641.24
10a
0.6
76.58
3,36
+3.30
0%
50%
100%
0%
50%
100%
Portion of Labels Examined
Portion of Labels Examined
Random
Dulascope TMC x10
Datascope TMC x100
Datassope KNN
Figure 22: Experiments where we use matching networks, a one-shot learning approach, as target model which we evaluate over the CifarN and MNSS datasets.
Data Repaired to Get 50% Maximum Accuracy
Dataset: CIFAR-N: Pipeline: Histogram of Oriented Gradients
Target Model: Logistic Regression; Validation
Size:
10c
Compute Time
10a
1k
3k
10k
32k
1k
3k
10k
32k
Training Set Size
Training
Set Size
Random
Datascope TMCx10
Datascope TMC x100
Ditascope KNN
Figure 23: Evaluating how the label repair efficiency and compute time of Datascope scale as function of dataset size. On the left-hand side show how many data examples need to be repaired in order to recover 1/2 of the maximum possible accuracy on the given dataset. We can notice that the KNN approximation is able consistently achieve comparative label repair efficiency with orders of magnitude less compute time.
35


Reviews:
[{"review_id": "HkYQb3vZP0", "reviewer": "Reviewer_V8Vh", "summary": "This paper introduces a framework for identifying influential training examples in a machine learning pipeline using Shapley Values algorithm in an efficient manner. The first efficiency problem that the paper addresses is identifying whether the output of data preprocessing pipeline for a given training example belongs to a given subset of training examples in O(1) time. The paper claims that this condition holds for the following three pipelines: map, fork, and one-to-many join.\nThe second efficiency problem that the paper addresses is related to the performance of the ML model and the utility metric used to measure the quality of the model. In this case, the paper suggests to use KNN algorithm and requires that the model quality metric is additive. The authors show that their framework is computationally more performant compared to baseline approaches. It also reaches competitive results in terms of accuracy on downstream tasks.", "questions": "1) Sections 3.2 - 3.3: why are  One-to-many, fork and join canonical ? How is the canonical pipeline defined ? Why exactly is `reduce` non-canonical ? Would you, please, bring examples ?\n2) Are modified KNN  and quality metrics based on previous work or something new that the authors propose ?\n3) What are the limitations of the work ? \n4) Since we are using modified quality metric and ML algorithm (KNN), I wonder how practical is the approach in terms of non-KNN models and different quality metrics?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1) The work discusses related work thoroughly and highlights their pros and cons and the relation to the work that they are proposing.\n2) The visual figures 1 and 2 are well made and help with the understanding of the proposed method.\n3) The work provides experimental results for a variety of different pipelines for text, tabular and image datasets.  It also shows improvements not only for runtime but also for accuracy and fairness metrics.", "weaknesses": "1) From the introduction and abstract of the paper there is an impression that the paper aims to identify influential training examples but they doesn't seem to be any experimental results on that aspect. The experimental results are mostly cumulative w.r.t. overall accuracy, runtime, etc. There are no examples that show the effectiveness of the method w.r.t. specific training instances.\n2) To make the paper more clear it would be good to define what exactly “canonical” pipeline and “ data provenance”  mean in the beginning of the paper. The readers need to have a clear understanding of those terms.\n3) The notation  `D_{tr}[v] to denote D` is a bit confusing.  t \\in f(D_{tr})  is confusing too since t \\in D_{tr} and we see exactly t \\in D_{tr}  notation later in the paper. It would be good to change the notation to make it more straightforward. \n4) In section 3.3  f* doesn’t seem to be defined too ?\n5) Figure 3 is referenced in pages 4 and 5 and it is not explained. It’s unclear why the Compute time of Canonpipe TMC x100 is worse than TMC x10.\n6) The intuitions behind modified KNN  and quality metrics in section 4.1 are unclear.\n7) The description of  Counting Oracle is not very clear. It would be good, if possible, to describe it in a more intuitive way. It seems to be overloaded with math notations and is not straightforward to follow.", "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": "09tJ3FvZlV", "reviewer": "Reviewer_guJp", "summary": "Data repair is typically performed on preprocessed data at the stage immediately preceding model training. This paper explores data valuation on raw data before preprocessing steps are performed. This necessitates a framework of data provenance in ML pipelines and a computation approach for data Shapley under a KNN approximation. The paper demonstrates the usefulness of this data valuation framework as achieving competitive performance in data debugging at significant compute cost/time reduction.", "questions": "See weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is thorough in introducing a new problem setting within data valuation and debugging. The methodology builds on KNN Shapley but factors arbitrary general data preprocessing pipelines. The algorithm includes theoretical guarantees on polynomial time computation and an extensive set of experiments to demonstrate the compute efficiency of the proposed method.", "weaknesses": "- The framework depends on a data preprocessing pipeline to be the same for both training and validation (equation 2). However, one challenge of data valuation before pre-processing is that there may be different pre-processing pipelines between training and validation. For example, we can consider random data augmentation techniques used in training, but not for testing. Does this methodology handle different pre-processing pipelines, or for example, a validation pipeline that is a subset of the training pipeline?\n- Near Section 3.2/3.3 (or a detailed version in the Appendix), it would be useful to have a detailed dictionary of common pipelines / components and how they fit into Map, Fork, Join, or can be approximated by Map-reduce. This could be a table for example similar to Table 1. A table such as this would make the significance of the proposed work more clear in terms of how an ML practitioner can think of pre-processing steps in these pipelines.\n- If I understand the experiments correctly, the baselines are performing data importance on the raw data before pre-preprocessing. Furthermore, existing KNN Shapley methods cannot accurately model the combinatorial explosion in subsets obtained from a data pipeline, making them conceptually unattractive. However, one baseline in data repair may be to perform valuation on data points after pre-processing, and then simply invert the pipeline manually to determine the relevant raw data points. How would existing methods including KNN Shapley perform on label repair in terms of accuracy improvement and compute time? More generally, what is the practical significance of identifying data points for repair with a method that captures the pre-processing operations versus simply identifying potential points for repair after pre-processing and then inverting the preprocessing pipeline to determine affected raw data points?\n- The experiment protocol is not thoroughly explained and relies on referencing prior work (e.g., noise injection, measuring labor cost). It would be useful to include this discussion perhaps in Appendix.\n- There is some minor writing improvements to be made, for example, In page 2, set S is used without definition", "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": "zUWXq24jUV", "reviewer": "Reviewer_bts9", "summary": "This work studies a novel and relevant problem of incorporating Shapley-based data evaluation into data processing pipelines. The work first clarifies the current limitations on implementing Shapley methods with data processing pipelines–the Monte-Carlo sampling approach would necessitate re-running the data processing pipeline which costs significant time; KNN-based approximations are incompatible with some constraints posed by the data processing pipelines and thus sometimes cannot be applied. Then, this work proposes the concept of “canonical” pipelines which allow directly relating inputs and outputs. By approximating pipelines as canonical, the proposed methods may achieve significant speed-ups for the Monte Carlo approach. Also, by combining canonical pipelines with the K-nearest neighbor as a proxy model, the proposed  PTIME Shapley computation algorithms allow applying KNN Shapley as a special case applicable to map pipelines. The paper is technically solid.", "questions": "It would be nice if the authors could better contextualize the proposed framework with real-world applications, like, providing some concrete examples or a motivating case to help the audience better delve into the problem.\n\n- Appendix should not be submitted under the main paper.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clear, sharp, and well-structured. The paper is well-written, well-contextualized, and well-motivated. The language is technically sound. The identified problem is valid and important. The proposed technical approaches are well-documented with rigorous elaborations. This work could be of lots of interest to data science practitioners. Proposed methods achieve significant speedups in empirical studies.", "weaknesses": "I do not see major weaknesses. I'm familiar with the literature on Shapley methods and their practical implementations but not much on data processing pipelines in the real world. The review provided is limited by the scope of my knowledge. I would leave it to other reviewers to evaluate the practicalness of the modeling and treatment of the data processing pipelines.\n\n- Format: Appendix is not cut from the main paper. The PDF provided for the main paper is this 34-page document.", "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": "bOZoIZYSZh", "reviewer": "Reviewer_5GXy", "summary": "This paper proposes a method called Canonpipe for efficiently computing Shapley-based data importance over machine learning pipelines. The authors introduce several approximations that lead to significant speed-ups, making Canonpipe capable of data error discovery that is as effective as existing Monte Carlo baselines, and in some cases even outperform them. Overall, Canonpipe is a solution to the fundamental concern of discovering the data examples that are the most likely culprits for poor-quality ML models.", "questions": "See above", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The authors tried to address a very important problem. i.e., computing Shapley value efficiently for a large dataset over general machine learning pipelines.\n+ The authors proposed a novel provenance-based solution over canonical machine learning pipelines, which can address the computational challenges for evaluating Shapley values.\n+ The authors also provided rigorous theoretical analysis for their proposed solution, which is sound and convincing\n+ The authors also performed extensive experiments in different settings to demonstrate the effectiveness of the proposed method.", "weaknesses": "+ Some experimental details are missing, For example, in Section 5.2 when the authors discussed the scalability, I am not sure whether the results in Figure 7 are the ones for evaluating Shapley value for one sample or all the training samples. I guess it would be the former case. Otherwise, the time complexity would be quadratic. So it would be better if the authors could clarify this.\n+ The overall experiments seem not to be comprehensive since the authors only evaluate their methods on simple dataset, e.g., FashinoMNIST, with simple models, such as KNN model. It would be great if the authors could demonstrate that their proposed method can handle large-scale datasets such as the ImageNet dataset\n+ Although the authors refer to the earlier work on approximately evaluating Shapley values with KNN surrogate model, it is unclear to the readers how that can work, it would be better if the authors could briefly discuss this prior work, in particular what kind of correctness guarantee that can be obtained by approximately evaluating Shapley values with KNN surrogate models. This can make this paper more self-contained.\n+ Also, the overall presentation could be improved. Although the authors mentioned that the PTIME computation time can be achieved with ADD. all the discussions of ADD are included in the appendix along with the main algorithm. Since this is the main contribution of this paper, it would be better if the authors could put some of these core technical parts in the main paper and briefly discuss them there.", "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)