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