Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Conditional Probability Tree Estimation Analysis and Algorithms
Alina Beygelzimer, John Langford, Yuri Lifshits, Gregory Sorkin, Alexander Strehl
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.
Keywords: null
Pages: 51-58
PS Link:
PDF Link: /papers/09/p51-beygelzimer.pdf
AUTHOR = "Alina Beygelzimer and John Langford and Yuri Lifshits and Gregory Sorkin and Alexander Strehl",
TITLE = "Conditional Probability Tree Estimation Analysis and Algorithms",
BOOKTITLE = "Proceedings of the Twenty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-09)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2009",
PAGES = "51--58"

hosted by DSL   •   site info   •   help