Multi-Label Structure Learning with Ising Model Selection

André R. Gonçalves, Fernando J. Von Zuben, Arindam BanerjeeIJCAI 2015

Introduction

In multi-label classification (MLC), instances are associated with multiple labels simultaneously. For example, a news article might be tagged with both "Politics" and "Economics." A common baseline approach, Binary Relevance, treats each label as an independent classification task. However, this ignores the inherent dependencies between labels—knowing an image contains "trees" significantly increases the probability of it being a "landscape" and decreases the likelihood of it being "underwater."

This paper introduces I-MTSL (Ising Multi-task Structure Learning), a framework designed to capture these complex dependencies. By integrating Ising model structure learning with a signed multi-task learning approach, I-MTSL models both positive and negative relationships between labels, resulting in more accurate and robust predictions across diverse domains.

The I-MTSL Framework

The I-MTSL algorithm proceeds in two main stages:

1. Label Dependence Estimation

The first stage treats labels as binary variables within an Ising Markov Random Field (I-MRF). To identify the structure of this field—essentially determining which labels interact—the authors employ $\ell_1$-regularized logistic regression. For each label, the model attempts to predict its presence using all other labels as features. The "neighborhood" of a label is defined by the other labels that receive non-zero coefficients. To ensure the robustness of these connections, Stability Selection is applied: the process is repeated over multiple data sub-samples, and only connections that appear consistently (e.g., in 80% of trials) are retained.

2. Task Parameter Estimation

The identified label dependency structure is then incorporated into a Multi-Task Learning (MTL) framework. A key contribution is the use of a Signed Laplacian matrix. Unlike standard Laplacians that only encourage similarity between related tasks, the signed version accounts for negative correlations. If two labels are negatively related, the model encourages their classifier weights to diverge, effectively pushing them in opposite directions. This entire process is formulated as a convex optimization problem, solved efficiently using an accelerated proximal gradient method.

Experimental Evaluation

The authors evaluated I-MTSL on eight benchmark datasets across diverse domains, including music (Emotions, CAL500), images (Scene), biology (Yeast, Genbase), audio (Birds), and text (Enron, Medical). These datasets vary in scale, with label counts ranging from 6 to 174. I-MTSL was compared against five baselines, including standard Binary Relevance (BR), Classifier Chains (CC), and state-of-the-art MTL algorithms like CMTL and Trace.

Results and Interpretability

Experimental results demonstrate that I-MTSL is a superior "all-rounder." While specific baselines might excel in a single metric like Recall, I-MTSL consistently provides the most balanced performance across Accuracy and F1-score. Using a ranking metric based on Discounted Cumulative Gain, I-MTSL achieved the highest average relative performance (1.00) for both Accuracy and F1-score compared to competitors.

Radar charts comparing I-MTSL (black bars) against baselines across six metrics on various datasets. I-MTSL consistently shows the most balanced and highest overall performance.

Beyond predictive performance, I-MTSL offers significant interpretability. The learned dependency graphs provide a visual map of label relationships within a specific domain. The resulting sparse matrices reveal "communities" of labels, such as clusters of related genes or medical symptoms, and explicitly highlight negative correlations that are often ignored by other methods.

Learned label dependency structures for the Yeast, Enron, Medical, and Genbase datasets. Black squares indicate positive correlations, while grey squares represent negative correlations.

Conclusion

I-MTSL effectively bridges the gap between complex graphical models and efficient multi-task learning. By explicitly modeling both positive and negative label dependencies through Ising model selection and a signed Laplacian, the framework achieves state-of-the-art performance while maintaining interpretability. Future work may explore higher-order interactions and joint learning of the structure and classifier parameters.

Summary updated

BibTeX
@inproceedings{goncalves2015multi,
  author = {André R. Gonçalves and Fernando J. Von Zuben and Arindam Banerjee},
  title = {{Multi-Label Structure Learning with Ising Model Selection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure