首页 » 机器学习实战 » 机器学习实战全文在线阅读

《机器学习实战》6.2 寻找最大间隔

关灯直达底部

如何求解数据集的最佳分隔直线?先来看看图6-3。分隔超平面的形式可以写成wTx+b。要计算点A到分隔超平面的距离,就必须给出点到分隔面的法线或垂线的长度,该值为|wTA+b|/||w||。这里的常数b类似于Logistic回归中的截距w0。这里的向量w和常数b一起描述了所给数据的分隔线或超平面。接下来我们讨论分类器。

 

图6-3 A到分隔平面的距离就是该点到分隔面的法线长度

6.2.1 分类器求解的优化问题

前面已经提到了分类器,但还没有介绍它的工作原理。理解其工作原理将有助于理解基于优化问题的分类器求解过程。输入数据给分类器会输出一个类别标签,这相当于一个类似于Sigmoid的函数在作用。下面将使用类似海维赛德阶跃函数(即单位阶跃函数)的函数对wTx+b作用得到f(wTx+b),其中当u<0f(u)输出-1,反之则输出+1。这和前一章的Logistic回归有所不同,那里的类别标签是0或1。

这里的类别标签为什么采用1和+1,而不是0和1呢?这是由于1和+1仅仅相差一个符号,方便数学上的处理。我们可以通过一个统一公式来表示间隔或者数据点到分隔超平面的距离,同时不必担心数据到底是属于1还是+1类。

当计算数据点到分隔面的距离并确定分隔面的放置位置时,间隔是通过label * (wTx+b)1来计算,这时就能体现出-1和+1类的好处了。如果数据点处于正方向(即+1类)并且离分隔超平面很远的位置时,wTx+b会是一个很大的正数,同时label * (wTx+b)也会是一个很大的正数。而如果数据点处于负方向(-1类)并且离分隔超平面很远的位置时,此时由于类别标签为-1,则label * (wTx+b)仍然是一个很大的正数。

现在的目标就是找出分类器定义中的wb。为此,我们必须找到具有最小间隔的数据点,而这些数据点也就是前面提到的支持向量。一旦找到具有最小间隔的数据点,我们就需要对该间隔最大化。这就可以写作:

直接求解上述问题相当困难,所以我们将它转换成为另一种更容易求解的形式。首先考察一下上式中大括号内的部分。由于对乘积进行优化是一件很讨厌的事情,因此我们要做的是固定其中一个因子而最大化其他因子。如果令所有支持向量的label * (wTx+b)都为1,那么就可以通过求||w||-1的最大值来得到最终解。但是,并非所有数据点的label * (wTx+b)都等于1,只有那些离分隔超平面最近的点得到的值才为1。而离超平面越远的数据点,其label * (wTx+b)的值也就越大。

在上述优化问题中,给定了一些约束条件然后求最优值,因此该问题是一个带约束条件的优化问题。这里的约束条件就是label * (wTx+b)≥ 1.0。对于这类优化问题,有一个非常著名的求解方法,即拉格朗日乘子法。通过引入拉格朗日乘子,我们就可以基于约束条件来表述原来的问题。由于这里的约束条件都是基于数据点的,因此我们就可以将超平面写成数据点的形式。于是,优化目标函数最后可以写成:

其约束条件为:

至此,一切都很完美,但是这里有个假设:数据必须100%线性可分。目前为止,我们知道几乎所有数据都不不可能那么“干净”。这时我们就可以通过引入所谓松弛变量(slack variable),来允许有些数据点可以处于分隔面的错误一侧。这样我们的优化目标就能保持仍然不变,但是此时新的约束条件则变为:

这里的常数C用于控制“最大化间隔”和“保证大部分点的函数间隔2小于1.0”这两个目标的权重。在优化算法的实现代码中,常数C是一个参数,因此我们就可以通过调节该参数得到不同的结果。一旦求出了所有的alpha,那么分隔超平面就可以通过这些alpha来表达。这一结论十分直接,SVM中的主要工作就是求解这些alpha

2. 被称为点到分隔面的函数间隔,称为点分隔面的几何间隔。——译者注

要理解刚才给出的这些公式还需要大量的知识。如果你有兴趣,我强烈建议去查阅相关的教材3,4,以获得上述公式的推导细节。

3. Christopher M. Bishop, Pattern Recognition and Machine Learning (Springer, 2006).

4. Bernhard Schlkopf and Alexander J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization,and Beyond (MIT Press, 2001).

6.2.2 SVM应用的一般框架

在第1章中,我们定义了构建机器学习应用的一般步骤,但是这些步骤会随机器学习任务或算法的不同而有所改变,因此有必要在此探讨如何在本章中实现它们。

SVM的一般流程

  1. 收集数据:可以使用任意方法。
  2. 准备数据:需要数值型数据。
  3. 分析数据:有助于可视化分隔超平面。
  4. 训练算法:SVM的大部分时间都源自训练,该过程主要实现两个参数的调优。
  5. 测试算法:十分简单的计算过程就可以实现。
  6. 使用算法:几乎所有分类问题都可以使用SVM,值得一提的是,SVM本身是一个二类分类器,对多类问题应用SVM需要对代码做一些修改。

到目前为止,我们已经了解了一些理论知识,我们当然希望能够通过编程,在数据集上将这些理论付诸实践。下一节将介绍一个简单但很强大的实现算法。