Multilabel Classification by Hierarchical Partitioning and Data-dependent Grouping

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

Abstract

In modern multilabel classification problems, each data instance belongs to a small number of classes from a large set of classes. In other words, these problems involve learning very sparse binary label vectors. Moreover, in 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 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 up the large label space and create 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 competitive accuracy with significantly lower computational costs.

Introduction

Extreme Multilabel Classification (XMLC) presents a significant challenge in modern machine learning. Applications such as tagging Wikipedia articles or product recommendation involve label spaces ($d$) that can reach millions, while any single instance typically only belongs to a very small subset ($k$) of these labels. This extreme sparsity is a defining characteristic of the problem.

Standard One-versus-All (OvA) approaches, which train a separate classifier for every label, become computationally infeasible at this scale. While tree-based and embedding-based methods have been proposed, they often struggle with high training latency or expensive "lifting" steps to recover labels from compressed representations. This paper introduces He-NMFGT, a framework that leverages hierarchical partitioning and data-driven group testing to achieve high accuracy with logarithmic prediction time and efficient training.

Methodology: He-NMFGT

The core of the proposed approach is Multilabel Group Testing (MLGT). Instead of training $d$ classifiers, the system trains $m$ classifiers ($m \ll d$) on groups of labels. The framework introduces three primary innovations to optimize this process.

Data-dependent Grouping (NMF-GT)

Unlike previous group testing methods that relied on random groupings, NMF-GT uses Symmetric Nonnegative Matrix Factorization (symNMF) on the label correlation matrix. By grouping labels that frequently co-occur in the training data, the individual binary classifiers become more accurate, as they capture meaningful semantic clusters.

Hierarchical Partitioning

For datasets with millions of labels, performing NMF on the full correlation matrix is computationally prohibitive. The authors employ graph partitioning techniques to decompose the massive label space into smaller, independent sub-problems. These sub-problems are then solved in parallel using the grouping approach.

Sparsity patterns of label correlation matrices, illustrating the hierarchical structure exploited for partitioning.

Training and Fast Decoding

The training phase involves constructing a group testing matrix $A$ and training $m$ binary classifiers. For prediction, the system utilizes the SAFFRON framework from coding theory to achieve $O(k \log d)$ prediction time, identifying relevant labels almost instantaneously.

Algorithms for MLGT training and prediction, showing the transformation of labels into a lower-dimensional group space.

Experimental Results

The researchers evaluated He-NMFGT on a variety of benchmarks, ranging from medium-scale (Mediamill, Bibtex) to extreme-scale (WikiLSHTC with 325k labels, Amazon-670K).

Efficiency and Speed

He-NMFGT demonstrated significant advantages in prediction latency. On the WikiLSHTC dataset, it achieved a prediction time of 0.8ms per instance, outperforming SLEEC (5.7ms) and Parabel (1.2ms). Training efficiency was also competitive, often reaching the accuracy of OvA methods using only 15-20% of the training data.

Accuracy

On large-scale datasets like Wiki10 and Amazon-670K, the method achieved Precision@k scores that were competitive with or superior to state-of-the-art methods like Parabel and PfastreXML. The data-dependent grouping proved particularly effective in maintaining high precision while reducing the number of required classifiers.

Conclusion and Future Work

He-NMFGT offers a scalable solution for XMLC by treating classification as a sparse signal recovery problem. By exploiting label correlations through NMF and managing scale via hierarchical partitioning, it bypasses the linear complexity of traditional methods.

Future work includes optimizing the symNMF process, which remains computationally intensive, and refining partition boundaries to better capture cross-partition correlations. Additionally, migrating the implementation from MATLAB to C++ could further enhance real-time performance for web-scale applications.

Summary updated

Abstract

In modern multilabel classification problems, each data instance belongs to a small number of classes from a large set of classes. In other words, these problems involve learning very sparse binary label vectors. Moreover, in 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 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 up the large label space and create 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 competitive 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