分类：支持向量机（二）——数值优化

       在上一篇博客中，较为详细的介绍了在数据完全线性可分的情况下，构建SVM模型的目标，并将构建目标转化为最大化几何距离的优化过程，本篇就将介绍具体优化时的计算过程。还是一样的，先推荐几篇不错的博文，大家也可以参考链接中的文章学习。

• 关于凸优化问题

        http://www.360doc.com/content/18/0522/09/32196507_756021531.shtml

• 关于拉格朗日乘子法及对偶优化问题

          https://www.cnblogs.com/xinchen1111/p/8804858.html

          https://www.cnblogs.com/ooon/p/5721119.html

          https://www.cnblogs.com/mashiqi/p/3719101.html

1.凸优化问题

       在一般的优化问题中求最大值或最小值，通常的做法是找出那些梯度为0的点（有的情况下还需要求出边界点的值），然后比较这些点的函数值，最后找出最大值或最小值。这个过程中有两个问题需要注意，一个是当存在多个极值点时，计算量会比较大；另外一个问题就是鞍点（比较常见的是函数在处）的问题。所以，如果优化问题能够在附加一些限制条件时能到简化，那将非常利于最大值或最小值的求解，凸优化问题正是这样一种简化后的优化问题。

       1.1  凸集

       对于  维空间中点的集合，如果对集合中任意两个点、，以及实数，，都有

                                                                         

则集合称为凸集，在二维空间中，可以用一张简单的图来描述一下凸集和非凸集的区别

                                             

 

       在一些特定的情况下，我们来考虑一下凸集 

• 在 维实向量空间中，、，对任意实数，，显然有

                                                                    

        这一结论表明，如果一个优化问题不带约束，那么该优化问题的变量可行域是凸集。

• 在 维实仿射子空间

                                                                                     

       中，假设 、，对任意实数，，有

                                                           

       即，这一结论表明：若优化问题中的约束是一组等式约束，那么它们确定的可行域是凸集。

• 在 维实向量空间中，多面体空间定义为

                                                                             

        在多面体空间中，假设 、，对任意实数，，有

                                                             

        即，这一结论表明：若优化问题中的约束是一组线性不等式约束，那么它们确定的可行域是凸集。

   最后，还有一个重要的结论是，多个凸集的交集仍然是凸集。​​​​​​                            

       1.2  凸函数

       对于函数，如果其定义域内的任意两个点 、满足

                                                           

       则函数成为凸函数，在二维空间中我们映像最深的凸函数就是下面这种情况了   

                                                                      

      在多维空间中，如何判断一个函数是否为凸函数，需要依据其Hessian矩阵判断。

      在一个优化问题中，若目标函数是凸函数，变量可行域是凸集，那么该优化问题就称为凸优化问题。通过以上对凸集及凸函数的定义，我们可以将单变量的凸优化问题用以下表达式描述，多变量的凸优化问题也类似

                                                     目标：

                                                     约束：

                                                                

    在凸优化问题中，局部最优值即是全局最优值。

2.拉格朗日乘子法

       拉格朗日乘子法用于求解带约束的优化问题，我们先从带等式约束的情况着手，一步步分析到带不等式约束的情况。

       2.1  等式约束    

       现假设有函数，带约束的优化目标为

                                                                                    

                                                                                            

函数、投影在平面上的等值线、如下图所示

                                                     

 

 图中带箭头的线条表示曲线在该点处的梯度方向。从上图中可以看到，只有约束曲线与等值线相切的地方，目标函数才有局部极值，因为在曲线与等值线不相切处(即交点处)，变量沿曲线移动时会增大或者减小，无法得到局部极值。因此，在计算最小值时，首先应该计算出所有满足约束的极值点，然后在这些极值点中找出最小值。

        现在观察一下等值线与曲线相切时的特征，在二维空间中，梯度与切线方向垂直（在多维空间中，梯度与切点处切超平面垂直），也就是说、在切点处的梯度共线(这里不能说反向，尽管上图中显示的是反向)，因此在切点处有

                                                                                                                (1)

为梯度，为任意实数，依据梯度的计算方式，式(1)等价于

                                                                                                                   (2)

                                                                                                                   (3)

为偏导数计算符号，这样在求解极值点时，联立式(2)、式(3)和计算即可。为了方便，构造函数

                                                                   

                                                                                 

求极值时直接求对、、的偏导数，并令其为0即可，结果和上面过程一样，这种方法就是等式约束下的拉格朗日乘子法。

        在多个等式约束情况下，也是一样的做法，构造函数，然后求解对、、 的偏导数并令其为0

                                                           

                                                                         

        2.2 不等式约束

        针对2.1节中的优化问题，现增加一个不等式约束                                                  

                                                                                 

                                                                                     

                                                                                           

        在带不等式约束的优化问题中，我们还是要采用先找出局部极值，然后通过比较极值的方式找出最小值，如果局部极值存在，那么只可能有两种情况，一种情况是局部极值点在的边界上，另外一种是时局部极值点在的区域内。我们先将函数、、投影到平面上，点为曲线与等值线的切点。

        第一种情况如下图所示

                           

此时不等式约束成为了等式约束，在2.1节中的约束问题中，因为等式约束的原因无法施加更多的约束，只能要求目标函数与约束函数在切点处的梯度共线，而在不等式约束中，尽管切点位于约束区域的边界上，但仍能将约束条件加强，我们知道梯度是数值增大最快的方向，函数在切点处的梯度肯定不是指向可行域的，因为这会使的值减小，而我们的目标是极小值优化问题，切点处是一个极小值点，因此在可行域内越靠近切点，的值越小，所以函数在切点处的梯度方向应该是指向区域的，因此函数、在切点处的梯度方向相反，这样我们可以利用拉格朗日乘子法构建函数

                                                        

极值点一定满足如下条件

                                                       

                                                                             

                                                                             

                                                                                   

 

        第二种情况，切点 不在区域的边界上，满足

                                           

这种情况下在切点处的不等式约束相当于不存在，我们可以构建函数为

                                                      

极值点一定满足如下条件

                                                       

                                                                         

                                                                          

                                                                                  

结合以上两种情况，我们可以利用拉格朗日乘子法构造如下函数

                                 

该函数的极值点满足

                                                    

                                                                           

                                                                           

                                                                                   

                                                                     

3.KKT条件与对偶问题

       第2节中最终总结出了极值点需满足的条件，这样一组约束条件即称为KKT条件，它是优化问题中获取极值点的必要条件。当然，在实际中并不是所有情况下极值点一定满足KKT条件，解出的极值点还是要代入目标函数中检查，要想一个优化问题的极值点满足KKT条件还需要一些规范性条件，我这里不在此列出这些规范性条件了(可以在文章推荐的文章中学习)。依据以上KKT条件，我们就可以求解优化问题了，但一般直接求解这组方程是比较困难的，为了更好的解决这个优化问题，数学家还找到了它的对偶问题，当对偶问题比较容易求解时，我们可以通过求解对偶问题来间接的求解原优化问题，我们还是以单个等式约束、不等式约束问题为例来说明其对偶问题。

       利用拉格朗日乘子法构建以下函数及约束条件

                                                     

                                                                        

                                                                               

                                                                                        

                                                                            

我们先来看一下，约束范围内的点满足、，所以可以得到

                                                                        

不在约束范围内的点，可以调整  和  的值使用取到无穷大

                                                                         

此时求解是没什么意义的。现在我们只考虑满足约束的点，那么原优化问题可以表达成

                                                                                                                        (4)

该问题的对偶问题即为

                                                                                                                        (5)

我们有

                                                                         

在很多文章中都说 “ 最大值中的最小值比最小值中的最大值大是很显然 ”，这样的理解在多变量函数中理解起来有点费劲，不过也暂时只能先这样理解了。求解公式(5)得到的解并不一定是公式(4)中的最优解，那么我们自然就会问，在什么条件下，公式(5)与公式(4)表示的问题是等价的呢？在上面说到的满足KKT条件所需的一些规范性条件中，有一个条件称为 条件，满足 条件的约束问题具有强对偶性质，公式(5)与公式(4)中的解是等价的。 条件表述为：如果优化问题是个凸优化问题，且至少存在一个点满足 和 ，则极值一定满足 KKT 条件，并且满足强对偶性质。

       本篇文章到这里为止，已经将准备知识说完了，接下来我们着手处理一下上一篇遗留的优化问题。

4.构建SVM超平面时的优化问题

   上一篇中最后的优化问题为

                                                                     

   我们将其转化为

                                                                                    

                                                                                   

这是等价的，目标函数显然是一个我们熟知凸函数，约束条件定义的可行域也是上文中所说的凸集，所以这是一个凸优化问题。先利用拉格朗日乘子法构建如下函数

                                                           

                                                                                                                                                          

                                                                                               

我们的优化目标可以表达如下

                                                                                                         

                                                                                                                                                                 

                                                                                               

其对偶问题为

                                                                                        (6)                                                       

                                                                                                                                               

                                                                                               

很明显，支持向量上的点满足，因此优化问题满足 条件，因此其对偶问题的解等价于原问题的解，这样我们可以直接求解其对偶问题的最优解。

 求取对、的偏导数，并令其为0，得到

                                                             

                                                      

将计算的结果代入公式(6)中，得到

                                                                 

利用一些数值计算软件，在训练数据集上就可以计算出结果满足最优结果的值了，继而求解出、。也有一些算法能快速计算出结果，这个我们后面再介绍，完全线性可分情况下的支持向量机构建到这里也就完成了。事实上，并不是所有的值均非0，只有支持向量机上的点其对应的值才非0，这和不等式约束中的第一种情况一致。

5.小结

      本篇博客中首先介绍了构建SVM时涉及的数值优化计算过程的背景知识，但是我没有很详细的介绍，只是介绍了一些必须的部分，感兴趣的同学可以自己再去多了解一些。本系列的前两篇介绍的是在数据完全线性可分情况下SVM的构建，但数据完全线性可分的情况毕竟很少，因此这样构建的SVM模型分类效果并不好，下一篇开始将进一步介绍数据不完全线性可分情况下SVM的构建。