《统计学习方法》第七章：支持向量机

支持向量机是一种与感知机相似的二分类模型，但感知机的学习策略仅仅是使线性可分的两类实例区分开来，而支持向量机使用的是间隔最大化策略。间隔最大化使支持向量机不仅能完成二分类任务，同时使支持向量机具有更加良好的可信度和预测功能。

训练数据	策略	模型
线性可分	硬间隔最大化	线性可分支持向量机
近似线性可分	软间隔最大化	线性支持向量机
线性不可分	核技巧、软间隔最大化	非线性支持向量机

线性可分支持向量机

模型

支持向量机的模型与感知机类似，分离超平面为

$$w^*\cdot x+b^*=0$$

分类决策函数为

$$f(x)=\mathrm{sign}(w^*\cdot x+b^*)$$

策略

函数间隔与几何间隔

实例到超平面的距离能相对地用 $|w\cdot x+b|$ 衡量，称为函数间隔。样本点到超平面的函数间隔记作 $\hat{\gamma}_i$，将数据集 $T$ 中所有样本点函数间隔的最小值称为超平面关于数据集 $T$ 的函数间隔，记作 $\hat{\gamma}$。

函数间隔会随着超平面参数 $w$ 与 $b$ 的改变而改变，但若 $w$ 与 $b$ 等比例缩放，超平面没有变化（等式左右可同时约去比例），样本点到超平面距离没有变化，而函数间隔变化了。

这说明需要将函数间隔规范化，也就得到了几何间隔 $\frac{w}{||w||}$，这也就是样本点到超平面的实际（几何）距离，记作 $\gamma_i$，类似地，超平面关于数据集的几何间隔记作 $\gamma$，得到转化公式

$$\begin{align} \gamma_i=\frac{\hat{\gamma}_i}{||w||}\\ \gamma=\frac{\hat{\gamma}}{||w||} \end{align}$$

间隔最大化

不同于感知机，间隔最大化的策略不仅用超平面将两类样本点分开，还要使不同类别的样本点的几何距离超平面最大，这样的做法使得超平面有足够的确信度将两类样本分开。

再回忆一下感知机，感知机仅仅将线性可分的样本点分开，因此运算过程中取样本点的顺序不同，会得到不同的结果，当然这些不同的结果都能分开两类样本。但支持向量机采用了间隔最大化策略，几何间隔最大的分离超平面是唯一的，最后也就得到唯一且最优的模型。

间隔最大化策略使得分离超平面的确定只依赖于最靠近超平面的样本点，这些实例点就称为支持向量。

根据间隔最大化的思路，可以得到以下最优化问题：

$$\begin{align} \max_{w,b}&\quad \frac{\hat{\gamma}}{||w||}\\ \mathrm{s.t.}&\quad y_i\frac{w\cdot x+b}{||w||}\geqslant \frac{\hat{\gamma}}{||w||} \end{align}$$

等比缩放 $w$ 与 $b$ 将得到 $\lambda \hat{\gamma}$，但超平面没有改变，几何间隔也没有改变，也就是说只需要考虑 $\frac{1}{||w||}$，略去 $\hat{\gamma}$ 得到

$$\begin{align} \max_{w,b}&\quad \frac{1}{||w||}\\ \mathrm{s.t.}&\quad y_i(w\cdot x+b)\geqslant 1 \end{align}$$

将该最优化问题转化为最小化问题：

$$\begin{align} \min_{w,b}&\quad \frac{1}{2}||w||^2\\ \mathrm{s.t.}&\quad y_i(w\cdot x+b)-1\geqslant 0 \end{align}$$

Note 最大化 $\frac{1}{||w||}$ 等价于最小化 $||w||^2$，当然前面的常数项更是无所谓的。

算法

原始算法

算法 7.1

输入：线性可分的数据集
输出：最大间隔分离超平面和分离决策函数

构造求解最优化问题得到最优解 $w^*$ 与 $b^*$（解不等式组）；
$$\begin{align} \min_{w,b}&\quad \frac{1}{2}||w||^2\\ \mathrm{s.t.}&\quad y_i(w\cdot x+b)-1\geqslant 0 \end{align}$$
得到分离超平面与决策函数。

对偶算法

对偶算法同样依赖于 Lagrange 函数（见第六章），构造 lagrange 函数：

$$\begin{align} L(w,b,\alpha)&=\frac{1}{2}||w||^2-\sum_i\alpha_i[y_i(w\cdot x+b)-1]\\ &=\frac{1}{2}||w||^2-\sum_i\alpha_iy_i(w\cdot x+b)+\sum_i\alpha_i \end{align}$$

求对偶问题的极小 $\min_{w,b}L(w,b,\alpha)$：

求 Lagrange 函数对 $w$ 与 $b$ 的偏导并令其为零：

$$\frac{\partial L}{w}=w-\sum_i\alpha_iy_ix_i=0$$

$$\frac{\partial L}{b}=-\sum_i\alpha_iy_i=0$$

将 $w=\sum_i\alpha_iy_ix_i$ 代入 Lagrange 函数，为简洁起见，先只考虑 $\frac{1}{2}||w||^2$ 一项：

$$\begin{align} \frac{1}{2}||w||^2&=\frac{1}{2}x^\mathrm{T}\cdot x\\ &=\frac{1}{2}\left(\sum_i\alpha_iy_ix_i\right)\cdot\left(\sum_j\alpha_jy_jx_j\right)\\ &=\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) \end{align}$$

再考虑到 $b\sum_i\alpha_iy_i=0$ 那么 Lagrange 函数应当为

$$\begin{align} L(w,b,\alpha)&=\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_i\alpha_iy_i\left(\sum_j\alpha_jy_jx_j\cdot x_i\right)+\sum_i\alpha_i\\ &=-\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_i\alpha_i \end{align}$$

对偶问题的极小也就是 $-\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_i\alpha_i$。

求对偶问题极小的极大 $\max_{\alpha}\min_{w,b}L(w,b,\alpha)$：

$$\begin{align} \max_{\alpha}&\quad -\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_i\alpha_i\\ \mathrm{s.t.}&\quad \sum_i\alpha_iy_i=0,\ \alpha_i\geqslant0 \end{align}$$

转化为极小问题

$$\begin{align} \min_{\alpha}&\quad \frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_i\alpha_i\\ \mathrm{s.t.}&\quad \sum_i\alpha_iy_i=0,\ \alpha_i\geqslant0 \end{align}$$

假设该问题的解为 $\alpha^*=(\alpha^*_1,\alpha^*_2,\cdots,\alpha^*_N)^\mathrm{T}$，那么支持向量机的参数（从 KKT 条件导出）为

$$\begin{align} &w^*=\sum_i\alpha^*_iy_ix_i\\ &b^*=y_j-\sum_i\alpha^*_iy_i(x_i\cdot x_j) \end{align}$$

可以看出，若 $\alpha_i=0$，参数与该分量无关，也就是说该分量所对应的样本点不影响支持向量机。从另一方面看，支持向量机只与 $\alpha_i>0$ 对应的样本点有关，这些样本点就是支持向量。

算法 7.2

输入：线性可分的数据集
输出：最大间隔分离超平面和分离决策函数

构造并求解问题得到 $\alpha^*$
$$\begin{align} \min_{\alpha}&\quad \frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_i\alpha_i\\ \mathrm{s.t.}&\quad \sum_i\alpha_iy_i=0,\ \alpha_i\geqslant0 \end{align}$$
用 $\alpha^*$ 计算 $w^*$，用 $\alpha^*$ 的正分量计算 $b^*$;
得到分离超平面与决策函数。

对偶算法案例

在算法 7.2 的第 1 步中，需要求解 $\alpha^*$，这里容易令人困惑，以书中的例子说明计算方法。

正例点为 $x_1=(3,3)^\mathrm{T}$ 与 $x_2=(4,3)^\mathrm{T}$，负例点为 $x_3=(1,1)^\mathrm{T}$，求线性可分支持向量机。

先计算样本点的 Gram 矩阵，以便后续计算：

$$G=\begin{bmatrix} 18 &21 &6\\ 21 &25 &7\\ 6 &7 &2 \end{bmatrix}$$

$$\begin{align} \min_{w,b}&\quad \frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_i\alpha_i\\ &=\frac{1}{2}(18\alpha^2_1+25\alpha^2_2+2\alpha^2_3+42\alpha_1\alpha_2-12\alpha_1\alpha_3-14\alpha_2\alpha_3)-\alpha_1-\alpha_2-\alpha3\\ \mathrm{s.t.}&\quad \alpha_1+\alpha_2-\alpha_3=0,\ \alpha_i\geqslant0 \end{align}$$

为了求解这一最优化问题，需要将约束代入目标问题，得到

$$s(\alpha_1,\alpha_2)=4\alpha^2_1+\frac{13}{2}\alpha^2_2+10\alpha_1\alpha_2-2\alpha_1-2\alpha_2$$

求其偏导并令其为零，得知 $s(\alpha_1,\alpha_2)$ 在 $(\frac{3}{2},-1)^\mathrm{T}$ 处取得极值，但 $\alpha_2=-1$ 违反了 $\alpha_i\geqslant0$ 的约束，那么最小值将在边界上取到。

$$\begin{align} &a_1=0,\quad s(0,\frac{2}{13})=-\frac{2}{13}\\ &a_2=0,\quad s(\frac{1}{4},0)=-\frac{1}{4} \end{align}$$

所以计算得到最终的 $\alpha^*=(\frac{1}{4},0,\frac{1}{4})^\mathrm{T}$。

线性支持向量机

模型

线性可分支持向量机是线性支持向量机的特例，所以线性支持向量机的模型与线性可分支持向量机相同。在现实情况中，很难遇到标准的线性可分的数据，这时候就需要使用更为普遍的线性支持向量机。

策略

线性可分数据集与近似线性可分数据集的差别在于，近似线性可分数据集中存在一些特异点，若将这些特异点去除，那么数据集就变成了线性可分的。

特异点无法被正常分类的原因是特异点不能满足支持向量机的分类条件

$$\begin{align} &正例点：w\cdot x+b\geqslant1\\ &负例点：w\cdot x+b\leqslant-1 \end{align}$$

从几何上来看，也就是特异点与分离超平面的距离不够远，不能满足函数间隔大于等于 1，因此引入一个松驰变量 $\xi_i\geqslant0$，使得特异点的函数间隔加上松驰变量大于等于 1，那么最优化问题的约束就变为

$$y_i(w\cdot x_i+b)\geqslant1-\xi_i$$

原来的目标函数改为

$$\frac{1}{2}||w||^2+C\sum_i\xi_i$$

其中 $C>0$ 称为惩罚参数，目标函数使 $\frac{1}{2}||w||^2$ 尽可能小，也就是间隔尽量大；$\xi_i$ 尽可能小，也就是误分类的点（补偿的间隔）尽量少；$C$ 就是在二种策略间权衡的权重值，调和二者关系。

算法

原始算法

线性支持向量机的原始问题为

$$\begin{align} \min_{w,b}&\quad \frac{1}{2}||w||^2+C\sum_i\xi_i\\ \mathrm{s.t.}&\quad y_i(w\cdot x_i+b)\geqslant1-\xi_i,\ \xi_i\geqslant0 \end{align}$$

线性支持向量机的原始问题与线性可分支持向量机也相似，求解该问题得到分离超平面与分类决策函数。

对偶算法

从原始问题中导出对偶问题，使用同样的步骤构造 Lagrange 函数，并求其极大极小：

$$\begin{align} \min_{\alpha}&\quad \frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_i\alpha_i\\ \mathrm{s.t.}&\quad \sum_i\alpha_iy_i=0,\ 0\leqslant\alpha_i\color{orangered}{\leqslant C} \end{align}$$

可以看出线性支持向量机的原始问题只是比线性可分支持向量机多了一个约束条件，因此最终导出的结果也是相似的。求解该对偶问题得到 $\alpha^*$，求得支持向量机参数

$$\begin{align} &w^*=\sum_i\alpha^*_iy_ix_i\\ &b^*=y_j-\sum_i\alpha^*_iy_i(x_i\cdot x_j) \end{align}$$

这里需要注意的是，由于存在 $0\leqslant\alpha_i\leqslant C$ 的约束条件，需要保证 $\alpha^*$ 中各分量满足这一约束，选择其中满足 $0<\alpha_i<C$ 条件的分量计算支持向量机参数，很容易明白，满足 $0<\alpha_i<C$ 条件分量所对应的样本点就是该模型中的支持向量。

算法 7.3

输入：数据集
输出：分离超平面和分离决策函数

构造并求解问题得到 $\alpha^*$
$$\begin{align} \min_{\alpha}&\quad \frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_i\alpha_i\\ \mathrm{s.t.}&\quad \sum_i\alpha_iy_i=0,\ 0\leqslant\alpha_i\leqslant C \end{align}$$
用 $\alpha^*$ 计算 $w^*$，用 $\alpha^*$ 中满足条件 $0<\alpha_i<C$ 的分量计算 $b^*$;
得到分离超平面与决策函数。

非线性支持向量机

模型

在实际情况中，常常还会得到非线性的数据集，这时候若尝试用一个超平面将两类实例区分开，会得到大量的误分类点，这样的模型没有很好的确信度和预测性能。超平面的模型是简单的，若使用更复杂一些的超曲面，通常能取得更好的效果。

我用一个简单的例子说明这个问题，回忆中学时代的线性回归，也就是用一条直线来拟合一系列数据点，如果数据点是由二次函数产生的，断然是无法找到这条合适的直线的。此时需要将数据点经过变换，经过变换后，在另一空间中得到适合拟合的数据。

核技巧

核技巧也是同样的思路，将不适合使用超平面分类的数据集变换到另一空间中，在该空间中使用超平面分类，就相当于在原空间中使用超曲面而非超平面分类。

将这个从输入空间到特征空间的映射记作 $\phi(x)$，使得输入空间中的所有 $x,z$ 满足

$$K(x,z)=\phi(x)\cdot\phi(z)$$

就称 $K(x,z)$ 为核函数。考虑对偶问题

$$\min_{\alpha}\quad \frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j(\color{orangered}{x_i\cdot x_j})-\sum_i\alpha_i$$

将核函数代入就得到非线性支持向量机的对偶问题

$$\min_{\alpha}\quad \frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_j\color{orangered}{K(x_i,x_j)}-\sum_i\alpha_i$$

所以非线性支持向量机的分类决策函数就是

$$f(x)=\mathrm{sign}\left(\sum_i\alpha^*_iy_iK(x,x_i)+b^*\right)$$

核函数一般不用自己计算，常见的核函数有

名称	核函数
多项式核函数	$K(x,z)=(x\cdot z+1)^p$
高斯核函数	$K(x,z)=\exp\left(-\frac{\\|x-z\\|^2}{2\sigma^2}\right)$

算法

非线性支持向量机的算法与线性支持向量机无异，不过是需要预先选择合适的核函数，构造最优化问题

$$\min_{\alpha}\quad \frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_i\alpha_i$$

最后用同样的方法求解该最优化问题得到非线性支持向量机。

《统计学习方法》第七章：支持向量机

Leo

线性可分支持向量机

模型

策略

函数间隔与几何间隔

间隔最大化

算法

原始算法

对偶算法

对偶算法案例

线性支持向量机

模型

策略

算法

原始算法

对偶算法

非线性支持向量机

模型

算法

References

名称	核函数
多项式核函数	\(K(x,z)=(x\cdot z+1)^p\)
高斯核函数	\(K(x,z)=\exp\left(-\frac{\\|x-z\\|^2}{2\sigma^2}\right)\)