机器学习之支持向量机（SVM）

SVM

SVM 即支持向量机，常用于二分类模型。它主要的思想是：

它是特征空间上间隔最大的线性分类器。
对于线性不可分的情况，通过非线性映射算法将低维空间的线性不可分的样本映射到高维特征空间，高维特征空间能够进行线性分析。

结构风险

对于指定的损失函数，根据一定的样本集就能根据这些样本来计算经验风险，而经验风险最小化就是根据样本集来最小化经验风险。

假如我们能获取到所有数据，那么我们希望整个数据集的损失能越小越好，这就表示模型越好。但很多时候基本不可能获取到所有数据，这时就可以根据样本的联合分布P(X,Y)来计算期望风险：

$R_{exp}(f) = E[L[Y,f(X)]] = \int L(Y,f(X))P(x,y)dxdy$

可以看到当样本数趋于无穷大时，经验风险会趋于期望风险。实际情况下，我们的训练样本很有限，如果完全只考虑经验风险，则可能会出现过拟合现象，这时它能很好预测训练样本，但其泛化能力有限，对非训练数据预测能力可能不好。为了克服这个问题，引入了结构风险。

结构风险 = 经验风险 + 置信风险。置信风险可以是一个正则化项，这种做法叫正则化，正则化项与模型的复杂程度相关，复杂度越高则正则化的值越大。常用的正则化项是模型参数的范数。

$R = R_{exp} + \lambda J(f)$

此外，如果不使用结构风险，则可以使用交叉验证的思想来综合考虑所有训练出来的模型，越能准确预测验证集的模型就表示越好。

间隔最大化

从感性上理解支持向量机，如下图，假设有两种不同类别的数据，分布在空间上，支持向量机的任务就是找到一个划分超平面，将它们分割成两类，所以我们看到其实是不止存在一个超平面可以对其进行划分的，到底哪一个才是最好的呢？这就需要我们根据一定的约束条件去找出这个最好的超平面。

对于给定的样本集 $T=\{(x_1,y_1),(x_2,y_2)...,(x_n,y_n)\}$ ，其中 $y_i \in Y=\{+1,-1\}$ ，它表示类标记，分别用+1和-1表示。我们设超平面对应方程为

$w^Tx + b =0$

其中w为法向量，b为位移项，超平面由法向量（决定方向）和位移项（决定超平面与原点距离）共同决定。那么样本对应的点到超平面的距离为，

$l = \frac{|w^T+b|}{||w||}$

在所有样本都能正确被超平面划分的情况下，则样本集T中，对于 $y_i=+1$ 则有 $w^Tx + b >0$ ，反之对于 $y_i=-1$ 则有 $w^Tx + b <0$ 。

超平面两边分别存在离超平面最近的一些样本点（这些点称为支持向量），如图中中间的超平面向两边平移后得到两个超平面，对应的方差分别为

$w^Tx + b =1$

$w^Tx + b =-1$

这两个超平面的距离即称为间隔，在这两个超平面的样本点到中间超平面的距离之和为

$l = \frac{2}{||w||}$

现在我们的任务是在约束条件下找到最大的间隔，即要找到w和b使得l最大，

$\underset{w,b}{max} \quad l$

$s.t.\ y_i(w^Tx_i+b) \ge 1 ,\ i=1,2,...,n$

其实就是最大化 $\frac{1}{||w||}$ ，等价于最小化 $\frac{1}{2}||w||^2$ ，于是上述优化问题变为，

$\underset{w,b}{min} \quad \frac{1}{2}||w||^2$

$s.t.\ y_i(w^Tx_i+b) \ge 1 ,\ i=1,2,...,n$

解除该优化问题即得到最大间隔分离超平面。

对偶问题

上面的优化问题是凸二次规划问题，一般可用拉格朗日方法求解。首先引入拉格朗日函数，要求 $a_i \ge 0$ ，

$L(w,b,a)=\frac{1}{2}||w||^2 +\sum^n_{i=1}a_i(1-y_i(w^Tx_i+b))$

其中 $a= (a_1,a_2,...a_n)^T$ 为拉格朗日乘子向量。

为求得对偶问题的解，需要先求拉格朗日函数对w、b的极小，再求拉格朗日函数对a的极大，即 $\underset{a}{max} \ \underset{w,b}{min} L(w,b,a)$ 。

求极小则对w，b求偏导并令其为0，有

$\triangledown_w L(w,b,a) = w - \sum^n_{i=1}a_iy_ix_i =0$

$\triangledown_b L(w,b,a) = \sum^n_{i=1}a_iy_i =0$

综合上述几个式子，将w代回原来的式子可以将w和b消掉，于是拉格朗日函数对a求极大变为，

$\underset{a}{max} \ \sum^n_{i=1}a_i -\frac{1}{2}\sum^n_{i=1}\sum^n_{j=1}a_ia_jy_iy_jx_i^Tx_j$

$s.t. \ \sum^n_{i=1}a_iy_i =0$

$a_i \ge0, i=1,2,...,n$

解上述方程可以用二次规划算法求解，也可以用数值方法求解，或者用SMO算法。解得a后就能解得w和b。

另外，还有一个很重要的约束， $a_i(y_i(wx_i+b)-1)=0$ ，可以看到对于任意样本 $(x_i,y_i)$ ，总满足 $a_i=0$ 或 $y_i(wx_i+b)=1$ 。当对应的拉格朗日系数为非0时，这个样本是一个支持向量，当对应拉格朗日系数为0时，这个样本不是支持向量，由此也可知大多数拉格朗日系数都是0，因为大多数样本都不是支持向量。