Conditional Probability Tree Estimation Analysis and Algorithms

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.

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

Cited by in corpus (10)

• Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms
• On Missing Labels, Long-tails and Propensities in Extreme Multi-label Classification
• Simultaneous Learning of Trees and Representations for Extreme Classification and Density Estimation
• Probabilistic Label Trees for Extreme Multi-label Classification
• Hierarchical Maximum Margin Learning for Multi-Class Classification
• Propensity-scored Probabilistic Label Trees
• On the computational complexity of the probabilistic label tree algorithms
• Context models on sequences of covers
• FALCON: Feature Driven Selective Classification for Energy-Efficient Image Recognition
• Data-dependent Generalization Bounds for Multi-class Classification