On the computational complexity of the probabilistic label tree algorithms

Understand

Label tree-based algorithms are widely used to tackle multi-class and multi-label problems with a large number of labels.

• We focus on a particular subclass of these algorithms that use probabilistic classifiers in the tree nodes.
• Examples of such algorithms are hierarchical softmax (HSM), designed for multi-class classification, and probabilistic label trees (PLTs) that generalize HSM to multi-label problems.
• If the tree structure is given, learning of PLT can be solved with provable regret guaranties [Wydmuch et.al.