第5章-支持向量机和核函数课件

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