  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.
