It is known that neural networks, such as convolutional neural networks, struggle with pattern recognition if training sets contain ambiguities (i.e. several labels can correspond to one and the same pattern). However, I struggle to locate the paper that directly discusses this issue, or demonstrates it for the first time, etc. If anybody can point me to the paper(s), that would really help. Thanks!


Traditional single-label classification implies disjoint labels. To the extent that labels are not disjoint or distinct within a single-label classification task, the problem is one of the definition of distinct concepts. This problem has been discussed as early as 1984 in Valiant's "A Theory of the Learnable" where he identified the theoretical limits of a class of learnable concepts that can be approximated in polynomial time via a deductive procedure.

On the other hand, labels can have a many-to-one relationship for images in multi-label datasets. The use of the word "ambiguities" implies incorrect, incomplete, or indeterminate mapping of labels in the training dataset. Note: A probabilistic or hierarchical label assignment is often used to quantify or qualify the class status and thus reduce errors related to labeling.[1]

Two of the main sources of label ambiguity can generally be divided into label noise and label redundancy.

Label noise refers to errors in labeling or the description of instances. "Classification on Soft Labels is Robust against Label Noise", (Thiel, 2008) includes several references to the problem in CNNs. An earlier paper "Reducing correspondence ambiguity in loosely labeled training data" (Barnard and Fan, 2007) addresses the issue of correspondence ambiguity and the use of soft labels:

The training data available for a specific classification task must not necessarily be labeled hard. That is, a training sample might belong, to different degrees, to multiple classes simultaneously. For example, multiple experts might not agree on the diagnosis for the sample, or hear different emotions in a spoken sentence. In fact, problems in the field of medical or life sciences, like predicting the secondary structure of proteins, often produce and require soft labels.

The theoretical consequence of label noise on generalization error was given by Vapnik and Chervonenkis (1971) in the Universal Estimate Rate bound. For $f$ features of $m$ data points in a $L$ learner applied to a training set $S$:

With high probability, the generalization error of the hypothesis $h = L(S)$, given by $L$ applied to $S$ (unrestricted to any feature subset), is bounded by:

$$ \epsilon(\hat{h}) \leq \epsilon_g (f) + \mathcal{O} \Big( \sqrt{\frac{f_{VC}}{(1-2\eta)^2m}\Big(log \frac{m}{f_{VC}}+1\Big)} \Big) $$ [...] when the training data have independently been corrupted at some noise rate $\eta$ [...].

Label redundancy is first mentioned by Zhao (2008) in "Adding Redundant Features for CRFs-based Sentence Sentiment Classification". Label semantic redundancy (eg, cat and kitten often refer to the same thing) is addressed in several papers related to multi-class classification. For example, it can be exploited by joint image/label embedding.[3]


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.