[机器学习西瓜书] 第06章 支持向量机 笔记
人工智能AI|计算机 ComputerScience
@ZYX 写于2020年08月10日
第06章 支持向量机
6.1 间隔与支持向量
- 训练样本集 $D=\{(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{m},y_{m})\}, y_{i} \in \{-1,+1\}$
- 最基本的想法就是基于训练集 $D$ 在样本空间中找到一个划分超平面,将不同类别分开
- 可能有很多
- 应该去找位于两类训练样本正中间的
- 因为该超平面对训练样本局部扰动的容忍性最好
- 在样本空间中，划分超平面可通过如下线性方程来描述:
[6.1] $w^{T}x+b=0$
- 法向量 $w=(w_{1};w_{2};\dots;w_{d})$ 决定了超平面的方向
- 位移项 $b$ 决定了超平面与原点之间的距离
- 划分超平面 可表达为 $(w,b)$
- 样本空间中任意点 $x$ 到超平面 $(w,b)$ 的距离 [6.2] $r=\frac{|w^{T}x+b|}{||w||}$
- 假设超平面能正确分类，则令 [6.3] $\begin{cases} w^{T}x+b\ge +1 &\text{, } y_{i}=+1; \\ w^{T}x+b\le -1 &\text{, } y_{i}=-1; \end{cases}$
- 支持向量 (support vector)
图6.2 支持向量与间隔- 距超平面最近的这几个训练样本点使式[6.3]成立, 称为支持向量(support vector)
- 间隔(margin)
- 两个异类支持向量到超平面的距离之和 $\gamma = \frac{2}{||w||}$ , 称为间隔(margin)
- 最大间隔(maximum margin)
- 欲找到具有最大间隔(maximum margin)的划分超平面
- 找到能满足式[6.3]中约束的参数 $w$ 和 $b$ ， 使得 $\gamma$ 最大，即 [6.5] $\begin{aligned} &\max_{w,b} \frac{2}{||w||} \\ &\text{s.t.} y_{i}(w^{T}x_{i}+b)\ge 1, i=1,2,\dots,m \end{aligned}$
- 支持向量机
- 为了最大化间隔，仅需最大化 $||w||^{-1}$，等价于最小化 $||w||^{2}$。可重写[6.5] 为
$\begin{aligned} &\min_{w,b} \frac{1}{2}||W||^{2} \\ &\text{s.t. } y_{i}(w^{T}x_{i}+b)\ge 1, i=1,2,\dots,m \end{aligned}$
- 这就是支持向量机(Support Vector Machine，简称SVM)的基本型
- 为了最大化间隔，仅需最大化 $||w||^{-1}$，等价于最小化 $||w||^{2}$。可重写[6.5] 为
$\begin{aligned} &\min_{w,b} \frac{1}{2}||W||^{2} \\ &\text{s.t. } y_{i}(w^{T}x_{i}+b)\ge 1, i=1,2,\dots,m \end{aligned}$
6.2 对偶问题
- 对[6.6]使用拉格朗日乘子法可得到其对偶问题(dual problem)
- 对[6.6]的每条约束添加拉格朗日乘子 $\alpha_{i} \ge 0$，则该问题的拉格朗日函数可写为
[6.8] $L(w,b,\alpha)=\frac{1}{2}||w||^{2}+\sum^{m}_{i=1}\alpha_{i}(1-y_{i}(w^{T}x_{i}+b))$
- 其中 $\alpha=(\alpha_{1};\alpha_{2};\dots;\alpha_{m})$
- 令 $w$ 和 $b$ 的偏导为零，得
- [6.9] $w=\sum^{m}_{i=1}\alpha_{i}y_{i}x_{i}$
- [6.10] $0=\sum^{m}_{i=1}\alpha_{i}y_{i}$
- 将[6.9]代入[6.8]，可消去 $w$ 和 $b$。再考虑[6.10]的约束，就得到[6.6]的对偶问题 [6.11] $\begin{aligned} &\max_{\alpha} \sum^{m}_{i=1}\alpha_{i}-\frac{1}{2}\sum^{m}_{i=1}\sum^{m}_{j=1}\alpha_{i}\alpha_{j}y_{i}y_{j}x^{T}_{i}x_{j} \\ &\text{s.t. } \sum^{m}_{i=1} \alpha_{i}y_{i}=0 \\ &\alpha_{i}\ge 0, i=1,2,\dots,m \end{aligned}$
- 解出 $\alpha$ 后，求出 $w$ 与 $b$ 得到模型 [6.12] $\begin{aligned} f(x)&=w^{T}x+b \\ &=\sum^{m}_{i=1} \alpha_{i}y_{i}x^{T}_{i}x+b \end{aligned}$
- 对[6.6]的每条约束添加拉格朗日乘子 $\alpha_{i} \ge 0$，则该问题的拉格朗日函数可写为
[6.8] $L(w,b,\alpha)=\frac{1}{2}||w||^{2}+\sum^{m}_{i=1}\alpha_{i}(1-y_{i}(w^{T}x_{i}+b))$
- KKT条件
- 从对偶问题[6.11]解出的 $\alpha_{i}$ 是[6.8]中的拉格朗日乘子， $\alpha_{i}$ 恰对应着训练样本 $(x_{i},y_{i})$
- SMO(Sequential Minimal Optimization) 求解算法
- 基本思路： 先固定 $\alpha_{i}$ 之外的所有参数，然后求向上的极值
- 因为有约束 $\sum^{m}_{i=1}\alpha_{i}y_{i}=0$
- 若固定 $\alpha_{i}$ 之外的其他变量，则 $\alpha_{i}$ 可由其他变量导出.
- 因为有约束 $\sum^{m}_{i=1}\alpha_{i}y_{i}=0$
- 每次选择两个变量 $\alpha_{i}$ 和 $\alpha_{j}$，并固定其他参数
- 在参数初始化后， SMO不断执行如下两步直至收敛:
- 选取一对需更新的变量 $\alpha_{i}$ 和 $\alpha_{j}$
- 只需选取的 $\alpha_{i}$ 和 $\alpha_{j}$ 中有一个不满足KKT条件[6.13]，目标函数就会在选代后减小
- SMO先选取违背KKT条件程度最大的变量。第二个变量应选择一个使目标函数值减小最快的变量
- KKT 条件违背的程度越大，则更新后可能导致的函数值减幅越大.
- SMO采用了一个启发式:使选取的两变量所对应样本之间的间隔最大
- 固定 $\alpha_{i}$ 和 $\alpha_{j}$ 以外的参数，求解[6.11]，更新$\alpha_{i}$ 和 $\alpha_{j}$
- 仅考虑 $\alpha_{i}$ 和 $\alpha_{j}$ 时，[6.11]中的约束可重写为
[6.14] $\alpha_{i}y_{i}+\alpha_{j}y_{j}=c, \alpha_{i} \ge 0, alpha_{j} \ge 0$
- $c=-\sum_{k \not = i,j}\alpha_{k}y_{k}$ 是使 $\sum^{m}_{i=1}\alpha_{i}y_{i}=0$ 成立的常数
- 消去[6.11]中的变量 $\alpha_{j}$，则得到一个关于 $\alpha_{i}$ 的单变量二次规划问题
- 这样的二次规划问题具有闭式解，于是不必调用数值优化算法即可高效地计算出新的 $\alpha_{i}$ 和 $\alpha_{j}$
- 仅考虑 $\alpha_{i}$ 和 $\alpha_{j}$ 时，[6.11]中的约束可重写为
[6.14] $\alpha_{i}y_{i}+\alpha_{j}y_{j}=c, \alpha_{i} \ge 0, alpha_{j} \ge 0$
- 选取一对需更新的变量 $\alpha_{i}$ 和 $\alpha_{j}$
- 基本思路： 先固定 $\alpha_{i}$ 之外的所有参数，然后求向上的极值
- 如何确定偏移项b
- 到对任意支持向量$(x_{s}, y_{s})$，都有 $y_{s}f(x_{s})=1$，即
[6.17] $y_{s}(\sum_{i \in s}\alpha_{i}y_{i}x^{T}_{i}x_{s}+b)=1$
- 其中 $S=\{ i| \alpha_{i}>0 , i=1,2,\dots,m \}$ 为所有支持向量的F标集
- 现实任务中， 使用所有支持向量求解的平均值 [6.18] $b=\frac{1}{|S|}\sum_{s\in S}(y_{s}-\sum_{i\in S}\alpha_{i}y_{i}x^{T}_{i}x_{s})$
- 到对任意支持向量$(x_{s}, y_{s})$，都有 $y_{s}f(x_{s})=1$，即
[6.17] $y_{s}(\sum_{i \in s}\alpha_{i}y_{i}x^{T}_{i}x_{s}+b)=1$
- SMO(Sequential Minimal Optimization) 求解算法
- 因为[6.6]中有不等式约束，因此上述过程需满足KKT(Karush-Kuhn-Tucker)条件，即要求
[6.13] $\begin{cases} &\alpha_{i}\ge 0; \\ &y_{i}f(x_{i})-1\ge 0; \\ &\alpha_{i}(y_{i}f(x_{i})-1)=0 \end{cases}$
- 对任意训练样本，总有$\alpha_{i}=0$ 或 $y_{i}f(x_{i})=1$
- 若 $\alpha_{i}=0$，则该样本将不会在[6.12]的求和中出现，也就不会对 $f(x)$ 有任何影响
- 若 $\alpha_{i}>0$，则有 $y_{i}f(x_{i})=1$，所对应的样本点位于最大间隔边界上，是一个支持向量
- 这显示出支持向量机的一个重要性质:训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关
- 对任意训练样本，总有$\alpha_{i}=0$ 或 $y_{i}f(x_{i})=1$
- 从对偶问题[6.11]解出的 $\alpha_{i}$ 是[6.8]中的拉格朗日乘子， $\alpha_{i}$ 恰对应着训练样本 $(x_{i},y_{i})$