SVM is a very important model in machine learning, proposed by Vladimir Vapnik, the father of statistical learning theory
This post takes binary classification with SVM as the example
Derivation
Given the training dataset $D=\\{(\mathbf{x_1},y_1),(\mathbf{x_2},y_2),...,(\mathbf{x_m},y_m)\\}, y_i \in \\{-1, +1\\}$, the most basic idea of a classifier is to find in the sample space a dividing space based on the training set D that separates the samples of different classes. The dividing hyperplane can be described by the following linear equation:
$$ {\mathbf{w}}^T\mathbf{x}+b=0$$where $\mathbf{w}=(w_1;w_2;...;w_d)$ is the normal vector, which determines the direction of the hyperplane, and b is the offset term, which determines the distance between the hyperplane and the origin; thus the hyperplane is determined by w and d. Then the distance from any point in space to the hyperplane (w,b) is:
$$\gamma = \frac{\vert{\mathbf{w}}^T\mathbf{x}+b\vert}{\Vert\mathbf{w}\Vert}$$Suppose the hyperplane (w,b) classifies the samples completely correctly, that is, for $(\mathbf{x_i}, y_i) \in D$, if $y_i=+1$ then ${\mathbf{w}}^T\mathbf{x_i}+b > 0$; if $y_i=-1$ then ${\mathbf{w}}^T\mathbf{x_i}+b < 0$, so we have:
$$ \begin{cases} {\mathbf{w}}^T\mathbf{x_i}+b \ge +1, \ y_i = +1 \\ {\mathbf{w}}^T\mathbf{x_i}+b \le -1, \ y_i = -1 \end{cases} \tag{1} $$The formula above can be combined into: $y_i({\mathbf{w}}^T\mathbf{x_i}+b) \ge 1, i=1,2,...,m$
For the few training sample points closest to the hyperplane, equation (1) holds with equality; these sample points are called “support vectors”, and the sum of the distances from the two support vectors of different classes to the hyperplane is:
$$\gamma = \frac{2}{\Vert\mathbf{w}\Vert}$$which is called the “margin”
SVM finds the dividing hyperplane with the maximum margin, that is, it satisfies the following:
$$ \begin{aligned} \min_{\mathbf{w},b} & \frac{1}{2}||\mathbf{w}||^2 \\ s.t. & \ y_i({\mathbf{w}}^T\mathbf{x_i}+b) \ge 1, i=1,2,...,m \end{aligned} \tag{2} $$The formula above is the basic form of SVM
Applying the Lagrange multiplier method to (2) gives:
$$ L(\mathbf{w},b,\mathbf{\alpha}) = \frac{1}{2}{\Vert\mathbf{w}\Vert}^2 + \sum_{i=1}^m \alpha_i(1-y_i({\mathbf{w}}^T\mathbf{x_i}+b)) \tag{3} $$where $\alpha = (\alpha_1;\alpha_2;...;\alpha_m)$. Setting the partial derivatives of $L(w,b,\alpha)$ with respect to w and b to 0:
$$ \begin{aligned} \frac{\partial L(\mathbf{w},b,\mathbf{\alpha})}{\partial \mathbf{w}} \ = \mathbf{w} - \sum_{i=1}^m \alpha_iy_i\mathbf{x_i} = 0 \\ \frac{\partial L(\mathbf{w},b,\mathbf{\alpha})}{\partial b} \ = 0+\sum_{i=1}^m \alpha_iy_i = 0 \end{aligned} $$then we obtain:
$$ \begin{aligned} \mathbf{w} = \sum_{i=1}^m \alpha_iy_i\mathbf{x_i} \\ 0 = \sum_{i=1}^m \alpha_iy_i \end{aligned} \tag{4} $$Substituting (4) into (3) gives:
$$ \begin{aligned} L(\mathbf{w},b,\mathbf{\alpha}) & = \frac{1}{2}{\mathbf{w}}^T\mathbf{w}+\sum_{i=1}^m \alpha_{1} -\sum_{i=1}^m \alpha_iy_i{\mathbf{w}}^T\mathbf{x_i}-\sum_{t=1}^m \alpha_iy_ib \\ & =\frac{1}{2}\sum_{i=1}^m \alpha_iy_i{\mathbf{x_i}}^T\cdot\sum_{j=1}^m \alpha_jy_j\mathbf{x_j}+\sum_{i=1}^m \alpha_i-\sum_{i=1}^m \sum_{j=1}^m \alpha_iy_i\alpha_jy_j{\mathbf{x_j}}^T\mathbf{x_i} \\ & =\sum_{i=1}^m \alpha_i + \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m \alpha_iy_i\alpha_jy_j{\mathbf{x_i}}^T\mathbf{x_j}-\sum_{i=1}^m \sum_{j=1}^m \alpha_iy_i\alpha_jy_j{\mathbf{x_j}}^T\mathbf{x_i} \\ & =\sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m \alpha_iy_i\alpha_jy_j{\mathbf{x_i}}^T\mathbf{x_j} \end{aligned} $$so we have:
$$ \begin{aligned} \max_\mathbf{\alpha} & \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m \alpha_i\alpha_jy_iy_j\mathbf{x_i}^T\mathbf{x_j} \\ s.t. & \sum_{i=1}^m \alpha_iy_i=0, \\ & \alpha_i \ge 0, i=1,2,...,m \end{aligned} \tag{5} $$After solving for $\mathbf{\alpha}$, $\mathbf{w}$ and $\mathbf{b}$ are obtained and the model is as follows:
$$ f(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+b=\sum_{i=1}^m \alpha_iy_i{\mathbf{x_i}}^T\mathbf{x}+b $$Solving (5) usually uses the SMO algorithm to obtain the value of $\mathbf{\alpha}$, after which b is computed with (6):
$$ b = \frac{1}{\vert{S}\vert}\sum_{s \in S}(\frac{1}{y_c}-\sum_{i \in s}\alpha_iy_i{\mathbf{x_i}}^T\mathbf{x_s}) \tag{6} $$Kernel trick
In the discussion above we assumed the data is linearly separable, but real data is in most cases not linearly separable. For this reason we can consider applying a mapping to the original data to make it linearly separable, and then hand it to the SVM model for training. Specifically:
Suppose the mapping function is $\phi(\mathbf{x})$; then: $f(\mathbf{x})={\mathbf{w}}^T\phi(\mathbf{x})+b$
$$ \begin{aligned} \min_{\mathbf{w},b} & \frac{1}{2}||\mathbf{w}||^2 \\ s.t. & \ y_i({\mathbf{w}}^T\phi(\mathbf{x_i})+b) \ge 1, i=1,2,...,m \end{aligned} $$Its dual problem is:
$$ \begin{aligned} \max_\mathbf{\alpha} & \sum_{i=1}^m \alpha_i-\frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m \alpha_i\alpha_jy_iy_j\phi(\mathbf{x_i})^T\phi(\mathbf{x_j}) \\ s.t. & \ \sum_{i=1}^m \alpha_iy_i=0 \\ & \alpha_i \ge 0, i=1,2,...,m \end{aligned} $$The term $\phi(\mathbf{x_i})^T\phi(\mathbf{x_j})$ appearing in the formula above can be replaced by a function $k(\mathbf{x_i},\mathbf{x_j})$, namely the kernel function
$$k(\mathbf{x_i},\mathbf{x_j})=\langle \phi(\mathbf{x_i}),\phi(\mathbf{x_j}) \rangle=\phi(\mathbf{x_i})^T\phi(\mathbf{x_j})$$so we have:
$$ \begin{aligned} \max_\mathbf{\alpha} & \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i-1}^m \sum_{j=1}^m \alpha_i\alpha_jy_iy_jk(\mathbf{x_i},\mathbf{x_j}) \\ s.t. & \ \sum_{i=1}^m \alpha_iy_i = 0, \\ & \alpha_i \ge 0, i=1,2,..,m \end{aligned} $$After solving:
$$ \begin{aligned} f(x) & ={\mathbf{w}}^T\phi(\mathbf{x})+b \\ & =\sum_{i=1}^m \alpha_iy_i\phi(\mathbf{x_i})^T\phi(\mathbf{x_j})+b \\ & =\sum_{i=1}^m \alpha_iy_ik(\mathbf{x},\mathbf{x_i})+b \end{aligned} $$Commonly used kernel functions:
| Name | Expression | Parameters |
|---|---|---|
| Linear kernel | $k(\mathbf{x_i},\mathbf{x_j})=\mathbf{x_i}^T\mathbf{x_j}$ | |
| Polynomial kernel | $k(\mathbf{x_i},\mathbf{x_j})=(\mathbf{x_i}^T\mathbf{x_j})^d$ | $d \ge 1$, the degree of the polynomial |
| Gaussian kernel | $k(\mathbf{x_i},\mathbf{x_j})=exp(-\frac{\Vert\mathbf{x_i}-\mathbf{x_j}\Vert^2}{2\sigma^2})$ | $\sigma \gt 0$, the bandwidth of the Gaussian kernel |
| Laplacian kernel | $k(\mathbf{x_i},\mathbf{x_j})=exp(-\frac{\Vert\mathbf{x_i}-\mathbf{x_j}\Vert}{\sigma})$ | $\sigma \gt 0$ |
| Sigmoid kernel | $k(\mathbf{x_i},\mathbf{x_j})=tanh(\beta \mathbf{x_i}^T\mathbf{x_j}+\theta)$ | tanh is the hyperbolic tangent function, $\beta \gt 0$, $\theta \gt 0$ |
Usual choices:
The linear kernel is generally used for linearly separable data or text data
The Gaussian kernel is generally used when the data is not linearly separable or the data situation is unclear
Regularization of SVM
To prevent overfitting, we usually use the soft margin support vector machine, which allows some samples to fall inside the margin; the model equation is then:
$$ \min_{\mathbf{w},b} \frac{1}{2}{\Vert\mathbf{w}\Vert}^2+C\sum_{i=1}^m l_{0/1}(y_i({\mathbf{w}}^T\mathbf{x_i}+b)-1) \tag{7} $$where C>0 is a constant and $l_{0/1}$ is the 0/1 loss function:
$$ l_{0/1}(z)=\begin{cases} 1, \ \text{if } \ z \le 0; \\ 0, \ \text{otherwise} \end{cases} $$Other functions are usually used to replace $l_{0/1}$, as follows:
$$ \begin{cases} \text{hinge loss: } \ l_{hinge}(z)=\max(0,1-z); \\ \text{exponential loss: } \ l_{exp}(z)=exp(-z); \\ \text{logistic loss: } \ l_{log}(z)=log(1+exp(-z)) \end{cases} $$Referring to (7), the more general form is:
$$\min_f \Omega(f)+C\sum_{i=1}^m l(f(\mathbf{x_i}),y_i)$$where $\Omega(f)$ is the structural risk, used to describe certain properties of the model f ($\Omega(f)$ can also be called the regularization term, commonly $L_0, L_1, L_2$ regularization), and the second term $\sum_{i=1}^m l(f(\mathbf{x_i}),y_i)$ is the empirical risk, used to describe how well the model fits the training data, with C striking a balance between the two.
Use in Scikit-learn
See the official Scikit-learn site for the concrete API:
Reference
Zhou Zhihua’s Watermelon Book and Li Hang’s Statistical Learning Methods