9.2 Linear SVM in the Non-Separable Case: Slack Variables

If the classes are not linearly separable, a zero training error is impossible and the hard-margin problem is infeasible.

We therefore introduce slack variables \(\{\xi_i\}_{i=1}^{n}\) and relax the margin constraints to \[ y_i\bigl(x_i^T\beta + \beta_0\bigr) \ge 1-\xi_i,\qquad \xi_i\ge 0. \]

Slack variables in the linearly non-separable case

Figure 9.3: Slack variables in the linearly non-separable case

The value of \(\xi_i\) has a direct geometric reading:

  • \(\xi_i=0\): the point is on the correct side and outside or on the margin.
  • \(0<\xi_i\le 1\): the point is on the correct side but inside the margin.
  • \(\xi_i>1\): the point is on the wrong side of the separating hyperplane.
The soft-margin problem is

\[ \operatorname{minimize}_{\beta,\,\beta_0,\,\xi}\quad \frac12\|\beta\|^2 + C\sum_{i=1}^{n}\xi_i \] \[ \text{subject to }\quad y_i\bigl(x_i^T\beta+\beta_0\bigr)\ge 1-\xi_i,\qquad \xi_i\ge 0,\qquad i=1,\ldots,n. \]

The objective trades a large margin \(2/\|\beta\|\) against the total slack \(\sum_i\xi_i\). The tuning parameter \(C>0\) is the cost of slack. A large \(C\) penalizes violations heavily and recovers the hard-margin problem as \(C\to\infty\). A small \(C\) tolerates more violations in exchange for a wider margin. In practice \(C\) is chosen by cross-validation.

In these notes the parameter is \(C\). In e1071::svm() the same quantity is called cost.


Solving the SVM with Slack Variables

The Lagrangian of the primal is \[\begin{align*} \mathcal{L}(\beta,\beta_0,\xi,\alpha,\gamma) &= \frac12\|\beta\|^2 + C\sum_{i=1}^{n}\xi_i - \sum_{i=1}^{n}\alpha_i\bigl\{y_i(x_i^T\beta+\beta_0)-(1-\xi_i)\bigr\} - \sum_{i=1}^{n}\gamma_i\xi_i, \end{align*}\] with \(\alpha_i\ge 0\) and \(\gamma_i\ge 0\). Stationarity yields \[\begin{align*} \nabla_{\beta}\mathcal{L}=0 &\quad\Leftrightarrow\quad \beta = \sum_{i=1}^{n}\alpha_i y_i x_i,\\ \nabla_{\beta_0}\mathcal{L}=0 &\quad\Leftrightarrow\quad \sum_{i=1}^{n}\alpha_i y_i = 0,\\ \nabla_{\xi_i}\mathcal{L}=0 &\quad\Leftrightarrow\quad C-\alpha_i-\gamma_i=0. \end{align*}\] The last identity, together with \(\gamma_i\ge 0\), forces \(0\le\alpha_i\le C\). Substituting back produces the soft-margin dual:

\[ \max_{\alpha}\ \sum_{i=1}^{n}\alpha_i - \frac12\sum_{i,j=1}^{n} y_i y_j\alpha_i\alpha_j\,\langle x_i,x_j\rangle \] \[ \text{subject to }\quad 0\le\alpha_i\le C,\qquad i=1,\ldots,n, \qquad \sum_{i=1}^{n}\alpha_i y_i=0. \]

The inner product \(\langle x_i,x_j\rangle\) is just \(x_i^T x_j\). As before, \[ \hat\beta = \sum_{i=1}^{n}\hat\alpha_i y_i x_i. \]

The KKT complementary slackness conditions are \[\begin{align*} \alpha_i\bigl\{y_i(x_i^T\beta+\beta_0)-(1-\xi_i)\bigr\}&=0,\\ \gamma_i\xi_i&=0,\\ y_i(x_i^T\beta+\beta_0)-(1-\xi_i)&\ge 0. \end{align*}\] They partition the training points into three groups:

  • \(\alpha_i=0\) (hence \(\xi_i=0\)): points strictly beyond the margin. They do not affect \(\hat\beta\).
  • \(0<\alpha_i<C\) (hence \(\xi_i=0\)): points on the margin. These are the free support vectors and are the ones used to recover \(\hat\beta_0\).
  • \(\alpha_i=C\): points inside the margin or on the wrong side, with \(\xi_i=1-y_i(x_i^T\beta+\beta_0)\ge 0\).

To compute \(\hat\beta_0\), use any free support vector (\(0<\hat\alpha_i<C\)), for which \(y_i(x_i^T\hat\beta+\hat\beta_0)=1\). Averaging over all such points is more stable numerically. Do not use the hard-margin midpoint formula here: with slack, the closest points from each class may be inside the margin or misclassified.

The two panels below use the same data with \(C=1000\) (left) and \(C=0.1\) (right). The plotted intercept is the solver intercept -svm.fit$rho, not the midpoint formula.

A large \(C\) puts more weight on avoiding slack than on widening the margin. A small \(C\) does the reverse and is influenced more by points far from the boundary. In estimation language: large \(C\) is closer to empirical 0-1 risk; small \(C\) is more regularization. The same soft-margin program can be used on separable data as well: we may deliberately allow a few points to cross a margin line if that substantially increases the margin. The parameter \(C\) controls that trade-off.