Please use this identifier to cite or link to this item: https://doi.org/10.1023/A:1012435301888
Title: The relaxed online maximum margin algorithm
Authors: Li, Y.
Long, P.M. 
Keywords: Large margin classifiers
Online learning
Perceptrons
Support vector machines
Issue Date: 2002
Source: Li, Y.,Long, P.M. (2002). The relaxed online maximum margin algorithm. Machine Learning 46 (1-3) : 361-387. ScholarBank@NUS Repository. https://doi.org/10.1023/A:1012435301888
Abstract: We describe a new incremental algorithm for training linear threshold functions: the Relaxed Online Maximum Margin Algorithm, or ROMMA. ROMMA can be viewed as an approximation to the algorithm that repeatedly chooses the hyperplane that classifies previously seen examples correctly with the maximum margin. It is known that such a maximum-margin hypothesis can be computed by minimizing the length of the weight vector subject to a number of linear constraints. ROMMA works by maintaining a relatively simple relaxation of these constraints that can be efficiently updated. We prove a mistake bound for ROMMA that is the same as that proved for the perception algorithm. Our analysis implies that the maximum-margin algorithm also satisfies this mistake bound; this is the first worst-case performance guarantee for this algorithm. We describe some experiments using ROMMA and a variant that updates its hypothesis more aggressively as batch algorithms to recognize handwritten digits. The computational complexity and simplicity of these algorithms is similar to that of perceptron algorithm, but their generalization is much better. We show that a batch algorithm based on aggressive ROMMA converges to the fixed threshold SVM hypothesis.
Source Title: Machine Learning
URI: http://scholarbank.nus.edu.sg/handle/10635/39176
ISSN: 08856125
DOI: 10.1023/A:1012435301888
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

98
checked on Dec 5, 2017

Page view(s)

70
checked on Dec 8, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.