机器学习之对偶支持向量机（机器学习技法）
为什么要有一个对偶问题
一般SVM的求解
一般SVM的求解我们的目标就是最小化W²而且伴随着一个条件如下图：
在实务上我们通常把这个标准问题转化为一个二次规划的问题（以下称之为QP问题）然后使用软件去解决这个问题找到最优的b，W：
在我们得到一个线性的SVM的时候我们可以通过特征转换让SVM变成更为强大的非线性分类器。
遇到的问题和我们的目标
在解决QP问题是时我们会遇到d+1个变量和N个约束条件，有时候由于一些复杂的特征转换我们转换到的一个空间的维度可能是非常高的，在非常高维的空间里d+1的值是非常大（有可能有无限多维）的与此同时我们的QP的计算会变得非常复杂。所以我们的目的是：我们要使得我们的求解不受d大小的影响。具体如下图：
我们想要找到一个原始问题的等价问题，新的QP问题只受资料量的影响有N个变数与N+1个约束条件，这个新的问题就是原始问题的对偶问题。
SVM的对偶问题
拉格朗日乘子法
机器学习中的正则化问题与对偶问题相同的是它们都是解决有限制条件下的最佳化问题，在机器学习基石中我们通常以下的方式去解决问题：
我们会通过拉格朗日乘子法去将原始的问题转化成一个多带一项的问题去解决（如上图中的从最小化Ein到最小化Eaug就是这个过程）。最后通过调试已给的λ来求出最优解。其中正则化中只有一个限制条件所以会有1个参数λ。
对偶SVM与拉格朗日乘子法
在解决SVM的最优化问题时我们有N个限制条件所以我们就会有N个类似于λ的乘子（在SVM问题中我们通常使用的符号是α），现在我们将原始的带有N个限制条件的SVM的最优化问题通过拉格朗日乘子法转换成一个新的无条件的多带N项的对偶问题如下图：
以前的条件都丢到我们要求解的问题中成为了我们要求解的一部分（特别声明上图右方就是转化后的问题我们称之为拉格朗日函数L），我们可以通过一个特殊的最佳化过程让这个对偶问题顺利解决，如下图：
我们的最佳化过程为：
①首先将L函数最大化，条件是参数α>=0
②将①的结果最小化，这样就得到了我们的最优解
最优化过程的理论保障
事实上在上述的最佳化的过程中我们隐含了选择过程它把不满足条件的解统统舍去。
①在不满足条件时，我们的最佳化的①步骤会趋向于无穷大使得我们最小化①的步骤无法进行。
②在满足条件时，我们的最佳化的①步骤会趋向于一个常数这样我们的最小化的步骤会顺利进行，最后的最大值为图中的□（也就是□后面的值为0，因为只有为0的时候才能够做最佳化，无论是α为0或者后面的式子为0）。
这样在最优化的时候就会将不满足条件的解统统过滤掉，我们“去掉”了原来绑手绑脚的条件。
SVM对偶问题的进一步转换——拉格朗日对偶问题
弱对偶关系与强对偶关系
在上面的推导中我们知道SVM的对偶问题中L函数中的参数是先经过最大化时取得的参数（比如说α），所以再随便找到一个α’的时候L函数的最小值肯定会<=原始函数的L函数。由于上图中前面的值老是>=后面的值，所以前面的最小值也会>=后面的最大值如下图：
上图后面的式子称作拉格朗日对偶问题。现在我们知道拉格朗日对偶问题是SVM对偶问题的下限，它们的关系很弱在最佳化问题中我们称之为弱对偶关系。
但是我们想要让上图中两个问题的解具有等价关系那么就需要它们两个是强对偶关系。首先说说强对偶关系的好处（也就是解上图右边式子的好处）：它能使我们以前解决的SVM的最佳化问题（b与W的最佳化）转化成直接解决一个无条件的最小化问题（上图右的L函数的最小化），而我们擅长于解决无条件的最佳化问题。
强对偶关系的条件
做最佳化问题的人推导了一下对于QP（二次规划）来说：
①我们要解的问题是凸函数的
②我们的原来的问题是有解的（能够找到原始资料的分割线）
③线性的限制条件
满足以上三个条件我们就认定它们有对偶关系，原始的问题确实满足这三个条件。
解决拉格朗日对偶问题
首先声明目标我们要解决的就是以下的问题：
首先解决L函数的最小化问题。我们首先想想一个凸函数的最优解肯定是在函数的谷底，这个时候函数的梯度等于0，也就是函数对于我们想要最佳化的变量W与b的偏导数都是0。以逆向思维来说就是b的偏导数 = 0与W的偏导数 = 0是最优解的条件，既然我们求的是最佳解那么我们不妨把这些条件加进去。
b的偏导数等于0有如下的结论：
将这个推论带到最佳化问题中会发现含有b的项都被消去，如下：
W的偏导数等于0有如下推论：
将这个推论的条件带入最佳化问题中会得到：
我们最后的问题消去了b，其中W也用α来代替了，我们只需求出最佳化问题中α的值就能够求出最佳的b与W的值。但同时要满足一些条件。这就是终结版本的简化版的拉格朗日的对偶问题。
KKT条件
在最佳解的条件下α，b，W都会满足一些关系，这些关系就叫做KKT条件。
①满足最原始标准问题的条件。
②满足对偶问题的基本条件。
③最佳化解时候（梯度为0）b与W的条件。
④SVM对偶问题中的隐含条件。
这些条件统称为KKT条件，用这些条件可以简化拉格朗日对偶问题。一个有最佳解的问题与满足KKT条件互为充分必要条件。
解决拉格朗日对偶问题
对偶问题的变形
我们的原始问题如下图：
我们习惯于解决最小化的问题，所以我们在上述问题中加一个负号将原始问题改为一个最小化问题。同时我们将二次项展开得到如下问题：
整个问题有以下几个要点：
①我们要求的是α所以去掉了有关W的约束条件。
②整个问题有N个变量，α从1到N。
③整个问题有N+1个约束条件，N（N个α>=0）,1(y*α的和 = 0)。
将对偶问题准换成标准的QP问题
①二次项系数为ynymznzm。
②一次项系数为长度为N各项都为-1的向量。
③a为条件中的α的一次项系数，在此我们特地的将ynαn = 0拆解成为它既大于0又小于0，我们用两个条件代替了一个等号条件。与此同时还有αn都得>=0，它的系数为单位向量。
④出现的三个常数项都各自为c = 0。
在实务上有很多软件都会有解决特殊的问题比如可以直接表示等式，还比如说是上下限也可以特殊的给定。
用软件解决QP问题的注意事项
通常我们会使用专门为SVM所设计的软件去解决QP问题，这些软件会利用一些特殊的规则与计算方式。比如在实际当中当资料量很大的时候QD矩阵的规模就很大而且大多数的元素都是非0项，这时的运算量就会非常大。而在使用特殊的软件之后我们只会在用到QD的时候进行计算以此来提高效率。
得到最优的W与b
由于KKT条件与最优解互为充要条件，所以我们可以在求出α的基础上利用KKT条件来求出最好的W与b。
其中W的值非常容易求直接带入。
b的值可以通过上图中的complementary slackness来解决。如果我们找到任意一个αn>0那么b的值如下：
此时此刻（αn>0）我们会得到y*S = 1（S为得分函数），算出来的这个点就在我们模型的边界上它是一个支撑向量。那么我们就可以说αn>0时的这些点就是支撑向量。事实上在模型边界上的点有的不满足αn>0，我们只把αn>0的点称之为支撑向量。
在计算W的时候只用支撑向量就好，因为其它的资料点αn = 0时W的值直接置为0就好参与计算会浪费计算资源。b的计算也是找一个任意的支撑向量就可以。除了支撑向量其他的资料点对于模型来说一点都不重要，如下：
SVM背后的哲学意义
SVM与PLA中的权重W都是原始资料的线性组合。SVM中的W只是支撑向量的线性组合，PLA中的W只是犯错误资料的线性组合。这些都说明了谁对W重要，SVM说重要的是那些支撑向量，PLA说重要的是那些犯错误的资料。
SVM的两种解决手段
原始的SVM与对偶的SVM的最大区别就是谁在决定变量的个数，原始问题是由转换后空间模型的VC维度决定，对偶问题是由资料量来决定。当VC维度很高的我们可以选择使用对偶问题来解决，当资料量过大的时候我们可能会选择原始的解决方法。
潜在的危机
事实上我们的对偶SVM并没有消除我们的计算量对VC维度的依赖，我们只是把它藏了起来没有体现在模型的变量的个数中，它潜藏在了QP问题的Q矩阵Z向量的内积中。至于如何避开这个依赖，敬请期待 : -)