Bonsai -- Diverse and Shallow Trees for Extreme Multi-label Classification

Extreme multi-label classification (XMC) refers to supervised multi-label involving hundreds of thousand or even millions of labels. In this, we develop a suite of algorithms, called Bonsai, which generalizes the of label representation in XMC, and partitions the labels in the space to learn shallow trees. We show three concrete of this label representation space including: (i) the input space is spanned by the input features, (ii) the output space spanned by label based on their co-occurrence with other labels, and (iii) the joint by combining the input and output representations. Furthermore, the-free multi-way partitions learnt iteratively in these spaces lead to trees. By combining the effect of shallow trees and generalized label, Bonsai achieves the best of both worlds - fast training which comparable to state-of-the-art tree-based methods in XMC, and much better accuracy, particularly on tail-labels. On a benchmark Amazon-3M with 3 million labels, \ outperforms a state-of-the-art-vs-rest method in terms of prediction accuracy, while being approximately200 times faster to train. The code for Bonsai is available at: //github. com/xmc-aalto/bonsai