模式识别第十三章

模式识别第十三章第一页，共四十二页，编辑于2023年，星期六2）经验非线性方法如人工神经网络（ANN）利用已知样本建立非线性模型。缺点：缺乏一种统一的数学理论统计学习理论

—针对小样本统计估计和预测的最佳理论第二页，共四十二页，编辑于2023年，星期六1.统计学习理论基本思想由贝尔实验室Vapnik于1992年首次提出

研究小样本下机器学习规律的理论。针对小样本统计问题，建立了一套新的理论体系基本思想：折衷考虑经验风险和推广的置信界限，取得实际期望风险的最小化。即根据有限样本信息在模型复杂性和学习能力之间寻求最佳折中两大核心概念：VC维和结构风险最小化。第三页，共四十二页，编辑于2023年，星期六在这一理论基础上，发展了一种新的通用模式识别方法——支持向量机（SVM）发展迅速，已经在许多领域都取得了成功的应用。

VC维的概念：（VC是取Vapnik和Chervonenkis名字的首字而成）描述函数集或学习机器的复杂性的指标，即描述机器学习能力的重要指标第四页，共四十二页，编辑于2023年，星期六打散:若存在一个有h个样本的样本集，被一函数集里的某个函数按照所有可能的2h种形式分为两类，则称函数集能够把样本数为h的样本集打散(shattering)。若对于任意的样本数，总能找到一个样本集能够被这个函数集打散，则函数集的VC维就是无穷大。函数集的vc维：用这个函数集中的函数所能够打散的最大样本集的样本数目。也就是说，如果存在h个样本的样本集能够被函数集打散，而不存在有h＋1个样本的样本集能被函数集打散，则函数集的VC维就是h。第五页，共四十二页，编辑于2023年，星期六例如：3个样本被线性分类器打散的情况有2h＝23＝8种分类形式第六页，共四十二页，编辑于2023年，星期六能打散VC维为3不能打散第七页，共四十二页，编辑于2023年，星期六

VC维是目前为止对函数集学习性能的最好描述指标。但遗憾的是目前尚没有通用的关于如何计算任意函数集的VC维的理论。第八页，共四十二页，编辑于2023年，星期六结构风险最小化的思想Vapnik证明，期望风险与经验风险之间的关系满足如下公式：其中n表示样本数，h为学习机器的VC维，称为置信区间。是随n/h增大而减小的函数。

VC维h越大，越大，经验风险和期望风险之间的偏差越大。这样即使在经验误差很小的情况下，其推广误差会越大。第九页，共四十二页，编辑于2023年，星期六将函数集构造为一个函数子集序列S1S2Sk,使各个子集按照VC维的大小排列（h1h2hk）。在每个子集中寻找最小经验风险,随子集复杂度增加而减小，在子集间折衷考虑经验风险和置信界限,取得实际风险的最小

第十页，共四十二页，编辑于2023年，星期六结构风险最小就是根据函数集的性质将它划分成一系列嵌套的子集，学习问题就是选择最好的子集(根据推广能力)和在子集中选择最好的函数（根据经验风险）

SVM是一种比较好地实现了结构风险最小化思想的方法第十一页，共四十二页，编辑于2023年，星期六分类超平面的一些基本概念W是超平面H的法向量,决定超平面的方向；b决定超平面的位置。两类问题：g(x)表示分类面第十二页，共四十二页，编辑于2023年，星期六2.支持向量机算法找到一个超平面，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。目标：解决方法：构造一个在约束条件下的优化问题。

SVM是利用核函数将输入向量映射到一个高维特征空间,并在该空间内构造一个最优超平面来逼近分类函数。最优分类超平面的构造最终可以归结为二次寻优问题。第十三页，共四十二页，编辑于2023年，星期六由于SVM在解决小样本，非线性及高维模式识别问题中表现出许多特有的优势，因此受到广泛的关注。最优分类面：1）线性可分情况：对于线性可分问题，是在经验风险为零时，最小化置信范围。第十四页，共四十二页，编辑于2023年，星期六使两类无错误的分开，且使两类的分类空隙最大，前者是保证经验风险尽可能小,后者是使真实风险最小。第十五页，共四十二页，编辑于2023年，星期六SVM问题的数学表示（线性可分情况）设两类线性可分训练样本集为，d维空间，线性判别函数的一般形式为：第十六页，共四十二页，编辑于2023年，星期六存在超平面为：使得训练样本中的正类输入和负类输入分别位于该超平面两侧。决策面方程许多决策平面都可以将两类样本分开，应选择哪一个呢？存在参数（w，b），使得：第十七页，共四十二页，编辑于2023年，星期六Class1Class2目标：最优分类面满足条件：经验风险最小（错分最少） 推广能力最大（空白最大）第十八页，共四十二页，编辑于2023年，星期六Class1Class2H2H3W’H1H如图所示，假定划分直线的法方向已给定。直线H1是一条以w’为法向量且能正确划分两类样本的直线。如何寻找最优面？第十九页，共四十二页，编辑于2023年，星期六这样的直线并不唯一。如果平行推移直线H1

，直到碰到某类训练点，就可得到两条极端直线H2和H3

，在直线H2和H3之间的平行直线都能正确分类。显然在H2和H3中间的那条直线H为最好。

以上给出了在已知法向量w’情况下构造划分直线的方法。这样就把问题归结为寻求法向量w及b。要让H满足wTx＋b＝0，则必须寻找最佳(w、b)第二十页，共四十二页，编辑于2023年，星期六判别函数归一化：假如H可表示为：因为H在中间，显然H2可表示为：H3可表示为：两边同除以k，令，第二十一页，共四十二页，编辑于2023年，星期六则H为：H2为：H3为：该过程称为分类直线的规范化过程（即判别函数归一化）。此时两条直线H2和H3之间的间隔为：第二十二页，共四十二页，编辑于2023年，星期六如前所述，对于适当的法向量，会有两条极端的直线，这两条直线之间有间隔。最优分类直线就应该是两直线间隔最大的那个法向量所表示的直线。第二十三页，共四十二页，编辑于2023年，星期六分类平面应使两类之间的间隔最大。归一化后分类面方程应满足：即：如何寻找w及b对于任意样本x有：第二十四页，共四十二页，编辑于2023年，星期六Class1Class2m图中分类间隔为第二十五页，共四十二页，编辑于2023年，星期六SVM基本思想：就是最大化分类间隔，因此等价于

最小化。因此，求取最优平面问题就转化为优化问题。因对于所有样本（1）

满足式（1），且使最小的分类面就是最优分类面第二十六页，共四十二页，编辑于2023年，星期六求极值：可用拉格朗日乘子法求解引入拉格朗日乘子i0，设Lagrange函数为：（2）使式(1)等号成立的样本（即H2

和H3

上的样本）就叫支持向量。在条件式（1）下，求函数的最小值。第二十七页，共四十二页，编辑于2023年，星期六（2）式是一个二次优化问题，存在唯一最优解。把该式分别对w、b求偏导，并使其等于零，即：将上面两式带入（2），可得到下式：第二十八页，共四十二页，编辑于2023年，星期六于是，对w和b求拉个朗日函数的极小值来求解最优分类面问题，可转化为在如下约束条件下（为样本数目）（３）对i求解下列函数的最大值（４）为与约束条件

对应的拉格朗日乘子。训练样本之间的内积第二十九页，共四十二页，编辑于2023年，星期六这也是一个二次函数寻优问题，存在唯一解。解中只有支持向量对应的系数i为非零值，即：只有支持向量影响最终的划分结果。若为最优解，则任取，可求得（可用支持向量求得）。第三十页，共四十二页，编辑于2023年，星期六由任一支持向量通过式(1)可求得b*。则最优分类函数为：（6）

式中求和实际只对支持向量进行（非支持向量对应的为0），b*是分类阈值，可用任意支持向量（满足（1）式的等号）求得，或通过两类中任意一对支持向量取中值求得。待分样本x与支持向量xi的内积第三十一页，共四十二页，编辑于2023年，星期六2.线性不可分情况约束条件：（7）（8）引入松弛项，使得允许存在错分样本，对应的优化问题变为：第三十二页，共四十二页，编辑于2023年，星期六在约束条件下，求式（7）的极小值，可得线性不可分情况下的最优分类面，称为广义最优分类面。对i

求解下式的最大值。同理，利用拉格朗日乘子法，可把求解广义最优分类面问题转化为在如下约束条件下：C为可调参数，即惩罚因子（C越大，惩罚越重），称这种SVM为C—SVM训练样本之间的内积第三十三页，共四十二页，编辑于2023年，星期六

在保留松驰项i的基础上，引入一新的参数V来控制支持向量的数目和误差，改进算法：V－SVM约束条件：，第三十四页，共四十二页，编辑于2023年，星期六对应的对偶问题：在如下约束条件下：求最小值，即（9）第三十五页，共四十二页，编辑于2023年，星期六相应的判别函数也变为：原始的SVM是两类分类器，对于多类分类问题需进行扩展，常用的方法有一类对余类和一类对一类。

（10）第三十六页，共四十二页，编辑于2023年，星期六3.非线性SVM：可通过某种非线性变换转化为另一空间的线性问题，在此线性空间求解最优或广义最优分类面，即将非线性问题映射为线性问题。注意到无论训练样本是否线性可分，求解其对应的优化问题以及最终得到的最优分类超平面都只需计算原始特征空间中样本间的内积，而不需要知道从原始特征空间到高维特征空间的非线性映射的具体形式第三十七页，共四十二页，编辑于2023年，星期六

非线性SVM采用核函数，将引入向量x，通过映射：RnH，即映射到Hilert空间。设核函数k满足下式：第三十八页，共四十二页，编辑于2023年，星期六一般不需要知道的具体形式和所属空间，只需一种核函数满足Mercer条件，它就对应某一变换空间中的内积，即对函数g(x)不恒为0,且所以采用引入适当核函数k的方法，就可实现非线性变换后的线性分类。事实上，在取核函数为点积形式时，就是线性SVM。则有：第三十九页，共四十二页，编辑于2023年，星期六对不同的核函数，对应不同的SVM，常用的几种有：1、线性SVM：2、多项式SVM：（为多项式的阶数）3、高斯核函数SVM：（为方差）