  The noise transition matrix plays a central role in the problem of learning
with noisy labels. Among many other reasons, a large number of existing
solutions rely on access to it. Identifying and estimating the transition
matrix without ground truth labels is a critical and challenging task. When
label noise transition depends on each instance, the problem of identifying the
instance-dependent noise transition matrix becomes substantially more
challenging. Despite recent works proposing solutions for learning from
instance-dependent noisy labels, the field lacks a unified understanding of
when such a problem remains identifiable. The goal of this paper is to
characterize the identifiability of the label noise transition matrix. Building
on Kruskal's identifiability results, we are able to show the necessity of
multiple noisy labels in identifying the noise transition matrix for the
generic case at the instance level. We further instantiate the results to
explain the successes of the state-of-the-art solutions and how additional
assumptions alleviated the requirement of multiple noisy labels. Our result
also reveals that disentangled features are helpful in the above identification
task and we provide empirical evidence.
