SVM是机器学习里面一个非常重要的模型，它是由统计学习理论之父弗拉基米尔·瓦普尼克提出的
本文以SVM二分类为例
推导过程
给定训练数据集$D=\\{(\mathbf{x_1},y_1),(\mathbf{x_2},y_2),...,(\mathbf{x_m},y_m)\\}, y_i \in \\{-1, +1\\}$，分类器最基本的想法就是基于训练集D在样本空间中找到一个划分空间，将不同类别的样本分开。划分超平面可用如下的线性方程描述：
$$ {\mathbf{w}}^T\mathbf{x}+b=0$$其中$\mathbf{w}=(w_1;w_2;...;w_d)$为法向量，决定了超平面的方向，b为偏移项，决定了超平面与原点之间的距离，可知超平面有w和d决定。则有空间中任意点到超平面(w,b)的距离为：
$$\gamma = \frac{\vert{\mathbf{w}}^T\mathbf{x}+b\vert}{\Vert\mathbf{w}\Vert}$$假设超平面(w,b)将样本完全分类正确，即对于$(\mathbf{x_i}, y_i) \in D$，若$y_i=+1$则有${\mathbf{w}}^T\mathbf{x_i}+b > 0$; 若$y_i=-1$，则有${\mathbf{w}}^T\mathbf{x_i}+b < 0$，故有：
$$ \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} $$上式可以合并为：$y_i({\mathbf{w}}^T\mathbf{x_i}+b) \ge 1, i=1,2,...,m$
在距离超平面最近的几个训练样本点使(1)式等号成立，这些样本点被称为“支持向量”，两个异类支持向量到超平面的距离之和为：
$$\gamma = \frac{2}{\Vert\mathbf{w}\Vert}$$它被称为“间隔”
SVM则是找到具有最大间隔的划分超平面，即满足下式：
$$ \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} $$上式即为SVM基本型
对(2)使用拉格朗日乘数法可得下式：
$$ 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} $$其中$\alpha = (\alpha_1;\alpha_2;...;\alpha_m)$，令$L(w,b,\alpha)$对w，b的偏导数为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} $$则可得下式：
$$ \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} $$将(4)式代入(3)有：
$$ \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} $$则有下式：
$$ \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} $$解出$\mathbf{\alpha}$后，求出$\mathbf{w}$, $\mathbf{b}$即可得到模型如下：
$$ f(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+b=\sum_{i=1}^m \alpha_iy_i{\mathbf{x_i}}^T\mathbf{x}+b $$求解(5)式通常采用的是SMO算法得出$\mathbf{\alpha}$的值，再由(6)式计算b的值：
$$ 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} $$核技巧
在前面的讨论中，我们假设了数据是线性可分的，但现实数据大多数情况下并非线性可分。为此，我们可以考虑对原始数据做一个映射，使其线性可分，之后再交由SVM模型训练。具体如下：
假设映射函数为$\phi(\mathbf{x})$，则有：$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} $$其对偶问题为：
$$ \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} $$对于以上式子出现的$\phi(\mathbf{x_i})^T\phi(\mathbf{x_j})$可用一个函数来替代$k(\mathbf{x_i},\mathbf{x_j})$，即为核函数
$$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})$$故有：
$$ \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} $$求解后有：
$$ \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} $$常用的核函数：
| 名称 | 表达式 | 参数 |
|---|---|---|
| 线性核 | $k(\mathbf{x_i},\mathbf{x_j})=\mathbf{x_i}^T\mathbf{x_j}$ | |
| 多项式核 | $k(\mathbf{x_i},\mathbf{x_j})=(\mathbf{x_i}^T\mathbf{x_j})^d$ | $d \ge 1$，为多项式次数 |
| 高斯核 | $k(\mathbf{x_i},\mathbf{x_j})=exp(-\frac{\Vert\mathbf{x_i}-\mathbf{x_j}\Vert^2}{2\sigma^2})$ | $\sigma \gt 0$，为高斯核的带宽 |
| 拉普拉斯核 | $k(\mathbf{x_i},\mathbf{x_j})=exp(-\frac{\Vert\mathbf{x_i}-\mathbf{x_j}\Vert}{\sigma})$ | $\sigma \gt 0$ |
| Sigmoid核 | $k(\mathbf{x_i},\mathbf{x_j})=tanh(\beta \mathbf{x_i}^T\mathbf{x_j}+\theta)$ | tanh为双曲正切函数，$\beta \gt 0$，$\theta \gt 0$ |
通常的选择：
线性核一般用于线性可分的数据或文本数据
高斯核一般用于线性不可分或数据情况不明的时候
SVM的正则化
为了防止过拟合，我们通常采用软间隔支持向量机，即允许有某些样本在间隔内，则模型方程为：
$$ \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} $$其中C>0是一个常数，$l_{0/1}$为0/1损失函数：
$$ l_{0/1}(z)=\begin{cases} 1, \ \text{if } \ z \le 0; \\ 0, \ \text{otherwise} \end{cases} $$通常用其它函数替换$l_{0/1}$，如下：
$$ \begin{cases} \text{hinge损失: } \ l_{hinge}(z)=\max(0,1-z); \\ \text{指数损失: } \ l_{exp}(z)=exp(-z); \\ \text{对率损失: } \ l_{log}(z)=log(1+exp(-z)) \end{cases} $$参考(7)式，更一般的形式为：
$$\min_f \Omega(f)+C\sum_{i=1}^m l(f(\mathbf{x_i}),y_i)$$其中$\Omega(f)$为结构风险，用于描述模型f的某些性质（$\Omega(f)$又可称为正则化项，常用的有$L_0,L_1,L_2$正则化），第二项$\sum_{i=1}^m l(f(\mathbf{x_i}),y_i)$为经验风险，由于描述模型与训练数据的契合程度，C由于两者进行折中。
Scikit-learn应用
具体API参考Skicit-learn官网：
参考
周志华的西瓜书，李航的统计学习方法