[机器学习西瓜书] 第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] 为
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.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$，则该问题的拉格朗日函数可写为
- 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]中的约束可重写为
- 选取一对需更新的变量 $\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$，即
- 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})$
6.3 核函数
- 对非线性可分问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分
- 如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分 【参见第12章】
- 对偶问题
- 令 $\phi(x)$ 表示将 $x$ 映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为
[6.19] $f(x)=w^{T}\phi(x)+b$- 其中 $w$ 和 $b$ 是模型参数
- 类似[6.6]，有
[6.20] $\begin{aligned}&\min_{w,b} \frac{1}{2}||w||^{w} \\ &\text{s.t.} y_{i}(w^{T}\phi(x_{i})+b)\ge 1, i=1,2,\dots,m \end{aligned}$ - 其对偶问题是
[6.21] $\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}\phi(x_{i})^{T}\phi(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}$- 由于特征空间维数可能很高，因此直接计算 $\phi(x_{i})^{T}\phi(x_{j})$ 通常是困难的。为了避开这个障碍，可以设想这样一个函数:
[6.22] $\kappa(x_{i},x_{j})=<\phi(x_{i}),\phi(x_{j})>=\phi(x_{i})^{T}\phi(x_{j})$- 即 $x_{i},x_{j}$ 在特征空间的内积等于它们在原始样本空间中通过函数 $\kappa(\cdot,\cdot)$ 计算的结果
- [6.21]可重写为
$\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}\kappa(x_{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$ 后即可得到
[6.24] $\begin{aligned} f(x)&=w^{T}\phi(x)+b \\ &=\sum^{m}_{i=1} \alpha_{i}y_{i}\phi(x_{i})^{T}\phi(x_{j})+b \\ &=\sum^{m}_{i=1} \alpha_{i}y_{i}\kappa(x_{i},x_{j})+b \end{aligned}$- 这里的函数 $\kappa(\cdot,\cdot)$ 就是核函数(kernel function)
- [6.24]展式亦称支持向量展式(support vector expansion)
- 由于特征空间维数可能很高，因此直接计算 $\phi(x_{i})^{T}\phi(x_{j})$ 通常是困难的。为了避开这个障碍，可以设想这样一个函数:
- 令 $\phi(x)$ 表示将 $x$ 映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为
- 定理6.1 (核函数)
- 令 $\chi$ 为输入空间，$\kappa(\cdot,\cdot)$ 是定义在 $\chi \times \chi$ 上的对称函数
- 则 $\kappa$ 是核函数 当且仅当 对于任意数据 $D=\{x_{1},x_{2},\dots,x_{m}\}$，核矩阵(kernel matrix) $K$ 总是半正定的:
6.1矩阵 - 对于一个半正定核矩阵，总能找到一个与之对应的映射$\phi$.
换言之，任何一个核函数都隐式地定义了一个称为再生核希尔伯特空间(Reproducing Kernel Hilbert Space ，简称RKHS)的特征空间.
- 特征空间的好坏对支持向量机的性能至关重要
表6.1 常用核函数 - 此外，还可通过函数组合得到 例如:
- 若 $\kappa_{1}$ 和 $\kappa_{2}$ 为核函数，则对于任意正数 $\gamma_{1}, \gamma_{2}$，其线性组合
[6.25] $\gamma_{1}\kappa_{1} + \gamma_{2}\kappa_{2}$ 也是核函数; - 若 $\kappa_{1}$ 和 $\kappa_{2}$ 为核函数，则核函数的直积
[6.26] $\kappa_{1} \otimes \kappa_{2}(x,z)=\kappa_{1}(x,z)\kappa_{2}(x,z)$ 也是核函数; - 若 $\kappa_{1}$ 为核函数，则对于任意函数 $g(x)$，
[6.27] $\kappa(x,z)=g(x)\kappa_{1}(x,z)g(z)$ 也是核函数
- 若 $\kappa_{1}$ 和 $\kappa_{2}$ 为核函数，则对于任意正数 $\gamma_{1}, \gamma_{2}$，其线性组合
6.4 软间隔与正则化
- 在现实任务中，往往很难确定合适的核函数，使得训练样本在特征空间中线性可分
- 即使恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定结果不是由于过拟合所造成的.
- 缓解该问题的一个办法是允许支持向量机在一些样本上出错
- 硬间隔
- 支持向量机形式是要求所有样本均满足约束[6.3] ，即所有样本都必须划分正确，这称为硬间隔(hard margin)
- 软间隔(soft margin)
- 允许某些样本不满足约束
[6.28] $y_{i}(w^{T}x_{i}+b)\ge 1$ - 在最大化间隔的同时，不满足约束的样本应尽可能少
- 于是，优化目标可写为
[6.29] $\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\mathcal{l}_{0/1}(y_{i}(w^{T}x_{i}+b)-1)$- $C>0$ 是个常数
- 当 $C$ 为无穷大时，式(6.29)迫使所有样本均满足约束(6.28)
- 于是式(6.29) 等价于(6.6)
- 当 $C$ 取有限值时，式(6.29)允许一些样本不满足约束
- $\mathcal{l}_{0/1}$是”0/1损失函数”
[6.30] $\mathcal{l}_{0/1}=\begin{cases}1 & \text{, if }z<0; \\ 0 & \text{otherwise} \end{cases}$- 然而，$\mathcal{l}_{0/1}$ 非凸、非连续，数学性质不太好
- 人们通常用其他一些函数来代替，称为替代损失(surrogate loss)
- 三种常用的替代损失函数:
图 6.5 三种常见的替代损失函数: hi日ge损失、指数损失、对率损失- [6.31] hinge 损失: $l_{hinge}(z)=\max(0,1-z)$
- [6.32] 指数损失(exponential loss): $l_{exp}(z)=e^{-z}$
- [6.33] 对率损失(logistic loss): $l_{log}(z)=\log(1+e^{-z})$
- 三种常用的替代损失函数:
- 若采用hinge 损失，则式(6.29)变成
[6.34] $\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\max(0, 1-y_{i}(w^{T}x_{i}+b))$ - 引入”松弛变量” (s1ack variables) $\xi_{i} \ge 0$ ，可将式(6.34)重写为
[6.35] $\begin{aligned}&\min_{w,b,\xi_{i}} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\xi_{i} \\ &\text{s.t.} y_{i}(w^{T}x_{i}+b)\ge 1-\xi_{i} \\ &\xi_{i} \ge 0, i=1,2,\dots,m \end{aligned}$ - 这就是常用的”软间隔支持向量机”，这仍是一个二次规划问题
- 于是类似式(6 .8) ，通过拉格朗日乘子法可得到式(6.35)的拉格朗日函数
[6.36] $L(w,b,\alpha,\xi,\mu)=\frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}\xi_{i}+\sum^{m}_{i=1}\alpha_{i}(1-\xi_{i}-y_{i}(w^{T}x_{i}+b))-\sum^{m}_{i=1}\mu_{i}\xi_{i}$- $\alpha \ge 0, \mu \ge 0$ 是拉格朗日乘子
- 令 $L(w,b,\alpha,\xi,\mu)$ 对 $w$，$b$的偏导为零可得
- [6.37]
$w=\sum^{m}_{i=1}\alpha_{i}y_{i}x_{i}$ - [6.38]
$0=\sum^{m}_{i=1}\alpha_{i}y_{i}$ - [6.39]
$C=\alpha_{i}+\mu_{i}$
- [6.37]
- 代入式(6.36) 即可得到式(6.35) 的对偶问题
$\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 \\ &0\le \alpha_{i}\le C, i=1,2,\dots,m \end{aligned}$- 将式(6.40)与(6.11)对比可看出，两者唯一差别就在对偶变量的约束不同
- 对软间隔支持向量机， KKT 条件要求
[6.41] - 于是，对任意训练样本$(x_{i},y_{i})$，总有 $\alpha_{i}=0$ 或 $y_{i}f(x_{i})=1-\xi_{i}$
- 这些替代函数产生的模型具有一个共性:
- 优化目标中的第一项描述划分超平面的”间隔”大小
- 另一项 $\sum^{m}_{i=1}l(f(x_{i},y_{i}))$ 表述训练集上的误差
- 可写为更一般的形式
[6.42] $\min_{f}\Omega(f)+C\sum^{m}_{i=1}l(f(x_{i},y_{i}))$- $\Omega(f)$ 称为结构风险(structural risk)
- 用于描述模型$f$ 的某些性质
- $\sum^{m}_{i=1}l(f(x_{i},y_{i}))$ 称为经验风险(empirical risk)
- 用于描述模型与训练数据的契合程度
- $C$ 用于对二者进行折中
- $\Omega(f)$ 称为结构风险(structural risk)
- 另一方面，该信息有助于削减假设空间，从而降低了过拟合风险
- 从这个角度来说，式(6 .42) 称为正则化(regularization)问题
- $\Omega(f)$ 称为正则化项
- $C$ 则称为正则化常数
- 从这个角度来说，式(6 .42) 称为正则化(regularization)问题
- 于是，优化目标可写为
- 允许某些样本不满足约束
6.5 支持向量回归
图6.6 支持向量回归示意图.红色显示出ε- 间隔带， 落入其中的样本不计算损失
– 支持向量回归(Support Vector Regression，简称SVR)
– 假设我们能容忍 $f(x)$ 与 $y$ 之间最多有 $\epsilon$ 的偏差
– 于是，SVR问题可形式化为
[6.43] $\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}l_{\epsilon}(f(x_{i})-y_{i})$
– $C$ 为正则化常数
– $l_{\epsilon}$ 是 ε不敏感损失(ε insensitive loss)函数
[6.44] $\mathcal{l}_{0/1}=\begin{cases}0 & \text{, if }|z|<\epsilon; \\ |z|-\epsilon & \text{otherwise} \end{cases}$
– 引入松弛变量 $\xi_{i}$ 和 $\hat \xi_{i}$ ，可将式(6 .43)重写为
[6.45] $\begin{aligned}&\min_{w,b} \frac{1}{2}||w||^{2}+C\sum^{m}_{i=1}(\xi_{i}+\hat \xi_{i}) \\ &\text{s.t.} f(x_{i})-y_{i}\le \epsilon+\xi_{i} \\ &y_{i}-f(x_{i})\le \epsilon+\xi_{i} \\ &\xi_{i}\ge 0, \hat \xi_{i} \ge 0, i=1,2,\dots,m \end{aligned}$