模式识别-第十三章统计学习理论与支持向量机.ppt
第10章统计学习理论与支持向量机,统计学习理论为基于小样本的统计理论支持向量机为基于统计学习理论的应用工具,统计学习理论的提出：传统模式识别理论的基础为样本数目足够大，实际上，样本的数目是有限的。统计学习理论为基于小样本的统计理论。应用目标：有限样本条件下，统计模式识别与机器学习问题的理论框架。为当前国际上机器学习领域的研究热点。,10.1 引言,基于数据的机器学习问题现代智能技术的一个重要方面。研究对象：现实世界中，大量的，目前无法准确认识，但可以观测的事物，由观测数据表征。研究目的：利用观测数据，得到目前不能通过原理分析来得到的规律,规律：为各学科方向的规律。用于分类学即模式识别用于模型学即参数模型的辩识用于系统控制即学习控制问题。传统统计学渐进理论，即样本数目趋于无穷大。表现为：统计学中关于估计的一致性，无偏性与估计方差的有界性,统计学习理论研究的历史,60年代，着手研究有限样本条件下的机器学习问题，研究成果为：经验风险最小化与有序风险最小化问题。90年代，由于需要，人工神经网络用于机器学习中的问题引出：网络结构的确定问题（高维空间），过学习与欠学习问题，局部极值问题等等，统计学习理论是研究机器学习问题中更为本质的问题。,92年提出 支持向量机，Support Vector Machine，（SVM），统计学习理论的一个应用模型，其优势表现在：小样本，非线性，高维数空间的模式识别中。可以推广到其他有关机器学习问题的应用中如：函数拟合，参数辩识，学习控制等。,10.2 机器学习的基本问题与方法,基本问题有：1 机器学习问题的表示方法2 经验风险最小化与期望风险最小化3 机器学习中的复杂性与推广性,10.2.1 机器学习问题的表示,模型：,数学描述：已知输入x与输出y之间存在未知的依赖关系未知的联合概率F(x,y)，（确定性关系为特例），根据n个独立同分布观测样本在一组函数f(x,)中，寻找一个最优函数f(x,0)，使得预测的期望风险 最小。,其中：f(x,)预测函数集合，任意函数，又称学习函数，学习模型，学习机器。损失函数，使用某预测函数f(x,)对y做预测的损失。3类基本的机器学习问题：模式识别，函数拟合，概率密度估计。,模式识别中的机器学习问题（有监督，有导师模式识别问题，）系统输出y为类别标号。两类情况时y=0,1或者y=-1,+1，为二值函数。预测函数又称，指示函数，判别函数损失函数定义为例如该定义下的期望风险就是平均错误率，期望风险最小的决策即贝叶斯决策,函数拟合中的机器学习问题y为变量x的连续函数。损失函数定义为（平方误差）通过将输出y做阈值的二值转换，函数拟合问题化为模式识别问题。,概率密度估计中的机器学习问题学习目的为：根据训练样本来确定x的概率分布。损失函数定义为 其中，为估计的密度函数。,10.2.2 经验风险最小化 与期望风险最小化,期望风险最小化的条件期望风险 其最小化必须依赖于联合概率F(x,y)中的信息。在模式识别问题中就是：必须已知类先验概率P()和类条件概率密度p(x|)。,但是在机器识别中，仅有样本信息：n个独立同分布观测样本：是不能计算期望风险 的。,经验风险：根据大数定律，由算术平均来替代数学期望有即由该式来逼近期望风险。在该式中，Remp()是由训练样本（经验数据）来定义的，因此，定义该式为经验风险。,经验风险最小化原则：参数w的Remp(w)最小化代替R(w)的最小化称经验风险最小化原则。依据该原则，提出了各种基于数据的分类器设计方法。但是存在问题：理论依据不足。,问题1：首先都是w的函数，概率论中的大数定律仅指明：n时，在概率意义上，Remp(w)R(w)*不能保证 Remp(w*)与R(w*)中的w是同一个点（w*与w*）。*更不能保证 能够使Remp(w*)R(w*),问题2：即使可以保证，n时，Remp(w)R(w)，也无法认定，在样本数目有限时，经验风险最小化方法得到的结果更好。统计学习理论的研究解决的几个基本问题：1 用经验风险最小化解决期望风险最小化问题的前提是什么？2 前提不成立时，经验风险最小化的性能如何3 是否存在更合理的原则？,10.2.3 机器学习的复杂性与推广性,机器学习的复杂性可以定义为：对于复杂问题的跟踪能力，搜索能力，探寻能力。机器学习的推广性学习机器对于未来目标的预测能力，或者可使用性。两者是矛盾的。,学习与过学习：实验数据1：已知小样本n=5，使用学习机器作曲线拟合，设拟合函数为y=exp(ax)sin(bx),经学习训练后，由训练误差为零，总可以找到参数a,b满足拟合函数。当使用更复杂的函数去拟合一个有限样本时，其学习结果便产生了过学习。产生过学习的原因：1 学习样本不够充分（已知小样本n=5）2 学习机器设计不合理（拟合函数为y=exp(ax)sin(bx)）,机器学习的复杂性与推广性的矛盾学习能力过强，用复杂函数去记忆有限样本，可以使经验风险最小（训练误差为零），但是无法保证对未来样本的预测能力，即丧失了推广性。,实验数据2实验数据为二次曲线加随机噪声生成，n=6。学习机器依经验风险最小原则，对数据分别作一次曲线拟合与二次曲线拟合，拟合结果为：,无论实验多少次，一次曲线总比二次曲线拟合的误差小得多，即一次曲线的期望风险小于二次曲线。其原因是：数据有限。小样本时，对于机器学习的基本结论：1 经验风险最小不一定是期望风险最小。2 学习机器的复杂性一定要与学习样本的有限性相适应,10.3 统计学习理论的核心内容,是小样本统计估计与预测学习的最佳理论，从理论上系统地研究了经验风险最小化原则的条件、有限样本条件下经验风险与期望风险的关系以及如何应用该理论找到新的学习原则与方法等问题。,核心内容如下1、经验风险最小化原则下，统计学习的 一致性条件（Consistency）2、在这些条件下关于统计学习方法 推广性的界的结论。3、在这些界的基础上建立小样本归纳推理原则。4、实现这些新的原则的实际算法。,10.3.1 学习过程一致性的条件,学习过程一致性训练样本数n时，有 Remp(w)R(w)，经验风险的最优值可以收敛到真实风险最优值。称该学习过程是一致的，又称该学习过程满足一致性。,一个学习过程，只有满足学习过程一致性的条件，才可以保证在经验风险最小化原则下得到的最优方法，在训练样本数n时，得到期望风险最小的最优结果。,定义：给定n个独立同分布观测样本预测函数f(x,w*)为该样本集合下在函数集合中使经验风险取最小的预测函数损失函数L(y,f(x,w*|n)最小经验风险值Remp(w*|n),期望风险R(w*|n)，在L(y,f(x,w*|n)下的，由式 得到的真实风险值。如果满足 其中 为实际真实风险的下确界。则称为经验风险最小化学习过程是一致的。,几何意义,定理：学习理论关键定理,如果损失函数有界，则经验风险最小化学习一致的充分必要条件是即经验风险一致收敛于真实风险其中：P表示概率Remp(w)经验风险R(w)同一w的真实风险,定理说明：1 在统计学习理论中是即为重要的。2 将学习一致性问题转化为公式的一致收敛问题。3 定理既依赖于预测函数集合，又依赖于样本的概率分布。4 双边一致收敛表达式为,5 经验风险与期望风险都是泛函（预测函数的函数）。6 目的不是用经验风险取逼近期望风险而是通过求使经验风险最小化的函数来逼近能使期望风险最小化的函数。7 与传统统计学中的一致性条件相比，该一致性条件更加严格。8 由公式可知，该一致性条件是取决于预测函数中最差的函数的，因此是最坏情况分析。,9 定理本身虽然给出了经验风险最小化原则成立的充分必要条件，但是该定理并没有给出什么样的方法能够满足这些条件。基于上述讨论，统计学习理论研究了一些评价预测函数集合的性能指标。,10.3.1 函数集合的学习性能与VC维,统计学习理论研究了一些评价预测函数集合的性能指标。这些性能指标是基于两类分类函数提出的，扩展到一般函数1 指示函数集的熵和生长函数设指示函数集和训练样本集为,函数集中的函数能够对样本集实现不同的分类方法数目，记为N(Zn)定义1：随机熵将上述不同的分类方法数目的对数定义为随机熵H(Zn)=lnN(Zn)说明：随机熵与分类函数集合有关，且与样本集有关。,定义2：指示函数的熵将随机熵取期望，称为指示函数的熵H(n)=ElnN(Zn)又称VC熵。定义3：退火VC熵Hann(n)=lnEN(Zn),定义4：生长函数函数集的生长函数定义为，在所有可能的样本集上的最大随机熵说明：1 生长函数描述了函数集把n个样本分成两类的最大可能的分法数目2 最大值：3 由于是在所有可能的样本集中取最大，因此与样本分布无关。,VC熵，退火VC熵，生长函数之间的关系为下面是几个关键定理定理1：函数集学习过程双边一致收敛充分必要条件为（由指示函数熵来表示学习理论关键定理，与学习理论关键定理等价,定理2：函数集学习过程收敛速度快的充分必要条件为定理3：函数集学习过程一致收敛的充分必要条件是对任意样本分布，有而且学习过程一致收敛的速度一定是快的。,2 生长函数的性质与VC维 定理1：所有函数集的生长函数或者与样本数成正比或者以下列样本数的某个对数函数为上界 其中，h为整数，n=h时，为上两式的转折点。,生长函数的该性质如图所示。,定义：VC维（Vapnike&Chervonenkis）如果存在一个h个样本的样本集能够被一个函数集中的函数按照所有可能的2n种形式分为两类，或者说函数集能够把样本数为h的样本集“打散”或者“粉碎”（shattering），则指示函数集的VC维就是用该函数集中的函数能够“打散”的最大样本集的样本数目。,换句话说，如果存在有h个样本的样本集能够被函数集中的函数“打散”，而不存在有h+1个样本的样本集能够被函数集中的函数“打散”，则函数集的VC维就是h。如果对于任意的样本数，总能找到一个样本集能够被这个函数集“打散”，则该函数集的VC维就是无穷大。,由此：如果对于一个指示函数集，其生长函数是线性的，则其VC维即为无穷大。如果生长函数以参数h的对数函数为上界，则函数集的VC维是有限的且其VC维等于h。由此：由前面的定理3，经验风险最小化学习过程一致的充分必要条件是函数集的VC是有限的，且收敛速度是快的。,关于VC维定义的说明：,1 可以证明，损失函数集与预测函数集有相同的VC维。2 d维空间中的阈值分类器 的VC维是d+1。,3 d维空间中的实值线性分类器其VC维也是d+1。4 VC维是统计学习理论的一个核心概念，目前为止对函数集学习性能的最好描述指标。5 遗憾的是，目前为止，没有通用的计算任意函数集VC维的理论。只有一些特殊函数集的VC维可以准确知道。,6 对于复杂的学习机器，比如神经网络，其VC维的确定除了与函数集的选择有关，而且受到学习算法的影响，确定其VC维更为困难。7 前沿研究课题：如何使用理论的或者实验的方法来计算预测函数的VC维。,10.3.3 推广性的界,10.4 支持向量机(Support Vector Machine,SVM),统计学习理论思想的实现方法支持向量机。由非线性变换将问题由低维空间变换到高维空间来解决经验风险最小化问题。支持向量机得到的解具有很好的推广性。最好地利用了分类边界样本信息，因此与样本分布无关。,10.4.1 最优分类面与支持向量,设线性可分样本集为d维向量，2类样本，y为类别标签。则线性判别函数为 分类面方程为,作判别函数归一化，即满足|g(x)|1，即距离分类面最近的样本距离为|g(x)|=1，则两类的分类间隔为2/|w|。如图所示,最优分类面令分类间隔2/|w|最大，等价于|w|或者|w|2最小，使得分类面对于所有的样本能正确分类，即满足则该分类面为最优分类面。支持向量过两类样本中离分类面最近的点，且平行于最优分类面的超平面H1,H2上的训练样本则称为支持向量，显见，最优分类面是由支持向量来“支撑”的。,最优分类面的求取由最优分类面的条件建立目标函数，为二次型由满足条件作为约束条件（样本条件）则有约束优化问题,由拉格朗日乘子法求解最优分类面的条件。定义拉格朗日函数为式中i0，为拉格朗日乘子。L对w，b求极小值。由 得到最优化条件,求原约束优化问题的对偶问题，可以得到单一变量的优化函数为（Q的求极大值）如果i*为最优解，则有最优分类面的权系数向量为训练样本向量的线性组合。该最优解满足,因此有：对于多数样本xi来说，i*为零，而不为零的i*对应于使等号成立的样本xi即支持向量。通常支持向量的个数很少。对应于最优权系数向量，则最优分类函数为 上式中，只对支持向量进行作求和运算。分类阈值b*则由任意一个支持向量满足等式解出。,10.4.2 广义最优分类面,前面的最优分类面式在线性可分条件下推导出来的。不能应用于线性不可分情况。改造。约束条件1：对于线性不可分情况，许多样本不能满足正确分类条件式因此，增加松弛项，分类条件式为,约束条件2：线性可分条件下的分类间隔最大，线性不可分时引入约束 在两个约束条件下对错分样本最小函数求极小值,10.4.3 支持向量机,支持向量机的数学表达最优分类的优化函数与最优分类函数 表达式中都含有内积运算,如果将表达式中的内积运算由内积函数来代替，将原来的特征空间作非线性变换，则优化函数成为 最优分类函数成为则称为支持向量机。,支持向量机的基本思想使用非线性的内积函数，将输入空间作非线性变换，变换到一个高维空间，然后在高维空间中确定最优分类面。非线性变换是由内积函数实现的。,支持向量机的拓扑结构支持向量机的拓扑结构类似一个RBF神经网络。输入层：中间层：基于s个支持向量的内积变换,输出层：（决策规则）加权系数：,常用的内积函数不同的内积函数表现为不同的支持向量机算法，常用的内积函数有以下几类（1）多项式内积函数（2）高斯核内积函数（3）S型内积函数,（4）指数型内积函数（5）线性内积函数线性内积函数，是内积函数的一个特例。,例题 样本集合如图所示。4个样本其中x1 x2，属于第1类，y1=+1其中x3 x4，属于第2类，y2=-1,由优化函数 代入展开 利用最优化条件（1）并对Q求偏导，得到方程组,解方程组得到：显然x1不是支持向量，乘子1=0，其余样本构成支持向量，乘子不为零。利用最优化条件（2），计算最优加权系数向量w*，为样本点加权线性组合，得到,由条件方程 求得偏移量 b*=3/4最优分类面方程为,小结1 统计学习理论与支持向量机是对有限样本下模式识别的一些根本问题的系统的理论研究结果。2 解决了在机器学习中困扰多年的许多问题模型选择过学习问题非线性维数灾难局部极小问题等等3 许多传统的机器学习问题可以由支持向量机方法来等价。,4 统计学习理论与支持向量机可以作为机器学习问题的基本框架。5 存在问题许多理论问题仍然没有解决如函数子集的结构设计VC维的计算和估计问题支持向量机的内积函数选择等等,
