浙江大学SVM(支持向量机)讲述

课件人工智能引论浙江大学研究生 徐从富(Congfu Xu) PhD, Associate Professor Email: xucongfu Institute of Artificial Intelligence, College of Computer Science, Zhejiang University, Hangzhou 310027, P.R. China September 11, 2003第一稿 Oct. 16, 2006第三次修改稿 第八章 统计学习理论与SVM (Chapter8 SLT 在每个子集中寻找最小经验风险,在子集 间折衷考虑经验风险和置信范围,取得实际风险的 最小。这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。 结构风险最小化（续1） 结构风险最小化（续2） n实现SRM原则的两种思路 ¨在每个子集中求最小经验风险,然后选择使最小 经验风险和置信范围之和最小的子集。 ¨设计函数集的某种结构使每个子集中都能取得 最小的经验风险,然后只需选择适当的子集使置 信范围最小,则这个子集中使经验风险最小的函 数就是最优函数。支持向量机方法实际上就是 这种思路的实现。 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从线性可分情况下的最优分类面发展而来。 n最优分类面就是要求分类线不但能将两类正确分 开(训练错误率为0),且使分类间隔最大。 nSVM考虑寻找一个满足分类要求的超平面,并且使 训练集中的点距离分类面尽可能的远,也就是寻 找一个分类面使它两侧的空白区域(margin)最大 。 n过两类样本中离分类面最近的点且平行于最优分 类面的超平面上H1,H2的训练样本就叫做支持向 量。 支持向量机理论（续1） 广义最优分类面 广义最优分类面（续1） n假定训练数据 n可以被一个超平面分开 n我们进行正归化 n此时分类间隔等于 n使最大间隔最大等价于使 最小 广义最优分类面（续2） n最优分类面问题可以表示成约束优化问题 ¨Minimize ¨Subject to n定义Lagrange函数 广义最优分类面（续3） nLagrange函数 一个简单的例子： x1 =(0, 0), y1 = +1 x2 =(1, 0), y2 = +1 x3 =(2, 0), y3 = -1 x4 =(0, 2), y4 = -1 可调用Matlab中的二次规划程序，求得1, 2, 3, 4的值，进而求得w和b的值。 8.6.3 支持向量机 n很多情况下，训练数据集是线性不可分的 ，Vapnik等人提出了用广义分类面（松弛 子）来解决这一问题。 n非线性问题通过非线性变换将它转化 为某个高维空间中的线性问题，在这个高 维空间中寻找最优分类面。 高维空间中的最优分类面 n分类函数只涉及到训练样本之间的内积运 算(xi·xj) ,因此,在高维空间中只需进行内 积运算,这种内积运算可通过定义在原空 间中的函数来实现, 甚至不必知道变换的 形式。 nSLT指出,根据Hibert-Schmidt原理,只要一 种运算满足Mercer条件,就可以作为内积 使用。 Mercer条件 支持向量机 n在最优分类面中采用适当的内积函数就可 以实现某一非线性变换后的线性分类,而计 算复杂度却没有增加。 支持向量机 8.6.4 核函数 nSVM中不同的内积核函数将形成不同的算法,主 要的核函数有三类： n多项式核函数 n径向基函数 nS形函数 8.6.5 支持向量机实现 ØSVMlight - 2.private:/usr/local/bin üsvm_learn, svm_classify Øbsvm - 2.private:/usr/local/bin üsvm-train, svm-classify, svm-scale Ølibsvm - 2.private:/usr/local/bin üsvm-train, svm-predict, svm-scale, svm-toy ØmySVM ØMATLAB svm toolbox 支持向量机实现 8.7 研究现状 n应用研究 n支持向量机研究 n支持向量机算法研究 8.7.1 应用研究 nSVM的应用主要于模式识别领域 n贝尔实验室对美国邮政手写数字库进行的实验 分类器错误率 人工表现2.5% 决策树C4.516.2% 最好的两层神经网络5.9% SVM4.0% SVM与神经网络（NN）的对比 ¨SVM的理论基础比NN更坚实，更像一门严谨 的“科学”（三要素：问题的表示、问题的解决、证明） ¨SVM 严格的数学推理 ¨NN 强烈依赖于工程技巧 ¨推广能力取决于“经验风险值”和“置信范围值” ，NN不能控制两者中的任何一个。 ¨NN设计者用高超的工程技巧弥补了数学上的 缺陷设计特殊的结构，利用启发式算法， 有时能得到出人意料的好结果。 “我们必须从一开始就澄清一个观点，就是如果某 事不是科学，它并不一定不好。比如说，爱情就不 是科学。因此，如果我们说某事不是科学，并不是 说它有什么不对，而只是说它不是科学。” by R. Feynman from The Feynman Lectures on Physics, Addison-Wesley 同理，与SVM相比，NN不像一门科学，更 像一门工程技巧，但并不意味着它就一定不 好！ 主要应用领域 n手写数字识别 n语音识别 n人脸识别 n文本分类 8.7.2 支持向量机研究 n如何针对不同的问题选择不同的核函数仍 然是一个悬而未决的问题。 n标准的SVM对噪声是不具有鲁棒性的,如何 选择合适的目标函数以实现鲁棒性是至关 重要的。 8.7.3 支持向量机算法研究 n支持向量机的本质是解一个二次规划问题, 虽然有一些经典（如对偶方法、内点算法 等）,但当训练集规模很大时,这些算法面 临着维数灾难问题。为此,人们提出了许多 针对大规模数据集的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（一对一方法） ¨Multi-class Objective Functions（多类SVM） ¨Decision Directed Acyclic Graph, DDAG ¨SVM Decision Tree ¨超球面SVM多值分类器 ¨ 总结 nSVM在模式识别、回归函数估计、预测等 大量应用中取得了良好的效果 nSVM存在两个主要问题： ¨二次规划的训练速度 ¨核函数的选择 n前途是光明的，道路是曲折的。 课后编程实现题目（二选一）： ¨设计并实现一个简单的用于文本分类的 SVM。 ¨设计并实现一个简单的基于SVM的“新闻 分离器”，主要用于对浙大BBS“缥缈水云 间”中news版上的新闻进行分类。 主要参考文献： nA tutorial on support 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. 著，张学工译. 统计学习理论. 人民邮电出版社. 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