How Many and Which Training Points Would Need to be Removed to Flip this Prediction? (2023)

Abstract: We consider the problem of identifying a minimal subset of training data \mathcal{S}_t such that if the instances comprising \mathcal{S}_t had been removed prior to training, the categorization of a given test point x_t would have been different.Identifying such a set may be of interest for a few reasons.First, the cardinality of \mathcal{S}_t provides a measure of robustness (if |\mathcal{S}_t| is small for x_t , we might be less confident in the corresponding prediction), which we show is correlated with but complementary to predicted probabilities.Second, interrogation of \mathcal{S}_t may provide a novel mechanism for contesting a particular model prediction: If one can make the case that the points in \mathcal{S}_t are wrongly labeled or irrelevant, this may argue for overturning the associated prediction. Identifying \mathcal{S}_t via brute-force is intractable.We propose comparatively fast approximation methods to find \mathcal{S}_t based on influence functions , and find that—for simple convex text classification models—these approaches can often successfully identify relatively small sets of training examples which, if removed, would flip the prediction.

## introduction in this work we pose the following problem in the context of binary classification: for a test point x t , identify a minimum subset s t of training data that one would need to remove in order to flip the prediction ŷt for x t . this subset may be of interest for a few reasons. first, the cardinality k of s t captures one measure of the (in)fragility of the prediction ŷt : small k indicates that a minor change in the training data would have resulted in a different (discrete) prediction for x t . we later show that this measure is correlated with, but complementary to, predicted probabilities. perhaps a more interesting motivation for recovering s t is to provide a potential mechanism for contesting model predictions @xcite , i.e., to enable individuals to interrogate and dispute automatic determinations that affect them. if removing a small set of training points would have yielded a different prediction, and if one could make the case for excluding these points (e.g., because they seem mislabeled, or reflect systematic labeling biases), this might provide a compelling case to overturn a model prediction. consider an educator using an automated essay grading system. 2 assume the system has output a comparatively poor grade for a student, a determination they see as unfair. contesting the inclusion of a small set of examples (s t ) which, if excluded, would have resulted in a higher grade provides a novel mechanism for disputation. naïvely attempting to find s t by brute enumeration and re-training would be hopelessly inefficient. we introduce an algorithm for finding such sets efficiently using influence functions (koh and liang, 2017) which allow us to approximate changes in predictions expected as a result of removing subsets of training data @xcite . we then provide an iterative variant of this method which does a better job of identifying sets s t . across different datasets and models, we find that we are often able to recover subsets s t with relatively small cardinality k; i.e., one can often identify a small to medium subset of training data which, if removed, would flip a given prediction. we also find that there are many test points for which models make predictions with high confidence but where k is small. the contributions here include an investigation of the task of identifying minimal training sets to flip particular predictions in the context of text classification, algorithms for this problem, and an empirical evaluation of their performance in the con-text of binary text classification. 3 ## methods assume a binary text classification problem. given a training set z @xmath0, ..., z n , where z @xmath1, y i ) ∈ x × y, we aim to estimate the parameters θ of a classification model f θ : @xmath2, i.e., loss l over z tr : θ := argmin θ 1 n n @xmath3, θ) + λ 2 θ t θ, which we will denote by r(θ). we assume throughout that r is twice-differentiable and strongly convex in θ, i.e., h θ := ∇ 2 θ r( θ) := 1 n n @xmath4, θ) + λi exists and is positive definite. suppose we removed a subset of k training points s ⊂ z tr and re-estimated θ, yielding new parameters θs . letting ε = -1 n , we can write this as: in principle, one could remove the points in s and re-train to find θs . in practice this is infeasible given the number of potential subsets s. koh and liang (2017) provide (relatively) efficient approximations to estimate θs when @xmath5. subsequent work @xcite found that this approximation correlates well with the actual empirical effects of removing a set of points (where @xmath6. finding influential subsets given input x t , we aim to design an approach to efficiently identify the smallest subset s t of z tr such that removing these examples prior to training would change ŷt . prior work @xcite derived the influence exerted by a train point i on the loss incurred for a test point t as: where ∆ i θ is the influence of upweighting z i during training on estimates θ @xcite . we are interested, however, in identifying points that have a particularly strong effect on a specific observed prediction. we therefore modify equation 2 to estimate the influence on prediction (ip), i.e., the change in predicted probability for x t 3 recent related work in economics by @xcite proposed and investigated a similar problem, with a focus on identifying the sensitivity of econometric analyses to removal of small subsets of data. recent work on datamodeling @xcite also considered a variant of this problem (see section 5). observed after removing training instance i. this can be expressed as: we then approximate the change in prediction on instance t we would anticipate after removing the training subset s t from the training data as the sum of the ∆ t f i terms for all points x @xmath7. algorithm 1 describes a method for constructing s t . we estimate the change in output expected upon removing each instance from the training dataset and assemble these in ∆ t f . we then greedily consider adding these differences (effectively adding points to s t ) until the resultant output is expected to cross the classification threshold (τ ); if we exhaust the training dataset without crossing τ , then we have failed to identify a set s t . algorithm 1: a simple method to find a minimal subset to flip a test prediction input: f : model; z tr : full training set; θ: parameters estimated z tr ; l: loss function; x t : a test point; τ : classification threshold (e.g., 0.5) output: s t : minimal train subset identified to flip the prediction (∅ if unsuccessful) binary prediction // sort instances (and estimated output differences) in order of the current prediction 5 direction ← {↑ if ŷt else ↓} 6 indices ← argsort(∆ t f, direction) 7 ∆ t f ← sort(∆ t f, direction) 8 for @xmath8... |z tr | do 9 ŷ′ @xmath9: k])) > τ 10 if ŷ′ t ̸ = ŷt then 11 return z tr [indices[: k]] we start with the entire train set as a "candidate" st , and then iteratively attempt to find strict subsets of this that by themselves would flip the prediction ŷt . on the first pass, this is equivalent to algorithm 1, after which-if successful-we will have found a candidate set st . here we update parameter estimates θ to approximate "removing" the points in st , and then we recompute the approximation of the influence that points in st would have on ŷt using a single-step newton approximation. the idea is that after the parameter update this approximation will be more accurate, potentially allowing us to find a smaller s t . this process continues until we are unable to find a new (smaller) subset. in sum, this variant of the algorithm attempts to iteratively identify increasingly small subsets st which would, upon removal prior to training, overturn the original prediction ŷt . there is a computational cost to this, because each iteration involves approximating the influence on a particular prediction; this is computationally expensive. this variant therefore trades run-time for (hopefully) more accurate identification of minimal s t . however, we find that empirically algorithm 2 ends up running for only 2.3 passes on average (across all experiments). that is, the algorithm adds a scalar to the run-time of algorithm 1, but often yields considerably smaller s t . we show the comparison of |s t | returned by two algorithms in the ## results here we present results for the iterative method (appendix algorithm 2), which outperforms the simpler algorithm 1. we provide full results for both methods in the in the appendix. how often can we find s t and how frequently does removing the instances it contains flip the prediction? as can be seen in ## related work influence functions @xcite @xcite provide machinery to identify training points that most informed a particular test prediction. influence can provide insight into predictions made by modern neural networks (koh and liang, 2017), and can be used to debug models and training data by surfacing mislabeled training points and/or reliance on artifacts @xcite @xcite , and tuning influence can be used to demote reliance on unwanted correlations @xcite . influence can also be used to audit models by inspecting training data responsible for predictions @xcite . @xcite audit individual predictions by approximating how much they might have changed under different samples from the training distribution. ting and brochu (2018) consider influence functions as a tool for optimally subsampling data in service of computational effi-ciency. @xcite considered approximating the effect of removing a group of training points using influence functions, and found that they do so fairly well (a result that we use). they assumed groups were given and then evaluated the accuracy of the influence approximation to the change in prediction. by contrast, we are interested in finding a (minimal) group which would have the specific effect of flipping a prediction. elsewhere, @xcite ask: "which training examples are most responsible for a given set of predictions?". broderick et al. (2020) assess the robustness of economic analyses when a fraction of data is removed. they therefore focus on the magnitude/significance of parameter estimates. this framing differs from our ml-centric motivation, which aims to recover specific small subsets of data that, if removed, would change a particular prediction (and so might support contestability). ## conclusions in the context of binary text classification, we investigated the problem of identifying a minimal set of training points s t such that, if excluded from training, the prediction for test instance x t would flip. we proposed two relatively efficient algorithms for this-both using approximate group influence @xcite -and showed that for regularized linear models they can often find relatively small s t . we provided empirical evidence that this captures uncertainty in a way that is somewhat complementary to predicted probabilities, and may serve as a mechanism to support contestability, by allowing individuals to review (and dispute) instances in s t .