Conditional Probability Tree Estimation Analysis and Algorithms

Alina Beygelzimer, John Langford, Yury Lifshits, Gregory Sorkin, Alex Strehl
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:43-50, 2009.

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 $10^6$ labels.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-beygelzimer09a, title = {Conditional Probability Tree Estimation Analysis and Algorithms}, author = {Beygelzimer, Alina and Langford, John and Lifshits, Yury and Sorkin, Gregory and Strehl, Alex}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {43--50}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/beygelzimer09a/beygelzimer09a.pdf}, url = {https://proceedings.mlr.press/r7/beygelzimer09a.html}, 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 $10^6$ labels.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Conditional Probability Tree Estimation Analysis and Algorithms %A Alina Beygelzimer %A John Langford %A Yury Lifshits %A Gregory Sorkin %A Alex Strehl %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-beygelzimer09a %I PMLR %P 43--50 %U https://proceedings.mlr.press/r7/beygelzimer09a.html %V R7 %X 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 $10^6$ labels. %Z Reissued by PMLR on 04 October 2026.
APA
Beygelzimer, A., Langford, J., Lifshits, Y., Sorkin, G. & Strehl, A.. (2009). Conditional Probability Tree Estimation Analysis and Algorithms. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:43-50 Available from https://proceedings.mlr.press/r7/beygelzimer09a.html. Reissued by PMLR on 04 October 2026.

Related Material