Discrete Binary Coding based Label Distribution Learning

Ke Wang, Xin Geng

Introduction

In modern machine learning, the traditional paradigms of Single-Label Learning (SLL) and Multi-Label Learning (MLL) often fail to capture the inherent ambiguity of real-world data. Label Distribution Learning (LDL) addresses this by assigning a probability distribution across all possible labels, representing the "description degree" of each. While LDL provides a more nuanced representation, it suffers from significant scalability issues. Existing algorithms are often computationally prohibitive for large datasets, primarily due to the reliance on high-dimensional feature spaces and slow $k$-Nearest Neighbor (k-NN) searches.

To overcome these challenges, this research introduces a scalable framework: Discrete Binary Coding based Label Distribution Learning (DBC-LDL). By transforming high-dimensional features into compact binary codes that preserve semantic label similarities, the proposed method achieves state-of-the-art accuracy with massive speedups—up to 657x faster than traditional methods on large-scale datasets.

Methodology: Scalable Hashing for LDL

The core innovation of DBC-LDL lies in its use of supervised binary coding, or hashing, to map instances into a low-dimensional Hamming space.

Supervised Binary Coding

Unlike standard unsupervised hashing, which only considers feature distributions, DBC-LDL integrates label distribution information directly into the coding process. The framework utilizes Adjusted Cosine Similarity (ACS) to quantify the semantic similarity between instances based on their label distributions. This ensures that instances with similar label profiles are mapped to similar binary codes.

Sequential Optimization and Convergence

To avoid the memory constraints associated with large similarity matrices, the authors employ a sequential learning strategy. This approach learns the binary code bit-by-bit, with each subsequent bit correcting the errors of the previous ones. This keeps training time linear relative to the number of instances ($O(n)$).

Convergence of the objective function value over iterations on the Ren-CECps dataset.

As shown in the convergence analysis, the objective function value decreases rapidly and stabilizes within a few iterations, demonstrating the efficiency of the optimization process.

Efficient Label Prediction

For prediction, a new instance is converted into its binary representation. An Approximate Nearest Neighbor (ANN) search is then performed in the Hamming space. The use of XOR operations and bit-counting at the hardware level makes this search nearly instantaneous compared to Euclidean distance calculations in real-valued spaces. A further optimization, BCTable, uses a hash table to store pre-calculated mean distributions for each code, potentially eliminating the search phase entirely during testing.

Experimental Evaluation

The researchers evaluated DBC-LDL and its variants on five diverse benchmark datasets: s-BU_3DFE (facial expressions), COPM (movie opinions), Twitter_LDL (sentiment analysis), Ren-CECps (text emotion), and MORPH (age estimation).

Performance and Speed

The experimental results demonstrate that DBC-LDL consistently outperforms or matches state-of-the-art LDL algorithms in terms of accuracy while providing orders-of-magnitude improvements in speed.

Performance comparison of DBC-LDL and BC-LDL against state-of-the-art methods across five benchmark datasets.

Key findings from the results table include:

  • Accuracy: DBC-LDL achieved the best performance on several datasets, including s-BU_3DFE and Ren-CECps, and remained highly competitive on others.
  • Speedup: On the MORPH dataset, DBC-LDL was over 12 times faster than the BFGS-LDL baseline. The BCTable variant achieved a staggering 333.7x speedup. On the Ren-CECps dataset, the speedup reached 657.7x compared to the AA-kNN baseline.
  • Compactness: Performance typically plateaus at a code length of 128 bits, indicating that very compact binary representations are sufficient for complex LDL tasks.

Discussion and Future Directions

The success of DBC-LDL stems from its semantic-aware hashing. By forcing the Hamming space to reflect label similarities, the model creates a semantically meaningful map of the data. Furthermore, the authors found that relaxing strict orthogonality constraints—common in other hashing methods—actually improved performance for real-world LDL tasks.

Limitations

Despite its strengths, the method shows sensitivity to small datasets; increasing code length on limited data can lead to overfitting. Additionally, performance remains dependent on the quality of initial feature extraction (e.g., VGGNet features).

Conclusion

DBC-LDL represents a significant step forward in making Label Distribution Learning practical for large-scale applications. By leveraging the efficiency of binary coding and Hamming space searches, it resolves the scalability bottleneck without sacrificing predictive accuracy. Future work may involve integrating deep learning directly into the binary coding process to further enhance feature representation and accuracy.

Summary updated

Abstract

Label Distribution Learning (LDL) is a general learning paradigm in machine learning, which includes both single-label learning (SLL) and multi-label learning (MLL) as its special cases. Recently, many LDL algorithms have been proposed to handle different application tasks such as facial age estimation, head pose estimation and visual sentiment distributions prediction. However, the training time complexity of most existing LDL algorithms is too high, which makes them unapplicable to large-scale LDL. In this paper, we propose a novel LDL method to address this issue, termed Discrete Binary Coding based Label Distribution Learning (DBC-LDL). Specifically, we design an efficiently discrete coding framework to learn binary codes for instances. Furthermore, both the pair-wise semantic similarities and the original label distributions are integrated into this framework to learn highly discriminative binary codes. In addition, a fast approximate nearest neighbor (ANN) search strategy is utilized to predict label distributions for testing instances. Experimental results on five real-world datasets demonstrate its superior performance over several state-of-the-art LDL methods with the lower time cost.
BibTeX
@inproceedings{wang2019discrete,
  author = {Ke Wang and Xin Geng},
  title = {{Discrete Binary Coding based Label Distribution Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/518},
}
Figure