SVM，即支持向量机，是一个常用的二分类机器学习方法。通过一些变换，也可以进行多分类和回归建模。其引入核函数，可以很好的应用于非线性可分场景，且对于高维数据，避免了维灾难问题。同时，其泛化性能好，适用于小数据集，决定决策边界的样本只是训练集的一个子集，称为“支持向量”。所以，当训练集样本较少时，SVM泛化性能依然很好。
1. 线性可分
我们以最简单的二分类为例。什么是线性可分？如图所示，红色和绿色分别代表两类样本。我们说该数据集是线性可分的，即可以找到这样一个超平面，使得所有红色的样本在一侧，所有绿色的样本在另外一侧，超平面能完全分割开两类样本。正如图1所示，这样的超平面有无穷多个，它们在训练样本上的误差均为0，那么我们应该选择怎样的超平面呢？
1.1 边缘
对于线性可分二分类问题，任意一个决策边界都可以往两边平移，直到最近的一个样本点落到平移后的决策边界上。则两个平移后的决策边界之间的距离就称为“边缘”。
1.2 最大边缘超平面
直观上，具有较大边缘的决策边界泛化性能更好。因为如果边缘较小，则决策边界附近轻微的噪声扰动都可能对分类产生显著的影响，从而在未知样本上泛化性能很差。理论上证明（待补充，没必要深究）
简单起见，以线性可分的二分类为例。假设训练集有$m$个样本${ (\boldsymbol{x}_1, y_1),(\boldsymbol{x}_2, y_2),…,(\boldsymbol{x}_m,y_m)}$。其中，$y_i\in\{-1, 1\}$(方便数学上的处理)。
则一个决策边界可以表示为：
$$\boldsymbol{w}^T \boldsymbol{x} + b = 0$$
优化目标为最大化决策边缘，即损失函数可以表示为：
$$\begin{aligned}
L=\max_{\boldsymbol{w},b}&\frac{1}{||\boldsymbol{w}||} \\
\text{subject to}\;\;y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)\ge&1, i=1,2,…,m.
\end{aligned}$$
等价于
$$\begin{aligned}
L=\min_{\boldsymbol{w},b}\frac{1}{2}&||\boldsymbol{w}||^2 \\
\text{subject to}\;\;y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)\ge&1, i=1,2,…,m.
\end{aligned}$$
1.3 对偶问题
这里涉及定理证明，数学优化问题，比较复杂，所以直接使用对偶问题求解结论
这样做的好处：
- 对偶问题往往更容易求解；
- 自然引入核函数，进而推广到非线性分类问题中；
- 避免了维灾难问题。
注意到式为一个凸二次规划(convex quadratic programming)问题。引入拉格朗日乘子向量$\boldsymbol{\alpha}$，其中$\boldsymbol{\alpha}=(\alpha_1, \alpha_2,…,\alpha_m)$，$\alpha_i\ge0$。定义拉格朗日函数：
$$\min_{\boldsymbol{w},b}\max_{\alpha}L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}||\boldsymbol{w}^2||-\sum_{i=1}^m \alpha_i(y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)-1)$$
对偶问题：$$\max_{\alpha}\min_{\boldsymbol{w},b}L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}||\boldsymbol{w}^2||-\sum_{i=1}^m \alpha_i(y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)-1)$$
在KKT条件下，原始问题和对偶问题解相同。KKT条件：
$$y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)-1\ge0, i=1,2,…,m.$$
$$\alpha_i(y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)-1)=0, i=1,2,…,m.$$
$$\alpha_i\ge0,i=1,2,…,m.$$
令$L(\boldsymbol{w},b,\boldsymbol{\alpha})$对$\boldsymbol{w}$和$b$的偏导数为0，可得：
$$\frac{\partial{L}}{\partial{w}}=\boldsymbol{w}-\sum_{i=1}^m\alpha_iy_i\boldsymbol{x}_i=0$$
$$\frac {\partial{L}} {\partial{b}} = - \sum_{i=1}^m \alpha_i y_i = 0$$
从而可得：
$$
\boldsymbol{w} = \sum_{i=1}^m \alpha_i y_i \boldsymbol{x}_i
$$
$$
0 =\sum_{i=1}^m \alpha_i y_i
$$
将式带入式，即可将$L(\boldsymbol{w},b,\boldsymbol{\alpha})$中的$\boldsymbol{w}$和$b$消去，得对偶问题：
$$\begin{aligned}
\max L(\boldsymbol{\alpha}) &= \sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j \\
&\alpha_i\ge0,i=1,2,…,m \\
&\text{subject to}\;\;\sum_{i=1}^{m} \alpha_i y_i=0
\end{aligned}$$
支持向量是使约束条件等号成立的点。最大边缘超平面由支持向量决定，所以SVM由很少的训练样本确定。
1.4 SMO
( Sequential Minimal Optimization )[Platt, 1998]待补充，求解方法
2. 线性不可分
2.1 松弛变量&软间隔
引入松弛变量$\xi_i$，$\xi_i\ge0$。则约束条件变为：$y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)\ge1-\xi_i, i=1,2,…,m.$
则目标函数修改为：
$$\begin{aligned}
L=\min_{\boldsymbol{w},b}\frac{1}{2}&||\boldsymbol{w}||^2 + C\sum_{i=1}^m\xi_i \\
\text{subject to}\;\;y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)\ge&1, i=1,2,…,m. \\
\xi_i\ge&0,i=1,2,…,m \\
C\ge&0
\end{aligned}$$
3. 非线性可分
3.1 核函数
引入核函数：$K(\boldsymbol{x_1},\boldsymbol{x_2})$，对于非线性变换：$\phi(\boldsymbol{x})$，使得$K(\boldsymbol{x_1},\boldsymbol{x_2})=\phi(\boldsymbol{x_1})\phi(\boldsymbol{x_2})$
- 线性核
- 多项核
- 高斯核
- 拉普拉斯核
- Sigmoid核
4. Refereneces
- The Elements of Statistical Learning : Data Mining, Inference, and Prediction, Trevor Hastie, Robert Tibshirani, Jerome Friedman
- Pattern Recognition and Machine Learning, Christopher Bishop