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官网：
致谢
周志华的西瓜书，李航的统计学习方法