机器学习技法—lecture1：Linear Support Vector Machine

Linear Support Vector Machine

摘要

学习完机器学习基石课程之后，我们接下来继续学习林轩田老师的机器学习技法课程，这是基石课程的进阶版，首先我们学习的是SVM。

本课程的设计主要基于feature transform进行展开，主要有以下三个方向：

1. 我们怎么运用不同的特征转换，并且在实现过程中控制模型的复杂度的问题，这个方向刺激了SVM模型的发展；

2. 我们能不能混合不同的特征去建立更有预测性的特征呢，这个方向刺激了adaboost演算法的发展；

3. 我们怎么让机器学到一些隐藏的特征的问题，这个方向促进了深度学习的发展。

1

Large-Margin Separating Hyperplane

我们首先回顾下我们学习过的线性分类的问题，现在对同一个问题，我们有三个选择（如下图），那其中哪一个是最好的选择呢？

经过分析可知，我们之前所学的PLA演算法和VC bound对这三种情形都无法判断孰优孰劣，但毫无疑问这三条线的分类效果是不一样的，因此我们需要确定分类器更优的标准，一个简单的标准是根据给一批测试数据时的分类准确率来判断，但我们没有测试数据，因此我们需要从训练数据角度思考。

从训练数据的角度思考，测试数据和训练数据取样来自同一个分布，我们假设他们是比较接近的，我们画出三种分类器对错误的容忍度，我们定义离直线的最近的点到直线的距离为这个衡量指标，可以知道这个距离越大，意味着这个分类器可以容忍更大的误差，可以对抗更多的过拟合，同样，我们可以对直线也定义类似的指标，相应的目标就变成求解最粗的线性分类器。

2

Standard Large-Margin Problem

于是我们建立了标准的large—margin problem，我们的目的是求解最大间隔的分割超平面，需要满足的限制条件是分割超平面需要将正负例完全分开。

我们将相关的目标函数和限制条件进行数学化，可以得到我们的目标即为上述的带条件的distance的最优化问题，由于wTx+b=0和3wTx+3b=0是一致的，也就是说缩放不改变点到直线的距离，于是我们进行一个特殊的缩放，可以得到下面的公式：

进一步，我们可以将约束条件放大为yn(wT xn + b) ≥ 1 ，我们使用反证法可以证明放大这个条件对最终问题的解是没有影响的，最后进行一些小的推演，可以得到简化后的标准的large-margin hyperplane 问题。

3

Support Vector Machine

接下来一个很实现的问题是如何解这样的问题，我们之前学习过的诸如梯度下降等方法目前看来并不适用了，不过我们可以借鉴前辈的经验使用二次规划的问题来解决，具体的流程如下，有兴趣的朋友可以深究下：

4

Reasons behind Large-Margin Hyperplane

最后我们来思考下SVM背后的理论保证，我们将其与regularization放在一起，我们发现二者的表现形式上有着惊人的相似性，这似乎在说SVM是一个regularization方法，只是要求更严格。

更进一步，我们从VC维度的角度来分析，我们知道SVM的目的是寻找那些有一定宽度边界的“胖胖的线”，加上了这个限制条件之后，相应的分类器的数量减少了，同时可以推导其VC维度理论上也是下降的。

一般情况下，hyperplane的数量是比较少的（付出的VC维度较低），同时他对应着比较简单的边界函数；特征转换后的hyperplane的数量会增长，同时他对应着更为复杂的边界函数，也能将Ein做的更好；我们知道large—margin hyperplane对应着更少的数量，于是我们可以结合非线性转换做出功能更强大的非线性SVM。

lecture1的内容主要是简单的SVM的介绍，首先我们从二元分类器的优化问题提出问题，然后我们推演得到标准的large—margin hyperplane问题，接着对他进行一些数学上的处理直到用QP方法来解决，最后我们分析了问题背后的理论保证和联系，下节课我们将着手实现非线性SVM。

小结