《人工智能7第七章机器学习33375.pptx》由会员分享，可在线阅读，更多相关《人工智能7第七章机器学习33375.pptx（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、机器学习机器学习要介绍的内容要介绍的内容l机器学习概述l统计学习理论的方法l基于符号的方法l连接主义的方法l遗传与进化的方法第七章机器学习第七章机器学习 5/11/20231机器学习机器学习的定义的定义l机器学习还没有统一的定义机器学习还没有统一的定义l机器学习的一种定义机器学习的一种定义:机器学习是一门研究机器获取新知识和新技能,并识别现有知识的学问。l另一种机器学习定义机器学习定义：如果一个计算机程序针对某类任务T的用P衡量的性能根据经验E来自我完善。那么我们称这个计算机程序在从经验E中学习，针对某类任务T，它的性能用P来衡量l任何智能系统必须具备学习的能力l学习是使得智能主体在与环境交互
2、的过程中改变自己.第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/20232机器学习研究机器学习研究的几种观点的几种观点l统计学习理论-基于统计理论进行的推断、预测等学习方法。l符号主义采用符号来表示问题域中的实体极其关系,通过对符号语言表示的规则进行搜索，试图用这些符号来推出新的、有效的并且也用这些符号表达的一般规则。l连接主义受生物神经网络系统的启发，把知识表示为由小的个体处理单元组成的网络的激活或者抑制状态模式。学习是通过训练数据来修改网络结构和连接权值来实现。l遗传和进化观点，在开始时有一组问题的后选解，根据他们解决问题的能力来进化，适者生存，并相互交叉产生下一代解，这样
3、，解不断的增强就像达尔文描述的生物世界一样第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/20233机器学习问题机器学习问题的表示的表示l系统s是要研究的对象，给定输入x，得到输出ylLM是所求的学习机，预测输出yl机器学习目的根据给定的已知训练样本，求取对系统输入输出之间依赖关系的估计，使它能够对未知输出作出尽可能准确的预测。第第七七章机器学习章机器学习 7.1 7.1概述概述输入x系统（s）背景知识输出y学习机（LM）预测输出y图机器学习问题的基本模型5/11/20234机器学习问题的形式化表示机器学习问题的形式化表示l已知变量y与输入x之间存在一定的未知依赖关系，l即存在一
4、个未知的联合概率F(x,y)，l机器学习根据n个独立同分布观测样本(x1,y1),(xn,yn)，在一组函数f(x,w)中求一个最优的函数f(x,w0)对依赖关系进行估计，使预测的期望风险最小第第七七章机器学习章机器学习 7.1 7.1概述概述l其中，f(x,w)为预测函数集，L()为损失函数l预测函数又称为学习函数或学习模型5/11/20235机器学习中的三类基本问题l模式识别l函数逼近l概率密度第第七七章机器学习章机器学习 7.1 7.1概述概述输入x系统（s）背景知识输出y学习机（LM）预测输出y5/11/20236模式识别问题的损失函数l模式识别问题，其实是个分类问题l多模式识别问题可
5、以分解成若干个两模式识别问题l预测函数可只考虑二值函数ly是只取0，1l损失函数可定义为：第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/20237函数逼近问题的损失函数ly是连续变量，是x的函数lf(x,w)是实函数l损失函数可定义为第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/20238概率密度估计问题的损失函数l学习的目的是根据训练样本确定x的概率分布。l将密度函数记为p(x,w)，l损失函数可以定义为：第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/20239经验风险l期望风险是预测函数在整个样本空间上出错率的数学期望l期望风险必须依赖于联合
6、概率的信息l联合概率未知，因此期望风险实际上不可求l传统的学习方法采用了经验风险来近似期望风险l定义经验风险第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202310经验风险最小化l经验风险为训练样本集上的平均错误率l设计学习函数使经验风险最小化。l经验风险最小化与期望风险最小化的等价前提是样本数据足够多l只有在样本数趋于无穷大时，其性能才有理论上的保证。l但在小样本的情况下，期望风险最小化到经验风险最小化并没有可靠的理论依据，只是直观上合理的想当然做法。l在实际应用中，一般难以取得理想的效果。第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202311推广能力（
7、泛化能力）l学习机器对未来输出进行正确预测的能力称为推广能力（或泛化能力）。l在某些情况下，当训练误差过小反而会导致推广能力的下降这就是过学习问题。l出现过学习现象的原因：一是因为学习样本不充分；二是学习机器设计不合理。这两个问题是互相关联的。第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202312预测问题举例预测问题举例 l绿色曲线：y=sin(2x)l蓝点：有随机噪声的样本l目标：曲线拟合，以便对新的输入值x，预测输出y第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202313多项式曲线拟合（回归）多项式曲线拟合（回归）第第七七章机器学习章机器学习 7.1
8、 7.1概述概述l学习，首先要选择一种模型形式l这里，我们选择多项式曲线l由于多项式对于未知参数是线性的l这种模型称为线性模型5/11/202314确定参数确定参数 w w第第七七章机器学习章机器学习 7.1 7.1概述概述l如何训练模型（确定w）l因为是线性模型l风险函数选择误差平方和l我们要确定我们要确定w，使风险最小，使风险最小5/11/202315 多项式次数多项式次数M的选择的选择thebestfittothefunction第第七七章机器学习章机器学习 7.1 7.1概述概述l欠拟合：对数据拟合差l表示性差l过拟合：对训练数据精确拟合，对函数表示差5/11/202316测试数据进行
9、评价测试数据进行评价均方根(RMS)误差(风险):N:标准化平方根:在同一尺度下度量ERMS第第七七章机器学习章机器学习 7.1 7.1概述概述l从图中看出：泛化性依赖Ml选择：M=3-9l过拟合：对训练数据精确拟合，对函数表示差l在M=9，为什么会震荡？5/11/202317多项式系数多项式系数 第第七七章机器学习章机器学习 7.1 7.1概述概述l用不同次数下的w，考察欠拟合与过拟合问题l随着M的增加，为了拟合随机噪音，w在变大5/11/202318数据集规模产生的影响数据集规模产生的影响数据集越大，拟合数据的模型就越灵活第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202
10、319预测函数复杂性与泛化能力预测函数复杂性与泛化能力 l从前例可以看出：“最优拟合函数”不一定能正确代表原来的函数模型。l原因是：用一个复杂的模型去拟合有限的样本，结果就会丧失推广能力。l有限样本下学习机器的复杂性与推广性之间的矛盾。l有时，已知问题是某个比较复杂的模型：由于训练样本有限，如用复杂预测函数去学习效果通常不如用相对简单的预测函数。第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202320统计学习理论的主要内容统计学习理论的主要内容l统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理论。l它从理论上较系统地研究了：经验风险最小化规则成立的条件、有限样本下
11、经验风险与期望风险的关系如何利用这些理论找到新的学习原则和方法l其主要内容包括如下四个方面：经验风险最小化原则下统计学习一致性的条件；在这些条件下关于统计学习方法推广性的界的结论；在这些界的基础上建立的小样本归纳推理原则；实现这些新的原则的实际方法。第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202321学习过程一致性学习过程一致性l学习一致性的结论是统计学习理论的基础l一致性条件，保证在经验风险最小化原则下得到的最优方法当样本无穷大时趋近于使期望风险最小的最优结果。l学习过程的一致性：(x1,y1)，(xn.yn)是n个独立同分布样本f(x,w*)最优预测函数Min(Rem
12、p(w)=Remp(w*|n)是经验风险最小值R(w*|n)为相应的真实风险值（期望风险值）R(w0)=inf(R(w)为实际的最小真实风险值（期望风险值）如果：Remp(w*|n)R(w0)，R(w*|n)R(w0)第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202322学习过程一致性的条件学习过程一致性的条件l非平凡一致性:如果预测函数集中每个函数都满足一致性l学习理论关键定理：对于有界的损失函数，经验风险最小化学习一致的充分必要条件是经验风险在如下意义上一致地收敛于真实风险其中，P表示概率，Remp(w)、R(w)分别表示在n个样本下的经验风险和真实风险。第第七七章机器
13、学习章机器学习 7.1 7.1概述概述5/11/202323定义指标，衡量函数集性能定义指标，衡量函数集性能l学习理论关键定理没有给出什么样的学习方法能够满足这些条件l为了研究函数集在经验风险最小化原则下的学习一致性问题和一致性收敛的速度l定义一些指标：指示函数集的熵（VC熵）和生长函数退火的VC熵VC维第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202324指示函数集的熵和生长函数指示函数集的熵和生长函数l指示函数集：f(x,w)l样本集：Zn=zi=(xi,yi)i=1,nl函数集中的函数能对这组样本实现的不同种分类数目：N(Zn)l随机熵：H(Zn)=In(N(Zn)(
14、函数集在这组样本上的)l指示函数集的熵（VC熵）：H(n)=E(In(N(Zn)(与样本无关)l由于VC熵与样本的分布有关l生长函数：G(n)=In(max(N(Zn)第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202325退火的VC熵l定义为：Hann(n)=In(E(N(Zn)lJensen不等式aiInxiIn(aixi)lH(n)Hann(n)G(n)nIn2第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202326学习过程一致收敛的充分必要条件l函数集学习过程一致收敛的充分必要条件是对任意的样本分布，都有limG(n)/n=0这时学习过程收敛速度一定
15、是快的l函数集学习收敛速度快的充分必要条件是limHann(n)/n=0第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202327生长函数的性质l所有函数集的生长函数或者：G(n)=nIn2l或者G(n)hIn(n/h+1)nhl其中，h是一个整数l可以看出，生长函数要么是线性的，要么以参数为h的对数函数为上界。第第七七章机器学习章机器学习 7.1 7.1概述概述G(n)nIn2nhhIn(n/h+1)5/11/202328VC维l函数集能够把样本集打散：函数集中的函数有2h种形式把h个样本的样本集分为两类，l指示函数集的VC维：函数集能够打散的最大样本集的h如果指示函数集的生
16、长函数是线性的，其VC维为无穷大如果生长函数以参数为h的对数函数为上界，则函数集的VC维是hlVC维是对由学习机器实现的分类函数族的容量或表示能力的测度。第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202329VC维与学习过程一致性l经验风险最小化学习过程一致的充分必要条件是函数集的VC维有限，l且这时收敛速度是快的。第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202330推广性的界l对于两类分类问题，对指示函数集中的所有函数，经验风险和实际风险之间至少以概率1-满足：第第七七章机器学习章机器学习 7.1 7.1概述概述l称为置信范围，或VC信任l置信范围既
17、受置信概率概率1-的影响，也受VC维和样本数目的影响l当n/h较小时，置信范围较大，用经验风险近似真实风险就有较大的误差l当n/h较大，则置信范围就会很小，经验风险最小化的最优解就接近实际的最优解。5/11/202331对对推广性界的说明推广性界的说明l推广性的界是对于最坏情况的结论l给出的界在很多情况下是松弛的，尤其当VC维比较高时更是如此。lVC维无穷大时这个界就不再成立l这种界往往只在对同一类学习函数进行比较时是有效的，用于指导从函数集中选择最优的函数l在不同函数集之间比较却不一定成立。第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202332函数子集序列（子集结构）函数
18、子集序列（子集结构）l经验风险最小化原则在样本数目有限时不合理：需要同时最小化经验风险和置信范围。l考虑分解函数集S=f(x,w)为一个函数子集序列（或叫子集结构）:S1S2SnS:使各个子集能够按照置信范围的大小排列，也就是按VC维的大小排列，即：h1h2hnhSl同一个子集中置信范围就相同第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202333结构风险最小化原则结构风险最小化原则SRMl在每一个子集中寻找最小经验风险l通常它随着子集复杂度的增加而减小l选择最小经验风险与置信范围之和最小的子集，就可以达到期望风险的最小，l这个子集中使经验风险最小的函数就是要求的最优函数。第
19、第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202334 Sn S*经验风险经验风险置信范围置信范围真实风险的界真实风险的界h1h*hnhS1S*Sn结构风险最小化图示结构风险最小化图示风险风险第第七七章机器学习章机器学习 7.1 7.1概述概述欠学习欠学习过学习过学习5/11/202335合理的函数子集结构应满足合理的函数子集结构应满足l两个基本条件：l一是每个子集的VC维是有限的且满足h1h2hnhSl二是每个子集中的函数对应的损失函数或者是有界的非负函数，或者对一定的参数对（p,k）满足如下关系第第七七章机器学习章机器学习 7.1 7.1概述概述lQ(z,)为损失函数5/
20、11/202336结构风险最小化原则下，分类器的设计过程结构风险最小化原则下，分类器的设计过程l设计过程包括以下两方面任务：选择一个适当的函数子集，使之对问题来说有最优的分类能力；从这个子集中选择一个判别函数，使经验风险最小。l第一步相当于模型选择，而第二步则相当于在确定了函数形式后的参数估计。第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/202337寻找具体使用结构风险最小化原则的方法寻找具体使用结构风险最小化原则的方法l结构风险最小化原则比经验风险最小化原则更科学l最终目的是在经验风险和置信范围之间进行折中l实际上实施这一原则并不容易l如果能够找到一种子集划分方法，使得不必
21、逐一计算就可以知道每个子集中所可能取得的最小经验风险，l则两步任务就可以分开进行：先选择使置信范围最小的子集，然后在其中选择最优函数。l结构风险最小化的一般原则可以用不同的方法实现l支持向量机是其中最成功的一个通过固定经验风险而最小化置信范围实现的。第第七七章机器学习章机器学习 7.1 7.1概述概述5/11/2023387.2 线性分类器线性分类器第第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器5/11/202339线性分类器定义线性分类器定义l在二类分类问题中,如果我们的学习函数选择为：第第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器l这种学习函数称为线
22、性分类器5/11/202340a考虑对下面情况的分类考虑对下面情况的分类第第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器5/11/202341采样线性分类，可以这样采样线性分类，可以这样第第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器5/11/202342采样线性分类，也可以这样采样线性分类，也可以这样Copyright 2001,2003,Andrew W.Moore第第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器5/11/202343采样线性分类，还可以这样采样线性分类，还可以这样Copyright 2001,2003,Andrew W
23、.Moore第第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器5/11/202344分类超平面分类超平面l有训练集：(xi,yi),i=1,2,N;yi+1,-1l如果分类函数y=wx+b，能够正确训练集l超平面（Hyperplane）:wx+b=0l称为分类超平面第第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器5/11/202345分类间隔分类间隔l样本点(xi,yi),到超平面H的函数间隔：yi(wxi+b)l几何间隔:只需换成归一化函数(w/|w|，b/|w|)l分类间隔（样本集到分类超平面的间隔）:样本集中所有点到分类超平面间隔（几何间隔）中的最小值第
24、第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器5/11/202346感知机算法感知机算法第第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器l给定线性可分样集S，学习率R+lW0=0,b0=0,k;lR=max|xi|;ldolk=0;lfor(i=1;in;i+)lif(yi(wkxi+bk)0)lwk+1=wk+yixi;lbk+1=bk+yiR2;lk+;lwhile(k0)5/11/202347分类间隔与误分次数的关系分类间隔与误分次数的关系l在采样感知机算法时，在采样感知机算法时，l若分类间隔=，R=max|xi|i=1,.,n，则：第第七七章机器学习
25、章机器学习 7.2 7.2 线性分类器线性分类器l误分次数一定程度上代表分类器的误差l分类间隔越大的解，它的误差上界越小。l最大化分类间隔成了训练阶段的目标5/11/202348最优分类面最优分类面l要求分类面能将两类正确分开(训练错误率为0),l且使分类间隔最大第第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器5/11/202349固定斜率时，最大间隔分固定斜率时，最大间隔分类面的导出类面的导出l设过两类中最靠近分类面的点的线分别为：wx+b=k1l1wx+b=k2l2l平行移动分类面，使：K1=k2=kl令w=w/k,b=b/k,则l1,l2变为：wx+b=1wx+b=1l
26、分类面则为：wx+b=0第第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器wx+b1wx+b非线性分划代价：2维空间内积6维空间内积非线性分类非线性分类5/11/202366为此，引进函数有比较(2)和(3)，可以发现这是一个重要的等式，提示6维空间中的内积可以通过计算中2维空间中的内积得到。非线性分类非线性分类5/11/202367实现非线性分类的思想实现非线性分类的思想给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数，一旦选定了函数，就可以求解最优化问题得，而决策函数5/11/202368决策函数其中实现非线性
27、分类的思想实现非线性分类的思想5/11/202369设是中的一个子集。称定义在上的函数是核函数(正定核或核)，如果存在着从到某一个空间的映射使得其中表示中的内积核函数核函数(核或正定核核或正定核)定义定义5/11/202370l多项式内核l径向基函数内核RBFlSigmoind内核目前研究最多的核函数主要有三类：得到q阶多项式分类器每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定包含一个隐层的多层感知器，隐层节点数是由算法自动确定核函数的选择核函数的选择5/11/202371多项式内核多项式内核Thekindofkernelrepresentstheinnerproductoftw
28、ovector(point)inafeaturespaceofdimension.Forexample5/11/202372Edgar Osuna(Cambridge,MA)等人在等人在IEEE NNSP97发表发表了了An Improved Training Algorithm for Support Vector Machines,提出了提出了SVM的分解算法，即将原问题分解为若的分解算法，即将原问题分解为若干个子问题，按照某种迭代策略，通过反复求解子问题，干个子问题，按照某种迭代策略，通过反复求解子问题，最终使得结果收敛于原问题的最优解。最终使得结果收敛于原问题的最优解。传统的利用二次型
29、优化技术解决对偶问题时：传统的利用二次型优化技术解决对偶问题时：n 需要计算存储核函数矩阵。当样本点数较大时，需要很大需要计算存储核函数矩阵。当样本点数较大时，需要很大的存储空间。例如：当样本点超过的存储空间。例如：当样本点超过4000时，存储核函数矩时，存储核函数矩阵就需要多达阵就需要多达128兆内存；兆内存；n SVM在二次型寻优过程中要进行大量的矩阵运算，通常在二次型寻优过程中要进行大量的矩阵运算，通常寻优算法占用了算法时间的主要部分。寻优算法占用了算法时间的主要部分。SVMSVM寻优寻优算法算法5/11/202373考虑去掉Lagrange乘子等于零的训练样本不会影响原问题的解，采用一
30、部分样本构成工作样本集进行训练，移除其中的非支持向量，并把训练结果对剩余样本进行检验，将不符合KKT条件的样本与本次结果的支持向量合并成为一个新的工作集。然后重新训练，如此重复获得最优结果。例如：基于这种思路的算法。根据子问题的划分和迭代策略的不同，大致分为：1.块算法(ChunkingAlgorithm)：SVM寻优寻优算法算法5/11/202374SMO使用了块与分解技术，而SMO算法则将分解算法思想推向极致，每次迭代仅优化两个点的最小子集，其威力在于两个数据点的优化问题可以获得解析解，从而不需要将二次规划优化算法作为算法一部分。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法
31、在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。块算法(ChunkingAlgorithm)：SVM寻优寻优算法算法5/11/202375SMO算法每次迭代时，在可行的区域内选择两点，最大化目标函数，从而优化两个点的最小子集。无论何时，当一个乘子被更新时，调整另一个乘子来保证线性约束条件成立，保证解不离开可行区域。每步SMO选择两个参数优化，其他参数固定，可以获得解析解。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。SVM寻优寻优算法算法5/11
32、/202376SVM寻优寻优算法算法类别名称测试样本数错误分类数准确度（%）政治146497.26军事830100经济137397.81法律32293.75农业106298.11体育90198.89卫生34197.06工业87297.70科技111298.20交通40197.50生活91198.90宗教30100天气24291.67合计9842197.875/11/202377SMO算法核缓存算法SMO算法在每次迭代只选择两个样本向量优化目标函数，不需要核矩阵。虽然没有核矩阵操作，但仍需要计算被选向量和训练集中所有样本向量的核函数，计算次数为2n（n为训练集中的样本数）。如果训练集中的样本选取
33、有误，在噪声比较多的情况下，收敛会很慢，迭代次数很多，则核函数的计算量也是非常可观的，SMO 算法的优点就完成失去了。同时，考虑到文本分类的文本向量一般维数比较大，核函数的计算将会非常耗时，尤其在高价多项式核和高斯核等核函数的计算中表现更加明显。SVM寻优寻优算法算法5/11/202378SMO算法核缓存算法在内存中为SMO算法核函数开辟n行m列的核矩阵空间。其中：n为训练集中的样本数；m是为可调节参数，根据实际的内存大小进行调整，每列存放训练集中某个样本向量与训练集中所有样本向量的核函数计算结果列表。在核矩阵列头生成m个节点的双向循环链表队列，每个节点指向核矩阵的列，通过双向循环链表队列实现
34、核矩阵中的核函数列唤入唤出操作。同时，为了实现样本向量的核函数列的快速查找，为每个训练样本向量设计了快速索引列表，通过索引列表判断该训练样本向量的核函数列是否在核矩阵中，并确定在哪一列。SVM寻优寻优算法算法5/11/202379SVM寻优寻优算法算法l选择一个训练集，通过调整核缓冲参数的大小，记录不同核缓存大小情况下训练时间，结果如下表：核缓存大小(Mb)训练样本数核矩阵迭代次数训练时间(M:S)156245624*23407267:061056245624*233407263:502056245624*466407262:413056245624*699407261:56405624562
35、4*932407261:295056245624*1165407261:236056245624*1398407261:087056245624*1631407261:058056245624*1864407261:049056245624*2097407261:0710056245624*2330407261:3725056245624*5624407261:125/11/202380通过引入核缓存机制，有效的改进了通过引入核缓存机制，有效的改进了SMOSMO算法，提算法，提高了文本分类的训练速度。在核缓存机制中采用简高了文本分类的训练速度。在核缓存机制中采用简单的单的hashhash查找算
36、法和队列查找算法和队列FILOFILO算法，有效提高了核算法，有效提高了核矩阵查找和唤入唤出操作的效率。设置核矩阵列参矩阵查找和唤入唤出操作的效率。设置核矩阵列参数，通过调节列参数，可以灵活的根据系统运行情数，通过调节列参数，可以灵活的根据系统运行情况调整训练的时间和空间开销，避免因系统空间开况调整训练的时间和空间开销，避免因系统空间开销过大使系统运行效率下降，反而影响训练速度。销过大使系统运行效率下降，反而影响训练速度。SVM寻优寻优算法算法5/11/202381活动向量集选择算法 当训练样本数非常大的时候，如果系统能够提供的核缓冲当训练样本数非常大的时候，如果系统能够提供的核缓冲大小很有限
37、，那么能够同时保存在核缓冲中训练样本的核大小很有限，那么能够同时保存在核缓冲中训练样本的核函数数目在训练样本数中所占比例将非常的小。在训练过函数数目在训练样本数中所占比例将非常的小。在训练过程中，训练样本在核缓冲中的核函数命中率将显著下降，程中，训练样本在核缓冲中的核函数命中率将显著下降，导致核缓冲中的核函数被频繁的唤入唤出，而每执行一次导致核缓冲中的核函数被频繁的唤入唤出，而每执行一次唤入唤出操作将引起系统重新计算训练样本的核函数，核唤入唤出操作将引起系统重新计算训练样本的核函数，核缓存的作用被很大程度的削弱了。如果出现这样的情况，缓存的作用被很大程度的削弱了。如果出现这样的情况，要么增加系
38、统的存储空间；要么减少训练样本数，才能提要么增加系统的存储空间；要么减少训练样本数，才能提高系统的训练速度。为解决训练样本数多，系统内存空间高系统的训练速度。为解决训练样本数多，系统内存空间小的矛盾，本文通过活动向量集选择算法，比较好地解决小的矛盾，本文通过活动向量集选择算法，比较好地解决了这个问题。了这个问题。SVM寻优寻优算法算法5/11/202382活动向量集选择算法 算法的主要思想是：定期检查训练样本集，在收敛前预先算法的主要思想是：定期检查训练样本集，在收敛前预先确定训练样本集中一些边界上的点（确定训练样本集中一些边界上的点（alpha=0alpha=0，或者，或者alpha=Cal
39、pha=C）是否以后不再被启发式选择，或者不再被判定为）是否以后不再被启发式选择，或者不再被判定为最有可能违例，如果存在这样的点，将它们从训练样本集最有可能违例，如果存在这样的点，将它们从训练样本集中剔除出去，减少参加训练的样本数。该算法基于如下的中剔除出去，减少参加训练的样本数。该算法基于如下的认识：经过多次迭代后，如果样本的拉格朗日乘子一直为认识：经过多次迭代后，如果样本的拉格朗日乘子一直为0 0，该点被当前估计的支持向量集所确定的超平面区分得很，该点被当前估计的支持向量集所确定的超平面区分得很开，即使以后支持向量集发生变化，该点也不会是最靠近开，即使以后支持向量集发生变化，该点也不会是最
40、靠近超平面的点，则可以确定该样本不是支持向量；经过多次超平面的点，则可以确定该样本不是支持向量；经过多次迭代后，如果样本的拉格朗日乘子一直为非常大的迭代后，如果样本的拉格朗日乘子一直为非常大的C C常数，常数，即使以后支持向量集发生变化，该点也不会远离超平面，即使以后支持向量集发生变化，该点也不会远离超平面，则可以确定该样本是上边界处的支持向量则可以确定该样本是上边界处的支持向量SVM寻优寻优算法算法5/11/202383活动向量集选择算法 这样就可以在这样就可以在SMO算法收敛前，提前将边界上的点从训算法收敛前，提前将边界上的点从训练样本集中剔除，逐渐缩小参加训练的活动样本集，从而练样本集中
41、剔除，逐渐缩小参加训练的活动样本集，从而减少减少SMO算法对核缓存空间的要求，提高训练速度。算法对核缓存空间的要求，提高训练速度。训练开始前，训练活动集样本初始化为全部训练样本。每训练开始前，训练活动集样本初始化为全部训练样本。每经过一定次数的迭代（比如迭代经过一定次数的迭代（比如迭代1000次），如果算法还没次），如果算法还没有收敛，应检查活动集中的向量，检查是否有训练样本可有收敛，应检查活动集中的向量，检查是否有训练样本可以不参加迭代运算。以不参加迭代运算。检查完当前活动向量集中所有样本后，产生了新的活动向检查完当前活动向量集中所有样本后，产生了新的活动向量集。如果新的活动向量集的样本数减
42、少一成以上（含一量集。如果新的活动向量集的样本数减少一成以上（含一成），则可以收缩当前活动向量集，用新的活动向量集替成），则可以收缩当前活动向量集，用新的活动向量集替换当前活动向量集。当活动向量集的样本数减少到一定的换当前活动向量集。当活动向量集的样本数减少到一定的程度，对核缓存空间的要求不是很大的时候，继续减少训程度，对核缓存空间的要求不是很大的时候，继续减少训练样本对训练速度的提高就非常有限了，这时就没有必要练样本对训练速度的提高就非常有限了，这时就没有必要再减少训练样本了。再减少训练样本了。SVM寻优寻优算法算法5/11/202384将工作样本集的大小固定在算法速度可以容忍的限度内，将工
43、作样本集的大小固定在算法速度可以容忍的限度内，迭代过程选择一种合适的换入换出策略，将剩余样本中的迭代过程选择一种合适的换入换出策略，将剩余样本中的一部分与工作样本集中的样本进行等量交换，即使支持向一部分与工作样本集中的样本进行等量交换，即使支持向量的个数超过工作样本集的大小，也不改变工作样本集的量的个数超过工作样本集的大小，也不改变工作样本集的规模，而只对支持向量中的一部分进行优化。规模，而只对支持向量中的一部分进行优化。例如例如:算法算法2.固定工作样本集固定工作样本集(Osuna et al.)：SVM寻优寻优算法算法5/11/202385SVM applicationslPatternr
44、ecognitionFeatures:wordscountslDNAarrayexpressiondataanalysisFeatures:expr.levelsindiff.conditionslProteinclassificationoFeatures:AAcomposition5/11/202386HandwrittenDigitsRecognition5/11/202387ApplyingSVMstoFaceDetectionlTheSVMface-detectionsystem1.Rescale the 1.Rescale the input image input image s
45、everal timesseveral times2.Cut 19x19 2.Cut 19x19 window patterns window patterns out of the out of the scaled imagescaled image3.Preprocess the 3.Preprocess the window using masking,window using masking,light correction and light correction and histogram equalizationhistogram equalization4.Classify
46、the 4.Classify the pattern using pattern using the SVMthe SVM5.If the class corresponds 5.If the class corresponds to a face,draw a rectangle to a face,draw a rectangle around the face in the around the face in the output image.output image.5/11/202388ApplyingSVMstoFaceDetectionlExperimentalresultso
47、nstaticimagesSetA:313high-quality,samenumberoffacesSetB:23mixedquality,totalof155faces5/11/202389ApplyingSVMstoFaceDetectionlExtensiontoareal-timesystemAn example An example of the skin of the skin detection detection module module implementeimplemented using d using SVMsSVMsFace Face Detection Dete
48、ction on the PC-on the PC-based based Color Real Color Real Time Time SystemSystem5/11/202390References5/11/202391Questions?!5/11/202392EBL的初始状态的初始状态一、一个目标概念依赖与具体的应用，可以是一个分类，要证明的定理，达到目标的一个计划，问题求解程序的启发式信息等二、一个训练实例目标概念的实例三、领域知识用于解释训练实例如何成为目标概念的规则和事实集合四、操作标准概念定义可以采取的形式的某种方式的描述第第七七章机器学习章机器学习 7.2 7.2 线性分
49、类器线性分类器5/11/202393什么时候物体是一个杯子什么时候物体是一个杯子l我们讨论EBL采用这个例子。l目标概念：一条规则，可以用来推断一个物体是否是一个杯子promise(X)-cup(X)(promise是一个合取表达式)l领域知识：liftable(X)holds_liquid(X)-cup(X)part(Z,W)concave(W)points_up(W)-holds_liquid(X)light(Y)part(Y,handle)-liftable(Y)samll(A)-light(A)made_of(A,feathers)-light(A)第第七七章机器学习章机器学习 7.2
50、 7.2 线性分类器线性分类器5/11/202394什么时候物体是一个杯子什么时候物体是一个杯子(续一续一)l训练实例cup(obj1)small(obj1)part(obj1,handle)owns(bob,obj1)part(obj1,bottom)part(obj1,bowl)points_up(bowl)concave(bowl)color(obj1,red)l操作标准需要目标概念用物体的可以观察的结构化的属性来定义第第七七章机器学习章机器学习 7.2 7.2 线性分类器线性分类器5/11/202395解释实例解释实例cup(obj1)Holds_liquid(obj1)Points_