机器学习笔记6——支持向量机
对间隔分类器的优化
给定一组训练集,通过找到一个决策边界并且将间隔最大化,对训练数据的预测得到的结果就是足够正确的。因而,在分类器中会有一个“缝隙”(几何间隔)将正负向的训练样本分割开来。
现在,我们假设给定的数据集是线性可分的,即可以通过超平面将正负向的训练样本分开。我们如何找到使几何间隔达到最大值的分类器呢?我们可以引出如下优化问题:
我们打算将参数
但最大化参数
问题变成了最大化
接着往下分析。回忆我们之前的讨论,对参数
无论对参数
这样一来,只要放缩操作影响了最终的函数间隔的值,都需要重新调整放缩。同时,可以对问题进行转化,最大化
这一优化问题的形式上的转化让问题变得更容易解决。上述的优化问题就成了只有线性约束的凸二次问题。这一形式的优化问题就是最优化间隔分类器的问题。这一问题可以用商业的二次规划软件(QP)进行优化。
接下来我们岔开话题讨论一下拉格朗日对偶性,了解过后我们会得到优化问题的对偶格式——这一格式是我们在之后讲到核问题时的关键。核使得在高维度的空间中最优间隔分类器依旧有良好的表现效果。对偶格式也可以推导出一个表现良好的算法用以解决上述的优化问题,且得到的这个算法的表现比QP软件要好。
拉格朗日对偶性
接下来我们要讨论如何解决优化问题的约束。
思考如下形式的问题:
受约束的优化问题可以使用拉格朗日算子来解决。在这一方法中,我们定义了拉格朗日函数:
函数中的参数
在这一小节中,我们会将受到约束的优化问题进行一般化,其中包括等式约束和不等式约束。因为篇幅的原因,不会讲述拉格朗日对偶性的完整理论,但是会给出主要的思想和结果,这些都可以运用到我们的优化间隔分类器问题上。
考虑下面这个问题:
这一问题被称作原始优化问题。为了解决这一问题,我们需要开始定义一般化的拉格朗日函数:
其中,参数
其中下标“P”代表“原始的”。参数
相反地,如果约束满足一个特定值
因此,在参数
值相等;而参数不满足约束的话,
从等式中可以看出这与我们原始的问题相同。为了后续的使用,我们也可以定义目标优化问题的值为
现在,我们来稍有不同的问题,我们定义:
其中,下标
上面的等式是对偶优化问题,这与我们之前的原始问题相同,除了“max”与“min”的顺序相反。我们同样定义了目标优化问题的值:
那么问题来了,原始问题与对偶问题之间又有什么关联呢?其实很简单:
在特定情况下,有
假设
解析:前面提到过很多次非凸性与凸性,可能有很多人不是很理解到底是个什么概念,这里具体解释一下。
当
举个例子,
至于什么是affine函数,此处也有定义。例如,存在参数
继续上面的话题。假设
基于上述的几个假设,一定存在
同时,如果存在
现在我们来观察等式(5),这一等式被称为KKT对偶互补条件。如果
之后我们会根据这一点,知道支持向量机中只有少部分的“支持向量”;在我们讲述SMO算法时也会利用KKT对偶互补条件做收敛性实验。
间隔分类器的优化
在之前我们提出了原始优化问题来优化间隔分类器:
还可以把约束写成这种格式:
针对每一个训练样本都有一个这样的约束。从这个约束以及KKT对偶互补条件中可知,只有当训练样本的函数间隔等于1时,约束中的
上图显示的是由实线代表的最大间隔分类超平面。图中间隔最小的点也是离决策边界最近的点。此时,图中有3个点(1负2正样本)在与决策边界平行的虚线上。因此,只有3个训练样本,会在优化问题的优化过程中
在之前的讲述中,我们推导出了优化问题的对偶形式。要注意的一个关键点是:我们会利用输入特征中任意两点的内积
针对优化问题我们创建对应的拉格朗日函数:
此处的拉格朗日算子只有
之后我们来找优化问题的对偶形式。此处需要将上述的拉格朗日函数分别对参数
得到结果:
然后对参数
如果我们取等式(9)中关于
但是从等式(10)中可知,最后一项必须为0,所以又得到:
回忆我们之前
我们同样需要知道,我们的优化问题同样还满足
我们将在之后讲述解决对偶问题的特殊算法,但是如果我们真的解决了这个问题(找到了满足约束,且使
在继续讲述之前,我们再次来研究一下等式(9),通过参数
因此,如果我们找到了
均为0。因此,之前讲述的所有项中很多值都为0,而且为了计算等式(13)来做预测,很有必要找到
通过对对偶形式的优化问题的观察,我们对问题的结构有了深刻的了解,也可以通过内积的形式写出整个算法。
下一小节中,我们将利用这个属性应用到核分类问题。由此产生的算法,支持向量机,会在高纬度的特征空间中有良好的学习表现。