支持向量机通俗导论（理解SVM的三层境界）(3)以及参考文献_支持向量机论文出处

第三层、证明SVM

说实话，凡是涉及到要证明的东西.理论，便一般不是怎么好惹的东西。绝大部分时候，看懂一个东西不难，但证明一个东西则需要点数学功底，进一步，证明一个东西也不是特别难，难的是从零开始发明创造这个东西的时候，则显艰难(因为任何时代，大部分人的研究所得都不过是基于前人的研究成果，前人所做的是开创性工作，而这往往是最艰难最有价值的，他们被称为真正的先驱。牛顿也曾说过，他不过是站在巨人的肩上。你，我则更是如此)。

正如陈希孺院士在他的著作《数理统计学简史》的第4章、最小二乘法中所讲：在科研上诸多观念的革新和突破是有着很多的不易的，或许某个定理在某个时期由某个人点破了，现在的我们看来一切都是理所当然，但在一切没有发现之前，可能许许多多的顶级学者毕其功于一役，耗尽一生，努力了几十年最终也是无功而返。

话休絮烦，要证明一个东西先要弄清楚它的根基在哪，即构成它的基础是哪些理论。OK，以下内容基本是上文中未讲到的一些定理的证明，包括其背后的逻辑、来源背景等东西，还是读书笔记。

本部分导述

• 3.1节线性学习器中，主要阐述感知机算法；
• 3.2节非线性学习器中，主要阐述mercer定理；
• 3.3节、损失函数；
• 3.4节、最小二乘法；
• 3.5节、SMO算法；
• 3.6节、简略谈谈SVM的应用；

3.1、线性学习器

3.1.1、感知机算法

3.3、损失函数

在本文1.0节有这么一句话“支持向量机(SVM)是90年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。”但初次看到的读者可能并不了解什么是结构化风险，什么又是经验风险。要了解这两个所谓的“风险”，还得又从监督学习说起。

监督学习实际上就是一个经验风险或者结构风险函数的最优化问题。风险函数度量平均意义下模型预测的好坏，模型每一次预测的好坏用损失函数来度量。它从假设空间F中选择模型f作为决策函数，对于给定的输入X，由f(X)给出相应的输出Y，这个输出的预测值f(X)与真实值Y可能一致也可能不一致，用一个损失函数来度量预测错误的程度。损失函数记为L(Y, f(X))。

常用的损失函数有以下几种（基本引用自《统计学习方法》）：

如此，SVM有第二种理解，即最优化+损失最小，或如@夏粉_百度所说“可从损失函数和优化算法角度看SVM，boosting，LR等算法，可能会有不同收获”。

OK，关于更多统计学习方法的问题，请参看此文。

关于损失函数，如下文读者评论中所述：可以看看张潼的这篇《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 年发表的，基本思想就是认为测量中有误差，所以所有方程的累积误差为

我们求解出导致累积误差最小的参数即可：

勒让德在论文中对最小二乘法的优良性做了几点说明：

•  最小二乘使得误差平方和最小，并在各个方程的误差之间建立了一种平衡，从而防止某一个极端误差取得支配地位
•  计算中只要求偏导后求解线性方程组，计算过程明确便捷
• 最小二乘可以导出算术平均值作为估计值

对于最后一点，从统计学的角度来看是很重要的一个性质。推理如下：假设真值为 , 为n次测量值, 每次测量的误差为，按最小二乘法，误差累积为

求解 使达到最小，正好是算术平均。

由于算术平均是一个历经考验的方法，而以上的推理说明，算术平均是最小二乘的一个特例，所以从另一个角度说明了最小二乘方法的优良性，使我们对最小二乘法更加有信心。

最小二乘法发表之后很快得到了大家的认可接受，并迅速的在数据分析实践中被广泛使用。不过历史上又有人把最小二乘法的发明归功于高斯，这又是怎么一回事呢。高斯在1809年也发表了最小二乘法，并且声称自己已经使用这个方法多年。高斯发明了小行星定位的数学方法，并在数据分析中使用最小二乘方法进行计算，准确的预测了谷神星的位置。

说了这么多，貌似跟本文的主题SVM没啥关系呀，别急，请让我继续阐述。本质上说，最小二乘法即是一种参数估计方法，说到参数估计，咱们得从一元线性模型说起。

3.4.2、最小二乘法的解法

OK，更多请参看陈希孺院士的《数理统计学简史》的第4章、最小二乘法。

3.5、SMO算法

等价于求解：

其中

其中，是常数。

化简下：

而b在满足下述条件：

3.6、SVM的应用

或许我们已经听到过，SVM在很多诸如文本分类，图像分类，生物序列分析和生物数据挖掘，手写字符识别等领域有很多的应用，但或许你并没强烈的意识到，SVM可以成功应用的领域远远超出现在已经在开发应用了的领域。

3.6.1、文本分类

一个文本分类系统不仅是一个自然语言处理系统，也是一个典型的模式识别系统，系统的输入是需要进行分类处理的文本，系统的输出则是与文本关联的类别。由于篇幅所限，其它更具体内容本文将不再详述。

参考文献及推荐阅读

1. 《支持向量机导论》，[美] Nello Cristianini / John Shawe-Taylor 著；
2. 支持向量机导论一书的支持网站：http://www.support-vector.net/；
3. 《数据挖掘导论》，[美] Pang-Ning Tan / Michael Steinbach / Vipin Kumar 著；
4. 《数据挖掘：概念与技术》，(加)Jiawei Han;Micheline Kamber 著；
5. 《数据挖掘中的新方法：支持向量机》，邓乃扬 田英杰 著；
6. 《支持向量机–理论、算法和扩展》，邓乃扬 田英杰 著；
7. 支持向量机系列，pluskid：http://blog.pluskid.org/?page_id=683；
8. http://www.360doc.com/content/07/0716/23/11966_615252.shtml；
9. 数据挖掘十大经典算法初探；
10. 《模式识别支持向量机指南》，C.J.C Burges 著；
11. 《统计学习方法》，李航著；
12. 《统计自然语言处理》，宗成庆编著，第十二章、文本分类；
13. SVM入门系列，Jasper：http://www.blogjava.net/zhenandaci/category/31868.html；
14. 最近邻决策和SVM数字识别的实现和比较，作者不详；
15. 斯坦福大学机器学习课程原始讲义：http://www.cnblogs.com/jerrylead/archive/2012/05/08/2489725.html；
16. 斯坦福机器学习课程笔记：http://www.cnblogs.com/jerrylead/tag/Machine%20Learning/；
17. http://www.cnblogs.com/jerrylead/archive/2011/03/13/1982639.html；
18. SMO算法的数学推导：http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html；
19. 数据挖掘掘中所需的概率论与数理统计知识、上；
20. 关于机器学习方面的文章，可以读读：http://www.cnblogs.com/vivounicorn/category/289453.html；
21. 数学系教材推荐：http://blog.sina.com.cn/s/blog_5e638d950100dswh.html；
22. 《神经网络与机器学习(原书第三版)》，[加] Simon Haykin 著；
23. 正态分布的前世今生：http://t.cn/zlH3Ygc；
24. 《数理统计学简史》，陈希孺院士著；
25. 《最优化理论与算法(第2版)》，陈宝林编著；
26. A Gentle Introduction to Support Vector Machines in Biomedicine：http://www.nyuinformatics.org/downloads/supplements/SVM_Tutorial_2010/Final_WB.pdf，此PPT很赞，除了对引入拉格朗日对偶变量后的凸二次规划问题的深入度不够之外，其它都挺好，配图很精彩，本文有几张图便引自此PPT中；
27. 来自卡内基梅隆大学carnegie mellon university(CMU)的讲解SVM的PPT：http://www.autonlab.org/tutorials/svm15.pdf；
28. 发明libsvm的台湾林智仁教授06年的机器学习讲义SVM：http://wenku.baidu.com/link?url=PWTGMYNb4HGUrUQUZwTH2B4r8pIMgLMiWIK1ymVORrds_11VOkHwp-JWab7IALDiors64JW_6mD93dtuWHwFWxsAk6p0rzchR8Qh5_4jWHC；
29. http://staff.ustc.edu.cn/~ketang/PPT/PRLec5.pdf；
30. Introduction to Support Vector Machines (SVM)，By Debprakash Patnai M.E (SSA)，https://www.google.com.hk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CCwQFjAA&url=http%3a%2f%2fwww%2epws%2estu%2eedu%2etw%2fccfang%2findex%2efiles%2fAI%2fAI%26ML-Support%2520Vector%2520Machine-1%2eppt&ei=JRR6UqT5C-iyiQfWyIDgCg&usg=AFQjCNGw1fTbpH4ltQjjmx1d25ZqbCN9nA；
31. 多人推荐过的libsvm：http://www.csie.ntu.edu.tw/~cjlin/libsvm/；
32. 《machine learning in action》，中文版为《机器学习实战》；
33. SMO算法的提出：Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines：http://research.microsoft.com/en-us/um/people/jplatt/smoTR.pdf；
34. 《统计学习理论的本质》，[美] Vladimir N. Vapnik著，非常晦涩，不做过多推荐；
35. 张兆翔，机器学习第五讲之支持向量机http://irip.buaa.edu.cn/~zxzhang/courses/MachineLearning/5.pdf；
36. VC维的理论解释：http://www.svms.org/vc-dimension/，中文VC维解释http://xiaoxia001.iteye.com/blog/1163338；
37. 来自NEC Labs America的Jason Weston关于SVM的讲义http://www.cs.columbia.edu/~kathy/cs4701/documents/jason_svm_tutorial.pdf；
38. 来自MIT的SVM讲义：http://www.mit.edu/~9.520/spring11/slides/class06-svm.pdf；
39. PAC问题：http://www.cs.huji.ac.il/~shashua/papers/class11-PAC2.pdf；
40. 百度张潼老师的两篇论文：《Statistical behavior and consistency of classification methods based on convex risk minimization》http://home.olemiss.edu/~xdang/676/Consistency_of_Classification_Convex_Risk_Minimization.pdf，《Statistical analysis of some multi-category large margin classification methods》；
41. http://jacoxu.com/?p=39；
42. 《矩阵分析与应用》，清华张贤达著；
43. SMO算法的实现：http://blog.csdn.net/techq/article/details/6171688；
44. 常见面试之机器学习算法思想简单梳理：http://www.cnblogs.com/tornadomeet/p/3395593.html；
45. 矩阵的wikipedia页面：http://zh.wikipedia.org/wiki/%E7%9F%A9%E9%98%B5；
46. 最小二乘法及其实现：http://blog.csdn.net/qll125596718/article/details/8248249；
47. 统计学习方法概论：http://blog.csdn.net/qll125596718/article/details/8351337；
48. http://www.csdn.net/article/2012-12-28/2813275-Support-Vector-Machine；
49. A Tutorial on Support Vector Regression：http://alex.smola.org/papers/2003/SmoSch03b.pdf；SVR简明版：http://www.cmlab.csie.ntu.edu.tw/~cyy/learning/tutorials/SVR.pdf。
50. SVM Org：http://www.support-vector-machines.org/；
51. R. Collobert. Large Scale Machine Learning. Université Paris VI phd thesis. 2004：http://ronan.collobert.com/pub/matos/2004_phdthesis_lip6.pdf；
52. Making Large-Scale SVM Learning Practical：http://www.cs.cornell.edu/people/tj/publications/joachims_99a.pdf；
53. 文本分类与SVM：http://blog.csdn.net/zhzhl202/article/details/8197109；
54. Working Set Selection Using Second Order Information
    for Training Support Vector Machines：http://www.csie.ntu.edu.tw/~cjlin/papers/quadworkset.pdf；
55. SVM Optimization: Inverse Dependence on Training Set Size：http://icml2008.cs.helsinki.fi/papers/266.pdf；
56. Large-Scale Support Vector Machines: Algorithms and Theory：http://cseweb.ucsd.edu/~akmenon/ResearchExam.pdf；
57. 凸优化的概念：http://cs229.stanford.edu/section/cs229-cvxopt.pdf；
58. 《凸优化》，作者: Stephen Boyd / Lieven Vandenberghe，原作名: Convex Optimization；
59. Large-scale Non-linear Classification: Algorithms and Evaluations，Zhuang Wang，讲了很多SVM算法的新进展：http://ijcai13.org/files/tutorial_slides/te2.pdf；
60. 基于SMO算法实现SVM：http://www.cs.iastate.edu/~honavar/smo-svm.pdf；
61. copper推荐的一些SVM相关的论文（当然，其中不少论文在上面的条目中都已经提到）：http://c.blog.sina.com.cn/profile.php?blogid=68d0b92d89000h35。