Training SVMs without offset Page: 2 of 59
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to UNT Digital Library by the UNT Libraries Government Documents Department.
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
Training SVMs without Offset
Ingo Steinwart, Don Hush, and Clint Scovel
Information Sciences Group, CCS-3
Los Alamos National Laboratory
{ingo, dhush, j cs}@lanl. gov
January 26, 2009
Abstract
We develop, analyze, and test a training algorithm for support vector machine clas-
sifiers without offset. Key features of this algorithm are a new stopping criterion and a
set of working set selection strategies that, although inexpensive, do not lead to substan-
tially more iterations than the optimal working set selection strategy. For these working
set strategies, we establish convergence rates that coincide with the best known rates
for SVMs with offset. We further conduct various experiments that investigate both the
run time behavior and the performed iterations of the new training algorithm. It turns
out, that the new algorithm needs less iterations and run-time than standard training
algorithms for SVMs with offset.
1 Introduction
Historically, support vector machines (SVMs) were motivated by a geometrical illustration
of their linear decision surface in the feature space. This illustration motivated the use of
an offset b that moves the decision surface from the origin. However, in recent years it
has become increasingly evident that this geometrical interpretation has serious flaws (see,
e.g., [19] for some illustrations) when considering kernels that have a large feature space
such as the Gaussian RBF kernels. In addition, the current approach for investigating the
generalization performance of SVMs does not suggest that the offset offers any improvement
for such kernels. On the other hand, the SVM optimization problem with offset imposes
more restrictions on solvers than the optimization problem without offset does. For example,
the offset leads to an additional equality constraint in the dual optimization problem, which
in turn makes it necessary to update at least two dual variables at each iteration of commonly
used solvers such as sequential minimal optimization (SMO). In addition, such solvers can
only update certain pairs of dual variables, namely the ones whose update still satisfy the
equality contraint. Moreover, the offset makes it also relatively expensive to calculate the
duality gap, see [3, p. 110], which may serve as a stopping criterion for these solvers, and
hence one usually considers upper bounds of this gap such as the one from the maximal
violating pair algorithm, see e.g. [14].
Despite these issues, research on algorithmic solutions has, with a few exceptions (see,
e.g., [7]), so far focused on SVM formulations with offset, see e.g. [12, 11, 13, 9, 16, 5, 17, 2, 8,
6, 15, 18] and the references therein. The goal of this work is to fill this gap by developing
algorithms for SVMs without offset. As it turns out, these algorithms not only achieve
a classification accuracy that is comparable to the one for SVMs with offset, but also runI
Upcoming Pages
Here’s what’s next.
Search Inside
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Steinwart, Ingo; Hush, Don & Scovel, Clint. Training SVMs without offset, article, January 1, 2009; [New Mexico]. (https://digital.library.unt.edu/ark:/67531/metadc930657/m1/2/: accessed April 19, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.