Support Vector Machines for Polycategorical Classification

Abstract

Polycategorical classification deals with the task of solving multiple interdependent classification problems. The key challenge is to systematically exploit possible dependencies among the labels to improve on the standard approach of solving each classification problem independently. Our method operates in two stages: the first stage uses the observed set of labels to learn a joint label model that can be used to predict unobserved pattern labels purely based on inter-label dependencies. The second stage uses the observed labels as well as inferred label predictions as input to a generalized transductive support vector machine. The resulting mixed integer program is heuristically solved with a continuation method. We report experimental results on a collaborative filtering task that provide empirical support for our approach.