• View
• Edit
• History
• Print

Online Conditional Probability Tree Learning

In many machine learning applications, it's critical to accurately predict the conditional probability P(y|x) of a label y given context information x. When the set of objects is large, many common approaches have a computational complexity scaling with the number of possible labels y. I will present a general purpose algorithm doing this in logarithmic time which learns the tree structure in a purely online fashion. This algorithm is suitable for large scale text applications where we test it out, showing radical computational performance improvement and similar prediction performance compared to exponentially slower approaches.