Technical Summary: Stochastic Order Learning (SOL) for Rank Estimation with Noisy Data

1. Problem Definition

Rank estimation, the task of predicting the ordinal class (rank) of an object, is fundamental in applications such as facial age estimation, aesthetic score regression, and medical assessment. A primary challenge in this domain is label noise. Unlike nominal classification where all errors are often treated equally, rank estimation suffers from structured uncertainty. An error of misclassifying a 43-year-old as 59 is significantly more severe than misclassifying them as 45.

Existing noise-robust methods for classification or segmentation often fail in rank estimation because they treat all label errors identically, ignoring the ordinal property. Conversely, standard regression-based approaches often underperform compared to classification-based methods due to a failure to learn high-entropy feature representations. Furthermore, existing order learning methods typically assume clean, deterministic annotations, an assumption that breaks down when labels are corrupted. In noisy settings, an instance does not correspond to a single unique rank but relates to multiple neighboring ranks with varying degrees of plausibility.

2. Methodology: Stochastic Order Learning (SOL)

The paper proposes Stochastic Order Learning (SOL), a framework that reformulates rank estimation under label noise as a stochastic ordering problem. Instead of assuming a deterministic link between an instance and a single rank, SOL models the relationship as inherently probabilistic.

Core Formulation

Given a noisy rank $r_x$ for an instance $x$, the true rank $\bar{r}_x$ is modeled as $r_x = \bar{r}_x + e_x$, where the error $e_x$ follows a discrete Gaussian distribution. Consequently, an instance $x$ is associated with a set of plausible centroids $\{\mu_r\}$ with probabilities determined by the noise distribution.

The goal is to learn an embedding space where the stochastic dissimilarity $D_h(x, r)$—the expected squared Euclidean distance between the instance embedding $h(x)$ and rank centroids—is minimized for the observed noisy rank and increases monotonically as the rank distance increases.

Learning Objectives

SOL optimizes an encoder $h$ and rank centroids $\{\mu_r\}$ using a total loss function $\ell_{total}$ composed of two complementary objectives:

1. Discriminative Loss ($\ell_{disc}$):
   This loss structures the interaction between instances and centroids. It enforces a monotonicity constraint where the distance from an instance to a centroid decreases as the centroid's rank approaches the instance's noisy rank.

   • Mechanism: It acts as a weighted sum of squared distances. Coefficients derived from the second-order derivative of the Gaussian noise distribution create an "attraction" force toward the noisy rank and its immediate neighbors (within a threshold $\delta$) and a "repulsion" force against distant ranks. This accounts for label uncertainty by allowing the instance to be close to multiple plausible centroids.

2. Stochastic Order Loss ($\ell_{order}$):
   This loss enforces probabilistic ordering relations between pairs of instances $(x, y)$. Since true ranks are unknown, the method computes the probabilities of three ordering cases ($x \prec y$, $x \approx y$, $x \succ y$) based on the noisy ranks and the assumed noise distribution.

   • Mechanism: It employs margin-based losses weighted by the computed probabilities. If $x$ is likely to have a lower rank than $y$, the loss encourages $h(x)$ to be closer to lower-rank centroids and $h(y)$ to be closer to higher-rank centroids. If they are likely similar, their embeddings are encouraged to be close.

Outlier Detection and Relabeling

To further refine the model, SOL includes an optional iterative step:

• Detection: Instances where the estimated rank significantly deviates from the noisy label are identified as outliers.
• Relabeling: The labels of these outliers are adjusted based on the mean absolute error of the dataset, preventing drastic changes while correcting extreme errors.
• Iteration: The encoder is fine-tuned using these refined labels, and the process repeats to gradually reduce label noise.

3. Key Contributions

The paper outlines three primary contributions:

1. Reformulation: It reframes rank estimation under label noise as a stochastic ordering problem, moving away from deterministic instance-rank associations to probabilistic ones.
2. Framework (SOL): It introduces a learning framework that captures ordinal label uncertainty through two complementary objectives: a discriminative loss for instance-centroid interactions and a stochastic order loss for relational consistency.
3. Empirical Validation: It demonstrates through extensive experiments that SOL enables reliable rank estimation across diverse domains (vision, medical imaging, aesthetics, NLP) under various noise types (Gaussian, Laplacian, Uniform, Skewed) and levels.

4. Experimental Results

The authors evaluated SOL on five benchmarks: MORPH II and CLAP2015 (facial age), AADB (aesthetic scores), RSNA (bone age), and WMT2020 (textual regression).

• Performance: SOL consistently outperformed state-of-the-art noise-robust classification methods (e.g., SPR, ACL), regression methods (e.g., ROR-CE, C-Mixup), and existing order learning methods (e.g., GOL, MWR).
  • On MORPH II, SOL achieved the lowest Mean Absolute Error (MAE) and highest Cumulative Score (CS) across all noise types. For instance, under Gaussian noise ($\kappa=0.4$), SOL achieved an MAE of 2.826 compared to 2.861 for the next best method (GOL).
  • On AADB, SOL achieved the best performance in all settings, outperforming the second-best method by 2.5% in MAE at high noise levels.
  • On RSNA, SOL yielded the best results with large margins, demonstrating robustness in medical assessment where error-free annotations are costly.
  • On WMT2020 (real-world noisy data), SOL achieved a Pearson correlation of 0.680, outperforming the previous state-of-the-art by 2.0 points.
• Ablation Studies: Experiments confirmed that both the discriminative loss and the stochastic order loss are necessary; using either alone resulted in degraded performance.
• Efficiency: While SOL introduces additional computational steps for centroid updates and outlier detection, it remains practical. It also demonstrated lower GPU memory consumption compared to methods like GOL due to its on-the-fly probability computation.

5. Significance and Claims

The paper claims that the significance of SOL lies in its ability to handle the structural uncertainty inherent in ordinal data, which standard noise-robust methods fail to address. By treating the instance-rank relationship as probabilistic rather than fixed, SOL avoids the pitfalls of making large estimation errors common in noisy rank estimation.

The authors emphasize that SOL is not merely an extension of order learning with added robustness mechanisms but a fundamental shift in how noisy ordinal labels are modeled. The framework's ability to perform well on both synthetic noise and real-world noisy annotations (like human aesthetic scores and medical assessments) suggests its generality.

Limitations and Modesty:
The authors modestly note several limitations:

• The method relies on a fixed stochastic noise distribution, though it shows robustness to various types.
• The outlier detection and relabeling module is a practical enhancement rather than a theoretical necessity, and its efficacy depends on the quality of the learned embedding.
• The approach requires several hyperparameters ($\sigma_{test}$, $T$, $\tau$, $\beta$), and fully automatic selection is left for future work.
• Regarding facial datasets, the authors acknowledge that inherent imbalances may lead to gender or racial bias, recommending the algorithm be used for research purposes until such biases are resolved.