Interactive Label Cleaning with Example-based Explanations Stefano Teso1 , Andrea Bontempelli1 , Fausto Giunchiglia1,2 and Andrea Passerini1 1 University of Trento, Italy 2 Jilin University, China Abstract We tackle sequential learning under label noise in applications where a human supervisor can be queried to relabel suspicious examples. Existing approaches are flawed, in that they only relabel incoming ex- amples that look “suspicious” to the model. As a consequence, those mislabeled examples that elude (or don’t undergo) this cleaning step end up tainting the training data and the model with no further chance of being cleaned. We propose cincer, a novel approach that cleans both new and past data by identifying pairs of mutually incompatible examples. Whenever it detects a suspicious example, cincer identifies a counter-example in the training set that—according to the model—is maximally incompat- ible with the suspicious example, and asks the annotator to relabel either or both examples, resolving this possible inconsistency. The counter-examples are chosen to be maximally incompatible, so to serve as explanations of the model’s suspicion, and highly influential, so to convey as much information as possible if relabeled. cincer achieves this by leveraging an efficient and robust approximation of influ- ence functions based on the Fisher information matrix (FIM). Our extensive empirical evaluation shows that clarifying the reasons behind the model’s suspicions by cleaning the counter-examples helps in acquiring substantially better data and models, especially when paired with our FIM approximation. Keywords Interactive Learning, Explainable AI, Label Noise, Influence Functions, Fisher Information 1. Introduction Label noise is a major issue in machine learning as it can lead to compromised predictive performance and unreliable models [1, 2]. We focus on sequential learning settings in which a human supervisor, usually a domain expert, can be asked to double-check and relabel any potentially mislabeled example. Applications include crowd-sourced machine learning and citizen science, where trained researchers can be asked to clean the labels provided by crowd- workers [3, 4], and interactive personal assistants [5], where the user self-reports the initial annotations (e.g., about activities being performed) and unreliability is due to memory bias [6], unwillingness to report [7], or conditioning [8]. This problem is often tackled by monitoring for incoming examples that are likely to be mislabeled, aka suspicious examples, and ask the supervisor to provide clean (or at least better) annotations for them. Existing approaches, however, focus solely on cleaning the incoming XAI.it 2021 - Italian Workshop on Explainable Artificial Intelligence " stefano.teso@unitn.it (S. Teso); andrea.bontempelli@unitn.it (A. Bontempelli); fausto.giunchiglia@unitn.it (F. Giunchiglia); andrea.passerini@unitn.it (A. Passerini) © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) Figure 1: Suspicious example and counter-examples selected using (from left to right) cincer, 1-NN and influence functions (IF), on noisy MNIST. Left: the suspicious example is mislabeled, the machine’s suspicion is supported by a clean counter-example. Right: the suspicious example is not mislabeled, the machine is wrongly suspicious because the counter-example is mislabeled. cincer’s counter-example is contrastive and influential; 1-NN’s is not influential and IF’s is not pertinent, see desiderata D1–D3 below. examples [9, 4, 10, 5]. This means that noisy examples that did not undergo the cleaning step (e.g., those in the initial bootstrap data set) or that managed to elude it are left untouched. This degrades the quality of the model and prevent it from spotting future mislabeled examples that fall in regions affected by noise. We introduce cincer (Contrastive and InflueNt CounterExample stRategy), a new explainable interactive label cleaning algorithm that lets the annotator observe and fix the reasons behind the model’s suspicions. For every suspicious example that it finds, cincer identifies a counter- example, i.e., a training example that maximally supports the machine’s suspicion. The idea is that the example/counter-example pair captures a potential inconsistency in the data—as viewed from the model’s perspective—which is resolved by invoking the supervisor. More specifically, cincer asks the user to relabel the example, the counter-example, or both, thus improving the quality of, and promoting consistency between, the data and the model. Two hypothetical rounds of interaction on a noisy version of MNIST are illustrated in Figure 1. cincer relies on a principled definition of counter-examples derived from few explicit, in- tuitive desiderata, using influence functions [11, 12]. The resulting counter-example selection problem is solved using a simple and efficient approximation based on the Fisher information matrix [13] that consistently outperforms more complex alternatives in our experiments. Contributions: We: 1) Introduce cincer, an explanatory interactive label cleaning strategy that leverages example-based explanations to identify inconsistencies in the data—as perceived by the model—and enable the annotator to fix them. 2) Show how to select counter-examples that explain why the model is suspicious and that are highly informative using (an efficient ap- proximation of) influence functions. 3) Present an extensive empirical evaluation that showcases the ability of cincer of building cleaner data sets and better models. 2. Background We are concerned with sequential learning under label noise. In this setting, the machine receives a sequence of examples 𝑧˜𝑡 := (x𝑡 , 𝑦˜𝑡 ), for 𝑡 = 1, 2, . . ., where x𝑡 ∈ R𝑑 is an instance and 𝑦˜𝑡 ∈ [𝑐] is a corresponding label, with [𝑐] := {1, . . . , 𝑐}. The label 𝑦˜𝑡 is unreliable and might differ from the ground-truth label 𝑦𝑡* . The key feature of our setting is that a human supervisor can be asked to double-check and relabel any example. The goal is to acquire a clean dataset and a high-quality predictor while asking few relabeling queries, so to keep the cost of interaction under control. The state-of-the-art for this setting is skeptical learning (SKL) [10, 5]. SKL is designed primarily for sequential interactive learning from unreliable users: in each iteration the machine receives an example and updates the model accordingly. However, for each example that it receives, the machine compares (an estimate of) the quality of the annotation with that of its own prediction, and if the prediction looks more reliable than the annotation by some factor, SKL asks the user to double-check his/her example. The details depend on the implementation: in [10] label quality is estimated using the empirical accuracy for the classifier and the empirical probability of contradiction for the annotator, while in [5] the machine measures the margin between the user’s and machine’s labels. Our approach follows the latter strategy. Another very related approach is learning from weak annotators (LWA) [9, 4], which focuses on querying domain experts rather than end-users. The most recent approach [4] jointly learns a prediction pipeline composed of a classifier and a noisy channel, which allows it to estimate the noise rate directly, and identifies suspicious examples that have a large impact on the model. A theoretical foundation is given in [9]. LWA is however designed for pool-based scenarios, where the training set is given rather than obtained sequentially. For this reason, in the remainder of the paper we will chiefly build on and compare to SKL. Limitations of existing approaches. A major downside of SKL is that it focuses on cleaning the incoming examples only. This means that if a mislabeled example manages to elude the cleaning step and gets added to the training set, it is bound to stay there forever. This situation is actually quite common during the first stage of skeptical learning, in which the model is highly uncertain and trusts the incoming examples—even if they are mislabeled. The same issue occurs if the initial training set used to bootstrap the classifier contains mislabeled examples. As shown by our experiments, the accumulation of noisy data in the training set may have a detrimental effect on the model’s performance (cf. Figure 2). In addition, it can also affect the model’s ability to identify suspicious examples: a noisy data point can fool the classifier into trusting incoming mislabeled examples that fall close to it, further aggravating the situation. 3. Explainable Interactive Label Cleaning with CINCER We consider a very general class of probabilistic classifiers 𝑓 : R𝑑 → [𝑐] of the form 𝑓 (x; 𝜃) := argmax𝑦∈[𝑐] 𝑃 (𝑦 | x; 𝜃), where the conditional distribution 𝑃∑︀(𝑌 | X; 𝜃) has been fit on training data by minimizing the cross-entropy loss ℓ((x, 𝑦), 𝜃) = − 𝑖∈[𝑐] 1{𝑖 = 𝑦} log 𝑃 (𝑖 | x, 𝜃). In our implementation, we also assume 𝑃 to be a neural network with a softmax activation at the top layer, trained using some variant of SGD and possibly early stopping. 3.1. The cincer Algorithm The pseudo-code of cincer is listed in Algorithm 1. At the beginning of iteration 𝑡, the machine has acquired a training set 𝐷𝑡−1 = {𝑧1 , . . . , 𝑧𝑡−1 } and trained a model with parameters 𝜃𝑡−1 Algorithm 1 Pseudo-code of cincer. Inputs: initial (noisy) training set 𝐷0 ; threshold 𝜏 . 1: fit 𝜃0 on 𝐷0 2: for 𝑡 = 1, 2, . . . do 3: receive new example 𝑧˜𝑡 = (x𝑡 , 𝑦˜𝑡 ) 4: if 𝜇(𝑧˜𝑡 , 𝜃𝑡−1 ) < 𝜏 then 5: 𝐷𝑡 ← 𝐷𝑡−1 ∪ {𝑧˜𝑡 } ◁ 𝑧˜𝑡 is compatible 6: else 7: find counterexample 𝑧𝑘 using Eq. 10 ◁ 𝑧˜𝑡 is suspicious 8: present 𝑧˜𝑡 , 𝑧𝑘 to the user, receive possibly cleaned labels 𝑦𝑡 , 𝑦𝑘 ′ ′ 9: 𝐷𝑡 ← (𝐷𝑡−1 ∖ {𝑧𝑘 }) ∪ {(x𝑡 , 𝑦𝑡′ ), (x𝑘 , 𝑦𝑘′ )} 10: fit 𝜃𝑡 on 𝐷𝑡 on it. At this point, the machine receives a new, possibly mislabeled example 𝑧˜𝑡 (line 3) and has to decide whether to trust it. Following skeptical learning [5], cincer does so by computing the margin 𝜇(𝑧˜𝑡 , 𝜃𝑡−1 ), i.e., the difference in conditional probability between the model’s prediction 𝑦^𝑡 := argmax𝑦 𝑃 (𝑦 | x𝑡 , 𝜃𝑡−1 ) and the annotation 𝑦˜𝑡 . More formally: 𝜇(𝑧˜𝑡 , 𝜃𝑡−1 ) := 𝑃 (𝑦^𝑡 | x𝑡 , 𝜃𝑡−1 ) − 𝑃 (𝑦˜𝑡 | x𝑡 , 𝜃𝑡−1 ) (1) The margin estimates the incompatibility between the model and the example: the larger the margin, the more suspicious the example. The example 𝑧˜𝑡 is deemed compatible if the margin is below a given threshold 𝜏 and suspicious otherwise (line 4); possible choices for 𝜏 are discussed in Section 3.5. If 𝑧˜𝑡 is compatible, it is added to the data set as-is (line 5). Otherwise, cincer computes a counter-example 𝑧𝑘 ∈ 𝐷𝑡−1 that maximally supports the machine’s suspicion. The intuition is that the pair (𝑧˜𝑡 , 𝑧𝑘 ) captures a potential inconsistency in the data. For instance, the counter- example might be a correctly labeled example that is close or similar to 𝑧˜𝑡 but has a different label, or a distant noisy outlier that fools the predictor into assigning low probability to 𝑦˜𝑡 . How to choose an effective counter-example is a major focus of this paper and discussed in detail in Section 3.2 and following. Next, cincer asks the annotator to double-check the pair (𝑧˜𝑡 , 𝑧𝑘 ) and relabel the suspicious example, the counter-example, or both, thus resolving the potential inconsistency. The data set and model are updated accordingly (line 9). 3.2. Counter-example Selection Counter-examples are meant to illustrate why an example 𝑧˜𝑡 is deemed suspicious by the machine in a way that makes it easy to elicit useful corrective feedback from the supervisor. We posit that a good counter-example 𝑧𝑘 should be: D1. Contrastive: 𝑧𝑘 should explain why 𝑧˜𝑡 is considered suspicious by the model, thus high- lighting a potential inconsistency in the data. D2. Influential: if 𝑧𝑘 is mis-labeled, correcting it should improve the model as much as possible, so to maximize the information gained by interacting with the annotator. In the following, we show how, for models learned by minimizing the cross-entropy loss, one can identify counter-examples that satisfy both desiderata. What is a contrastive counter-example? We start by tackling the first desideratum. Let 𝜃𝑡−1 be the parameters of the current model. Intuitively, 𝑧𝑘 ∈ 𝐷𝑡−1 is a contrastive counter- example for a suspicious example 𝑧˜𝑡 if removing it from the data set and retraining leads to a −𝑘 model with parameters 𝜃𝑡−1 that assigns higher probability to the suspicious label 𝑦˜𝑡 . The most contrastive counter-example is then the one that maximally affects the change in probability: {︁ }︁ −𝑘 argmax𝑘∈[𝑡−1] 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 ) − 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 ) (2) While intuitively appealing, optimizing Eq. 2 directly is computationally challenging as it involves retraining the model |𝐷𝑡−1 | times. This is impractical for realistically sized models and data sets, especially in our interactive scenario where a counter-example must be computed in each iteration. Influence functions. We address this issue by leveraging influence functions (IFs), a compu- tational device that can be used to estimate the impact of specific training examples without retraining [11, 12]. Let 𝜃𝑡 be the empirical risk minimizer on 𝐷𝑡 and 𝜃𝑡 (𝑧, 𝜖) be the minimizer obtained after adding an example 𝑧 with weight 𝜖 to 𝐷𝑡 , namely: 𝜃𝑡 := argmin𝜃 1𝑡 𝑡𝑘=1 ℓ(𝑧𝑘 , 𝜃) (︀∑︀𝑡 𝜃𝑡 (𝑧, 𝜖) := argmin𝜃 1𝑡 (3) ∑︀ )︀ 𝑘=1 ℓ(𝑧𝑘 , 𝜃) + 𝜖ℓ(𝑧, 𝜃) Taking a first-order Taylor expansion,(︀ 𝑑 the difference ⃒ )︀ between 𝜃𝑡 = 𝜃𝑡 (𝑧, 0) and 𝜃𝑡 (𝑧, 𝜖) can be written as 𝜃𝑡 (𝑧, 𝜖) − 𝜃𝑡 (𝑧, 0) ≈ 𝜖 · 𝑑𝜖 𝜃𝑡 (𝑧, 𝜖)⃒𝜖=0 . The derivative appearing on the right hand side is the so-called influence function, denoted ℐ𝜃𝑡 (𝑧). It follows that the effect on 𝜃𝑡 of adding (resp. removing) an example 𝑧 to 𝐷𝑡 can be approximated by multiplying the IF by 𝜖 = 1/𝑡 (resp. 𝜖 = −1/𝑡). Crucially, if the loss is strongly convex and twice differentiable, ∑︀ the IF can be written as ℐ𝜃𝑡 (𝑧) = −𝐻(𝜃𝑡 )−1 ∇𝜃 ℓ(𝑧, 𝜃𝑡 ), where the curvature matrix 𝐻(𝜃𝑡 ) := 1𝑡 𝑡𝑘=1 ∇2𝜃 ℓ(𝑧𝑘 , 𝜃𝑡 ) is positive definite and invertible. IFs were shown to capture meaningful information even for non-convex models [12]. Identifying contrastive counter-examples with influence functions. To see the link between contrastive counter-examples and influence functions, notice that the second term of Eq. 2 is independent of 𝑧𝑘 , while the first term can be conveniently approximated with IFs by applying the chain rule: (︂ ⃒ )︂ (︂ ⃒ )︂ 1 𝑑 ⃒ 1 ⊤ 𝑑 ⃒ − 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 (𝑧𝑘 , 𝜖))⃒ ⃒ =− ∇𝜃 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 ) 𝜃𝑡−1 (𝑧𝑘 , 𝜖)⃒⃒ 𝑡 − 1 𝑑𝜖 𝜖=0 𝑡−1 𝑑𝜖 𝜖=0 (4) 1 =− ∇𝜃 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 )⊤ ℐ𝜃𝑡−1 (𝑧𝑘 ) (5) 𝑡−1 The constant can be dropped during the optimization. This shows that Eq. 2 is equivalent to: argmax𝑘∈[𝑡−1] ∇𝜃 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 )⊤ 𝐻(𝜃𝑡−1 )−1 ∇𝜃 ℓ(𝑧𝑘 , 𝜃𝑡−1 ). This problem can be solved efficiently by combining two strategies [12]: i) Caching the inverse Hessian-vector product (HVP) ∇𝜃 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 )⊤ 𝐻(𝜃𝑡−1 )−1 , so that evaluating the objective on each 𝑧𝑘 becomes a simple dot product, and ii) Solving the inverse HVP with an efficient stochastic estimator like LISSA [14]. This gives us an algorithm for computing contrastive counter-examples. Contrastive counter-examples are highly influential. Can this algorithm be used for identifying influential counter-examples? It turns out that, as long as the model is obtained by optimizing the cross-entropy loss, the answer is affirmative. Indeed, note that if ℓ(𝑧, 𝜃) = − log 𝑃 (𝑦 | x; 𝜃), then: ∇𝜃 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 ) ∇𝜃 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 ) = 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 ) = (6) 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 ) = 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 )∇𝜃 log 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 ) = −𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 )∇𝜃 ℓ(𝑧˜𝑡 , 𝜃𝑡−1 ) (7) Hence, Eq. 5 can be rewritten as: − 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 )∇𝜃 ℓ(𝑧˜𝑡 , 𝜃𝑡−1 )⊤ 𝐻(𝜃𝑡−1 )−1 ∇𝜃 ℓ(𝑧𝑘 , 𝜃𝑡−1 ) (8) ⊤ −1 ∝ −∇𝜃 ℓ(𝑧˜𝑡 , 𝜃𝑡−1 ) 𝐻(𝜃𝑡−1 ) ∇𝜃 ℓ(𝑧𝑘 , 𝜃𝑡−1 ) (9) It follows that, under the above assumptions and as long as the model satisfies 𝑃 (𝑦˜𝑡 | x𝑡 ; 𝜃𝑡−1 ) > 0, Eq. 2 is equivalent to: argmax𝑘∈[𝑡−1] −∇𝜃 ℓ(𝑧˜𝑡 , 𝜃𝑡−1 )⊤ 𝐻(𝜃𝑡−1 )−1 ∇𝜃 ℓ(𝑧𝑘 , 𝜃𝑡−1 ) (10) This equation recovers exactly the definition of influential examples given in Eq. 2 of [12] and shows that, for the large family of classifiers trained by cross-entropy, highly influential counter-examples are highly contrastive and vice versa, so that no change to the selection algorithm is necessary. 3.3. Counter-example Selection with the Fisher information matrix Unfortunately, we found the computation of IFs to be unreliable in practice, cf. [15]. This leads to unstable ranking of candidates and reflects on the quality of the counter-examples, as in Figure 1. The issue is that, for the common use case of non-convex classifiers trained using gradient-based methods (and possibly early stopping), 𝜃𝑡−1 is seldom close to a local minimum of the empirical risk, rendering the Hessian non-positive definite. In our setting, the situation is further complicated by the presence of noise, which dramatically skews the curvature of the empirical risk. Remedies like fine-tuning the model with L-BFGS [12, 16], preconditioning and weight decay [15] proved unsatisfactory in our experiments. We take a different approach. The idea is to replace the Hessian by the Fisher information matrix (FIM). The FIM 𝐹 (𝜃) of a discriminative model 𝑃 (𝑌 | X, 𝜃) and training set 𝐷𝑡−1 is [17, 18]: 1 ∑︀𝑡−1 ⊤ (11) [︀ ]︀ 𝐹 (𝜃) := 𝑡−1 𝑘=1 E 𝑦∼𝑃 (𝑌 | x 𝑘 ,𝜃) ∇ 𝜃 log 𝑃 (𝑦 | x 𝑘 , 𝜃)∇ 𝜃 log 𝑃 (𝑦 | x 𝑘 , 𝜃) It can be shown that, if the model approximates the data distribution, the FIM approximates the Hessian, cf. [19, 20]. Even when this assumption does not hold, as is likely in our noisy setting, the FIM still captures much of the curvature information encoded into the Hessian [17]. Under this approximation, Eq. 10 can be rewritten as: argmax𝑘∈[𝑡−1] −∇𝜃 ℓ(𝑧˜𝑡 , 𝜃𝑡−1 )⊤ 𝐹 (𝜃𝑡−1 )−1 ∇𝜃 ℓ(𝑧𝑘 , 𝜃𝑡−1 ) (12) The advantage of this formulation is twofold. First of all, this optimization problem also admits caching the inverse FIM-vector product (FVP), which makes it viable for interactive usage. Second, and most importantly, the FIM is positive semi-definite by construction, making the computation of Eq.12 much more stable. The remaining step is how to compute the inverse FVP. Naïve storage and inversion of the FIM, which is |𝜃| × |𝜃| in size, is impractical for typical models, so the FIM is usually replaced with a simpler matrix. Three common options are the identity matrix, the diagonal of the FIM, and a block-diagonal approximation where interactions between parameters of different layers are set to zero [17]. Our best results were obtained by restricting the FIM to the top layer of the network. We refer to this approximation as “Top Fisher”. While more advanced approximations like K-FAC [17] exist, the Top Fisher proved surprisingly effective in our experiments. 3.4. Selecting Pertinent Counter-examples So far we have discussed how to select contrastive and influential counter-examples. Now we discuss how to make the counter-examples easier to interpret for the annotator. To this end, we introduce the additional desideratum that counter-examples should be: D3 Pertinent: it should be clear to the user why 𝑧𝑘 is a counter-example for 𝑧˜𝑡 . We integrate D3 into cincer by restricting the choice of possible counter-examples. A simple strategy, which we do employ in all of our examples and experiments, is to restrict the search to counter-examples whose label in the training set is the same as the prediction for the suspicious example, i.e., 𝑦𝑘 = 𝑦^𝑡 . This way, the annotator can interpret the counter-example as being in support of the machine’s suspicion. In other words, if the counter-example is labeled correctly, then the machine’s suspicion is likely right and the incoming example needs cleaning. Otherwise, if the machine is wrong and the suspicious example is not mislabeled, it is likely the counter-example – which backs the machine’s suspicions – that needs cleaning. Finally, one drawback of IF-selected counter-examples is that they may be perceptually different from the suspicious example. For instance, outliers are often highly influential as they fool the machine into mispredicting many examples, yet they have little in common with those examples [20]. This can make it difficult for the user to understand their relationship with the suspicious examples they are meant to explain. This is not necessarily an issue: first, a motivated supervisor is likely to correct mislabeled counter-examples regardless of whether they resemble the suspicious example; second, highly influential outliers are often identified (and corrected if needed) in the first iterations of cincer (indeed, we did not observe a significant amount of repetitions among suggested counter-examples in our experiments). Still, cincer can be readily adapted to acquire more perceptually similar counter-examples. One option is to replace IFs with relative IFs [20], which trade-off influence with locality. Alas, the resulting optimization problem does not support efficient caching of the inverse HVP. A better alternative is to restrict the search to counter-examples 𝑧𝑘 that are similar enough to 𝑧˜𝑡 in terms of some given perceptual distance ‖·‖𝒫 [21] by filtering the candidates using fast nearest neighbor techniques in perceptual space. This is analogous to FastIF [22], except that the motivation is to encourage perceptual similarity rather than purely efficiency, although the latter is a nice bonus. 3.5. Advantages and Limitations The main benefit of cincer is that, by asking a human annotator to correct potential inconsis- tencies in the data, it acquires substantially better supervision and, in turn, better predictors. In doing so, cincer also encourages consistency between the data and the model. Another benefit is that cincer allows the supervisor to spot bugs and justifiably build – or, perhaps more importantly, reject [23, 24] – trust into the prediction pipeline. cincer only requires to set a single parameter, the margin threshold 𝜏 , which determines how frequently the supervisor is invoked. The optimal value depends on the ratio between the cost of a relabeling query and the cost of noise. If the annotator is willing to interact (for instance, because it is payed to do so) then the threshold can be quite generous. cincer can be readily applied in applications in which the data set is retained over time, even partially. If retaining data is not an option, cincer could be adapted to synthesize counter-examples ex novo. This is however highly non-trivial and left to future work. 4. Experiments We address empirically the following research questions: Q1: Do counter-examples contribute to cleaning the data? Q2: Which influence-based selection strategy identifies the most mislabeled counter-examples? Q3: What contributes to the effectiveness of the best counter-example selection strategy? We implemented cincer using Python and Tensorflow [25] on top of three classifiers and compared different counter-example selection strategies on five data sets. The IF code is adapted from [26]. All experiments were run on a 12-core machine with 16 GiB of RAM and no GPU. The code for all experiments is available at: https://github.com/abonte/cincer. Data sets. We used a diverse set of classification data sets: Adult [27]: data set of 48,800 persons, each described by 15 attributes; the goal is to discriminate customers with an income above/below $50K. Breast [27]: data set of 569 patients described by 30 real-valued features. The goal is to discriminate between benign and malignant breast cancer cases. 20NG [27]: data set of newsgroup posts categorized in twenty topics. The documents were embedded using a pre-trained Sentence-BERT model [28] and compressed to 100 features using PCA. MNIST [29]: handwritten digit recognition data set from black-and-white, 28 × 28 images with pixel values normalized in the [0, 1] range. The data set consists of 60K training and 10K test examples. Fashion [30]: fashion article classification dataset with the same structure as MNIST. For adult and breast a random 80 : 20 training-test split is used while for MNIST, fashion and 20 NG the split provided with the data set is used. The labels of 20% of training examples were corrupted Drop CE No CE CINCER (Top Fisher) 30 30 20 30 20 20 20 10 10 10 10 0 0 0 0 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 0.95 0.80 0.75 0.40 0.73 0.90 0.38 0.70 0.70 0.85 0.36 0.60 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 Iterations Iterations Iterations Iterations Figure 2: cincer using Top Fisher vs. drop CE and no CE. Left to right: results for FC on adult, breast and 20NG, CNN on MNIST. Top row: # of cleaned examples. Bottom row: 𝐹1 score. at random. Performance was measured in terms of 𝐹1 score on the (uncorrupted) test set. Error bars in the plots indicate the standard error. The experiments were repeated five times, each time changing the seed used for corrupting the data. All competitors received exactly the same examples in exactly the same order. Models. We applied cincer to three models: LR, a logistic regression classifier; FC, a feed- forward neural network with two fully connected hidden layers with ReLU activations; and CNN, a feed-forward neural network with two convolutional layers and two fully connected layers. For all models, the hidden layers have ReLU activations and 20% dropout while the top layer has a softmax activation. LR was applied to MNIST, FC to both the tabular data sets (namely: adult, breast, german, and 20NG) and image data sets (MNIST and fashion), and CNN to the image data sets only. Upon receiving a new example, the classifier is retrained from scratch for 100 epochs using Adam [31] with default parameters, with early stopping when the accuracy on the training set reaches 90% for FC and CNN, and 70% for LR. This helps substantially to stabilize the quality of the model and speeds up the evaluation. Before each run, the models are trained on an bootstrap training set (containing 20% mislabeled examples) of 500 examples for 20NG and 100 for all the other data sets. The margin threshold is set to 𝜏 = 0.2. Due to space constraints, we report the results on one image data set and three tabular data, and we focus on FC and CNN. The other results are consistent with what is reported below; these plots are reported in the Supplementary Material. 4.1. Q1: Counter-examples improve the quality of the data To evaluate the impact of cleaning the counter-examples, we compare cincer combined with the Top fisher approximation of the FIM, which works best in practice, against two alternatives, namely: No CE: an implementation of skeptical learning [5] that asks the user to relabel any incoming suspicious examples identified by the margin and presents no counter-examples. Drop CE: a variation of cincer that identifies counter-examples using Top Fisher but drops them from the data set if the user considers the incoming example correctly labeled. The results are reported in Figure 2. The plots show that cincer cleans by far the most examples on all data sets, between 33% and 80% more than the alternatives (top row in Figure 2). This translates into 0.4 0.4 0.4 0.4 IF precision precision precision precision 0.3 0.3 0.3 0.3 0.2 0.2 0.2 0.2 Practical Fisher 0.1 0.1 0.1 0.1 Top Fisher 0.0 Pr@5 Pr@10 0.0 Pr@5 Pr@10 0.0 Pr@5 Pr@10 0.0 Pr@5 Pr@10 Full Fisher Figure 3: Counter-example Pr@5 and Pr@10. Standard error information is reported. Left to right: results for FC on adult, breast and 20NG, and CNN on MNIST. better predictive performance as measured by 𝐹1 score (bottom row). Notice also that cincer consistently outperforms the drop CE strategy in terms of 𝐹1 score, suggesting that relabeling the counter-examples provides important information for improving the model. These results validate our choice of identifying and relabeling counter-examples for interactive label cleaning compared to focusing on suspicious incoming examples only, and allow us to answer Q1 in the affirmative. 4.2. Q2: FIM-based strategies identify the most mislabeled CEs Next, we compare the ability of alternative approximations of IFs of discovering mislabeled counter-examples. To this end, we trained a model on a noisy bootstrap data set, selected 100 examples from the remainder of the training set, and measured how many truly mislabeled counter-examples are selected by alternative strategies. In particular, we computed influence using the IF LISSA estimator of [12], the actual FIM (denoted “full Fisher” and reported for the simpler models only for computational reasons) and its approximations using the identity matrix (aka “practical Fisher” [32]), and Top Fisher. We computed the precision at 𝑘 for 𝑘 ∈ {5, 10}, i.e, the fraction of mislabeled counter-examples within five or ten highest-scoring counter-examples retrieved by the various alternatives, averaged over 100 iterations for five runs. The results in Figure 3 show that, in general, FIM-based strategies outperform the LISSA estimator, with Full Fisher performing best and Top Fisher a close second. Since the full FIM is highly impractical to store and invert, this confirms our choice of Top Fisher as best practical strategy. 4.3. Q3: Both influence and curvature contribute to the effectiveness of Top Fisher Finally, we evaluate the impact of selecting counter-examples using Top Fisher on the model’s performance, in terms of use of influence, by comparing it to an intuitive nearest neighbor alternative (NN), and modelling of the curvature, by comparing it to the Practical Fisher. NN simply selects the counter-example that is closest to the suspicious example. The results can be viewed in Figure 4. Top Fisher is clearly the best strategy, both in terms of number of cleaned examples and 𝐹1 score. NN is always worse than Top Fisher in terms of 𝐹1 , even in the case of adult (first column) when it cleans the same number of examples, confirming the importance of influence in selecting impactful counter-examples. Practical Fisher clearly underperforms compared with Top Fisher, and it shows the importance of having the curvature matrix. For each data set, all methods make a similar number of queries: 58 for 20NG, 21 for breast, 31 for adult and 37 for MNIST. In general, cincer detects around 75% of the mislabeled examples (compared to 50% of the other methods) and only about 5% of its queries do not involve a NN Practical Fisher Top Fisher 30 30 20 30 20 20 20 10 10 10 10 0 0 0 0 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 0.95 0.80 0.75 0.40 0.90 0.73 0.38 0.70 0.70 0.85 0.36 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 Iterations Iterations Iterations Iterations Figure 4: Top Fisher vs. practical Fisher vs. NN. Left to right: results for FC on adult, breast and 20NG, CNN on MNIST. Top row: # of cleaned examples. Bottom row: 𝐹1 score. corrupted example or counter-example. The complete values are reported in the Supplementary Material. As a final remark, we note that cincer cleans more suspicious examples than counter- examples (in a roughly 2 : 1 ratio), as shown by the number of cleaned suspicious examples vs. counter-examples reported in the Supplementary Material. Comparing this to the curve for Drop CE shows that proper data cleaning improves the ability of the model of being suspicious for the right reasons, as expected. 5. Related Work Interactive learning under noise. Most existing approaches are designed for crowd-sourcing applications in which items are labelled by different annotators of varying quality and the goal is to aggregate weak annotations into a high-quality consensus label [3]. Our work is strongly related to skeptical learning [10, 5] and learning from weak annotators [9, 4]. These approaches completely ignore the issue of noise in the training set, which can be quite detrimental, as shown by our experiments. Moreover, they are completely black-box, making it hard for him/her to establish or reject trust into the data and the model. Influence functions and Fisher information. It is well known that mislabeled examples tend to exert a larger influence on the model [33, 12, 34, 20] and indeed IFs may be a valid alternative to the margin for identifying suspicious examples. Building on the seminal work of Koh and Liang [12], we instead leverage IFs to define and compute contrastive counter-examples that explain why the machine is suspicious. The difference is that noisy training examples influence the model as a whole, whereas contrastive counter-examples influence a specific suspicious example. To the best of our knowledge, this application of IFs is entirely novel. IFs has been used to present to the user training examples that negatively influence the model and from them, augmented examples are created to fine-tune the model [35]. This approach does not consider mislabeled examples. Notice also that empirical evidence that IFs recover noisy examples is restricted to offline learning [12, 34]. Our experiments extend this to a less forgiving interactive setting in which only one counter-example is selected per iteration and the model is trained on the whole training set. The idea of exploiting the FIM to approximate the Hessian has ample support in the natural gradient descent literature [17, 18]. The FIM has been used for computing example-based explanations by Khanna et al. [34]. Their approach is however quite different from ours. cincer is equivalent to maximizing the Fisher kernel [32] between the suspicious example and the counter-example (Eq. 12) for the purpose of explaining the model’s margin, and this formulation is explicitly derived from two simple desiderata. In contrast, Khanna et al. maximize the squared Fisher kernel between 𝑧𝑘 and 𝑧˜𝑡 divided by the norm of 𝑧𝑘 in the RKHS, which is not equivalent to Eq. 12 and does not admit caching the inverse FIM-vector product. Other works. cincer draws inspiration from explanatory active learning, which integrates local [24, 36, 37, 38] or global [39] explanations into interactive learning and allows the annotator to supply corrective feedback on the model’s explanations. These approaches differ from cincer in that they neither consider the issue of noise nor perform label cleaning, and indeed they explain the model’s predictions rather than the model’s suspicion. Another notable difference is that they rely on attribution-based explanations, whereas the backbone of cincer are example- based explanations, which enable users to reason about labels in terms of concrete (training) examples [40, 41]. Saliency maps could potentially be integrated into cincer to provide more fine-grained information. 6. Conclusion We introduced cincer, an approach for handling label noise in sequential learning that asks a human supervisor to relabel any incoming suspicious examples. Compared to previous approaches, cincer identifies the reasons behind the model’s skepticism and asks the supervisor to double-check them too. This is done by computing a training example that maximally supports the machine’s suspicions. This enables the user to correct both incoming and old examples, cleaning inconsistencies in the data that confuse the model. Our experiments shows that, by removing inconsistencies in the data, cincer enables acquiring better data and models than less informed alternatives. Our work can be improved in several ways. cincer can be straightforwardly extended to online active and skeptical learning, in which the label of incoming instances is acquired on the fly [42, 10]. cincer can also be adapted to correcting multiple counter-examples as well as the reasons behind mislabeled counter-examples using “multi-round” label cleaning and group-wise measures of influence [43, 44, 45]. This more refined strategy is especially promising for dealing with systematic noise, in which counter-examples are likely affected by entire groups of mislabeled examples. Potential negative impact. Like most interactive approaches, there is a risk that cincer annoys the user by asking an excessive number of questions. This is currently mitigated by querying the user only when the model is confident enough in its own predictions (through the margin-based strategy) and by selecting influential counter-examples that have a high chance to improve the model upon relabeling, thus reducing the future chance of pointless queries. Moreover, the margin threshold 𝜏 allows to modulate the amount of interaction based on the user’s commitment. Another potential issue is that cincer could give malicious annotators fine- grained control over the training data, possibly leading to poisoning attacks. This is however not an issue for our target applications, like interactive assistants, in which the user benefits from interacting with a high-quality predictor and is therefore motivated to provide non-adversarial labels. Acknowledgments This research has received funding from the European Union’s Horizon 2020 FET Proactive project “WeNet - The Internet of us”, grant agreement No. 823783, and from the “DELPhi - DiscovEring Life Patterns” project funded by the MIUR Progetti di Ricerca di Rilevante Interesse Nazionale (PRIN) 2017 – DD n. 1062 del 31.05.2019. The research of ST and AP was partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215. References [1] B. Frénay, M. Verleysen, Classification in the presence of label noise: a survey, IEEE transactions on neural networks and learning systems 25 (2014) 845–869. [2] H. Song, M. Kim, D. Park, J.-G. Lee, Learning from noisy labels with deep neural networks: A survey, arXiv preprint arXiv:2007.08199 (2020). [3] J. Zhang, X. Wu, V. S. Sheng, Learning from crowdsourced labeled data: a survey, Artificial Intelligence Review 46 (2016) 543–576. [4] J. Kremer, F. Sha, C. Igel, Robust active label correction, in: International conference on artificial intelligence and statistics, PMLR, 2018, pp. 308–316. [5] A. Bontempelli, S. Teso, F. Giunchiglia, A. Passerini, Learning in the Wild with Incremental Skeptical Gaussian Processes, in: Proceedings of the 29th International Joint Conference on Artificial Intelligence, 2020. [6] R. Tourangeau, L. J. Rips, K. Rasinski, The psychology of survey response, Cambridge University Press, 2000. [7] L. Corti, Using diaries in social research, Social research update 2 (1993). [8] B. T. West, J. Sinibaldi, The quality of paradata: A literature review, Improving Surveys with Paradata (2013) 339–359. [9] R. Urner, S. Ben-David, O. Shamir, Learning from weak teachers, in: Artificial intelligence and statistics, PMLR, 2012, pp. 1252–1260. [10] M. Zeni, W. Zhang, E. Bignotti, A. Passerini, F. Giunchiglia, Fixing mislabeling by human annotators leveraging conflict resolution and prior knowledge, Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies 3 (2019) 32. [11] R. D. Cook, S. Weisberg, Residuals and influence in regression, New York: Chapman and Hall, 1982. [12] P. W. Koh, P. Liang, Understanding black-box predictions via influence functions, in: Proceedings of the 34th International Conference on Machine Learning, JMLR. org, 2017, pp. 1885–1894. [13] E. L. Lehmann, G. Casella, Theory of point estimation, Springer Science & Business Media, 2006. [14] N. Agarwal, B. Bullins, E. Hazan, Second-order stochastic optimization for machine learning in linear time, The Journal of Machine Learning Research 18 (2017) 4148–4187. [15] S. Basu, P. Pope, S. Feizi, Influence functions in deep learning are fragile, arXiv preprint arXiv:2006.14651 (2020). [16] C.-K. Yeh, J. S. Kim, I. E. Yen, P. Ravikumar, Representer point selection for explaining deep neural networks, in: Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018, pp. 9311–9321. [17] J. Martens, R. Grosse, Optimizing neural networks with kronecker-factored approximate curvature, in: International conference on machine learning, PMLR, 2015, pp. 2408–2417. [18] F. Kunstner, L. Balles, P. Hennig, Limitations of the empirical fisher approximation for natural gradient descent, in: 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Curran Associates, Inc., 2020, pp. 4133–4144. [19] D. Ting, E. Brochu, Optimal subsampling with influence functions, in: Advances in Neural Information Processing Systems, 2018, pp. 3650–3659. [20] E. Barshan, M.-E. Brunet, G. K. Dziugaite, Relatif: Identifying explanatory training examples via relative influence, in: The 23rd International Conference on Artificial Intelligence and Statistics, 2020. [21] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, S. Hochreiter, Gans trained by a two time-scale update rule converge to a local nash equilibrium, in: Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017, pp. 6629–6640. [22] H. Guo, N. F. Rajani, P. Hase, M. Bansal, C. Xiong, Fastif: Scalable influence functions for efficient model interpretation and debugging, arXiv preprint arXiv:2012.15781 (2020). [23] C. Rudin, Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead, Nature Machine Intelligence 1 (2019) 206–215. [24] S. Teso, K. Kersting, Explanatory interactive machine learning, in: Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, 2019, pp. 239–245. [25] M. Abadi, et al., TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL: https://www.tensorflow.org/, software available from tensorflow.org. [26] T. Ye, Example based explanation in machine learning, https://github.com/Timothy-Ye/ example-based-explanation, 2020. [27] D. Dua, C. Graff, UCI machine learning repository, 2017. URL: http://archive.ics.uci.edu/ml. [28] N. Reimers, I. Gurevych, Sentence-bert: Sentence embeddings using siamese bert-networks, in: EMNLP-IJCNLP, 2019. [29] Y. LeCun, C. Cortes, C. Burges, Mnist handwritten digit database, ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist 2 (2010). [30] H. Xiao, K. Rasul, R. Vollgraf, Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017. arXiv:cs.LG/1708.07747. [31] D. P. Kingma, J. Ba, Adam: A method for stochastic optimization, arXiv preprint arXiv:1412.6980 (2014). [32] T. S. Jaakkola, D. Haussler, et al., Exploiting generative models in discriminative classifiers, Advances in neural information processing systems (1999) 487–493. [33] M. Wojnowicz, B. Cruz, X. Zhao, B. Wallace, M. Wolff, J. Luan, C. Crable, “influence sketch- ing”: Finding influential samples in large-scale regressions, in: 2016 IEEE International Conference on Big Data (Big Data), IEEE, 2016, pp. 3601–3612. [34] R. Khanna, B. Kim, J. Ghosh, S. Koyejo, Interpreting black box predictions using fisher kernels, in: The 22nd International Conference on Artificial Intelligence and Statistics, 2019, pp. 3382–3390. [35] H. Zylberajch, P. Lertvittayakumjorn, F. Toni, Hildif: Interactive debugging of nli models using influence functions, in: Proceedings of the First Workshop on Interactive Learning for Natural Language Processing, 2021, pp. 1–6. [36] R. R. Selvaraju, S. Lee, Y. Shen, H. Jin, S. Ghosh, L. Heck, D. Batra, D. Parikh, Taking a hint: Leveraging explanations to make vision and language models more grounded, in: Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019, pp. 2591–2600. [37] P. Lertvittayakumjorn, L. Specia, F. Toni, Human-in-the-loop debugging deep text classi- fiers, in: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020, pp. 332–348. [38] P. Schramowski, W. Stammer, S. Teso, A. Brugger, F. Herbert, X. Shao, H.-G. Luigs, A.-K. Mahlein, K. Kersting, Making deep neural networks right for the right scientific reasons by interacting with their explanations, Nature Machine Intelligence 2 (2020) 476–486. [39] T. Popordanoska, M. Kumar, S. Teso, Machine guides, human supervises: Interactive learning with global explanations, arXiv preprint arXiv:2009.09723 (2020). [40] T. Miller, Explanation in artificial intelligence: Insights from the social sciences, Artificial Intelligence (2018). [41] J. V. Jeyakumar, J. Noor, Y.-H. Cheng, L. Garcia, M. Srivastava, How Can I Explain This to You? An Empirical Study of Deep Neural Network Explanation Methods, Advances in Neural Information Processing Systems 33 (2020). [42] L. Malago, N. Cesa-Bianchi, J. Renders, Online active learning with strong and weak annotators, in: NIPS Workshop on Learning from the Wisdom of Crowds, 2014. [43] P. W. W. Koh, K.-S. Ang, H. Teo, P. S. Liang, On the accuracy of influence functions for measuring group effects, in: Advances in Neural Information Processing Systems, 2019, pp. 5254–5264. [44] S. Basu, X. You, S. Feizi, Second-order group influence functions for black-box predictions, arXiv preprint arXiv:1911.00418 (2019). [45] A. Ghorbani, J. Zou, Data shapley: Equitable valuation of data for machine learning, in: International Conference on Machine Learning, PMLR, 2019, pp. 2242–2251.