Training a model on samples with both correct and wrong (non-noise) labels When we train a model, we usually use pairs of $(x_n,\ label_n)$ as training data. In my case, I have pairs of $(x_n, \ label_n)$ and also pairs of $(x_n,\ wrong\_label_n)$, where both $label$ and $wrong\_label$ come from the same set of labels. Note: the wrong labels are known, not noise.
Is there any way to train on samples with known wrong and correct labels instead of training on correct labels only? Maybe a modified loss function I can use? I don't really mind what kind of model it works for (regressions, CART, ANNs etc).
 A: It's a good question. There are similar works in the field of clustering (aka constrained clustering, where you provide "must link" and "cannot link" connections as input to the algorithm), but I'm not aware of anything along these lines for classification using neural networks.
As a first attempt, I would probably do something along these lines:
First, convert your labels to the format $([true\_labels], [false\_labels])$. For example, if I do animal classification:


*

*Image1, which I know is of a cat, would be labeled $([cat], [])$ 

*Image2, which I'm sure is not a whale would be $([], [whale])$ 


I would then adapt the loss function appropriately. For example, standard 0-1 loss could be extended to this case by paying a penalty of 1 for either of the two following scenarios: Either classifying an animal differently than its' true label (classifying Image1 as whale) or classifying an animal to be a something which I know is not the true label (classifying Image2 to be a whale).
For example, in the simple case in which we allow a single label for each case (true label and false label), then the regular 0-1 loss, $\sum _{x,y} {1[h(x)\neq y ]} $, will become:
$\sum _{x,y=(y_{true},y_{false})} {1[h(x)\neq y_{true} \lor h(x)=y_{false}]} $
A: The key is to notice that your problem is equivalent to machine learning with overlapping classes. 
Given item $x_n$ and information that it does not belong to class $L_i$, notice that 
$x_n \notin L_i \iff x_n \in (L \setminus L_i)$
and, for another class $L_j$,
$L_i \cap L_j = \emptyset \Rightarrow L_j \in (L \setminus L_i)$
so 
$x_n \in L_j, x_n \notin L_i \Rightarrow x_n \in L_j \subseteq (L \setminus L_i)$
You can thus define $L'_i:= L \setminus L_i$. These new classes work just like regular classes, and can contain the regular classes defined earlier.
Unfortunately, this does not mean that the classification is hierarchical (which would simplify matters), since for two classes $L'_i$ and $L'_j$ these classes might have a non-zero intersection. Consider $x_1, x_2 \notin L_1$ and $x_2, x_3 \notin L_2$. Then, $L'_1$ and $L'_2$ overlap, but one is not contained in the other.
I don't know much about ML with overlapping classes; I know the problem is considered to be tough and that there are definitely publications on this. Search for multi-label classifications (e.g. the mldr package in R). Hope this helps.
