模式识别-第九章-支持向量机_52202661.ppt

1、Xinggang Lin, Tsinghua University 第九章 支持向量机,1,支持向量机：Support Vector Machine, SVM 简单回顾 3.3 用广义线性识别函数作分类识别（边书P85） 建立输入向量XRn 的一个函数族i(X),i=1,2,N 把输入向量X映射到一个高维特征空间 在该高维空间设计线性分类器（求分类超平面）,9.2 支持向量机（SVM）（边书P296-304）,Xinggang Lin, Tsinghua University 第九章 支持向量机,2,广义线性识别函数举例（边书P86）,高次多项式（2个特征值、2次多项式）,广义线性识别函数 取

2、X的适当的函数族 使原来的非线性函数，具有线性的表达式，例如,设,取 构成一个对于Z的N 维空间,称作广义线性识别函数,Xinggang Lin, Tsinghua University 第九章 支持向量机,3,广义线性识别函数具体例子,线性识别函数不存在,Xinggang Lin, Tsinghua University 第九章 支持向量机,4,广义线性识别函数具体例子（续1）,作平面,分开,Xinggang Lin, Tsinghua University 第九章 支持向量机,5,广义线性识别函数具体例子（续2）,3维空间中平面,改写成2维形式,双曲线,Xinggang Lin, Tsin

3、ghua University 第九章 支持向量机,6,广义线性识别函数作分类识别存在的问题,维数灾难 训练样本数量不足（样本数与空间维数的比值） 训练样本过多时的过训练问题 推广能力差，“经验风险”与“期望风险”不一致 计算复杂性增加快 高维空间处理困难 如何选择函数族，不同函数族结果不同 实际上使用很困难（在支持向量机SVM之前）,Xinggang Lin, Tsinghua University 第九章 支持向量机,7,线性识别函数、扩展特征向量、扩展权向量（边书P84-87） 线性识别函数,设扩展（增广）特征向量（n+1维）,设扩展（增广）权向量（n+1维）,(齐次)线性识别函数,Xi

4、nggang Lin, Tsinghua University 第九章 支持向量机,8,线性识别函数示意图,Xinggang Lin, Tsinghua University 第九章 支持向量机,9,识别函数的几何示意图（边书P84）,d(X)的值正比于点X到识别平面的距离Dx,Xinggang Lin, Tsinghua University 第九章 支持向量机,10,识别函数的几何示意图（续）,Xinggang Lin, Tsinghua University 第九章 支持向量机,11,扩展特征向量和“解区”（边书P92）,线性识别函数,识别界面 ：在X空间过原点的（超）平面,示意图,未规

5、范化,规范化,Xinggang Lin, Tsinghua University 第九章 支持向量机,12,扩展特征向量、权空间、“余量” （边书P93）,Xinggang Lin, Tsinghua University 第九章 支持向量机,13,研究支持向量机的基本思路（边书P296）,数据预处理：用合适的非线性映射()把样本映射到比原来特征空间的维数高得多的映射空间 两类问题的线性可分：如果两类样本可分（特征空间中无任何一点同时属于两个不同类），则一定存在向着高维空间的非线性映射而使样本线性可分 转化成两个基本问题 如何在高维空间寻找最优线性界面 （注：不降维而升维，不仅要找到而且要“最

6、优”） 如何寻找合适的非线性映射函数(),Xinggang Lin, Tsinghua University 第九章 支持向量机,14,高维空间的最优线性界面图示,避开样本可能稀疏造成统计上的困难 两类边界附近的样本：“最麻烦”、也“最重要” 设计识别函数，尽量利用边界样本的分类信息,假定两类线性可分,超平面H1、H2平行H，且过 两类离界面H最近的样本,使“间隔”最大的H称“最优”,Xinggang Lin, Tsinghua University 第九章 支持向量机,15,高维空间的最优线性界面图示（续1）,Xinggang Lin, Tsinghua University 第九章 支持向

7、量机,16,高维空间的最优线性界面图示（续2）,“间隔”(margin)不最大,“间隔”(margin),Xinggang Lin, Tsinghua University 第九章 支持向量机,17,最优线性界面的计算,两类问题的线性识别函数,识别界面,对于总样本数为N的有穷、线性可分的训练样本集，两类之间必定存在间隔，设间隔值为2C，C0。可改写,用二元组表示训练样本及其类别属性，则训练样本集写成,设超平面 将样本集S正确分类，则需设法使相应间隔最大,Xinggang Lin, Tsinghua University 第九章 支持向量机,18,最优线性界面的计算,两式合并，得,此时间隔为,最

8、优化：使间隔最大，可等价于使 最小，即条件极值问题：,在满足 条件下，求下式极小值：,构造Lagrange函数，设i 为待定系数，有,极值条件,Xinggang Lin, Tsinghua University 第九章 支持向量机,19,最优线性界面的计算（续1）,（注意：只含未知量）,给定训练样本集 ，在不等式约束条件下对的二次函数求极值。可用非线性规划中的“二次规划”求得唯一解。由K-T条件，只有支持向量，即满足 条件，才对最优解 W* 起作用,Xinggang Lin, Tsinghua University 第九章 支持向量机,20,或用一个支持向量,最优线性界面的计算（续2）,设用二

9、次规划求得的解为 ，则最优界面的权向量W*的模的平方,运算单纯，只需计算内积,支持向量通常数量很少，空间维数虽高但计算量不大,Xinggang Lin, Tsinghua University 第九章 支持向量机,21,广义最优线性界面,训练样本集中有若干样本线性不可分，可增添松驰项i0,为约束条件, 在求极小之时， C 和i 对“极小”起相反作用，C 值越大，i 作用越小，倾向于有更大的“间隔”，可容忍较大的分类错误。, 应用中， C 值可能有不止一个“最优”值，应通过实验选取。,Xinggang Lin, Tsinghua University 第九章 支持向量机,22,广义最优线性界面（

10、续）,Xinggang Lin, Tsinghua University 第九章 支持向量机,23,支持向量机, 高维空间只涉及内积运算，故只需知道非线性映射的内积运算 即可，只要变换空间中的内积能用原空间的变量直接计算, 只要定义变换后的内积运算，而不必真的进行变换, 根据泛函理论，若核函数 满足Mercer条件（略），即 可对应某个变换空间中的内积。, 改写 为,Xinggang Lin, Tsinghua University 第九章 支持向量机,24,支持向量机示意图,Xinggang Lin, Tsinghua University 第九章 支持向量机,25,支持向量机“推广性”与变换空间维数无关,若一组训练样本能被一个（广义）最优识别界面分开，则对测试样本识别错误率期望值的上界为训练样本中平均的支持向量占总训练样本数的比例，即, 支持向量机的推广性与变换空间的维数无关，只要适当选择 一种内积定义，构造支持向量数相对较少的界面，即可希望 有较小的错误识别率。,Xinggang Lin, Tsinghua University 第九章 支持