人工智能7第七章机器学习

12019/8/1机器学习要介绍的内容机器学习概述统计学习理论的方法基于符号的方法连接主义的方法遗传与进化的方法第七章机器学习22019/8/1机器学习的定义机器学习还没有统一的定义机器学习的一种定义:机器学习是一门研究机器获取新知识和新技能,并识别现有知识的学问。另一种机器学习定义：如果一个计算机程序针对某类任务T的用P衡量的性能根据经验E来自我完善。那么我们称这个计算机程序在从经验E中学习，针对某类任务T，它的性能用P来衡量任何智能系统必须具备学习的能力学习是使得智能主体在与环境交互的过程中改变自己.第七章机器学习7.1概述32019/8/1机器学习研究的几种观点统计学习理论--基于统计理论进行的推断、预测等学习方法。符号主义采用符号来表示问题域中的实体极其关系,通过对符号语言表示的规则进行搜索，试图用这些符号来推出新的、有效的并且也用这些符号表达的一般规则。连接主义受生物神经网络系统的启发，把知识表示为由小的个体处理单元组成的网络的激活或者抑制状态模式。学习是通过训练数据来修改网络结构和连接权值来实现。遗传和进化观点，在开始时有一组问题的后选解，根据他们解决问题的能力来进化，适者生存，并相互交叉产生下一代解，这样，解不断的增强就像达尔文描述的生物世界一样第七章机器学习7.1概述42019/8/1机器学习问题的表示系统s是要研究的对象，给定输入x，得到输出yLM是所求的学习机，预测输出y’机器学习目的根据给定的已知训练样本，求取对系统输入／输出之间依赖关系的估计，使它能够对未知输出作出尽可能准确的预测。第七章机器学习7.1概述输入x系统（s）背景知识输出y学习机（LM）预测输出y’图机器学习问题的基本模型52019/8/1机器学习问题的形式化表示已知变量y与输入x之间存在一定的未知依赖关系，即存在一个未知的联合概率F(x,y)，机器学习根据n个独立同分布观测样本(x1,y1),…(xn,yn)，在一组函数{f(x,w)}中求一个最优的函数f(x,w0)对依赖关系进行估计，使预测的期望风险最小第七章机器学习7.1概述),()),(,()(yxdFwxfyLwR其中，{f(x,w)}为预测函数集，L()为损失函数预测函数又称为学习函数或学习模型62019/8/1机器学习中的三类基本问题模式识别函数逼近概率密度第七章机器学习7.1概述输入x系统（s）背景知识输出y学习机（LM）预测输出y’72019/8/1模式识别问题的损失函数模式识别问题，其实是个分类问题多模式识别问题可以分解成若干个两模式识别问题预测函数可只考虑二值函数y是只取0，1损失函数可定义为：第七章机器学习7.1概述),(if1),(if0)),(,(wxfxwxfxwxfyL82019/8/1函数逼近问题的损失函数y是连续变量，是x的函数f(x,w)是实函数损失函数可定义为第七章机器学习7.1概述2)),(()),(,(wxfywxfyL92019/8/1概率密度估计问题的损失函数学习的目的是根据训练样本确定x的概率分布。将密度函数记为p(x,w)，损失函数可以定义为：第七章机器学习7.1概述)),(ln()),((wxpwxpL102019/8/1经验风险期望风险是预测函数在整个样本空间上出错率的数学期望期望风险必须依赖于联合概率的信息联合概率未知，因此期望风险实际上不可求传统的学习方法采用了经验风险来近似期望风险定义经验风险第七章机器学习7.1概述)),(,(1)(1wxfyLnwRiniiemp112019/8/1经验风险最小化经验风险为训练样本集上的平均错误率设计学习函数使经验风险最小化。经验风险最小化与期望风险最小化的等价前提是样本数据足够多只有在样本数趋于无穷大时，其性能才有理论上的保证。但在小样本的情况下，期望风险最小化到经验风险最小化并没有可靠的理论依据，只是直观上合理的想当然做法。在实际应用中，一般难以取得理想的效果。第七章机器学习7.1概述122019/8/1推广能力（泛化能力）学习机器对未来输出进行正确预测的能力称为推广能力（或泛化能力）。在某些情况下，当训练误差过小反而会导致推广能力的下降这就是过学习问题。出现过学习现象的原因：一是因为学习样本不充分；二是学习机器设计不合理。这两个问题是互相关联的。第七章机器学习7.1概述132019/8/1预测问题举例绿色曲线：y=sin(2πx)蓝点：有随机噪声的样本目标：曲线拟合，以便对新的输入值x’，预测输出y’第七章机器学习7.1概述142019/8/1多项式曲线拟合（回归）第七章机器学习7.1概述学习，首先要选择一种模型形式这里，我们选择多项式曲线由于多项式对于未知参数是线性的这种模型称为线性模型152019/8/1确定参数w第七章机器学习7.1概述如何训练模型（确定w）因为是线性模型风险函数选择误差平方和我们要确定w，使风险最小21)),((21)(nnNntwxywR162019/8/1多项式次数M的选择thebestfittothefunction第七章机器学习7.1概述欠拟合：对数据拟合差表示性差过拟合：对训练数据精确拟合，对函数表示差172019/8/1测试数据进行评价均方根(RMS)误差(风险):N:标准化平方根:在同一尺度下度量ERMS第七章机器学习7.1概述从图中看出：泛化性依赖M选择：M=3-9过拟合：对训练数据精确拟合，对函数表示差在M=9，为什么会震荡？182019/8/1多项式系数第七章机器学习7.1概述用不同次数下的w，考察欠拟合与过拟合问题随着M的增加，为了拟合随机噪音，w在变大192019/8/1数据集规模产生的影响数据集越大，拟合数据的模型就越灵活第七章机器学习7.1概述202019/8/1预测函数复杂性与泛化能力从前例可以看出：“最优拟合函数”不一定能正确代表原来的函数模型。原因是：用一个复杂的模型去拟合有限的样本，结果就会丧失推广能力。有限样本下学习机器的复杂性与推广性之间的矛盾。有时，已知问题是某个比较复杂的模型：由于训练样本有限，如用复杂预测函数去学习效果通常不如用相对简单的预测函数。第七章机器学习7.1概述212019/8/1统计学习理论的主要内容统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理论。它从理论上较系统地研究了：经验风险最小化规则成立的条件、有限样本下经验风险与期望风险的关系如何利用这些理论找到新的学习原则和方法其主要内容包括如下四个方面：①经验风险最小化原则下统计学习一致性的条件；②在这些条件下关于统计学习方法推广性的界的结论；③在这些界的基础上建立的小样本归纳推理原则；④实现这些新的原则的实际方法。第七章机器学习7.1概述222019/8/1学习过程一致性学习一致性的结论是统计学习理论的基础一致性条件，保证在经验风险最小化原则下得到的最优方法当样本无穷大时趋近于使期望风险最小的最优结果。学习过程的一致性：(x1,y1)…，(xn.yn)是n个独立同分布样本f(x,w*)最优预测函数Min(Remp(w))=Remp(w*|n)是经验风险最小值R(w*|n)为相应的真实风险值（期望风险值）R(w0)=inf(R(w))为实际的最小真实风险值（期望风险值）如果：Remp(w*|n)→R(w0)，R(w*|n)→R(w0)第七章机器学习7.1概述232019/8/1学习过程一致性的条件非平凡一致性:如果预测函数集中每个函数都满足一致性学习理论关键定理：对于有界的损失函数，经验风险最小化学习一致的充分必要条件是经验风险在如下意义上一致地收敛于真实风险其中，P表示概率，Remp(w)、R(w)分别表示在n个样本下的经验风险和真实风险。第七章机器学习7.1概述00)))()((sup(limwRwRPempwn242019/8/1定义指标，衡量函数集性能学习理论关键定理没有给出什么样的学习方法能够满足这些条件为了研究函数集在经验风险最小化原则下的学习一致性问题和一致性收敛的速度定义一些指标：指示函数集的熵（VC熵）和生长函数退火的VC熵VC维第七章机器学习7.1概述252019/8/1指示函数集的熵和生长函数指示函数集：{f(x,w)}样本集：Zn={zi=(xi,yi)i=1,…n}函数集中的函数能对这组样本实现的不同种分类数目：N(Zn)随机熵：H(Zn)=In(N(Zn))(函数集在这组样本上的)指示函数集的熵（VC熵）：H(n)=E(In(N(Zn)))(与样本无关)由于VC熵与样本的分布有关生长函数：G(n)=In(max(N(Zn)))第七章机器学习7.1概述262019/8/1退火的VC熵定义为：Hann(n)=In(E(N(Zn)))∵Jensen不等式∑aiInxi≤In(∑aixi)∴H(n)≤Hann(n)≤G(n)≤nIn2第七章机器学习7.1概述272019/8/1学习过程一致收敛的充分必要条件函数集学习过程一致收敛的充分必要条件是对任意的样本分布，都有limG(n)/n=0这时学习过程收敛速度一定是快的函数集学习收敛速度快的充分必要条件是limHann(n)/n=0第七章机器学习7.1概述282019/8/1生长函数的性质所有函数集的生长函数或者：G(n)=nIn2或者G(n)≤hIn(n/h+1)nh其中，h是一个整数可以看出，生长函数要么是线性的，要么以参数为h的对数函数为上界。第七章机器学习7.1概述G(n)nIn2nhhIn(n/h+1)292019/8/1VC维函数集能够把样本集打散：函数集中的函数有2h种形式把h个样本的样本集分为两类，指示函数集的VC维：函数集能够打散的最大样本集的h如果指示函数集的生长函数是线性的，其VC维为无穷大如果生长函数以参数为h的对数函数为上界，则函数集的VC维是hVC维是对由学习机器实现的分类函数族的容量或表示能力的测度。第七章机器学习7.1概述302019/8/1VC维与学习过程一致性经验风险最小化学习过程一致的充分必要条件是函数集的VC维有限，且这时收敛速度是快的。第七章机器学习7.1概述312019/8/1推广性的界对于两类分类问题，对指示函数集中的所有函数，经验风险和实际风险之间至少以概率1-η满足：第七章机器学习7.1概述)())()(hnwRwRempΦ称为置信范围，或VC信任置信范围既受置信概率概率1-η的影响，也受VC维和样本数目的影响当n/h较小时，置信范围较大，用经验风险近似真实风险就有较大的误差当n/h较大，则置信范围就会很小，经验风险最小化的最优解就接近实际的最优解。322019/8/1对推广性界的说明推广性的界是对于最坏情况的结论给出的界在很多情况下是松弛的，尤其当VC维比较高时更是如此。VC维无穷大时这个界就不再成立这种界往往只在对同一类学习函数进行比较时是有效的，用于指导从函数集中选择最优的函数在不同函数集之间比较却不一定成立。第七章机器学习7.1概述332019/8/1函数子集序列（子集结构）经验风险最小化原则在样本数目有限时不合理：需要同时最小化经验风险和置信范围。考虑分解函数集S={f(x,w)}为一个函数子集序列（或叫子集结构）:S1S2…Sn…S:使各个子集能够按照置信范围φ的大小排列，也就是按VC维的大小排列，即：h1≤h2≤…≤hn≤…≤hS同一个子集中置信范围就相同第七章机器学习7.1概述342019/8/1结构风险最小化原则SRM在每一个子集中寻找最小经验风险通常它随着子集复杂度的增加而减小选择最小经验风险与置信范围之和最小的子集，就可以达到期望风险的最小，这个子集中使经验风险最小的函