Unlabeled Data as the Anchor: Identifying Label-Noise Matrices from Block-Independent Mixtures

When training labels are wrong at a systematic rate, the standard repair is to estimate a noise transition matrix, a table giving the probability that an example of true class $i$ is recorded as class $j$, and then correct the classifier with it. Almost every estimator needs either "anchor points" (examples that certainly belong to one class) or a geometric assumption about how class posteriors spread inside the probability simplex. On text and tabular data, classes overlap, so neither tends to hold. We propose to stop asking the noisy labels to carry the whole burden. If features can be grouped into three or more blocks that are roughly independent once the true class is known, then a large pool of unlabeled examples is enough to recover the class-conditional distributions, up to a relabeling of which component is which. The same multi-view argument recovers latent classes in tensor models. After that, the noisy labels have two small jobs: estimate the transition matrix through a convex fit, and decide which recovered component corresponds to which class.

Put in two sentences: unlabeled data identifies the hidden classes, because conditionally independent feature blocks make a mixture model identifiable, and the noisy labels only align those classes and measure how they get corrupted. Under this split, the accuracy of the transition estimate should be governed by the size of the unlabeled pool, not the noise rate. That prediction can be tested directly, and it would explain when unlabeled data helps noisy-label learning on text and tables.

Core Claim

Let $\hat r_k(x)$ be the posterior probability of latent component $k$ given features $x$, taken from a block-independent mixture fit on unlabeled data. With $\hat r$ held fixed, the transition matrix is estimated from the noisy labeled set $D_l$ by

$$\hat T = \arg\max_{T \in \mathcal{S}} \sum_{i \in D_l} \log \sum_{k=1}^{K} \hat r_k(x_i)\, T_{k \tilde y_i},$$

where $\mathcal{S}$ is the set of row-stochastic $K \times K$ matrices and $\tilde y_i$ is the observed noisy label. The objective is the log of a function linear in $T$, so it is concave and has a global optimum. It identifies $T$ whenever the second-moment matrix of $\hat r(x)$ over $D_l$ is full rank. That condition is far weaker than requiring anchors, which would make $\hat r$ one-hot somewhere, or VolMinNet's "sufficiently scattered" condition. The components carry arbitrary indices, so $\hat T$ absorbs a permutation. We pick the permutation that makes $\hat T$ diagonally dominant, solved as an assignment problem. This is the only step where the labels need to be "mostly right," and it is the same diagonal-dominance condition that Improved Naive Bayes with Mislabeled Data imposes.

The second ingredient addresses why conditional independence has kept Naive Bayes, a classifier that treats every feature as independent given the class, from being trusted here. Its posteriors are overconfident. In this setting overconfidence does specific damage: near one-hot $\hat r$ act as fake anchors and bias $\hat T$ toward the classifier's own confusion. We therefore do not assume independence across all features. Instead we learn a partition of features into blocks from unlabeled co-occurrence statistics, so that strongly dependent features (collocations such as "San"/"Francisco", or correlated clinical indicators) fall in the same block. Each block gets its own richer distribution, and independence is assumed only across blocks. Identifiability needs only three independent views, not full factorization, so this relaxation costs nothing in theory and should reduce overconfidence in practice.

Relation to Prior Work

Two papers motivate the proposal by connecting independence to noise identification. Identifiability of Label Noise Transition Matrix uses Kruskal's theorem to show that conditionally independent features can stand in for extra noisy labels. It applies this only to the noisy labeled set and only to discretized features, and it reports that better self-supervised or disentangled representations cut the transition-matrix error from 14.51 to 4.42 (SimCLR) and 3.73 (IPIRM) on CIFAR-10 at 30% noise. We move the multi-view identification to unlabeled data and to blocks with continuous or count-valued features. Improved Naive Bayes with Mislabeled Data runs EM over Naive Bayes with a latent true label and a mislabeling matrix, but it has no unlabeled pool and assumes fully factorized binary features. We borrow its identifiability constraint and add both the unlabeled pool and block structure.

Learning to Classify Text from Labeled and Unlabeled Documents supplies the semi-supervised EM machinery but assumes the seed labels are clean. It also gives the key constraining negative result: when mixture components do not match classes, unlabeled data can hurt. Our method inherits this risk, and the experiments below test it head on.

Anchor-free estimators constrain the design by showing what labeled-only identification costs. Provably End-to-end Label-noise Learning without Anchor Points minimizes simplex volume and depends on the network's own noisy posteriors. Learning Noise Transition Matrix from Only Noisy Labels via Total Variation Regularization inverts the way label noise contracts the simplex. Clusterability as an Alternative to Anchor Points When Learning with Noisy Labels uses agreement among nearest-neighbor triplets. All three extract identification from the labeled set alone. Beyond Images: Label Noise Transition Matrix Estimation for Tasks with Lower-Quality Features is the closest in domain: it uses linear PCA decoupling and mutual-information weighting on tabular and text data. PCA gives uncorrelated features, not conditionally independent ones, and that paper uses no unlabeled data. DivideMix: Learning with Noisy Labels as Semi-supervised Learning and Instance-Dependent Label-Noise Learning with Manifold-Regularized Transition Matrix Estimation bring semi-supervised ideas into noisy-label learning, but they use them on the noisy set itself and rely on image augmentations.

Research Program

We first build the block-independent mixture. Features are clustered into $B \geq 3$ blocks by spectral clustering on a dependence graph estimated from the unlabeled pool. For text the dependence measure is pointwise mutual information of co-occurrence; for tables it is a mixed-type dependence measure. Within a block, text uses a multinomial over the block's vocabulary with pairwise terms for the strongest dependencies, and tables use a full-covariance Gaussian or a categorical joint distribution. The mixture over $K$ components is fit by EM on the unlabeled pool, with a tensor-method initialization to avoid poor local optima.

Second, we estimate $T$ with the convex fit above. We then compare it with a joint variant in which a single EM sees labeled and unlabeled data together. This tests whether the decoupled two-stage estimate is a better-conditioned version of the joint likelihood or simply equivalent to it. We expect the decoupled version to be more stable at high noise, because labels cannot pull the components toward the noise. If the joint EM matches it, we report the method as the joint EM, and the contribution becomes the blocking and the identification analysis.

Third, we analyze the method. We will derive a finite-sample bound in which the error of $\hat T$ splits into a mixture-estimation term, which shrinks with the unlabeled size $n_u$ at the usual $1/\sqrt{n_u}$ parametric rate, and an alignment term that depends on $n_l$ and the conditioning of $E[\hat r \hat r^\top]$. We will also characterize the bias caused by residual dependence across blocks.

Finally, the corrected classifier is either the mixture posterior itself or a discriminative model trained with forward correction using $\hat T$. The second option tests whether the estimated matrix is useful beyond its own generative model.

Baselines

The naive reference is a classifier trained directly on the noisy labels with no correction. We run it as both multinomial Naive Bayes and logistic regression on the same features, with an equal tuning budget on a noisy validation split. It sets the floor that any correction must clear.

The strongest generative competitor is the union of Learning to Classify Text from Labeled and Unlabeled Documents and Improved Naive Bayes with Mislabeled Data. Concretely, this is a single EM over a fully factorized Naive Bayes that sees labeled and unlabeled data together and includes a transition matrix. It is the obvious construction at this intersection, so it must be beaten. It receives the same unlabeled pool, the same initialization budget, and the same number of EM restarts. Beating it means a lower transition-matrix error and higher clean accuracy at noise rates of 40% and above, with the gap growing as noise increases. For reference, INB reports 92.6% versus 75.9% for plain Naive Bayes on its synthetic 500-feature, 5-class benchmark. Nigam et al. report 70% accuracy on 20 Newsgroups with 300 clean labels and 10,000 unlabeled documents. We found no reported result on Lacuna for 20 Newsgroups combining noisy labels with an unlabeled pool, so this baseline must be run by us.

The strongest anchor-free estimator for this domain is Beyond Images: Label Noise Transition Matrix Estimation for Tasks with Lower-Quality Features. It reports a reduction in estimation error "by over 50%" against Confident Learning and HOC on UCI tables and a "~3% jump" in accuracy on AG's News with BERT embeddings, though no per-dataset numbers were found. To make the comparison fair, we also give it the unlabeled pool for fitting its PCA. HOC and VolMinNet are run on the same features as additional anchor-free baselines.

Two ablations isolate the key ingredients. Replacing learned blocks with full factorization isolates the blocking. Replacing the unlabeled fit with a fit on the noisy labeled set alone isolates the unlabeled data. A third ablation tempers $\hat r$ to vary its confidence, which tests the fake-anchor mechanism.

Why not just…?

Why not just run the combined Nigam/INB EM? This is the most serious threat. Under its fully factorized model it should, in principle, identify the same quantities. Our bet is that two things break it in practice. Full factorization produces overconfident posteriors that act as fake anchors, and at high noise the labeled likelihood term drags components toward the noisy partition. The blocking ablation and the joint-versus-decoupled comparison settle this directly. If the combined EM with learned blocks equals our method, we say so and report the blocking as the contribution.

Why not learn representations on the unlabeled data and then run HOC or the Beyond Images estimator? The Identifiability paper's own numbers (14.51 to 4.42 error with SimCLR) show that unlabeled pretraining helps existing estimators substantially, so this is a real competitor. The difference is that those estimators still extract identification from labeled-set geometry, so they should degrade as noise grows. Our method should stay flat until the diagonal-dominance alignment fails. We run them on self-supervised and frozen-BERT features, with the same unlabeled pool, to test this.

Why not use DivideMix and skip the transition matrix? DivideMix depends on MixUp and image augmentations that have no clean counterpart for bag-of-words or tabular rows. It also trains two networks. Its strong image numbers (76.0% on CIFAR-10 at 90% symmetric noise) do not transfer by default. We will run a feature-space MixUp version on BERT embeddings for AG's News to check, and we will concede the point on any dataset where it wins.

Proposed Experiments

Experiments use 20 Newsgroups, Reuters-21578, and AG's News (bag-of-words and frozen BERT embeddings), plus the UCI tabular sets used by Beyond Images, including Heart and Titanic. On each, we hold out a large unlabeled pool. The labeled portion is corrupted with symmetric, pair-flip, and instance-dependent noise from 20% to 70%, with labeled sizes from 300 to 5,000. Metrics are the absolute transition-matrix error as in the Identifiability paper, clean test accuracy or micro-F1, and calibration error of the corrected posteriors.

Three decisive checks follow. First, at fixed $n_u$, we plot matrix error against noise rate. Our method should be flat up to the point where the true $T$ stops being diagonally dominant, while labeled-only estimators should rise steadily. Second, at fixed noise, varying $n_u$ should shrink the error roughly as $1/\sqrt{n_u}$, while varying $n_l$ should mostly affect alignment failures. Third, on synthetic data we can dial in dependence across blocks and add Nigam-style sub-topics, meaning several clusters within a class. This maps where identification breaks. If sub-topics break it, we test multi-component classes in which the component-to-class mapping is aligned by the same assignment step.

A failure of the first check would mean unlabeled data is not doing the identifying, and the core claim would be wrong.