Conditional Probability Tree Estimation Analysis and Algorithms

2014/08/09 by Alina Beygelzimer, John Langford, Beygelzimer, Alina +9 · 4 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1408.2031

Appears in Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI2009)

arxiv created 2014/08/09 · openalex publication_date 2014/08/09 · arxiv updated 2014/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02

Abstract

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.

Citations

• VERIFICATION OF FORECASTS EXPRESSED IN TERMS OF PROBABILITY

Cited by

• TARO: Toward Semantically Rich Open-World Object Detection
• Beyond Softmax: A Natural Parameterization for Categorical Random Variables
• Context models on sequences of covers
• Simultaneous Learning of Trees and Representations for Extreme Classification and Density Estimation
• On the computational complexity of the probabilistic label tree algorithms

Related

• Conditional Probability Tree Estimation Analysis and Algorithms
• On the computational complexity of the probabilistic label tree algorithms
• Treeffuser: Probabilistic Predictions via Conditional Diffusions with Gradient-Boosted Trees
• Efficient distributional regression trees learning algorithms for calibrated non-parametric probabilistic forecasts
• Odds-On Trees