  We consider multi-class classification where the predictor has a hierarchical
structure that allows for a very large number of labels both at train and test
time. The predictive power of such models can heavily depend on the structure
of the tree, and although past work showed how to learn the tree structure, it
expected that the feature vectors remained static. We provide a novel algorithm
to simultaneously perform representation learning for the input data and
learning of the hierarchi- cal predictor. Our approach optimizes an objec- tive
function which favors balanced and easily- separable multi-way node partitions.
We theoret- ically analyze this objective, showing that it gives rise to a
boosting style property and a bound on classification error. We next show how
to extend the algorithm to conditional density estimation. We empirically
validate both variants of the al- gorithm on text classification and language
mod- eling, respectively, and show that they compare favorably to common
baselines in terms of accu- racy and running time.
