Unsupervised and Semi-Supervised Multi-class Support Vector Machines

Linli Xu, Dale Schuurmans

We present new unsupervised and semi-supervised training algorithms for multi-class support vector machines based on semidefinite programming. Although support vector machines (SVMs) have been a dominant machine learning technique for the past decade, they have generally been applied to supervised learning problems. Developing unsupervised extensions to SVMs has in fact proved to be difficult. In this paper, we present a principled approach to unsupervised SVM training by formulating convex relaxations of the natural training criterion: find a labeling that would yield an optimal SVM classifier on the resulting training data. The problem is hard, but semidefinite relaxations can approximate this objective surprisingly well. While previous work has concentrated on the two-class case, we present a general, multi-class formulation that can be applied to a wider range of natural data sets. The resulting training procedures are computationally intensive, but produce high quality generalization results.

Content Area: 12. Machine Learning

Subjects: 12. Machine Learning and Discovery

Submitted: May 11, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.