Change search
ReferencesLink to record
Permanent link

Direct link
Online learning of multi-class Support Vector Machines
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
2012 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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.

Place, publisher, year, edition, pages
IT, 12 061
National Category
Engineering and Technology
URN: urn:nbn:se:uu:diva-185084OAI: diva2:570643
Educational program
Master Programme in Computer Science
Available from: 2012-11-20 Created: 2012-11-20 Last updated: 2012-11-20Bibliographically approved

Open Access in DiVA

fulltext(569 kB)933 downloads
File information
File name FULLTEXT02.pdfFile size 569 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 933 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 300 hits
ReferencesLink to record
Permanent link

Direct link