支持向量机

作者: songcmic | 来源:发表于2017-10-13 20:24 被阅读41次

原文
支持向量机（SVM）是一个非常好的监督学习算法，由于这个算法涉及到的数学知识比较多，而且不容易弄懂，因此我额外补了一些拉格朗日对偶性的一些知识，还初步了解了以下凸优化的相关知识，建议如过想学SVM的先去学一些拉格朗日对偶问题以及一些凸优化的相关东西。终于能大致弄懂SVM的整个过程中所涉及到的一些东西，但是仍有一些地方还是不太明白，还有待继续学习。这里先对所掌握的过程进行回顾总结。

支持向量机（SVM）

支持向量机是一个监督学习算法，它实质上是一种特征空间上的间隔最大的线性分类器，这其中涉及到核技巧将线性不可分问题映射成特征空间中的线性可分问题，因此支持向量机可以说是一个非线性分类器，它的学习策略就是间隔最大化，最后的问题可以转化为一个凸优化问题，使用拉格朗日对偶性来求解对偶问题，从而间接得到原问题的解，一般使用SMO算法来求对偶问题的解。

间隔最大化

支持向量机的思想就是间隔最大化，根据间隔最大化来构造原始问题。这里涉及到的间隔包括函数间隔和几何间隔，其中函数间隔为

$\hat\gamma_i=y_i(\omega\cdot{x_i})+b$
然后得到所有样本的函数间隔中的最小的一个 $\hat\gamma=\min_{i=1,\cdots,N}(\hat\gamma_i)$

几何间隔由空间中两点的实际距离定义记作

$\gamma_i=\dfrac{\omega}{||\omega||}\cdot{x_i}+\dfrac{b}{||\omega||}$
同理求出所有几何间隔最小的 $\gamma=\min_{i=1,\cdots,N}(\gamma_i)$ 可以看出函数间隔是不唯一的，因为满足分离超平面 $\omega^\ast\cdot{x}+b^\ast=0$

的参数并不是唯一的。而几何距离却不会发生变化。

同时还可以看出函数间隔和几何间隔之间满足关系(3)

$\gamma=\dfrac{\hat\gamma}{||\omega||}$

因此这里考虑求解几何间隔最大的分离超平面，该问题则表示为下面的约束最优化问题

$\max_{\omega,b}\quad\gamma\\s.t.\quad{y_i}(\frac{\omega}{||\omega||}\cdot{x_i}+\dfrac{b}{||\omega||})\ge\gamma,\qquad{i}=1,2,\cdots,N$
根据上述关系(3)将问题转换为
$\max_{\omega,b}\quad\dfrac{\hat\gamma}{||\omega||}\\s.t.\quad{y_i}(\omega\cdot{x_i}+b)\ge\hat\gamma,\qquad{i}=1,2,\cdots,N$

问题进一步转化为

$\min_{\omega,b}\quad\dfrac{1}{2}||\omega||^2\\s.t.\quad{y_i}(\omega\cdot{x_i}+b)\ge{1},\qquad{i}=1,2,\cdots,N$
问题(6)就是支持向量机需要解决的问题，即原始最优化问题，最终我们求得的分类决策函数

拉格朗日对偶性

对上述问题(6)建立拉格朗日函数，引入拉格朗日乘子，定义拉格朗日函数为

$L(\omega,b,\alpha)=\dfrac{1}{2}||\omega||^2-\sum_{i=1}^N\alpha_iy_i(\omega\cdot{x_i}+b)+\sum_{i=1}^N\alpha_i$

分别对两个变量求偏导令其为零然后带入到拉格朗日函数(8)中去，即得到其对偶问题(关于对偶的相关知识不在此陈述)

$\min_{\alpha}\quad\dfrac{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\\s.t.\quad\sum_{i=1}^N\alpha_iy_i=0\\\alpha_i\ge{0},\quad{i}=1,2,\cdots,N$
然而实际情况中，线性可分的情况是十分少的，一般都是近似线性可分的的，这里涉及到的是软间隔支持向量机，也称为线性支持向量机，是最基本的支持向量机。

对与近似线性可分的样本中的噪声样本通过引入一个松弛变量$\xi_i$，从而使其在一定的可接受的误差范围内可分，因此得到线性支持向量机的原始最优化问题

$\min_{\omega,b}\quad\dfrac{1}{2}||\omega||^2+C\sum_{i=1}^N\xi_i\\s.t.\quad{y_i}(\omega\cdot{x_i}+b)\ge{1}-\xi_i,\qquad{i}=1,2,\cdots,N\\\xi_i\ge{0},\quad{i}=1,2,\cdots,N$

其对偶问题为

$\min_{\alpha}\quad\dfrac{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\\s.t.\quad\sum_{i=1}^N\alpha_iy_i=0\\0\le\alpha_i\le{C},\quad{i}=1,2,\cdots,N$
可一看到，他和线性可分支持向量机的唯一区别是$\alpha_i$的约束多了一个上限。

非线性支持向量机与核技巧

对于输入空间中的分线性分类问题，可以通过非线性变换将它转换为某个高维特征空间中的线性分类问题，在高维空间中学习线性支持向量机。

输入空间到某个高维空间的转换是通过映射来完成的，对于$\forall x,z \in \chi$，函数$K(x,z)$满足条件$K(x,z) = \phi(x)\cdot\phi(z)$，则称函数$K(x,z)$为核函数。

目标函数与分类决策函数中都只涉及实例与实例之间的内积，因此并不需要显示的指定非线性变换，而是直接用核函数来代替内积，对偶问题则变为如下形式

$W(\alpha)=\dfrac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i$

分类决策函数中的内积也用核函数来表示
因此在线性支持向量机学习的对偶问题中使用核函数来代替内积即可解得非线性支持向量机。

序列最小最优化算法（SMO）

该算法分为两个部分分别是

求解两个变量二次规划的解析方法

选择变量的启发式方法

两个变量的二次规划解析方法

假定选择两个变量，而其它的变量保持不变，则(12)式的子问题可以表示为

$\min_{\alpha_1,\alpha_2}\quad{W}(\alpha_1,\alpha_2)=\dfrac{1}{2}K_{11}\alpha_1^2+\dfrac{1}{2}K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_2\\\quad\quad\quad-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^{N}y_i\alpha_iK_{i1}+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK_{i2}\\s.t.\quad\alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^Ny_i\alpha_i=\zeta\\0\le\alpha\le{C},\quad{i}=1,2$

将问题(14)中的等式约束

$\alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^Ny_i\alpha_i=\zeta$
进行变换，那么问题就变为关于变量$\alpha_2$的二次函数求极值的问题，求得$\alpha_2$之后通过等式即可得到$\alpha_1$的值。

启发式变量选择方法

SMO称第一个变量的选择为外层循环，外层循环在训练样本中选取违反KKT条件最严重的样本点，并将其对应的变量作为第一个变量，具体的检验训练样本$(x_i, y_i)$是否满足KKT条件，即

$\alpha_i=0\Leftrightarrow{y_i}g(x_i)\ge{1}\\0\lt\alpha_i\lt{C}\Leftrightarrow{y_i}g(x_i)=1\\\alpha_i=C\Leftrightarrow{y_i}g(x_i)\le{1}$

第二个变量的选择称为内层循环，在找到第一个变量$\alpha_1$的条件下，在内层循环中寻找第二个变量$\alpha_2$，第二个变量的选择标准是希望能够使$\alpha_2$尽量有足够大的变化。

关于SMO算法中的变量选择方法我目前并不是完全懂，先写到这里为止。

总结

此次总结对之前学的支持向量机的相关知识进行了一次回顾，支持向量机结合核技巧是一个非常好的学习算法，它利用了拉格朗日问题的对偶性，将原问题转换为对偶问题，因为可能存在一种情况是每个样本的属性非常的多，也就是输入空间的维数非常的大，而转换为对偶问题之后，参数是和样本一一对应的，因此参数数目就是样本的数目，这能够大大减小计算的复杂度，最后对于求解凸二次规划问题有十分有效的SMO算法，因为子问题有解析解，因此每次计算子问题都十分的快，虽然子问题数目多，但是总体上看来还是很快的。
原文

支持向量机

支持向量机（SVM）

间隔最大化

拉格朗日对偶性

非线性支持向量机与核技巧

序列最小最优化算法（SMO）

两个变量的二次规划解析方法

启发式变量选择方法

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

机器学习

数据挖掘机器学习 Python R 人工智能

数据科学与R语言

程序员

机器学习与数据挖掘

深度学习

支持向量机

支持向量机（SVM）

间隔最大化

拉格朗日对偶性

非线性支持向量机与核技巧

序列最小最优化算法（SMO）

两个变量的二次规划解析方法

启发式变量选择方法

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

机器学习

数据挖掘 机器学习 Python R 人工智能

数据科学与R语言

程序员

机器学习与数据挖掘

深度学习

数据挖掘机器学习 Python R 人工智能