Large Margin Hierarchical Classification

Abstract

We present an algorithmic framework for supervised classification learningwhere the set of labels is organized in a predefined hierarchical structure. This structure is encoded by a rooted tree which induces a metric over thelabel set. Our approach combines ideas from large margin kernel methods and Bayesian analysis. Following the large margin principle, we associate aprototype with each label in the tree and formulate the learning task as anoptimization problem with varying margin constraints. In the spirit of Bayesian methods, we impose similarity requirements between the prototypescorresponding to adjacent labels in the hierarchy. We describe new online andbatch algorithms for solving the constrained optimization problem. We derive aworst case loss-bound for the online algorithm and provide generalizationanalysis for its batch counterpart. We demonstrate the merits of our approachwith a series of experiments on synthetic, text and speech data.