机器学习——支持向量机(SVM)

作者:helen1313

本文主要参考吴恩达《机器学习》课程,以及网上各个大牛们的博文。

支持向量机,是一种对线性和非线性数据进行分类的方法。它按以下方法工作:使用一种非线性映射,把原训练数据映射到较高的维上,在新的维上,它搜索最佳分离超平面。使用到足够高维上的、合适的非线性映射,两个类的数据总可以被超平面分开。与其他模型相比,支持向量机不太容易过拟合。

下面按照吴恩达《机器学习》的讲义顺序进行讲解。

1 从逻辑回归到支持向量机

支持向量机从本质上来讲,就是最大间隔分类器。

这边从逻辑回归引出支持向量机,以及它最重要的思路——最大间隔。

考虑逻辑回归:


换种思路,如下图,x是正类(y=1),o是负类(y=0),直线为分类超平面,A点离超平面很远,则预测A点为正类可信度很高,而C点离超平面很近,如果超平面稍有变化,可能C点就变成了负类,所以预测C点为正类的可信度比较低。


上图中,要把x类和o类分开,可以有无线多条分离直线,我们想找出“最好的”一条,使得两种类别中离分离直线最近的点,到分离直线的距离最大。这就是最大间隔分类器。

2    标记

考虑一个线性二元分类器:


3    函数间隔和几何间隔

1 函数间隔

给定一个样本点  ,其函数间隔:

1. 如果y=1,想要预测更为准确,则要求 是一个大的正数;

2. 如果y=-1,想要预测更为准确,则要求 是一个大的负数;

结论:如果 ,则对于该样本点的预测是正确的,一个大的函数间隔代表着一个可信度高且正确的预测。

 

函数间隔的一个缺点:w和b成倍扩大或缩减,不改变h(x)的值(h(x)只和符号有关),但是函数间隔却成倍的扩大或缩减了。

 

给定一个训练集  ,其函数间隔为所有样本点函数间隔的最小值:


2      几何间隔


给定一个样本点  ,其几何间隔就是点到面的距离(如上图A点到直线的距离AB)。

下面给出几何间隔的求解过程:

已知:

向量w垂直于超平面,则为垂直于超平面的单位向量;

A点的坐标:  ,其中A点为正类(y=1);

B点为A点在超平面上的投影,则几何间隔就是AB的长度。

求解AB:

A点: ,则B点: ,由于B点在超平面上,所以代入超平面中等于0,即:


上述为正类A点的几何间隔,一般的,给定一个训练样本 ,其几何间隔表示如下:


根据以上,可以得到:

1, 如果  ,函数间隔=几何间隔。

2, 几何间隔不会受w,b的缩放影响,因此我们可以随意规定w,比如令

 

给定一个训练集  ,其几何间隔为所有样本点几何间隔的最小值:


4          最优间隔分类器

给定一个训练集,找到一个决策边界,最大化其几何间隔。

假设给定的训练集是线性可分的,即可找到一个超平面将正类和负类分离,如何找到这样的超平面,使得几何间隔最大化?

可用以下优化问题:

优化目标是几何间隔  ,约束是 (这样几何间隔  =函数间隔  ),每个样本的函数间隔都小于函数间隔 (也就是几何间隔 )。

由于 是一个非凸函数,不好求解(梯度下降法需要凸函数才能求解,不然会求解局部最优解,而不是全局最优解)。因此将上述问题修改如下:

同样,优化目标是几何间隔,这里用函数间隔 来表示。

这里就不再需要 这个约束条件了。但是 是一个非凸函数,还是不能求解。

上面有说过,w,b的缩放,不影响几何间隔以及决策边界等。这里我们缩放w,b,使得函数间距 ,则上述优化问题变形为:


这个优化问题可以被有效的求解,一个凸二次目标函数,以及线性约束条件。这个优化问题的求解,最终得到我们的最优间隔分类器。可用二次规划求解。

发表评论

0个评论

我要留言×

技术领域:

我要留言×

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

提示x

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

删除图谱提示×

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

删除节点提示×

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

删除节点提示×

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