The label-noise guarantee that weakens near a tie

A label-noise transition matrix stores Tᵢⱼ = P(ỹ = i | Y = j): the chance that true class j is recorded as label i. Knowing it lets a learner correct losses, audit biased labels, and build prediction sets when annotations are unreliable.

The usual anchor method searches for one example that a model believes is almost certainly class j, then reads that example's noisy-label posterior as column j. That makes the whole matrix depend on one extreme, pointwise probability estimate—the place calibration is least trustworthy.

For each class, the algorithm chooses a score threshold that maximizes accepted-set purity while keeping at least a prescribed number of examples. The site runs the TypeScript below; Python and C++ are line-for-line translations.

def estimate_column(labels, accepted, class_count):
    counts = [0] * class_count
    total = 0
    for label, keep in zip(labels, accepted):
        if keep:
            counts[label] += 1
            total += 1
    if total == 0:
        raise ValueError('accept at least one sample')
    return [count / total for count in counts]

On a six-example toy score list, requiring four accepted examples selects threshold 0.82, accepts 4, and estimates the target-class column entry as 0.75. The important control is coverage: accepting fewer points raises purity but leaves fewer counts from which to estimate the column.

Theorem 1 separates error into a bias term and a finite-sample term. In a deterministic illustration with 10,000 samples, ten classes, and diagonal margin 0.4, higher coverage steadily reduces sampling noise while admitting more off-class examples. The U-shape is computed from the theorem's formula; it is not a paper-reported experiment.

The bound multiplies its bias by Cₜ = 2 / (Tⱼⱼ − max Tⱼₗ). The denominator is the gap between the correct observed label and the strongest wrong label in column j. When those probabilities nearly tie, the guarantee becomes weak even with a good selector.

The anchor estimator inherits the pointwise posterior rate n⁻ᵅ⁄⁽²ᵅ⁺ᵈ⁾. With fixed sample size and smoothness, that rate approaches one as dimension grows—barely learning at all. The selective estimator's sampling term has no explicit dimension factor, though the classifier still has to rank examples well in practice.

Under 0.2-uniform synthetic noise, at least one proposed algorithm improves on the anchor baseline for most model–dataset pairs. On CIFAR-10 with a neural net, Algorithm 2 reduces transition-matrix MAE from 0.009 to 0.006.

The harsh 0.45-flip setting reveals the useful caveat. On CIFAR-10 with a neural net, Algorithm 1 is worse than the anchor baseline (0.036 versus 0.029), even though Algorithm 2 reaches 0.015. The framing is powerful; the particular selector and threshold rule still matter.

The experiments inject class-dependent noise synthetically and train one binary problem per class. The paper notes that this scales poorly with class count and can struggle for minority classes. The next test should use real annotator disagreements, report per-class coverage and condition numbers, and compare downstream corrected-model accuracy—not only matrix MAE.

Build the one-versus-rest score on the logistic-regression page, or replace it with a random forest. The estimator only needs a useful ranking; it does not require calibrated probabilities.