No Regularization Is Needed: Efficient and Effective Incomplete Label Distribution Learning

Xiang Li, Songcan ChenIJCAI 2024 · OpenReview

Abstract

In reality, it is laborious to obtain complete label degrees, giving birth to Incomplete Label Distribution Learning (InLDL), where some degrees are missing. Existing InLDL methods often assume that degrees are uniformly random missing. However, it is often not the case in practice, which arises the first issue. Besides, they often adopt explicit regularization to compensate the incompleteness, leading to burdensome parameter tuning and extra computation, causing the second issue. To address the first issue, we adopt a more practical setting, i.e., small degrees are more prone to be missing, since large degrees are likely to catch more attention. To tackle the second issue, we argue that label distribution itself already contains abundant knowledge, such as label correlation and ranking order, thus it may have provided enough prior for learning. It is precisely because existing methods overlook such a prior that leads to the forced adoption of explicit regularization. By directly utilizing the label degrees prior, we design a properly weighted objective function, exempting the need from explicit regularization. Moreover, we provide rigorous theoretical analysis, revealing in principle that the weighting plays an implicit regularization role. To sum up, our method has four advantages, it is 1) model selection free; 2) with closed-form solution (sub-problem) and easy-to-implement (a few lines of codes); 3) with linear computational complexity in the number of samples, thus scalable to large datasets; 4) competitive with state-of-the-arts in both random and non-random missing scenarios.

Introduction

Label Distribution Learning (LDL) is a paradigm where, instead of a single "hard" label (e.g., "dog"), a sample is assigned a distribution across multiple labels (e.g., 0.7 dog, 0.2 cat, 0.1 bird). This is effective for handling ambiguity, but in real-world scenarios, obtaining a complete distribution is expensive. This leads to Incomplete LDL (InLDL), where some values in the distribution are missing.

Existing InLDL research often suffers from two major flaws. First, most models assume labels are missing "uniformly at random." In reality, labels with small degrees (like a tiny "house" in the background of a landscape) are much more likely to be missed by annotators than dominant features like "sky."

An example of incomplete label distribution where small degrees like 'house' and 'wire pole' are missing, reflecting a realistic non-random missing scenario.

Second, to compensate for missing data, current methods rely on explicit regularization terms (such as trace norms for low-rank constraints). This makes the models computationally heavy and requires tedious hyperparameter tuning.

The WInLDL Method

The authors propose WInLDL (Weighted Incomplete LDL), challenging the status quo by showing that explicit regularization is unnecessary. The core idea is to leverage the prior knowledge already present in the label distribution through a weighted objective function.

Weighting and Optimization

WInLDL utilizes a weighting matrix $Q$ that assigns larger weights to smaller observed label degrees. This forces the model to prioritize the "hard-to-see" labels that are typically underfitted. The optimization is handled via the Alternating Direction Method of Multipliers (ADMM), resulting in closed-form solutions for sub-problems. This makes the algorithm extremely easy to implement, often requiring just a few lines of code.

Implicit Regularization

A key theoretical contribution of this work is the proof that the weighting scheme acts as implicit regularization. By utilizing the label degrees prior, the model achieves a generalization bound without the need for extra penalty terms, making it "model selection free."

Experimental Evaluation

The study evaluates WInLDL on 10 real-world datasets spanning biology (Gene), facial expressions (SBU3DFE, RAF_ML), and natural scenes (Flickr). These datasets vary in size and label count, providing a robust benchmark for scalability.

Efficiency and Speed

Because WInLDL avoids complex regularization terms, its computational complexity is linear $O(N)$ with respect to the number of samples. In benchmarks, WInLDL completed training across 10 datasets in just 10.95 seconds, while competing state-of-the-art methods took between 500 and 3,500 seconds.

Comparison of total run time (seconds) across 10 datasets, highlighting WInLDL's significant speed advantage over existing methods.

Performance Accuracy

Despite its simplicity, WInLDL ranked 1st on 8 out of 10 datasets in non-random missing scenarios. It outperformed existing methods in both traditional "randomly missing" and more realistic "non-randomly missing" contexts, proving its versatility and robustness.

Conclusion

WInLDL demonstrates that the label distribution itself contains sufficient information for learning, provided it is utilized correctly. By replacing explicit regularization with a weighted objective, the authors provide a method that is both more efficient and more accurate in realistic settings. Future work may involve extending this approach to non-linear models using deep learning architectures.

Summary updated

Abstract

In reality, it is laborious to obtain complete label degrees, giving birth to Incomplete Label Distribution Learning (InLDL), where some degrees are missing. Existing InLDL methods often assume that degrees are uniformly random missing. However, it is often not the case in practice, which arises the first issue. Besides, they often adopt explicit regularization to compensate the incompleteness, leading to burdensome parameter tuning and extra computation, causing the second issue. To address the first issue, we adopt a more practical setting, i.e., small degrees are more prone to be missing, since large degrees are likely to catch more attention. To tackle the second issue, we argue that label distribution itself already contains abundant knowledge, such as label correlation and ranking order, thus it may have provided enough prior for learning. It is precisely because existing methods overlook such a prior that leads to the forced adoption of explicit regularization. By directly utilizing the label degrees prior, we design a properly weighted objective function, exempting the need from explicit regularization. Moreover, we provide rigorous theoretical analysis, revealing in principle that the weighting plays an implicit regularization role. To sum up, our method has four advantages, it is 1) model selection free; 2) with closed-form solution (sub-problem) and easy-to-implement (a few lines of codes); 3) with linear computational complexity in the number of samples, thus scalable to large datasets; 4) competitive with state-of-the-arts in both random and non-random missing scenarios.
BibTeX
@inproceedings{li2024no,
  author = {Xiang Li and Songcan Chen},
  title = {{No Regularization Is Needed: Efficient and Effective Incomplete Label Distribution Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=rVWmQAY65l},
}
Figure