Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors present an approach and framework to mitigate training biases by combining influence functions and data relabeling. 
The idea behind training biases is that part of the data that is used to train the model does not accurately represent the real data distribution seen in the test set. Thus, having a mismatch between training and test data. This creates a generalization problem for the machine learning model. 

Other authors have used different resampling approaches to try and address this problem, relying on the training loss and then relabeling the data; or by using influence functions and changing the weight of the harmful examples so that the effect on the test loss is lower. 
The current authors combine both approaches, and present a framework that relabels harmful training data based on influence functions (on the test set). 

The results of their experiments show that they are able to reduce the test loss compared to other data resampling approaches.
main_review: I believe the paper is very well-written and structured. I appreciate that the authors had taken time and consideration into writing an abstract and introduction that clearly motivates the problem in hand, gives enough background into the problem, and that clearly explains the solutions and the experimental results.

The paper seems to be solidly based in theoretical proofs of their methods, together with experimental results comparing it to some baselines plus the state-of-the-art approach. I liked that the limitations are clearly explained in the appendix.  
All in all I think is a good paper. 

Regarding weaknesses of the paper that I believe could help at improve the paper if addressed. 
- First, is not until the reader reaches section three that the reader realizes that the authors use influence analysis on the validation set rather than on the test set. I think that the authors should improve the consistency across the paper of using the term "test set". Throughout the introduction, abstract, background, and part of the methodology, the validation set is referred as the test set. Which then is clarified to be the validation set, since the test set is only used for a proper test evaluation (without altering the training set). I would suggest to either clarify that at the beginning, or simply use validation set instead of test set. 
- Algorithm for RDIA such as done for RDIA-LS (Algorithm 1) in the Appendix E. I believe this will help portray more details for further reproducibility.
- Regarding reproducibility, the authors mention that the code is available in the Appendix. Do the authors mean the programming code? If so, I couldn't find a link there. A link with the source code would be beneficial for the same reasons as the point above. 
- My last and probably the most relevant concern is the following. Imagine we have an imbalanced dataset, and that the algorithm is not able to classify well that portion of the dataset with fewer examples. The problem in this case is that we don't have enough data of some particular group of instances, needing some sort of solution like data augmentation (for example). 
However, if we would apply the authors solution (or the other authors solution for that matter) we would be treating these examples as incorrect. In the authors case the positive aspect is that the examples won't be removed (as with some of the others solutions). But, how would relabeling those examples help the model learn about this specific category of instances? I am thinking on the lines of a dataset where we have sensitive attributes e.g race, gender. Where some of the people are less represented. From my perspective this solution might have a negative impact in the generalization aspect since the model might not really learn those people that might look different from the rest. Or it could be the case where it helps at mitigating this bias. 
This comment is more of an opening for a discussion with the authors, rather than "something to fix" . It would be great if the authors could just comment what they think on this matter during the discussion period. Since I am sure they have thought about this aspect, and I wouldn't want to have missed or misinterpreted some part of the paper. 
Just to clarify, my scoring hasn't been influenced by this last comment. 
summary_of_the_review: I think this is a good paper with merits to be included as part of the conference proceedings. 
I believe that the paper is well-written, the claims are well-supported, and the experiments seem correct. 


I believe a few things can be improved (as mentioned above)
The reason I don't give a higher score is because I believe that the methodology does not seem to be too novel and the results are marginally better, except for one or two datasets.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents a relabeling scheme for binary and multiclass
classification tasks in which harmful training examples identified by
influence functions are relabeled to improve performance on a hold-out
set. The authors formally prove that the relabeling scheme determines
a reduction in loss wrt down-weighting or discarding examples, and
report experimental comparisons confirming the advantage of the
proposed strategy.
main_review: The manuscript is well-written and clear. The proposed solution is
simple and clean with a sound theoretical justification.

The practical utility of the approach is unfortunately limited given
the cost of estimating influence functions on non-linear models. This
is a well-known problem, especially when applying influence function
to deep architectures. The authors address the problem by proposing to
replace influence functions with training loss while retaining their
relabeling scheme. I wonder how this simple strategy works in
comparison to their RDIA approach (the appendix does not report
comparisons in terms of accuracy), and under which conditions it could
fail (e.g. distribution shift rather than noise). Otherwise one has
the (probably false?) impression that all you need is training loss +
relabeling. 
summary_of_the_review: A simple and clean solution for influence-based data relabeling.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper uses influence functions from robust statistics to perform two tasks in order to mitigate label noise and generalize better: (i) Identify harmful instances via IF; (ii) Relabel the harmful instances to have better generalization. 

main_review: The paper uses  influence functions from robust statistics to first identify harmful instances and then relabel them based on a novel relabeling function using influence approximation. Influence estimations have been widely used to identify harmful instances or understand the impact of training samples. This paper goes one step further and uses this analysis to relabel the instances in order to achieve better generalization and lower test error. While the technical novelty is limited as the proposed formulations are extensions of existing influence functions and application is interesting. The authors use their relabeling strategy on multiple datasets and models (including deep models).     

Pros:

(1) The paper does a focused job of using influence function for identifying harmful examples and fixing them by relabeling. While in the recent times there are papers on influence functions to identify harmful instances, this paper does a very good comprehensive and focused study compared to others.

(2) The paper is well-written and easy to follow. Related works is well laid out and well covered.

(3) Experimental section is complete with experiments on deep models and the proposed RDIA-LS.  The authors acknowledge the limitations of RDIA on deep models due to erroneous influence estimates for deep models and provide a workaround for it in the Appendix. This is an improvement from the earlier versions of the paper (from a previous conference). I would definitely like to highlight this section in the main paper as it’s important for all practical purposes. 


Cons:

(1) The technique of using influence function for identifying harmful instances is not new and well known and applied in the recent times. Hence I feel the technical novelty is not solid and limited in some aspects. However saying that, applications of existing influence functions are not straightforward and hence that’s one point to be noted. 


In general, the paper is well-organized, a good study on influence based relabeling and has sufficient empirical studies to backup it’s proposed formulation. 
summary_of_the_review: The paper does an end to end study of using influence functions for relabeling instances to achieve a lower test-loss. The technical novelty is slightly limited as the formulations are extensions of current influence functions, however the paper is supported by strong empirical studies (including limitations about RDIA in deep models).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a data relabeling technique using influence function.
The authors first derived the influence function for data relabeling as follows.

$$
\eta_{\theta \delta}\left(z\_i, z\_j^{c}\right) \left. \triangleq \frac{d l\_j^c \left(\hat{\theta}\_{\epsilon\_i \delta\_j}\right)}{d \epsilon\_i}\right|_{c\_i=0} =-\nabla\_{\theta} l\_j^c(\hat{\theta}) H\_{\hat{\theta}}^{-1}\left(\nabla\_\theta l\_i\left(z\_{i \delta}, \hat{\theta}\right)-\nabla\_\theta l\_i(\hat{\theta})\right)
$$

The authors then derived the specific expression for the cross-entropy loss:
$$
\eta_{\theta R}\left(z_{i}, z_{j}^{c}\right)=-\nabla_{\theta} l_{j}(\hat{\theta}) H_{\hat{\theta}}^{-1} w\left(z_{i}, \hat{\theta}\right)=-\nabla_{\theta} l_{j}(\hat{\theta}) H_{\hat{\theta}}^{-1}\left(-\frac{\nabla_{\theta} l_{i}(\hat{\theta})}{1-\varphi\left(x_{i}, \hat{\theta}\right)}\right)=\frac{-\Phi_{\theta}\left(z_{i}, z_{j}^{c}\right)}{1-\varphi\left(x_{i}, \hat{\theta}\right)}
$$
The authors experimentally demonstrated that data relabeling is more effective than the standard sampling/data reweighting-based approach for model improvement.
main_review: ## Strength
The authors empirically demonstrated that the label correction is much more effective than the standard sampling/data reweighting-based approach for model improvement.
This result is coherent with the one previously reported in [Ref1] where a very similar data relabeling approach was studied.
The results on DNNs (on MNIST and CIFAR10) are new where [Ref1] considered only kernel-based models.

* [Ref1] Training Set Debugging Using Trusted Items, AAAI 2018.
    * *I am not the author of [Ref1].*

## Weakness
The proposed method is very similar to the one proposed in [Ref1], while the current paper misses this important prior work.
[Ref1] formulated the data relabeling problem as the bi-level optimization, and proposed an algorithm to optimize the amount of relabeling using gradient descent.
An important point here is that the gradient of the amount of relabeling considered in [Ref1] is essentially identical to the relabeling criteria proposed in (10) in this paper (see below for the detail).
In addition, once we interpret the proposed label correction criteria as the gradient descent update, Lemma1 and Theorem1 confirming the decrease of the validation loss are more or less trivial (unless the amount of correction is too large).
In summary, although the ways the amount of relabeling is optimized are different (using gradient descent or by one step update), I believe the close connection between [Ref1] and the proposed method needs to be described appropriately in the paper, e.g., through detailed discussions and experimental comparisons.

*Close connection to [Ref1]*

As the special case of the formulation of [Ref1], we can obtain the following bi-level optimization (here, I removed some terms from the original formulation in [Ref1] for simplicity, and used the notation of the current paper).

$$
\min\_{\delta \in \mathbb{R}^{n}} L(Q; \hat{\theta}\_\delta) := \frac{1}{M} \sum\_{j=1}^{M} l\_j^c(\hat{\theta}\_\delta) , \\: \text { s.t. } \\: \hat{\theta}\_\delta = \underset{\theta \in \mathbb{R}^{p}}{\operatorname{argmin}} \frac{1}{N} \sum\_{i=1}^{N} l\_i(z\_{i\delta\_i}, \theta) ,
$$

where $\delta$ is the amount of relabeling.
This is the optimization of the amount of relabeling so that the the validation loss to be minimized.
Following [Ref1], we can derive the gradient of the validation loss $L(Q; \hat{\theta}_\delta)$ with respect to $\delta_i$ as

$$
\frac{dL(Q; \hat{\theta}\_\delta)}{d\delta\_i} = \nabla\_\theta L(Q; \hat{\theta}\_\delta) \frac{d\hat{\theta}\_\delta}{d\delta\_i} = -\frac{1}{N}\nabla\_\theta L(Q; \hat{\theta}\_\delta)^\top H\_{\hat{\theta}\_\delta}^{-1} \frac{\partial l\_i(z_{i\delta_i}, \hat{\theta}\_\delta)}{\partial \delta\_i} .
$$

When there is no label correction, $\delta = 0$ and we have $\hat{\theta}_0$.

Then, if we consider relabeling the $i$-th training instance with the gradient step size $\epsilon$, we have the update

$$
\delta\_i \leftarrow 0 - \epsilon \left. \frac{dL(Q; \hat{\theta}\_\delta)}{d\delta\_i} \right|\_{\delta\_i = 0}
$$

and the decrease of the validation loss induced by this update is 

$$
L(Q; \hat{\theta}\_{\delta}) - L(Q; \hat{\theta}\_0) \approx \epsilon \left. \frac{dL(Q; \hat{\theta}\_\delta)}{d\delta\_i} \right|\_{\delta\_i = 0} 
$$
$$
= \frac{\epsilon}{N} \nabla\_\theta L(Q; \hat{\theta}\_0)^\top H\_{\hat{\theta}\_0}^{-1} \frac{\partial l\_i(z\_{i\delta\_i}, \theta_0)}{\partial \delta\_i}
$$
$$
\approx \frac{1}{N}\nabla\_\theta L(Q; \hat{\theta}\_0)^\top H\_{\hat{\theta}\_0}^{-1} (l\_i(z\_{i \epsilon}, \theta) - l\_i(\theta)) .
$$
The last line is nothing but the criteria (10) proposed in this paper.

---
## After Discussion with Authors

I conducted an experiment on breast cancer dataset by myself (see below).
There, I confirmed that RDIA does better than the One-Step GD update of [Ref1].
I therefore decided to increase my score with a strong expectation to the authors for **referring [Ref1] appropriately in the main body of the paper**.
As I mentioned in my original review, this is not the first study considering relabeling based on the influence function-like technique.
Recalling that influence function is one specific example of implicit gradient, [Ref1] is the first work in this direction to my knowledge (even if [Ref1] does not describe the fact explicitly).
As I demonstrated in my code, the simplest version of [Ref1] with only one-step update (and without any human intervention) does good job.
**I strongly expect the authors to pay certain respect to [Ref1] and do not underestimate their technical contribution**.
For example, the current writing in Appendix H seems to be not appropriate.
Even without human intervention, DUTI [Ref1] can do the same (i.e., relabel the training bias towards better model performance) as the proposed approach (but with slightly inferior performance).
> (2) The learning task of DUTI is to debug the training instances which may contain the wrong labels and predict the true labels. While the target of our approach is to relabel the training bias towards better model performance. In this way, only our approach could relabel the biased training samples with correct labels towards better model performance.

### The results on breast cancer dataset

*Test Accuracy*

|     |   ERM |   One-Step GD |   RDIA |
|----:|------:|--------------:|-------:|
| 0   | 0.959 |         0.96  |  0.961 |
| 0.1 | 0.96  |         0.968 |  0.962 |
| 0.2 | 0.953 |         0.951 |  0.959 |
| 0.3 | 0.931 |         0.944 |  0.957 |
| 0.4 | 0.842 |         0.897 |  0.958 |
| 0.5 | 0.563 |         0.762 |  0.958 |
| 0.6 | 0.178 |         0.782 |  0.953 |
| 0.7 | 0.075 |         0.875 |  0.953 |
| 0.8 | 0.05  |         0.931 |  0.949 |
| 0.9 | 0.037 |         0.95  |  0.94  |

*Test Loss*

|     |      ERM |   One-Step GD |     RDIA |
|----:|---------:|--------------:|---------:|
| 0   | 0.141025 |      0.161033 | 0.13819  |
| 0.1 | 0.237151 |      0.24697  | 0.146115 |
| 0.2 | 0.345921 |      0.347718 | 0.157343 |
| 0.3 | 0.453018 |      0.451272 | 0.171787 |
| 0.4 | 0.56437  |      0.557865 | 0.185989 |
| 0.5 | 0.698697 |      0.63033  | 0.197167 |
| 0.6 | 0.876071 |      0.590184 | 0.203124 |
| 0.7 | 1.08732  |      0.492453 | 0.196512 |
| 0.8 | 1.44151  |      0.362804 | 0.197389 |
| 0.9 | 2.0108   |      0.265325 | 0.241273 |

```
import numpy as np
import pandas as pd
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from IPython.display import display

def sigmoid(u):
    return 1.0 / (1.0 + np.exp(-u))

def logloss(w, b, x, y):
    p = sigmoid(x.dot(w) + b)
    return - (y.dot(np.log(p)) + (1 - y).dot(np.log(1 - p))) / y.size

def logreg(x, y, lam=0.1, lr=0.01, max_itr=100):
    num, dim = x.shape
    xo = np.concatenate([x, np.ones((num, 1))], axis=1)
    w = np.zeros(dim+1)
    for itr in range(max_itr):
        p = sigmoid(xo.dot(w))
        g = (p - y).dot(xo) / num
        g[:-1] = g[:-1] + lam * w[:-1]
        w = w - lr * g
    return w[:-1], w[-1]

# experiment
lam = 1e-2
acc, loss = [], []
nr = np.linspace(0, 0.9, 10)
for noise_rate in nr:
    acc_n, loss_n = [], []
    for seed in range(10):

        # breast cancer data
        # train / val / test = 300 / 169 / 100
        x, y = datasets.load_breast_cancer(return_X_y=True, as_frame=False)
        x, xte, y, yte = train_test_split(x, y, test_size=269, random_state=seed)
        xval, xte, yval, yte = train_test_split(xte, yte, test_size=100, random_state=seed)

        # normalize features
        scaler = StandardScaler().fit(x)
        x = scaler.transform(x)
        xval = scaler.transform(xval)
        xte = scaler.transform(xte)

        # noisy label in training
        np.random.seed(seed)
        flip = np.random.rand(y.size) < noise_rate
        y = np.logical_xor(y, flip).astype(int)

        # fit logreg
        w, b = logreg(x, y, max_itr=500, lam=lam)

        # test accuracy / loss
        zte = (xte.dot(w) + b > 0).astype(int)
        acc_te1 = np.mean(yte == zte)
        loss_te1 = logloss(w, b, xte, yte)

        # influence function
        num, dim = x.shape
        xo = np.concatenate([x, np.ones((num, 1))], axis=1)
        p = sigmoid(x.dot(w) + b)
        H = xo.T.dot((p * (1 - p))[:, np.newaxis] * xo) / num
        H = 0.5 * (H + H.T) + np.diag([lam] * dim + [0]) # Hessian
        g = ((p - y)[:, np.newaxis] * xo) / num # gradient
        f = - np.linalg.solve(H, g.T).T # influence function

        # label gradient over validation loss
        xv = np.concatenate([xval, np.ones((xval.shape[0], 1))], axis=1)
        q = sigmoid(xval.dot(w) + b)
        gv = (q - yval).dot(xv) / xval.shape[0] # gradient of validation loss
        gy = f.dot(gv) * (np.log(p) - np.log(1 - p)) # label gradient

        # label correction by one-step gradient descent
        ynew = y - 1e+3 * gy # step size of GD = 1e+3
        ynew = np.minimum(1, np.maximum(0, ynew)) # clip label
        wnew, bnew = logreg(x, ynew, max_itr=500, lam=lam)

        # test accuracy / loss after label correction
        zte = (xte.dot(wnew) + bnew > 0).astype(int)
        acc_te2 = np.mean(yte == zte)
        loss_te2 = logloss(wnew, bnew, xte, yte)

        # label correction by RDIA
        ynew = y.copy()
        #ynew[f.dot(gv) > 0] = 1 - ynew[f.dot(gv) > 0] # flip label
        ynew[f.dot(gv) > 1e-3] = 1 - ynew[f.dot(gv) > 1e-3] # flip label
        wnew, bnew = logreg(x, ynew, max_itr=500, lam=lam)

        # test accuracy / loss after label correction
        zte = (xte.dot(wnew) + bnew > 0).astype(int)
        acc_te3 = np.mean(yte == zte)
        loss_te3 = logloss(wnew, bnew, xte, yte)

        acc_n.append((acc_te1, acc_te2, acc_te3))
        loss_n.append((loss_te1, loss_te2, loss_te3))
    
    acc.append(acc_n)
    loss.append(loss_n)
acc = np.array(acc)
loss = np.array(loss)

acc = pd.DataFrame(np.mean(acc, axis=1))
acc.columns = ['ERM', 'One-Step GD', 'RDIA']
acc.index = nr
loss = pd.DataFrame(np.mean(loss, axis=1))
loss.columns = ['ERM', 'One-Step GD', 'RDIA']
loss.index = nr
print('Test Accuracy')
display(acc)
print('Test Loss')
display(loss)
```
summary_of_the_review: The proposed method is very similar to the one proposed in [Ref1], while the current paper misses this important prior work.
Although the ways the amount of relabeling is optimized are different (using gradient descent or by one step update), I believe the close connection between [Ref1] and the proposed method needs to be described appropriately in the paper, e.g., through detailed discussions and experimental comparisons.

* [Ref1] Training Set Debugging Using Trusted Items, AAAI 2018.

The strong aspect of this paper over [Ref1] is the experimental results where the results on DNNs (on MNIST and CIFAR10) are reported, while [Ref1] considered only kernel-based models.

---
## After Discussion with Authors

I conducted an experiment on breast cancer dataset by myself (see below).
There, I confirmed that RDIA does better than the One-Step GD update of [Ref1].
I therefore decided to increase my score with a strong expectation to the authors for **referring [Ref1] appropriately in the main body of the paper**.
As I mentioned in my original review, this is not the first study considering relabeling based on the influence function-like technique.
Recalling that influence function is one specific example of implicit gradient, [Ref1] is the first work in this direction to my knowledge (even if [Ref1] does not describe the fact explicitly).
As I demonstrated in my code, the simplest version of [Ref1] with only one-step update (and without any human intervention) does good job.
**I strongly expect the authors to pay certain respect to [Ref1] and do not underestimate their technical contribution**.
review_title: null

Meta-review: All reviewers are very positive about this paper. The reviewer with the lowest score did independent experiments that show that the authors' method works well, and has had an extensive discussion with the authors that justifies a higher score. The paper is potentially very valuable to practitioners, since it shows how to compensate for a training set that is not representative of the test data.

Suggestion from the area chair to the authors: Briefly discuss the relationship between influence scores and propensity scores, which are standard in the literature on causal modeling and on sample selection bias, as in https://jmlr.csail.mit.edu/papers/volume10/bickel09a/bickel09a.pdf for example.
Decision: Accept (Oral)