Multilabel Classification by Hierarchical Partitioning and Data-dependent Grouping

Shashanka Ubaru, Sanjeeb Dash, Arya Mazumdar, Oktay Günlük

In the world of machine learning, "Extreme Multilabel Classification" (XMC) is the ultimate needle-in-a-haystack problem. Imagine trying to tag a YouTube video or a Wikipedia article from a pool of millions of possible labels. You know only a handful of tags are correct, but checking every single one is computationally exhausting.

In their NeurIPS 2020 paper, researchers from IBM, UMass Amherst, and Cornell present a clever way to shrink this haystack. By combining hierarchical partitioning with data-dependent group testing, they’ve developed a framework that makes training faster and prediction nearly instantaneous.

The Challenge of Extreme Scale

Standard Multilabel Classification (MLC) is difficult primarily because of scale. If you have a million labels, a standard "One-versus-All" (OvA) approach requires training a million separate classifiers—a nightmare for both memory and time.

Previous attempts to solve this include:

  1. Tree-based methods: These break the label space into a hierarchy but can be expensive to train.
  2. Embedding methods: These project labels into a low-dimensional space, but recovering the original labels often requires complex, slow matrix inversions.
  3. Group Testing (MLGT): This involves grouping labels into random subsets. If an instance belongs to a group, you know it might have one of the labels in that group. While fast, random groups often lump unrelated labels together, making the classifiers "confused" and less accurate.

The authors set out to fix the "confusion" in group testing while maintaining its incredible speed.

Proposed Methods

The authors build upon the standard Multilabel Group Testing (MLGT) framework, introducing two main innovations to improve accuracy and handle extreme scale.

Algorithms for MLGT Training and Prediction

1. NMF-GT (Data-dependent Grouping)

Instead of picking groups at random, the authors use Symmetric Nonnegative Matrix Factorization (symNMF) on the label correlation matrix.

  • The Logic: If "Apple" and "iPhone" often appear together, they should probably be in the same group.
  • The Process: They decompose the label co-occurrence matrix to find underlying clusters. They then use these clusters to build a "Group Testing Matrix." This ensures that the binary classifiers are trained on meaningful, correlated sets of labels, which significantly boosts accuracy over random grouping.

2. He-NMFGT (Hierarchical Partitioning)

For "Extreme" datasets with hundreds of thousands of labels, running NMF on the whole matrix is too slow.

  • The Logic: Use a "divide and conquer" strategy.
  • The Process: They use matrix reordering techniques (specifically vertex separator partitioning) to find independent blocks of labels that don't interact much. They split the massive label space into smaller sub-problems, solve each using the NMF-GT approach in parallel, and then combine the results.
Partitioned Label Matrix

3. Fast Decoding

They leverage a bipartite graph-based algorithm called SAFFRON. This allows them to move from the compressed "group" space back to the original label space in $O(k \log d)$ time, where $d$ is the number of labels and $k$ is the number of active labels. This is a massive leap over linear-time decoders.

Key Insights and Results

The researchers evaluated their method on several benchmark datasets from the Extreme Classification Repository, ranging from small (Mediamill, 101 labels) to massive (Amazon-670K, ~670k labels).

  • Correlation is Key: The "Aha!" moment is that group testing doesn't have to be blind. By using NMF to bake label relationships into the group structure, you get the efficiency of compression without the noise of random assignments.
  • Logarithmic is the Goal: In high-throughput systems, linear time isn't good enough. Achieving $O(\log d)$ prediction latency is the "holy grail" for these applications.
  • Sparsity as a Strength: The method relies on the fact that label vectors are extremely sparse. By treating MLC as a compressed sensing problem, they turn a high-dimensional burden into a low-dimensional advantage.

The proposed He-NMFGT method proved to be highly efficient without sacrificing quality:

  • Speedup: On the WikiLSHTC dataset (325k labels), the prediction time per instance was just 0.8ms, compared to 5.7ms for embedding-based SLEEC and 1.2ms for tree-based Parabel.
  • Training Efficiency: Training on the same dataset took about 47 minutes, whereas the OvA method "Dismec" takes a staggering 750 hours.
  • Accuracy: The method achieved competitive (and sometimes superior) accuracy compared to popular tools like PfastreXML and Parabel, particularly on the Precision@1 metric.

Limitations and Future Work

While highly effective, the current implementation is in MATLAB. Moving to C++ or CUDA would likely unlock even greater performance gains for real-time production environments. Additionally, performance depends on choosing the right number of groups and partitions, requiring some manual hyperparameter tuning. Finally, the hierarchical approach assumes the label space can be cleanly partitioned; datasets with extremely dense label correlations across the entire space might render the partitioning less effective.

Summary updated

Abstract

In modern multilabel classification problems, each data instance belongs to a small number of classes among a large set of classes. In other words, these problems involve learning very sparse binary label vectors. Moreover, in the large-scale problems, the labels typically have certain (unknown) hierarchy. In this paper we exploit the sparsity of label vectors and the hierarchical structure to embed them in low-dimensional space using label groupings. Consequently, we solve the classification problem in a much lower dimensional space and then obtain labels in the original space using an appropriately defined lifting. Our method builds on the work of (Ubaru & Mazumdar, 2017), where the idea of group testing was also explored for multilabel classification. We first present a novel data-dependent grouping approach, where we use a group construction based on a low-rank Nonnegative Matrix Factorization (NMF) of the label matrix of training instances. The construction also allows us, using recent results, to develop a fast prediction algorithm that has a \emph{logarithmic runtime in the number of labels}. We then present a hierarchical partitioning approach that exploits the label hierarchy in large-scale problems to divide the large label space into smaller sub-problems, which can then be solved independently via the grouping approach. Numerical results on many benchmark datasets illustrate that, compared to other popular methods, our proposed methods achieve comparable accuracy with significantly lower computational costs.
BibTeX
@inproceedings{ubaru2020multilabel,
  author = {Shashanka Ubaru and Sanjeeb Dash and Arya Mazumdar and Oktay Günlük},
  title = {{Multilabel Classification by Hierarchical Partitioning and Data-dependent Grouping}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=IQKTg0_K-mM},
}
Figure