支持向量机入门系列.doc

第一部分 ??引子 ? 1. 支持向量机的目的是什么？ 对于用于分类的支持向量机来说，给定一个包含正例和反例（正样本点和负样本点）的样本集合，支持向量机的目的是寻找一个超平面来对样本进行分割，把样本中的正例和反例用超平面分开，但是不是简单地分看，其原则是使正例和反例之间的间隔最大。 超平面是什么呢？简单地说，超平面就是平面中的直线在高维空间中的推广。那么，对于三维空间，超平面就是平面了。对于更高维的空间，我们只能用公式来表达，而缺少直观的图形了。总之，在n维空间中的超平面是n-1维的。 超平面的公式为。公式中的w为可以调整的系数向量，b为bias。注意我们的表达习惯，所有的向量都是列向量，所以在第一项的内积中向量w需要进行转置。 现在考虑样本集合{xi，di}，xi是输入的特征，di是样本对应的分类。现在规定当样本xi属于第一类时，di为1，当xi属于第二类时，di为-1。 那么，线性可分的意思就是一个超平面可以把两类样本完全地分割开来。用公式表达就是： 你现在可能会问，那么如果不是线性可分的情况应该怎么办呢？事实是这些会在后面处理到。在这里我们首先讨论线性可分的情况，然后将其拓展到线性不可分的情况. 现在假设对于线性可分的样本集，我们有了一个分割超平面INCLUDEPICTURE \d /attachment/201112/1/0_1322703652fUc4.gif \* MERGEFORMATINET ，现在我们想通过调整w0和b0让它分割的正样本和负样本保持最大的间隔，这样我们就获得了最优的超平面。实际上在操作过程中，我们最大化的是离超平面最近的点到超平面的距离。也就是说，我们要让超平面尽量远离最近的点。从图中可见超平面到正样本最近点的距离和超平面到负样本最近点的距离是相等的。这是个巧合么？ 假设我们已经找到了一个超平面，它离正样本最近点的距离大于离负样本最近点的距离，那么这个离超平面最近的点就是负样本中的最近点。而考虑到我们的目标，我们还会调整超平面的位置使它还可以增大一些，即使这样会牺牲离正样本最近点的距离。所以调整到最后的结果肯定是超平面离两侧最近点的距离是等距的。? 为了更形象地表现正负样本的间隔，我们可以在分割超平面的两侧再定义两个超平面H1和H2（如图中虚线所示），这两个超平面分别通过正样本和负样本中离分割超平面最近的样本点（图中加了外圈）。从以上分析可以知道，超平面H1和H2离分割超平面是等距的。 我们定义超平面H1和H2上面的点叫做支持向量。正负样本的间隔可以定义为超平面H1和H2之间的间隔，它是分割超平面距最近正样本点距离和最近负样本点距离之和。 从图中可以看出，支持向量对于分割超平面的位置是起到关键作用的。在优化分割超平面位置之后，支持向量也显露出来，而支持向量之后的样本点则对分类并不关键。为什么这样说呢？因为即使把支持向量以外的样本点全部删除，再找到最优的分割超平面，这个超平面的位置跟原先的分割超平面的位置也是一样的。总结起来就是： 支持向量包含着重构分割超平面所需要的全部信息！ ? ?2. 样本点到超平面距离的表示 如何求一点到超平面的距离呢？ 现在我们来看看系数向量w0是什么含义？回忆一下，w0实际上是超平面的法向量！ 那么，对于任意一个样本点x，它可以表示为： 其中xp是x在超平面上的投影，r是x到超平面的几何距离（几何间隔）。 设?， 现在由定义有g(xp)为0，则有。 现在我们开看，g(x)实际上度量了样本点x到超平面的距离，在||w0||恒定的情况下，g(x)绝对值的大小反映了几何间隔r的大小。我们给g(x)起个名字叫做函数间隔。注意几何间隔r和函数间隔g(x)都是有正负号的，代表着处于超平面的不同侧。 ? 3. 最大化间隔 我们已经知道了函数间隔和几何间隔的表示，现在回到正题，我们需要最大化支持向量到分割超平面的距离，当然在最开始我们不知道哪些向量是支持向量。 我们的目的是最大化支持向量到分割超平面的几何间隔r，而不是最大化函数间隔g(x)，为什么呢？因为超平面方程的系数可以同比例增大或者减小，而不改变超平面本身。所以||w0||是不固定的，这就会影响函数间隔g(x)的大小。 所以我们需要最大化的是几何间隔r，这等价于我们固定||w0||，然后最大化函数间隔g(x)。但是实际上我们不会这么做，通常的处理方法是固定函数间隔g(x)的绝对值为1，然后最小化||w0||。也就是说我们把支持向量到分割超平面的函数间隔g(x)的绝对值设定为1，然后最小化||w0||。 ? 4. 正式的表述 现在我们可以正式地表述这个问题了。我们需要最小化||w0||，也就是最小化超平面权重向量w0的欧几里得范数。但是有没有限定条件呢？还记得上一节最后一句话么？ “也就是说我们把支持向量到分割超