B.4.8 svm

This is an implementation of a support vector machine (SVM) classifier. We didn't actually implement our own SVM, but embedded SVM$^{\mbox{\emph{light}}}$ [18] in the software. SVM is a novel type of learning machine which tries to find the largest margin linear classifier. Vapnik [42] shows how training a support vector machine leads to the following quadratic optimization problem:

$$\begin{array}{rcl r@{}c@{}l} {\bf W}(\alpha) & = & \multicolu... ...rk>932 \alpha_i & \leq & C, & i & = & 1 \ldots \ell \end{array}$$ (B.10)

The number of training examples is denoted by $\ell$. $\alpha$ is a vector of $\ell$ variables, where each component $\alpha_i$ corresponds to a training example $(x_i, y_i)$. The solution of Problem  is the vector $\alpha^*$ for which ${\bf W}(\alpha)$ is minimized and the constraints are satisfied. Defining the matrix Q as $Q_{ij} = {y_i}{y_j}k(x_i,x_j)$, this can equivalently be written as

$$\begin{array}{l rcl r@{}c@{}l} \mbox{minimize} & {\bf W}(\alp... ...935 & \alpha_i & \leq & C1, & i & = & 1 \ldots \ell \end{array}$$ (B.11)

Two good tutorials for SVM are [29] and [3].

Keyword	Arg Type	Arg Vals	Default
Common
capacity	float	[1e-10, $\infty$)	10.0
cost	float	[1e-10, 1e+10]	1.0
gamma	float	(0, $\infty$)	0.002
kernel	int	0, 2	0
svmdir	path		./
usedefcapacity	none
usedefgamma	none
Rare
learn	filename		svm_learn
classify	filename		svm_classify
example	filename		svm_example
model	filename		svm_model
result	filename		svm_result

Common keywords and arguments:

• capacity float: This corresponds to the -c option for svm_learn . From the SVM$^{\mbox{\emph{light}}}$ command-line help:

  C: trade-off between training error and margin (default avg. $(x^T x)^{-1}$)

  If you would like to use the SVM$^{\mbox{\emph{light}}}$ default value, please see the usedefcapacity argument, below.

• cost float: This corresponds to the -j option for svm_learn . From the SVM$^{\mbox{\emph{light}}}$ command-line help:

  Cost: cost-factor, by which training errors on positive examples outweigh errors on negative examples (default 1) (see K. Morik, P. Brockhausen, and T. Joachims, Combining statistical learning with a knowledge-based approach - A case study in intensive care monitoring. International Conference on Machine Learning (ICML), 1999.

• gamma float: This corresponds to the -g option for svm_learn . From the SVM$^{\mbox{\emph{light}}}$ command-line help:

  parameter gamma in rbf kernel

  If you would like to use the SVM$^{\mbox{\emph{light}}}$ default value, please see the usedefgamma argument, below.

• kernel int: This corresponds to the -k option for svm_learn . From the SVM$^{\mbox{\emph{light}}}$ command-line help:

  type of kernel function:

  1:

  linear (default)

  2:

  polynomial $(s a*b+c)^d$

  3:

  radial basis function $\exp(-gamma \vert\vert a-b\vert\vert^2)$

  4:

  sigmoid $tanh(s a*b + c)$

  5:

  user defined kernel from kernel.h

  Note that at present we only support linear and radial basis function kernels; additional kernels from the list above will be supported upon request.

• svmdir path: This option specifies the directory in which the SVM$^{\mbox{\emph{light}}}$ executables can be found. If the learn or classify options are set, their values are appended to the value of svmdir

• usedefcapacity none: If you specify this option, the default capacity of SVM$^{\mbox{\emph{light}}}$ will be used in place of this program's default.

• usedefgamma none: If you specify this option, the default gamma of SVM$^{\mbox{\emph{light}}}$ will be used in place of this program's default.

Rare keywords and arguments:

• classify filename: This allows specification of the svm_classify executable name. The value of classify will be appended to the value of svmdir (path separators are inserted as necessary).

• example filename: This allows specification of the svm_example executable name. The value of example will be appended to the value of svmdir (path separators are inserted as necessary).

• learn filename: This allows specification of the svm_learn executable name. The value of learn will be appended to the value of svmdir (path separators are inserted as necessary).

• model filename: This allows specification of the svm_classify executable name. The value of model will be appended to the value of svmdir (path separators are inserted as necessary).

• result filename: This allows specification of the svm_classify executable name. The value of result will be appended to the value of svmdir (path separators are inserted as necessary).