Conditional Probability Tree Estimation Analysis and Algorithms

Details Conditional Probability Tree Estimation Analysis and Algorithms Conditional Probability Tree Estimation Analysis and Algorithms

2009-03-25

arxiv.org/abs/0903.4217v2

Computer Science

Learning

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Conditional Probability Tree Estimation Analysis and Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Conditional Probability Tree Estimation Analysis and Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conditional Probability Tree Estimation Analysis and Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-67788