Towards General Robustness to Bad Training Data
Authors: Tianhao Wang
Yi Zeng
Ming Jin
Ruoxi Jia
Venue: ICLR 2022 Submitted (2022)
Keywords: General Robustness
Data Valuation
Data Utility Learning

Abstract: In this paper, we focus on the problem of identifying bad training data when the underlying cause is unknown in advance. Our key insight is that regardless of how bad data are generated, they tend to contribute little to training a model with good prediction performance or more generally, to some utility function of the data analyst. We formulate the problem of good/bad data selection as utility optimization. We propose a theoretical framework for evaluating the worst-case performance of data selection heuristics. Remarkably, our results show that the popular heuristic based on the Shapley value may choose the worst data subset in certain practical scenarios, which sheds lights on its large performance variation observed empirically in the past work. We then develop an algorithmic framework, DataSifter, to detect a variety of and even unknown data issues---a step towards general robustness to bad training data. DataSifter is guided by the theoretically optimal solution to data selection and is made practical by the data utility learning technique. Our evaluation shows that DataSifter achieves and most often significantly improves the state-of-the-art performance over a wide range of tasks, including backdoor, poison, noisy/mislabel data detection, data summarization, and data debiasing. 

Under review as a conference paper at ICLR 2022
TOWARDS GENERAL ROBUSTNESS TO BAD TRAINING DATA
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we focus on the problem of identifying bad training data when the underlying cause is unknown in advance. Our key insight is that regardless of how bad data are generated, they tend to contribute little to training a model with good prediction performance or more generally, to some utility function of the data analyst. We formulate the problem of good/bad data selection as utility optimization. We propose theoretical framework for evaluating the worst-case performance of data selection heuristics. Remarkably, our results show that the popular heuristic based on the Shapley value may choose the worst data subset in certain practical scenarios, which sheds lights on its large performance variation observed empirically in the past work. We then develop an algorithmic framework, DATASIFTER, to detect a variety of and even unknown data issues a step towards general robustness bad training data. DATASIFTER is guided by the theoretically optimal solution to data selection and is made practical by the data utility learning technique. Our evaluation shows that DATASIFTER achieves and most often significantly improves the fatee-of-th--eee performance over a wide range of tasks, including backdoor, poison, noisy/mislabel data detection, data summarization, and data debiasing.
INTRODUCTION
The quality of training data is a fundamental ingredient towards useful and reliable ML--based applications. Unfortunately, there are unaccountably many possible data issue types. For example, errors and bias occur frequently in data generation and collection processes. Bad data could also be caused by adversarial attacks (e.g., data poisoning and backdoor attacks), as training data are often collected from anonymous and unverified sources. On the other hand, most of the existing data selection strategies only applicable to specific data issues. Due to the diversity of data issues, there is an urgent need to achieve general robusiness to bad data of various types and even unknown types.
Purging bad data a long-standing problem, intensively studied by both the database and the ML community. Most of the existing approaches, however, can only achieve specialized robusiness to bad data of certain types. In the database community, the state-of-ther oof-the-art art data cleaning approaches such as ActiveClean (Krishnan et al. 2016)) BoostClean (Krishnan et al. 2017), AlphaClean (Krishnan and Wu 2019), and CPClean (Karlaš et al. 2020) are only applicable to certain classes of ML models and data issues. In particular, they cannot detect adversarial attacks on training data. The endeavors of the
ML community have covered a wider range of data quality issues such as adversarial attacks (Wang al., 2019: Chen et al. 2019)), data debiasing (Zemel al., 2013 Madras al. 2018), and mislabel detection (Zhao et al. 2019). However, each aforementioned solution only focuses on addressing a specific data issue effectively. The effectiveness of these approaches is based on the premise that the data quality issues are known priori, which usually does not hold in reality. Few recent works have the potential to achieve general robustness to unknown data issues. One line of such works is based on differentially private training (Du et al., 2019: Hong et al. (222)). These approaches do not perform data selection; instead, they attempt to restrict the impact of each training data point on the learning outcome in an undifferentiated manner. As a side effect, these approaches hinder learning
from good data, thereby leading to poor learning performance in practice (Tramèr and Boneh 2020). Another line of works that has potential to achieve general robustness is based on data valuation.
These works first adopt a data importance metric, e.g., influence function (Koh and Liang 2017
Koh et al. 2019
Feldman and Zhang 2020) or Shapley value (Ghorbani and Zou 2019 Mia et al.

---

Under review as a conference paper at ICLR 2022
2019a), to quantify each training data point's contribution to the training process. Then, which data to retain or remove is decided based on the ranking of data value. However, past empirical studies (Jia et al. 2019b) and our experiments (Section (6) show that their performance varies considerably across different data and learning algorithms. Overall, existing approaches to had data filtering either cannot identify unknown data issues by design suffer from poor detection efficacy.
In this work, we take step towards general robustness to bad training data. Our work is underpinned by key insight about what defines "bad training data". Despite the diverse types of data issues, the crucial commonality is that all bad data contribute little to achieving good model performance. If data point contributes positively to learning, it would be beneficial to just keep it as part of the training set, thus not considered a "bad" point. Hence, promising way to select data without knowing data issue types in advance is to search for data subsets that results in the highest trained model performance. More generally, the data analyst may have a utility function beyond model performance, so we formulate data selection as utility optimization problem (Section 3}
Secondly, with the utility optimization objective in mind, we present novel theoretical framework (Section 4 for rigorously analyzing the worst-case performance of data selection approaches. The line of existing works closest to achieving general robustness is the aforementioned data value ranking approaches. However, we show that these approaches have unsatisfying worst-case performance guarantees due to failure to capture the interactions amongst selected data points (also empirically shown in Appendix F.5.2). In particular, the popular Shapley value-based approach could select the worst data in some common scenarios.
We then design a general algorithmic framework guided by the theoretically optimal (but computa- tionally infeasible) solution to utility optimization (Section 5). A significant technical challenge for finding the subset that optimize the model utility is that, in order to evaluate the impact of different subsets of data on model performance, we need to retrain model on every possible subset. To solve the computational challenge, we introduce DATASIFTER, which directly learns a parametric function to predict the performance of a model trained on given subset and then performs data selection via optimizing the function. Compared with prior data selection algorithms, DTTASIFTER has the following advantages: (1) being able to handle various data issues (general robustness), (2) applies to any target ML model architectures imodel-agnostic) and (3) instantiated by the goal of downstream ML tasks (task-driven). Finally, we conduct a thorough empirical study on a range of data issues (Section 6 including backdoor and poisoning attack detection, noisy label/feature detection, data summarization, and data debiasing. Our experiments demonstrate that DATASIFTER achieves and most often significantly improves the state-of-the-art performance of data valuation-based approaches.
2 RELATED WORK
Data valuation- based approaches can potentially achieve general robustness against diverse data issues by quantifying data importance or "data value", and then picking data points with high value for model training process. One simple idea to quantify data importance is to use the leave-one-ore error. Koh and Liang (017)) provides an efficient algorithm to approximate leave-one-out error for each training point. Recent works leverage credit allocation schemes originated from cooperative game theory to quantify data importance. Particularly, Shapley value has been widely used (Ghorbani and Zoul 2019: Jia al. [2019a è b. Wang et al. (2020). as it uniquely satisfies set of desirable axiomatic properties, More recently, Yan and Procaccia (2020) suggests that the Least core is also a viable alternative to Shapley value for measuring data importance. However, computing the exact Shapley and Least core values are generally NP-hard. Several approximation heuristics, such as RMC-Shapley (Ghorbani and Zou| 2019). G-Shapley (Ghorbani and Zou| 2019), KNN-Shaple (aa et al. (2019c), have been proposed for the Shapley value. Despite their computational advantage, they are biased in nature. On the other hand, unbiased estimators such as Permutation Sampling (Maleki) 2015) and Group Testing (Jia et al. (2019)) still require retraining models many times for any decent approximation accuracy. TracIn (Pruthi et al. 2020) estimates the importance by tracing the test loss change caused by training example during the training process. The representer point method (Yeh) jet al. 2018) captures the importance of training point by decomposing the pre-activation prediction of neural network into a linear combination of activations of training points.
The typical paradigm of data valuation- based approaches for selecting high-quality data (or filtering bad data) is straightforward: (1) each data point's 's value (e.g., Shapley value) is computed. (2) data
2

---

Under review as a conference paper at ICLR 2022
points are sorted by value and data points with the highest value selected. However, this paradigm fails capture the interactions amongst selected data points (Section 4 and Appendix F.5.)). i.e., the existence of one data point often affect the importance of another.
Differentially private training (Du et al. 2019 Hong et al. 2020) have the potential to achieve general robustness to unknown data issues. However, fundamentally, ly, these approaches diminish the influence of each training data on the learned model in an undifferentiated manner. Hence, these approaches hinder learning from good data, which lead poor learning performance (Tramèr and Boneh 2020).
Data cleaning approaches from database community are not able to achieve general robustness. The tfte-of-thh-ar data cleaning approaches leverage the information about downstream MI. tasks to guide the cleaning process, examples include ActiveClean (Krishnan et al. (2016). BoostClean (Krishnan al. 2017), AlphaClean (Krishnan and Wu, 2019). and CPClean (Karlaš al.. 2020). However, the state- of data cleaning methods are only applicable to certain architectures of ML models (e.g.. convex model, nearest neighbors). data format (e.g., tabular data), and data issues (e.g., missing values, outliers). In particular, data cleaning approaches cannot be straightforwardly extended to adversarial attacks such as data poisoning attacks and backdoor attacks.
3 FORMALISM
We propose to formulate the problem of achieving general robustness to bad data as finding a subset of data points with the highest utility. We use the data utility function to characterize the mapping from set of data points to its utility.
(o) denote the training set with data points of different quality. A learning algorithm AA is a function that takes a dataset S S D and outputs a classifier f. A metric function u takes ff as input and outputs its model utility. In the machine learning context, we often use test accuracy as the metric, u(f, V) | [(ew)ev [f)()) y] for test set V. However, test set V is usually not available during the training time. In practice, u(f. V) is typically approximated by validation accuracy u() uff, V) where V is a validation set separated from the training set.
More formally, let D
With a potentially randomized learning algorithm A and a corresponding metric function u, we define the data utility function as U U... subscript and simply write US)). The concept of data utility functions was originally discussed in Wang et al. (2021a). where it is used for active learning tasks. The critical difference between our formulation and Wang et al. (2021a) is that our formulation incorporates the label information as the input to a data utility function. This is important as label information is required for identifying both mislabeled and many types of adversarial attacks on training data.
EA [u(A(()), V)]. When the context is clear. we omit the
With the modified notion of the data utility function, we abstract the objective of selecting high-quality data as a utility optimization problem:
max U(S) SCD.SS
(1)
where 0 < n indicates the selection budget, which can be predetermined (e.g., based on the prior knowledge about potential data defects or computational requirements). The fundamental intuition behind this formulation is that despite the diversity of data issue types, all "bad data" have the commonality that they all contribute little or negatively to model performance. Hence, optimizing data utility function is a principled way to achieve general robustness. Besides, the interactions between data points will significantly affect model performance. A "good data" can only be defined relative to the rest of the data points in the dataset. Therefore, high-quality data selection needs to be done in batch-style instead of byne Overall, promising way to deal with unknown data issues is to search for a set of data points that results in the highest trained model performance on a clean validation set.
4 WORST- CASE ANALYSIS FOR VALUATION-BASER APPROACHE
In this section, we introduce theoretical framework to analyze the worst-case performance of data selection algorithms for the utility optimization objective in (I). We show that data valuation- based approaches, such as leave-one-out (LOO),, Shapley value, and Least core, achieve unsatisfying
3

---

Under review as a conference paper at ICLR 2022
worst-case guarantee. Note that here assume exact data value can be computed for every data point. In practice, however, data value notions such as Shapley value require model retraining on every possible data subset. Typically, only approximations can be obtained, which may further impair data selection results. We will defer all proofs to Appendix.
We start by formalizing data selection algorithms into general paradigm. We call an algorithm M such that M((D, U), k) returns S [ 'D of size k a heuristic to (size-k) data selection problem on dataset D. The typical pattern of data valuation-based heuristics is that they first rank the data points according to their corresponding data importance metric, and then select the data points with the highest importance scores, We call the heuristies matching this selection pattern as linear heuristics. Definition (Linear heuristic). We say M is a linear heuristic for data selection problem for every instance I (D,U) where D ? M works as follows:
1. Assign a score v- = (VI,...,,U, for every data point 2, E D. Sort D according to e in non-ascending order and get (2(1)....., -()). Certain rules are applied to break tie.
2. For query of selecting & high-quality data points, return the k data points in D with the highest scores ;()):...... 2(k)).
For example, for Shapely-based data selection approach, each v, = Escn((H) ((3T)) [U(SU
(21) U(S) and M((D. U)) returns data points with the highest Shapley values.
Our theoretical framework for studying the worst-case performance of data selection heuristics is inspired by the domination analysis framework initially proposed in Glover and Punnen (1997). Our worst-case performance metric is domination ratio, which measures how many subsets achieve lower utility than the selected set in the worst-case scenario.
Definition 2 (Domination ratio). The domination ratio of a heuristic M for the data selection problem is the maximun ratio 0 < d(n,,k) < s.t., for every problem instance I =(D,U on dataset D of size n and utility function U, MMI, k) produces a size-k subset S C D which has utility (S) no worse than at least d(n,, k) percentage of all size-k subsets.
For example, d(n, n) = for any heuristic since there is only one choice of size-n set. d(n, n/2) will be calculated by the least number of size-n/2 subsets S C DD where M(DD,), U), k) has better utility than across all datasets D and utility function U. divided by the total number of subsets (./2)- The domination ratio is well defined for every data selection heuristic. A heuristic with higher domination ratio may be a better choice than a heuristic with a smaller domination ratio due to the better worst-case guarantee. The best heuristic for data selection has domination ratio d(n, k) = 1 for every h I n, which means that it will always pick the size-k data subset with the highest utility (the exact solution for Objective (I) for every possible data utility function. The worst possible domination ratio is d(n, k) = // (+). as the returned subset has utility at least no worse than itself.
The following result shows that no linear heuristic is among the best heuristic whenever n 2 3. Theorem 1. For n 2 3, there exists no linear heuristic M s.t. d(n, k) = f.ror every k E {l,..., n...
Furthermore, we can tighten the upper bound of the domination ratio for data valuation based heuristics by noticing another common property: two data points will receive the same importance score if they contribute equally to all possible subsets of the training data. This property is often referred to as symmetry axiom in the literature (Tia et al.) [019%] Yan and Procaccial 2020).
Definition 3 (Symmetry axiom). A linear heuristic M satisfies symmetry axiom if its scoring vector v in the Step I of Def. satisfies: [(VS E D \ 2 (2)) = (S U {21 = U = Uj.
The symmetry axiom may be desired for application scenarios requiring fairness, c.g., data importance scores are used to assign monetary rewards for data sharing. However, for data selection, symmetry axiom may be undesirable because simply gathering high-value data points may lead to set of redundant points. Based on this intuition, the following theorem further upper bounds the domination ratio for non-trivial linear heuristics that with symmetry property.
Theorem 2. If a linear heuristic M assigns different scores to different data points and satisfies symmetry axiom, then the domination ratio d(n,, k) of M is upper bounded by [n/k] In particular, when nn/k for some constant integer c, d(n, k) (k/n))=1 =110)==m(00)0))
1/2)) k
4

---

Under review as a conference paper at ICLR 2022
The above theorem suggests that whenever & S n/2, the domination ratio will be exponentially small for linear heuristics that satisfy symmetry axiom. The key insight is that symmetry axiom makes the heuristics tend to select similar data points as similar data points will have similar value, while the data utility does not simply add up. We experimentally demonstrate this in Appendix [.5.2
Notably, we show that the Shapley value-based heuristic has performance guarantee in the worst case scenario, even if we restrict data utility functions to be submodular, a common assumption of data utilities (Wang et al. 2021 a by Han et al. 2020). The intuition is that Shapley value of training data weights higher for its marginal contributions on small datasets. Thus, data points that make a larger contribution on tiny datasets may be assigned with higher Shapley value, even if they make little or negative contributions in every dataset of desired selection size k.
Theorem 3. For any n 2 4 and le E [I.....n.. the domination ratio of Shapley value-based heuristics is d(n, k) = // (+) even if the data uility function U submodular.
5 DATASIFTER
One straightforward way to optimize Objective is to exhaustively evaluate US) for all possible size-k subsets S C 'D and choose the one that achieves the highest utility. Of course, this theoretically optimal but unrealistic algorithm requires prohibitively large computational resources as the required number of utility evaluations is (*) and worse yet, each evaluation of data utility function requires retraining the model. Our approach to resolving the computation issues is inspired by a recent line of work, which shows that data utility functions for many common ML algorithms exhibit "approximate" " submodularity. This property allows data utility functions be learned (Balcan and Harvey [00T]] Wang et al. 2021c) and optimized (Minoux 1978) efficiently. Hence, the idea of our approach is to first learn a parametric model to approximate data utility functions. With such a model, one can estimate the learning performance for any dataset by feeding the dataset at the input and query the function's ' output. Then, one can select the data subset by optimizing this model. If the model can fully recover the utility function U, under the same unbounded computation assumption made for the analysis of linear heuristics, the domination ratio is just as our method can always numerate all possible subsets and find the optimal one.
Specifically, the proposed data selection framework, termed DATASIFTER, proceeds in two phases: learning and selection phase.
Learning Phase. Figure I depicts the learning phase of the DATASIFTER, which consists of a utility sampling step and utility model training step. Formally, suppose that we have training set D D= =((x,,))) y:)) and a small validation set V representative for potential test data. To learn the data utility model, we train the classifier f for multiple times with different subsets S C D. The set {(S, u(f,, }))} could serve as a training set for learning U. When the learning algorithm is stochastic, for the sake of efficiency we just train f once and calculate u(f, F V) to approximate the utility USS). If computational budget permits, one can choose to retrain ff multiple times and compute the average utility. We adopt a canonical model architecture for set function 2017)-a as our model for U. A DeepSets model is a set function f(S) = (E.es d())) where both and Φ are neural networks, and in our context Its cermutation-invariant property and universal expressive power making it suitable as the parametric model for learning data utility function. With the utility samples {(S, u(f. V)) as the training data,
SearninggDeepSeee (Zaheer et al.)
(Ir, y) the concatenation of data feature and label.
we can learn the data utility function through training the DeepSets model Ú with standard stochastic gradient descent. In this work, the sampling distribution of S is simple: we first uniformly pick set size, and then uniformly sample subset of the given size without replacement. We stress that more fine-ge -raiing subset sampling methods could potentially improve the resulting data selection performance (see further discussion in Section 6.2.2 We left exploring the relationship between subset sampling distribution and data selection performance as future work.
Selection Phase. Given a trained utility model Ú, we could optimize it as a surrogate for objective ①1 efficiently and approximately using greedy algorithms, as most of the data utility functions are empirically shown to be approximately submodular. We follow Wang et al. (2021a) and choose stochastic greedy algorithm (SG) from Mirzasoleiman et al. (2015) to find the subset that optimizes utility model (i.e., the trained DeepSets model). The SG is simple algorithm that, for each iteration, randomly selects a subset of data { and then finds the best data point within that subset. In the context of optimizing utility model, the "best data point" within each randomly selected subset refers
5

---

Under review as a conference paper at ICLR 2022
Sampling Step
Training Step
91.75
Performance Scores
Training Data
Validation Data
74.32
74:32
Sampled
Scored
Subsets
Subsets
Downstream
92.11
Utility ML Model
ML Model
Figure 1: Overview of the learning phase, which consists of utility sampling step and utility model training. We randomly sample subsets from the training data during the sampling step, retrain the model on the subset and obtain the utility score for each set by evaluating the ML model over a clean validation set. Then, train the utility model predict the utility of given dataset.
the data point with the highest marginal contribution ÚSS (=)) (S), where S is the set of data points selected in previous iterations. SG runs in linear time while provides decent optimization guarantee for submodular functions. Although its approximation guarantee has been proved only for monotone submodular objective functions, our experiments show that it achieves high empirical performance on data utility models that are approximately submodular. more detailed discussion and pseudo-code for SG can be found in Appendix [D] We also note that the rigorous characterization of the (approximate) submodularity for data utility functions is surprisingly difficult and it is still an open question (Wang et al. 2021a
In our experiment (Section 6). the number of utility samples 4000 for all the tasks we evaluated (an empirically tuned number for efficiency- performance tradeoff). Model retraining could be computa- tionally expensive for large training datasets and models. However, retraining on differ- ent subsets is common and of- ten unavoidable for data selec- tions algorithms aiming at gen- eral robustness, e.g., permuta- tion sampling for Shapley value requires On log n) times model retraining. For DITASIFTER, two techniques could used to improve scalability. The first technique is based on the observation that 4000 times of model retraining is still relatively efficient small datasets. For example, training 4000 small CNN models on the subsets of 2000 CIFAR-10 images takes only about 15 hours with NVIDIA Tesla K80 GPU. As long different data subsets have observable differences utilities (e.g., 10% vs 30% test accuracy), the learned utility model can still be used to differentiate between good and bad data points. Since the learned utility model can provide utility estimations for of unseen data points by design, when the utility learning is on smaller subsets, greedy optimization can still be performed on larger dataset by selecting good data in batch-mode style. This largely improves the scalability of DATASIFTER (Appendix F.5.9). The second technique is to use smaller proxy model for utility sampling, which is proposed in Wang et al. (2021a). and the idea of using proxy model for data selection was also explored in Lewis and Catleti (1994) Coleman et al. 2019). This technique is based on the observation that the utilities of data for different learning algorithms usually posirively correlated. In experiment, we find that sampling utilities small subsets can already achieve good efficiency and performance (Appendix F.5.9).
General Model-
Task-
Est.
Method Type
Robustness Agnostic
Driven
Utility
Data Cleaning
X
Perm-SV (Maleki 2015)
TMC-SV (Ghorbum and Zon
2019
G-SV (Gherbani Hid 2019
KNN-SY eJ 2019C
Least Core (Yan and Procaccia 2020
X
Leave-one-oüff (Koh
Infi. Func. Koh and Liaing 2017)
X
TracIn (Prullii at. 2020
DATASIFTER
Table I: Summary of the differences between prior works and DATASIFTER. means only some of the techniques in the type satisfy the property. 'SV' means Shapley value.
Compared with prior data selection algorithms mentioned in Section 2 DATASIFTER has the following advantages: (1) achieves general robustness by design, (2) is model aagdosic as data utility function can be defined for every learning algorithm, and (3) is task-driven as the optimization objective (the

---

Under review as a conference paper at ICLR 2022
utility function) is defined in terms of the downstream ML task (the learning algorithm and metric function). In addition, with the learned data utility model, DATASIFTER can provide an estimate of the utillity for the selected dataset, which will be useful for data analysts to decide the number of data points to select. The major differences between DATASIFTER and previous data selection algorithms summarized in Table
6 EVALUATION
To test the general robustness of DATASIFTER, we evaluate this algorithmic paradigm on vari- ety of tasks with different data issues, as listed in Table We consider various benchmark mod- els and datasets used in past literature for each task. Since we observe similar results different datasets, we only describe the result on one repre- sentative dataset for each task here and leave the other dataset in the Appendix. We also evaluate the scalability of DATASIFTER larger datasets in Appendix F.5.9
Task
Datasets
Main Text
Appendix
Backdoor Delection
CIFAR
MNIST
11. Poisoned Data Detection
CIFAR-10
Dog vs. Cal
III.
Naisy Feature Delection
CIFAR 10
MNIST
Mislabeling Detection
SPAM
CIFAR-10
V. Data Summarization
PuhFig83
COVID-CT
VI. Data Debiasing
Aduli
COMPAS
Table 2: Summary of tasks and datasets.
6.1 IMPORTANT SETTINGS AND BASELINES
For fair comparison between DATASIFTER and baselines, we fix the number of utility sampling as 4000 for DATASIFTER as well as baseline algorithms that require utility sampling. For DATASIFTER, subsets are sampled by first picking a set size uniformly, and then uniformly sample a subset of the given size. The validation data in utility sampling are 500 clean data points sampled from the test data of the corresponding datasets. We repeat model training ten times for each selected set of data points to obtain the error bars. The metric function we use for Data Debiasing experiment is weighted accuracy, and for all other experiments the metric function is validation accuracy. Both DATASIFTER and baselines use the same metric function.
We focus on comparing data valuation-based approaches as they are closest to achieving general robustness. Differentially private training methods are omitted from comparison as they significantly impair model performance. Data cleaning methods also omitted as their applicability is limited to specific data types, error types, and model architectures. We consider the following eight statc-of-art data valuation-
approaches: (1) Shapley Permutation Sampling (Perm-SV) (Maleki) (2015), Monte Carlo- based algorithm for Shapley value estimation. (2) TMC-Shapley (TMC-SV) (Ghorbani and Zou, 2019), refined version of the Perm-SV, where the computation focuses the subsets whose utility changes significantly when an extra point is added. (3) G-Shupley (G-SV) (Ghorbani and Zou| 2019). which approximates the Shapley value by anticipating the utility change caused by an extra point with its gradient. (4) KNN-Shapley (KNN-SV) (Jia et al. 2019c). which approximates the Shapley value by using --Nearest-Neighbor as a proxy model. (5) Least Core (LC) Yan and Procaccia 2020), another data value notion in cooperative game theory with Monte Carlo-based approximation. (6) Leave-one-out (L.O0) (Ghorbani and Zou 2019) evaluates the change of model
performance when data point is removed. (7) Influence Function (INF) (Koh and Liang] 2017 Koh
(et al. 2019), which approximates the LOO error with first-order extrapolation. (8) TracIn Clean (Pruthi et al. 2020). which traces the loss clean validation data change during the training process whenever the training point of interest is sampled in batch SGD. (9) TracIn-Self (Pruthi et al. 2020) the similar technique as Ceeean but traces the self influence i.c., the reduction of a training point on its own loss. This approach is used for detecting bad data. (10) Random is a setting where randomly select a subset from the target dataset.
6.2 RESULTS
6.2.1 FILTERING OUT HARMFUL DATA
Training data could be contaminated by various harmful examples, e.g., backdoor triggers, poison information, noisy/mislabeled samples. Our goal here is to identify data points that are most likely to be harmful. These points can either be discarded presented with high priorities to human experts for manual cleaning. To evaluate the performance of different data selection methods, we examine the training instances filtered by each method and plot the change of the fraction of detected corrupted
7

---

Under review as a conference paper at ICLR 2022
DataSifter Perm-SV
TMC-SV
KNN-SV
LOO
Tracin-Self Tracin-Clean
Random
G.SV
LC
INF
Pct. of Polsons
1.0
of Selected Poisons
Seleectdd Noisles
1.0
0.8
0.8
0.8
Detection Rate
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.0
0.0
0.0
0
500
1000
1500 2000
100
200
300 400 500
500
1000
1500 2000
0 100
200
300 400 500
Lia)
Inspected Data
I1.aa)
# inspected Data
Inspected Date
IV(0)
Inspected Data
100
36
Attack Accuracy (%)
Attack Accuracy (%)
Model Accuracy (%)
80
32
96
60
60
80
94
28
82
40
40
26
90
20
20
Model
24
22
88
86
200 40C
600
800 1000
50
150
250
400
84
100 150
250 Data
L(b]
Thrown
(l:b)
Thrown Data
[II,(b)
Thrown
IV(b)
Figure 2: The experimental results and comparisons of the DATASIFTER under the case of filtering out harmful data (application I-IV). The light blue region in each (a) graph represents the area that a method is better than a random selection. For L(b) and II.(b), we depict the Attack Success Rate (ASR), where a lower ASR indicates a more effective detection. For (lI. and IV.(b), we show the model test accuracy, where higher accuracy means better selection.
data with the fraction of the checked training data. Additionally, for poisoned/backdoor data detection, we plot the change of Attack Success Rate (ASR), and for noisy feature/label detection, we plot the change of model accuracies after filtering out the low-quality data points selected by each technique.
I. Backdoor Detection. Backdoor attacks (Gu et al. 2017] embed an exploit training time that is subsequently invoked by the presence of a "trigger" at test time. They are considered particularly dangerous since they make victim models predict a target output on inputs with predefined triggers while still retain high accuracy on clean data. Since data points with the backdoor triggers contribute little or negatively to the learning of clean test data, they are expected not to be not included in the subset that optimizes objective (1). This experiment studies the effectiveness of DATASIFTER for removing backdoored examples. We evaluate Trojan attack (Liu et al., 2017) here. We adopted a three-layer CNN as the target model, poison rate of 0.05, and a target label 'Airplane'. Figure (. (a) and I.(b) elaborate the Trojan attack detection results for a 2,000-size randomly selected subset of the CIFAR-10 10 dataset. As we can see, DATASIFTER significantly outperforms other approaches; for instance, achieves a detection rate of 90% with 46 % fewer inspected data points than the others.
II. Poisoned Data Detection. In data poisoning attacks, adversaries make slight modifications to some training samples to cause misclassification on target test samples. We evaluate different techniques feature collision attack (Shafahi et al.) 2018) and influence sunction-bssed attack (Koh) and Liang 2017). They are clean-label attacks where the attacker does not need to control the labeling of poisoned data. Figure (a. and II.(b) show the results for feature collision attack (Shafahi et al.. 2018) on a 500-size randomly selected CIFAR-10 subset, where 50 data points of class "cat' are perturbed with features extracted from 'frog' sample in the test set. We see that DATASIFTER significantly outperforms all other methods in the poisoned data detection task; for instance, it attains a 90% detection rate with 66 % fewer examined data points.
III. Noisy Feature Detection. Noise in features originated from sampling or transmitting (c.g.. Gaussian noise) may decrease classification accuracy. Following the settings in Wang et al. (2021a), we add white noise to clean samples, and we evaluate the performance of each technique on detecting those samples. For the CIFAR- 10 dataset, we corrupt 25% the training data images by adding white noise. Based on Figure (a) and (II, we conclude that DATASIFTED significantly outperforms all other methods on this task; for example, it achieves a 90% of detection rate by examining 67.25% % fewer data points. Meanwhile, the KNN-SV approach exhibits distinctive trend it only starts finding the noisy data points until filtering out a certain amount of clean data. This is mainly because all noisy data points are diit----iitriuttionn (OOD). A more detailed discussion is in the Appendix.
8

---

Under review as a conference paper at ICLR 2022
IV. Mislabeling Detection. Following Ghorbani and Zou (2019), perform experiments on two datasets and present the results of SVM trained on Enronl SPAM dataset (Shams and Mercer 2013) We adopt bag-of-wordd representation for training. The noise flipping ratio is 15%. Under this setting, influence-ban with gradient-based approaches. Figure (a)) show that DATASIFTER does attain the highest detection rate. This is because for SPAM dataset, the margin between the two classes is large so small amount of mislabeled samples do not significantly affect model performance; hence, those mislabeled samples could evade detection based on the validation performance. Such evasion acceptable as the model trained over the data points selected by DATASIFTER still achieves competitive accuracy (as shown in Figure 2 (V).)). On the other hand, KNN-SV and LOO can accomplish a good detection rate but end up with lower model performance. This is because they select very unbalanced samples, as both of them satisfy the symmetry axiom discussed in Section
techniques and G-SV are not applicable since they require the model trained
6.2.2 SELECTING HIGH-QUALITY DATA
V. Data Summarization. Data summa- rization aims to select a small, repre- sentative subset from massive dataset, which can retain a comparable utility to that of the whole dataset. We use CNN trained on the PubFig83 dataset in this experiment. Figure V shows that DATASIFTER and KNN-SV significantly outperform all the other methods.
50
Weighted Accuracy (96)
-90
Detxtatter
Perm-SV
Top-s Accurecy
80
G-SV
TMC-SV
1704-5V
70
20
LOO
200 400 600 800 1000 50
200 400 600 800 1000
Selected Data
Selected Date
Figure The experimental results for the case of selecting high-quality data (application V and VI). We depict the validation accuracy for both cases. A higher accuracy indicates better performance.
VI. Data Debiasing.
We explore whether techniques help select sub- set of training data that improves both fair- ness and performance for the ML task. We use logistic regression trained on the UCI Adult Census dataset as the task model. We measure the fairness by weighted accuracy the average of model classification accuracy over females and that over males. G-SV, KNN-SV, and Influence-basse techniques are not applicable for this application since they are designed for computing data importance when the metric is test accuracy or loss. Figure 3 VI shows that DATASIFTER achieves the top-tire performance along with the Perm-SV. We note that for this particular task, one can potentially further improve DATASIFTER' performance by changing the subset sampling distribution with more variation in the ratio of sensitive attributes, e.g.. gender in Adult dataset. Here, we stick with the uniform subset sampling as other tasks since we specific data issue type.
intend to evaluate general robustness instead of targeting
LIMITATIONS AND FUTURE WORK
We propose principled objective for achieving general robustness in data selection tasks. Based on the objective, we theoretically analyzed the worst-case performance of the existing data valuation- based algorithms and show that these approaches suffer unsatisfying performance guarantees. We present DATASIFTER, a new data selection paradigm guided by the theoretically optimal solution achieve general robustness against various data issue types, and we showed that DATASIFTER is closer to achieve the goal of general robustness than data valuation- approaches.
One limitation of our work is the scalability. While in Appendix F.5.9 DATASIFTER often more efficient than other algorithms with similar design goals of general robustness on large datasets, it could still be ineffective for very high dimensional data. Improving the scalability of DATASIFTER through some efficient approximation of data utility functions would be interesting future works.
Another future direction to explore other possible architecture or algorithm for utility learning. While DeepSet-bass utility models have shown promising results in our experiment, we can further exploit the approximate submodularity of common data utility functions and use more fine-grained architecturss/llorritns for utility learning, e.g., set transformer (Lee et al. 2019 or submodular regularizations (Alieva et a

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
The anonymized sample implementation for data utility learning and optimization is provided in httts::/tinyuz//
du doom//wwwwthhhbel]]]] The details of baseline implementations (as well as their source code link, if applicable) are provided in Appendix F.II The data preprocessing steps are described Appendix F.2 and detailed in Appendix F:3 The experimented data selection tasks are detailed in Appendix F33
The details of DeepSets implementations and data utility learning are
described in Appendix F.4
REFERENCES
Sanjay Krishnan, Jiannan Wang, Hugene Wu, Michael Franklin, and Ken Goldberg. Activeclean: Interactive data cleaning for statistical modeling. Proceedings of the VLDB Endowment, 9(12): 948-959, 2016.
Sanjay Krishnan, Michael J Franklin, Ken Goldberg, and Eugene Wu. Boostclean: Automated error detection and repair for machine learning. arXiv preprint arXiv:1711.01299 2017.
Sanjay Krishnan and Eugene Wu, Alphaclcan: Automatic generation data cleaning pipelines. arXiv preprint 1904v 11827, 2019.
Bojan Karlaš, Peng Li, Renzhi Wu, Nezihe Merve Gürel, Xu Chu, Wentao Wu, and Ce Zhang. Nearest neighbor classifiers over incomplete information: From certain answers certain predictions. arXiv preprint ar xxXv:20055005 2020.
Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y Zhao. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEEE Symposium Security and Privacy (SP), pages 707-723. IEEE, 2019.
Huili Chen, Cheng Fu, Jishen Zhao, and Farinaz Koushanfar. Deepinspect: A black-box trojan detection and mitigation framework for deep neural networks. In IJCAI, pages 4658 1658-4664, 2019.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International conference on machine learning, pages 325-333. PMLR, 2013.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference on Machine Learning, pages PMLR, 2018.
Zilong Zhao, Robert Birke, Rui Han, Bogdan Robu, Sara Bouchenak, Sonia Ben Mokhtar, and Lydia Y Chen. Rad: On-line anomaly detection for highly unreliable data. arXiv preprint 1rXiv:1911.04338 2019.
Min Du, Ruoxi Jia, and Dawn Song. Robust anomaly detection and backdoor attack detection via differential privacy. arXiv preprint 1rXiv:191..07116 2019.
Sanghyun Hong, Varun Chandrasekaran, Yigitcan Kaya, Tudor Dumitraş, and Nicolas Papernot. On the effectiveness mitigating data poisoning attacks with gradient shaping. arXiv preprint arXiv:2002.11497 2020.
Florian Tramèr and Dan Boneh. Differentially private learning needs better features (or much more data). arXiv preprint arXiv:2011.11660. 2020.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference Machine Learning, pages 1885-1894. PMLR, 2017.
Pang Wei Koh, Kai-Siang Ang, Hubert HK Teo, and Percy Liang. On the accuracy of influence functions for measuring group effects. arXiv preprint arXiv:/908 13289, 2019.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. arXiv preprint arXiv=2008.03370, 2020.
10

---

Under review as a conference paper at ICLR 2022
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In Interaational Conference on Machine Learning, pages 2242-222 2251.. PMLR, 2019.
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, pages 1167-1176. PMLR. 2019a.
Ruoxi Jia, Fan Wu, Xuehui Sun, Jiacen Xu, David Dao, Bhavya Kailkhura, Ce Zhang, Bo Li, and Dawn Song. Scalability vs, utility: Do we have to sacrifice one for the other in data importance quantification? arXiv preprint /91 1.000 2019b.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas Spanos, and Dawn Song. Efficient specific data valuation for nearest neighbor algorithms. arXiv preprint arXiv: 1908.0899,, 2019c.
Tianhao Wang, Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song. A principled approach to data valuation for federated learning. In Federated Learning, pages 153-167. Springer, 2020.
Tom Yan and Ariel D Procaccia. If you like shapley then you'll 'Il love the core, 2020.
Sasan Maleki. Addressing the computational issues of the Shapley value with applications in the smart grid. PhD thesis, University of Southampton, 2015.
Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. Advances in Neural Information Processing Systems, 33, 2020.
Chih-Kuan Yeh, Joon Sik Kim, Ian EH Yen, and Pradeep Ravikumar, Representer point selection for explaining deep neural networks. arXiv preprint 1811v:1811.099 2018
Tianhao Wang, Si Chen, and Ruoxi Jia. One-round active learning, arXiv preprint arXiv:2104.11843, 2021a.
Fred Glover and Abraham P Punnen. The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms. Journal of the Operational Research Society, 48(5):502-510, 1997.
Tianhao Wang, Yu Yang. and Ruoxi Jia. Learnabliity of learning performance and its application to data valuation. arXiv preprint arXiv:2107.063366 2021b.
Dongge Han, Michael Wooldridge, Alex Rogers, Shruti Tople, Olga Ohrimenko, and Sebastian Tschiatschek. Replication-robus, payoff-allocation for machine learning data markets. arXiv preprint arXiv:2006. 14583, 2020.
the forry-third annual ACM symposium on Theory of computing, pages 793-802, 2011. Maria-Florina Balcan and Nicholas JA Harvey. Learning submodular functions. In Proceedings of
Tianhao Wang, Zana Buçinca, and Zilin Ma. Learning interpretable fair representations. 2021c.
Michel Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization techniques, pages 234-243. Springer, 1978.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets. arXiv preprint arXiv: 1rXiv:1703.061 14, 2017.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
David Lewis and Jason Catlett. Heterogeneous uncertainty sampling for supervised learning. In Machine learning proceedings 1994, pages 148-156. Elsevier, 1994.
11

---

Under review as a conference paper at ICLR 2022
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Perey Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. arXiv preprint arXiv: /8829, 2019.
Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint (.Kiv:1770.0675535 2017.
Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen Cen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang. Trojaning attack on neural networks. 2017.
Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. arXiv preprint arXiv: 000..00000022. 2018.
Rushdi Shams and Robert E Mercer. Classifying spam emails using text and readability features. In 2013 IEEE 13th international conference on data mining, pages 657-666. IEEE, 2013.
Juho Lee, Yoonho Lee, Jungtack Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Tch. Set trans- former: framework for attention based permutation-invariie neural networks. In International Conference on Machine Learning, pages 3744-3753. PMLR, 2019.
Ayya Alieva, Aiden Aceves, Jialin Song, Stephen Mayo, Yisong Yue, and Yuxin Chen. Learning to make decisions via submodular regularization.
Kai Wei, Rishabh lyer, and Jeff Bilmes. Submodularity in data subset selection and active learning.
In International Conference on Machine Learning, pages 1954-1963. PMLR, 2015.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. A sharp concentration inequality with applications. Random Structures & Algorithms, 16(3):277-292. 2000.
Vitaly Feldman and Jan Vondrák. Optimal bounds on approximation of submodular and xos functions by juntas. SIAM Journal on Computing, 129-):11291170,, 2016.
Vitaly Feldman, Pravesh Kothari, and Jan Vondrák. Tight bounds on 1l approximation and learning of self- self- bounding functions. Theoretical Computer Science, 808:86-98, 2020.
Samyadeep Basu, Xuchen You, and Soheil Feizi. On second-order group influence functions for black-box predictions. In International Conference on Machine Learning, pages 715-724. PMLR, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. cow/exdb/nmist// 1998.
Kaggle. Dog cat.
Bryan Klimt and Yiming Yang. The enron corpus: A new dataset for email classification research. In European Conference on Machine Learning, pages 217-226. Springer, 2004.
Nicolas Pinto, Zak Stone, Todd Zickler, and David Cox. Scaling up biologically-inspired computer vision: case study in unconstrained face recognition on facebook. CVPR 201 WORKSHOPS, pages 42- IEEE, 2011.
Jinyu Zhao, Yichen Zhang, Xuchai He, and Pengtao Xic. Covid-ct-dataset: a ct scan dataset about covid-19. arXiv preprint arXiv:2003. 2020.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL htthhhttp///hhhhaa
ics. uci edu/mll
Hongjun Yoon. A machine learning evaluation of the compas dataset. In 2018 IEEE International Conference on Big Data (Big Data), pages 5474-5474. IEEE, 2018.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86 (6(11):2278-232, 1998.
Fabian Pedregosa, Gaël Varoquaux. Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830. 2011.
12

---

Under review as a conference paper at ICLR 2022
A
PROOF OF THEOREM I
Theorem 1. For n 2 3, there exists no linear heuristic M s.t. d(n, k) = for every E fl....,
Proof. Suppose, for contradiction, that there exists a linear heuristic M d(n, k) for all k. For a dataset D = (1,2,...,) n and utility function U, WLOG assume that the ranks (in non-ascending
order) output by M in the Step 2 of Definition [ iis (I....,7)). Then it means
U(())) USS) for all S s.t. [|S] 1,
U({1,2)) 2 US) for all S s.t. |S| = 2,
U(I,,..., - 1}) 2 U() for all S.t. |S| = 1. -n......--11. We construct a simple counter example of U to demonstrate such M does not exist: let n = 3, we define U as follows:
U(0) 0,
(20(= = 9,U((2,,3) = 10,
= U((1,2,3)) = 110
To make d(3, = 3, M must choose for k = 1. However, for size-2 subsets, .M can only choose
between [1, and (1,3), whose utilities are both ((2,,3)). Therefore, d(3, 2) = 3.
B PROOF OF THEOREM 2
To formally state and prove Theorem 2 we introduce the formal definition of data type here.
Definition 4. Given a dataset D and utility function U, for all subser S D {i,j}, we have U(SU (i)) U(S U (i)),
say two data points and j of the same type.
In other words, two data points are the same type if they will be scored equally by every linear heuristic that satisfies Symmetry Axiom. Theorem Searreemesssnttiin essentially says that for all linear heuristic that will assign different scores to different types of data points, their domination ratio can be further upper bounded. We stress that this is very mild assumption, especially when the space of the scores are continuous, which are the case for most of the existing data value notions.
To simplify the notations for set operations, we replicates of data point 2, and we denote the union of two data sets S U U.S = S + S2. The proof idea of Theorem is to construct balanced dataset that contains same amount of data points from different types. If linear heuristic M satisfies symmetry axiom, then M will select data points of the same type when the target selection number is small, as all data points the same type will receive the same scores. However, dataset contains only one type of data points will have nearly no utility.
{z} denote dataset that contains
Theorem 2 (Restated). If a linear heuristic M satisfies symmetry axiom and will always assign different scores for different types of data points, then the domination ratio d(n, k) of M upper bounded by [n/k] (I (ي]))) ()). In particular, when c = nz/ for some constant integer c, d(n, k) S (L) k-1 ( (1))))(m)
Proof. Suppose there are e types of data points: 21, Zc. Let r = n mod c. We construct the datasct D) that contains [n/c] data points for each of type 21...,, Zn-r. and contains nn/c] data points for each of type 2n-rt1,.... Zn, i.e., D = Σnn" In/c| x (2,) Em [n/c] {2). We construct utility function U as follows:
U()) = 0:
U(i {=1) de x (2e)) =
13

---

Under review as a conference paper at ICLR 2022
for every tuple of non-negative integers (61..... tc) s.t. 1 Σj=1 S except that U(k { =0
U(k x {21))
for all & I [_] This construction reflects the rationale that dataset that only contains type of data points (c.g., all of the same label) provide little information for training ML models.
Since M satisfies symmetry axiom, we know that all data points of the same type will receive the same scores. Besides, data points of different types will receive different scores by assumption. Therefore, when the target selection size k - 1x .M will return & x {zy). which has the worst utilities for subset at size and there are (c - ( single types of data points. For each k, by taking the largest possible such that l: S [x the desired bound. When c = n//k k: an integer, we have
r ((Tv/o) such subsets that only contains
we obtain
n/h d(n, k))
(1/0)am-11 (1/c)
where the second inequality is due to
Remark 4. The upper bound indicates that when S 2, the domination ratio is exponentially small for linear heuristics with symmetry property. We also note the assumption that M always assigns different scores for disferent data types can be further relaxed as long as there exists such balanced dataset described in the proof that M assigns different scores for different data types.
C PROOF OF THEOREM
Given dataset D {L,.... n and submodular utility function U, the Shapley value is computed as
Σ
1 (U) U(S)
Uchap
SCD(() (is))
Theorem 3 (Restated). The domination ratio d(n,,k) of Shapley value-based heuristics is 1/(2) for every n. 2 4 and any k (1......1 even if we restrict the data utility function U to be submodular.
Proof. We first consider the case when k 2 3.
We construct an instance of dataset D {l,..., n) and submodular utility function U follows:
U(0)= = 0; U((1)) = (((2)) .... U((K)) 7, (,((())) 5 for i i k+1
U(S) = 2 for all S... | k
U((I..., kb} = 24 4, U(S) 2k + for all other S s.t. |S| k;
U(S) = 2k + for all S s.t. |S] 2 ++
We can compute Shapley value according to its definition in
2(k
4(n
k)
3) + 2(x
-
U Ushap (1) _.. Ushap (k)
+
2(k
71
n 1
4n 2k 2
2k + +
n
n 1
2k 4(n k - 1)
Ushap (k: + 1) ... Ushap (n)
5
+ +
3) n-
4n - 2k 4
2k +
n
14

---

Under review as a conference paper at ICLR 2022
Since
1 n
1
2
Ushap (1) Ushap (k 1) 2
0,
n
n(n - 1)
we know that M will always output {1....,k) k). which achieves the lowest utility among all data
subsets of size k. Therefore, Shapley value's domination ratio d(n2, k) 1/()) for all 3 S k S n 1.
We then consider the case when k 2. The submodular data utility functions for the case of A: 2 be easily adapted as follows:
U(0) = 0:
U((1) = ((2)) = for 12:22 3; U( 8, U(S) = for all other S s.t. |S| - 2;
U(S) = for all S s.t. |S| 3.
The Shapley value is computed follows:
1
1
+
4(n 2)
Ushop (1) Ushap
7
n
1
3
11
n
n
1
1
+
4(n - 3)
Ushap(33 (3) =... Eshap (n))
+
+
71
1
(n 1)(n 2)
1
4
2
71
(n
1)(n 2)
Since
2 2
Ushap (1)
(shap(3) (3) =
2
n(n 1) > 0,
(R=1)
1 R
we know that M will always output f1...., .2, which achieves the lowest utility among all data subsets of size 2. Therefore, for Shapley value, d(n, 2) = 1/().
Finally, we consider the case when 1. Similarly, we construct submodular utility function as follows:
U(0)= = 0:
U((1)) 6, U(ft)) = for 2:
U((1,i)) = 11 for 2 (,U((()) for i,j 2 2;
U(S) 11 for all S |S| 3.
The Shapley value is computed as follows:
1 Uskap (1)
12 7
16
11
1
5+ 2(n - 2)
2(n 2n 3) (n 1)(n 2)
Ushap (i)
+
71
1
1
1
11
71
n1
12
Us)
Therefore, Shapley value's domination ratio d(n, 1/(1), which concludes the theorem.
15

---

Under review as a conference paper at ICLR 2022
D STOCHASTIC GREEDY ALGORITHM
For completeness, we briefly introduce the stochastic greedy algorithm (SG) for submodular optimization from Mirzasoleiman et al. (2013) here. The stochastic greedy algorithm is a simple approach that, for each iteration, randomly selects a subset of data and then finds the best data point within that subset. In the context of optimizing utility model (i.e., the trained DeepSets model), the "best data point" within each randomly selected subset refers to the data point with the highest marginal contribution (S U {=}) (S). where S is the set of data points selected in previous iterations. The pseudo-code outlined in Algorithm [ The distinction between this approach and the vanilla greedy algorithm is that the candidate data points to be selected in each iteration of stochastic greedy algorithm is smaller, randomly selected subset instead of all unselected data points. Thus, this approach is more efficient than vanilla greedy optimization and the runtime is linear in the number of dataset size to achieve - 1/e - optimization guarantee for monotone submodular functions (c is the precision parameter used in Algorithm Tp. Although its approximation guarantee has been proved only for monotone submodular objective functions, previous work (Wang) al. 2021a) as well our experiments show that it also achieve high empirical performance on data utility functions that are approximately submodular, therefore we use this algorithm for optimizing data utility models. Exploring different approaches for optimizing data utility models are interesting future directions.
ALGORITHM 1: Stochastic Greedy Optimization for Utility Model
input :dtaaset D, trained utility model Ü 22 -> IR, target selection size k, precision parameter for stochastic greedy algorithm
output A set S C D s.t. SS| k.
3 0.
for t = 1...,,k ., do
Sample R D S of size [Pl log(1/c) Find & = arg max_en ((SU{z}) S (z)
end
7 return S
E CHARACTERIZATION AND LEARNABILITY OF DATA UTILITY FUNCTIONS
Approximate Submodularity and Data Utility Functions. It has been empirically observed in prior works (Wang al.) 2021a) that the data utility functions of many commonly used learning algorithms exhibits approximate submodularity property. Submodular functions are almost always being characterized by the "diminishing return" property. Formally, a set function f 2" + R returning a real value for any subset S _ V is submodular if f((} US) f(S) 2 UT) fTT), YS T E V \ T. Figure shows some examples of the marginal contributions of a fixed data point versus the sizes of a sequence of data subsets. We can see clear "diminishing returns" phenomenon from the figure. That is, an extra training data point contributes less to model accuracy as the base training set size increases.
However, submodularity is an overly stringent condition to characterize data utility functions, es- pecially when the learning algorithm is stochastic. |Wang al. (b02 propose relaxation of submodularity condition for modeling common data utility functions as follows:
Definition 5 (3-relaxed submodularity (Wang et al.) 2021bb). We say that a set function f satisfies 3-relaxed submodularity for every $ CT C N, and every j N T,,
((TU < f ((SU ((S) + --"- (1T1-11)))))
(3)
It's been empirically observed that the above condition is satisfied by the data utility functions of commonly used learning algorithms for reasonable values of B. In particular, when < 1. the bias term (17((7)-1))) attempts to model the phenomenon that when the datasets are small, the
16

---

Under review as a conference paper at ICLR 2022
Marginal Contribution
Logistic
0.06
SVM
0.04
MLP
0.02
0.00
-0.02
0
100
200
300
400
500
Size
Figure 4: Figure I from Wang et al.
2a2 t An illustration of "diminishing return" property of data utility functions for widely used learning a algorithm (trained on USPS dataset).
contributions of an additional data point to the datasets have larger variance. Hence, when two data sets get more different in sizes, the contributions to two sets might deviate more from the exact submodularity property. When / = 0, this condition reduces to exact submodularity definition. However, this relaxation is mainly developed based on empirical experiments as well as mathematical convenience. There are no theoretical analysis for the correctness of the above characterization. Although the (approximate) submodularity seems very plausible and intuitive for commonly used data utility functions, the rigorous theoretical analysis is surprisingly hard. Submodularity has thus far been proved for only two simple classes classifiers-Nan Naive Bayes and Nearest Neighbors (Weil ct al. 2015). The rigorous proof of the approximate submodularity of more widely used models such as logistic regression and deep nets seem to be important future works.
Characterization of Data Utility Functions for Specifie Learning Algorithms. In Section 4 our only assumption of data utility functions is submodularity. Of course, analyzing more restrictive function classes can give tighter results. In fact, tight analysis of data utility function is possible for simple models (e.g., see the derivation for KNN and Naive Bayes in Wei et al. (2055). Such analysis seems to be intractable for more complicated models such as deep neural networks. Hence, in Section f we tried to find the most restrictive function classes for describing data utility functions without losing generalizability to commonly used ML models. Given the current literature, (approximate) submodularity appears to be the most restrictive function class that can well describe the data utility functions for commonly used ML models. Hence, we devote our analysis Section utility functions.
submodular
Theoretical Analysis of the Learnability of Data Utility Functions. Wang et al. 2021h) also shows that any set functions with range [0, 1] and satisfy the relaxed submodularity condition in to a larger function class called self-bounding functions (Boucheron et al. 2000). This class of functions is known for the dimension-free concentration bound and has been proven to be efficiently learnable (Feldman and Vondrák 2016 Feldman et al.) 2020) under mild conditions. This could serve as an insight into why data utility functions can be efficiently learned.
Equation belongs Dellnss
F EXPERIMENT DETAILS AND ADDITIONAL RESULTS
F.1 BASELINE IMPLEMENTATION
The settings of baselines are summarized in Table For fair comparisons between DATASIFTER and baselines, we fix the total number of utility sampling as 4000 for DATASIFTER and all baseline algorithms that require utility sampling, including Perm-SV, TMC-SV, G-SV, and LC. For each sampled subset S. we only train model on once to approximate (S). Following the settings in Ghorbanni and Zou 2019). set the performance tolerance in TMC-Shapley 10-3 Following the
17

---

Under review as a conference paper at ICLR 2022
Baseline
Settings and Hyperparameters
Perm-SV
TMC-SV
Tol = 10
G-SV
hyper-parameter search for specific learning algorithm
KNN-SV
K 5, use exact calculation formula Break tie by least core vector that has the smallest Eg norm
LC
LOO
Rank according to influence on the model loss over the clean validation data (the higher, the better): for neural networks, we use stochastic estimation where recursion depth is 5000 and the number of iterations as 10 or larger
INF
Rank according to influence the model loss over the clean validation data (the higher. the better); use exact TracIn described in Pruthi al. (2020] Rank according to influence on the model loss over themselves (the lower, the better)
TracIn-Clean
TracIn-Self
Table 3: Summary of Baseline Settings.
Jia settings in Jia al. (2019c). we set K 5 for KNN-Shapley. We use CVXOPT library solve the constrained minimization problem in the least core calculation. For influence function technique, we rank training data points according to their influences on the model loss over the validation data. The code is adapted from the PyTorch implementation of influence function on GitHut For TracIn technique, we use all the parameters in model. We use the exact TracIn instead of the more efficient TracInCP described in Pruthi et al. (2020). That is, we trace the influence of data point 2 on the loss of 2 by sum over all iterations (not checkpoints) in which 2 is chosen in the batch. TracIn-Self is only used for bad data selection tasks. The intuition is that bad examples are likely to be OOD and have strong influence for themselves. Therefore, when using TracIn-Self to detect bad data, we sort training examples by decreasing self-influence. On the contrary, when using Inacln-Clean, we sort training examples by increasing influence on clean validation data.
For the second-order influence function method from Basu al. 2022)), since the group selection method proposed in the paper is extremely expensive (in addition to the expensive nature of influence function), we do not compare with their method.
F.2 DETAILS OF DATASETS USED IN SECTION 6
CIFAR-10 (rrizhessyy et al. 2009). CIFAR-10 consists of 60,000 3-channel images in 10 classes (airplane, automobile, bird, cat, deer, dog, frog, horse, ship and truck). Each image is of size 32 x 32.
MNIST (LeCun 1998). MNIST consists of 70,000 handwritten digits. The images are 28 x 28 grayscale pixels.
Dog vs. Cat (Kaggle). Dog vs. Cat dataset consists of 2000 images (1000 for 'dog' and 1000 for 'cat') extracted from CIFAR-I0 dataset. Each image is of size 32 x 32.
Enron SPAM (Shams and Mercer 2013). Enron SPAM dataset consists of 2000 emails extracted from Enron corpus (Klimt and Yang 2004). The bag-of-words representation has 10714 14 dimensions, and we perform x" test to the dataset to retrieve only 10% best features (so the feature dimension becomes 1071).
PubFig83 (Pinto et al., 2011). PubFig83 is a real-life dataset of 13,837 facial images for 83 celebrities, where the images are of varying quality, e.g., some images contain two human faces. We resize each image to 32 x 32.
Covid-CT (Zhao al. 2020). The COVID-CT-Datall has 746 CT images in total, containing 349 images from 216 COVID- patients and the rest of them are from healthy people. The dataset is separated into 543 training images and 203 test images. We resized each image 32 x 32.
httos://cvxgpt.org//
18

---

Under review as a conference paper at ICLR 2022
Data Quality Issue
Dataset
Size
Bad Data Rate
Relevant Hyperparameters
Backdoor- - Trojan Attack
CIFAR-TO TO
2000
0.05
Square ingger on bottom-right corner
Backdoor BadINets
MNIST
1000
0.25
Pattern Backdoor on bottom-nght corner
Poisoning Feature Collision
CIFAR-10
500
3
0.25, learning 500 255, 120 iterations
Pojsoning Influence-uused
Dog Vs Cut
2000
0.025
0.02, 100 iterations
Noisy Feature
CIFAR-I0
2000
0.25
coordinate-wise Gaussian noise with
Noisy Feature
MNIST
1000
0.25
coordinate-wis Gaussian noise with
Mislabeling
SPAM
500
0.15
Plip label uniformly at random
Mislabeling
CIFAR-TO 1O
500
0.25
Flip label uniformly at random
Table 4: Summary of Hyperparameters in Bad Data Detection tasks. For Feature collision data
poisoning attack, we followed public source code https: //gi thub. com/Trutted-AT http://aannnaa.tttaaaaa/////////
eoversarial--obustee
. py to apply the poison frogs attack (feature collision attack). The implementation does not hardcode the dynamical calculation of the dimension of the feature layer, thus requiring larger learning rate obtain similar coefficients. We fine-tuned the model with a learning rate (A) of 500*255.0 and obtained the successful attack.
Feature_co htw.uure_oolisson_ttttteoee
UCI Adult Census Duua and Graffi 2017). The Adult dataset contains 48,842 records from the 1994 Census database. Each record has 14 attributes, including the sensitive gender and race information. The task is to predict whether one's income exceeds $50K/yr based on census data. The categorical attributes in the dataset are one-hot encoded.
COMPAS YYon, 2018). We use a subset of the COMPAS dataset that contains 6172 data records used by the COMPAS algorithm in scoring defendants, along with their outcomes within two years of the decision, for criminal defendants in Broward County, Florida. Each data record has features including the number of priors, age, race, etc. The categorical attributes the dataset are one-hot encoded.
F.3 EXPERIMENTS IMPLEMENTATION
The attack success rate of backdoor attacks is measured by separate test backdoored dataset. For the experiment on backdoor detection, data poisoning detection, noisy detection, and mislabel detection on the CIFAR- 10 dataset, the CNN model follows each with the ReLU as the activation function, and followed by three fully-connected layers. For the experiment on Backdoor detection and noisy feature detection the MNIST dataset, use LeNet adapted from LeCun et al.) (1998,, which has two convolutional layers, two max-pooling layers, and one fully-connected layer. For the experiment on data summarization on PubFig83, we use simplified VGG architecture For the experiment on poisoning detection over the Dog vs. Cat dataset as well as the data summarization over the COVID-CT dataset, we use a small CNN model adapted from Py PyTorch tutoria We use Adam optimizer with learning rate 10 10-3, mini-batch size 32 to train all of the models mentioned above for 30 epochs, except that we train LeNet for epochs on MNIST. For the experiment on data biasing on the Adult dataset, we implement logistic regression in scikit-learn (Pedregosa et al. 201T) and use the Libl.inear solver. For the experiment on mislabeling detection on SPAM and data debiasing on COMPAS, we adopt SVM implementation from scikit-learn library (Pedregosa et al. 201 with RBF kernel. The x" test used for pre- pre-processing Enron SPAM dataset is implement by scikit-learn library for univariate feature selection.
has two convolutional layers. A max- max-pooling layer
F,4 DATA UTILITY LEARNING CONFIGURATION
A DeepSets model is set function f(S) (E,c ((x)) where both p and are neural networks. Since summation does not depend on the permutation of elements in S, the architecture is permutation- invariant and thus set function. In experiment, both and p networks have three fully-connected layers. We note that ó network can also be convolutional for image datasets. However, we find that for image datasets CIFAR-10, Dog vs Cat, PubFigg3 and Covid-CT, it is better to use the data features extracted by the convolutional layers of the target model (trained on the full training set) as the input for DeepSets models. All labels are one-hot encoded, and each label vector y is concatenated with
far 1 htmm
19

---

Under review as a conference paper at ICLR 2022
Synthetic Dataset
CIFAR-10 Dataset
Predicted Accuracy
0.9
Predicted Accuracy
30
0.8
25
0.7
20
0.6
15
0.5
10
0.5
0.6
0.7
0.8
0.9
10
15
20
25
30
True Accuracy
True Accuracy
Figure 5: Predicted vs. True Utility for unseen subsets of (a) logistic regression classifier trained on synthetic dataset, and (b) CNN model trained on subset of CIFAR-10 dataset.
the corresponding data feature vector 24, and then feed (24, y:) into the DeepSets model as the input. We tune the DeepSets model architecture for different datasets. For the COMPAS dataset, we set the number of neurons in every hidden layer and the dimension of set features (i.e., the output of network) to be 64. For all other datasets, we set the number of neurons and set dimension to be 128. use the Adam optimizer with learning rate 10-4, mini-batch size 32, 31 0.9, and [3 = 0.999 to train all of the DeepSets utility models, for up to 20 epochs. The number of utility samples 4000 for all experiments, as mentioned in Section To sample a subset, we first uniformly pick a set size, and then uniformly sample subset of the given size without replacement. We left exploring the relationship between subset sampling distribution and data selection performance as our future work. The validation data in utility sampling are 500 clean data points sampled from the test data of the corresponding datasets.
F.5 ADDITIONAL RESULTS
F.5.1 GENERALIZATION OF DATA UTILITY LEARNING
In Figure show examples of correlation plot between predicted and actual data subset utility. For Figure 5 (a), the data utility function is the validation accuracy of logistic regression model trained on synthetic dataset. For the synthetic data generation, we sample 200 data points from a 50-dimensional Gaussian distribution, where the covariance matrix is identity matrix and the 50 mean parameters are sampled uniformly from [-1, Each data point is labeled by the sign of the sum of the data point vector. Since logistic regression problem is convex and has unique global minimum, the data utility has smaller variance due to the randomness in learning algorithm and thus utility prediction is relatively accurate. For Figure 5 (b), the data utility function is the validation
accuracy CNN model trained on subset of CTFAR-10 dataset of size 2000. Since learning neural networks is non-convex problem, the variance in data utility from the optimization process relatively large, the utility prediction error is also relatively large. However, we can still need strongly positive correlation between the predicted and true data utility, which means that the data utility model is still able to differentiate between subsets with large utility gaps.
F,5.2 EFFECT OF SYMMETRY AXIOM
To better illustrate the issue raised by symmetry axiom (Section we evaluate data selection performance of LOO, Shapley, and least core heuristic on synthetic dataset with training data points (so that we can compute the exact Shapley and least core values, as well as obtain the optimal subset). The tiny synthetic dataset is generated by sample data points from a 2-dimensional standard Gaussian distribution, where the mean vector of the Gaussian distribution is (0.1, -0.1). Each data point is labeled by the sign of its vector's s sum. We first sample 9 data points with positive label and 2 data points with negative label. We then replicate each of the two negatively labeled data points for two times. To simulate natural noise, we add Gaussian noise to the copied data vector with scale 10-5, By sampling and copying, obtained 15 data points with natural redundancy. The utility
20

---

Under review as a conference paper at ICLR 2022
Optimal
Shapley
LOO
Lcast
1.0
Validation Accuracy
0.9
0.8
0.7
0.6
0.5
8 10
12
14
# Selected Data
Figure 6: Results of data selection with different heuristics on tiny dataset with natural redundancy. Dataset and implementation are detailed in the Appendix.
metric is the test accuracy of a Support Vector Machine (SVM) classifier trained on the dataset. Since there are only data points with negative label, they tend to be assigned with larger (and similar) importance scores by linear heuristics like Shapley value. Both Shapley and Least core thus rank negative points with higher importance. This means that when the target selection size less than the selected dataset contains only data of negative label and no information about the positive label class at all. As shown in Figure 6. both Shapley and Least core achieves trivial utility for the first selected data points. With small selection budgets, the subsets selected by all the heuristics have low utility as the heuristics fail to promote diversity during selection due to symmetry axiom, and thus suffer poor data selection performance.
F.5.3 BACKDOOR ATTACK
We consider the two most popular types of backdoor attacks, namely the BadNets (Gu et al. 2017) and the Trojan square trigger (Liu et al.) 2017). Those two attacks' major difference is the trigger itself, where BadNets adopts a white block trigger at the right corner, and Trojan attack adopts a square trigger.
Here, we show the results of DATASIFTER and baseline techniques over detecting BadNets triggers on MNIST dataset. The poisoning rate is 0.25, and the target label is '0', The performance of different techniques is illustrated in 7 methods in the detection rate and significantly reduces the attack accuracy after filtering out bad data points. Besides, we can see that TracIn-Clean and influence function exhibits similar trends, which only starts finding the adversarially perturbed data points until filtering out a certain amount of clean data (same thing happen for data poisoning detection). We conjecture that this is because adversarially perturbed data points are designed change the model prediction of particular target examples; each individual perturbed data point, however, does not have significant impact on the loss of clean validation data. Besides, adversarially perturbed data points are similar and their influence on validation data is also similar in nature, thus they tend to be ranked together by influence- basedd methods.
and I.(b). We can see that DATASIFTER outperforms all other
F.5.4 DATA POISONING ATTACK
We discuss two popular types of clean-label data poisoning attacks. Feature collision attack (Shafahi jet al. 2018) crafts poison images that collide with a target image in feature space, thus making difficult for model to discriminate between the two. Influence function-based based poisoning attack (Koh) and Liang 2017) identifies the most influential training data points for the target image and generates the adversarial training perturbation that causes the most increase in the loss on the target image. The Attack Success Rate is measured by the model's 's confidence on the prediction of poisoned data (with respect to the target label).
Figure 7 (a) (b) show the results for influence dunetion-based attack on Dog vs. Cat dataset, where 50 data points of class 'cat" perturbed to increase the model loss 'dog" sample in the test.
21

---

Under review as a conference paper at ICLR 2022
DataSifter Perm-SV
TMC-SV
KNN-SV
LOO
Tracin
G-SV
LC
INF
Random
1.0
Pct. Selected Noisies
Detection Raie
Detection Rate
0.8
Detection Rate
0.8
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.0
0.0
0.0
200
400 600 8001000
500
1000 1500 2000
500
1000
100
200
300
400 500
I.(a)
Inspected
11.(0)
Inspected Data
[11.(a)
Inspected Data
IV(a)
Inspected
Attack Success Rate (%)
100
27.5
Attack Accuracy (%)
80
Model Accuracy(9)
90
25.0
80
85
Accuracy
22.5
60
20.0
40
75
17.5
70
15.0
20
20
12.5
60
10.0
1000
100 150 200 250
14b)
Thrown Data
11,(b)
# Thrown Data
11I(b)
# Thrown Data
IV.b)
Thrown Data
Figure 7: The experimental results and comparisons of the DATASIFTER under the case of filtering out harmful data (application I-IV). The light blue region in each (a) graph represents the area that method is no better than a random selection. For I.bb) and II.(b,, we depict the Attack Success Rate (ASR), where lower ASR indicates more effective detection. For III.(b) and IV.(b), show the model test accuracy, where a higher accuracy means a better selection.
set. As we can see, DATASIFTER is a more effective approach to detect poisoned data points than all other baselines.
F,5.5 NOISY FEATURE
We follow the same evaluation method for noisy data detection as in Section with another setting: LeNet model trained noise polluted MNIST. We randomly select 1000 data points and corrupt 25% of them with white noise. As shown Figure 7 (I).(a)) (b), we can see that although KNN-Shapley achieve slightly better performance in detecting noisy data points, DITASIFTER still retains higher performance for model accuracy. Besides, similar to the case for CIFARIO, we find that the KNN-SV approach only starts finding the noisy data points until filtering out certain amount of clean data. This is mainly because all noisy data points are out- cutt-o--disrrbuutiin (OOD), shown in Figure (b). The mechanism of KNN-SV. however, tends assign values to OOD data points while assign negative values to clean data points that are in-distribution but have different labels from their neighbors. Figure gives a visualization of the distribution of KNN- Mha-lly values.
F.5.6 MISLABELED DATA
We conduct another experiment on noisy label detection: a small CNN model trained on 500 data points from the CIFAR-10 dataset. The noise flipping ratio is 25%. The performance of mislabel detection shown in Figure (a).). As we can see, no techniques are particularly effective in detecting mislabeled data for this task. Only KNN-SV and TracIn-Self achieves slightly better performance than other approaches. We conjecture that the difficulty of mislabel detection on CIFAR- 10 dataset due to the following reason: since an oracle for detecting mislabeled data points can also be used to implement classifier, the difficulty of mislabeling detection is at least as difficult as classification. classifier directly trained on the 500 clean data points this experiment, however, can only attain around 28% test classification accuracy. Nevertheless, Figure 7 (Vb shows that DATASIFTER only achieves slightly worse model accuracy than KNN-SV after filtering out selected bad data points. Besides, data points than others, does not lead to higher accuracy for the selected data as TracIn-Self ignores data interaction and end up selecting similar data points.
that although TracIn-Self is able to filter out more mislabeled
22

---

Under review as a conference paper at ICLR 2022
5-
KNN SV
566
2000
2000
2000
10 15 20
data index
(a)
(b)
Figure 8: (a) normal image from CIFAR-IO, (b) an example of noisy data image, (c) a sample of KNN-Shapley values, where data points with index < 500 are noisy. data point with higher KNN-Shapley value considered more important.
F.5.7 DATA SUMMARIZATION
As another setting for the data summarization appli- cation we consider, we use the patient CT images from COVID-CT dataset for a binary classification task,
Weighted Accuracy (%)
90
DataSifter
Perm SV
Accuracy (%)
85
TMC-SV
80
G-SV
65
75
LC
LOO
70
INF
which aims to determine whether an individual is diagnosed with COVID-19 or not. The CNN model trained the dataset achieves around 72% classification accuracy. Figure 9 V. shows the results for selecting up to 400 data points with different techniques. As we can see, DATASIFTER achieves the best model accuracies on the selected data points along with KNN-SV.
65
Random
200
100 150
V.
# Selected Data
VI.
Selected Data
Figure The experimental results and comparison of the DATASIFTER under the case of selecting high-quality data (ap- plication V and VI). We depict the validation accuracy for both cases. A higher accuracy indicates a better performance.
F.5.8 DATA DEBIASING
We introduce another data debiasing experiment on the criminal recidivism prediction (COMPAS) task, where races considered the sensitive attribute. The utility metric adopted here is the average accuracy across different race groups. The learning algorithm we use SVM with RBF kernel. Baselines including G-SV, KNN-SV, and ceattence-basee techniques not applicable for this application due to the utility metric and learning algorithm we use. Figure VL. shows the results for DATASIFTER and the remaining five baselines. We that DATASIFTER again achieves the top-tire performance.
F.5.9 UTILITY OPTIMIZATION ON LARGER DATASETS
We compare the scalability between DATASIFTER and other baselines on large datasets. We show the results for backdoor detection on a 10,000-size Trojan square poisoned CIFAR-10 dataset here. For DATASIFTER, we only sample data subset utilities from 1000 data points (10% of the whole dataset), while the learned utility model (the DeepSets model) is optimized over the entire 10,000 data points. The intuition of this approach is that the learned utility model can provide utility estimations for sets of seen data points as well as unseen data points. Therefore, the greedy optimization can be performed Since the learned utility model may not generalize well on dataset of sizes greater than 1000, we start over the optimization process once the selected data points exceed 1000, and then select another 1000
larger dataset even if the utility learning is smaller subsets.
23

---

Under review as a conference paper at ICLR 2022
Attack Success (%)
100
Detection Rate
0.8
80
0.6
60
DataSifter
Tracin Self
0.4
40
KNNN SV
Tracin-Clean
20
2500 5000 750010000 Inspected Data
1250
2500 3750 5000
(b).
# Thrown Data
Figure 10: The experimental results and comparison of the DATASIFTER and baseline algorithms for detecting backdoored data larger datasets.
data points until we reach the target selection budget. The pseudo-code is summarized in Algorithm
ALGORITHM 2:
Utility Optimization on Large Datasets
input dataset D, trained utility model Ú, target selection size k. the maximium size of sets where U has seen during utility training B (usually much smaller than D), precision parameter for stochastic greedy algorithm e.
output:A AA set S C D s.t. |S| k.
+ 0. So < 0.
for t 1...., do
10
Sample _ D of size k
[D] log(1/c).
Find = = arg max ER ÚSU (z)).
11
So < 5o U [z].
12
if [Sp B then
14
= S UU..
Su < 0.
16
end
17
S SUSSU So-
18 end
return 5
When executed on NVIDIA Tesla K80 GPU, the clock time for the utility sampling step within 15 hours for 4000 utility samples with a small CNN model, as the data size is fairly small. The LOO, the Least core, and all the Shapley value-based approaches except KNN-SV did terminate in 24 hours, so we remove them from comparison. As we can see from Figure TO DATASIFTER once again outperforms all the remaining approaches. The results show that the learned utility model can provide utility estimations for sets of unseen data points, which largely improves the scalability of DATASIFTER. On the contrary, the existing valuation- basedd approaches cannot predict the importance of unseen data points. Thus their utility sampling has to be conducted
the entire dataset.
Follow the same method in Algorithm 2. we perform noisy data detection on a 20,000-size CIFAR-10 dataset. The corruption ratio 25%. Again, for DATASIFTER, train the utility model utility samples collected from retraining on subsets of 1000 data points (5% of 20,000). We remove the LOO, the Least core, and all the Shapley value-based approaches except KNN-SV from comparison, as they did not terminate in 24 hours for 4000 utility sampling on the 20,000-sizi set. As we can see from Figure II (a) and (b), DATASIFTER significantly outperforms all other baseline techniques except TracIn Clean. However, TracIn-Clean only starts finding bad data after filtering out certain clean data points. The results demonstrate that although the utility sampling step could be expensive, the scalability of DATASIFTER can be boosted by the predictive power of the learned utility model.
24

---

Under review as a conference paper at ICLR 2022
1.0
75.0
Detection Rate
0.8
72.5
70.0
DataSifter
Tracin Self
0.4
65.0
62.5
Tracin-Clean
0.2
60.0
Random
0.0
10000
20000
2500 5000
7500 10000
# Inspected Data
(b).
Thrown Data
Figure 11: The experimental results and comparison of the DATASIFTER and baseline algorithms for detecting noisy data on larger datasets.
25


Reviews:
[{"review_id": "yf1c2kDtP0q", "reviewer": "Reviewer_yuTL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I enjoyed reading the paper.  It was well-structured, easy to follow, and presented ideas clearly.  Nonetheless, it is my view that the paper still needs more work in particular around the experimental evaluation.\n\n**Strengths**: \n\n1) The idea of training empirical estimator $\\hat{U}$ is simple (a strength) and nice.  \n\n2) Most recently published methods too narrowly target specific forms of “bad data”, specific learning domains (e.g., vision), specific model types, or even specific adversarial attacks.  More work needs to be directed towards agnostic robustness, which the authors do here.  Such general-purpose methods are generally harder to achieve (both theoretically and empirically) and are more useful in practice.\n\n3) Your empirical evaluation includes an impressively large number of baselines.  This level of thoroughness is commendable. \n\n**Weaknesses**: \n\n1) The proposed methodology relies on utility metrics displaying \"'approximate' submodularity.\"  Intuitively such submodularity is very plausible.  However, more detail is needed.  A more quantitative understanding/definition of what constitutes \"approximate\" would be appreciated.  Similarly, reading the first paragraph of Sec. 5 seems to imply that while many potential applications exhibit \"'approximate' submodularity\", others do not. Even if it only appears in the supplement, expanding this discussion so a potential reader knows when DataSifter applies (and more importantly when it does not) is important.  It is also unclear how the submodularity approximation affects DataSifter’s practical worst case performance.\n\n2) Beyond the number of baselines, I have concerns about other aspects of your experimental design.\n\n* I would have appreciated seeing empirically how well $\\hat{U}$ performs in practice (e.g., a correlation plot between predicted and actual subset utility perhaps across different size subsets).  This could be in the supplement.\n\n* Reviewing your supplemental materials, most of the models you consider are small in size (please correct me if I am wrong).  Do you have any analysis on large models -- e.g., SOTA, modern transformers?  Even if numerical values cannot be included now, can you anecdotally speak to how well your method has performed on such models (both in terms of execution time and numerical performance)?\n\n* Mislabeling Detection (6.2.1.IV) - It seems that DataSifter underperforms some Shapley Value-based methods for moderately sized datasets.  I did not find the explanation around small amounts of data not affecting validation accuracy very strong.  While in absolute terms, the change in accuracy is small, the relative change in error rate seems large.  Perhaps I am missing something.\n\n* For the experiments, I would have preferred a table in the supplemental materials that summarized the various dataset sizes, attack set sizes, perturbation distances etc.  It was time consuming to piece that various information together from reading the individual paragraphs.\n\n* If I understood Sec. 6.2.1 and suppl. Sec. E.5.2 correctly, the backdoor experiments used a poisoning rate of 20%-25%, which is high and somewhat unrealistic in practice.  Also, by having a high poisoning rate, influence based methods generally will perform poorly since the effect of the attack is diffused over all the attack samples.  How does your method perform with much smaller poisoning rates?\n\n* Methods like TracIn and Influence Functions consider a specific target example.  Are the attack success rate values w.r.t. to the specified target or any backdoored sample?  How was the target selected?\n \n* In suppl. Section E.3, your proposed model for CIFAR10 has two convolutional layers and three fully-connected layers.  This seems a peculiar choice for CIFAR10 classification and probably would not perform well on larger dataset sizes.\n\n* Section E.5.8 mentions that Influence Functions (i.e., LOO) took >24 hours on a small CNN model.  Having worked with influence functions before, including the source implementation you cite, this seems quite high.\n\n* For TracIn, sampling every 15 epochs seems too sparse -- especially if you are training only 30 epochs and seems more akin to TracInCp than TracIn -- correct me if I misunderstood.  Also, reviewing Pruthi et al. again, using only the last linear layer is a speed-up due to limitations with Influence Functions.  Did you compare to TracIn using all layers as well?\n\n    * Further to this end, it would be helpful if you had a table of the hyperparameters for the various methods (e.g., influence functions) to determine how the corresponding baseline hyperparameters were set.  That would allow me to better evaluate your setup.\n\n* Since you are considering groups of points, perhaps second-order influence methods that directly consider group effects would have been a better baseline choice.  See for example: Basu et al. 2021 “On Second-Order Group Influence Functions for Black-Box Predictions” or Koh et al. 2019 “On the Accuracy of Influence Functions for Measuring Group Effects”.  If these baselines do not work, please provide more of an explanation why.\n\n**Questions**\n\n1) I assume $\\mathcal{A}$ can be stochastic (e.g., in initial parameters, batch sequence, underlying implementation like CUDA).  Should Objective (1) then be the expected utility over randomization?  If Objective (1) is shown as deterministic for simplicity, that should be stated.\n\n2) Did you observe randomization having any effect on $\\hat{U}$’s performance (e.g., restarting analysis leading to meaningfully different utility predictions)?  As mentioned above, I did not see any ablation-like analysis of just this component of the method.\n\n3) Do any alternatives exist to DeepSets (Zaheer et al 2017), and if so why did you select DeepSets over alternatives?\n\n**General Points**\n\n* In the abstract, you specify a “key insight”, but I was unsure of its intended meaning. It seemed like the most likely meaning was that the “bad data” does not contribute much (if anything) to a model’s corresponding performance metric(s).  This feels like an elementary insight so I think I may have missed your intended idea.\n\n* You use the term “general robustness” in the introduction’s first paragraph.  When I read it, I was not sure exactly what you intended (it does becomes clear later).  General robustness is a clear strength of your method so being explicit on this definition earlier may be more impactful to a reader.\n\n* A reference that seems related to your work is Feldman & Zhang from NeurIPS’20.\n\n* I think your claims of general robustness would be significantly strengthened if you had more empirical evaluation on NLP data.  SPAM is used but the bag of words representation is somewhat simple and outdated.\n\n* There is a good number of typographical errors in the main text.\n", "summary_of_the_paper": "This paper proposes, *DataSifter*, an optimization-based, general-purpose framework for filtering \"bad data\" from a training set.  General-purpose broadly covers different data corruption types (e.g., adversarial perturbation, label noise, etc.), different model architectures, and performance metrics (e.g., test error).", "summary_of_the_review": "Promising paper with clear ideas.  I have concerns in particular around the evaluation as detailed above.  Author response is important for my setting of the final score.\n\nEdit: The authors provided thoughtful detailed reviews and addressed many of my concerns.  Their responsiveness and turnaround time on feedback was quite remarkable and duly noticed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "pJLiO79bV-", "reviewer": "Reviewer_4LgM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and easy to follow. The problem of identifying harmful or bad training data is interesting and important in dataset creation and cleaning. The theory for worst case performances of valuation based approaches is motivating but it doesn't necessarily imply the method will fail as it's only a worst case analysis. The other drawback is that the DataSifter algorithm is highly empirical with no theoretical support. Some detailed comments are made as follows.\n\n1. The counterexamples in Theorem 1 to 3 are highly constructive in $U$ and might not reflect actual performances of linear heuristics on real datasets. Especially if the utility function has certain structure and cannot be defined arbitrarily. The experiment in E.5.1 uses SVM as utility metric which as a special instance can be much better than the worst-case performance bound (and the same is also true for a wider range of utility functions used in practice). I would like results more with additional constraints on the utility function or lower bounds for a particular class of utility functions used in practice.\n2. The paper shows good empirical performance of the DataSifter algorithm in certain identification tasks. It seems a bit unrelated to the first part of the paper as the good performance for some datasets doesn't imply a higher worst-case lower bound. A more reasonable comparison is to either provide a better worst-case lower bound for DataSifter (maybe under assumptions like exact recovery $\\widehat{U} = U$) or as pointed out in my first point to give instance-specific performance upper bound for the valuation-based approaches.\n\nIn all, I think the paper gives some interesting empirical results but the theory doesn't exactly corroborate the main argument that we should prefer DataSifter over coventional heuristics. I incline to reject the paper.", "summary_of_the_paper": "In this paper, the authors study the problem of data selection in the presence of bad training data by maximizing the utility function $U$ over all subsets of cardinality $k$. The authors first show that the valuation based approaches can have bad performances, and propose the DataSifter algorithm to approximately solve the combinatorial optimization problem.", "summary_of_the_review": "The paper provides worst-case analysis of data selection using linear heuristics, revealing potentially hazards using valuation-based approaches, which is interesting and novel. However, it doesn't exactly corroborate the main argument that we should prefer DataSifter over coventional heuristics.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "oSJpsC4xjKm", "reviewer": "Reviewer_GEXW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the paper is clearly written and presents a novel framework to identify bad training data. Empirical results and comparison with baselines look interesting. \n\nHowever, I have the following concerns with the work: \n\n-  Proposed method (as described in Section 5) is based on a set learning phase where the task is the following: Given a training set, the aim is to learn how an underlying model when trained on that training set will generalize to unseen data from the same distribution. Their method DATASIFTER crucially depends on this step. However, this set learning problem is in general underspecified and hence hard to tackle. At a high level, to perform well on this task, the set functional learning architecture would not only need to mimic the underlying model trained on some training set (without actually using that model) but would also need to understand how the underlying model generalizes. The authors present no empirical evidence their algorithm solves this task in a reasonable manner.  Some empirical results showing correlations would be interesting to see. \n\n- Models considered in the work are small in size as compared to the state-of-the-art models. Is there any specific reason for this? ", "summary_of_the_paper": "This paper focuses on the problem of identifying bad training data when the underlying cause is unknown in advance. Authors develop an algorithmic framework, DATASIFTER, for general robustness to bad training data. Empirical evaluation show efficacy of DATASIFTER in a wide range of tasks, including backdoor, poison, noisy/mislabel data detection, data summarization, and data debiasing", "summary_of_the_review": "The proposed framework of DATASIFTER is interesting and novel with promising results. However, the method primarily depends on a set selection phase for which no empirical/theoretical evidence is provided.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TxEIr7YUcRK", "reviewer": "Reviewer_s9Xw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\\textbf{Strength:}\n\n1. This paper suggests an algorithmic framework based on utility optimization approach to achieve robustness against general bad data. The method performs well empirically. \n\n2. Theoretically shows that Shapley value based methods has small domination ratio.\n\n\\textbf{Weakness:}\n\n1. Regarding Theorem 3: \"...even if the data utility function U is submodular\"  Bad worst case performance could be due to restricting U to be submodular. What happens if U is not submodular? I disagress with the choice of words \"even if\". In my opinion it should read \"...when the data utility function U is submodular.\"\n\n2. It should be highlighted clearly in the main paper (not in appendix) that the better empirical performance is for a specific choice of utility function $u$, ,e.g., average accuracy in debiasing. Since choice of utility function is the most important part of detecting bad data, and the supremacy of one method over the other may not hold for a different utility function. \n\n3. The authors criticize linear heuristic methods showing that worst case domination ratio of the methods are small. But there is no theoretical analysis of DataSifter. It performs only empirically better, and since the experiments are done for a specific choice of utility function, nothing can be said about its worst case performance, and it could as well be as small as linear heuristics. \n\n4. The DeepSets approach to utility optimization has been introduced by Wang et.al. 2021a (as the authors agree) and this method itself is not a novel contribution of this work (including the label information does not contribute anything new to the idea). \n\n\\textbf{Minor issues:}\n\n1. On page 2: \"Guided by goals of downstream...\" It is not clear to me what this line means. \n\n2. Line 7, page 5: adds ----> add", "summary_of_the_paper": "In this work, the authors:\n\n1. shows that linear heuristic like Shapley value based methods do no perform well w.r.t worst case performance in selecting the best subset of data. \n\n2. develops an algorithmic framework based on utility optimization approach to achieve robust ness against general \\textit{bad} data", "summary_of_the_review": "My decision is borderline accept for this paper only because of empirical success in some specific examples and theoretical results on the domination ratio of Shapley value based methods. Although, I should mention this paper has considerable weakness. Depending on discussion with other reviewers I may increase/decrease my score. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the question of identifying bad data so that models can be trained on the subset of data that is good. This question is formulated as a utility optimization problem. The paper shows that some popular heuristics are quite bad in the framework they propose. They also propose a new algorithmic framework called DataSifter. There is empirical evaluation provided for this. Questions have been raised in the reviews about the size of the models that have been used in the empirical evaluation. The authors have responded to this by suggesting the use of proxy model techniques. There are also questions about learnability of data utility for which some responses are provided in the rebuttal.
Decision: Reject