机器学习技法-SVM笔记

      这个课程将围绕特征转换的问题在3个方向上进行探讨：

1、若我们有很多特征转换，如何运用这些特征、以及如何控制复杂度的问题产生了SVM（Support Vector Machine）的想法

2、为了找出具有预测性质的特征，并将其混合，使模型有更好的表现而出现逐步增强法Adaptive Boosting

3、找出或者用机器学出隐藏的特征，Deep Learning

 

Linear Support Vector Machine

在PLA算法中，我们的目标是找出可以将数据正确分类的线或者超平面，想了解的更具体一点，可以参考点击打开链接

                       

       PLA的特点是，其最后结果依赖于使用过的数据，产生的结果是哪条线并不一定。不同于PLA算法，SVM的目标是不仅要找到可以将已知数据正确分类的线或者超平面，而且对未来将要预测的未知数据有很好的抗噪能力，简单理解就要说对预测数据的预测性能要好

                            

       那么什么样的分类线或者超平面对预测数据的分类比较准确呢？若让我们根据直觉从上图中选择的话，必然会选择上图的第三种情况。这是有理论依据的，根据点到直线的距离来说，第三种情况下两类点到分类线的最小距离的间隔最大，这样对待测数据预测的确信度就会越大。所以SVM目标概括如下：

1、 找到能够正确区分所有数据点的分割面；

2、 找到所有数据点到分割面距离的最小值，并将其最大化这样这个面的确信度或者抗噪能力强。

                        

     我们可以设超平面方程为 ，其中w为n维向量，x为数据，b为常数。接下来我们求任意点到w和b确定的平面的距离。若一个x‘点在 确定的平面上，则其必然满足 。若x',x''都在平面上，则 。由于 ，所以等式 成立。x',x''都是平面上的点，这两个向量的连线确定了这个平面，而 说明 与平面垂直。根据几何知识，平面外一点到平面的距离就是这个点与平面上一点间的连线在平面法向量上的投影，即任意一个x到平面的距离为x-x’在 上的投影就是x到平面的距离。

根据线性代数里向量到另外一个方向的投影公式：

                   

                

将上式括号展开并利用分割线两侧的点满足

 

得到如下结果

所以我们可以得出

        

由于对w和b同时放缩并不会影响等式，即 。同样，我们可以对w和b进行放缩，使1 ，则可以得出如下结果，

                  

所以，可将原始问题简化为

                           

由于 ，所以every 必然成立，划掉多余条件 得

将 条件放宽为 后，若所有点的解满足w=1.126，b=1.126，由于将w和b同时缩小1.126倍，等式不变，所以最优解w=b=1.126不是最优解，与前面w=b=1.126为最优解矛盾。

      

由上述内容可知，将条件放松，对结果没有影响，所以将最大化问题化为最小化问题，并去掉根号得

                    

上式称为标准问题。

      那么我们如何解上述标准问题呢？之前我们了解到的梯度下降法针对无约束问题是较好的算法，但对于有约束的问题，并不好解。根据最小化问题理论，标准问题在最小化问题中，是一个凸二次规划问题，我们可以理解为它是线性规划的升级版。

解关于u向量的凸二次规划问题时，我们将Q，p，A，c 4个系数放到解二次规划的工具中即可求得结果。那么该如何将标准问题和二次规划中的系数相对应呢？

   

从上面的对应关系，我们可以得出：二次式的系数放到Q矩阵里，一次项系数放到p向量里，有m个约束条件，每个条件对应的一次式的系数 放到矩阵A里，常数 放到c向量里，得标准问题的二次规划系数为

上述问题我们称为Linear SVM。若想进行非线性划分，则需将x转换到更高维的z空间

                                              

即在原始的x空间SVM不是线性可分的，但转换到高维的z空间可能成为线性可分的。

对SVM的理解：

1、 SVM与回归对比

                

2、 VC dimension越小，复杂度越低；VC dimension：与数据有关；VC：与数据无关，看hypothesis（具体含义请自行百度，或参照机器学习基石课程相关内容）。

简单来说，满足如下关系：

                

其中，$\rho$ 为分割线（面）宽窄，越窄复杂度越低。

将上述内容总结如下：

            

      一开始介绍了本课程内容，接下来提出我们想要使这个分类器的抗噪能力较强。将问题正式化后开始通过距离以及其他方法去简化条件，使问题变为标准问题（即使w较小）接着将问题送到QP工具去解这个问题。

接下来，我们来学习非线性SVM。

 

DualSupport Vector Machine

    上一节中，我们提到对于x空间中非线性SVM，我们通过特征转换 将其转到z空间进行SVM最优化问题求解。

非线性SVM可以在以下情况给出SVM的解，

     

但当有无限维时，我们不可能去解一个无限维的二次规划问题。因此，怎样能不依赖于维度d。

       为了达到这个目的，我们将原始有d+1个变量，N个约束条件的SVM问题等价为N个变量，N+1个约束条件的SVM问题，这个对等形式称为原始SVM的对偶问题。

       在引入对偶问题时，我们用到了一个关键的工具：拉格朗日乘子。这个工具我们之前在回归问题中也同样使用过。

       通过在原始问题每个条件前乘以拉格朗日乘子，然后将其加到最小化问题里。在回归问题里，$ \lambda$已知，但在dual SVM中，$\lambda$ 是未知的。每个条件对应一个 $\lambda$，我们将其当成一个变量，去解和这个变量有关的最小化问题。SVM有N个条件，所以对应有N个 $\lambda$乘子。在对偶问题中，我们使用$\alpha$ 来表示拉格朗日乘子。所以SVM问题可以表示为如下形式，

此时，SVM的目的就是使如下

            

每个b和w，都对其算出一个值，b和w固定，调节 ，使拉格朗日函数最大，其中 ；此时，b和w是其代表值下次b和w来时，对其进行同样的操作，最后，从所有b和w中选最小的一个。

理解：

无效的b和w：由于 为正数，则可选择 其最大为无穷；有效的b和w：由于 为非正数，乘以非负数 ，为了使其最大， 应该为0

                          

因为对任意固定 $\alpha$来说，对 进行最大化操作，则它必然会比固定的大，故上式成立。对于任意固定 来说，上式成立，所以对右边取 最大值，上式依然成立，即：

               

结果即为SVM对偶问题

上式在最小化问题里称为弱对偶（weak duality。将大于等于改为等于，则称为强对偶（strong duality）。等于号成立的条件：原始问题为凸二次规划；原始问题有解（即原始数据线性可分）；满足线性条件。

所以解原来左侧的SVM问题等价于解右侧对偶问题。其中右侧比左侧简单就在于解ｂ和ｗ的有约束问题化为无约束问题，此时可以使用梯度下降法进行计算

根据高等数学知识，min最小值时：L对ｂ和ｗ微分结果为０。所以将L对ｂ的微分结果加到对偶问题里，也不会影响对偶问题的解，因为与 有关，所以将其加到与 有关的约束里，即

                

            

ｂ的系数为 ，所以对偶问题简化为下式

                       

接下来对每个 求偏微分得并以向量的形式表示上式为

                

将 约束条件代入且由于 由此可将ｗ和ｂ化简，min即可消失

３个约束条件分别来自于：对偶问题对 的约束；最小化ｂ对 的约束；最小化ｗ对 的约束。

若上述 、ｂ和ｗ满足原始问题和对偶问题的最优解的话，则其满足以下条件：

这称为KKT条件。所以标准SVM 对偶问题表示为

上式中 和ｗ关系隐藏了，为了专注于解 。即可以将原来的问题化为N个变量和N＋１个条件的二次规划问题。其对应系数如下：

               

在使用QP工具解对偶SVM问题时系数矩阵Q常常不为0，若其有N=3000个数据，则计算时需要大于3GRAM。

因此，一般使用专为SVM设计的QP工具解上述问题。若考虑其特殊性质，我们还可以加快其解的速度。根据前面的公式，很容易算ｗ。选择一个 大于０的，则求得 。所有 对于的ｂ应该相等（可以有一定的差，但很小）。此外， 大于０对应的点对应的点就是边界上的点。

           

       因此，仅 大于０的那些点是支撑向量。之前认为在边界上的为支撑向量，解对偶问题得出的结果说明仅 大于０对应的那些点才是支撑向量。由此我们可以发现支撑向量很重要，在计算ｗ时，仅需考虑 大于０的那些项；ｂ也可以只靠支撑向量计算得出。

        

                           

       仔细观察，我们会发现SVM和PLA具有一定相似性：在SVM中，ｗ为阿尔法和 的线性组合；在PAL中，ｗ为错误分类点的线性组合；SVM通过对偶问题求解间隔最大的超平面，但PAL则通过错误数据点找出正确将数据区分的超平面。

               

总结：

                     

       原始SVM变量的数量和所在空间有关，若比较小的话可以在原始空间解，若很大的话，在原始空间求解会很费时；对偶问题与所在空间无关（看起来是这样），仅与数据量有关。数据量小的话，可以解对偶问题求解SVM，若数据量大的话，求解也比较慢；

原始问题物理意义：求解ｂ和ｗ，对ｂ和ｗ进行放缩可得到最小化问题

对偶问题物理意义：找到支撑向量，通过支撑向量求得 ，从而求得ｂ和ｗ，建立分割边界。这两种解法都可以得到最佳的ｂ和ｗ。

       对偶问题的提出是为了避免和原始空间维数有关联，虽然从形式上对偶SVM确实与空间维度无关，但对偶 SVM并没有真正不依赖于原始空间维数，仔细思考，我们会发现其系数Q矩阵的每一项 的计算与空间维数有关。

           

       下面，我们来总结一下本节讲的内容：

       首先为了不依赖于空间的维度，我们提出对偶SVM；然后我们给出对偶SVM的拉格朗日乘子和其与原始SVM联系的KKT条件；最后我们给出求解对偶SVM的思路以及从对偶SVM我们发现分割面仅与支持向量有关。

 

KernelSVM

    那么如何使对偶SVM彻底不依赖于空间维度呢？在对偶问题中，我们将x空间转换到z空间，然后将转换后的每一项相乘。

           

但若能将转换和内积这两个步骤一次完成，则可以大大加快速度。

       以二阶多项式为例。二次转换如下，其中有一次项系数，二次项系数，其中也包含了0次项。因为 ，所以我们可将其合在一起。

      

将 以求和号表示为下式

                 

因此，我们将原来先转换后求内积的方式在x空间中一次进行，使原来O(d^2) 的复杂度降为 O(d)，d为x的空间维度。我们将转换和求内积的操作合称为Kernel function（核函数）。

以上，我们强调:在x直接进行转换,无需经过z空间,减少运算复杂度

因此，我们在对偶SVM中，求二次项系数可以通过核函数来求。那么求得系数 后，我们用已经求得的系数来求解b。由之前的知识，我们在求b时可以使用一个支持向量即可，因此选一个支持向量，通过下式求b

求得 ,用来对未来数据进行预测

很明显，核函数:引入有效的核函数,避免依赖于维度。此时，对偶SVM变为Kernel SVM。此时，SVM求解过程如下：

并且，在对未来数据预测时，仅需计算核函数即可，无需进行其他运算。

那么引入核函数，究竟会带来多大的复杂度优势呢？首先，我们在计算Q时需要O(N^2)O(k)，其中K为计算核函数需要的时间；接下来就是计算有N个变量N+1个条件的QP问题，与空间维度没有任何关系；计算第三步和第四步仅与支持向量个数和核函数的估计有关，与空间维度无关。

    

其他常用二次多项式介绍

由上式知，我们可以通过在前面使用的二次项多项式系数前进行不同的放缩得到其他的多项式。

                           

 

那么不同系数的二次项多项式有什么区别呢？

由上图我们可以看出，不同的系数确定了不同的SVM边界，其支持向量和复杂度也不尽相同。由此得出，蓝色和绿色核函数区别:在作用上是相等的,但对应的几何距离不一样,即最后SVM确信度不一样.无法说哪种核函数最好,不同的核函数确定不同的支撑向量,产生不同的超平面。

    之前，我们需要对转换的函数做选择，现在由于转换已经包含在核函数里，因此我们需要对核函数做选择。

                 

根据上述思路，我们可以对常数进行改动,增加参数.对系数进行调整,可得到多个多项式. 代表放缩系数,必须大于0,ζ大于等于0,Q为几次方的转换。此时计算量为原来空间的内积加多项式的计算。

       由于核函数的引入，10次转换复杂度和二次也差不多,只要把核函数计算出来即可。但若进行太高次的转换，会不会产生过拟合问题呢？由于largemargin控制, 可以减小过拟合的可能（但并不是完全避免）。

                 

       虽然多次转换和一次转换复杂度差别不是很大，但为了避免过拟合，如果不需要多次转换,则选择Q为1即可。

      一般来说,对数据先进行线性SVM,如果效果不好,再进行非线性SVM。线性SVM我们可以在原始空间进行求解，则无需转换到对偶空间，若线性SVM无法给出很好的分类效果，再考虑到对偶SVM进行求解。

计算无限维转换的核函数:

      上面我们使用Kernel进行与空间维度无关的SVM的求解，那么如果是无限维呢？我们是否也可以找到其对应的Kernel来求解其SVM的分割面。

从上式我们可以看出，将 括号展开，并用泰勒展开式对得到的2xx’项进行展开得然后用求和号进行合并，我们可以发现 这就是x到无限维空间的映射。更一般的

                           

其中γ为可调节的参数。

此时 为中心在支撑向量上的高斯函数的线性组合。对应于将原来的x映射到无限维的空间，在那个空间找到最大边界，在测试时可以做好多分类。结果其实就是一堆中心在支撑向量上的高斯函数的线性组合,因此常被称为RBF（Radial BasisFunction） Kernel。

                              

将Gaussian Kernel放入后，其找出组合系数 以及需要使用的Gaussian在

       顺序:hyperplanes->hyper planes + transforms ->hyper planes +transformwith kernel trick。但是如果只做这样的转换无法控制复杂度。因此Large margin 可以控制复杂度

        

      所以我们的求解思路改变:不再计算转换后的z，通过核函数将转换存在核函数中;不在执着于存储z空间中的w,而是存和w有关的支撑向量和系数。

从上图中看出：γ越大,核函数越复杂，γ越大表示高斯函数越尖，很有可能过拟合，因此要慎重选择γ。

 

Kernel分析:

Linear kernel:

优点：最简单，最安全，应该优先尝试；可以使用特别的QP solver来解原始最优化问题；可以很任意看出machine如何做分类，w可以告诉你每个特征的权重;可以发现哪些向量是重要的(即支撑向量)。

缺点：对线性不可分数据无法正确进行分类。

Polynomial Kernel：

    优点：比linear限制要宽松；Q可控制限制模型复杂度。

    缺点：电脑上来说,由于浮点数运算不是很好算，此外由于参数较多，选择合适的参数比较

困难，一个个去试会花很多时间，通常用于Q较小时

                                 

Gaussian kernel:

    优点:比线性和Polynomial更强大，可以产生很复杂的边界;比Polynomial数值上计算的困难度要低;要选择的参数只有伽马一个,比Polynomial参数选择要容易。

    缺点:比较难解释明白；计算比较慢(相对于linear 来说);太复杂容易过拟合。

其他核函数:

Kernel代表x和x’ 相似性,转换后在z空间相似性.内积本来就是代表相似性;

直接从相似性出发，定义kernel。则需证明这个是核函数：满足对称性;证明其是半正定矩阵(是必要条件也是充分条件)，这个有可能,但很困难。

接下来，我们对本节内容进行总结。

      首先，我们讲了Kernel Trick 作为转换和内积的计算捷径，可以加快求解速度。然后讲了多项式核函数和包含无限维转换的高斯核函数，最后对几种核函数进行了对比。

 

 

                     

      前面的hard margin　SVM就是说不能有任何数据点被误分类；今天我们要讲的就是soft margin，即允许有部分数据点违反边界。上节讲的Gaussian核函数有点太复杂，虽然有hard　margin控制复杂度，但还是容易过拟合。过拟合有两个原因，一个是核函数太复杂，另外一个就是坚持要把数据点都完全分开。因此想到了soft margin 来减少过拟合。

此前我们碰到过拟合是怎么解决的：学到的第一个模型是Pocket。

                        

                        

Pocket：无法找到一条线将数据完全分开，那就找一条犯错误最少的线将数据分开。而原来的SVM坚持要将数据完全分开，因此我们考虑将原来SVM条件放宽，可以容忍一些错误。

　　　　　　　

这个表达的意思就是对于正确分类的点，要满足原来的约束条件，对于误分类的点，要使其数量越少越好，C是调整参数，来控制相对重要性。

 

　　　　　

　　由于要判断是否正确分类，上述内容已经不是一个线性问题，因此也无法使用之前我们学习的内容来求解，且上述问题无法区分误分类的数据点离超平面的远近。因此，我们将误分类的错误记录到 里，即可得出下式

              

其中 表示这个点离 的大小。此时，我们将原来记录的错误的个数变为记录错误的大小，因此还是ｗ和 的二次式，即QP问题。

即我们以 表示数据点离我们想要的边界的距离，C为调节参数。C越大，表示我们想要误分类点的个数少；C越小，表示我们想要使边界大一点。此时这个问题为ｄ＋１＋N个变量，２Ｎ个约束条件的二次规划问题。上述问题称为软间隔支持向量机的原始问题。

　　　　　

按照之前的原始问题到对偶问题的思路，我们可以在红色约束条件前乘以拉格朗日乘子 ，在蓝色约束条件前乘以拉格朗日乘子β，即可得出下式

　　　　　　　　　

拉格朗日对偶问题则为

　　　　　              　　　

然后用KKT条件来简化这个问题。

对 求偏微分得

，将其写为 ，为了满足原来对β＝０的条件，则使　 。将β代入使上式化为

　　　　　　　　　

上式里面和之前的对偶SVM相同，只是在括号外边多了些约束条件。所以按照之前的思路，对ｂ和ｗ微分得

　　　　　      　　　　　　　 　　

最后我们求得的结果为

　　　　　　　　　　　

它与硬间隔唯一的区别就是 有上界C。所以这个二次规划问题有N个变量，２N＋１个约束条件。所以新的对偶SVM问题的QP解法如下：

           　　　　　

在之前，我们解ｂ时是由于 和 不能同时不为０，所以任选一个支持向量，其所对应的 大于０，因此可以求得ｂ。但在软间隔里，由于 与ｂ有关，即 无法求解。若我们将 消去。则可对ｂ进行求解。若我们使 ，则可以很容易的求得ｂ。由于 时， 。因此，我们选择 的支持向量即可求得ｂ，此时的支持向量我们称为自由支持向量。

                     

即使是软间隔，若参数选择不当，也会发生过拟合，例如下图分别为高斯核函数的系数为

１，１０，１００的情况。

　　　　　　　　　

接下来我们分析 的含义

　　　　　　　　　　

自由支持向量：由于前面的一项 不为０，则后面的一项为 ；由上式知，自由支持向量即为刚好在边界上的点。

非支持向量：此时 ＝０，所以 ，即这些点是没有违反边界的点，这些点大部分会在边界外，有极少数会落在边界上。

违反边界的点： ，则 ，由于 记录的是违反边界的大小，所以这些点或多或少违反了边界。

 

Kernel选择：

　　　　

　　上面左侧这张图所使用的Kernel都是高斯核，横向是各种不同的C，纵向是不同的γ若选择的核是Polynomial，则需要选择的参数更多。我们之前在机器学习基石里学过的最好的工具是Cross　Validation，哪一个Cross　Validation小，我们就选哪一个。上面右侧图所示的Cross　Validation分别对应左侧的高斯核。

　　Cross Validation到极限的话，就是每一份资料切成一份，每次选一份做Cross Validation，其他做训练这称为Leave－One－Out　CV　Error　for　SVM。这个方法在SVM上有个很有趣的结果。这个方法的Error和SVM的支持向量是有关系的，即 。

　                          　　　　　　　　　

证明过程如下：假设有10000个点，第10000个点的 =0（即它不是支持向量），若将最后一组数据去掉，则前面的9999组数据一定还是最佳解，若这９９９９个点不是最佳解，则应该还有一组更好的，把第１００００个点加回来又有一组更好的，这就矛盾了。则此时

这９９９９个点对应的解就是最佳解。这其实对应了之前在hard margin 里所说的，去掉不是支持向量的点对边界没有影响。所以，也可以通过支持向量来选择模型

                                       　　　　　　　　　　　　　　

真正算Cross Validation比较花时间的时候，选择这种方法控制模型复杂度比较简单。给出一个警告就是我们只能从支持向量估计一个上限，不能给出最佳答案。所以支持向量通常用来排除一些比较不太好的模型，

　　　　                             　　　　　　　　　　　

总结如下：

　　　　　　　　  

　　出发点是不要坚持将所有点都正确分开，所以加上了违反程度的大小，将其作为惩罚项。推导时发现它也是个QP问题，所以推导其对偶问题，发现它其实和硬间隔SVM一样，只不过其 上界是C。通过SVM我们可以把点分为3类：不在边界上的非支持向量；在边界上的支持向量；违反边界的点。可以通过Cross Validation和支持向量来选择模型。