请先阅读：
支持向量机通俗导论：理解SVM的三层境界（一）
支持向量机通俗导论：理解SVM的三层境界（二）
第三层、证明SVM
说实话，凡是涉及到要证明的东西.理论，便一般不是怎么好惹的东西。绝大部分时候，看懂一个东西不难，但证明一个东西则需要点数学功底，进一步，证明一个东西也不是特别难，难的是从零开始发明创造这个东西的时候，则显艰难(因为任何时代，大部分人的研究所得都不过是基于前人的研究成果，前人所做的是开创性工作，而这往往是最艰难最有价值的，他们被称为真正的先驱。牛顿也曾说过，他不过是站在巨人的肩上。你，我则更是如此)。
正如陈希孺院士在他的著作《数理统计学简史》的第4章、最小二乘法中所讲：在科研上诸多观念的革新和突破是有着很多的不易的，或许某个定理在某个时期由某个人点破了，现在的我们看来一切都是理所当然，但在一切没有发现之前，可能许许多多的顶级学者毕其功于一役，耗尽一生，努力了几十年最终也是无功而返。
话休絮烦，要证明一个东西先要弄清楚它的根基在哪，即构成它的基础是哪些理论。OK，以下内容基本是上文中未讲到的一些定理的证明，包括其背后的逻辑、来源背景等东西，还是读书笔记。
本部分导述
3.1、线性学习器
3.1.1、感知机算法
这个感知机算法是1956年提出的，年代久远，依然影响着当今，当然，可以肯定的是，此算法亦非最优，后续会有更详尽阐述。不过，有一点，你必须清楚，这个算法是为了干嘛的：不断的训练试错以期寻找一个合适的超平面(是的，就这么简单)
下面，举个例子。如下图所示，凭我们的直觉可以看出，图中的红线是最优超平面，蓝线则是根据感知机算法在不断的训练中，最终，若蓝线能通过不断的训练移动到红线位置上，则代表训练成功。
既然需要通过不断的训练以让蓝线最终成为最优分类超平面，那么，到底需要训练多少次呢？Novikoff定理告诉我们当间隔是正的时候感知机算法会在有限次数的迭代中收敛，也就是说Novikoff定理证明了感知机算法的收敛性，即能得到一个界，不至于无穷循环下去。
这里
，
为扩充间隔。根据误分次数公式可知, 迭代次数与对应于扩充(包括偏置)权重的训练集的间隔有关。
顺便再解释下这个所谓的扩充间隔，即为样本到分类间隔的距离，即从引出的最大分类间隔。OK，还记得上文第1.3.2节开头的内容么？如下：“
在给出几何间隔的定义之前，咱们首先来看下，如上图所示，对于一个点 x ，令其垂直投影到超平面上的对应的为 x0 ，由于 w 是垂直于超平面的一个向量，
为样本x到分类间隔的距离，我们有
”
然后后续怎么推导出最大分类间隔请回到本文第一、二部分，此处不重复板书。
同时有一点得注意：感知机算法虽然可以通过简单迭代对线性可分数据生成正确分类的超平面，但不是最优效果，那怎样才能得到最优效果呢，就是上文中第一部分所讲的寻找最大分类间隔超平面。此外，Novikoff定理的证明请见这里http://www.cs.columbia.edu/~mcollins/courses/6998-2012/notes/perc.converge.pdf。
3.2、非线性学习器
3.2.1、Mercer定理
Mercer定理 ：如果函数K是
上的映射（也就是从两个n维向量映射到实数域）。那么如果K是一个有效核函数（也称为Mercer核函数），那么当且仅当对于训练样例
，其相应的核函数矩阵是对称半正定的。
要理解这个Mercer定理，先要了解什么是半正定矩阵，要了解什么是半正定矩阵，先得知道什么是正定矩阵http://zh.wikipedia.org/wiki/正定矩阵（矩阵理论博大精深，关于矩阵推荐我正在看的一本《矩阵分析与应用》）。然后这里http://ftp136343.host106.web522.com/a/biancheng/matlab/2013/0120/648.html有一个此定理的证明，可以看下。
正如@Copper_PKU所说：核函数在SVM的分类效果中起了重要的作用，最后这里https://people.eecs.berkeley.edu/~bartlett/courses/281b-sp08/7.pdf有个tutorial可以看看。
3.3、损失函数
在本文1.0节有这么一句话“支持向量机(SVM)是90年代中期发展起来的基于统计学习理论的一种机器学习http://lib.csdn.net/base/machinelearning方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。”但初次看到的读者可能并不了解什么是结构化风险，什么又是经验风险。要了解这两个所谓的“风险”，还得又从监督学习说起。
监督学习实际上就是一个经验风险或者结构风险函数的最优化问题。风险函数度量平均意义下模型预测的好坏，模型每一次预测的好坏用损失函数来度量。它从假设空间F中选择模型f作为决策函数，对于给定的输入X，由f(X)给出相应的输出Y，这个输出的预测值f(X)与真实值Y可能一致也可能不一致，用一个损失函数来度量预测错误的程度。损失函数记为L(Y, f(X))。
常用的损失函数有以下几种（基本引用自《统计学习方法》）：
如此，SVM有第二种理解，即最优化+损失最小，或如@夏粉_百度所说“可从损失函数和优化算法角度看SVM，boosting，LR等算法，可能会有不同收获”。
OK，关于更多统计学习方法的问题，请参看此文http://blog.csdn.net/qll125596718/article/details/8351337。
关于损失函数，如下文读者评论中所述：可以看看张潼的这篇《Statistical behavior and consistency of classification methods based on convex risk minimization》。各种算法中常用的损失函数基本都具有fisher一致性，优化这些损失函数得到的分类器可以看作是后验概率的“代理”。此外，张潼还有另外一篇论文《Statistical analysis of some multi-category large margin classification methods》，在多分类情况下margin loss的分析，这两篇对Boosting和SVM使用的损失函数分析的很透彻。
3.4、最小二乘法
3.4.1、什么是最小二乘法？
既然本节开始之前提到了最小二乘法，那么下面引用《正态分布的前世今生》里的内容稍微简单阐述下。
我们口头中经常说：一般来说，平均来说。如平均来说，不吸烟的健康优于吸烟者，之所以要加“平均”二字，是因为凡事皆有例外，总存在某个特别的人他吸烟但由于经常锻炼所以他的健康状况可能会优于他身边不吸烟的朋友。而最小二乘法的一个最简单的例子便是算术平均。
最小二乘法（又称最小平方法）是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。用函数表示为：
使误差「所谓误差，当然是观察值与实际真实值的差量」平方和达到最小以寻求估计值的方法，就叫做最小二乘法，用最小二乘法得到的估计，叫做最小二乘估计。当然，取平方和作为目标函数只是众多可取的方法之一。
最小二乘法的一般形式可表示为：
有效的最小二乘法是勒让德在 1805 年发表的，基本思想就是认为测量中有误差，所以所有方程的累积误差为
我们求解出导致累积误差最小的参数即可：
勒让德在论文中对最小二乘法的优良性做了几点说明：
对于最后一点，从统计学的角度来看是很重要的一个性质。推理如下：假设真值为 θ, x1,⋯,xn为n次测量值, 每次测量的误差为ei=xi−θ，按最小二乘法，误差累积为
求解 使
达到最小，正好是算术平均
。
由于算术平均是一个历经考验的方法，而以上的推理说明，算术平均是最小二乘的一个特例，所以从另一个角度说明了最小二乘方法的优良性，使我们对最小二乘法更加有信心。
最小二乘法发表之后很快得到了大家的认可接受，并迅速的在数据分析实践中被广泛使用。不过历史上又有人把最小二乘法的发明归功于高斯，这又是怎么一回事呢。高斯在1809年也发表了最小二乘法，并且声称自己已经使用这个方法多年。高斯发明了小行星定位的数学方法，并在数据分析中使用最小二乘方法进行计算，准确的预测了谷神星的位置。
说了这么多，貌似跟本文的主题SVM没啥关系呀，别急，请让我继续阐述。本质上说，最小二乘法即是一种参数估计方法，说到参数估计，咱们得从一元线性模型说起。
3.4.2、最小二乘法的解法
什么是一元线性模型呢？ 请允许我引用这里http://blog.csdn.net/qll125596718/article/details/8248249的内容，先来梳理下几个基本概念：
监督学习中，如果预测的变量是离散的，我们称其为分类（如决策树，支持向量机等），如果预测的变量是连续的，我们称其为回归。
回归分析中，如果只包括一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归分析称为一元线性回归分析。
如果回归分析中包括两个或两个以上的自变量，且因变量和自变量之间是线性关系，则称为多元线性回归分析。
对于二维空间线性是一条直线；对于三维空间线性是一个平面，对于多维空间线性是一个超平面...
对于一元线性回归模型, 假设从总体中获取了n组观察值（X1，Y1），（X2，Y2）， …，（Xn，Yn）。对于平面中的这n个点，可以使用无数条曲线来拟合。要求样本回归函数尽可能好地拟合这组值。综合起来看，这条直线处于样本数据的中心位置最合理。
选择最佳拟合曲线的标准可以确定为：使总的拟合误差（即总残差）达到最小。有以下三个标准可以选择：
用“残差和最小”确定直线位置是一个途径。但很快发现计算“残差和”存在相互抵消的问题。
用“残差绝对值和最小”确定直线位置也是一个途径。但绝对值的计算比较麻烦。
最小二乘法的原则是以“残差平方和最小”确定直线位置。用最小二乘法除了计算比较方便外，得到的估计量还具有优良特性。这种方法对异常值非常敏感。
最常用的是普通最小二乘法（ Ordinary Least Square，OLS）：所选择的回归模型应该使所有观察值的残差平方和达到最小，即采用平方损失函数。
我们定义样本回归模型为:
其中ei为样本（Xi, Yi）的误差。
接着，定义平方损失函数Q：
则通过Q最小确定这条直线，即确定
，以为变量，把它们看作是Q的函数，就变成了一个求极值的问题，可以通过求导数得到。
求Q对两个待估参数的偏导数：
根据数学知识我们知道，函数的极值点为偏导为0的点。
解得：
这就是最小二乘法的解法，就是求得平方损失函数的极值点。自此，你看到求解最小二乘法与求解SVM问题何等相似，尤其是定义损失函数，而后通过偏导求得极值。
OK，更多请参看陈希孺院士的《数理统计学简史》的第4章、最小二乘法。
3.5、SMO算法
在上文中，我们提到了求解对偶问题的序列最小最优化SMO算法，但并未提到其具体解法。首先看下最后悬而未决的问题：
等价于求解：
1998年，Microsoft Research的John C. Platt在论文https://www.microsoft.com/en-us/research/?from=http%3A%2F%2Fresearch.microsoft.com%2Fen-us%2Fum%2Fpeople%2Fjplatt%2Fsmotr.pdf《Sequential Minimal Optimization：A Fast Algorithm for Training Support Vector Machines》中提出针对上述问题的解法：SMO算法，它很快便成为最快的二次规划优化算法，特别是在针对线性SVM和数据稀疏时性能更优。
接下来，咱们便参考John C. Platt的这篇https://www.microsoft.com/en-us/research/?from=http%3A%2F%2Fresearch.microsoft.com%2Fen-us%2Fum%2Fpeople%2Fjplatt%2Fsmotr.pdf文章来看看SMO的解法是怎样的。
3.5.1、SMO算法的推导
咱们首先来定义特征到结果的输出函数：
注：这个u与我们之前定义的
实质是一样的。
接着，重新定义下咱们原始的优化问题，权当重新回顾，如下：
求导得到：
代入中，可得
。
通过引入拉格朗日乘子转换为对偶问题后，得：
s.t：
且
注：这里得到的min函数与我们之前的max函数实质也是一样，因为把符号变下，即由min转化为max的问题，且yi也与之前的等价，yj亦如此。
经过加入松弛变量后，模型修改为：
从而最终我们的问题变为：
下面要解决的问题是：在
上求上述目标函数的最小值。为了求解这些乘子，每次从中任意抽取两个乘子
和
，然后固定和以外的其它乘子
，使得目标函数只是关于和的函数。这样，不断的从一堆乘子中任意抽取两个求解，不断的迭代求解子问题，最终达到求解原问题的目的。
而原对偶问题的子问题的目标函数可以表达为：
其中
为了解决这个子问题，首要问题便是每次如何选取和。实际上，其中一个乘子是违法KKT条件最严重的，另外一个乘子则由另一个约束条件选取。
根据KKT条件可以得出目标函数中
取值的意义：
这里的还是拉格朗日乘子：
对于第1种情况，表明是正常分类，在间隔边界内部（我们知道正确分类的点
）；
对于第2种情况，表明了是支持向量，在间隔边界上；
对于第3种情况，表明了是在两条间隔边界之间；
而最优解需要满足KKT条件，即上述3个条件都得满足，以下几种情况出现将会出现不满足：
也就是说，如果存在不满足KKT条件的
，那么需要更新这些，这是第一个约束条件。此外，更新的同时还要受到第二个约束条件的限制，即
。
因此，如果假设选择的两个乘子
和
，它们在更新之前分别是
、
，更新之后分别是
、
，那么更新前后的值需要满足以下等式才能保证和为0的约束：
其中，
是常数。
两个因子不好同时求解，所以可先求第二个乘子的解（），得到的解（）之后，再用的解（）表示的解（）。
为了求解，得先确定的取值范围。假设它的上下边界分别为H和L，那么有：
接下来，综合
和这两个约束条件，求取的取值范围。
当y1 != y2时，根据可得
，所以有
，
，如下图所示：
当y1 = y2时，同样根据可得：
，所以有
，
，如下图所示：
如此，根据y1和y2异号或同号，可得出的上下界分别为：
回顾下第二个约束条件，令上式两边乘以y1，可得
其中，
。
因此可以用表示，
，从而把子问题的目标函数转换为只含的问题：
对求导，可得
化简下：
然后将
、、和代入上式可得：
令
（表示预测值与真实值之差），
，然后上式两边同时除以
，得到一个关于单变量的解：
这个解没有考虑其约束条件
，即是未经剪辑时的解。
然后考虑约束可得到经过剪辑后的的解析解为：
求出了后，便可以求出，得
。
那么如何选择乘子和呢？
而b在满足下述条件：
下更新b：
且每次更新完两个乘子的优化后，都需要再重新计算b，及对应的Ei值。
最后更新所有，y和b，这样模型就出来了，从而即可求出咱们开头提出的分类函数：
此外，这里http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html也有一篇类似的文章，大家可以参考下。
3.5.2、SMO算法的步骤
综上，总结下SMO的主要步骤，如下：
意思是，
第一步选取一对
和
，选取方法使用启发式方法；
第二步，固定除和之外的其他参数，确定W极值条件下的，由表示。
假定在某一次迭代中，需要更新
，
对应的拉格朗日乘子
，
，那么这个小规模的二次规划问题写为：
那么在每次迭代中，如何更新乘子呢？引用这里http://staff.ustc.edu.cn/~ketang/PPT/PRLec5.pdf的两张PPT说明下：
知道了如何更新乘子，那么选取哪些乘子进行更新呢？具体选择方法有以下两个步骤：
步骤1：先“扫描”所有乘子，把第一个违反KKT条件的作为更新对象，令为a1；
步骤2：在所有不违反KKT条件的乘子中，选择使|E1 −E2|最大的a2进行更新，使得能最大限度增大目标函数的值（类似于梯度下降. 此外，而，求出来的E代表函数ui对输入xi的预测值与真实输出类标记yi之差）。
最后，每次更新完两个乘子的优化后，都需要再重新计算b，及对应的Ei值。
综上，SMO算法的基本思想是将Vapnik在1982年提出的Chunking方法推到极致，SMO算法每次迭代只选出两个分量ai和aj进行调整，其它分量则保持固定不变，在得到解ai和aj之后，再用ai和aj改进其它分量。与通常的分解算法比较，尽管它可能需要更多的迭代次数，但每次迭代的计算量比较小，所以该算法表现出较好的快速收敛性，且不需要存储核矩阵，也没有矩阵运算。
3.5.3、SMO算法的实现
行文至此，我相信，SVM理解到了一定程度后，是的确能在脑海里从头至尾推导出相关公式的，最初分类函数，最大化分类间隔，max1/||w||，min1/2||w||^2，凸二次规划，拉格朗日函数，转化为对偶问题，SMO算法，都为寻找一个最优解，一个最优分类平面。一步步梳理下来，为什么这样那样，太多东西可以追究，最后实现。如下图所示：
至于下文中将阐述的核函数则为是为了更好的处理非线性可分的情况，而松弛变量则是为了纠正或约束少量“不安分”或脱离集体不好归类的因子。
台湾的林智仁教授写了一个封装SVM算法的libsvm库http://www.csie.ntu.edu.tw/~cjlin/libsvm/，大家可以看看，此外这里http://www.pami.sjtu.edu.cn/people/gpliu/document/libsvm_src.pdf还有一份libsvm的注释文档。
除了在这篇论文《fast training of support vector machines using sequential minimal optimization》中platt给出了SMO算法的逻辑代码之外，这里http://blog.csdn.net/techq/article/details/6171688也有一份SMO的实现代码，大家可以看下。
3.6、SVM的应用
或许我们已经听到过，SVM在很多诸如文本分类，图像分类，生物序列分析和生物数据挖掘，手写字符识别等领域有很多的应用，但或许你并没强烈的意识到，SVM可以成功应用的领域远远超出现在已经在开发应用了的领域。
3.6.1、文本分类
一个文本分类系统不仅是一个自然语言处理系统，也是一个典型的模式识别系统，系统的输入是需要进行分类处理的文本，系统的输出则是与文本关联的类别。由于篇幅所限，其它更具体内容本文将不再详述。
OK，本节虽取标题为证明SVM，但聪明的读者们想必早已看出，其实本部分并无多少证明部分（特此致歉），怎么办呢？可以参阅《支持向量机导论》一书，此书精简而有趣。本节完。
读者评论
本文发表后，微博http://weibo.com/julyweibo上的很多朋友给了不少意见，以下是节选的一些精彩评论：
1. “压力”陡增的评论→//@藏了个锋：我是看着July大神的博文长大的啊//@zlkysl：就是看了最后那一篇才决定自己的研究方向为SVM的。--http://weibo.com/1580904460/zraWk0u6u?mod=weibotime.
2. @张金辉：“SVM的三重境界，不得不转的一篇。其实Coursera的课堂上Andrew Ng讲过支持向量机，但显然他没有把这作为重点，加上Ng讲支持向量机的方法我一时半会难以完全消化，所以听的也是一知半解。真正开始了解支持向量机就是看的这篇“三重境界”，之后才对这个算法有了大概的概念，以至如何去使用，再到其中的原理为何，再到支持向量机的证明等。总之，这篇文章开启了我长达数月的研究支持向量机阶段，直到今日。”--http://zhan.renren.com/profile/249335584?from=template#!//tag/三重境界。
3. @孤独之守望者："最后，推出svm的cost function 是hingeloss，然后对比其他的方法的cost function，说明其实他们的目标函数很像，那么问题是svm为什么这么popular呢？您可以再加些VC dimension跟一些error bound的数学，点一下，提供一个思路和方向"。--http://weibo.com/1580904460/AiohoyDwq?mod=weibotime。
4. @夏粉_百度：“在面试时，考察SVM可考察机器学习各方面能力：目标函数,优化过程,并行方法，算法收敛性,样本复杂度，适用场景,调参经验，不过个人认为考察boosting和LR也还不错啊。此外，随着统计机器学习不断进步，SVM只被当成使用了一个替代01损失hinge研究，更通用的方法被提出，损失函数研究替代损失与贝叶斯损失关系，算法稳定性研究替代损失与推广性能关系,凸优化研究如何求解凸目标函数，SVM,boosting等算法只是这些通用方法的一个具体组建而已。”
5. @居里猴姐：关于SVM损失函数的问题，可以看看张潼老师的这篇《Statistical behavior and consistency of classification methods basedon convex risk minimization》。各种算法中常用的损失函数基本都具有fisher一致性，优化这些损失函数得到的分类器可以看作是后验概率的“代理”。此外，张潼老师还有另外一篇论文《Statistical analysis of some multi-category large marginclassification methods》，在多分类情况下margin loss的分析，这两篇对Boosting和SVM使用的损失函数分析的很透彻。
6. @夏粉_百度：SVM用了hinge损失，hinge损失不可导，不如其它替代损失方便优化并且转换概率麻烦。核函数也不太用，现在是大数据时代，样本非常大，无法想象一个n^2的核矩阵如何存储和计算。 而且，现在现在非线性一般靠深度学习了。//@Copper_PKU:请教svm在工业界的应用典型的有哪些？工业界如何选取核函数，经验的方法？svm的训练过程如何优化？
7. @Copper_PKU：July的svm tutorial 我个人觉得还可以加入和修改如下部分：(1) 对于支持向量解释，可以结合图和拉格朗日参数来表达，松弛中sv没有写出来. (2) SMO算法部分，加入Joachims论文中提到的算法，以及SMO算法选取workset的方法，包括SMO算法的收敛判断，还有之前共轭梯度求解方法，虽然是较早的算法，但是对于理解SMO算法有很好的效果。模型的优化和求解都是迭代的过程，加入历史算法增强立体感。-- http://weibo.com/1580904460/Akw6dl3Yk#_rnd1385474436177。
8. //@廖临川: 之所以sgd对大训练集的效果更好，1.因为SGD优化每次迭代使用样本子集，比使用训练全集（尤其是百万数量级）要快得多；2.如果目标函数是凸的或者伪凸的，SGD几乎必然可以收敛到全局最优；否则，则收敛到局部最优；3.SGD一般不需要收敛到全局最优，只要得到足够好的解，就可以立即停止。//@Copper_PKU：sgd的核心思想：是迭代训练，每拿到一个样本就算出基于当前w(t) 的loss function，t代表训练第t次，然后进行下一w（t+1）的更新，w(t+1)=w(t)-(learningrate) * loss function的梯度，这个类比神经网络中bp中的参数训练方法。 sample by sample就是每次仅处理一个样本 而不是一个batch。
9. //@Copper_PKU：从损失函数角度说：primal问题可以理解为正则化项+lossfunction，求解目标是在两个中间取平衡如果强调loss function最小则会overfitting，所以有C参数。 //@研究者July：SVM还真就是在一定限定条件下，即约束条件下求目标函数的最优值问题，同时，为减少误判率，尽量让损失最小。
10. ...
非常享受这种全民大讨论的年代，没有谁一定就对或一定就错，而是各自发表各自的理解见解，真棒！
后记
OK，此文从最初2012年5月开始动笔，到后续不断的修改，创造了三个之最，即所写时间最长，所花心血最大，所改次数最多，因为我的目标是让没有任何机器学习基础的都能看懂此文，所以总是不停的改，不停的改，不想放过任何一个小的细节。再者，引用侯捷的一句话是：天下大作，必作于细。
最后，非常感谢pluskid及诸多朋友们的文章及著作，让我有机会在其基础上总结、深入。有任何问题，敬请广大读者随时不吝批评指正，感谢。
