# Are the labels updated during training in the algorithm presented in “An algorithm for correcting mislabeled data”?

I am trying to understand an algorithm for correcting mislabeled data in the paper An algorithm for correcting mislabeled data (2001) by Xinchuan Zeng et al. The authors are suggesting to update the output class probability vector using the formula in equation 4 and class label in equation 5.

I am wondering:

1. Are they updating labels while training, starting from very first back-propagation?

2. It seems like if we train on the same data and then predict labels on the same data, it would be the same as what the authors are suggesting. Does it make sense or I misunderstood?

I think that making some draws might help.

Below I tried to draw the model architecture. We start with classic feed-forward structure: input represented by a vector I with length f (number of features), a hidden layer H which does not have a fixed size, and output O of length c (number of classes). Then we have 3 extra vectors than usual: a vector U they refer as input (a bit confusing I have to say), and two vectors V and P representing classes probabilities. All these vectors have length c.

P is what we want to learn, new class probabilities for each instance that should correct wrong labels of misclassified instances in the initial dataset. So in some sense the aim of the work is not to train a model to make predictions but rather train a model to clean a training dataset. I think it's important to stress out this point because we talk about training but there is actually no test after the training, we just end with a modified training dataset with some instances relabelled. The relabelling depends on the learning of V rather than P (because as I will say also later on, the final arrow that goes from V to P is the identity function). V depends on U that also depends on V, again it sounds a bit confusing, the tricks rely in the initialisation.

In the second picture I just copied some formulas from the paper. They don't specifically say how they get the vector P in the first place, but I treat it simply as given because we need it to initialise U by applying the inverse sigmoid function, element-wise. We need also to define the hyper parameter D, the initial probability value for the true class V$$_y$$ in the initial dataset. In the paper they set it to .95. Using D we can initialise the vector V.

Once we initialise U and V we have all the elements to iterate over the dataset.

A first thing to notice is that they don't use back propagation to update U,V and P, they just define some updating rules (which require to define some other initial parameters, $$\textit{u_0}$$ and L$$_p$$). I want to stress out again that the mapping between V and P is just the identity function, I guess that they define it just to avoid confusion, because in the paper P appear as an input element, but nevertheless is also the output we want to learn. Back propagation is used only to update the weights in H.

So we can finally say that, regarding your first question, the answer is yes, they do start updating the classes probability vectors P from the very first iteration, even though is not clear how they initialise them (or from where they got them).

Regarding the second question instead I would say that no, this is definitely not as training a model with fixed label and then making predictions over the training dataset again. The whole point is that similar training instances will be initialised with the same P, and they will also produce similar U and V vectors. For misclassified instances, U will be updated with larger changes, because of the different produced O. For example an image of a 2 will generate a different output than an image of a 5, this would be reflected first on U and then on V and P . If training with fixed label instead you would just force the weight in the hidden layer to learn a function that treat the representation of a 2 and a 5 in a similar way, leading to low accuracy cause you would be telling the model "Hey, the straight line in the 5 is important also to recognise a 2".

I have to say that I never read about this dataset cleaning approach but it is interesting, and their results show that the cleaned version of the dataset lead to better performances, which is interesting because machine learning analysis usually gives for granted the correctness of the labels.

Hope this is of help in some ways!

• Many many thanks. This is really helpful. I think vector P is coming from D i.e. initial probability values with higher values to actual class: "In our experiment we chose D = 0.95. If C = 3 and y = 1, for example, then p1(O) = 0.95, and p2(O) = p3(O) = 0.05/2 = 0.025" Is it correct? 2. May be I missed it, where do they mention initialising U by inverse sigmoid. In equation 3, its V by sigmoid? 3. Do they only update class probabilities during training or also label (equation 5)? I thought labels should be updated in the end other wise whole input labels will be messed up after 1st Epoch. – ViB Mar 15 '20 at 22:19
• D is used to initialise V, which in principle is the same as P after the first iteration, but you might be right and they could have use the same initialisation for P as well. U initialisation is explained at page 495 "The input Ui is then determined from the corresponding output using the inverse sigmoid function". The arctan used to calculate V is another mystery, they say sigmoid and then they write tanh in the formula. The label in question 5 are calculated to perform the back propagation update on the hidden layer weight, so in my opinion they update it every step, not every epoch. – Edoardo Guerriero Mar 15 '20 at 22:31
• Waao, this is also what I missed "The input Ui is then determined from the corresponding output using the inverse sigmoid function". – ViB Mar 15 '20 at 22:41
• Sorry, I meant every iteration not epoch. By step you mean one iteration? – ViB Mar 15 '20 at 22:46
• You may be right again, I followed the updates order as describe in the paper. But thinking about it I would say that the order is probably not so determinant. I could update the label straight away and then back propagate using the new label, or I could back propagate with the actual label, then update the label and at that point the weights will be refined at the next epoch with the updated label (slowing down convergence probably). This is a classic situation in which the paper code would be really useful. – Edoardo Guerriero Mar 15 '20 at 23:07