Semi-supervised Multi-label Learning by Constrained Non-negative Matrix Factorization

Yi Liu, Rong Jin, Liu YangAAAI 2006 · OpenReview

Abstract

We present a novel framework for multi-label learning that explicitly addresses the challenge arising from the large number of classes and a small size of training data. The key assumption behind this work is that two examples tend to have large overlap in their assigned class memberships if they share high similarity in their input patterns. We capitalize this assumption by first computing two sets of similarities, one based on the input patterns of examples, and the other based on the class memberships of the examples. We then search for the optimal assignment of class memberships to the unlabeled data that minimizes the difference between these two sets of similarities. The optimization problem is formulated as a constrained Non-negative Matrix Factorization (NMF) problem, and an algorithm is presented to efficiently find the solution. Compared to the existing approaches for multi-label learning, the proposed approach is advantageous in that it is able to explore both the unlabeled data and the correlation among different classes simultaneously. Experiments with text categorization show that our approach performs significantly better than several state-of-the-art classification techniques when the number of classes is large and the size of training data is small.

The Challenge of Multi-label Learning

In real-world applications such as news tagging or image annotation, items often belong to multiple categories simultaneously. This "multi-label learning" faces two significant hurdles:

  1. Data Sparsity: With hundreds of potential classes but limited labeled examples, many categories lack sufficient training data for traditional binary classifiers.
  2. Class Correlations: Standard methods often treat classes independently, ignoring the fact that certain categories (e.g., "Politics" and "Economics") are inherently related.

Methodology: Constrained NMF

The proposed framework, CNMF (Constrained Non-negative Matrix Factorization), addresses these issues by assuming that examples with similar input features should have similar label overlaps. The model optimizes a Label Confidence matrix ($T$) by minimizing the discrepancy between input pattern similarity ($A$) and class-based similarity ($TBT^T$), where $B$ represents inter-class correlations.

Unlike previous semi-supervised methods, CNMF incorporates constraints to ensure that for labeled data, the learned matrix $T$ matches the ground truth. It uses an iterative bound optimization algorithm to maintain non-negativity and ensure efficient convergence.

Experimental Results

The researchers evaluated CNMF against three baselines—Spectral Graph Transducer (SGT), Multi-label Informed Latent Semantic Indexing (MLSI), and SVM—using the ESTA dataset (a subset of ImageCLEF 2003).

Comprehensive performance comparison of CNMF against SGT, MLSI, and SVM across Precision, Recall, and F1 metrics for training sizes of 100 and 500 examples.

Key Findings

  • Superior Recall in "Cold Start" Scenarios: CNMF demonstrated a significant advantage when training data was most scarce (100 documents). As shown in the recall plots, CNMF consistently identifies more relevant labels than competing methods.
  • Effective Label Ranking: The F1-score for CNMF peaked when predicting 3 to 4 labels per document, aligning closely with the dataset's actual average of 4.5 labels. This suggests the model's ranking of potential labels is highly reliable.
Comparison of Recall Micro for 100 and 500 training examples, highlighting CNMF's consistent lead over baselines as the number of predicted labels increases.

Conclusion and Future Work

CNMF provides a robust solution for multi-label classification by simultaneously leveraging unlabeled data and inherent class correlations. While the model's performance depends on the quality of initial similarity matrices, its robustness to hyperparameters makes it a practical choice for sparse data environments. Future research may extend this framework to domains like bioinformatics for gene function prediction or automated image annotation.

Summary updated

Abstract

We present a novel framework for multi-label learning that explicitly addresses the challenge arising from the large number of classes and a small size of training data. The key assumption behind this work is that two examples tend to have large overlap in their assigned class memberships if they share high similarity in their input patterns. We capitalize this assumption by first computing two sets of similarities, one based on the input patterns of examples, and the other based on the class memberships of the examples. We then search for the optimal assignment of class memberships to the unlabeled data that minimizes the difference between these two sets of similarities. The optimization problem is formulated as a constrained Non-negative Matrix Factorization (NMF) problem, and an algorithm is presented to efficiently find the solution. Compared to the existing approaches for multi-label learning, the proposed approach is advantageous in that it is able to explore both the unlabeled data and the correlation among different classes simultaneously. Experiments with text categorization show that our approach performs significantly better than several state-of-the-art classification techniques when the number of classes is large and the size of training data is small.
BibTeX
@inproceedings{liu2006semi,
  author = {Yi Liu and Rong Jin and Liu Yang},
  title = {{Semi-supervised Multi-label Learning by Constrained Non-negative Matrix Factorization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=BkW4R1Z_-H},
}
Figure