Multi-Label Prediction via Sparse Infinite CCA

Piyush Rai, Hal Daumé IiiNeurIPS 2009 · OpenReview

Introduction

In many real-world machine learning scenarios, such as text categorization or protein function prediction, a single example can have multiple labels. Because these labels are rarely independent, treating each as a separate classification task ignores valuable correlation data. While classical Canonical Correlation Analysis (CCA) is often used to find a shared low-dimensional space between inputs and labels, it suffers from three major limitations:

  1. Model Selection: The number of correlation components ($K$) must be manually chosen, usually via expensive cross-validation.
  2. Lack of Sparsity: It assumes all features contribute to all components, making results difficult to interpret and prone to noise.
  3. Rigidity: As a non-probabilistic method, it cannot naturally handle missing data or incorporate unlabeled test data for semi-supervised learning.

This paper introduces a nonparametric, fully Bayesian version of CCA that automatically determines the number of latent correlation components and captures the underlying sparsity of the data.

Methodology: A Bayesian Approach to CCA

To overcome the limitations of classical CCA, the authors build upon a Probabilistic CCA framework, injecting two powerful Bayesian tools:

  • The Indian Buffet Process (IBP): This nonparametric prior models an "infinite" binary matrix. It allows the model to start with an unbounded number of potential latent features, letting the data dictate how many are actually needed. This effectively automates the selection of $K$.
  • Sparse Projections: To ensure interpretability and robustness, the projection matrix $W$ is decomposed into a Hadamard (element-wise) product of a binary matrix $B$ (drawn from the IBP) and a continuous Gaussian matrix $V$. This forces the model to select only a subset of features for each latent component.
Graphical model of the sparse infinite CCA

The authors propose two specific implementations for multi-label learning:

  • Model-1 (Fully Supervised): Learns the shared subspace using only labeled training data.
  • Model-2 (Semi-Supervised): Combines training and test data, treating the missing labels of the test set as latent variables to be imputed during inference.

Inference is performed using Gibbs sampling combined with Metropolis-Hastings steps to handle the expanding number of features.

Key Insights and Results

The model was evaluated on a synthetic dataset, as well as two real-world datasets from the UCI Repository: Yeast (biological data) and Scene (image data).

Automatic Complexity Control and Sparsity

On the synthetic dataset (which had exactly 4 ground-truth correlation components and 63% sparsity), classical CCA overfit by finding 8 significant components. The Infinite CCA correctly identified exactly 4 components, demonstrating its robustness against spurious correlations. Furthermore, while classical CCA produced dense matrices (achieving only ~25% sparsity even after thresholding), the proposed Bayesian model achieved ~60% exact sparsity, closely matching the ground truth.

Multi-Label Prediction Performance

The authors compared their models against standard SVMs (Full), PCA, and classical CCA. The semi-supervised approach (Model-2) consistently performed the best. By "seeing" the distribution of the test inputs during training, the model learned a more robust projection that generalized better to those specific test instances.

Performance comparison on Yeast and Scene datasets

As shown in the results, Model-2 achieved an accuracy of 0.6156 on the Yeast dataset, significantly outperforming classical CCA (0.5441) and the Full SVM (0.5583). On the Scene dataset, Model-2 reached an accuracy of 0.7664, again outperforming the baselines. Across nearly all metrics (F1-macro, F1-micro, and AUC), the Bayesian models (Model-1 and Model-2) demonstrated strong gains over traditional methods.

Limitations and Future Work

While the paper demonstrates clear performance improvements, there are a few areas for further exploration:

  • Computational Scaling: Gibbs sampling for inference can be computationally expensive as the number of features or samples grows. While Metropolis-Hastings is used for faster mixing, wall-clock times for massive datasets remain a challenge.
  • Task Scaling: Experiments were conducted on datasets with a relatively small number of labels (6 to 14). The authors hypothesize that the benefits of capturing label correlations will be even more significant as the number of tasks/labels increases.
  • Missing Inputs: The model is designed to handle missing labels ($Y$), but it could theoretically also handle missing input features ($X$), which warrants further experimental focus.

Summary updated

Abstract

Canonical Correlation Analysis (CCA) is a useful technique for modeling dependencies between two (or more) sets of variables. Building upon the recently suggested probabilistic interpretation of CCA, we propose a nonparametric, fully Bayesian framework that can automatically select the number of correlation components, and effectively capture the sparsity underlying the projections. In addition, given (partially) labeled data, our algorithm can also be used as a (semi)supervised dimensionality reduction technique, and can be applied to learn useful predictive features in the context of learning a set of related tasks. Experimental results demonstrate the efficacy of the proposed approach for both CCA as a stand-alone problem, and when applied to multi-label prediction.
BibTeX
@inproceedings{rai2009multi,
  author = {Piyush Rai and Hal Daumé III},
  title = {{Multi-Label Prediction via Sparse Infinite CCA}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=SyZh2DWu-H},
}
Figure