SVM

Figure 5.3: Separating hyperplane between two classes obtained using SVM. The points on the margin (dashed line) are the Support Vectors.

Both LDA and logistic regression lead to a linear decision boundary. However, the criteria used to determine this boundary are fundamentally different.

SVM (CV95), like LDA and logistic regression, produces a linear classifier based on a discriminant function of the form shown in equation (5.5). However, the approach is different. The goal of SVM is to determine, among all hyperplanes that correctly separate the two classes, the one that maximizes the separation margin between the training examples and the decision boundary (decision boundary). The idea underlying this approach is that a wider margin generally leads to better classifier generalization and greater robustness to variations in the data.

Let the classification classes be defined as the typical classes of a binary problem in the form $y_i = \{+1,-1\}$, and consider the hyperplane of formula (5.4). Suppose that there exist optimal parameters $(\mathbf{w}_0,b_0)$ satisfying the constraint

$$\begin{array}{ll} \mathbf{x}_i \cdot \mathbf{w}_0 + b_0 \ge... ...athbf{w}_0 + b_0 \leq -1 & \text{per } y_i = -1 \\ \end{array}$$ (5.26)

or, more compactly:

$$y_i ( \mathbf{x}_i \cdot \mathbf{w}_0 + b_0 ) - 1 \geq 0$$ (5.27)

for every $(y_i, \mathbf{x}_i)$ sample provided during the training phase.

It can be assumed that, for each category, one or more vectors $\mathbf{x}_i$ exist for which constraint (5.27) is satisfied with equality. These elements are called Support Vectors. They are the samples that determine the separation margin and, as will be shown later through the KKT conditions, are the only samples associated with nonzero Lagrange multipliers.

The point-to-plane distance $\rho$ (cf. Eq. (1.88)) is

$$\rho = \frac{ \Vert \mathbf{w} \cdot \mathbf{x} + b \Vert } { \Vert \mathbf{w} \Vert }$$ (5.28)

Given two points from opposite classes satisfying equality (5.27), the margin can be derived from equation (5.28) and is

$$\rho = \frac{2}{\Vert \mathbf{w}_0 \Vert}$$ (5.29)

To maximize the margin $\rho$ in equation (5.29), its inverse must be minimized, namely

$$\min_{\mathbf{w},b} \frac{1}{2} \Vert \mathbf{w} \Vert^2$$ (5.30)

subject to the set of constraints expressed by inequality (5.27). This is what is defined as the standard-form primal optimization problem for the SVM.

This class of problems (minimization with inequality constraints, or the primal optimization problem) is solved using the Karush-Kuhn-Tucker approach, which is the method of Lagrange multipliers generalized to inequalities. Using the KKT conditions, the Lagrangian function is obtained:

$$\mathcal{L}(\mathbf{w}, b, \boldsymbol\alpha) = \frac{1}{2}... ...i \left( y_i ( \mathbf{x}_i \cdot \mathbf{w} + b ) - 1 \right)$$ (5.31)

to be minimized with respect to $\mathbf{w}$ and $b$ and maximized with respect to $\boldsymbol\alpha$. The weights $\alpha_i \geq 0$ are the Lagrange multipliers. Setting the partial derivatives to zero gives

$$\frac{\partial \mathcal{L} }{\partial b} = 0 \rightarrow \sum y_i \alpha_i = 0$$ (5.32)

$$\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = 0 \rightarrow \mathbf{w} = \sum \alpha_i y_i \mathbf{x}_i$$ (5.33)

Substituting these results (the primal variables) into the Lagrangian (5.31), it becomes a function only of the multipliers, the dual variables, yielding the Wolfe dual form:

$$\Psi (\boldsymbol\alpha) = \sum \alpha_i -\frac{1}{2} \sum_... ...um_j \alpha_i \alpha_j y_i y_j \mathbf{x}_i \cdot \mathbf{x}_j$$ (5.34)

subject to the constraints $\alpha_i \ge 0$ and $\sum \alpha_i y_i = 0$. The maximum of function $\Psi$ computed over $\boldsymbol\alpha$ gives the $\alpha_i$ associated with each training vector $\mathbf{x}_i$. This maximum makes it possible to find the solution to the original problem.

The KKT conditions hold for this relation, among which the constraint known as Complementary slackness is particularly important:

$$\alpha_i \left( y_i ( \mathbf{x}_i \cdot \mathbf{w} + b ) - 1 \right) = 0$$ (5.35)

The complementary slackness condition states that, at the optimum, for each sample, at least one of the multiplier $\alpha_i$ and the constraint violation must be zero. In particular,

$$\alpha_i > 0 \quad\Longrightarrow\quad y_i(\mathbf{x}_i\cdot\mathbf{w}+b)=1$$ (5.36)

Samples associated with nonzero multipliers therefore lie exactly on the margin and are called Support Vectors. All other samples have $\alpha_i=0$ and do not contribute directly to the solution.

By solving the quadratic problem (5.34), subject to constraint (5.32) and $\alpha_i \geq 0$, the weights having $\alpha_i\neq 0$ will be the Support Vectors. Substituting these weights into equations (5.33) and (5.35) yields the maximum-margin hyperplane.

The most widely used method for solving this QP is Sequential Minimal Optimization (SMO). For an in-depth treatment of topics related to SVMs, see (SS02).