Convex Calibrated Surrogates for Hierarchical Classification

Hierarchical classification problems are multi-class supervised learning problems with a pre-defined hierarchy over the set of class labels. In this work, we study the consistency of hierar-chical classification algorithms with respect to a natural loss, namely the tree distance metric on the hierarchy tree of class labels, via the us-age of calibrated surrogates. We first show that the Bayes optimal classifier for this loss classi-fies an instance according to the deepest node in the hierarchy such that the total conditional probability of the subtree rooted at the node is greater than 12. We exploit this insight to develop new consistent algorithm for hierarchical classi-fication, that makes use of an algorithm known to be consistent for the “multiclass classification with reject option (MCRO) ” problem as a sub-routine. Our experiments on a number of bench-mark datasets show that the resulting algorithm, which we term OvA-Cascade, gives improved performance over other state-of-the-art hierarchi-cal classification algorithms. 1