# A no-regret generalization of hierarchical softmax to extreme multi-label classification

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

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2018.

## Built on by (most cited first, 30 of 52)

- [Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2110.00685/) (2021)
- [LightXML: Transformer with Dynamic Negative Sampling for High-Performance Extreme Multi-label Text Classification](https://mlsanity.com/paper/2101.03305/) (2021)
- [ECLARE: Extreme Classification with Label Graph Correlations](https://mlsanity.com/paper/2108.00261/) (2021)
- [DeepXML: A Deep Extreme Multi-Label Learning Framework Applied to Short Text Documents](https://mlsanity.com/paper/2111.06685/) (2021)
- [DECAF: Deep Extreme Classification with Label Features](https://mlsanity.com/paper/2108.00368/) (2021)
- [NGAME: Negative Mining-aware Mini-batching for Extreme Classification](https://mlsanity.com/paper/2207.04452/) (2022)
- [Extreme Multi-label Learning for Semantic Matching in Product Search](https://mlsanity.com/paper/2106.12657/) (2021)
- [Learning with Holographic Reduced Representations](https://mlsanity.com/paper/2109.02157/) (2021)
- [sigmoidF1: A Smooth F1 Score Surrogate Loss for Multilabel Classification](https://mlsanity.com/paper/2108.10566/) (2021)
- [Multi-Label Learning with Stronger Consistency Guarantees](https://mlsanity.com/paper/2407.13746/) (2024)
- [CascadeXML: Rethinking Transformers for End-to-end Multi-resolution Training in Extreme Multi-label Classification](https://mlsanity.com/paper/2211.00640/) (2022)
- [Decoding-based Regression](https://mlsanity.com/paper/2501.19383/) (2025)
- [Disentangling Sampling and Labeling Bias for Learning in Large-Output Spaces](https://mlsanity.com/paper/2105.05736/) (2021)
- [Top-k eXtreme Contextual Bandits with Arm Hierarchy](https://mlsanity.com/paper/2102.07800/) (2021)
- [Propensity-scored Probabilistic Label Trees](https://mlsanity.com/paper/2110.10803/) (2021)
- [Label Disentanglement in Partition-based Extreme Multilabel Classification](https://mlsanity.com/paper/2106.12751/) (2021)
- [PINA: Leveraging Side Information in eXtreme Multi-label Classification via Predicted Instance Neighborhood Aggregation](https://mlsanity.com/paper/2305.12349/) (2023)
- [SemSup-XC: Semantic Supervision for Zero and Few-shot Extreme Classification](https://mlsanity.com/paper/2301.11309/) (2023)
- [Towards Memory-Efficient Training for Extremely Large Output Spaces -- Learning with 500k Labels on a Single Commodity GPU](https://mlsanity.com/paper/2306.03725/) (2023)
- [Recent Advances in Hierarchical Multi-label Text Classification: A Survey](https://mlsanity.com/paper/2307.16265/) (2023)
- [Generalized test utilities for long-tail performance in extreme multi-label classification](https://mlsanity.com/paper/2311.05081/) (2023)
- [Keyword Extraction from Short Texts with a Text-To-Text Transfer Transformer](https://mlsanity.com/paper/2209.14008/) (2022)
- [Noise Contrastive Estimation-based Matching Framework for Low-Resource Security Attack Pattern Recognition](https://mlsanity.com/paper/2401.10337/) (2024)
- [Consistent algorithms for multi-label classification with macro-at-k metrics](https://mlsanity.com/paper/2401.16594/) (2024)
- [Prototype Memory for Large-scale Face Representation Learning](https://mlsanity.com/paper/2105.02103/) (2021)
- [Speeding-up One-vs-All Training for Extreme Classification via Smart Initialization](https://mlsanity.com/paper/2109.13122/) (2021)
- [Set-valued prediction in hierarchical classification with constrained representation complexity](https://mlsanity.com/paper/2203.06676/) (2022)
- [MatchXML: An Efficient Text-label Matching Framework for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2308.13139/) (2023)
- [Multi-modal Extreme Classification](https://mlsanity.com/paper/2309.04961/) (2023)
- [Learning label-label correlations in Extreme Multi-label Classification via Label Features](https://mlsanity.com/paper/2405.04545/) (2024)

## Abstract (arXiv)

Extreme multi-label classification (XMLC) is a problem of tagging an instance with a small subset of relevant labels chosen from an extremely large pool of possible labels. Large label spaces can be efficiently handled by organizing labels as a tree, like in the hierarchical softmax (HSM) approach commonly used for multi-class problems. In this paper, we investigate probabilistic label trees (PLTs) that have been recently devised for tackling XMLC problems. We show that PLTs are a no-regret multi-label generalization of HSM when precision@k is used as a model evaluation metric. Critically, we prove that pick-one-label heuristic - a reduction technique from multi-label to multi-class that is routinely used along with HSM - is not consistent in general. We also show that our implementation of PLTs, referred to as extremeText (XT), obtains significantly better results than HSM with the pick-one-label heuristic and XML-CNN, a deep network specifically designed for XMLC problems. Moreover, XT is competitive to many state-of-the-art approaches in terms of statistical performance, model size and prediction time which makes it amenable to deploy in an online system.