Neyman-Pearson multiclass classification under label noise via empirical likelihood

1. Problem Statement

The paper addresses the Neyman-Pearson Multiclass Classification (NPMC) problem in the presence of label noise.

• The NPMC Framework: Unlike standard classification which minimizes overall error, NPMC seeks a classifier $\phi$ that minimizes a weighted misclassification risk while imposing strict upper bounds ($\alpha_k$) on the error rates for specific classes $k \in S$. This is critical in high-stakes domains (e.g., medical diagnosis) where false negatives for certain classes are catastrophic.
• The Challenge: Existing NPMC methods assume training labels are clean. In reality, labels are often corrupted by measurement errors, annotator inconsistencies, or adversarial noise.
• The Gap: Ignoring label noise in NPMC leads to violated safety constraints (e.g., the actual error rate exceeds the target $\alpha_k$) or overly conservative classifiers with inflated Type II errors. Furthermore, existing noise-robust methods often require prior knowledge of the noise transition matrix (the probability of a true label being mislabeled as another), which is rarely available in practice.
• Goal: Develop a method to learn a classifier from noisy labels that satisfies the NPMC error constraints with respect to the unobserved true labels, without requiring prior knowledge of the noise mechanism.

2. Methodology

The authors propose a novel framework combining Empirical Likelihood (EL) and Density Ratio Modeling (DRM) to recover the necessary clean-label statistics from noisy data.

A. Problem Setup & Assumptions

• Instance-Independent Noise: The paper assumes the noise is independent of the features $X$ given the true label $Y$ (i.e., $P(\tilde{Y}|X, Y) = P(\tilde{Y}|Y)$). This is a standard assumption where the confusion matrix is constant across the feature space.
• Latent Variables: The true labels $Y$ are unobserved; only noisy labels $\tilde{Y}$ are available.

B. Density Ratio Model (DRM) & Exponential Tilting

The core of the method models the relationship between the true class-conditional distributions $P_k$ and the noisy distributions $\tilde{P}_l$ using an Exponential Tilting relationship.

• The posterior probabilities of the true labels are modeled via a multinomial logistic regression form:
  $$\pi_k(x) = P(Y=k|X=x) \propto \exp(\gamma_k + \langle \beta_k, g(x) \rangle)$$
• This implies a density ratio between classes: $dP_k/dP_0 = \exp(\gamma_k + \langle \beta_k, g(x) \rangle)$.
• Under the noise assumption, the observed noisy distribution $\tilde{P}_l$ is a mixture of the true distributions. The authors derive that the density of the noisy data relative to a base distribution can also be expressed via a parametric form involving the noise transition matrix $T^*$ and the true parameters.

C. Empirical Likelihood (EL) Estimation

Instead of assuming a parametric form for the base distribution $P_0$ (which would be restrictive), the authors use Empirical Likelihood to estimate the parameters non-parametrically.

• They construct a profile log-empirical likelihood function based on the observed noisy data.
• The parameters to be estimated are the true class proportions ($w^*$), the noise transition matrix ($T^*$), and the exponential tilting parameters ($\gamma, \beta$).
• Identifiability: The paper rigorously proves that under mild conditions (distinct feature coefficients, rich feature space, and full-rank confusion matrix), the parameters are strictly identifiable, resolving the ambiguity typically found in mixture models.

D. Optimization via EM Algorithm

Since the true labels are latent, the maximization of the profile EL is non-trivial. The authors develop an Expectation-Maximization (EM) algorithm:

1. E-step: Compute the posterior probability of the true label $Y_i=k$ given the noisy label $\tilde{Y}_i$ and current parameter estimates.
2. M-step: Update the parameters ($w, T, \gamma, \beta$) by maximizing the expected complete-data log-likelihood. This involves updating the transition matrix and solving a weighted multinomial logistic regression for the tilting parameters.
3. Convergence: The algorithm is proven to monotonically increase the profile log-likelihood.

E. Classifier Construction

Once the parameters are estimated, the method recovers:

1. The true class proportions $\hat{w}_k$.
2. The true posterior probabilities $\hat{\pi}_k(x)$.
   These are then plugged into the existing NPMC-CX solver (Tian & Feng, 2025) to compute the optimal Lagrange multipliers and the final error-controlled classifier.

3. Key Contributions

1. First NPMC Method for Noisy Labels: This is the first work to extend the NPMC framework to handle label noise in the multiclass setting without requiring the noise transition matrix as input.
2. Theoretical Guarantees:
   • Consistency & Normality: The proposed Maximum Empirical Likelihood Estimators (MELE) for the noise parameters and true posteriors are proven to be consistent and asymptotically normal with optimal convergence rates ($O(n^{-1/2})$).
   • Oracle Inequalities: The resulting classifier satisfies NP oracle inequalities. Specifically, the class-specific error rates converge to the target levels $\alpha_k$ asymptotically, matching the performance of an oracle classifier trained on clean data.
3. No Prior Knowledge Required: Unlike previous approaches (e.g., Yao et al., 2023) that require bounds or exact values of the noise matrix, this method learns the noise structure directly from the data.
4. Unified Framework: The approach naturally handles both binary and general multiclass classification.

4. Experimental Results

The authors conducted extensive simulations and real-data experiments.

• Simulations:

  • Binary Case: Compared against "Vanilla" (ignoring noise) and "NPC" (noise-adjusted umbrella algorithm requiring bounds). The proposed method achieved Type I error rates close to the target $\alpha$ with significantly lower Type II error (higher power) than the conservative Vanilla and NPC methods. It performed nearly as well as the "Oracle" (which knows the true noise matrix).
  • Multiclass Case: Tested on independent, dependent, and unequal covariance Gaussian data. The method maintained error control close to the target levels as sample size increased, whereas the Vanilla method became increasingly conservative (violating the objective function minimization) or failed to control errors.
  • Robustness: The method remained effective even when the Density Ratio Model was slightly misspecified (e.g., non-Gaussian data), outperforming baselines significantly.

• Real Data:

  • Applied to the Landsat Satellite and Dry Bean datasets.
  • Results confirmed that the method controls error rates close to the target levels while minimizing the overall risk, closely mimicking the performance of classifiers trained on clean labels.

5. Significance

This paper provides a critical solution for safety-critical machine learning. In domains like healthcare or finance, where specific error types must be strictly bounded, training on noisy data can lead to dangerous violations of safety constraints.

• Practical Impact: It allows practitioners to use NPMC frameworks on real-world datasets (which are inherently noisy) without needing to manually estimate or bound the noise transition matrix.
• Theoretical Advancement: It bridges the gap between density ratio modeling, empirical likelihood, and constrained classification, providing rigorous statistical guarantees for a problem previously considered intractable without strong prior assumptions.
• Future Directions: The authors suggest extending the framework to instance-dependent noise (where noise depends on $X$) and integrating deep neural networks for feature extraction.