SVM支持向量机（一）基本概念和目标

一、从线性分类说起

    svm是用来分类的，从最基础的二分类开始，当然有了2分类就可以拓展成多分类。从几何意义上来看，非常只管。从最简单的二维的情况看起，假设有一群人，我们知道每个人的身高和体重，如何对这群人进行分类？先把身高和体重作成二维坐标系，然后把人都画上去。看起来“粗胖”的人用实心点表示，看起来“细瘦”的人用空心点来表示，那么得到下面的左图
我们在中间可以画一条线，就将细瘦的人和粗胖的人分开了。因为这是2维的坐标系，我们可以把这条直线设为

wx+b=0

其中w是向量，x也是向量。这是二维的，展开来说就是w1*x1 + w2*x2 + b = 0 . 实际上w 就是这条直线的法向量，如果把w作为向量画出来，是垂直与这条直线的。这个用我们初中学的数学知识就知道了。x是身高和体重，一个人可以用向量(x1,x2)来表示。用一根直线将两个类别区分开来，就是线性分类。如果是3维空间，那么就不是直线，而是一个平面。4维以上，我们就很难想像了，可以统称为超平面。
    但是，看右图，这样的直线、或者平面可能有无数个，哪一个最好呢？一个直线或者超平面，将两个类的间隔分的最大，这个平面就是我们要求的解。

    看图5-22, B1和B2都可以把两个类的点分开，但是将B1，B2往两边平移，直到他们接触到两个类最边缘的点，可以看到B1所制造的间隔比B2制造的间隔大，这时我们认为B1比B2好。为什么呢？如果间隔越大，判错的概率就越小，置信度最小的点置信度最大。支持向量机就是要依照最大间隔的原则，找到一个超平面将两个类分开。

    假设B1就是我们找出来的超平面，b11和b12是B1平移后刚好碰到两个类最边缘的点的时候的超平面。在b11和b12上面的那两个点就叫做支持向量。

    究竟怎么算出来这个超平面呢？看下图

    假设，我们要求的这个超平面就是 wx+b = 0，那么这个超平面网上下移动碰到支持向量之后，得到的两个支持平面应该是wx+b = 1和wx+b = -1 。有人看到这里会非常不解，这他吗不是瞎说吗？我开始也这样想，并且想过各种推导，始终无法得到wx+b = 1和wx+b = -1这两个平面，尤其让我不解的是，为什么截距差偏偏是1和-1？ 这里应该是任意的值才对。我甚至想出了反例： 极端情况下，我画三条水平线y=2,y=6,刚好这两条线上有支持向量，那么要求的wx+b=0 实际上是y=4, 往上往下都不是1 。 用上面的写法就是 (0,1)*(x,y) -4 = 0 ，而上下两个平面分别是 (0,1)*(x,y) -2 =0, (0,1)*(x,y) -6 = 0 。想必大家看到这里就明白了，因为一个平面是一个等式，而等式的右边是0 ，这意味着我们把等式两边同时扩大或者缩小是不会改变这个平面的， 上面的这个极端情况也可以写成 (0,2)*(x,y) -2 = 0 ，(0,2)*(x,y) -2 = -1, (0,2)*(x,y) -2 = 1 。也就是说，上图确实是一个普遍的情况，只不过我们求出的系数向量w是扩大若干倍数后的w，而不是我们约简后的最简值。这样的写法会在后面我们求解时减少一个未知数，极大的简化求解过程，而且并不会对结果有任何影响。这里是可以证明的，过程就省略了。

   接着我们继续看支持向量机到底要做什么。我们假设了要求的超平面是wx+b = 0，我们也知道了，支撑平面wx+b =1和wx+b = -1，现在我们就可以求这两个支撑平面见的距离了，我们之前提到，两个支撑平面间的距离越大越好。这个距离怎么求呢？看上面的图，d就是两个平面间的距离，x1这个点在上面的平面上，所以有w*x1+b=1 （?），同理w*x2+b=-1（?），我们可以得到x1-x2这个向量，记住，w是这wx+b=0这个平面的法向量，而这三个平面是平行的，我们其实求x1-x2这个向量在w方向上的投影的长度，就是d。也就是w*(x1-x2)/||w|| ,x1-x2由方程??可以求出，就是2/w，带回到d = w*(x1-x2)/||w||，得到d=2/||w||。 也就是两个平面间的距离是2/||w||。 ||w||这个是什么呢？其实就代表向量的长度，||x||是范数的写法，我们这里说的是2范数，假如w=(w1, w2, w3……wn)，那么
||w|| = （│_w1│²+│w₂│²+…+│x_n│²）^1/2  

其实就是先求平方和，再开方。如果还不理解，可以想一想，三维坐标系里一个点，你怎么求这个点到原点的距离，是不是就是做两次勾股定理，其实就是二范数，这里这个记号只是用来表示向量的长度而已。

    现在，我们设了未知数w和b，记住w是一个向量，根据这两个未知数，求出了平面间的距离d，先在我们要取合适的w和b从而使d最大。这个过程并不是没有任何条件的。既然是分类，当然要求，这个平面的一边全是一个类，另一边全是另一个类。怎么从数学角度来表达一下呢

    在上图左边的条件下，求合适的w和b，使右边的式子最大。解释一下左边的条件的意思。 首先，我们设分类为1和-1，可以对应上面的“矮胖”和“高瘦”，x1,x2,x3……xi，这些都是一个个样本，对应上面一个人。我们要取w和b，使每一个人都满足左边的条件，所以有i个人的话，左边其实就有i个条件。一个人（xi）如果这个人是“矮胖”（对应yi=1）那么这个人的身高和体重放到w*(身高，体重）+b 应该大于等于1。反过来是“高瘦”就要小于-1.  为什么是大于1或者小于-1呢？支持向量是最边上的点，同时位于支撑平面上，把支持向量带入左边的式子都是等于1的。当这个点再往原理支撑平面的方向移动一点，就会大于1或者小于-1 。我们其实可以算点到平面的距离来观察到这个。但是上面的表达式，还存在一些问题，首先，限制条件为两个，不好写代码，其次，范数是要开方的，计算起来比较复杂。所以我们把条件合并成一个，范数一定大于0，我们要求2/||w||的最大值，实际上是求||w||的最小值，实际上等同于求||w||^2的最小值，这样就不用开方了，精简之后变成下面的式子

    注意这个式子有N个限制条件。 推导到这个地方，SVM彻底变成了一个数学问题，我们之后要想办法写代码，求出最佳的w和b。而上面这种形式，被称之为凸优化问题，是一个经典的问题，已经有很多解决方法。在后面的博客里，将会慢慢解决这个问题。

    当求出了w和b，我们只需要把新的要分类的点，带入到超平面的表达式中，计算大于1还是小于-1，就可以知道是属于哪一个类。

二、线性不可分

    上面的举的例子中，都是比较理想的情况，我们只需要一条直线或者一个平面就可以把两个类别完全分开。现实情况下，很难做到这一点，偏偏就有一些异常点，让我们不能一个平面就把所有东西分开，这中情况叫做线性不可分。如下图

    这样子一条直线没有办法将两个类完全分开，这时候，是不是支持向量机就没有办法处理呢？其实我们引入惩罚函数，如果有点分错了地方，就把两个平面的距离上减去一点。这样，还是能够使用SVM来进行分类，但是这样也会多一些未知数和约束条件。不过引入惩罚函数后，求解的过程还是一样的，并不会对我们的计算产生影响。这个在后面的博客里会在做笔记。

三、非线性分类

    解决了线性不可分难道就能解决所有的分类问题，这里还有更复杂的情况，

虽然我们用肉眼，一眼就看出来可以分类，但是这个用线性的分类器是没法分出来的，我们要画一个圆而不是一条直线。此时，我们可以增加维度，把这种线性不可分的情况映射到更高的维度，然后会惊奇的发现，映射过后是可以线性分类的。例如，现在只有x,y两个维度，图中两个圈分别是x^2+y^2=5,x^2+y^2=10 。 我们把x^2 ，y^2 ,和x 看成3个变量，然后再在三维的坐标系里看，会发现，两个圈之间会隔开，此时就可以找到一个平面来将他们分开，支持向量机依然可用。但是我们如何把变量映射到更高维呢，维度增高之后，计算太过于复杂怎么办，在后面的博客里将会做核函数的笔记，利用核函数，可以避免这些问题，使得SVM更加强大。