《统计学习理论与SVM（支持向量机）》由会员分享，可在线阅读，更多相关《统计学习理论与SVM（支持向量机）（68页珍藏版）》请在金锄头文库上搜索。
1、课件人工智能引论浙江大学研究生第八章 统计学习理论与SVM (Chapter8 SLT 在每个子集中寻找最小经验风险,在子集 间折衷考虑经验风险和置信范围,取得实际风险的 最小。这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。结构风险最小化（续1）结构风险最小化（续2）n实现SRM原则的两种思路在每个子集中求最小经验风险,然后选择使最小 经验风险和置信范围之和最小的子集。设计函数集的某种结构使每个子集中都能取得 最小的经验风险,然后只需选择适当的子集使置 信范围最小,则这个子集中使经验风险最小的函 数就是最优函数。支持向量机方法实际上就是
2、这种思路的实现。8.6 支持向量机概述n支持向量机概述n支持向量机理论n支持向量机n核函数n支持向量机实现8.6.1 支持向量机概述n1963年，Vapnik在解决模式识别问题时提出了支 持向量方法,这种方法从训练集中选择一组特征子 集,使得对特征子集的划分等价于对整个数据集的 划分,这组特征子集就被称为支持向量(SV)。n1971年，Kimeldorf提出使用线性不等约束重新构 造SV的核空间,解决了一部分线性不可分问题。n1990年，Grace,Boser和Vapnik等人开始对SVM进 行研究。n1995年，Vapnik正式提出统计学习理论。8.6.2 支持向量机理论nSVM从线性可分情
3、况下的最优分类面发展而来。n最优分类面就是要求分类线不但能将两类正确分 开(训练错误率为0),且使分类间隔最大。nSVM考虑寻找一个满足分类要求的超平面,并且使 训练集中的点距离分类面尽可能的远,也就是寻 找一个分类面使它两侧的空白区域(margin)最大 。n过两类样本中离分类面最近的点且平行于最优分 类面的超平面上H1,H2的训练样本就叫做支持向 量。支持向量机理论（续1）广义最优分类面广义最优分类面（续1）n假定训练数据n可以被一个超平面分开n我们进行正归化n此时分类间隔等于n使最大间隔最大等价于使 最小广义最优分类面（续2）n最优分类面问题可以表示成约束优化问题MinimizeSubj
4、ect ton定义Lagrange函数广义最优分类面（续3）nLagrange函数一个简单的例子：x1 =(0, 0), y1 = +1x2 =(1, 0), y2 = +1x3 =(2, 0), y3 = -1x4 =(0, 2), y4 = -1可调用Matlab中的二次规划程序，求得1, 2, 3, 4的值，进而求得w和b的值。 8.6.3 支持向量机n很多情况下，训练数据集是线性不可分的 ，Vapnik等人提出了用广义分类面（松弛 子）来解决这一问题。n非线性问题通过非线性变换将它转化 为某个高维空间中的线性问题，在这个高 维空间中寻找最优分类面。高维空间中的最优分类面n分类函数只涉及
5、到训练样本之间的内积运 算(xixj) ,因此,在高维空间中只需进行内 积运算,这种内积运算可通过定义在原空 间中的函数来实现, 甚至不必知道变换的 形式。nSLT指出,根据Hibert-Schmidt原理,只要一 种运算满足Mercer条件,就可以作为内积 使用。Mercer条件支持向量机n在最优分类面中采用适当的内积函数就可 以实现某一非线性变换后的线性分类,而计 算复杂度却没有增加。支持向量机8.6.4 核函数nSVM中不同的内积核函数将形成不同的算法,主 要的核函数有三类：n多项式核函数n径向基函数nS形函数8.6.5 支持向量机实现SVMlight - 2.private:/usr/
6、local/binsvm_learn, svm_classifybsvm - 2.private:/usr/local/binsvm-train, svm-classify, svm-scalelibsvm - 2.private:/usr/local/binsvm-train, svm-predict, svm-scale, svm-toymySVMMATLAB svm toolbox支持向量机实现8.7 研究现状n应用研究n支持向量机研究n支持向量机算法研究8.7.1 应用研究nSVM的应用主要于模式识别领域n贝尔实验室对美国邮政手写数字库进行的实验分类器错误率人工表现2.5%决策树C4.
7、516.2%最好的两层神经网络5.9%SVM4.0%SVM与神经网络（NN）的对比SVM的理论基础比NN更坚实，更像一门严谨 的“科学”（三要素：问题的表示、问题的解决、证明）SVM 严格的数学推理NN 强烈依赖于工程技巧推广能力取决于“经验风险值”和“置信范围值” ，NN不能控制两者中的任何一个。NN设计者用高超的工程技巧弥补了数学上的 缺陷设计特殊的结构，利用启发式算法， 有时能得到出人意料的好结果。“我们必须从一开始就澄清一个观点，就是如果某 事不是科学，它并不一定不好。比如说，爱情就不 是科学。因此，如果我们说某事不是科学，并不是 说它有什么不对，而只是说它不是科学。” by R. F
8、eynmanfrom The Feynman Lectures on Physics, Addison-Wesley同理，与SVM相比，NN不像一门科学，更 像一门工程技巧，但并不意味着它就一定不 好！主要应用领域n手写数字识别n语音识别n人脸识别n文本分类8.7.2 支持向量机研究n如何针对不同的问题选择不同的核函数仍 然是一个悬而未决的问题。n标准的SVM对噪声是不具有鲁棒性的,如何 选择合适的目标函数以实现鲁棒性是至关 重要的。8.7.3 支持向量机算法研究n支持向量机的本质是解一个二次规划问题, 虽然有一些经典（如对偶方法、内点算法 等）,但当训练集规模很大时,这些算法面 临着维数灾难
9、问题。为此,人们提出了许多 针对大规模数据集的SVM训练算法。支持向量机算法研究（续1）n思路1：分解子问题块算法SMO算法(Sequential Minimal Optimization)n思路2：序列优化n思路3：近邻SVM支持向量机算法研究（续2）n训练SVM的绝大多数算法都是针对分类问题 ,只有一小部分算法考虑了回归函数的估计 问题。n提高算法效率、降低复杂度。支持向量机算法研究（续3）nSVM增量学习算法的研究n超球面SVM算法研究One-class SVM算法nSVM多值分类器算法One-against-the-rest（一对多方法）One-against-one（一对一方法）Mu
10、lti-class Objective Functions（多类SVM）Decision Directed Acyclic Graph, DDAGSVM Decision Tree超球面SVM多值分类器总结nSVM在模式识别、回归函数估计、预测等 大量应用中取得了良好的效果nSVM存在两个主要问题：二次规划的训练速度核函数的选择n前途是光明的，道路是曲折的。课后编程实现题目（二选一）：设计并实现一个简单的用于文本分类的 SVM。设计并实现一个简单的基于SVM的“新闻 分离器”，主要用于对浙大BBS“缥缈水云 间”中news版上的新闻进行分类。主要参考文献：nA tutorial on supp
11、ort vector machines for pattern recognition. Data Mining and Knowledge Discovery,1998,2(2)nVapnik V N. The Nature of Statistical Learning Theory, NY: Springer-Verlag, 1995（中译本：张 学工译.统计学习理论的本质.清华大学出版社 ,2000）【说明】：该书附带介绍了很多科学研究的基本原则 ，很有启发、借鉴意义。nIntroduction to Support Vector Machine.nVapnik V N. 著，张学工译
12、. 统计学习理论. 人民邮电出版社.n张学工. 关于统计学习理论与支持向量机. 自动化学报, 2000年第1期.n史朝辉. SVM算法研究及在HRRP分类中的 应用. 空军工程大学硕士学位论文, 2005.主要参考文献（续）：THANKS FOR YOUR PRESENCE!“A righteous man may have many troubles, but the LORD delivers him from them all; he protects all his bones, not one of them will be broken.”from Psalms 34:19-20 NIV
