Y. Li
and P. M. Long. The
relaxed online maximum margin algorithm. Machine
Learning, 46 (1/3):361-387, 2002. (Available in Postscript and PDF formats.)
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 perceptron 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.
Related paper
Since we published our paper,
Yoram Singer
told us about the following related paper.
H.H. Bauschke
and P.L. Combettes. A
weak-to-strong convergence principle for Fejer-monotone Methods in
Hilbert spaces. Mathematics of Operations Research 26(2),
pp. 248-264, 2001.
That paper includes a description of a framework in the following
thesis:
Y. Haugazeau. Sur les inéquations variationnelles et la minimisation
de fonctionnelles convexes. Thèse, Université de Paris, 1968.
ROMMA is a special case of this framework. Our analysis is also related
to an extent.