《模式识别第十三章SV.ppt》由会员分享，可在线阅读，更多相关《模式识别第十三章SV.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第十三章第十三章 支持向量机简介支持向量机简介（Support Vector MachineSupport Vector Machine：SVMSVM）一般模式识别方法的一般模式识别方法的问题问题问题问题1 1）传统统计方法传统统计方法基于经验风险最小化基于经验风险最小化，经验风险最小，经验风险最小不等于不等于期望风险最小，期望风险最小，不能保证不能保证分类器的分类器的推广能力推广能力。经验风险只有经验风险只有在样本数无穷大趋近于期望风在样本数无穷大趋近于期望风险，险，即在即在有限样本有限样本情况下，情况下，经验风险最小并不经验风险最小并不意味着期望风险最小。意味着期望风险最小。需要需要已知样
2、本的分布形式已知样本的分布形式2 2）经验非线性方法）经验非线性方法如人工神经网络（如人工神经网络（ANNANN）利用已知样本利用已知样本建立非线性模型。建立非线性模型。缺点：缺乏一种统一的缺点：缺乏一种统一的数学理论数学理论统计学习理论统计学习理论 针对小样本统计估计和预测的针对小样本统计估计和预测的最佳理论最佳理论1.1.统计学习理论基本思想统计学习理论基本思想由贝尔实验室由贝尔实验室VapnikVapnik于于19921992年首次提出年首次提出 研究研究小样本下小样本下机器学习规律的理论。机器学习规律的理论。针对小样本统针对小样本统针对小样本统针对小样本统计问题，建立了一套计问题，建立
3、了一套计问题，建立了一套计问题，建立了一套新的理论新的理论新的理论新的理论体系体系体系体系基本思想：折衷考虑基本思想：折衷考虑经验风险经验风险和推广的和推广的置信界限置信界限，取得实际取得实际期望风险的最小化期望风险的最小化。即。即根据有根据有限样本信息在模型复杂性和学习能力之限样本信息在模型复杂性和学习能力之间寻求间寻求最佳折中最佳折中两大核心概念：两大核心概念：VCVC维和结构风险最小化维和结构风险最小化。在这一理论基础上，发展了一种新的通用在这一理论基础上，发展了一种新的通用模式识别方法模式识别方法支持向量机（支持向量机（SVMSVM）发展迅速，已经在发展迅速，已经在许多领域许多领域都取
4、得了都取得了成功成功的应用。的应用。VCVC维的概念：维的概念：（VCVC是取是取VapnikVapnik和和ChervonenkisChervonenkis名字的首字而成）名字的首字而成）描述函数集或学习机器的描述函数集或学习机器的复杂性复杂性的指标的指标，即描述，即描述机器学习能力机器学习能力的重要指标的重要指标打散打散:若存在一个有若存在一个有h h个样本的样本集个样本的样本集，被一函数集里，被一函数集里的某个函数按照所有可能的的某个函数按照所有可能的2 2h h种形式种形式分为两类分为两类，则，则称称函数集能够把样本数为函数集能够把样本数为h h的的样本集打散样本集打散(shatter
5、ing)。若对于任意的样本数，总能找到一个样本集能够被这若对于任意的样本数，总能找到一个样本集能够被这个函数集打散，则个函数集打散，则函数集的函数集的VCVC维就是无穷大维就是无穷大。函数集的函数集的vcvc维：维：用这个函数集中的函数用这个函数集中的函数所能够打散的最大样本集所能够打散的最大样本集的样本数目的样本数目。也就是说，如果。也就是说，如果存在存在h h个个样本的样本集能样本的样本集能够被函数集打散，而够被函数集打散，而不存在有不存在有h h1 1个个样本的样本集能样本的样本集能被函数集打散，则被函数集打散，则函数集的函数集的VCVC维就是维就是h h。例如：例如：3 3个样本被个样
6、本被线性线性线性线性分类器分类器打散打散的情况的情况有有2 2h h 2 23 38 8种分类形式种分类形式 能打散能打散VCVC维为维为3 3不能打散不能打散 VCVC维维是目前为止对函数集是目前为止对函数集学习性能学习性能的的最好描最好描述指标述指标。但遗憾的是目前尚。但遗憾的是目前尚没有通用的关于如何没有通用的关于如何计算任意函数集的计算任意函数集的VCVC维的理论。维的理论。结构风险最小化的思想结构风险最小化的思想VapnikVapnik证证明明，期期望望风风险险与与经经验验风风险险之之间间的的关关系系满满足如下公式：足如下公式：其中其中n n表示样本数，表示样本数，h h为为学习机器
7、的学习机器的VCVC维维，称为置信区间。称为置信区间。是随是随n/hn/h增大而减小的函数。增大而减小的函数。VCVC维维h h越大，越大，越大越大，经验风险和期望风险之间的，经验风险和期望风险之间的偏差越大偏差越大。这样。这样即使在经验误差很小的情况下，其推即使在经验误差很小的情况下，其推广误差会越大。广误差会越大。将函数集构造为一个函数子集序列将函数集构造为一个函数子集序列S S1 1 S S2 2 S Sk k ,使各个子集按照使各个子集按照VCVC维的大小排列（维的大小排列（h h1 1 h h2 2 h hk k ）。在每个子集中寻找最小经验风险。在每个子集中寻找最小经验风险,随子集
8、随子集复杂度增加而减小，复杂度增加而减小，在子集间折衷考虑经验风险和在子集间折衷考虑经验风险和置信界限置信界限,取得实际风险的最小取得实际风险的最小 结构风险最小结构风险最小就是根据函数集的性质将它划就是根据函数集的性质将它划分成一系列嵌套的子集，分成一系列嵌套的子集，学习问题就是学习问题就是选择最好选择最好的子集的子集(根据推广能力根据推广能力)和在子集中和在子集中选择最好的函选择最好的函数数（根据经验风险）（根据经验风险）SVMSVM是一种比较好地实现了是一种比较好地实现了结构风险最小化思想结构风险最小化思想的方法的方法分类超平面的分类超平面的一些基本概念一些基本概念W W是超平面是超平面
9、H H的法向量的法向量,决定超平面的方向；决定超平面的方向；b b 决定超平面的位置。决定超平面的位置。两类问题：两类问题：g(xg(x)表示分类面表示分类面 2.2.支持向量机算法支持向量机算法 找到一个找到一个超平面超平面，使得它能够，使得它能够尽可能多尽可能多尽可能多尽可能多的将两的将两类数据点类数据点正确的分开正确的分开，同时使分开的两类数据点，同时使分开的两类数据点距距距距离分类面最远离分类面最远离分类面最远离分类面最远。目标：目标：解决方法：解决方法：构造一个在约束条件下的构造一个在约束条件下的优化问题优化问题。SVMSVM是利用是利用核函数核函数将输入向量将输入向量映射映射到一个
10、到一个高维高维特特征空间征空间,并在该空间内构造一个并在该空间内构造一个最优超平面最优超平面来逼近分来逼近分类函数。类函数。最优分类超平面的构造最终可以归结为最优分类超平面的构造最终可以归结为二二次寻优问题次寻优问题。由于由于SVMSVM在解决在解决小样本小样本小样本小样本，非线性非线性非线性非线性及及及及高维高维高维高维模式识模式识模式识模式识别别别别问题中表现出问题中表现出许多特有的优势许多特有的优势，因此受到广泛，因此受到广泛的关注。的关注。最优分类面最优分类面：1 1）线性线性线性线性可分情况可分情况：对于对于线性可分线性可分问题，是在问题，是在经验风险经验风险为零为零时时，最小化最小
11、化置信范围置信范围。使两类使两类无错误无错误的分开，且使两类的分类的分开，且使两类的分类空隙最大空隙最大，前，前者是保证者是保证经验风险经验风险尽可能尽可能小小,后者是使后者是使真实风险最小真实风险最小。SVMSVM问题的问题的数学表示数学表示（线性可分情况）（线性可分情况）设两类线性可分训练样本集为设两类线性可分训练样本集为 ，d维维空间，空间，线性判别函数线性判别函数的一般形式为：的一般形式为：存在存在超平面为超平面为 ：使得训练样本中的正类输入和负类输入分别位使得训练样本中的正类输入和负类输入分别位于该于该超平面两侧超平面两侧。决策面方程决策面方程 许多决策平面都可以将两类样本分开，许多
12、决策平面都可以将两类样本分开，应选择应选择哪一个呢？哪一个呢？存在参数（存在参数（w w，b b），使得：），使得：Class 1Class 2目标：目标：最优最优分类面分类面满足条件：满足条件：经验风险经验风险最小最小（错分最少）（错分最少）推广能力推广能力最大最大（空白最大）（空白最大）Class 1Class 2H2H3WH1H如图所示，假定划分如图所示，假定划分直线的直线的法方向法方向已给定已给定。直线直线H H1 1是一条以是一条以ww为法向量为法向量且能且能正确划分两类样本正确划分两类样本的直线。的直线。如何寻找最优面？如何寻找最优面？这样的这样的直线直线并不唯一并不唯一。如果平行
13、推移直线。如果平行推移直线H H1 1 ，直到，直到碰到某类训练点碰到某类训练点，就可得到两条极端直线就可得到两条极端直线H H H H2 2 2 2和和和和H H H H3 3 3 3 ，在直线在直线H H2 2和和H H3 3之间的之间的平行直线平行直线都能正确都能正确分类分类。显然显然在在H H2 2和和H H3 3中间的那条直线中间的那条直线H H为最好为最好。以上给出了在已知法向量以上给出了在已知法向量w w情况下情况下构造构造划分直划分直线的方法线的方法。这样就把问题归结为。这样就把问题归结为寻求法向量寻求法向量寻求法向量寻求法向量w w w w及及及及b b b b。要让要让H
14、H满足满足w wT Tx xb b0 0 ，则，则必须寻找必须寻找最佳最佳(w(w、b)b)判别函数判别函数归一化归一化：假如假如H H可表示为可表示为：因为因为H H在中间在中间，显然显然H H2 2可表示为：可表示为：H H3 3可表示为可表示为 ：两边同除以两边同除以k k，令，令，则则H H为：为：H H2 2为：为：H H3 3为：为：该过程称为分类直线的该过程称为分类直线的规范化过程规范化过程（即判别函数（即判别函数归归一化一化）。）。此时此时两条直线两条直线H H2 2和和H H3 3之间的之间的间隔为间隔为：如前所述，对于如前所述，对于适当的法向量适当的法向量，会有会有两条极端
15、两条极端的的直线，直线，这两条直线之间这两条直线之间有间隔有间隔。最优分类直线最优分类直线就应该就应该是是两直线间隔最大两直线间隔最大的那个的那个法向量法向量所表示的所表示的直线直线。分类平面应使两类之间的间隔最大。归一化后分类分类平面应使两类之间的间隔最大。归一化后分类面方程面方程 应满足：应满足：即：即：如何寻找如何寻找w w及及b b对于对于任意样本任意样本x x有：有：Class 1Class 2m图中分类间隔为图中分类间隔为SVMSVM基本思想基本思想：就是就是最大化分最大化分类间隔类间隔 ，因此等价于因此等价于 最小化最小化 。因此，求取最优平面问题就因此，求取最优平面问题就转化为
16、优化问题转化为优化问题。因对于所有样本因对于所有样本（1）满足式（满足式（1 1），且使），且使 最小的分类面就是最小的分类面就是最优分类面最优分类面求极值：可用求极值：可用拉格朗日乘子法求解拉格朗日乘子法求解引入拉格朗日乘子引入拉格朗日乘子 i i 0 0，设设LagrangeLagrange函数为：函数为：（2）使式使式(1)(1)等号成立等号成立的样本的样本（即即H H2 2 和和H H3 3 上上的样本）就叫的样本）就叫支持向量支持向量。在条件式（在条件式（1 1）下，）下，求函数求函数的的最小值最小值。（2 2）式是一个）式是一个二次优化问题二次优化问题，存在唯一最优解。把，存在唯一
17、最优解。把该式该式分别对分别对w w、b b求偏导求偏导，并使其等于零，即：，并使其等于零，即：将上面两式带入（将上面两式带入（2 2），可得到下式：），可得到下式：于是，于是，对对w w和和b b求拉个朗日函数的求拉个朗日函数的极小值极小值来求解最优分来求解最优分类面问题，类面问题，可转化为可转化为在如下在如下约束条件约束条件下下（为样本数目）（为样本数目）（）对对 i i求解求解下列函数的下列函数的最大值最大值（）为与约束条件为与约束条件对应的对应的拉格朗日乘子。拉格朗日乘子。训练样本之间的训练样本之间的内积内积 这也是一个这也是一个二次函数寻优二次函数寻优问题，存在唯一解。解问题，存在唯
18、一解。解中只有中只有支持向量支持向量支持向量支持向量对应的对应的对应的对应的系数系数 i i为非零值，为非零值，即：只有即：只有支支支支持向量影响最终的划分结果持向量影响最终的划分结果持向量影响最终的划分结果持向量影响最终的划分结果。若若 为最优解，则为最优解，则任取任取 ，可求得（，可求得（可用支持向量求得可用支持向量求得）。）。由由任一支持向量任一支持向量通过式通过式(1)(1)可可求得求得b*b*。则最优分类则最优分类函数为：函数为：（6）式中求和实际式中求和实际只对支持向量只对支持向量进行（进行（非支持向量对非支持向量对应的应的 为为0 0），b*b*是分类阈值，是分类阈值，可用任意支
19、持向量可用任意支持向量（满足（满足（1 1）式的等号）求得）式的等号）求得，或通过两类中任意一或通过两类中任意一对支持向量取中值求得。对支持向量取中值求得。待分样本待分样本x与与支持支持向量向量xi的的内积内积2.2.线性不可分情况线性不可分情况约束条件：约束条件：（7）（8）引入引入松弛项松弛项 ，使得允许存在错分样本，使得允许存在错分样本，对应的优化问题变为：对应的优化问题变为：在约束条件下，求式（在约束条件下，求式（7 7）的极小值，可得线性不）的极小值，可得线性不可分情况下的最优分类面，可分情况下的最优分类面，称为广义最优分类面。称为广义最优分类面。对对 i i 求解下式求解下式 的最
20、大值。的最大值。同理，利用同理，利用拉格朗日乘子法，可把求解广义最优分类拉格朗日乘子法，可把求解广义最优分类面问题转化为在如下面问题转化为在如下约束条件下约束条件下：C C为可调参数，为可调参数，即惩罚因子即惩罚因子（C C越大，越大，惩罚越重），惩罚越重），称称这种这种SVMSVM为为CSVMCSVM训练样本之间的训练样本之间的内积内积 在在保留松驰项保留松驰项 i i的基础上，引入一新的的基础上，引入一新的参数参数V V来来控制控制支持向量的支持向量的数目和误差数目和误差，改进算法：改进算法：V VSVMSVM约束条件：约束条件：，对应的对偶问题：对应的对偶问题：在在如下如下约束条件下约束
21、条件下：求最小值求最小值，即，即（9）相应的相应的判别函数也变为：判别函数也变为：原始的原始的SVMSVM是两类分类器，对于多类分类问题需是两类分类器，对于多类分类问题需进行扩展，常用的方法有进行扩展，常用的方法有一类对余类和一类对一类。一类对余类和一类对一类。（10）3.3.非线性非线性SVMSVM：可通过某种可通过某种非线性变换非线性变换转化转化为另一空间的线性为另一空间的线性问题问题，在此，在此线性空间线性空间求解最优或广义最优分类面，求解最优或广义最优分类面，即将非线性问题即将非线性问题映射映射为线性问题。为线性问题。注意到注意到无论训练样本是否线性可分无论训练样本是否线性可分，求解其
22、对应，求解其对应的的优化问题优化问题以及最终得到的以及最终得到的最优分类超平面最优分类超平面都都只需计只需计算原始特征空间中算原始特征空间中样本间的内积样本间的内积，而，而不需要知道不需要知道从原从原始特征空间到高维特征空间的始特征空间到高维特征空间的非线性映射的具体形式非线性映射的具体形式 非线性非线性SVMSVM采用采用核函数核函数，将引入向量，将引入向量x x，通过，通过映映射射：R Rn n H H，即，即映射到映射到HilertHilert 空间。空间。设设核函数核函数k k满足下式：满足下式：一般一般不需要知道不需要知道 的具体形式和所属空间的具体形式和所属空间，只需，只需一种核函
23、数一种核函数满足满足MercerMercer条件条件，它就，它就对应某一变换空对应某一变换空间中的内积，间中的内积，即对函数即对函数g(xg(x)不恒为不恒为0,0,且且 所以所以采用采用引入适当核函数引入适当核函数k k的方法，就可的方法，就可实现实现非线性变换后的非线性变换后的线性分类线性分类。事实上，事实上，在取核函数为在取核函数为点积形式时，就是点积形式时，就是线性线性SVMSVM。则有：则有：对不同的核函数，对应不同的对不同的核函数，对应不同的SVMSVM，常用的几种有：常用的几种有：1 1、线性、线性SVMSVM：2 2、多项式、多项式SVMSVM：（为多项式的阶数）为多项式的阶数
24、）3 3、高斯核函数、高斯核函数SVMSVM：（为方差）为方差）4 4、SigmoidSigmoid核函数：核函数：(、是给定的常数）是给定的常数）这时，目标函数为：这时，目标函数为：相应分类函数为：相应分类函数为：这就是支持向这就是支持向量机量机SVMSVM存在的问题：存在的问题：算法算法速度慢速度慢，算法，算法复杂复杂且难以实现，检测阶且难以实现，检测阶段段运算量大运算量大等。等。改进：改进：去掉使去掉使 j j0 0的训练样本，的训练样本，对给定的训练样对给定的训练样本，若本，若支持向量已知支持向量已知，寻优法寻优法可以可以排除排除非支持向非支持向量，量，只需对只需对支持向量计算权值支持向量计算权值 j j即可。即可。新方法：超球面新方法：超球面