支持向量机讲解(很详
细明了)
w支持向量机: Maximum Margin Classifier
by pluskid, on 2010-09-08, in Machine Learning84 comments
支持向量机即Support Vector Machine，简称 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)=w T x+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 是互通的，我们定义 functional margin
为γ?=y(w T x+b)=yf(x)，注意前面乘上类别y之后可以保证这个 margin 的非
负性（因为f(x)<0对应于y=?1的那些点），而点到超平面的距离定义为geometrical margin 。不妨来看看二者之间的关系。如图所示，对于一个
点x，令其垂直投影到超平面上的对应的为x0，由于w是垂直于超平面的一个向量（请自行验证），我们有
又由于x0是超平面上的点，满足f(x0)=0，代入超平面的方程即可算出
不过，这里的γ是带符号的，我们需要的只是它的绝对值，因此类似地，也乘
上对应的类别y即可，因此实际上我们定义 geometrical margin 为：
显然，functional margin 和 geometrical margin 相差一个∥w∥的缩放因子。按照我们前面的分析，对一个数据点进行分类，当它的 margin 越大的时候，分类的 confidence 越大。对于一个包含n个点的数据集，我们可以很自然地定义它的 margin 为所有这n个点的 margin 值中最小的那个。于是，为了使得分类的 confidence 高，我们希望所选择的 hyper plane 能够最大化这个margin 值。
不过这里我们有两个 margin 可以选，不过 functional margin 明显是不太适合用来最大化的一个量，因为在 hyper plane 固定以后，我们可以等比例地缩
放w的长度和b的值，这样可以使得f(x)=w T x+b的值任意大，亦即functional margin γ?可以在 hyper plane 保持不变的情况下被取得任意大，而geometrical margin 则没有这个问题，因为除上了∥w∥这个分母，所以缩放w和b的时候γ?的值是不会改变的，它只随着 hyper plane 的变动而变动，因此，这是更加合适的一个 margin 。这样一来，我们的 maximum margin classifier 的目标函数即定义为
当然，还需要满足一些条件，根据 margin 的定义，我们有
其中，根据我们刚才的讨论，即使在超平面固定的情况下，
γ?的值也可以随着∥w∥的变化而变化。由于我们的目标就是要确定超平面，因此可以把这个无关的变量固定下来，固定的方式有两种：一是固定∥w ∥，当我们找到最优的γ?时γ?也就可以随之而固定；二是反过来固定γ?，此时∥w∥也可以根据最优的γ?得到。处于方便推导和优化的目的，我们选择第二种，令γ?=1，则我们的目标函数化为：
通过求解这个问题，我们就可以找到一个 margin 最大的 classifier ，如下图所示，中间的红色线条是 Optimal Hyper Plane ，另外两条线到红线的距离都是
等于γ?的：
到此为止，算是完成了 Maximum Margin Classifier 的介绍，通过最大化margin ，我们使得该分类器对数据进行分类时具有了最大的 confidence （实际上，根据我们说给的一个数据集的 margin 的定义，准确的说，应该是“对最不 confidence 的数据具有了最大的confidence”——虽然有点拗口）。不过，到现在似乎还没有一点点 Support Vector Machine 的影子。很遗憾的是，这个要等到下一次再说了，不过可以先小小地剧透一下，如上图所示，我们可以看到 hyper plane 两边的那个 gap 分别对应的两条平行的线（在高维空间中也应该是两个 hyper plane）上有一些点，显然两个 hyper plane 上都会有点存在，
否则我们就可以进一步扩大 gap ，也就是增大γ?的值了。这些点呢，就叫做support vector ，嗯，先说这么多了。
支持向量机: Support Vector
by pluskid, on 2010-09-10, in Machine Learning49 comments
本文是“支持向量机系列”的第二篇，参见本系列的其他文章。
上一次介绍支持向量机，结果说到 Maximum Margin Classifier ，到最后都没有说“支持向量”到底是什么东西。不妨回忆一下上次最后一张图：
可以看到两个支撑着中间的 gap 的超平面，它们到中间的 separating hyper plane 的距离相等（想想看：为什么一定是相等的？），即我们所能得到的最大的 geometrical margin γ?。而“支撑”这两个超平面的必定会有一些点，试
想，如果某超平面没有碰到任意一个点的话，那么我就可以进一步地扩充中间的 gap ，于是这个就不是最大的 margin 了。由于在n维向量空间里一个点实
际上是和以原点为起点，该点为终点的一个向量是等价的，所以这些“支撑”的点便叫做支持向量。
很显然，由于这些 supporting vector 刚好在边界上，所以它们是满
足y(w T x+b)=1（还记得我们把 functional margin 定为 1 了吗？），而对于
所有不是支持向量的点，也就是在“阵地后方”的点，则显然有y(w T x+b)>1。
事实上，当最优的超平面确定下来之后，这些后方的点就完全成了路人甲了，它们可以在自己的边界后方随便飘来飘去都不会对超平面产生任何影响。这样的特性在实际中有一个最直接的好处就在于存储和计算上的优越性，例如，如果使用 100 万个点求出一个最优的超平面，其中是 supporting vector 的有 100 个，那么我只需要记住这 100 个点的信息即可，对于后续分类也只需要利用这100 个点而不是全部 100 万个点来做计算。（当然，通常除了 K-Nearest Neighbor 之类的Memory-based Learning算法，通常算法也都不会直接把所有的点记忆下来，并全部用来做后续 inference 中的计算。不过，如果算法使用
了 Kernel 方法进行非线性化推广的话，就会遇到这个问题了。Kernel 方法在下一次会介绍。）
当然，除了从几何直观上之外，支持向量的概念也会从其优化过程的推导中得到。其实上一次还偷偷卖了另一个关子就是虽然给出了目标函数，却没有讲怎么来求解。现在就让我们来处理这个问题。回忆一下之前得到的目标函数：
这个问题等价于（为了方便求解，我在这里加上了平方，还有一个系数，显然这两个问题是等价的，因为我们关心的并不是最优情况下目标函数的具体数值）：
到这个形式以后，就可以很明显地看出来，它是一个凸优化问题，或者更具体地说，它是一个二次优化问题——目标函数是二次的，约束条件是线性的。这个问题可以用任何现成的QP (Quadratic Programming)的优化包进行求解。所
以，我们的问题到此为止就算全部解决了，于是我睡午觉去了~
啊？呃，有人说我偷懒不负责任了？好吧，嗯，其实呢，虽然这个问题确实是一个标准的 QP 问题，但是它也有它的特殊结构，通过Lagrange Duality变换到对偶变量 (dual variable) 的优化问题之后，可以找到一种更加有效的方法来进行求解——这也是 SVM 盛行的一大原因，通常情况下这种方法比直接使用通用的 QP 优化包进行优化要高效得多。此外，在推导过程中，许多有趣的特征也会被揭露出来，包括刚才提到的 supporting vector 的问题。
关于 Lagrange duality 我没有办法在这里细讲了，可以参考 Wikipedia 。简单地来说，通过给每一个约束条件加上一个 Lagrange multiplier，我们可以将它们融和到目标函数里去(参见高数中的带约束条件的求极值问题，使用拉格朗日数乘法)
然后我们令
容易验证，当某个约束条件不满足时，例如y i(w T x i+b)<1，那么我们显然
有θ(w)=∞（只要令αi=∞即可）。而当所有约束条件都满足时，则