Abstract

Large Margin Hierarchical Classification
Ofer Dekel - The Hebrew University Joseph Keshet - The Hebrew University Yoram Singer - The Hebrew University
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 andBayesian 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 ofBayesian 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.

Large Margin Hierarchical Classification

Ofer Dekel - The Hebrew University
Joseph Keshet - The Hebrew University
Yoram Singer - The Hebrew University

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 andBayesian 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 ofBayesian 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.