《模式识别-第九章-支持向量机_52202661.ppt》由会员分享，可在线阅读，更多相关《模式识别-第九章-支持向量机_52202661.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2010/3n支持向量机：支持向量机：Support Vector Machine,SVMn简单回顾简单回顾u3.3 用广义线性识别函数作分类识别用广义线性识别函数作分类识别（边书（边书P85）u建立输入向量建立输入向量XRn 的一个函数族的一个函数族i(X),i=1,2,Nu把输入向量把输入向量X映射到一个高维特征空间映射到一个高维特征空间u在该高维空间设计线性分类器（求分类超平面）在该高维空间设计线性分类器（求分类超平面）9.2 支持向量机（支持向量机（SVM）（边书边书P296-304）1Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3广义
2、线性识别函数举例广义线性识别函数举例（边书（边书P86）n高次多项式（高次多项式（2个特征值、个特征值、2次多项式）次多项式）n广义线性识别函数广义线性识别函数 取取X的适当的函数族的适当的函数族 使原来的非线性函数，具有线性的表达式，例如使原来的非线性函数，具有线性的表达式，例如设设取取 构成一个对于构成一个对于Z的的N 维空间维空间 称作广义线性识别函数称作广义线性识别函数2Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3广义线性识别函数具体例子广义线性识别函数具体例子线性识别函数不存在线性识别函数不存在把把2维空间维空间 变为变为3维空间维
3、空间3Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3广义线性识别函数具体例子（续广义线性识别函数具体例子（续1）作平面作平面分开分开4Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3广义线性识别函数具体例子（续广义线性识别函数具体例子（续2）3维空间中平面维空间中平面改写成改写成2维形式维形式用用 来使维数上升，来使维数上升，对应于原来空间中的高次对应于原来空间中的高次曲线（面）曲线（面）常采用各种正交函数族常采用各种正交函数族双曲线双曲线5Xinggang Lin,Tsinghua Univer
4、sity 第九章 支持向量机2010/3广义线性识别函数作分类识别存在的问题广义线性识别函数作分类识别存在的问题u维数灾难维数灾难u训练样本数量不足（样本数与空间维数的比值）训练样本数量不足（样本数与空间维数的比值）u训练样本过多时的过训练问题训练样本过多时的过训练问题推广能力差，推广能力差，“经验风险经验风险”与与“期望风险期望风险”不一不一致致u计算复杂性增加快计算复杂性增加快u高维空间处理困难高维空间处理困难u如何选择函数族，不同函数族结果不同如何选择函数族，不同函数族结果不同实际上使用很困难（在支持向量机实际上使用很困难（在支持向量机SVM之前）之前）6Xinggang Lin,Tsi
5、nghua University 第九章 支持向量机2010/3n线性识别函数、扩展特征向量、扩展权向量线性识别函数、扩展特征向量、扩展权向量（边书（边书P84-87）u线性识别函数线性识别函数设扩展（增广）特征向量（设扩展（增广）特征向量（n+1维）维）设扩展（增广）权向量（设扩展（增广）权向量（n+1维）维）(齐次齐次)线性识别函数线性识别函数7Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3线性识别函数示意图线性识别函数示意图8Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3n识别函数的几何示
6、意图识别函数的几何示意图（边书（边书P84）原点原点PXd(X)的值正比于点的值正比于点X到到识别平面的距离识别平面的距离Dx9Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3识别函数的几何示意图（续）识别函数的几何示意图（续）10Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3扩展特征向量和扩展特征向量和“解区解区”（边书（边书P92）线性识别函数线性识别函数识别界面识别界面：在：在X空间过原点的（超）平面空间过原点的（超）平面示意图示意图未规范化未规范化规范化规范化11Xinggang Lin,
7、Tsinghua University 第九章 支持向量机2010/3扩展特征向量、权空间、扩展特征向量、权空间、“余量余量”（边书（边书P93）12Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3研究支持向量机的基本思路研究支持向量机的基本思路（边书（边书P296）u数据预处理：用合适的非线性映射数据预处理：用合适的非线性映射()把样本映射把样本映射到比原来特征空间的维数高得多的映射空间到比原来特征空间的维数高得多的映射空间u两类问题的线性可分：如果两类样本可分（特征空两类问题的线性可分：如果两类样本可分（特征空间中无任何一点同时属于两个不同类
8、），则一定存间中无任何一点同时属于两个不同类），则一定存在向着高维空间的非线性映射而使样本线性可分在向着高维空间的非线性映射而使样本线性可分u转化成两个基本问题转化成两个基本问题u如何在高维空间寻找最优线性界面如何在高维空间寻找最优线性界面 （注：不降维而升维，不仅要找到而且要（注：不降维而升维，不仅要找到而且要“最优最优”）u如何寻找合适的非线性映射函数如何寻找合适的非线性映射函数()13Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3高维空间的最优线性界面图示高维空间的最优线性界面图示n避开样本可能稀疏造成统计上的困难避开样本可能稀疏造成统计
9、上的困难u两类边界附近的样本：两类边界附近的样本：“最麻烦最麻烦”、也、也“最重要最重要”设计识别函数，尽量利用边界样本的分类信息设计识别函数，尽量利用边界样本的分类信息假定两类线性可分假定两类线性可分超平面超平面H无错误分开两类无错误分开两类超平面超平面H1、H2平行平行H，且过且过 两类离界面两类离界面H最近的样本最近的样本 H1、H2之间距离称之间距离称“间隔间隔”(margin)margin使使“间隔间隔”最大的最大的H称称“最最优优”离界面离界面H最近的样本称支持最近的样本称支持 向量向量(Support Vector)14Xinggang Lin,Tsinghua Universi
10、ty 第九章 支持向量机2010/3高维空间的最优线性界面图示（续高维空间的最优线性界面图示（续1）15Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3高维空间的最优线性界面图示（续高维空间的最优线性界面图示（续2）“间隔间隔”(margin)不最大不最大“间隔间隔”(margin)16Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3最优线性界面的计算最优线性界面的计算两类问题的线性识别函数两类问题的线性识别函数判别规则判别规则识别界面识别界面对于总样本数为对于总样本数为N的有穷、线性可分的训练样本
11、集，两类之间必的有穷、线性可分的训练样本集，两类之间必定存在间隔，设间隔值为定存在间隔，设间隔值为2C，C0。可改写可改写判别规则判别规则用二元组表示训练样本及其类别属性，则训练样本集写成用二元组表示训练样本及其类别属性，则训练样本集写成设超平面设超平面 将样本集将样本集S正确分类，则需设法使相应间隔正确分类，则需设法使相应间隔最大最大17Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3最优线性界面的计算最优线性界面的计算改变权向量的模，使判别规则写成归一化形式改变权向量的模，使判别规则写成归一化形式两式合并，得两式合并，得此时间隔为此时间隔为最
12、优化：使间隔最大，可等价于使最优化：使间隔最大，可等价于使 最小，即条件极值问题：最小，即条件极值问题：在满足在满足 条件下，求下式极小值：条件下，求下式极小值：构造构造Lagrange函数，设函数，设i 为待定系数，有为待定系数，有极值条件极值条件18Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3利用利用Lagrange优化方法，转化为其对偶问题，即约束条件为优化方法，转化为其对偶问题，即约束条件为对对i 求解如下函数的极大值求解如下函数的极大值最优线性界面的计算（续最优线性界面的计算（续1）最优线性界面，其解的最优线性界面，其解的 必须满足
13、必须满足且且（最优界面权向量（最优界面权向量W*为训练为训练 样本集样本集S中样本中样本Xi 的线性组合）的线性组合）即在即在W*的展开中，只有支持向量才具有非零系数的展开中，只有支持向量才具有非零系数 约束条件约束条件 的等号，只对支持向量成立，的等号，只对支持向量成立，（注意：只含未知量（注意：只含未知量）设支持向量集为设支持向量集为Ssp，有有（库恩（库恩-塔克条件，非线性规划塔克条件，非线性规划）给定训练样本集给定训练样本集 ，在不等式约束条件下对，在不等式约束条件下对的二次函数求极值。可的二次函数求极值。可用非线性规划中的用非线性规划中的“二次规划二次规划”求得唯一解。由求得唯一解。
14、由K-T条件，只有支持向量，即条件，只有支持向量，即满足满足 条件，才对最优解条件，才对最优解 W*起作用起作用19Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3或或用一个支持向量用一个支持向量最优线性界面的计算（续最优线性界面的计算（续2）设用二次规划求得的解为设用二次规划求得的解为 ，则最优界面的权向，则最优界面的权向量量W*的的模的平方模的平方设设 ，则，则阈值阈值b*可由两类中任意一对支持向量求得，即可由两类中任意一对支持向量求得，即最优识别函数最优识别函数sgn为符号函数为符号函数注意：注意：界面权向量界面权向量W*由支持向量的线性组
15、合表示，可不求出界面方程由支持向量的线性组合表示，可不求出界面方程运算单纯，只需计算内积运算单纯，只需计算内积支持向量通常数量很少，空间维数虽高但计算量不大支持向量通常数量很少，空间维数虽高但计算量不大20Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3广义最优线性界面广义最优线性界面n训练样本集中有若干样本线性不可分，可增添松驰项训练样本集中有若干样本线性不可分，可增添松驰项i0引入常数引入常数C 0，用于控制对错分样本的惩罚程度，目标函数改为用于控制对错分样本的惩罚程度，目标函数改为求极小求极小为约束条件为约束条件 在求极小之时，在求极小之时
16、，C 和和i 对对“极小极小”起相反作用，起相反作用，C 值越大，值越大，i 作用越小，倾向于有更大的作用越小，倾向于有更大的“间隔间隔”，可容忍较大的分类错误。，可容忍较大的分类错误。应用中，应用中，C 值可能有不止一个值可能有不止一个“最优最优”值，应通过实验选取。值，应通过实验选取。只是条件只是条件 改为更严格的改为更严格的求解过程用求解过程用“二次规划二次规划”（quadratic programming）与前述相同，与前述相同，21Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3广义最优线性界面（续）广义最优线性界面（续）22Xingg
17、ang Lin,Tsinghua University 第九章 支持向量机2010/3支持向量机支持向量机 高维空间只涉及内积运算，故只需知道非线性映射的内积运算高维空间只涉及内积运算，故只需知道非线性映射的内积运算 即可，只要变换空间中的内积能用原空间的变量直接计算即可，只要变换空间中的内积能用原空间的变量直接计算 只要定义变换后的内积运算，而不必真的进行变换只要定义变换后的内积运算，而不必真的进行变换 根据泛函理论，若核函数根据泛函理论，若核函数 满足满足Mercer条件（略），即条件（略），即 可对应某个变换空间中的内积。可对应某个变换空间中的内积。改写改写 为为 识别函数为识别函数为此
18、即为支持向量机此即为支持向量机23Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3支持向量机示意图支持向量机示意图24Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3支持向量机支持向量机“推广性推广性”与变换空间维数无与变换空间维数无关关n若一组训练样本能被一个（广义）最优识别界面分开，则对若一组训练样本能被一个（广义）最优识别界面分开，则对测试样本识别错误率期望值的上界为训练样本中平均的支持测试样本识别错误率期望值的上界为训练样本中平均的支持向量占总训练样本数的比例，即向量占总训练样本数的比例，即
19、 支持向量机的推广性与变换空间的维数无关，只要适当选择支持向量机的推广性与变换空间的维数无关，只要适当选择 一种内积定义，构造支持向量数相对较少的界面，即可希望一种内积定义，构造支持向量数相对较少的界面，即可希望 有较小的错误识别率。有较小的错误识别率。25Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3可用的内积核函数可用的内积核函数K(Xi,X)多项式形式多项式形式 高斯径向基函数高斯径向基函数 指数径向基函数指数径向基函数 双曲正切双曲正切S型函数型函数 线性核函数线性核函数有实验表明（边书有实验表明（边书P303表表13-2），支持向量机对不同方法不很），支持向量机对不同方法不很敏感，不同的方法得到的性能相似。敏感，不同的方法得到的性能相似。26Xinggang Lin,Tsinghua University 第九章 支持向量机2010/3存在问题举例存在问题举例27Xinggang Lin,Tsinghua University 第九章 支持向量机