# Conditional Probability Tree Estimation Analysis and Algorithms

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2014.

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

- [On Missing Labels, Long-tails and Propensities in Extreme Multi-label Classification](https://mlsanity.com/paper/2207.13186/) (2022)
- [A Reduction to Binary Approach for Debiasing Multiclass Datasets](https://mlsanity.com/paper/2205.15860/) (2022)
- [Propensity-scored Probabilistic Label Trees](https://mlsanity.com/paper/2110.10803/) (2021)
- [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)
- [Generalized test utilities for long-tail performance in extreme multi-label classification](https://mlsanity.com/paper/2311.05081/) (2023)
- [Set-valued prediction in hierarchical classification with constrained representation complexity](https://mlsanity.com/paper/2203.06676/) (2022)
- [Conformal Prediction in Hierarchical Classification with Constrained Representation Complexity](https://mlsanity.com/paper/2501.19038/) (2025)
- [Multilingual hierarchical classification of job advertisements for job vacancy statistics](https://mlsanity.com/paper/2411.03779/) (2024)
- [Beyond Softmax: A Natural Parameterization for Categorical Random Variables](https://mlsanity.com/paper/2509.24728/) (2025)
- [Beyond Flat Unknown Labels in Open-World Object Detection](https://mlsanity.com/paper/2510.09173/) (2025)

## Abstract (arXiv)

We consider the problem of estimating the conditional probability of a label in time O(log n), where n is the number of possible labels. We analyze a natural reduction of this problem to a set of binary regression problems organized in a tree structure, proving a regret bound that scales with the depth of the tree. Motivated by this analysis, we propose the first online algorithm which provably constructs a logarithmic depth tree on the set of labels to solve this problem. We test the algorithm empirically, showing that it works succesfully on a dataset with roughly 106 labels.