【一起啃书】《机器学习》第六章 支持向量机

第六章 支持向量机

6.1 间隔和支持向量

  给定训练样本集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } , y i ∈ { − 1 , + 1 } D = \{ ({x_1},{y_1}),({x_2},{y_2}),...,({x_m},{y_m})\} ,{y_i} \in \{ - 1, + 1\} D={(x1​,y1​),(x2​,y2​),...,(xm​,ym​)},yi​∈{−1,+1}分类学习最基本的想法就是基于训练集$D$在样本空间中找到一个划分超平面将不同类别的样本分开但能将训练样本分开的划分超平面可能有很多如下所示

  直观上看应该去找位于两类训练样本“正中间”的划分超平面该超平面对训练样本局部扰动的“容忍”性最好也就是该划分超平面所产生的分类结果是最鲁棒的对未见示例的泛化能力最强。划分超平面的线性方程如下所示
$${\omega }^{T}x+b=0$$
  其中$\omega =({\omega }_1;{\omega }_2;...;{\omega }_d)$为法向量决定了超平面的方向$b$为位移项决定了超平面与原点之间的距离下面定义样本空间中任意点$x$到超平面$(\omega ,b)$的距离如下所示
$$r=\frac{\left|{\omega }^{T}x+b\right|}{\Vert \omega \Vert }$$
  假设超平面$(\omega ,b)$能将训练样本正确分类有如下定义
$$\{\begin{array}{r}{\omega }^T{x}_i+b⩾+1,y_i=+1\\ {\omega }^T{x}_i+b⩽-1,y_i=-1\end{array}$$
  如下图所示距离超平面最近的这几个训练样本点使上式的等号成立这些点被称为“支持向量”两个异类支持向量到超平面的距离之和为$\gamma =\frac{2}{\Vert \omega \Vert }$也被称为“间隔”。

  欲找到具有“最大间隔”的划分超平面需要找到满足约束条件的参数$\omega$和$b$使得$\gamma$最大即
$$\begin{array}{rl}& \underset{\omega ,b}{\max }\frac{2}{\Vert \omega \Vert }\\ & s.t.y_i({\omega }^T{x}_i+b)⩾1,i=1,2,...,m\end{array}$$
  最大化${\Vert \omega \Vert }^{-1}$等价于最小化${\Vert \omega \Vert }^2$于是得到如下表达这也是支持向量机的基本型。
$$\begin{array}{rl}& \underset{\omega ,b}{\min }\frac{1}{2}{\Vert \omega \Vert }^2\\ & s.t.y_i({\omega }^T{x}_i+b)⩾1,i=1,2,...,m\end{array}$$
  虽然间隔看着貌似只与$\omega$有关但实际上$b$通过约束隐式地影响着$\omega$的取值因为这些支持向量是使得等号成立的样本点所以如果$b$发生变化那么$\omega$也会发生变化。

6.2 对偶问题

  SVM基本型的对偶问题是将原始问题的最小化目标函数转换为最大化拉格朗日函数利用拉格朗日对偶性求解出拉格朗日乘子从而得到超平面的参数。首先对原来的约束条件添加拉格朗日乘子${\alpha }_i⩾0$得到如下的拉格朗日函数
$$L(\omega ,b,\alpha )=\frac{1}{2}{\Vert \omega \Vert }^2+\sum _{i=1}^m{\alpha }_i(1-y_i({\omega }^T{x}_i+b))$$
  下面分别对$\omega$和$b$求偏导得到如下结果
$$\omega =\sum _{i=1}^m{\alpha }_i{y}_i{x}_i,0=\sum _{i=1}^m{\alpha }_i{y}_i$$
  将上面求偏导的结果再带入到原来的拉格朗日函数中就可以得到SVM基本型的对偶问题如下所示
$$\begin{array}{rl}& \underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\\ & s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0\end{array}$$
  上述问题是一个二次规划问题但该问题的规模正比于训练样本数会在实际任务中造成很大的开销为了避开这个障碍在这里引入了SMO算法来解决这个问题SMO算法需要注意以下几点

• SMO算法的基本思想是每次选择两个拉格朗日乘子${\alpha }_i$ 和 ${\alpha }_j$作为优化变量固定其他的乘子将原问题简化进行求解。
• SMO算法的关键是如何选择合适的 ${\alpha }_i$ 和 ${\alpha }_j$以及如何更新它们的值一般来说选择违反KKT条件最严重的 ${\alpha }_i$ 作为第一个变量然后在约束条件下选择第二个变量 ${\alpha }_j$使得目标函数有足够大的变化。
• SMO算法的终止条件是所有的拉格朗日乘子都满足KKT条件或者达到最大迭代次数。
• SMO算法的优点是可以高效地求解SVM对偶问题避免了矩阵运算和存储只需要利用核函数计算样本之间的内积而缺点是需要调整一些启发式的参数如容错率和最大迭代次数以及核函数的选择。

6.3 核函数

  在现实任务中原始样本空间内也许并不存在一个能正确划分两类样本的超平面如下左图所示对这样的问题可将样本从原始空间映射到一个更高维的特征空间使得样本在这个特征空间内线性可分如下右图所示。

  令$\varphi (x)$表示将$x$映射后的特征向量于是在特征空间中划分超平面所对应的模型可表示为
$$f(x)={\omega }^T\varphi (x)+b$$
  以下为其基本型
$$\begin{array}{rl}& \underset{\omega ,b}{\min }\frac{1}{2}{\Vert \omega \Vert }^2\\ & s.t.y_i({\omega }^T\varphi (x_i)+b)⩾1,i=1,2,...,m\end{array}$$
  以下为对应的对偶问题
$$\begin{array}{rl}& \underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\varphi (x_i{)}^T\varphi (x_j)\\ & s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0\end{array}$$
  求解上述式子涉及到$\varphi (x_i{)}^T\varphi (x_j)$这是样本$x_i$与$x_j$映射到特征空间之后的内积。由于特征空间维数可能很高甚至可能是无穷维因此直接计算$\varphi (x_i{)}^T\varphi (x_j)$通常是困难的。为了避开这个障碍可以设想这样一个函数
$$\kappa (x_i,x_j)⩽\varphi (x_i),\varphi (x_j)⩾\varphi (x_i{)}^T\varphi (x_j)$$
  即$x_i$与$x_j$在特征空间的内积等于它们在原始样本空间中通过函数$\kappa (\cdot ,\cdot )$计算的结果于是可以得到如下式子
$$\begin{array}{rl}& \underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\kappa (x_i,x_j)\\ & s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0\end{array}$$
  求解后即可得到$f(x)=\sum _{i=1}^m{\alpha }_i{y}_i\kappa (x_i,x_j)+b$这里的$\kappa (x_i,x_j)$被称为“核函数”这一展开式也被称为“支持向量展开”。下面为判断核函数的一个定理。

  以下为常见的核函数。

  对于核函数的选择可以参考以下规则

• 如果数据是线性可分的或者特征的数量很大接近于样本的数量可以选择线性核函数因为线性核函数参数少速度快而且可以得到很好的效果。
• 如果数据是非线性的或者特征的数量比较小而样本的数量一般可以选择高斯核函数也叫RBF核函数因为高斯核函数可以将数据映射到一个无限维的特征空间具有很强的拟合能力。不过高斯核函数的分类结果非常依赖于参数的选择需要通过交叉验证等方法来寻找合适的参数。
• 如果数据是非线性的而且有明显的结构特征例如图像、文本等可以选择与数据结构相匹配的核函数例如多项式核函数、字符串核函数、图核函数等。这些核函数可以利用数据的先验知识提取更有效的特征提高分类或回归的准确性。

6.4 软间隔与正则化

  在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分即便恰好找到了某个核函数使训练集在特征空间中线性可分也很难断定这个貌似线性可分的结果不是由于过拟合所造成的缓解这个问题的一个办法是允许支持向量机在一些样本上出错如下为软间隔示例图红色圈出了一些不满足约束的样本。

  若要求所有样本都必须划分正确这称为“硬间隔”而软间隔则是允许某些样本不满足约束$y_i({\omega }^T{x}_i+b)⩾1$而在最大化间隔的同时不满足约束的样本应尽可能少于是就有了如下优化目标
$$\underset{\omega ,b}{\min }\frac{1}{2}{\Vert \omega \Vert }^2+C\sum _{i=1}^m{\ell }_{0/1}(y_i({\omega }^T{x}_i+b)-1)$$
  其中类似${\ell }_{0/1}$的函数被称为“替代损失”常见的替代函数以及它们的图像如下所示

  下面引入松弛变量${\xi }_i⩾0$即可得到如下的软间隔支持向量机
$$\begin{array}{rl}& \underset{\omega ,b,\xi }{\min }\frac{1}{2}{\Vert \omega \Vert }^2+C\sum _{i=1}^m{\xi }_i\\ & s.t.y_i({\omega }^T{x}_i+b)⩾1-{\xi }_i\end{array}$$
  松弛变量${\xi }_i$表示第$i$个样本违反约束条件的程度$C$是一个正的常数表示对松弛变量的惩罚系数。可以看到当$C$很大时相当于对松弛变量的惩罚很大要求所有样本都满足约束条件这就退化为硬间隔的情况当$C$很小时相当于对松弛变量的惩罚很小允许一些样本不满足约束条件这就增加了模型的泛化能力。因此$C$的大小决定了svm对分类错误的容忍程度和模型的复杂度。

  而这里需要注意$C$比较大会增加松弛变量的值是因为要最小化整个目标函数而不是只最小化间隔。目标函数由两部分组成一部分是$\frac{1}{2}{\Vert \omega \Vert }^2$表示间隔的倒数另一部分是$C{\sum }_{i=1}^n{\xi }_i$表示对松弛变量的惩罚。当$C$比较大时表示对松弛变量的惩罚比较大也就是要求所有样本都满足约束条件即$y_i({\omega }^T{x}_i+b)\ge 1-{\xi }_i$。这样的话如果有一些样本本来不满足约束条件那么就要增加它们的松弛变量的值让它们满足约束条件。这样做的好处是可以减少分类错误提高模型在训练集上的准确率。但是这样做的坏处是可能导致过拟合降低模型在测试集上的泛化能力。

  同时这里的$C$也是正则化尝试正则化可以理解为一种“罚函数法”即对不希望得到的结果施以惩罚从而使得优化过程趋向于希望目标从贝叶斯估计的角度来看正则化项可认为是提供了模型的先验概率。

6.5 支持向量回归

  对于样本$(x,y)$传统回归模型通常直接基于模型输出$f(x)$与真实输出$y$之间的差别来计算损失当且仅当$f(x)$与$y$完全相同时损失才为零。与此不同支持向量回归假设我们能容忍$f(x)$与$y$之间最多有$\epsilon$的偏差即仅当$f(x)$与$y$之间的差别绝对值大于$\epsilon$时才计算损失如下图所示相当于以$f(x)$为中心构建了一个宽度为$2\epsilon$的间隔带若训练样本落入此间隔带则认为是被预测正确的。

  引入松弛变量得到如下优化问题这里引入两个松弛变量是因为间隔带两侧的松弛程度可以不同。
$$\begin{array}{rl}& \underset{\omega ,b,\xi ,\stackrel{\ast }{\xi }}{\min }\frac{1}{2}{\Vert \omega \Vert }^2+C\sum _{i=1}^m{\xi }_i+{\stackrel{\ast }{\xi }}_i\\ & s.t.f(x_i)-y_i⩽\epsilon +{\xi }_i,\\ & y_i-f(x_i)⩽\epsilon +\underset{i}{\overset{\ast }{\xi }},\\ & {\xi }_i⩾0,\underset{i}{\overset{\ast }{\xi }}⩾0\end{array}$$
  同样的需要引入拉格朗日乘子进行优化求解最后得到对偶问题同时也可以引入核函数。

6.6 核方法

  给定训练样本$\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}$若不考虑偏移项$b$则无论SVM还是SVR学得的模型总能表示成核函数$\kappa (\mathbf{x},x_i)$的线性组合同时可以得到如下被称为“表示定理”的更一般的结论。

  表示定理 令$\mathbb{H}$为核函数$\kappa$对应的再生核希尔伯特空间${\Vert h\Vert }_{\mathbb{H}}$表示$\mathbb{H}$空间中关于$h$的范数对于任意单调递增函数$\Omega :[0,\infty ]\mapsto \mathbb{R}$和任意非负损失函数$\ell :{\mathbb{R}}^m\mapsto [0,\infty ]$优化问题
$$\underset{h\in \mathbb{H}}{\min }F(h)=\Omega ({\Vert h\Vert }_{\mathbb{H}})+\ell (h(x_1),h(x_2),...,h(x_m))$$
  的解总可写为
$$h^{\ast }(x)=\sum _{i=1}^m{\alpha }_i\kappa (\mathbf{x},x_i)$$
  表示定理对损失函数没有限制对正则化项$\Omega$仅要求单调递增甚至不要求$\Omega$是凸函数意味着对于一般的损失函数和正则化项上述优化问题的最优解都可以表示为核函数的线性组合。

  因此人们发展出一系列基于核函数的学习方法统称为“核函数”。最常见的是通过“核化”即引入核方法来将线性学习器拓展为非线性学习器比如SVM、PCA、LDA、聚类等等都可以引入核方法。

6.7 一些问题

1SVM、BP神经网络和C4.5决策树的异同

• SVM是一种基于核函数和凸优化的算法它的目标是在特征空间中寻找一个最大间隔超平面来分割两个类别。SVM的优点是能够处理非线性可分问题泛化能力强不容易过拟合。SVM的缺点是计算复杂度高对参数和核函数的选择敏感难以解释。

• BP神经网络是一种多层人工神经网络它的目标是通过反向传播算法来调整网络权重使得网络输出和期望输出之间的误差最小。BP神经网络的优点是结构灵活能够拟合复杂的非线性函数适用于语音、图像、自然语言等领域。BP神经网络的缺点是训练速度慢容易陷入局部最优解需要大量数据进行训练。

• 决策树是一种基于信息论和递归划分的算法它的目标是构建一棵树状结构每个内部节点表示一个特征判断每个叶子节点表示一个类别或回归值。决策树的优点是易于理解和解释非参数型适合处理离散特征。决策树的缺点是容易过拟合对噪声数据敏感可能不稳定。

2线性判别分析与线性核SVM在什么条件下等价

• 数据集是线性可分的即存在一个超平面可以完美地分割两个类别
• 数据集服从高斯分布即每个类别的数据都符合一个多元正态分布
• 数据集的协方差矩阵相同即每个类别的数据都有相同的方差和相关性。

  如果数据集是线性可分的那么LDA和线性核SVM都可以找到一个超平面来完美地分割两个类别但这个超平面不一定是唯一的。其次如果数据集服从高斯分布那么LDA可以通过最大化两个类别均值之差来得到一个最优的投影方向而线性核SVM可以通过最大化两个类别支持向量之间的距离来得到一个最优的分类器。最后如果数据集的协方差矩阵相同那么LDA和线性核SVM的目标函数都可以化简为两个类别均值之差的函数从而得到相同的超平面。

3高斯核SVM与RBF神经网络之间的联系

  高斯核SVM与RBF神经网络都使用了高斯核函数作为非线性映射的工具将低维空间中的数据映射到高维空间中从而实现线性可分或近似线性可分当RBF神经网络的隐层神经元数设置为训练样本数且每个训练样本对应一个神经元中心时RBF神经网络与高斯核SVM的预测函数是相同的。

4SVM对噪声敏感的原因

  SVM的目的是求出与支持向量有最大距离的超平面以每个样本为圆心该距离为半径作圆可以近似认为圆内所有的点都与该样本属于相同分类若圆内出现了噪声那么该噪声所造成的错误分类也将最大化因此SVM对噪声是敏感的。为了克服SVM对噪声敏感的问题可以引入松弛变量和惩罚因子构造软间隔分类器允许一些样本不满足硬间隔约束条件从而避免过拟合和模型过于复杂。