搜索
w支持向量机:MaximumMarginClassifierbypluskid,on2010-09-08,inMachineLearning84comments支持向量机即SupportVectorMachine，简称SVM。我最开始听说这头机器的名号的时候，一种神秘感就油然而生，似乎把Support这么一个具体的动作和Vector这么一个抽象的概念拼到一起，然后再做成一个Machine，一听就很玄了！不过后来我才知道，原来SVM它并不是一头机器，而是一种算法，或者，确切地说，是一类算法，当然，这样抠字眼的话就没完没了了，比如，我说SVM实际上是一个分类器(Classifier)，但是其实也是有用SVM来做回归(Regression)的。所以，这种字眼就先不管了，还是从分类器说起吧。SVM一直被认为是效果最好的现成可用的分类算法之一（其实有很多人都相信，“之一”是可以去掉的）。这里“现成可用”其实是很重要的，因为一直以来学术界和工业界甚至只是学术界里做理论的和做应用的之间，都有一种“鸿沟”，有些很fancy或者很复杂的算法，在抽象出来的模型里很完美，然而在实际问题上却显得很脆弱，效果很差甚至完全fail。而SVM则正好是一个特例——在两边都混得开。好了，由于SVM的故事本身就很长，所以废话就先只说这么多了，直接入题吧。当然，说是入贴，但是也不能一上来就是SVM，而是必须要从线性分类器开始讲。这里我们考虑的是一个两类的分类问题，数据点用x来表示，这是一个n维向量，而类别用y来表示，可以取1或者-1，分别代表两个不同的类（有些地方会选0和1，当然其实分类问题选什么都无所谓，只要是两个不同的数字即可，不过这里选择+1和-1是为了方便SVM的推导，后面就会明了了）。一个线性分类器就是要在n维的数据空间中找到一个超平面，其方程可以表示为一个超平面，在二维空间中的例子就是一条直线。我们希望的是，通过这个超平面可以把两类数据分隔开来，比如，在超平面一边的数据点所对应的y全是-1，而在另一边全是1。具体来说，我们令f(x)=wTx+b，显然，如果f(x)=0，那么x是位于超平面上的点。我们不妨要求对于所有满足f(x)0的点，其对应的y等于-1，而f(x)0则对应y=1的数据点。当然，有些时候（或者说大部分时候）数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在，不过关于如何处理这样的问题我们后面会讲，这里先从最简单的情形开始推导，就假设数据都是线性可分的，亦即这样的超平面是存在的。如图所示，两种颜色的点分别代表两个类别，红颜色的线表示一个可行的超平面。在进行分类的时候，我们将数据点x代入f(x)中，如果得到的结果小于0，则赋予其类别-1，如果大于0则赋予类别1。如果f(x)=0，则很难办了，分到哪一类都不是。事实上，对于f(x)的绝对值很小的情况，我们都很难处理，因为细微的变动（比如超平面稍微转一个小角度）就有可能导致结果类别的改变。理想情况下，我们希望f(x)的值都是很大的正数或者很小的负数，这样我们就能更加确信它是属于其中某一类别的。从几何直观上来说，由于超平面是用于分隔两类数据的，越接近超平面的点越“难”分隔，因为如果超平面稍微转动一下，它们就有可能跑到另一边去。反之，如果是距离超平面很远的点，例如图中的右上角或者左下角的点，则很容易分辩出其类别。实际上这两个Criteria是互通的，我们定义functionalmargin为γˆ=y(wTx+b)=yf(x)，注意前面乘上类别y之后可以保证这个margin的非负性（因为f(x)0对应于y=−1的那些点），而点到超平面的距离定义为geometricalmargin。不妨来看看二者之间的关系。如图所示，对于一个点x，令其垂直投影到超平面上的对应的为x0，由于w是垂直于超平面的一个向量（请自行验证），我们有又由于x0是超平面上的点，满足f(x0)=0，代入超平面的方程即可算出不过，这里的γ是带符号的，我们需要的只是它的绝对值，因此类似地，也乘上对应的类别y即可，因此实际上我们定义geometricalmargin为：显然，functionalmargin和geometricalmargin相差一个∥w∥的缩放因子。按照我们前面的分析，对一个数据点进行分类，当它的margin越大的时候，分类的confidence越大。对于一个包含n个点的数据集，我们可以很自然地定义它的margin为所有这n个点的margin值中最小的那个。于是，为了使得分类的confidence高，我们希望所选择的hyperplane能够最大化这个margin值。不过这里我们有两个margin可以选，不过functionalmargin明显是不太适合用来最大化的一个量，因为在hyperplane固定以后，我们可以等比例地缩放w的长度和b的值，这样可以使得f(x)=wTx+b的值任意大，亦即functionalmarginγˆ可以在hyperplane保持不变的情况下被取得任意大，而geometricalmargin则没有这个问题，因为除上了∥w∥这个分母，所以缩放w和b的时候γ˜的值是不会改变的，它只随着hyperplane的变动而变动，因此，这是更加合适的一个margin。这样一来，我们的maximummarginclassifier的目标函数即定义为当然，还需要满足一些条件，根据margin的定义，我们有其中，根据我们刚才的讨论，即使在超平面固定的情况下，γˆ的值也可以随着∥w∥的变化而变化。由于我们的目标就是要确定超平面，因此可以把这个无关的变量固定下来，固定的方式有两种：一是固定∥w∥，当我们找到最优的γ˜时γˆ也就可以随之而固定；二是反过来固定γˆ，此时∥w∥也可以根据最优的γ˜得到。处于方便推导和优化的目的，我们选择第二种，令γˆ=1，则我们的目标函数化为：通过求解这个问题，我们就可以找到一个margin最大的classifier，如下图所示，中间的红色线条是OptimalHyperPlane，另外两条线到红线的距离都是等于γ˜的：到此为止，算是完成了MaximumMarginClassifier的介绍，通过最大化margin，我们使得该分类器对数据进行分类时具有了最大的confidence（实际上，根据我们说给的一个数据集的margin的定义，准确的说，应该是“对最不confidence的数据具有了最大的confidence”——虽然有点拗口）。不过，到现在似乎还没有一点点SupportVectorMachine的影子。很遗憾的是，这个要等到下一次再说了，不过可以先小小地剧透一下，如上图所示，我们可以看到hyperplane两边的那个gap分别对应的两条平行的线（在高维空间中也应该是两个hyperplane）上有一些点，显然两个hyperplane上都会有点存在，否则我们就可以进一步扩大gap，也就是增大γ˜的值了。这些点呢，就叫做supportvector，嗯，先说这么多了。支持向量机:SupportVectorbypluskid,on2010-09-10,inMachineLearning49comments本文是“支持向量机系列”的第二篇，参见本系列的其他文章。上一次介绍支持向量机，结果说到MaximumMarginClassifier，到最后都没有说“支持向量”到底是什么东西。不妨回忆一下上次最后一张图：可以看到两个支撑着中间的gap的超平面，它们到中间的separatinghyperplane的距离相等（想想看：为什么一定是相等的？），即我们所能得到的最大的geometricalmarginγ˜。而“支撑”这两个超平面的必定会有一些点，试想，如果某超平面没有碰到任意一个点的话，那么我就可以进一步地扩充中间的gap，于是这个就不是最大的margin了。由于在n维向量空间里一个点实际上是和以原点为起点，该点为终点的一个向量是等价的，所以这些“支撑”的点便叫做支持向量。很显然，由于这些supportingvector刚好在边界上，所以它们是满足y(wTx+b)=1（还记得我们把functionalmargin定为1了吗？），而对于所有不是支持向量的点，也就是在“阵地后方”的点，则显然有y(wTx+b)1。事实上，当最优的超平面确定下来之后，这些后方的点就完全成了路人甲了，它们可以在自己的边界后方随便飘来飘去都不会对超平面产生任何影响。这样的特性在实际中有一个最直接的好处就在于存储和计算上的优越性，例如，如果使用100万个点求出一个最优的超平面，其中是supportingvector的有100个，那么我只需要记住这100个点的信息即可，对于后续分类也只需要利用这100个点而不是全部100万个点来做计算。（当然，通常除了K-NearestNeighbor之类的Memory-basedLearning算法，通常算法也都不会直接把所有的点记忆下来，并全部用来做后续inference中的计算。不过，如果算法使用了Kernel方法进行非线性化推广的话，就会遇到这个问题了。Kernel方法在下一次会介绍。）当然，除了从几何直观上之外，支持向量的概念也会从其优化过程的推导中得到。其实上一次还偷偷卖了另一个关子就是虽然给出了目标函数，却没有讲怎么来求解。现在就让我们来处理这个问题。回忆一下之前得到的目标函数：这个问题等价于（为了方便求解，我在这里加上了平方，还有一个系数，显然这两个问题是等价的，因为我们关心的并不是最优情况下目标函数的具体数值）：到这个形式以后，就可以很明显地看出来，它是一个凸优化问题，或者更具体地说，它是一个二次优化问题——目标函数是二次的，约束条件是线性的。这个问题可以用任何现成的QP(QuadraticProgramming)的优化包进行求解。所以，我们的问题到此为止就算全部解决了，于是我睡午觉去了~啊？呃，有人说我偷懒不负责任了？好吧，嗯，其实呢，虽然这个问题确实是一个标准的QP问题，但是它也有它的特殊结构，通过LagrangeDuality变换到对偶变量(dualvariable)的优化问题之后，可以找到一种更加有效的方法来进行求解——这也是SVM盛行的一大原因，通常情况下这种方法比直接使用通用的QP优化包进行优化要高效得多。此外，在推导过程中，许多有趣的特征也会被揭露出来，包括刚才提到的supportingvector的问题。关于Lagrangeduality我没有办法在这里细讲了，可以参考Wikipedia。简单地来说，通过给每一个约束条件加上一个Lagrangemultiplier，我们可以将它们融和到目标函数里去(参见高数中的带约束条件的求极值问题，使用拉格朗日数乘法)然后我们令容易验证，当某个约束条件不满足时，例如yi(wTxi+b)1，那么我们显然有θ(w)=∞（只要令αi=∞即可）。而当所有约束条件都满足时，则有θ(w)=12∥w∥2，亦即我们最初要最小化的量。因此，在要求约束条件得到满足的情况下最小化12∥w∥2实际上等价于直接最小化θ(w)（当然，这里也有约束条件，就是αi≥0,i=1,…,n），因为如果约束条件没有得到满足，θ(w)会等于无穷大，自然不会是我们所要求的最小值。具体写出来，我们现在的目标函数变成了：这里用p∗表示这个问题的最优值，这个问题和我们最初的问题是等价的。不过，现在我们来把最小和最大的位置交换一下：当然，交换以后的问题不再等价于原问题，这个新问题的最优值用d∗来表示。并，我们有d∗≤p∗，这在直观上也不难理解，最大值中最小的一个总也比最小值中最大的一个要大吧！总之，第二个问题的最优值d∗在这里提供了一个第一个问题的最优值p∗的一个下界，在满足某些条件的情况下，这两者相等，这个时候我们就可以通过求解第二个问题来间接地求解第一个问题。具体来说，就是要满足KKT条件，这里暂且先略过不说，直接给结论：我们这里的问题是满足KKT条件的，因此现在我们便转化为求解第二个问题。首先要让L关于w和b最小化，我们分别令∂L/∂w和∂L/∂