人工智能机器学习讲义.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,人工智能机器学习,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,人工智能机器学习,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,人工智能机器学习,人工智能机器学习,机器学习研究,的几种观点,统计学习理论-基于统计理论进行的推断、预测等学习方法。,符号主义采用符号来表示问题域中的实体极其关系,通过对符号语言表示的规则进行搜索，试图用这些符号来推出新的、有效的并且也用这些符号表达的一般规则。,连接主义受生物神经网络系统的启发，,把知识表示为由小的个体处理单元组成的网络的激活或者抑制状态模式。学习是通过训练数据来修改网络结构和连接权值来实现。,遗传和进化观点，在开始时有一组问题的后选解，根据他们解决问题的能力来进化，适者生存，并相互交叉产生下一代解，这样，解不断的增强就像达尔文描述的生物世界一样,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,机器学习问题,的表示,系统s是要研究的对象，给定输入x，得到输出y,LM是所求的学习机，预测输出y,机器学习目的根据给定的已知训练样本，求取对系统输入输出之间依赖关系的估计，使它能够对未知输出作出尽可能准确的预测。,第,七,章机器学习,7.1概述,输入x,系统（s）,背景知识,输出y,学习机（LM）,预测输出y,图 机器学习问题的基本模型,9/14/2025,人工智能机器学习,机器学习问题的形式化表示,已知变量y与输入 x之间存在一定的未知依赖关系，,即 存在一个未知的联合概率F(x,y)，,机器学习,根据n个独立同分布观测样本(x,1,y,1,),(x,n,y,n,)，,在一组函数f(x,w)中求一个最优的函数f(x,w,0,),对依赖关系进行估计，使预测的期望风险最小,第,七,章机器学习,7.1概述,其中，f(x,w)为预测函数集，L()为损失函数,预测函数又称为学习函数或学习模型,9/14/2025,人工智能机器学习,机器学习中的三类基本问题,模式识别,函数逼近,概率密度,第,七,章机器学习,7.1概述,输入x,系统（s）,背景知识,输出y,学习机（LM）,预测输出y,9/14/2025,人工智能机器学习,模式识别问题的损失函数,模式识别问题，其实是个分类问题,多模式识别问题可以分解成若干个两模式识别问题,预测函数可只考虑二值函数,y是只取0，1,损失函数可定义为：,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,函数逼近问题的损失函数,y是连续变量，是x的函数,f(x,w)是实函数,损失函数可定义为,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,概率密度估计问题的损失函数,学习的目的是根据训练样本确定x 的概率分布。,将密度函数记为p(x,w)，,损失函数可以定义为,：,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,经验风险,期望风险 是预测函数在整个样本空间上出错率的数学期望,期望风险必须依赖于联合概率的信息,联合概率未知，因此期望风险实际上不可求,传统的学习方法采用了经验风险来近似期望风险,定义经验风险,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,经验风险最小化,经验风险为训练样本集上的平均错误率,设计学习函数使经验风险最小化。,经验风险最小化与期望风险最小化的等价前提是样本数据足够多,只有在样本数趋于无穷大时，其性能才有理论上的保证。,但在小样本的情况下，期望风险最小化到经验风险最小化并没有可靠的理论依据，只是直观上合理的想当然做法。,在实际应用中，一般难以取得理想的效果。,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,推广能力（泛化能力）,学习机器对未来输出进行正确预测的能力称为,推广能力（或泛化能力）。,在某些情况下，当训练误差过小反而会导致推广能力的下降,这就是过学习问题。,出现过学习现象的原因：,一是因为学习样本不充分；,二是学习机器设计不合理。,这两个问题是互相关联的。,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,预测问题举例,绿色曲线：,y=sin(2,x,),蓝点：有随机噪声的样本,目标：曲线拟合，以便对新的输入值x，预测输出y,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,多项式曲线拟合（回归）,第,七,章机器学习,7.1概述,学习，首先要选择一种模型形式,这里，我们选择多项式曲线,由于多项式对于未知参数是线性的,这种模型称为线性模型,9/14/2025,人工智能机器学习,确定参数,w,第,七,章机器学习,7.1概述,如何训练模型（确定w）,因为是线性模型,风险函数选择误差平方和,我们要确定w，使风险最小,9/14/2025,人工智能机器学习,多项式次数,M,的选择,the best fit to the function,第,七,章机器学习,7.1概述,欠拟合：,对数据拟合差,表示性差,过拟合：,对训练数据精确拟合，,对函数表示差,9/14/2025,人工智能机器学习,测试数据进行评价,均方根,(RMS),误差,(,风险,):,N,:标准化,平方根:在同一尺度下度量 E,RMS,第,七,章机器学习,7.1概述,从图中看出：,泛化性依赖M,选择：M=3-9,过拟合：,对训练数据精确拟合，,对函数表示差,在M=9，为什么会震荡？,9/14/2025,人工智能机器学习,多项式系数,第,七,章机器学习,7.1概述,用不同次数下的w，考察欠,拟合与过拟合,问题,随着M的增加，为了拟合随机噪音，w在变大,9/14/2025,人工智能机器学习,数据集规模产生的影响,数据集越大，拟合数据的模型就越灵活,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,预测函数复杂性与泛化能力,从前例可以看出：,“最优拟合函数”不一定能正确代表原来的函数模型。,原因是：,用一个复杂的模型去拟合有限的样本，,结果就会丧失推广能力。,有限样本下学习机器的复杂性与推广性之间的矛盾。,有时，已知问题是某个比较复杂的模型：,由于训练,样本有限，如用复杂预测函数去学习,效果通常不如用相对简单的预测函数。,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,统计学习理论的主要内容,统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理论。,它从理论上较系统地研究了：,经验风险最小化规则成立的条件、,有限样本下经验风险与期望风险的关系,如何利用这些理论找到新的学习原则和方法,其主要内容包括如下四个方面：,经验风险最小化原则下统计学习一致性的条件；,在这些条件下关于统计学习方法推广性的界的结论；,在这些界的基础上建立的小样本归纳推理原则；,实现这些新的原则的实际方法。,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,学习过程一致性,学习一致性的结论是统计学习理论的基础,一致性条件，保证在经验风险最小化原则下得到的最优方法当样本无穷大时趋近于使期望风险最小的最优结果。,学习过程的一致性：,(x,1,y,1,)，(x,n,.y,n,)是n个独立同分布样本,f(x,w*)最优预测函数,Min(R,emp,(w)=R,emp,(w*|n)是经验风险最小值,R(w*|n)为相应的真实风险值（期望风险值）,R,(w,0,)=inf(R(w)为实际的最小真实风险值（期望风险值）,如果：R,emp,(w*|n)R,(w,0,)，R(w*|n)R,(w,0,),第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,学习过程一致性的条件,非平凡一致性:,如果预测函数集中每个函数都满足一致性,学习理论关键定理：,对于有界的损失函数，经验风险最小 化学习一致的充分必要条件是经验风险在如下意义上一致地收敛于真实风险,其中，P表示概率，R,emp,(w)、R,(w)分别表示在n个样本下的经验风险和真实风险。,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,定义指标，衡量函数集性能,学习理论关键定理没有给出什么样的学习方法能够满足这些条件,为了研究函数集在经验风险最小化原则下的学习一致性问题和一致性收敛的速度,定义一些指标：,指示函数集的熵（VC熵）和生长函数,退火的VC熵,VC维,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,指示函数集的熵和生长函数,指示函数集：f(x,w),样本集：Z,n,=z,i,=(x,i,y,i,)i=1,n,函数集中的函数能对这组样本实现的不同种分类数目：N(Z,n,),随机,熵：H(Z,n,)=In(,N(Z,n,),)(,函数集在这组样本上的),指示函数集的熵（VC熵）,：,H(n)=E(In(,N(Z,n,),)(与,样本无关,),由于VC熵与样本的分布有关,生长函数：G(n)=In(max(,N(Z,n,),),第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,退火的VC熵,定义为：H,ann,(n)=In(E(,N(Z,n,),),Jensen不等式a,i,Inx,i,In(a,i,x,i,),H(n),H,ann,(n),G(n),nIn2,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,学习过程一致收敛的充分必要条件,函数集学习过程一致收敛的充分必要条件是对任意的样本分布，都有,lim G(n)/n=0,这时学习过程收敛速度一定是快的,函数集学习收敛速度快的充分必要条件是,lim,H,ann,(n)/n=0,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,生长函数,的性质,所有函数集的生长函数或者：,G(n),=nIn2,或者,G(n),h,In(n/h+1)nh,其中，h是一个整数,可以看出，生长函数要么是线性的，要么以参数为h 的对数函数为上界。,第,七,章机器学习,7.1概述,G(n),nIn2,n,h,hIn(n/h+1),9/14/2025,人工智能机器学习,VC维,函数集能够把样本集打散：,函数集中的函数,有2,h,种形式把,h个样本的样本集,分为两类，,指示函数集的VC维：,函数集能够打散的最大样本集的h,如果指示函数集的生长函数是线性的，其VC维为无穷大,如果生长函数以参数为h的对数函数为上界，则函数集的VC维是h,VC维是对由学习机器实现的分类函数族的容量或表示能力的测度。,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,VC,维与学习过程一致性,经验风险最小化学习过程一致的充分必要条件是函数集的VC维有限，,且这时收敛速度是快的。,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,推广性的界,对于两类分类问题，对指示函数集中的所有函数，经验风险和实际风险之间至少以概率1-满足：,第,七,章机器学习,7.1概述,称为置信范围，或VC信任,置信范围既受置信概率概率1-的影响，也受VC维和样本数目的影响,当n/h较小时，置信范围较大，用经验风险近似真实风险就有较大的误差,当n/h较大，则置信范围就会很小，经验风险最小化的最优解就接近实际的最优解。,9/14/2025,人工智能机器学习,对,推广性界的说明,推广性的界是对于最坏情况的结论,给出的界在很多情况下是松弛的，尤其当VC维比较高时更是如此。,VC维无穷大时这个界就不再成立,这种界往往只在对同一类学习函数进行比较时是有效的，用于指导从函数集中选择最优的函数,在不同函数集之间比较却不一定成立。,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,函数子集序列（子集结构）,经验风险最小化原则在样本数目有限时不合理：,需要同时最小化经验风险和置信范围。,考虑分解函数集S=f(x,w)为一 个函数子集序列（或叫子集结构）:,S,1,S,2,S,n,S,:,使各个子集能够按照置信范围的大小排列，也就是按VC维的大小排列，即：,h,1,h,2,h,n,h,S,同一个子集中置信范围就相同,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,结构风险最小化原则SRM,在每一个子集中寻找最小经验风险,通常它随着子集复杂度的增加而减小,选择最小经验风险与置信范围之和最小的子集，就可以达到期望风险的最小，,这个子集中使经验风险最小的函数就是要求的最优函数。,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,Sn,S*,经验风险,置信范围,真实风险的界,h1,h*,hn,h,S1,S*,Sn,结构风险最小化图示,风险,第,七,章机器学习,7.1概述,欠学习,过学习,9/14/2025,人工智能机器学习,合理的函数子集结构应满足,两个基本条件：,一是每个子集的VC维是有限的且满足,h,1,h,2,h,n,h,S,二是每个子集中的函数对应的损失函数或者是有界的非负函数，或者对一定的参数对（p,k,）满足如下关系,第,七,章机器学习,7.1概述,Q(z,)为损失函数,9/14/2025,人工智能机器学习,结构风险最小化原则下，分类器的设计过程,设计过程包括以下两方面任务：,选择一个适当的函数子集，使之对问题来说有最优的分类能力；,从这个子集中选择一个判别函数，使经验风险最小。,第一步相当于模型选择，而第二步则相当于在确定了函数形式后的参数估计。,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,寻找具体使用结构风险最小化原则的方法,结构风险最小化原则比经验风险最小化原则更科学,最终目的是在经验风险和置信范围之间进行折中,实际上实施这一原则并不容易,如果能够找到一种子集划分方法，使得不必逐一计算就可以知道每个子集中所可能取得的最小经验风险，,则两步任务就可以分开进行：,先选择使置信范围最小的子集，,然后在其中选择最优函数。,结构风险最小化的一般原则可以用不同的方法实现,支持向量机是其中最成功的一个,通过固定经验风险而最小化置信范围实现的。,第,七,章机器学习,7.1概述,9/14/2025,人工智能机器学习,7.2 线性分类器,第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,线性分类器定义,在二类分类问题中,如果我们的学习函数选择为：,第,七,章机器学习,7.2,线性分类器,这种学习函数称为线性分类器,9/14/2025,人工智能机器学习,a,考虑对下面情况的分类,第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,采样线性分类，可以这样,第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,采样线性分类，也可以这样,Copyright 2001,2003,Andrew W.Moore,第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,采样线性分类，还可以这样,Copyright 2001,2003,Andrew W.Moore,第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,分类超平面,有训练集：,(,x,i,y,i,),i=1,2,N;y,i,+1,-1,如果分类函数,y=,wx,+b,，能够正确训练集,超平面（,Hyperplane,）,:,wx,+b=0,称为分类超平面,第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,分类间隔,样本点,(,x,i,yi),到超平面H的函数间隔：,yi(wxi+b),几何间隔:,只需换成归一化函数,(w/|w|，b/|w|),分类间隔（样本集到分类超平面的间隔）:,样本集中所有点到分类超平面间隔（几何间隔）中的最小值,第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,感知机算法,第,七,章机器学习,7.2,线性分类器,给定线性可分样集S，学习率R,+,W,0,=0,b,0,=0,k;,R=max|,x,i|;,do,k=0;,for(i=1;in;i+),if(yi(w,k,x,i,+b,k,)0),w,k+1,=w,k,+y,i,x,i,;,b,k+1,=b,k,+y,i,R,2,;,k+;,while(k0),9/14/2025,人工智能机器学习,分类间隔与误分次数的关系,在采样感知机算法时，,若分类间隔=，R=max|xi|i=1,.,n，则：,第,七,章机器学习,7.2,线性分类器,误分次数一定程度上代表分类器的误差,分类间隔越大的解，它的误差上界越小。,最大化分类间隔成了训练阶段的目标,9/14/2025,人工智能机器学习,最优分类面,要求分类面能将两类正确分开(训练错误率为0),且使分类间隔最大,第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,固定斜率时，最大间隔分,类面的导出,设过两,类中最靠近分类面的点的线分别为：,w,x+b,=k,1,l,1,w,x+b,=k,2,l,2,平行移动分类面，使：,K,1,=,k,2,=,k,令w=,w,/k,b=,b,/k,则,l,1,l,2,变为：,wx+b=1,w,x+b,=1,分类面则为：,wx+b=0,第,七,章机器学习,7.2,线性分类器,wx,+b1,wx,+b非线性分划,代价：,2维空间内积6维空间内积,非线性分类,9/14/2025,人工智能机器学习,为此，引进函数,有,比较(2)和(3)，可以发现,这是一个重要的等式，提示6维空间中的内积,可以通过计算 中2维空间中的内积 得到。,非线性分类,9/14/2025,人工智能机器学习,实现非线性分类的思想,给定训练集后，决策函数仅依赖于,而不需要再考虑非线性变换,如果想用其它的非线性分划办法，则可以考虑选择其它形式,的函数 ，一旦选定了函数，就可以求解最优化问题,得 ，而决策函数,9/14/2025,人工智能机器学习,决策函数,其中,实现非线性分类的思想,9/14/2025,人工智能机器学习,设 是 中的一个子集。称定义在 上的函数,是,核函数,(正定核或核)，如果存在着从 到某一个,空间 的映射,使得,其中 表示 中的内积,核函数(核或正定核)定义,9/14/2025,人工智能机器学习,多项式内核,径向基函数内核RBF,Sigmoind内核,目前研究最多的核函数主要有三类：,得到q 阶多项式分类器,每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定,包含一个隐层的多层感知器，隐层节点数是由算法自动确定,核函数的选择,9/14/2025,人工智能机器学习,多项式内核,The kind of kernel represents the inner product of two vector(point)in a feature space of dimension.,For example,9/14/2025,人工智能机器学习,Edgar Osuna(Cambridge,MA)等人在IEEE NNSP97发表了An Improved Training Algorithm for Support Vector Machines,提出了SVM的分解算法，即将原问题分解为若干个子问题，按照某种迭代策略，通过反复求解子问题，最终使得结果收敛于原问题的最优解。,传统的利用二次型优化技术解决对偶问题时：,需要计算存储核函数矩阵。当样本点数较大时，需要很大的存储空间。例如：当样本点超过4000时，存储核函数矩阵就需要多达128兆内存；,SVM在二次型寻优过程中要进行大量的矩阵运算，通常寻优算法占用了算法时间的主要部分。,SVM,寻优,算法,9/14/2025,人工智能机器学习,考虑去掉Lagrange乘子等于零的训练样本不会影响原问题的解，采用一部分样本构成工作样本集进行训练，移除其中的非支持向量，并把训练结果对剩余样本进行检验，将不符合KKT条件的样本与本次结果的支持向量合并成为一个新的工作集。然后重新训练，如此重复获得最优结果。,例如：基于这种思路的 算法。,根据子问题的划分和迭代策略的不同，大致分为：,块算法(Chunking Algorithm)：,SVM,寻优,算法,9/14/2025,人工智能机器学习,SMO使用了块与分解技术，而SMO算法则将分解算法思想推向极致，每次迭代仅优化两个点的最小子集，其威力在于两个数据点的优化问题可以获得解析解，从而不需要将二次规划优化算法作为算法一部分。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。,块算法(Chunking Algorithm)：,SVM,寻优,算法,9/14/2025,人工智能机器学习,SMO算法每次迭代时，在可行的区域内选择两点，最大化目标函数，从而优化两个点的最小子集。无论何时，当一个乘子被更新时，调整另一个乘子来保证线性约束条件成立，保证解不离开可行区域。每步SMO选择两个参数优化，其他参数固定，可以获得解析解。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。,SVM,寻优,算法,9/14/2025,人工智能机器学习,SVM,寻优,算法,类别名称,测试样本数,错误分类数,准确度（%）,政治,146,4,97.26,军事,83,0,100,经济,137,3,97.81,法律,32,2,93.75,农业,106,2,98.11,体育,90,1,98.89,卫生,34,1,97.06,工业,87,2,97.70,科技,111,2,98.20,交通,40,1,97.50,生活,91,1,98.90,宗教,3,0,100,天气,24,2,91.67,合计,984,21,97.87,9/14/2025,人工智能机器学习,SMO算法核缓存算法,SMO算法在每次迭代只选择两个样本向量优化目标函数，不需要核矩阵。虽然没有核矩阵操作，但仍需要计算被选向量和训练集中所有样本向量的核函数，计算次数为2n（n为训练集中的样本数）。如果训练集中的样本选取有误，在噪声比较多的情况下，收敛会很慢，迭代次数很多，则核函数的计算量也是非常可观的，SMO 算法的优点就完成失去了。同时，考虑到文本分类的文本向量一般维数比较大，核函数的计算将会非常耗时，尤其在高价多项式核和高斯核等核函数的计算中表现更加明显。,SVM,寻优,算法,9/14/2025,人工智能机器学习,SMO算法核缓存算法,在内存中为SMO算法核函数开辟n行m列的核矩阵空间。其中：n为训练集中的样本数；m是为可调节参数，根据实际的内存大小进行调整，每列存放训练集中某个样本向量与训练集中所有样本向量的核函数计算结果列表。在核矩阵列头生成m个节点的双向循环链表队列，每个节点指向核矩阵的列，通过双向循环链表队列实现核矩阵中的核函数列唤入唤出操作。同时，为了实现样本向量的核函数列的快速查找，为每个训练样本向量设计了快速索引列表，通过索引列表判断该训练样本向量的核函数列是否在核矩阵中，并确定在哪一列。,SVM,寻优,算法,9/14/2025,人工智能机器学习,SVM,寻优,算法,选择一个训练集，通过调整核缓冲参数的大小，记录不同核缓存大小情况下训练时间，结果如下表：,核缓存大小(Mb),训练样本数,核矩阵,迭代次数,训练时间(M:S),1,5624,5624*23,40726,7:06,10,5624,5624*233,40726,3:50,20,5624,5624*466,40726,2:41,30,5624,5624*699,40726,1:56,40,5624,5624*932,40726,1:29,50,5624,5624*1165,40726,1:23,60,5624,5624*1398,40726,1:08,70,5624,5624*1631,40726,1:05,80,5624,5624*1864,40726,1:04,90,5624,5624*2097,40726,1:07,100,5624,5624*2330,40726,1:37,250,5624,5624*5624,40726,1:12,9/14/2025,人工智能机器学习,通过引入核缓存机制，有效的改进了SMO算法，提高了文本分类的训练速度。在核缓存机制中采用简单的hash查找算法和队列FILO算法，有效提高了核矩阵查找和唤入唤出操作的效率。设置核矩阵列参数，通过调节列参数，可以灵活的根据系统运行情况调整训练的时间和空间开销，避免因系统空间开销过大使系统运行效率下降，反而影响训练速度。,SVM,寻优,算法,9/14/2025,人工智能机器学习,活动向量集选择算法,当训练样本数非常大的时候，如果系统能够提供的核缓冲大小很有限，那么能够同时保存在核缓冲中训练样本的核函数数目在训练样本数中所占比例将非常的小。在训练过程中，训练样本在核缓冲中的核函数命中率将显著下降，导致核缓冲中的核函数被频繁的唤入唤出，而每执行一次唤入唤出操作将引起系统重新计算训练样本的核函数，核缓存的作用被很大程度的削弱了。如果出现这样的情况，要么增加系统的存储空间；要么减少训练样本数，才能提高系统的训练速度。为解决训练样本数多，系统内存空间小的矛盾，本文通过活动向量集选择算法，比较好地解决了这个问题。,SVM,寻优,算法,9/14/2025,人工智能机器学习,活动向量集选择算法,算法的主要思想是：定期检查训练样本集，在收敛前预先确定训练样本集中一些边界上的点（alpha=0，或者alpha=C）是否以后不再被启发式选择，或者不再被判定为最有可能违例，如果存在这样的点，将它们从训练样本集中剔除出去，减少参加训练的样本数。该算法基于如下的认识：经过多次迭代后，如果样本的拉格朗日乘子一直为0，该点被当前估计的支持向量集所确定的超平面区分得很开，即使以后支持向量集发生变化，该点也不会是最靠近超平面的点，则可以确定该样本不是支持向量；经过多次迭代后，如果样本的拉格朗日乘子一直为非常大的C常数，即使以后支持向量集发生变化，该点也不会远离超平面，则可以确定该样本是上边界处的支持向量,SVM,寻优,算法,9/14/2025,人工智能机器学习,活动向量集选择算法,这样就可以在SMO算法收敛前，提前将边界上的点从训练样本集中剔除，逐渐缩小参加训练的活动样本集，从而减少SMO算法对核缓存空间的要求，提高训练速度。,训练开始前，训练活动集样本初始化为全部训练样本。每经过一定次数的迭代（比如迭代1000次），如果算法还没有收敛，应检查活动集中的向量，检查是否有训练样本可以不参加迭代运算。,检查完当前活动向量集中所有样本后，产生了新的活动向量集。如果新的活动向量集的样本数减少一成以上（含一成），则可以收缩当前活动向量集，用新的活动向量集替换当前活动向量集。当活动向量集的样本数减少到一定的程度，对核缓存空间的要求不是很大的时候，继续减少训练样本对训练速度的提高就非常有限了，这时就没有必要再减少训练样本了。,SVM,寻优,算法,9/14/2025,人工智能机器学习,将工作样本集的大小固定在算法速度可以容忍的限度内，迭代过程选择一种合适的换入换出策略，将剩余样本中的一部分与工作样本集中的样本进行等量交换，即使支持向量的个数超过工作样本集的大小，也不改变工作样本集的规模，而只对支持向量中的一部分进行优化。,例如:算法,2.,固定工作样本集(Osuna et al.)：,SVM,寻优,算法,9/14/2025,人工智能机器学习,SVM applications,Pattern recognition,Features:words counts,DNA array expression data analysis,Features:expr.levels in diff.conditions,Protein classification,Features:AA composition,9/14/2025,人工智能机器学习,Handwritten Digits Recognition,9/14/2025,人工智能机器学习,Applying SVMs to Face Detection,The SVM face-detection system,1.Rescale the input image several times,2.Cut 19x19 window patterns out of the scaled image,3.Preprocess the window using masking,light correction and histogram equalization,4.Classify the pattern using the SVM,5.If the class corresponds to a face,draw a rectangle around the face in the output image.,9/14/2025,人工智能机器学习,Applying SVMs to Face Detection,Experimental results on static images,Set A:313 high-quality,same number of faces,Set B:23 mixed quality,total of 155 faces,9/14/2025,人工智能机器学习,Applying SVMs to Face Detection,Extension to a real-time system,An example of the skin detection module implemented using SVMs,Face Detection on the PC-based Color Real Time System,9/14/2025,人工智能机器学习,References,Vladimir Vapnik.,The Nature of Statistical Learning Theory,Springer,1995,Andrew W.Moore.,cmsc726:SVMs.,www.cs.cmu.edu/awm/tutorials,C.Burges.A tutorial on support vector machines for pattern recognition.Data Mining and Knowledge Discovery,2(2):955-974,1998.Vapnik.Statistical Learning Theory.Wiley-Interscience;1998,Thorsten Joachims (joachims_01a):,A Statistical Learning Model of Text Classification for Support Vector Machines,Ben Rubinstein.Statistical Learning Theory.,Dept.Computer Science and Division of Genetics&Bioinformatics,Walter&Eliza Hall Institute,9/14/2025,人工智能机器学习,(promise是一个合取表达式),领域知识：,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,线性分类器,9/14/2025,人工智能机器学习,什么时候物体是一个杯子(续一),训练实例,cup(obj1),small(obj1),part(obj1,handle),owns(bob,obj1),part(obj1,bottom),part(obj1,bowl),points_up(bowl),concave(bowl),color(obj1,red),操作标准,需要目标概念用物体的可以观察的结构化的属性来定义,第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,解释实例,cup(obj1),Holds_liquid(obj1),Points_up(bowl),concave(bowl),part(obj1,bowl),small(obj1),part(obj1,handle),light(obj1),liftable(obj1),第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,泛化解释,我们的目标是用变量替换那些是训练实例的一部分常量。而保留领域知识中有的常量和限制。,本例中常量handle是领域知识中的一部分，因此保留，从而得到泛化树,可以有多种方法来建造泛化树,第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,泛化数,cup(X),Holds_liquid(X),Points_up(W),concave(W),part(X,W),small(X),part(X,handle),light(X),liftable(X),基于泛化树，得到一条规则：,small(X)part(X,handle)part(X,W)concave(W),Points_up(W)cup(X),第,七,章机器学习,7.2,线性分类器,9/14/2025,人工智能机器学习,连接主义观点,神经元激励模型不再强调用符号来解决问题,认为智能存在于这种简单的、相互作用的部件（生物的或人工的神经元）组成的系统中,调节神经元之间的连接参数可以提高智能,神经网络的问题求接是并行的,第,七,章机器学习,7.3,连接主义的机器学习,9/14/2025,人工智能机器学习,人工神经元,输入信号xi,：可能来自环境也可来自其神经元的刺激。不同模型允许输入参数有不同范围,权值wi：,描述连接强度,激励层,阈值函数f,第,七,章机器学习,7.3,连接主义的机器学习,wixi,f(),w1,w2,wn,x1,x2,xn,9/14/2025,人工智能机器学习,用神经元模型构造逻辑函数,McCulloch和Pitts在1943年构造的逻辑函数,输入信号,：只有+1和-1,阈值函数f：,大于0返回+1，否则返回-1,第,七,章机器学习,7.3,连接主义的机器学习,x+y-2,0,+1,+1,-2,x,y,1,xy,x+y-1,0,+1,+1,-1,x,y,1,x,y,9/14/2025,人工智能机器学习,七章,机器学习,The End.,9/14/2025,人工智能机器学习,