# Exploring space efficiency in a tree-based linear model for extreme multi-label classification

arXiv: https://arxiv.org/abs/2410.09554 · HTML: https://mlsanity.com/paper/2410.09554/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 17 references that are in the map.
- First posted on arXiv 12 Oct 2024.

## Builds on (most cited first, 6 of 6)

- [LexGLUE: A Benchmark Dataset for Legal Language Understanding in English](https://mlsanity.com/paper/2110.00976/) (2021)
- [DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification](https://mlsanity.com/paper/1609.02521/) (2016)
- [Bonsai -- Diverse and Shallow Trees for Extreme Multi-label Classification](https://mlsanity.com/paper/1904.08249/) (2019)
- [PECOS: Prediction for Enormous and Correlated Output Spaces](https://mlsanity.com/paper/2010.05878/) (2020)
- [Extreme Multi-label Learning for Semantic Matching in Product Search](https://mlsanity.com/paper/2106.12657/) (2021)
- [Probabilistic Label Trees for Extreme Multi-label Classification](https://mlsanity.com/paper/2009.11218/) (2020)

## Abstract (arXiv)

Extreme multi-label classification (XMC) aims to identify relevant subsets from numerous labels. Among the various approaches for XMC, tree-based linear models are effective due to their superior efficiency and simplicity. However, the space complexity of tree-based methods is not well-studied. Many past works assume that storing the model is not affordable and apply techniques such as pruning to save space, which may lead to performance loss. In this work, we conduct both theoretical and empirical analyses on the space to store a tree model under the assumption of sparse data, a condition frequently met in text data. We found that, some features may be unused when training binary classifiers in a tree method, resulting in zero values in the weight vectors. Hence, storing only non-zero elements can greatly save space. Our experimental results indicate that tree models can achieve up to a 95% reduction in storage space compared to the standard one-vs-rest method for multi-label text classification. Our research provides a simple procedure to estimate the size of a tree model before training any classifier in the tree nodes. Then, if the model size is already acceptable, this approach can help avoid modifying the model through weight pruning or other techniques.