# Probabilistic Label Trees for Extreme Multi-label Classification

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2020.

## Built on by (most cited first, 13 of 13)

- [Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification](https://mlsanity.com/paper/2110.00685/) (2021)
- [Extreme Multi-label Learning for Semantic Matching in Product Search](https://mlsanity.com/paper/2106.12657/) (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)
- [Generalized test utilities for long-tail performance in extreme multi-label classification](https://mlsanity.com/paper/2311.05081/) (2023)
- [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)
- [Labels in Extremes: How Well Calibrated are Extreme Multi-label Classifiers?](https://mlsanity.com/paper/2411.04276/) (2024)
- [Enterprise-Scale Search: Accelerating Inference for Sparse Extreme Multi-Label Ranking Trees](https://mlsanity.com/paper/2106.02697/) (2021)
- [Multilingual hierarchical classification of job advertisements for job vacancy statistics](https://mlsanity.com/paper/2411.03779/) (2024)
- [AGNOMIN -- Architecture Agnostic Multi-Label Function Name Prediction](https://mlsanity.com/paper/2509.25514/) (2025)
- [Exploring space efficiency in a tree-based linear model for extreme multi-label classification](https://mlsanity.com/paper/2410.09554/) (2024)

## Abstract (arXiv)

Extreme multi-label classification (XMLC) is a learning task of tagging instances with a small subset of relevant labels chosen from an extremely large pool of possible labels. Problems of this scale can be efficiently handled by organizing labels as a tree, like in hierarchical softmax used for multi-class problems. In this paper, we thoroughly investigate probabilistic label trees (PLTs) which can be treated as a generalization of hierarchical softmax for multi-label problems. We first introduce the PLT model and discuss training and inference procedures and their computational costs. Next, we prove the consistency of PLTs for a wide spectrum of performance metrics. To this end, we upperbound their regret by a function of surrogate-loss regrets of node classifiers. Furthermore, we consider a problem of training PLTs in a fully online setting, without any prior knowledge of training instances, their features, or labels. In this case, both node classifiers and the tree structure are trained online. We prove a specific equivalence between the fully online algorithm and an algorithm with a tree structure given in advance. Finally, we discuss several implementations of PLTs and introduce a new one, napkinXC, which we empirically evaluate and compare with state-of-the-art algorithms.