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