逻辑斯蒂回归与线性SVM

SVM，全称Support Vector Machines，中文叫做支持向量机，是最常用的机器学习算法之一。SVM的出现对机器学习的理论发展具有里程碑式的意义。而与此同时，SVM又是一个非常接地气的算法，模型的训练过程并不算复杂，而预测的过程则更加简单和优美。市面上存在着各种SVM的开源实现，而对于大部分的分类问题，SVM都可以得到比较好的分类效果，作为baseline，总是可以在各种paper中作为背景帝出现。

以前我对SVM的具体算法一直有畏惧的情绪。那是因为一次人工智能课的开卷考试，居然出了一道问答题让我回答什么是支持向量机（这里不得不黑一下母校当年的出卷老师，这里就不点名了）。我当时一个学期没怎么上过课，考前也没有看过书，对于SVM一无所知，只记得当时抄了整整一面卷子的公式，只觉天昏地暗。从此，心理就对SVM就产生了一种畏惧的情绪。直到若干年以后，我才慢慢领悟到，原来SVM并没有这么难，其实是可以用很简单的话就能够说清楚的。然而，后来我发现我又错了，但这是后话了。这里，我尝试先抛开各种繁琐的公式与理论，简单的说说我的SVM的直观理解。

机器学习中的分类问题，看起来其实并不是太复杂。最直接的做法，是把已经标好的正负样本点都放在它们所在的线性空间进行观察。需要学习的分类函数则是这个空间里的一个平面或者曲面，能够很好地把训练集中的正负样本分隔开来，当然，更重要的是，还需要对训练数据以外的数据同样起作用。为了描述简单，我们就假设所有的样本都是二维空间中的一个点，而针对这样样本的线性分类器，则是在平面上的一条直线。

下面的图展示了一个成功的线性分类器，它成功地分隔了训练数据集中的正样本和负样本（分别对应图中的原点和方点）。这个场景就像刚刚摆好棋子的象棋盘，双方棋子各在楚河汉界一边，泾渭分明。当然，这样的情况往往只在理想中，很少出现在现实世界，否则，也不用去花这么多的力气研究各种各样的分类算法了。不过，这样一个简单的例子，可以作为理解SVM的一个开始。

前面给出了分类器的直观几何解释，下面来用代数的语言简单的对这个分类的问题进行一下描述。对于上面空间中的每一个点，可以用一个向量xi来表示。最后分类的结果，可以用(+1,?1)表示，分别对应正样本和负样本。而我们学习的分类器则可以看成是一个这样的函数f，它的输入是x，输出f(x)则是+1或?1中的某一个值。显然，这个分类函数与上图中的分类平面有着非常密切的联系。

考虑上面图中的情况，假设这个分类直线的方程是 x(1)w(1)+x(2)w(2)+b=0，正样本在直线的上方，负样本在直线的下方，当x(1)w(1)+x(2)w(2)+b>0时，点x应该处在直线上方，是正样本，而当x(1)w(1)+x(2)w(2)+b<0时，x则被这条分类直线看做是负样本。当维度升高时，之前的二维分类直线变成了高维空间中的超平面，上面的情况依然是适用的。那么参照超平面的方程，就可以写出线性分类器情况下分类函数f的一种形式：

f(x)=sign(xTw+b)

其中x=(x(1),x(2),…)T，w=(w(1),w(2),…)T ，sign是取符号的函数啦。这样，在给定了一组的训练样本之后，我们就可以根据定义的损失函数进行优化，从而得到最优的分类函数f。可这个优化的过程有一个没有解决的问题，就是取符号的这个sign函数引入之后，f的求解变得不是那么容易。假如说我们把square loss作为目标的损失函数，那么最终的目标函数可以写成这样的形式：

minimize∑i=1n(sign(wTxi+b)?yi)2

其中 n 表示训练样本的个数，yi∈(?1,+1)。为了求出最优的w与b， 我们需要求损失函数对w和b的导数。可是显然，取符号的函数sign并不是处处可求导的，所以这一条思路的进展并不顺利。这时我们很常见的一个办法就是把问题简化为我们熟悉的场景，用熟悉的方法来解决，那么最简单的方法就是暂时去掉sign函数，这时目标函数就变成了：

minimize∑i=1n(wTxi+b?yi)2

上面这个问题其实就是一个标准的线性回归问题，直接就可以用最小二乘法求解了。这样学习出来的目标函数的意义是什么呢？大概可以这样理解：之前我们要求预测的输出必须是+1或者?1，但是这个很难满足，放松之后，我们希望正样本预测的得分和+1尽量接近，比如是个0.8或者1.2，而负样本预测的得分和?1尽量接近。这样一来，我们比较样本预测得分的大小，也可以设置一个阈值(比如说是0)，把正负样本区分开了。乍一看，这个思路也合情合理，但是却有着一个致命的缺点。

我们知道任何一个点xi到直线wTx+b=0的距离是 :

|wTxi+b|∥w∥

那么对于正样本xi(既yi=1)来说，我们希望wTxi+b尽量和+1接近，也就是希望分类平面尽量的在x_i的下方，且和xi的距离尽量接近于 1∥w∥。而负样本的情形也与之类似。在某些场景下，为了满足这个要求，可能会跟我们分类函数的效果带来一些不必要的损失。

上面的图给出了一类很有代表性的例子，有一类样本的分布范围非常大，很多样本距离分类平面非常远。此时，如果还需要按之前的目标函数来求解f，则f应该选择f1对应的直线，才能保证绝大多数的点距离直线的距离是相同的。可这样所造成的后果是对一部分样本点的误分类，真正能够正确进行分类的应该是f2所对应的分类平面。如果仔细分析出现这样的根本原因，是因为我们在优化目标函数是，对所有数据点都是一视同仁的，但实际上并不是所有训练样本对分类函数都应该有相同的贡献，这实际上是线性分类与线性回归这两类问题的根本区别。回归问题考虑的是要尽量把所有的样本点都预测到目标值，而对于分类问题来说，由于算法关心的只是预测结果的符号而非具体数值，所以靠近分类平面的样本点应该在学习分类函数的过程中比原理分类平面的点起到更大的作用。这个区别决定了对分类问题，需要设计针对性的算法，而不是简单套用线性回归的思路。

下面的图中给出了两种解决策略。策略1是对数据点或者说对于损失函数进行一个映射，将所有样本点非线性的向靠近分类平面的方向进行映射。使得在计算损失函数时，离分类平面较远的数据点映射之后与分类平面的距离大大减小，而离分类平面较近的点与分类平面的距离也有一定程度的减少（但减少程度远小于远离分类平面的样本点）。这样的映射之后，样本点自然向分类平面靠拢，也就避免了之前出现的问题。策略2则是更加极端的一种做法，它索性移除了远离分类平面的所有数据点，只选择和分类平面距离较近的一些数据点，利用这些点学习出分类平面。而通过这种方法学习出的分类器，也自然能够对远离分类平面的数据点进行正确的分类。

由此可见，上面两个策略的基本思想都是为了减小离分类平面较远的样本点对分类器学习的影响。策略1采用相对温和的方法，通过非线性的映射减少这些远离平面数据点对结果的影响，而策略2则更加偏激，直接在模型中去掉了那些数据点，只保留与分类平面距离较近的数据点。实际上，策略1对应的算法就是逻辑斯蒂回归(Logistic Regression)，而策略2对应的算法就是我们要重点介绍的支持向量机(Support Vector Machines)，而在此策略中被保留的那些数据点则被叫做支持向量(Support Vectors)。