Conditional Probability Tree Estimation Analysis and Algorithms

Alina Beygelzimer, John Langford, Yuri Lifshits +2

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…