Support vector machine foundations

Support vector machines construct a decision rule from a subset of training observations called support vectors. This chapter derives the linear maximum-margin classifier, introduces the kernel representation, and then gives the primal, dual, and decision functions for the three model families supported by MISTIC.

From a separating plane to maximum margin

For binary labels \(y_i\in\{-1,+1\}\), a linear classifier uses

\[f(\mathbf{x}) = \mathbf{w}^{\mathsf T}\mathbf{x}+b, \qquad \widehat y = \operatorname{sign}(f(\mathbf{x})).\]

Multiplying \((\mathbf{w},b)\) by a positive constant does not change the plane \(f(\mathbf{x})=0\). We therefore choose a canonical scaling in which the nearest observations obey \(y_i(\mathbf{w}^{\mathsf T}\mathbf{x}_i+b)=1\). The two supporting planes are \(f(\mathbf{x})=+1\) and \(f(\mathbf{x})=-1\). Their perpendicular distance is \(2/\lVert\mathbf{w}\rVert\), so maximizing the margin is equivalent to minimizing \(\frac12\lVert\mathbf{w}\rVert^2\).

Gold rings mark support vectors: the observations that constrain the margin. Non-support vectors do not appear in the final kernel expansion.

Perfect separation is often impossible. Slack variables \(\xi_i\geq 0\) permit margin violations, and \(C\) controls their penalty. This gives the soft-margin primal problem [1]:

\[\min_{\mathbf{w},b,\boldsymbol\xi} \frac12\lVert\mathbf{w}\rVert^2+C\sum_{i=1}^{n}\xi_i\]
\[\text{subject to}\quad y_i(\mathbf{w}^{\mathsf T}\phi(\mathbf{x}_i)+b)\geq 1-\xi_i, \qquad \xi_i\geq 0.\]

The map \(\phi\) is written explicitly because the same derivation applies in a transformed feature space.

Lagrange multipliers and the classification dual

Introduce multipliers \(\alpha_i\geq0\) for the margin constraints and \(\mu_i\geq0\) for nonnegative slack. Stationarity of the Lagrangian gives

\[\mathbf{w}=\sum_i\alpha_i y_i\phi(\mathbf{x}_i),\qquad \sum_i\alpha_i y_i=0,\qquad 0\leq\alpha_i\leq C.\]

Substituting these conditions removes \(\mathbf w\), \(b\), and the slack variables, yielding the SVC dual:

\[\max_{\boldsymbol\alpha} \left[ \sum_i\alpha_i- rac12\sum_{i,j}\alpha_i\alpha_j y_i y_j K(\mathbf{x}_i,\mathbf{x}_j) \right]\]
\[\text{subject to}\quad 0\leq\alpha_i\leq C, \qquad \sum_i\alpha_i y_i=0.\]

Only observations with \(\alpha_i>0\) are support vectors. If \(\beta_i=\alpha_i y_i\), the decision function is

\[f_{\mathrm{SVC}}(\mathbf{x})= \sum_{i\in SV}\beta_i K(\mathbf{x}_i,\mathbf{x})+b.\]

The kernel trick

The dual uses transformed observations only through inner products \(\phi(\mathbf{x}_i)^{\mathsf T}\phi(\mathbf{x}_j)\). A kernel evaluates that inner product directly,

\[K(\mathbf{x}_i,\mathbf{x}_j) =\phi(\mathbf{x}_i)^{\mathsf T}\phi(\mathbf{x}_j),\]

without explicitly constructing the possibly high-dimensional coordinates. The optimization remains a linear maximum-margin problem in feature space even when its boundary is nonlinear in the original inputs. MISTIC computes these kernel matrices so it can recompute them after adding or removing feature groups.

Support vector regression

SVR replaces the classification margin with an \(\varepsilon\)-insensitive tube around a regression function [2]. Deviations inside the tube have zero loss. The primal is

\[\min_{\mathbf w,b,\boldsymbol\xi,\boldsymbol\xi^*} \frac12\lVert\mathbf w\rVert^2 +C\sum_i(\xi_i+\xi_i^*)\]

subject to

\[y_i-f(\mathbf{x}_i)\leq\varepsilon+\xi_i, \quad f(\mathbf{x}_i)-y_i\leq\varepsilon+\xi_i^*, \quad \xi_i,\xi_i^*\geq0.\]

With one multiplier for each side of the tube, the dual becomes

\[\max_{\boldsymbol\alpha,\boldsymbol\alpha^*} \left[ -\frac12(\boldsymbol\alpha-\boldsymbol\alpha^*)^{\mathsf T} K(\boldsymbol\alpha-\boldsymbol\alpha^*) -\varepsilon\sum_i(\alpha_i+\alpha_i^*) +\sum_i y_i(\alpha_i-\alpha_i^*) \right]\]
\[\text{subject to}\quad 0\leq\alpha_i,\alpha_i^*\leq C, \qquad \sum_i(\alpha_i-\alpha_i^*)=0.\]

Writing \(\beta_i=\alpha_i-\alpha_i^*\), the prediction function is

\[f_{\mathrm{SVR}}(\mathbf{x})= \sum_{i\in SV}\beta_i K(\mathbf{x}_i,\mathbf{x})+b.\]

MISTIC’s regression score combines squared Pearson correlation with nonnegative R-squared and also reports root mean squared error. Interpret errors and explanations in the units of the modeled target, including any target transformation.

One-class SVM

A one-class SVM estimates a region containing most of an inlier distribution [3]. It separates mapped observations from the origin. Its primal is

\[\min_{\mathbf w,\rho,\boldsymbol\xi} \frac12\lVert\mathbf w\rVert^2 +\frac{1}{\nu n}\sum_i\xi_i-\rho\]
\[\text{subject to}\quad \mathbf w^{\mathsf T}\phi(\mathbf{x}_i)\geq\rho-\xi_i, \qquad \xi_i\geq0.\]

The dual is

\[\min_{\boldsymbol\alpha}\frac12\boldsymbol\alpha^{\mathsf T} K\boldsymbol\alpha \quad\text{subject to}\quad 0\leq\alpha_i\leq\frac{1}{\nu n},\quad\sum_i\alpha_i=1,\]

and the signed decision function is

\[f_{\mathrm{OCSVM}}(\mathbf{x})= \sum_{i\in SV}\alpha_iK(\mathbf{x}_i,\mathbf{x})-\rho.\]

MISTIC and scikit-learn use \(+1\) for inliers and \(-1\) for novelties. Positive decision values lie on the learned inlier side. The choice of inlier population changes the scientific question, preprocessing, fitted region, and explanations.

Connecting the three models

All three decision functions have the common sparse form

\[f(\mathbf{x})=\boldsymbol\beta^{\mathsf T} \mathbf{k}(\mathbf{x})+b_0,\]

where \(\mathbf{k}(\mathbf{x})\) contains kernels between support vectors and \(\mathbf{x}\). The meanings of \(\boldsymbol\beta\) and \(b_0\) differ by model, but the shared form is what permits MISTIC’s kernel perturbations and analytical gradients.

References