@inproceedings{beygelzimer2014conditional,
author = {Beygelzimer, Alina and Langford, John and Lifshits, Yuri and Sorkin, Gregory and Strehl, Alex},
title = {Conditional Probability Tree Estimation Analysis and Algorithms},
booktitle = {Twenty-Fifth Conference on Uncertainty in Artificial Intelligence},
year = {2014},
month = {August},
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.},
url = {http://approjects.co.za/?big=en-us/research/publication/conditional-probability-tree-estimation-analysis-and-algorithms/},
note = {See related paper from June 2009},
}