机器学习-SVM

1. 线性感知机分类

2. 支持向量机

线性感知机（Perceptron）

感知机是线性二值分类器。

注意：什么是线性？线性分割面就是，就是在分割面中，任意两个的连线也在分割面中，这个分割面，就是线性分割面。

f(x,w,b)=sign(wx+b)

wx+b>0, f=1

wx+b<0, f=-1

为什么分割面能写成 wx+b=0？w 一个向量。

对于普通的方程 y=kx+b,那么我们可以写成 kx-y+b=0,写成向量方程就是：

当k=1时，w(1,-1) 如下图知，w 是分割面的法向量。 

感知机--目标函数

最小化错误率：

I 函数是：当预测值 f() 与实际值 y 不相等时，I=1，相等是 I=0 。所以求和为错误的样本数。

我们可以转换成后边的函数，sign 函数是：wx+b>0 是 函数值为1，wx+b<=0 时函数值为-1.

那么如果分对：sign 与 y 符号相同，相减为 0，如果分错，sign 与 y 符号相反，那么相减为2 或者 -2 所以需要除以2，就是分错样本数了。

由于sign() 函数不是处处可导，给算法设计带来困难。所以我们换一个容易的策略。

                   函数 ①

这个函数只统计分错样本，所以如果全分对L=0，如果有分错样本时L>0  (<0,所以函数前边有个负号）

 结论：线性可分时，最小化 L 等价于最小化错误率。

注意：如果不是线性不可分时，这个结论不成立。

如：w1xi+b=0.2    分错

      w1xj+b=0.3    分错   L1=0.5

  

      w2xk+b=0.6     分错： L2=0.6

当为 w1 是有两个 样本点分错了错误率为2，L1=0.5 ，但是当为 w2 时 有一个样本点分错了错误率为1， L2=0.6>L1 

现在我们要 最小化 函数 ①，那么我对函数① 分别对w 和 b 求偏导。（-xiyi,-yi）

我们用梯度下降法来找函数① 的极值。

w = w + p*y_i*x_i

b = b + p*y_i

 是学习率。

算法步骤：

1. 随机设定：w ，b 的值

2. 用当前（w，b）轮流对所有的样本点分类，如果分错，更新(w,b) 的，继续。

3. 重复步骤2直到所有的点都被分对

感知机的不足：

1. 有无穷多个可行解

2. 由于感知机是贪婪算法，所以结果依赖初始值和误分点的顺序。

3. 线性限制（对于线性不可分的特征空间，线性感知机无能为力）

  

          不足 1                        不足 3

线性感知机有这些不足，接下来我们看看在支持向量中是怎么弥补的。

支持向量机（Support Vector Machine）

1. 线性可分：硬间隔SVM

2. 适用于线性不可分：软间隔SVM

3. SVM对偶问题和解的性质

4. 非线性：Kernel SVM

硬间隔 SVM

                                    

                    图 1                                                                                               图 2                                                                      图 3

看图1，这里有两个分割线，到底哪个好呢？对于新数据（哪个方框）到底应该属于哪一类呢？我看到超平面不同，对新数据的影响不同。

看图2，间隔：分界面到最近样本距离（的两倍）。

          我们认为使间隔最大的分界面是最好的分界面，因为间隔最大，将来落在间隔内的新数据更够跟准确的分到所属的类中。

          最大间隔分类器是使得间隔宽度最大的线性分类器。

看图3  要求：对正样本wx+b>=1

                    对负样本wx+b<=-1

原因：由于wx+b>0  那么肯定存在一个非常接近0的ε 使 wx+b>=ε ,两边同时除以 ε 得 wx/ε+b/ε>=1，那么我将w/ε=w,b/ε=b(先的未知数),于是就有wx+b>=1,同理wx+b<=-1

求间隔（margin）：

M 由向量投影公式：投影=向量与投影方向单位向量的内积。

（第二个式子是根据直角三角形计算出来的）                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         将conθ 带入二式就得到了M的值。

wx+b>=1 , y=1  

wx+b<=1 , y=-1 所以：y(wx+b)>=1 

我们要最大 ，就等价于最小化，因为：，而 是一个单调递增函数，最小化的也就是最小化 x ，同理最小化化，优化问题，前边加一个1/2 系数，对优化问题没有影响，添加一个1/2 系数是为了对二次求导有一个2系数相消。

     这样就转化为一个关于 w 和 b 的二次规划问题：

          

软间隔 SVM

     感知机是有无穷多个可行解，现在硬间隔SVM 通过最大间隔，有唯一解。那么目前还有什么缺点？对噪音的处理。现在都是要求线性可分，如果存在噪音，那么将会出现震荡。那么我们接下来，看看软间隔ＳＶＭ是怎么解决噪音问题的。

　如果存在噪音点。

     软间隔ＳＶＭ　通过引入松弛变量ξi，使得错分样本得到惩罚（注意：当还没有找到最优解时，一些非噪音点也会遭到惩罚）。

     最小化松弛项，同时最大化间隔。

     minimize 错分样本对应的 ξi>=1,所以：Σiξi>=错误样本个数。

硬间隔 VS 软间隔

　　

                         硬间隔ＳＶＭ                                                                                软间隔ＳＶＭ

拉格朗日函数

为什么要引入拉格朗日函数呢?对于一般函数我们要极值，我们只需求导等于零即可。那么对于带约束的函数求导，我们怎么求他的极值。我们用拉格朗日乘子，将目标函数和约束函数写到一个新函数中，对这个新函数我们求导等于零即可。

优化问题

 对每个约束引入拉格朗日乘子 ai,ui 得到：

 且 a>=0,u>=0

这个拉个朗函数，根据 α和u 求最大，然后根据：w，b， ξ 求最小。

那么经这转换，最后求出解还是原问题的解吗？

分析：内部最大化：当不成立，也就是小于 0 ，根据式子值，α的系数是正数 且 α>=0，那么这时根据 α 求拉格朗日函数的最大值为正无穷。

                              同理当不成立时， 且 u>=0 ，拉格朗日函数最大值为正无穷。

                              当成立时，，α的系数是负数，且α>=0 ,所以只有 α=0 时，拉个朗日函数的最大值为0.

                              当成立时， ，u 的系数是负数，且u>=0 ,所以只有 u=0 时，拉个朗日函数的最大值为0.

结论：     当 成立时，拉格朗日函数 根据 a,u求得最大值为0，则此在根据w，b,ξ 求最小值，就是原函数的最小值

               当 不成立时，，拉格朗日函数 根据 a,u求得最大值为正无穷，则此在根据w，b,ξ 求最小值，没有意义。

     

          图1                                        图2

原问题就像图1

朗格朗日函数就像图2

拉个朗日的对偶问题：

 且ai>=0,ui>=0

对偶函数只是将最大化和最小化交换了一下位置。那么优化对偶函数的解和拉格朗日函数的解是一致的吗？

凸优化是一样的。因为凸规划满足KKD条件。凸规划问题就是：约束是凸集，目标函数是凸函数。

求极值问题，L对 w,b,ξ 求导等于零。

式（1）得到：，带入L：

需满足式2,3和对偶条件：

1. ai>=0

2. ui>=0

3. C-ai-ui=0

4. Σyiai=0

使用ui=C-ai  消掉ui，得到最终的对偶问题：

由于， 预测函数变为：

求b：满足 0<ai<C 的i 对应的支持向量，解yif(xi)=1得到b

对偶问题有点，只需内积，不需 x 具体值。这样也就可以用核函数了。

KKT 条件

最优化问题，最后变成求KKT条件。只要满足KKT 条件的解，就是原问题的最优解。

非线性SVM

对于线性可分数据，线性SVM表现很好了。

如果训练数据本身存在复杂非线性关系（在给定的特征空间中），很难用线性模型较好的处理。

解决办法：通过一个函数，将原来的特征空间中的样本，映射到高维的特征空间中:

 将原来的数据的平方作为第二维。

原始空间中任意形状的两个区域，总是可以在某些高维特征空间中映射成线性可分的区域。

将到原点的距离最为第四维的数据。

核函数：

之前我们讲过，SVM分类器的训练和预测都仅依赖于样本对的内积值 K（xi,xj）=xi^Txj

核函数对应某个特征空间中的内积。

核函数例子：

1. 线性：（这就是内积定义，就是映射的还是原来的空间）

2. p次多项式：

3. 高斯核（RBF核）（特征空间是无限维空间，此核可以用来逼近任意复杂的分类面）（σ 参数需要自己调）

4. Sigmoir：

注意：引入Kernel 的同时带来高计算复杂度：

1. Kernel SVM 中，支持向量个数随样本数增多。

2. Kernel SVM 问题求解至少是n^2 复杂度。（因为我们需要计算每个特性向量与其他特征向量的内积）

最著名的两个工具包

LIBSVM:

     http://www.csie.ntu.edu.tw/~cjlin/libsvm/

SVM Light:

     http://www.cs.cornell.edu/People/tj/svm_light/

liblinear-1.93：这个是针对线性可分的数据，做了很多优化，比libsvm-3.17　快很多。