前面讲到，SVM的学习问题可以转化为下面的对偶问题：
需要满足的KKT条件：
也就是说找到一组αi可以满足上面的这些条件的就是该目标的一个最优解。所以我们的优化目标是找到一组最优的αi*。一旦求出这些αi*，就很容易计算出权重向量w*和b，并得到分隔超平面了。
这是个凸二次规划问题，它具有全局最优解，一般可以通过现有的工具来优化。但当训练样本非常多的时候，这些优化算法往往非常耗时低效，以致无法使用。从SVM提宽如岁出到现在，也出现了很多优化训练的方法。其中，非常出名的一个是1982年由Microsoft Research的John C. Platt在论文《Sequential Minimal Optimization: A Fast Algorithm for TrainingSupport Vector Machines》中提出的Sequential Minimal Optimization序列最小化优化算法，简称SMO算法。SMO算法的思想很简单，它将大优化的问题分解成多个小优化的问题。这些小问题往往比较容易求解，并且对他们进行顺序求解的结果与将他们作为整体来求解的结果完全一致。在结果完全一致的同时，SMO的求解时间短很多。在深入SMO算法之前，我们先来了解下坐标下降这个算法，SMO其实基于这种简单的思想的。
8.1、坐标下降（上升）法
假设要求解下面的优化问题：
在这里，我们需要求解m个变量αi，一般来说是通过梯度下降（这里是求最大值，所以应该叫上升）等算法每一次迭代对所有m个变量αi也就是α向量进行一次性优化。通过误差每次迭代调整α向量中每个元素的值。而坐标上升法（坐标上升与坐标下降可以看做是一对，坐标上升是用来求解max最优化问题，坐标下降用于求min最优化问题）的思想是每次迭代只调整一个变量αi的值，其他变量的值在这次迭代中固定不变。
最里面语句的意思是固定除αi之外的所有αj(i不等于j)，这时W可看作只是关于αi的函数，那么直接对αi求导优化即可。这里我们进行最大化求导的顺序i是从1到m，可以通过更改优化顺序来使W能够更快地增加并收敛。如果W在内循环中能够很快地达到最优，那么坐标上升法会是一个很高效的求极值方法。
用个二维的例子来说明下坐标下橡哪降法：我们需要寻找f(x,y)=x2+xy+y2的最小值处的(x*, y*)，也就是下图的F*点的地方。
假设我们初始的点是A（图是函数投影到xoy平面的等高线图，颜色越深值越小），我们需要达到F*的地方。那最快的方法就是图中黄色线的路径，一次性就到达了，其实这个是牛顿优化法，但如果是高维的话，这个方法就不太高效了（因为需要求解矩阵的逆，这个不在这里讨论）。我们也可以按照红色所指示的路径来走。从A开始，先固定x，沿着y轴往让f(x, y)值减小的方向走到B点，然后固定y，沿着x轴慎睁往让f(x, y)值减小的方向走到C点，不断循环，直到到达F*。反正每次只要我们都往让f(x, y)值小的地方走就行了，这样脚踏实地，一步步走，每一步都使f(x, y)慢慢变小，总有一天，皇天不负有心人的。到达F*也是时间问题。到这里你可能会说，这红色线比黄色线贫富差距也太严重了吧。因为这里是二维的简单的情况嘛。如果是高维的情况，而且目标函数很复杂的话，再加上样本集很多，那么在梯度下降中，目标函数对所有αi求梯度或者在牛顿法中对矩阵求逆，都是很耗时的。这时候，如果W只对单个αi优化很快的时候，坐标下降法可能会更加高效。
8.2、SMO算法
SMO算法的思想和坐标下降法的思想差不多。唯一不同的是，SMO是一次迭代优化两个α而不是一个。为什么要优化两个呢？
我们回到这个优化问题。我们可以看到这个优化问题存在着一个约束，也就是
假设我们首先固定除α1以外的所有参数，然后在α1上求极值。但需要注意的是，因为如果固定α1以外的所有参数，由上面这个约束条件可以知道，α1将不再是变量（可以由其他值推出），因为问题中规定了：
因此，我们需要一次选取两个参数做优化，比如αi和αj，此时αi可以由αj和其他参数表示出来。这样回代入W中，W就只是关于αj的函数了，这时候就可以只对αj进行优化了。在这里就是对αj进行求导，令导数为0就可以解出这个时候最优的αj了。然后也可以得到αi。这就是一次的迭代过程，一次迭代只调整两个拉格朗日乘子αi和αj。SMO之所以高效就是因为在固定其他参数后，对一个参数优化过程很高效（对一个参数的优化可以通过解析求解，而不是迭代。虽然对一个参数的一次最小优化不可能保证其结果就是所优化的拉格朗日乘子的最终结果，但会使目标函数向极小值迈进一步，这样对所有的乘子做最小优化，直到所有满足KKT条件时，目标函数达到最小）。
总结下来是：
重复下面过程直到收敛{
（1）选择两个拉格朗日乘子αi和αj；
（2）固定其他拉格朗日乘子αk(k不等于i和j)，只对αi和αj优化w(α)
（3）根据优化后的αi和αj，更新截距b的值；
}
拉格朗日乘子法是一种寻找多元函数在一组约束下的极值方法。
上图中
与椭圆体相交则升薯平面上直线 如果高度上没有限制那么 就形成一个面，这个面与椭圆体相交可以表示为 ,我们孙者就可以在这个曲线找到最小值。然后我们可以将这等高线投影到二维平面上来简化问题
在上图中，我们可以推断出其实最小(或最大值)就位于限制条件g(x,y)和方程f(x,y)等号线相切的位置。而且有共同切线的斜率，那么他们法线方向是 成比例 的。这个比例系数就是拉格朗日乘子
我们现在来简单推导笑磨一下，这里将 y 表示为对于 x 的函数，那么就有 y(x),然后分别带入下面两个方程就得到。
下面我么这个两个方程都对x 进行偏微分，通过链式法则我们就得到下面式子
因为我们知道他们斜率是成比例的，所有就可以得到这样结论，这就是拉格朗日乘子法，其中 就是乘子
我们就可以利用这个三个条件来求在有限制条件下方程极值问题
假设 ,在 的条件限制下有极值。
利用上面知识来求极值
然后他们带入到 得到
那么结果就是最小值和最大值分别是 5 和 -5
在前面的几讲中，我们终于引出了支撑向量的概念，同时得到了求解最大间隔分类器的桐慧目标规划式，接下来，我们就要对该式进行求解，但在正式求解之前，我想介绍一下求解需要了解的两个知识，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）条件。在求解最优化问题中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件。这一节，我们先来介绍拉格朗日乘子法。
我们这里提到的最优化问题通常是指对于给定的某一函数，求其在指定作用域上的全局最小值(因为最小值与最大值可以很容易转化，即最大值问题可以转化成最小值问题)。 一般情况下，最优化问题会碰到一下三种情况：
这是最简单的情况，解决方法通常是函数对变量求导，令求导函数等于0的点可能是极值点。将结果带回原函数进行验证即可。
这里的等式约束条件一般形式如下：
则解决方法是消元法或者拉格朗日法。消元法比较简单不在赘述，这里主要讲拉格朗日法，因为后面提到的KKT条件是对拉格朗日乘子法的一种泛化。
我们先通过一个例子来直观感受下拉格朗日乘子法，至于为什么这么做是可行的，后面会进一步介绍。
假设我们的目标函数如下：
约束条件如下：
拉格朗日乘子法的一般做法是将约束条件加入到目标函数中，将问题转化为无约束条件的问题，随后对参数进行求导解得极值。
到我们的题目中，我们将有约束的最优化问题转换为无约束的最优化问题如下：
可以看到，现在的问题中有四个参数，我们分别对四个参数求偏导数：
对后联立四个方程可以求解得到：
为什么这么做是可行的呢？维基百科上的解释很好，这里我拿来用一下。以一个最简单的二维优化问题为例：
这里画出z=f(x,y)的等高线：
绿线标出的是约束g(x,y)=c的点的轨迹。蓝线是f(x,y)的等高线。箭头表示斜率，和等高线的法线平行。从梯度的方向上来看，显然有d1>d2。绿色的线是约束，也就是说，只要正好落在这条绿线上的点才可能是满足要求的点。如果没有这条约束，f(x,y)的最小值应该会落在最小那圈等高线内部的某一点上。而现在加上了约束，最小值点应该在哪里呢？显然应该是在f(x,y)的等高线正好和约束线相切的位置，因为如果只是相交意味着弊激肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小，只有到等高线与目标函数的曲线相切的时候，可能取得最优值。
相切的时候满足什么条件呢？从图上的梯度方向箭头可以很明显的看出来，相切的时候f(x,y)和g(x,y)的梯度一定是在同一个方向上的，也就是说∇f(x,y)=λ（∇g(x,y)-C) ，这里∇代表函数的梯度。
这时候再来看我们的之前例子的求解过程，我们对所有参数求偏导数：
令上面式子中的前三个等于0，其实就是令∇f(x,y)=λ（∇g(x,y)-C)，
而第四个式子恰好是使求得的x,y,z满足我们原有的约束条件。所以可以看到，拉格朗日乘子法在求解等式约束条件的最优化问题时是可行的！
之前我们说最优化问题会碰到一下三种情况，这一讲只介绍了租轮袜两种，第三种我们将留到下一讲中介绍！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）