课件：第章支持向量机和核函数.ppt

第5章 支持向量机和核函数,“支持向量机方法是建立在统计学习理论的VC 维理论和结构化风险最小原理基础上” 结构化风险 结构化风险 = 经验风险 + 置信风险 经验风险 = 分类器在给定样本上的误差 置信风险 = 分类器在未知样本上分类的结果的误差,一般模式识别方法的问题,1）传统统计方法 基于经验风险最小化，经验风险最小不等于期望风险最小，不能保证分类器的推广（泛化）能力。 经验风险只有在样本数无穷大趋近于期望风险，即在有限样本情况下，经验风险最小并不意味着期望风险最小。 需要已知样本的分布形式,推广能力是指: 将学习机器(即预测函数,或称学习函数、学习模型)对未来输出进行正确预测的能力。 “过学习问题”：某些情况下，当训练误差过小反而会导致推广能力的下降。 例如：对一组训练样本(x,y),x分布在实数范围内，y取值在0，1之间。无论这些样本是由什么模型产生的，我们总可以用y=sin(w*x)去拟合，使得训练误差为0.,机器学习本质上就是一种对问题真实模型的逼近，但真实模型一定是不知道的。那么我们选择的假设与问题真实解之间究竟有多大差距，我们就没法得知。这个与问题真实解之间的误差，就叫做风险。我们选择了一个假设后，真实误差无从得知， 但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间的差值来表示。这个差值叫做经验风险Remp(w)。以前的机器学习方法都把经验风险最小化作为努力的目标，但后来发现很多分类函数能够在样本集上轻易达到100%的正确率，在真实分类时却一塌糊涂（即所谓的推广能力差，或泛化能力差）。,原因：选择了一个足够复杂的分类函数，能够精确的记住每一个样本，但对样本之外的数据一律分类错误。 统计学习引入了泛化误差界的概念，就是指真实风险应该由两部分内容刻画，一是经验风险，代表了分类器在给定样本上的误差；二是置信风险，代表了我们在多大程度上可以信任分类器在未知样本上分类的结果。很显然，第二部分是没有办法精确计算的，因此只能给出一个估计的区间，也使得整个误差只能计算上界，而无法计算准确的值。 置信风险与两个量有关，一是样本数量，显然给定的样本数量越大，我们的学习结果越有可能正确，此时置信风险越小；二是分类函数的VC维，VC维越大，推广能力越差，置信风险会变大。,2）经验非线性方法 如人工神经网络（ANN） 利用已知样本建立非线性模型。 缺点：缺乏一种统一的数学理论,统计学习理论 针对小样本统计估计和预测的最佳理论,1.统计学习理论基本思想,由贝尔实验室Vapnik于1992年首次提出,研究小样本下机器学习规律的理论。针对小样本统计问题，建立了一套新的理论体系,基本思想：折衷考虑经验风险和推广的置信界限，取得实际期望风险的最小化。即根据有限样本信息在模型复杂性和学习能力之间寻求最佳折中,两大核心概念： VC维和结构风险最小化。,在这一理论基础上，发展了一种新的通用模式识别方法支持向量机（SVM）,发展迅速，已经在许多领域都取得了成功的应用。,VC维的概念： （VC是取Vapnik和Chervonenkis名字的首字而成）,描述函数集或学习机器的复杂性的指标，即描述机器学习能力的重要指标,样本数量，给定的样本数量越大，学习结果越有可能正确，此时置信风险越小； 分类函数的VC维，VC维越大，推广能力越差，置信风险会变大。 提高样本数量，降低VC维，降低置信风险。 以前机器学习的目标是降低经验风险，要降低经验风险，就要提高分类函数的复杂度，导致VC维很高，VC维高，置信风险就高，所以，结构风险也高。- 这是SVM比其他机器学习具有优势的地方,VC维的引入,打散:若存在一个有h个样本的样本集，被一函数集里的某个函数按照所有可能的2h种形式分为两类，则称函数集能够把样本数为h的样本集打散(shattering)。,若对于任意的样本数，总能找到一个样本集能够被这个函数集打散，则函数集的VC维就是无穷大。,函数集的vc维： 用这个函数集中的函数所能够打散的最大样本集的样本数目。也就是说，如果存在h个样本的样本集能够被函数集打散，而不存在有h1个样本的样本集能被函数集打散，则函数集的VC维就是h。,例如：3个样本被线性分类器打散的情况,有2h 238种分类形式,能打散 VC维为3,不能打散,VC维是目前为止对函数集学习性能的最好描述指标。但遗憾的是目前尚没有通用的关于如何计算任意函数集的VC维的理论。,VC维是目前为止对函数集学习性能的最好描述指标。但遗憾的是目前尚没有通用的关于如何计算任意函数集的VC维的理论。,结构风险最小化的思想,Vapnik证明，期望风险与经验风险之间的关系满足如下公式：,其中n表示样本数，h为学习机器的VC维， 称为置信区间。 是随n/h增大而减小的函数。,VC维h越大， 越大，经验风险和期望风险之间的偏差越大。这样即使在经验误差很小的情况下，其推广误差会越大。,将函数集构造为一个函数子集序列S1 S2 Sk ,使各个子集按照VC维的大小排列（h1 h2 hk ）。在每个子集中寻找的最小经验风险,随子集复杂度增加而减小，在子集间折衷考虑经验风险和置信界限,取得实际风险的最小 。,结构风险最小就是根据函数集的性质将它划分成一系列嵌套的子集，学习问题就是选择最好的子集(根据推广能力)和在子集中选择最好的函数（根据经验风险）,SVM是一种比较好地实现了结构风险最小化思想的方法,分类超平面的一些基本概念,W是超平面H的法向量,决定超平面的方向； b 决定超平面的位置。,两类问题：g(x)表示分类面,2.支持向量机算法,找到一个超平面，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。,目标：,解决方法：,构造一个在约束条件下的优化问题。,SVM是利用核函数将输入向量映射到一个高维特征空间,并在该空间内构造一个最优超平面来逼近分类函数。最优分类超平面的构造最终可以归结为二次寻优问题。,由于SVM在解决小样本，非线性及高维模式识别问题中表现出许多特有的优势，因此受到广泛的关注。,最优分类面：,1）线性可分情况：,对于线性可分问题，是在经验风险为零时，最小化置信范围。,使两类无错误的分开，且使两类的分类空隙最大，前者是保证经验风险尽可能小, 后者是使真实风险最小。,SVM问题的数学表示（线性可分情况）,设两类线性可分训练样本集为 ，,d维空间，线性判别函数的一般形式为：,存在超平面为 ：,使得训练样本中的正类输入和负类输入分别位于该超平面两侧。,决策面方程,许多决策平面都可以将两类样本分开，应选择哪一个呢？,存在参数（w，b），使得：,目标：最优分类面,满足条件： 经验风险最小（错分最少） 推广能力最大（空白最大）,如图所示，假定划分直线的法方向已给定。直线H1是一条以w为法向量且能正确划分两类样本的直线。,如何寻找最优面？,这样的直线并不唯一。如果平行推移直线H1 ，直到碰到某类训练点，就可得到两条极端直线H2和H3 ，在直线H2和H3之间的平行直线都能正确分类。显然在H2和H3中间的那条直线H为最好。,以上给出了在已知法向量w情况下构造划分直线的方法。这样就把问题归结为寻求法向量w及b。,要让H满足wTxb0 ，则必须寻找最佳(w、b),判别函数归一化：,假如H可表示为：,因为H在中间，显然H2可表示为：,H3可表示为 ：,两边同除以k，令,，,则H为：,H2为：,H3为：,该过程称为分类直线的规范化过程（即判别函数归一化）。,此时两条直线H2和H3之间的间隔为：,如前所述，对于适当的法向量，会有两条极端的直线，这两条直线之间有间隔。最优分类直线就应该是两直线间隔最大的那个法向量所表示的直线。,分类平面应使两类之间的间隔最大。归一化后分类 面方程 应满足：,即：,如何寻找w及b,对于任意样本x有：,图中分类间隔为,SVM基本思想：就是最大化分类间隔 ，因此等价于 最小化 。,因此，求取最优平面问题就转化为优化问题。因对于所有样本,（1）,满足式（1），且使 最小的分类面就是最优分类面,使式(1)等号成立的样本（即H2 和H3 上的样本）就叫支持向量。,由上节可知 我们的目标函数：,用另一个完全等价的目标函数来代替，那就是：,如果直接来解这个求最小值问题，很容易看出当|w|=0的时候就得到了目标函数的最小值。反映在图中，就是H2与H3两条直线间的距离无限大，这个时候，所有的样本点（无论正样本还是负样本）都跑到了H2和H3中间，而我们原本的意图是，H2右侧的 被分为正类，H3 左侧的被分为负类，位于两类中间的样本则拒绝分类。这下可好，所有样本点都进 入了无法分类的灰色地带。造成这种结果的原因是在描述问题的时候只考虑了目标，而没有加入约束条件， 体现在我们的问题中就是样本点必须在H2或H3的某一侧（或者至少在H2或H3上），而不能跑到两者中间。,约束是什么？,求极值：可用拉格朗日乘子法求解,引入拉格朗日乘子i0，设Lagrange函数为：,（2）,使式(1)等号成立的样本（即H2 和H3 上的样本）就叫支持向量。,（2）式是一个二次优化问题，存在唯一最优解。把该式分别对w、b求偏导，并使其等于零，即：,将上面两式带入（2），可得到下式：,于是，对w和b求拉个朗日函数的极小值来求解最优分类面问题，可转化为在如下约束条件下,（ 为样本数目）,（）,对i求解下列函数的最大值,（）,为与约束条件 对应的拉格朗日乘子。,训练样本之间的内积,这也是一个二次函数寻优问题，存在唯一解。解中只有支持向量对应的系数i为非零值，即：只有支持向量影响最终的划分结果。,若 为最优解，则,任取 ，可求得 （可用支持向量求得）。,由任一支持向量通过式(1)可求得b*。则最优分类函数为：,（6）,待分样本x与支持向量xi的内积,2. 线性不可分情况,约束条件：,（7）,（8）,引入松弛项 ，使得允许存在错分样本，对应的优化问题变为：,在约束条件下，求式（7）的极小值，可得线性不可分情况下的最优分类面，称为广义最优分类面。,对i 求解下式,的最大值。,同理，利用拉格朗日乘子法，可把求解广义最优分类面问题转化为在如下约束条件下：,C为可调参数，即惩罚因子（C越大，惩罚越重），称这种SVM为CSVM,训练样本之间的内积,C越大,表示分类越严格,允许错分的样本受到的限制越大,错分的样本数少,越过拟合。,在保留松驰项i的基础上，引入一新的参数V来控制支持向量的数目和误差，,改进算法：VSVM,约束条件：,，,对应的对偶问题：在如下约束条件下：,求最小值，即,（9）,相应的判别函数也变为：,原始的SVM是两类分类器，对于多类分类问题需 进行扩展，常用的方法有一类对余类和一类对一类。,（10）,多类SVM算法,SVM本质上是两类分类器. 常用的SVM多值分类器构造方法有:,3.非线性SVM：,可通过某种非线性变换转化为另一空间的线性问题，在此线性空间求解最优或广义最优分类面，即将非线性问题映射为线性问题。,3.非线性SVM：,可通过某种非线性变换转化为另一空间的线性问题，在此线性空间求解最优或广义最优分类面，即将非线性问题映射为线性问题。,注意到无论训练样本是否线性可分，求解其对应的优化问题以及最终得到的最优分类超平面都只需计算原始特征空间中样本间的内积，而不需要知道从原始特征空间到高维特征空间的非线性映射的具体形式,总结,目标函数： 约束条件：,目标函数： 约束条件：,拉格朗日乘数法可将问题转化为对偶问题： 目标函数： 约束条件：,线性分类,巧妙之处：原问题 = 二次凸优化问题 = 对偶问题 对偶问题求解： 更巧妙的地方： 未知数据x的预测，只需要计算它与训练数据点的内积即可,非线性分类,对于以上所述的SVM，处理能力还是很弱，仅仅能处理线性可分的数据。如果数据线性不可分的时候，我们就将低维的数据映射向更高的维次，以此使数据重新线性可分。这转化的关键便是核函数。,2019/8/24,59,可编辑,非线性分类,找不到一个超平面（二维空间：直线）将其分割开来，而很自然的想到可以用一个椭圆将数据分为两类,Z1=X1, Z2=X12, Z3=X2, Z4=X22, Z5=X1X2 (X1,X2) (Z1, Z2, Z3, Z4, Z5,) 即将：R2空间映射到R5空间。 此时，总能找到一个超平面wT Z + b = 0 wT = a1， a2， a3， a4， a5T ，b = a6 使得数据很好的分类。,映射过后的空间:,one case study：核函数引入,对于非线性的情况，SVM 的处理方法是选择一个核函数 (,) ，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。由于核函数的优良品质，这样的非线性扩展在计算量上并没有比原来复杂多少。当然，这要归功于核方法除了 SVM 之外，任何将计算表示为数据点的内积的方法，都可以使用核方法进行非线性扩展。,one case study：核函数引入,在遇到核函数之前，如果用原始的方法，那么在用线性学习器学习一个非线性关系，需要选择一个非线性特征集，并且将数据写成新的表达形式，这等价于应用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器，因此，考虑的假设集是这种类型的函数：,one case study：核函数引入,one case study：核函数引入,如下图所示的两类数据，分别分布为两个圆圈的形状，这样的数据本身就是线性不可分的，你准备如何把这两类数据分开呢,one case study：核函数引入,one case study：核函数引入,one case study：核函数引入,one case study：核函数引入,非线性SVM采用核函数，将引入向量x，通过映射：Rn H，即映射到Hilbert 空间。,设核函数k满足下式：,一般不需要知道的具体形式和所属空间，只需一种核函数满足Mercer条件，它就对应某一变换空间中的内积，即对函数g(x)不恒为0,且,所以采用引入适当核函数k的方法，就可实现非线性变换后的线性分类。事实上，在取核函数为点积(内积)形式时，就是线性SVM。,则有：,核函数,则核函数为 其中 为将数据映射到高维空间的映射 有许多可能的核函数 最简单的为核,对不同的核函数，对应不同的SVM，常用的几种有：,1、线性SVM：,2、多项式SVM：,（ 为多项式的阶数）,3、高斯核函数SVM：,（ 为方差）,4、Sigmoid核函数：,( 、 是给定的常数）,这时，目标函数为：,相应分类函数为：,这就是支持向量机,核方法的要点,通过将输入空间映射到高维空间（特征空间），然后在高维空间中用线性方法 高维：维数灾难 通过核技巧，避免维数灾难,核方法的要点,核技巧(kernel trick ) ：寻找一个映射 和一个学习方法，使得 F的维数比X高 , 因此模型更丰富 算法只需要计算点积 存在一个核函数，使得 在算法中任何出现项 的地方，用 代替,点积核,非线性SVM和核函数总结,85,85,1.如何解决少量非线性可分样本？,86,内容提要,2.如何解决大量非线性可分样本？,3.核函数方法（Kernel Trick）,86,基本思想：通过训练误差和类间宽度之间的权衡，得到一个最优超平面。,1. 线性SVM求解含少量非线性可分样本的思想,优化目标：,约束条件：,权衡因子,松弛变量,87,1类样本：位于分类间隔之外,88,类似的，通过Lagrange函数，转化为对偶问题,1类样本,2类样本,3类样本,2类样本：支持向量,3类样本：位于分类间隔之内,88,不同的权衡因子得到的不同的分类面,C10,C1000,89,2.非线性支持向量机,当线性支持向量机划分样本会产生过多训练误差时，需要考虑使用非线性分类面对两类样本进行划分。,90,2.1 寻找非线性问题的三种思路,思路1:原空间法 在原空间中直接求解非线性问题,91,例1：XOR问题,思路2 :特征空间法 将非线性问题的求解转换成另一个空间中的线性问题求解,92,例2：物种分类问题,93,寻找特征映射所面临的问题：,1. 特征映射的确定往往需要相当高的技巧和相当专业的领域知识；,3. 特征映射往往是一个低维向高维映射的过程，这个映射过程经常面临维数灾难。,2. 特征映射的计算可能会相当复杂；,94,思路3. 核函数方法,优化问题：,判别函数：,样本之间的内积,构建到特征空间的隐式映射,95,2.2 线性SVM通过核函数扩展为非线性SVM,线性SVM:,假设经过某种非线性特征映射后原来的非线性可分问题可以通过线性SVM来解决，则在特征空间中的判别函数可以表示为：,96,其中,通过求解如下的优化问题得到：,利用核函数将非线性问题转化为线性问题的手段和方法称之为核函数方法。,97,例：XOR问题中我们构造了一个非线性映射实现了特征的升维：,样本点在新的特征空间中的内积为：,核函数描述了样本点在经过某种特征变换后，在新的特征空间中的内积。,98,优化问题：,判别函数：,线性支持向量机,非线性支持向量机,利用支持向量机求解异或问题的结果示意图,核函数,99,3.1 核函数的定义,定义 核函数是一个对称函数，对所有的,满足：,特征空间中的内积运算的充分必要条件是，对于任意的,，它是某个,100,3 核函数方法,推论 令X是有限输入空间，K(x , z)是X上的对称函数。那么K(x , z)是核函数的充要条件是矩阵：,是半正定的。,常用的核函数：,多项式核函数,高斯核函数,sigmoid核函数,101,3.2 核函数的构造,令K1和K2是X*X上的核，f()是X上的一个实值函数。B是一个对称半正定矩阵。那么下面的函数是核函数：,从核函数中构造,从特征中构造,从相似性度量中构造,102,103,3.3 核函数的可分性,定理2：样本点D在核函数k(x,y)导出的特征映射下线性可分的充要条件是，下列方程组不存在非负解：,其中，,104,3.3 核函数的可分性,其中，,推论1：当 时，样本点线性可分。,推论2： 对任意给定的训练样本，如果选用RBF核函数 ，则当宽度参数 充分小时， 训练样本总是线性可分的。,105,3.4 如何选择核函数,问题1： 何谓一个好的核函数？,好的核函数能够真实反映样本间的远近关系。,问题2： 如何判断核函数是否真实的反映的样本间的远近关系？,比较难！但是初步判断核函数是否真实反映了训练样本之间的远近关系还是可能的。,核函数的选择策略： 选择能够真实反映训练样本远近关系的核函数。,106,问题3：训练样本间的远近关系如何表达？,物理含义：两个属于同类的样本相似度为1，不同类的样本相似度为0。,问题4：核函数与训练样本间的远近关系的一致性评估,利用矩阵的相似性度量：,草案：通过求解下面的优化问题进行核函数参数的选择：,问题：如果K()如下所示：,它是一个糟糕的Gram矩阵。因为它把所有的训练样本均看作是同一类样本 。而它会使目标函数取到比较大的值！,例1：核函数的选择,最终方案：通过求解下面的优化问题进行核函数的选择：,其中，,K=,物理意义：一个好的核函数能够使同类的样本更加接近，而使不同类的样本更加疏远。,例1：核函数的