SVM——(一)线性可分之目标函数推导方法1
最近在看支持向量机,也查了很多资料。其中关于如何推导出最终的优化目标函数(见文末
找了这么多资料,这绝对是直接用距离来推导出优化问题最详细的文章,赞!
一、SVM算法要解决什么问题
SVM的全称是Support Vector Machine,即支持向量机,主要用于解决模式识别领域中的数据分类问题,属于有监督学习算法的一种。SVM要解决的问题可以用一个经典的二分类问题加以描述。如图1所示,红色和蓝色的二维数据点显然是可以被一条直线分开的,在模式识别领域称为线性可分问题。然而将两类数据点分开的直线显然不止一条。图1(b)和(c)分别给出了A、B两种不同的分类方案,其中黑色实线为分界线,术语称为“决策面”。每个决策面对应了一个线性分类器。虽然在目前的数据上看,这两个分类器的分类结果是一样的,但如果考虑潜在的其他数据,则两者的分类性能是有差别的。
SVM算法认为图1中的分类器A在性能上优于分类器B,其依据是A的分类间隔比B要大。这里涉及到第一个SVM独有的概念“分类间隔”。在保证决策面方向不变且不会出现错分样本的情况下移动决策面,会在原来的决策面两侧找到两个极限位置(越过该位置就会产生错分现象),如虚线所示。虚线的位置由决策面的方向和距离原决策面最近的几个样本的位置决定。而这两条平行虚线正中间的分界线就是在保持当前决策面方向不变的前提下的最优决策面。两条虚线之间的垂直距离就是这个最优决策面对应的分类间隔。显然每一个可能把数据集正确分开的方向都有一个最优决策面,而不同方向的最优决策面的分类间隔通常是不同的,那个具有“最大间隔”的决策面就是SVM要寻找的最优解。而这个真正的最优解对应的两侧虚线所穿过的样本点,就是SVM中的支持样本点,称为“支持向量”。对于图1中的数据,A决策面就是SVM寻找的最优解,而相应的三个位于虚线上的样本点在坐标系中对应的向量就叫做支持向量。
从表面上看,我们优化的对象似乎是这个决策面的方向和位置。但实际上最优决策面的方向和位置完全取决于选择哪些样本作为支持向量。而在经过漫长的公式推导后,你最终会发现,其实与线性决策面的方向和位置直接相关的参数都会被约减掉,最终结果只取决于样本点的选择结果。
到这里,我们明确了SVM算法要解决的是一个最优分类器的设计问题。既然叫作最优分类器,其本质必然是个最优化问题。所以,接下来我们要讨论的就是如何把SVM变成用数学语言描述的最优化问题模型,这就是我们在第二部分要讲的“线性SVM算法的数学建模”。
二、线性SVM算法的数学建模
一个最优化问题通常有两个最基本的因素:
1)目标函数,也就是你希望什么东西的什么指标达到最好;
2)优化对象,你期望通过改变哪些因素来使你的目标函数达到最优。在线性SVM算法中,目标函数显然就是那个“分类间隔”,而优化对象则是决策面。所以要对SVM问题进行数学建模,首先要对上述两个对象(“分类间隔”和“决策面”)进行数学描述。按照一般的思维习惯,我们先描述决策面。
2.1 决策面方程
请你暂时不要纠结于n维空间中的n-1维超平面这种超出正常人想象力的情景。我们就老老实实地看看二维空间中的一根直线,我们从初中就开始学习的直线方程形式很简单。
现在我们做个小小的改变,让原来的
公式(2.3)的向量形式可以写成:
进一步可以写成如下形式:
其中,
就着公式(2.5),我们再稍稍尝试深入一点。那就是探寻一下向量
上面说了这么多,是想告诉你向量
到这里,我们花了很多篇幅描述一个很简单的超平面方程(其实只是个直线方程),这里真正有价值的是这个控制方向的参数
2.2 分类“间隔”的计算模型
我们在第一章里介绍过分类间隔的定义及其直观的几何意义。间隔的大小实际上就是支持向量对应的样本点到决策面的距离的二倍,如图2所示。
所以分类间隔计算似乎相当简单,无非就是点到直线的距离公式(推导见文中几何间隔)。公式如下:
这里
但问题当然不会这么简单,我们还需要面对一连串令人头疼的麻烦。
2.3 约束条件
接着2.2节的结尾,我们讨论一下究竟还有哪些麻烦没有解决:
1)并不是所有的方向都存在能够实现100%正确分类的决策面,我们如何判断一条直线是否能够将所有的样本点都正确分类?
2)即便找到了正确的决策面方向,还要注意决策面的位置应该在间隔区域的中轴线上,所以用来确定决策面位置的截距
3)即便取到了合适的方向和截距,公式
以上三条麻烦的本质是“约束条件”,也就是说我们要优化的变量的取值范围受到了限制和约束。事实上约束条件一直是最优化问题里最让人头疼的东西。但既然我们已经论证了这些约束条件确实存在,就不得不用数学语言对他们进行描述。尽管上面看起来是3条约束,但SVM算法通过一些巧妙的小技巧,将这三条约束条件融合在了一个不等式里面。
我们首先考虑一个决策面是否能够将所有的样本都正确分类的约束。图2中的样本点分成两类(红色和蓝色),我们为每个样本点
如果我们的决策面方程能够完全正确地对图2中的样本点进行分类,就会满足下面的公式:
如果我们要求再高一点,假设决策面正好处于间隔区域的中轴线上,并且相应的支持向量对应的样本点到决策面的距离为
符号
其中:
把
公式
2.4 线性SVM优化问题基本描述
公式
公式
另外我们还可以尝试将公式
好了,到这里我们可以给出线性SVM最优化问题的数学描述了:
这里m是样本点的总个数,缩写s. t. 表示“Subject to”,是“服从某某条件”的意思。公式
接下来,我们将在下一篇文章中讨论:如何利用最优化技术求解公式
一点小建议,读到这里,你可以试着在纸上随便画一些点,然后尝试用SVM的思想手动画线将两类不同的点分开。你会发现大多数情况下,你会先画一条可以成功分开两类样本点的直线,然后你会在你的脑海中想象去旋转这条线,旋转到某个角度,你就会下意识的停下来,因为如果再旋转下去,就找不到能够成功将两类点分开的直线了。这个过程就是对直线方向的优化过程。对于有些问题,你会发现SVM的最优解往往出现在不能再旋转下去的边界位置,这就是约束条件的边界,对比我们提到的等式约束条件,你会对代数公式与几何想象之间的关系得到一些相对直观的印象。
SVM——(七)SMO(序列最小最优算法)
SVM——(六)软间隔目标函数求解
SVM——(五)线性不可分之核函数
SVM——(四)目标函数求解
SVM——(三)对偶性和KKT条件(Lagrange duality and KKT condition)
SVM——(二)线性可分之目标函数推导方法2
SVM——(一)线性可分之目标函数推导方法1
参考资料: