Online learning of multi-class Support Vector Machines

University essay from Uppsala universitet/Institutionen för informationsteknologi

Author: Xuan Tuan Trinh; [2012]

Keywords: ;

Abstract:

Support Vector Machines (SVMs) are state-of-the-art learning algorithms forclassification problems due to their strong theoretical foundation and their goodperformance in practice. However, their extension from two-class to multi-classclassification problems is not straightforward. While some approaches solve a seriesof binary problems, other, theoretically more appealing methods, solve one singleoptimization problem. Training SVMs amounts to solving a convex quadraticoptimization problem. But even with a carefully tailored quadratic program solver,training all-in-one multi-class SVMs takes a long time for large scale datasets. We firstconsider the problem of training the multi-class SVM proposed by Lee, Lin and Wahba(LLW), which is the first Fisher consistent multi-class SVM that has been proposed inthe literature, and has recently been shown to exhibit good generalizationperformance on benchmark problems. Inspired by previous work on onlineoptimization of binary and multi-class SVMs, a fast approximative online solver for theLLW SVM is derived. It makes use of recent developments for efficiently solvingall-in-one multi-class SVMs without bias. In particular, it uses working sets of size twoinstead of following the paradigm of sequential minimal optimization. After successfulimplementation of the online LLW SVM solver, it is extended to also support thepopular multi-class SVM formulation by Crammer and Singer. This is done using arecently established unified framework for a larger class of all-in-one multi-class SVMs.This makes it very easy in the future to adapt the novel online solver to even moreformulations of multi-class SVMs. The results suggest that online solvers may providefor a robust and well-performing way of obtaining an approximative solution to thefull problem, such that it constitutes a good trade-off between optimization time andreaching a sufficiently high dual value.

  AT THIS PAGE YOU CAN DOWNLOAD THE WHOLE ESSAY. (follow the link to the next page)