统计学习方法——第7章支持向量机（个人笔记）

参考《统计学习方法》（第二版）李航

支持向量机（support vector machines，SVM）是一种二分类模型，是定义在特征空间上的间隔最大的线性分类器。间隔最大使他有别于感知机。

7.1 线性可分支持向量机与硬间隔最大化

7.1.1 线性可分支持向量机

一般来说，当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开。

感知机利用误分类最小的策略，求得分离超平面，不过解有无穷多个。

线性可分支持向量机利用间隔最大化求最优分离超平面，这时解是唯一的。

定义 7.1 （线性可分支持向量机）

给定线性可分训练数据集，通过间隔最大化求解而得到的分离超平面为

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

对应的分类决策函数

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

称为线性可分支持向量机。

7.1.2 函数间隔和集合间隔

一个点距离分离超平面的远近可以表示分类预测的确信程度。

定义 7.2 （函数间隔）

给定数据集T和超平面（w,b），则超平面（w,b）和样本点
$(x_i,y_i)$
的函数间隔为

$\hat{\gamma}_i=y_i(w\cdot x_i+b)$

定义所有样本点的函数间隔的最小值为

$\hat{\gamma}=\min \hat{\gamma}_i$

由于2w和2b没有改变超平面，但改变了函数间隔，需要对w加约束，如规范化。

定义7.3 （几何间隔）

对于给定的训练数据集T和超平面（w,b）,则超平面（w,b）和样本点
$(x_i,y_i)$
的几何间隔为

$\gamma_i=y_i\left ( \frac{w}{||w||}\cdot x_i+\frac{b}{||w||} \right )$

则所有样本点的几何间隔的最小值为

$\gamma=\min \gamma_i$

7.1.3 间隔最大化

所谓间隔最大化，就是不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将他们分开。

1.最大间隔分离超平面

最优化问题为

$\max_{w,b} \gamma \\subject\ to\ y_i\left ( \frac{w}{||w||}\cdot x_i+\frac{b}{||w||} \right )\geq \gamma$

化为

$\max_{w,b} \frac{\hat{\gamma} }{||w||}\\subject\ to\ y_i\left ( w\cdot x_i+b \right )\geq \hat{\gamma}$

令函数间隔
$\hat{\gamma}=1/2$
，得到

线性支持向量机学习的最优化问题

$\min_{w,b} \frac{1}{2}||w||\\subject\ to\ y_i\left ( w\cdot x_i+b \right )-1\geq 0$

算法 7.1 (最大间隔法)

输入：线性可分训练数据集

输出：最大间隔分离超平面和分类决策函数

（1）最优化问题

$\min_{w,b} \frac{1}{2}||w||\\subject\ to\ y_i\left ( w\cdot x_i+b \right )-1\geq 0$

求得最优解
$w^*,b^*$
。

（2）由此得到分离超平面：

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

分类决策函数

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

2.最大间隔分离超平面的存在唯一性

3.支持向量和间隔边界

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。

直线H1和H2之间的距离称为间隔，则H1和H2称为间隔边界

例子

7.1.4 学习的对偶算法

对偶算法：应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解。

优点：

①更容易求解

②引入核函数，从而推广到非线性分类。

首先定义拉格朗日函数：

$L(w,b,a)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\alpha _iy_i(w\cdot x_i+b)+\sum_{i=1}^{N}\alpha _i$

其中，α为拉格朗日乘子。

则问题变为极大极小问题：

$\max_{\alpha}\min_{w,b}L(w,b,\alpha)$

对w，b求极小，对α求极大：

（1）求
$\min_{w,b}L(w,b,\alpha)$

对w，b求偏导，

$\bigtriangledown _wL(w,b,\alpha)=w-\sum_{i=1}^{N}\alpha_i y_i x_i=0$

$\bigtriangledown _bL(w,b,\alpha)=-\sum_{i=1}^{N}\alpha_iy_i=0$

代入拉格朗日函数中，

$L(w,b,\alpha)=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_iy_i((\sum_{j=1}^{N}\alpha_jy_jx_j)\cdot x_i+b)+\sum_{i=1}^{N}\alpha_i \\ =-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^{N}\alpha_i$