svmpath: Fit the entire regularization path for a 2-class SVM

In svmpath: The SVM Path Algorithm

Description

The SVM has a regularization or cost parameter C, which controls the amount by which points overlap their soft margins. Typically either a default large value for C is chosen (allowing minimal overlap), or else a few values are compared using a validation set. This algorithm computes the entire regularization path (i.e. for all possible values of C for which the solution changes), with a cost a small (~3) multiple of the cost of fitting a single model.

Usage

svmpath(x, y, K, kernel.function = poly.kernel, param.kernel = 1, trace,
  plot.it, eps = 1e-10, Nmoves = 3 * n, digits = 6, lambda.min = 1e-04,ridge=0, ...)

Arguments

x	the data matrix (n x p) with n rows (observations) on p variables (columns)
y	The "-1,+1" valued response variable.
K	a n x n kernel matrix, with default value K= kernel.function(x, x)
kernel.function	This is a user-defined function. Provided are poly.kernel (the default, with parameter set to default to a linear kernel) and radial.kernel
param.kernel	parameter(s) of the kernels
trace	if TRUE, a progress report is printed as the algorithm runs; default is FALSE
plot.it	a flag indicating whether a plot should be produced (default FALSE; only usable with p=2
eps	a small machine number which is used to identify minimal step sizes
Nmoves	the maximum number of moves
digits	the number of digits in the printout
lambda.min	The smallest value of lambda = 1/C; default is lambda=10e-4, or C=10000
ridge	Sometimes the algorithm encounters singularities; in this case a small value of ridge, around 1e-12, can help. Default is ridge=0
...	additional arguments to some of the functions called by svmpath. One such argument that can be passed is ridge (default is 1e-10). This is used to produce "stable" solutions to linear equations.

Details

The algorithm used in svmpath() is described in detail in "The Entire Regularization Path for the Support Vector Machine" by Hastie, Rosset, Tibshirani and Zhu (2004). It exploits the fact that the "hinge" loss-function is piecewise linear, and the penalty term is quadratic. This means that in the dual space, the lagrange multipliers will be pieceise linear (c.f. lars).

Value

a "svmpath" object is returned, for which there are print, summary, coef and predict methods.

Warning

Currently the algorithm can get into machine errors if epsilon is too small, or if lambda.min is too small. Increasing either from their defaults should make the problems go away, by terminating the algorithm slightly early.

Note

This implementation of the algorithm does not use updating to solve the "elbow" linear equations. This is possible, since the elbow changes by a small number of points at a time. Future version of the software will do this. The author has encountered numerical problems with early attempts at this.

Author(s)

Trevor Hastie

References

The paper http://www-stat.stanford.edu/~hastie/Papers/svmpath.pdf, as well as the talk http://www-stat.stanford.edu/~hastie/TALKS/svmpathtalk.pdf.

See Also

print, coef, summary, predict, and FilmPath

Examples

data(svmpath)
attach(unbalanced.separated)
svmpath(x,y,trace=TRUE,plot=TRUE)
detach(2)
## Not run: svmpath(x,y,kernel=radial.kernel,param.kernel=.8)

Example output

Loaded svmpath 0.955

1:	Obs 1	 ->E  lambda = 2.607316  Sum Eps = 4.35 Elbow = 2 Error = 2
1:	Obs 11	 ->E  lambda = 2.607316  Sum Eps = 4.35 Elbow = 2 Error = 2
2:	Obs 6	L->E  lambda = 1.981148  Sum Eps = 4.14 Elbow = 3 Error = 2
3:	Obs 11	E->R  lambda = 1.173511  Sum Eps = 4.14 Elbow = 2 Error = 2
4:	Obs 10	L->E  lambda = 0.960737  Sum Eps = 3.73 Elbow = 3 Error = 2
5:	Obs 1	E->R  lambda = 0.705765  Sum Eps = 3.73 Elbow = 2 Error = 2
6:	Obs 4	L->E  lambda = 0.460165  Sum Eps = 3.1 Elbow = 3 Error = 1
7:	Obs 10	E->R  lambda = 0.194509  Sum Eps = 3.1 Elbow = 2 Error = 1
8:	Obs 8	L->E  lambda = 0.101745  Sum Eps = 2.27 Elbow = 3 Error = 1
9:	Obs 4	E->R  lambda = 0.0676586  Sum Eps = 2.27 Elbow = 2 Error = 1
10:	Obs 3	L->E  lambda = 0.0273655  Sum Eps = 0.83 Elbow = 3 Error = 0
11:	Obs 8	E->R  lambda = 0.0128392  Sum Eps = 0.83 Elbow = 2 Error = 0
12:	Obs 9	L->E  lambda = 0.00750737  Sum Eps = 0 Elbow = 3 Error = 0
1:	Obs 1	 ->E  lambda = 2.607316  Sum Eps = 4.35 Elbow = 2 Error = 2
1:	Obs 11	 ->E  lambda = 2.607316  Sum Eps = 4.35 Elbow = 2 Error = 2
2:	Obs 6	L->E  lambda = 1.981148  Sum Eps = 4.14 Elbow = 3 Error = 2
3:	Obs 11	E->R  lambda = 1.173511  Sum Eps = 4.14 Elbow = 2 Error = 2
4:	Obs 10	L->E  lambda = 0.960737  Sum Eps = 3.73 Elbow = 3 Error = 2
5:	Obs 1	E->R  lambda = 0.705765  Sum Eps = 3.73 Elbow = 2 Error = 2
6:	Obs 4	L->E  lambda = 0.460165  Sum Eps = 3.1 Elbow = 3 Error = 1
7:	Obs 10	E->R  lambda = 0.194509  Sum Eps = 3.1 Elbow = 2 Error = 1
8:	Obs 8	L->E  lambda = 0.101745  Sum Eps = 2.27 Elbow = 3 Error = 1
9:	Obs 4	E->R  lambda = 0.0676586  Sum Eps = 2.27 Elbow = 2 Error = 1
10:	Obs 3	L->E  lambda = 0.0273655  Sum Eps = 0.83 Elbow = 3 Error = 0
11:	Obs 8	E->R  lambda = 0.0128392  Sum Eps = 0.83 Elbow = 2 Error = 0
12:	Obs 9	L->E  lambda = 0.00750737  Sum Eps = 0 Elbow = 3 Error = 0

svmpath documentation built on July 14, 2020, 5:06 p.m.