Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
2012.
Series
IT, 12 061
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-185084OAI: oai:DiVA.org:uu-185084DiVA: diva2:570643
Educational program
Master Programme in Computer Science
Uppsok
Technology
Supervisors
Examiners
Available from: 2012-11-20 Created: 2012-11-20 Last updated: 2012-11-20Bibliographically approved

Open Access in DiVA

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

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 1230 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

urn-nbn

Altmetric score

urn-nbn
Total: 633 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf