Support vector machines

Because SVM learning is guaranteed to converge to a single global solution, the algorithm itself is fairly simple. Our implementation follows the formulation of [Jaakkola et al., 1998]. This approach differs slightly from that of [Vapnik, 1998], although the geometric interpretation remains the same. Let ${\bf X} = {\bf X_1} \dots {\bf X_n}$ be a set of training examples, and $y = y_1 \dots y_n$ be the corresponding set of classifications, where y_i = 1 if ${\bf X_i}$is a member of the class to be learned, and y_i = -1 otherwise. Define the discriminant function

$$L({\bf X}) = \sum_{i=1}^{n} y_i \alpha_i K({\bf X}, {\bf X_i}),$$ (4)

where $\alpha_i$ is the weight of training example ${\bf X_i}$. The goal is to learn a set of weights that maximize the following objective function:

$$J(\alpha) \sum_{i=1}^{n} \alpha_i(2 - y_i L({\bf X_i}))$$ = (5)

$$2 \sum_i \alpha_i - \sum_{i,j} \alpha_i \alpha_j y_i y_j K({\bf X_i},{\bf X_j})$$ = (6)

This maximum can be obtained by iteratively updating the weights using the following update rule:

$$\alpha_i \leftarrow f\left(\frac{1 - y_i L({\bf X_i}) + \alpha_i K({\bf X_i}, {\bf X_i})} {K({\bf X_i},{\bf X_i})} \right),$$ (7)

where f(x)=x for x > 0 and f(x)=0 for x <= 0. Note that equation 7 differs from the corresponding equation in [Jaakkola et al., 1998], in that the weights $\alpha_i$ are not constrained to be less than 1. This difference arises because we implement the soft margin by modifying the diagonal of the kernel matrix, rather than by truncating the weights.

The output of the SVM learning algorithm is the optimized set of weights $\alpha_1 \dots \alpha_n$. The class of a new input vector ${\bf X}$ is then given by the sign of the discriminant $L({\bf X})$computed using the optimized weights.³