|
|
|
|
Conditional Probability Tree Estimation Analysis and Algorithms
Alina Beygelzimer, John Langford, Yuri Lifshits, Gregory Sorkin, Alexander Strehl
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.
Keywords: null
Pages: 51-58
PS Link:
PDF Link: /papers/09/p51-beygelzimer.pdf
BibTex:
@INPROCEEDINGS{Beygelzimer09,
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)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2009",
PAGES = "51--58"
}
|
|
