SVM(Support Vector Machines):支持向量机

作者:a130737

 支持向量机以前很火了。 现在风头被深度学习给占据了。   

支持向量机的相关理论非常的beautiful and elegant, 最后将学习的问题转化成了一个凸优化的问题, 确保了最优解的存在。 并且可以利用kernels解决了样本的非线性可分问题。 这也是SVM的优点吧。

SVM是用于分类的一种强大的工具。

给定一个具有m个训练样本的训练样本集(training set):

其中:

也就是说x 是我们的n维的输入特征向量, y是样本的labels, 可以取 +1或者-1。 note: 这里先考虑2-class classification的问题。

现在的目的就是找出一个hyperplane, 能够使得训练集合中的正负样本尽可能的(即margine 达到最大)分割开来。

所谓的margine, 就是样本距离那个用hyperplane 定义的decision boundary的距离。 其距离的定义如下:

由于我们要保证margine是一个正数值, 所以我们乘以其类标号yi(取值只有+1, -1两种情况)。

我们希望对于所有的训练样本, 最终得到的margin是越大(即距离decision boundary 越远越好), 我们对于样本类标号的分割就更加自信。

然而单纯的使用作为计算我们的margin是有问题的, 因为这会导致对于margin的随意性。 这种随意性源于如下:

假如我们的decision boundary的函数如下:

我们知道将上述等式左右两边同时乘以一个常数a, 那么等式依然成立, 这个新的等式仍然定义着同样的一个hyperplane, 但是问题来了, 我们在计算训练样本的margin的时候, 这个数值都变成了原来的a倍了。 这种随意的margin是我们无法掌控的。

所以改进办法就是采用平面的方向向量进行归一化。 这样我们得到的margin也被称为geometric margin。 如下图:

 

具体推导忽略。 这大概是高中数学知识, 求某一个点到一条线的几何距离。直接将点的坐标带入到直线中得到一个值, 对这个值取绝对值, 然后用指向的向量qui求得的值进行归一化了。  

当yi= -1的时候, 带入求出的值是一个负数, 所以乘以yi就变成了正数。 这就是我们的几何距离了。

 现在我们的任务就是maximize这个minimum的margine就可以了(minimum的margin最大化了, 当然就是最大化所有的训练样本的marigin了, 这些距离decision boundary 最近的样本就是我们后面调到的support vectors(支持向量))。

我们的任务就变成了如下的最优化问题:

 

我们从直观上就知道, γ就是对应着距离decision boundary 最近的样本的距离了。 我们需要最大化这个值。

更进一步, 将上述式子简化为如下:

对于约束不等式, 我们可以通过如下化简(只要保证不等式是同一个不等式就好了):

令:

得到:

 上述优化问题等价于:

上述的问题其实是一个凸优化的问题。 (这样, 就变成了support vectors距离decision boundary 的距离等于1了。 但是, 问题又来了。 如果我们的样本不是线性可分的时候, 怎么办? 解决办法之一就是在不等式中我们可以引入slack variables Ci, 即不等式右边变成了 1 - Ci, 在目标函数中引入penalty, 即加上∑Ci。)我们利用拉格朗日乘子求解, 下面表达lagrangian如下:

或者如下:

下面写出上述式子KKT条件( Karush–Kuhn–Tucker (KKT) conditions)如下:

 

我们利用上述的KKT条件对上述的Lagrangian进行化简。

带入KKT的第一个条件化简得到:

带入KKT的第二个条件:

再一次的使用KKT的第一个条件, 得到:

将上述式子带入:

得到如下只是取决于a的式子。  配合着KKT的第二个条件和第三个条件, 我们得到上述原始问题的对偶问题(dual):

不难看出,约束条件是:m个ai均大于等于0, 等式是关于m个训练样本的标号和拉格朗日乘子系数的等式。

还有两个KKT的条件没有在上面的对偶问题中用到。 如下:

这两个式子分别为m个, 是关于和这m个训练样本之间的关系的。

最终, 我们的目标就变成了求解上述对偶问题的最优解。

我们可以采用如下两种办法求解。

(1)二次规划

(2)使用算法SMO。

一旦我们解出了最佳解:  我们就可以利用这个dual prolem的解直接获得原始问题(primal problem)的解。 我们可以直接吧这m个最佳值带入到KKT第一个条件得到最佳的梯度向量:

这个公式非常的nice, 使得我们能够很快的计算出decision boundary的梯度向量了。 还要注意一点, 只有支持向量对应的非0, 其他的非支持向量的样本对应的均为0.. 所以我们能够很快的计算出来。

我们利用support vector(支持向量, 即那些距离decision boundary为1的训练样本) 距离decision boundary求解处 :

注意, 可能不止一个支持向量, 但是我们只需要选择其中一个支持向量就可以计算出来, 假设选择一个支持向量的类标号为1, 则有:

另外, 由于support vector的margin最小(为1), 所以我们可以按照如下的方式rewrite:

一样的。

 

问题: 支持向量(support vectors):

支持向量是是训练样本集中距离decision boundary的margin为1的那些样本(这样的样本的数目不多, 支持着我们的decision boundary 的存在)。

使用KKT的第四个条件complementary slackness, 我们有如下的式子:

从上述式子, 可以看出, 只有支持向量对应的a*非0, 非支持向量的普通的样本对应的a*的值均为0。支持向量是样本集中的那些距离decision boundary的距离最小(为1)的那些样本。

 

上述讨论的问题都是对于训练样本集是线性可分的这个前提下进行的。 当训练样本不是线性可分的时候, 该如何做?

 

也有解决办法。 就是引入slack variables。 也就是条件松弛。 并对这些松弛变量进行惩罚。

例如, 我们的原始问题变成如下了:

 

上述右边的约束不等式的个数为2m个: m + m。

不难有如下观察:

如果, 我们就将设置为0。 相应的,目标函数中这个样本对应的penalty为0。 否则就有penaly

hyper parameter C控制着关于向量和惩罚项的tradeoff.  作用是使得(这样最小的margin就会变大)small的同时, 使得大多数的样本都具有最小为的margin。

 

对应与非线性可分的例子, 我们得到的相应的Lagrangian为:

上述问题的对偶问题也可以化成如下:

上述的式子分厂的neat and nice。

 

 

求解SVM的SMO算法。

SMO(sequential Minimal optimization)是一种用于求解SVM的坐标上升(coordinate ascent)的最优化算法。

对于如下的最优化问题:

 

如果我们选择固定住, 然后按照第一个坐标的方向take step, 也就是说改变以最大化上述的目标函数(关于a这m个参数的更新顺序问题, 有很多的heuristics, 这里不讨论), 我们就会遇到无法更新的地步, 因为约束等式的自由度为n-1:

根据约束不等式

 我们有:

由于固定, 所以也固定了。

所以为了求解这个最优化问题, 我们需要一次更新至少两个参数, 我们选择一次更新两个参数:

所以我们有如下图:

所以, 我们可以在上述的直线上来回移动。

进步的化简:

上述的函数是关于a2的二次函数。 我们只需要对a2求导, 令其等于0, 获得a2的值, 然后进入下一次SMO的迭代更新其他ai。  如果求导等于0得到的a2在区间[L, H]之外, 我们只需要令a2在下一次的迭代等于L或者等于H即可。 具体等于哪一个值,还得check 一次。

举个例子:

 

 

 

 

 

发表评论

0个评论

我要留言×

技术领域:

我要留言×

留言成功,我们将在审核后加至投票列表中!

提示x

人工智能机器学习知识库已成功保存至我的图谱现在你可以用它来管理自己的知识内容了

删除图谱提示×

你保存在该图谱下的知识内容也会被删除,建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗?

删除节点提示×

无法删除该知识节点,因该节点下仍保存有相关知识内容!

删除节点提示×

你确定要删除该知识节点吗?