高级人工智能---机器学习ppt课件

高级人工智能第6章机器学习,.,2,机器学习,机器学习就是计算机自动获取知识，它是知识工程的三个分支(知识获取、知识表示和知识推理)之一，是AI中一个重要的研究领域，一直受到人工智能和认知心理学家们的普遍关注。机器学习涉及计算机科学、数学、心理学、生理学等多个交叉学科，涉及的面比较宽，许多理论和技术的问题尚处于研究阶段。从IJCAI，当前AI中三个研究热点：机器学习、知识表示和推理、多Agent系统,本章内容参考文献6.1概述6.2机器学习系统的基本模型6.3机械学习(RoteLearning)6.4归纳学习(InductiveLearning)6.5强化学习(ReinforcementLearning)6.6统计学习(StatisticalLearning)6.7多示例学习(Learning)本章小结,第6章机器学习,.,4,参考文献(1),蔡自兴，徐光佑.人工智能及其应用.清华大学出版社.2004:第6章TomM.Mitchell,机器学习，曾华军等译，机械工业出版社，2003年1月第一版史忠植.高级人工智能.科学出版社,1998年：第6章/第7章/第8章陆汝钤编著:人工智能(下册)第20章/第21章T.Mitchell,Thedisciplineofmachinelearning,July2006R.E.Schapire(2001),TheBoostingApproachtoMachineLearningAnOverview,见网页/schapire/boost.htmlLawrenceR.Rabiner(1989),AtutorialonHiddenMarkovModels只有当对知识的检索所需时间少于重新计算的时间时，机械学习才有效。为了快速检索知识库的内容，要合理组织。因此，采用适当的存储方式，使检索速度尽可能的快，是机械式学习中的重要问题。环境的稳定性与存储信息的适用性：在急剧变化的情况下，机械学习不适用。机械学习的一个重要假设是认为保存的知识或信息以后仍然有效。如果环境变化快，这个假设就破坏了。因此，机械学习必须保证所保存的信息适应于外界环境变化的需要，即所谓的信息适用性问题。,第6章机器学习,.,33,机械学习系统要考虑的问题(2),随时监控环境的变化，不断更新知识库中保存的信息或知识。例如当发现某种汽车被淘汰了，则把与这种汽车相关的知识删除。存储与计算之间的衡量在解决一个新问题时，是利用知识库的知识还是重新计算，需要权衡比较二者的代价。在权衡到底是存储还是利用计算时，考虑两方面：在首次得到一条信息时，确定是否要保存它，这时要考虑该信息以后的使用概率、存储空间和计算代价为了保证足够的检索速度，需要尽量精简知识库的内容(存储的越多检索速度越慢)。因此，对保存的内容在读取时加上时间标志，表示最后使用的时间，当保存一项新内容时，要删除一项未使用时间最长的旧内容。,第6章机器学习,.,34,6.4归纳学习(InductiveLearning),实例学习/观察与发现学习,第6章机器学习,.,35,归纳学习,归纳是人类拓展认识能力的重要方法，是一种从个别到一般、从部分到整体的推理行为归纳推理利用归纳方法，从足够多的具体实例中归纳出一般性知识，提取事物的一般性规律，它是一种从个别到一般的推理归纳推理的特点：能够产生新知识，但不保真，保假归纳学习是应用归纳推理进行学习的一种方法；归纳学习旨在根据给定关于某个概念的一系列已知的正例和反例，归纳出一个一般的概念描述。它是机器学习最核心、最成熟的分支。根据有无教师指导，归纳学习分为实例学习和观察与发现学习。前者有导师，后者没有导师,第6章机器学习,.,36,6.6.1实例学习(Learningfromexamples),通过从环境中取得若干与某概念相关的例子，经归纳得出一般性概念的一种方法。在这种学习中，外部环境(教师)提供给系统一些特殊的例子，这些实例事先由教师将其分为正例和反例两类实例学习系统根据这些实例进行归纳推理，得到一般性的规则或知识，这些一般性的知识应能解释所有的正例，排除所有给定的反例早在20世纪50年代，实例学习就引起了AI学者的注意，是机器学习领域中研究最充分、成果最丰富的一个分支实例学习在某些系统中的应用已经成为机器学习走向实用的先导,第6章机器学习,.,37,实例学习,实例学习的任务：给定由N个“输入-输出”对样例组成的训练集(x1,y1),.(xN,yN)，其中每个yi由未知函数y=f(x)生成发现一个函数h，它逼近真实函数fx和y不限于数值，可以是任何形式的值(属性值向量表示法)函数h是一个假说学习是一个搜索过程，它在可能假说空间寻找一个不仅在训练集上，而且在新样例上具有高精度的假说为了测量假说h的精确度，一般给学习系统一个由样例组成的测试集，它不同于训练集所谓一个假说泛化地好是指他能正确预测新样例的y值拟合：指假设能够很好地在训练集上模拟f有的时候，函数f是随机的，而不是x的严格函数，其实要学的是一个条件概率分布P(Y|x),.,38,当输出y的值为有限集合时，学习问题称为是分类若值集只包括两个元素，称为布尔或二元分类若y值是数值型的，则学习问题称为回归一个例子：在某些数据点上拟合一个单变量函数样例是(x,y)平面上的点，在真实函数f未知的情况下，用假设空间H的一个函数h逼近它假说空间是诸如x5+3x2+2形式的多项式集合,.,39,图(a)表示能用直线确切拟合某些数据/该假设称为一致假说，因为它与所有的数据相符图(b)为一个与同样数据一致的高阶多项式。,图(a),图(b),.,40,这说明了归纳学习中的一个基本问题：如何从多个假设中进行抉择？答案是选择与数据一致的最简单假说这个原理基于奥卡姆剃刀原理一般来说，在较好的拟合训练数据的复杂假说和更好泛化的简单假说之间存在着折中,.,41,例如，给出肺炎与肺结核两种病的一些病例(实例)。每个病例都含有五种症状：发烧(无、低、高)，咳嗽(轻度、中废、剧烈)，x光所见阴影(点状、索条状、片状、空洞)，皿沉(正常、快)听诊(正常、干鸣音、水泡音)。,.,42,.,43,实例学习算法的一般步骤,预处理训练实例集对新事物分类预处理训练实例集，包括6个部分：离散化连续值型属性，将连续型属性的值划分为有穷多个小区间；过滤无关属性，过滤掉与目标概念无关的属性，一般可采用统计属性重要性，最小充分属性等办法来实现；处理“未知”属性值，有3种途径：赋一个特殊值；赋一个最可能的值；按条件概率赋所有可能的值。,第6章机器学习,.,44,处理不重要的属性值，不重要的属性值只会使实例集增大，导致学习复杂性增加，预测精度下降。清理无意义的属性值，将训练实例和将来要分类的实例中无意义的属性值去掉；数据清理，从训练集中选择一个好的实例集，以便减少噪音和不一致性，同时使得到的实例集更具有代表性。对新事物分类构造分类器的目的就是要检查新事例是否与目标概念的分类规则匹配。,.,45,按最后得到规则的表示形式，分为覆盖算法(coveringalgorithms)：归纳生成规则，一般用析取范式表示。知名的覆盖算法：AQ11(MichabkiChilausky,1980)及其扩充EQll(Michabki，Hong等，l986)，AEl(Hong，1985)及其改进AE9(赵美德、洪家荣，1995)、HCV(wM，1992)，HCV(陈格、洪家荣，1996)，GS(洪家荣，1987)，扩张TU,.,46,分治算法(divideandconquer)：归纳生成树状结构。知名的分治算法有CLS(Hunt等，1966)及其改进ID3(QuinLan,1983)、C4.5(QuinLan,1984)。,第6章机器学习,洪家荣.归纳学习算法、理论和应用。科学出版社,1997,.,47,覆盖算法,假定有两组人，其中每个人具有如下三个特征：身材：高或矮发色：金色、黑色或红色眼睛(颜色)：黑色、蓝色或灰色每个人一个向量来表征，即下表给出了这两组人向量特征的集合(例子的集合)实例学习的目的就是从两类或多类例子的集合中找出描述其中一类而排出其余类的一般规则如，对于上例运行某种覆盖算法，得到两个规则,.,48,.,49,为了讨论方便，通常把一个离散符号集映射到非负整数集上，并且把正、反例集PE与NE列成矩阵的形式并仍记为PE与NE,.,50,基本概念,设E是一个n维离散符号的有穷向量空间，E=D1D2Dn，其中Dj是有穷离散符号集，jN，N=1，2,n为变元下标集。E中的元素e称为一个例子，记作e=，其中vjDj。选择子是形为xj#Aj的关系语句，其中xj是第j个变元，AjDj，关系#=,，选择子S=xj#Aj及公式当e满足选择子所定义的条件时，称e满足选择子；当e满足L所定义的条件时，称e满足公式L，也称为L覆盖e。给定一个正例集PE=e1+,e2+,ek+，反例集NE=e1-,e2-,em-，其中ei*=,.,51,正例集PE在反例集NE背景下满足公式L当且仅当每个正例都满足L，而每个反例不满足L。已知正例集PE、反例集NE，以及学习算法A。算法A归纳产生覆盖PE但排除NE的规则记为Cover(PE,NE,A)或Cover(PE,NE),.,52,星算法与AQ11,最早的覆盖算法是Michalski的Aq，其意为准优算法(quasi-optimalalgorithm)，Aq算法的核心是星算法，其定义如下。已知正例集PE=e1+,e2+,ek+，反例集NE=e1-,e2-,em-，其中ei*=。一个正例ei+在反例ej-背景下的星记为G(ei+|ej-)，是所有覆盖ei+而排除ej-的极大复合的集合。这里一个极大复合是除覆盖ei+排除ej-之外覆盖最多数目的其他正例的复合。正例ei+在反例集NE背景下的星记为G(ei+|NE)，是所有覆盖ei+而排除NE中所有反例的极大复合的集合。引理：ei+=在反例ej-=背景下的星G(ei+|ej-)是一个逻辑公式，为ei+ej-,.,53,即(x1=vi1+x2=vi2+xn=vin+)(x1=vj1-x2=vj2-xn=vjn-)，即，(x1=vi1+x2=vi2+xn=vin+)(x1vj1-x2vj2-xn=vjn+)展开式中那些极大复合的集合。正例ei+在反例集NE背景下的星G(ei+|NE)是逻辑公式ei+NE展开式中那些极大复合的集合。易见G(ei+|NE)的展开式中共有nm个复合，其中n是变元数，m是反例数，从中寻找极大复合的问题是NP完全的，因此直接构造星是不实际的，而Aq中使用缩小的星。,.,54,1980，AQ11(MichabkiChilausky,1980)扩充AQll(Michabki，Hong等，l986)AEl(Hong，1985)AE9(赵美德、洪家荣，1995)HCV(XindongWu，1992)HCV(陈格、洪家荣，1996)GS(洪家荣，1987)1991年洪家荣提出扩张矩阵EM1997郭茂祖扩张图,.,55,分治算法,分治算法是用属性对例子集逐级划分，直到一个结点仅含有同一类的例子为止。分治算法的结果是一棵决策树(decisiontree)最早的分治算法是Hunt等的CLS(ConceptLearningSystem)，后来又出现了Quinlan的ID3、C4.5等。决策树每一个节点表示对样本实例的某个属性值进行测试，该节点后相连接的各条路径上的值表示该属性的可能取值（二叉，三叉，）叶子节点即为实例所属的分类。每一个叶子产生一条规则，规则由根到该叶子的路径上所有节点的,.,56,决策树的说明,条件，规则的结论是叶子上标注的结论（决策，分类，判断）决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取决策树以事物的属性描述集合作为输入，输出通常是一个分类(离散的输出)一般是二值分类(真或假),.,57,决策树例子,第6章机器学习方法,(Outlook=Sunny)(Humidity=Normal)(Outlook=Overcast)(Outlook=Rain)(Wind=Weak),.,58,决策树适用问题,决策树学习的适用问题：实例是由“属性-值”对表示的固定的属性+离散或连续的取值目标函数具有离散的输出值析取表达式训练数据可以包含错误决策树学习的鲁棒性好训练数据可以包含缺少属性值的实例,第6章机器学习方法,.,59,基本的决策树学习算法,大多数决策树学习算法是一种核心算法CLS的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3是这种算法的代表决策树学习包括2个步骤：从实例中归纳出决策树(建立决策树)利用决策树对新实例进行分类判断ID3的构建决策树的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复以上过程，用每个分支关联的训练样例来选取该节点被测试的最佳属性。,.,60,表3-1用于学习布尔函数的ID3算法概要,ID3(Examples,Target_attribute,Attributes)创建树的root节点如果Examples都为正,返回label=+的单节点树root如果Examples都为反,返回label=-的单节点树root如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值否则开始AAttributes中分类examples能力最好的属性root的决策属性A对于A的每个可能值vi在root下加一个新的分支对应测试A=vi令Examplesvi为Examples中满足A属性值为vi的子集如果Examplesvi为空在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-A）返回root,.,61,属性选择,ID3算法的核心问题是选取在树的每个结点要测试的属性。希望选择最有助于分类实例的属性。/目标是为了最小化最终树的深度，从而使用尽可能少的判断步骤来分类某个实例ID3衡量分类属性区分训练样例能力的标准是“信息增益”。即，ID3在构建树的每一步使用这个信息增益标准从候选属性中选择属性。为了定义信息增益，现定义信息论中广泛使用的一个度量标准熵，它刻画了样例集的纯度。,.,62,熵,一个信息的大小是通过它的不确定性来衡量的。p(x)表示随机变量x的概率，那么用s(x)表示X的信息量。如果p(x)=1或0，则s(x)=0;一个随机变量x(假设x有n个可能取值)的平均信息量，即熵是这样计算的：对于包含关于某个目标概念的正反样例集S，那么S相对于这个布尔型分类的熵为，其中p1和p2分别表示S中正例的比例和反例的比例,.,63,熵的物理意义,熵用于衡量样本集的纯度；如果样例集S中所有成员均属于一类，则S的熵为0；如果S中正反例数目相当，其熵为1。熵值越大，表示样例越不纯，同时信息量越多；反之则样例越纯，信息量越小,.,64,.,65,信息增益,有了用熵度量训练样例集纯度的标准，现在可以定义属性分类训练数据能力的度量标准。一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低。即，一个属性A相对于样例集合S的信息增益Gain(S,A)被定义为：其中，values(A)表示属性A所有可能值的集合，Sv是S中属性A的值为v的子集，Entropy(S)表示原集合S的熵，Entropy(Sv)表示用A分类S后的熵。,.,66,例：假定S是一套有关天气的训练样例，描述它的属性为可具有weak和Strong两个值的Wind。假定S中有14个样例，其中正例9个，反例5个。在这14个样例中，假定正例中的6个和反例中的2个有Wind=weak，其他的是Wind=Strong。由于按照属性Wind分类14个样例得到的信息增益计算如下：,.,67,.,68,在ID3中，每次要选择增益最大的属性如何理解选信息增益最大的属性？,第6章机器学习方法,开始，决策树的树根对应于最大的不确定状态，表示在分类之前对被分类的对象一无所知随着每个属性的不断判断，向树的叶子方向前进，即相当于选择了其中的一棵子树，其不确定状态就减小了到达叶子节点，分类完成，此时不确定性为零综上所述，构建决策树的过程是熵不断下降的过程。要提高决策树的分类效率，就要求熵值下降的更快/这样，ID3算法的实质就是构造一棵熵值下降平均最快的决策树每次选择信息增益最大的属性，就相当于是选择平均熵下降最快的属性；,.,69,决策树算法的要点是在构造决策树的每一层次(从根向下)时，从尚未检测的属性中挑选一个信息增益最高的属性进行分解,.,70,例子,著名的隐形眼镜例子对于是否可配戴隐形眼镜，可把人们分为3类：类1：适于配戴硬性隐形眼镜；类2：适于配戴软性隐形眼镜；类3：不适于配戴隐形眼镜为了判断一个人是否适合配戴隐形眼镜，需要检查以下4种属性：属性a：配戴者年龄，取值a=属性b：配戴者的视力缺陷，取值b=属性c：配戴者是否有散光，取值c=属性d：配戴者泪腺分泌情况，取值d=,第6章机器学习方法,.,71,隐形眼镜例子(1),上述属性和人群分类一律按顺序用数字1,2表示，可以假设根据属性a、b、c、d有如下表的分类(纯属虚拟)计算S初始熵值和各属性分解熵值如下：初始熵值为Entropy(S)=-p1logp1-p2logp2-p3logp3属于第1类4个/第2类5个/第3类15个Entropy(S)=-=-(4/24)log(4/24)-(5/24)log(5/24)-(15/24)log(15/24)=0.4308+0.4715+0.4238=1.3261,第6章机器学习方法,.,72,隐形眼镜例子(2),第6章机器学习方法,.,73,隐形眼镜例子(3),为了方便地计算各个属性的信息增益，给出下表从表中可得，X中属性a=2/3的w1元素只有1个，a=1的w1元素是2个/而属性d=1的w3元素共有12个，而此时没有w1/w2分类/如此等等,第6章机器学习方法,.,74,隐形眼镜例子(4),利用上表，可以得到如下计算：Entospy(a=1)=-(2/8)log(2/8)-(2/8)log(2/8)-(4/8)log(4/8)=0.5+0.5+0.5=1.5Entospy(a=2)=-(1/8)log(1/8)-(2/8)log(2/8)-(5/8)log(5/8)=0.375+0.5+0.4238=1.2988Entospy(a=3)=-(1/8)log(1/8)-(1/8)log(1/8)-(6/8)log(6/8)=0.375+0.375+0.3113=1.0613由此得Gain(S,a)=E(S)-p(a1)Entospy(a=1)-p(a2)Entospy(a=2)-p(a3)Entospy(a=3)=1.3261-(8/24)*1.5+(8/24)*1.2988+(8/24)*1.0613=1.3261-0.5-0.4329-0.3538=0.0394,第6章机器学习方法,.,75,隐形眼镜例子(5),同样可得：Gain(S,b)=1.3261-(12/24)*(0.5+0.4308+0.4536)+12/24)*(0.2987+0.5+0.3900)=1.3261-0.6922-0.5944=0.0395Gain(S,c)=1.3261-(12/24)*(0+0.5263+0.4536)+(12/24)*(0.5283+0+0.3900)=1.3261-0.4900-0.4592=0.3769Gain(S,d)=1.3261-(12/24)*(0.5283+0.5263+0.5)=0.5488,第6章机器学习方法,.,76,隐形眼镜例子(6),根据以上计算数据，选择信息增益最大的Gain(S,d)，即以属性d作为第一次划分/此时d=1分支中的元素全部为w=3类别，只需对d=2分支继续进行熵值计算/d=2分支为(X,a,b,c)，X是去掉d=1的元素之后剩下的集合(12个元素),第6章机器学习方法,X,d,d=1,d=2,w3,X,.,77,隐形眼镜例子(7),缩小以后集合S的属性取值表如下,第6章机器学习方法,.,78,隐形眼镜例子(8),接着进行计算，注意在集合S下Entropy(S)Gain(S,a)=.Gain(S,b)=Gain(S,c)=Gain(S,d)=经过反复计算，可得如图示的决策树,第6章机器学习方法,.,79,隐形眼镜例子(9),第6章机器学习方法,该例子给出的数据完整情况(请考虑实例不完整情况下如何建立决策树？),.,80,算法的评价,一个学习算法产生的假设(或者分类)应该对未知的实例进行很好的预测如何评价预测的质量也就是学习算法的性能？有2种方式预先估计预测的质量计算学习理论，回答为什么学习是可行的事后考察预测的质量实验验证(训练集/测试集),第6章机器学习方法,.,81,实验验证策略,预留法（holdoutcrossvalidation）随机将数据分为训练集和测试集，训练集用于学习算法产生h，测试集用于评估h的精度缺点：不能利用所有可用数据，得到的低劣假说或低劣估计K-折交叉验证（k-foldcrossvalidation）能从数据中获取更多东西，并仍然获得精确估计每个样例既作为训练数据又做为测试数据,.,82,基本思想：将数据划分为k个规模相等的子集执行k轮次学习在每次学习中，选择1个子集作测试集，然后k-1个作为训练集；k轮测试中得到的平均分数应该好于单一分数但是需要多花费K倍的计算时间,.,83,模型选择和相对良好性拟合,多项式的阶数越高，就越能更好地模拟训练数据，但阶数太高会出现过度拟合，从而在验证数据上表现低劣定义过拟合(overfit)给定假设空间H和一个假设hH,如果存在其他假设hH使得在训练样例上h的错误率比h小，但在整个实例分布上h错误率比h小，则称h过拟合训练样例如何寻找一个训练充分又具有最好的泛化能力的决策树呢？当验证集误差开始下降时停止(下页图)。,.,84,随着决策树节点的增加，在训练样例上的精度是单调上升的，然而，在独立于训练样例的测试样例上，精度先上升后下降。,.,85,决策树算法的性能,产生过拟合的原因：训练样例数量太少，很可能出现一些巧合的规律性数据中含有噪声,第6章机器学习方法,.,86,观察与发现学习,一种无教师指导的归纳学习。分为观察学习和发现学习两种。观察学习用于对事例进行概念聚类，形成概念描述；发现学习用于发现规律，产生定律或规则。概念聚类：观察学习研究中的一个重要技术,基本思想是把事例按一定的方式和准则进行分组,如划分为不同的类、不同的层次等,使不同的组代表不同的概念,并且对每一个分组进行特征概括,得到一个概念的语义符号描述。/聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小;,第6章机器学习,.,87,概念聚类算法,列举现在的聚类算法，举例说明与实例学习的区别;训练集,.,88,聚类的基本要素,定义数据之间的相似度;聚类有效性函数（停止判别条件）;1.在聚类算法的不同阶段会得到不同的类别划分结果，可以通过聚类有效性函数来判断多个划分结果中哪个是有效的;2.使用有效性函数作为算法停止的判别条件，当类别划分结果达到聚类有效性函数时即可停止算法运行;类别划分策略（算法）;通过何种类别划分方式使类别划分结果达到有效性函数;,.,89,流行聚类算法,基于划分:K-means,K-medoids基于层次:HFC基于密度:DBSCAN基于网格:CLIQUE,STING参考文献：孙吉贵.聚类算法研究.软件学报,2008,19(1)：48-61,.,90,发现学习：由系统的初始知识、观察事例或经验数据中归纳出规律或规则；是最困难且最富有创造性的一种学习。分为经验发现和知识发现，经验发现指从经验数据中发现规律和定律,如，物理、化学定理，Bacon；知识发现是从已观察的事例中发现新的知识,.,91,集成学习(EnsembleLearning),归纳学习通常从假设空间中选出一个假设对新实例进行分类预测集体学习的思路是在对新的实例进行分类的时候，把若干个单个分类器集成起来，通过对多个分类器的分类结果进行某种组合来决定最终的分类，以取得比单个分类器更好的性能。,三个臭皮匠，胜过诸葛亮,.,92,为什么集成学习有效？,统计上的原因：对于一般的学习任务，往往要搜索的空间十分庞大，但是用于训练分类器的训练集中实例个数不足够用来精确地学习到目标假设，这时学习的结果可能是一系列满足训练集的假设，而学习算法只能够选择这些假设的其中之一作为学习到的分类器进行输出。把多个假设集成起来能够降低这种风险。,.,93,计算上的原因：证明了在人工神经网络学习和决策树学习中，学习到最好的人工神经网络或者是决策树是一个NP-hard问题，其他的分类器模型也面临着类似的计算复杂度的问题。这使得我们只能用某些启发式的方法来降低寻找目标假设的复杂度，但这样的结果是找到的假设不一定是最优的。通过把多个假设集成起来能够使得最终的结果更加接近实际的目标函数值。,.,94,表示上的原因：由于假设空间是人为规定的，在大多数机器学习的应用场合中实际目标假设并不在假设空间之中，如果假设空间在某种集成运算下不封闭，那么我们通过把假设空间中的一系列假设集成起来就有可能表示出不在假设空间中的目标假设。,.,95,集成学习有效的条件,虽然以上几点原因使得集成学习可能取得更好的学习效果，但是并不是所有的集成方式都有效的，集成学习有效的条件是每个单一的学习器错误率都应当低于0.5，否则集成的结果反而会提高错误率进行集成学习的每个分类器还应当各不相同/如果每个基本分类器分类结果差不多，则集成后的分类器整体和单个分类器做出的决策实际上没有什么差异，这样集成后的分类器就难以保证比单个分类器有更好的性能了。,.,96,考察一个集成学习方法时应该考虑以下几方面的问题：a)基本分类器之间是什么关系？b)怎么样生成多个不同的基本分类器？c)如何把多个基本分类器的分类结果整合起来？,.,97,基本分类器之间的关系,按照基本分类器之间的种类关系可以把集成学习方法划分为异态集成学习和同态集成学习两种异态集成学习指的是使用各种不同的分类器进行集成，异态集成学习的两个主要代表是叠加法（StackGeneralization）和元学习法（MetaLearning）。同态集成学习：集成的基本分类器都是同一种分类器，只是这些基本分类器之间的参数有所不同。,.,98,不同的基本分类器的获得方式,基本分类器的多样性是评价集成学习算法的重要标准，因此如何获取不同的基本分类器对集成学习的效果有着重要影响。对于异态集成学习方法，基本分类器的不同来源于他们本身种类的不同；对于同态集成学习方法，基本分类器的不同来自于多种可能，以下把不同基本分类器的获取方式划分为4类，并分别予以说明：,.,99,不同的基本分类器的获得方式,对训练样例进行处理对数据特征进行处理引入随机扰动,.,100,不同的基本分类器的获得方式,对训练样例进行处理对数据特征进行处理引入随机扰动,.,101,对训练数据进行处理,BaggingBagging由Breiman提出：对训练集有效地抽取训练样例，从而为每一个基本分类器都构造出一个跟训练集同样大小但各不相同集，从而训练出不同的分类器。Bagging是基于对训练集进行处理的集成方法中最简单、最直观的一种。要使Bagging有效，基本分类器的学习算法必须是不稳定的，即对训练数据敏感。基本分类器的算法对训练数据越敏感，Bagging的效果越好，因此，对于决策树和人工神经网络这样的学习算法Bagging相当有效。Bagging的分类器数应该随着分类种数的增多而增加。,.,102,Boosting最先由RobertT.Schapire提出：对那些容易分错的训练实例加强学习首先给每一个训练样例赋予相同的权重，然后训练第一个基本分类器并用它来对训练集进行测试；对于那些分类错误的测试样例提高其权重，然后用调整后的带权训练集训练第二个基本分类器，然后重复这个过程直到得到一个较好的分类器为止。典型算法：AdaBoost,.,103,不同的基本分类器的获得方式,对训练样例进行处理对数据特征进行处理引入随机扰动,.,104,对输入特征进行处理,对于具有多种特征的实例，通过抽取不同的特征子集分别进行训练，从而获得不同的分类器。特征子集的选取又叫做集成特征选取（EnsembleFeatureSelection），根据特征子集的选取方式不同，又有随机子空间法（随机抽取特征子集）和少量余留法（InputDecimation，只抽取和问题最相关的那些特征）,.,105,不同的基本分类器的获得方式,对训练样例进行处理对数据特征进行处理引入随机扰动,.,106,随机扰动法（InjectingRandomness）,在每个基本分类器的学习过程之中引入随机扰动，使得学习出来的每个基本分类器都不同，这是用于进行人工神经网络集成学习的最常见方法。只要基本学习器对随机扰动敏感，则随机扰动法能够有效地产生多个不同的基本分类器。对于人工神经网络，使用后向传递算法来进行学习的时候对于每个神经网络的初始权值都随机分配，则产生的基本分类器会有很明显的不同，对于决策树，则可以在每个决策结点的特征选取的时候从某个特征子集（例如前20个导致熵增益最大的特征构成的集合）里面随机选取一个作为该结点的分类特征。,.,107,基本分类器分类结果的整合方式,简单投票贝叶斯投票基于D-S证据理论的整合方式,.,108,简单投票,多个基本分类器都进行分类预测，然后根据分类结果用某种投票的原则进行投票表决，按照投票原则的不同投票法可以有一票否决：当且仅当所有的分类器都把实例x划分到类Ci时才把x划分到Ci，否则拒绝这个实例;一致表决:没有分类器否定把实例x划分到类Ci时把x划分到Ci少数服从多数:让多个分类器投票(加权或不加权)，得票数最多的类Ci是实例x的最终分类阈值表决：首先统计出把实例x划分为和不划分为的分类器Ci的数目分别是多少，然后当这两者比例超过某个阈值的时候把x划分到Ci。,.,109,贝叶斯投票,简单投票法假设每个基本分类器都是平等的，没有分类能力之间的差别，但是这种假设并不总是合适的，在实际生活中，我们听取一个人的意见的时候会考虑到这个人过去的意见是否有用。贝叶斯投票法是基于每一个基本分类器在过去的分类表现来设定一个权值，然后按照这个权值进行投票，其中每个基本分类器的权值基于贝叶斯定理来进行计算。虽然理论上贝叶斯投票法在假设空间所有假设的先验概率都正确的情况下能够获得最优的集成效果，但是实际应用中往往不可能穷举整个假设空间，也不可能准确地给每个假设分配先验概率，从而使得在实际使用中其他集成方法也会优于贝叶斯投票法。,.,110,基于D-S证据理论的整合方式,这些整合方式的基本思想是通过识别率、拒绝率等一系列参数计算出每个目标分类的信任范围，从而最终推断出分类结果。,.,111,6.7强化学习(ReinforcementLearning),第6章机器学习,.,112,引言强化学习模型Q学习,.,113,概述,增强学习（ReinforcementLearning，又称为强化学习或再励学习）是近年来机器学习与智能控制研究的热点领域。强化学习技术是从控制理论、统计学、心理学等相关学科发展而来。其思想来源于动物学习心理学。“失败乃成功之母”“吃一堑，长一智”。与监督学习不同，增强学习不需要给定输入状态下的期望输出，而强调在与环境的交互中进行学习，以极大化（或极小化）从环境获得的评价性反馈信号为学习目标，因此增强学习在求解无法获得教师信号的复杂优化与决策问题中具有广泛的应用前景。,.,114,由于没有教师信号，增强学习需要利用“试错法”来发现哪个行为能带来更大的回报。实际问题中，当前时刻的行为不仅决定了当前的回报，还有可能影响下一时刻的回报，甚至影响后面所有时刻的回报。“试错法”和延迟回报，是增强学习的两个主要特征。增强学习不是一种具体的算法，而是一种解决问题的思路，凡是具有这两个特征的方法，都可以认为是增强学习方法。,.,115,发展现状,增强学习仅仅需要环境的评价性反馈信号，与监督学习中的导师信号不同，这个反馈信号仅仅是对行为好坏的一种评价，而不是告诉增强学习如何产生正确的动作，因此很容易获得。所以在上个世纪六、七十年代，增强学习一度引起人们的关注。由于外部环境提供的信息很少，这给求解增强学习问题的增加了很大的困难，因此在二十世纪七、八十年代，增强学习的研究一度陷入低谷。而同期在监督学习方法的研究中则取得了一系列的研究成果，如神经网络反向传播、决策树学习算法等,.,116,由于监督学习需要给出不同环境状态下的教信号，因此教师信号的好坏直接决定了最后策略的好坏，并且在有些情况下，获得其完全正确的导师信号非常困难。因此，到了二十世纪九十年代，研究人员又把目光转向增强学习，并且通过与运筹学、自适应控制理论的结合，在理论和算法方面取得了一些突破性进,.,117,基本原理,人类（通常）从与外界环境的交互中学习。但是，动作的反馈并不总是立即的和直接的。例如，经常需要比较长时间才能充分知道我们的动作所得出的结果。强化学习是一种独特的机器学习方法，它只需要记忆所处环境的状态和当前的策略知识，能利用不确定的环境奖赏来发现最优行为策略强化学习从环境状态到行为映射的学习，以使系统行为从环境中获得的累积奖励值最大。与传统监督学习技术区别：传统学习通过正例、反例来告知采取何种行为；强化学习通过试错来发现最优行为/进行学习的系统不会像其他机器学习方法那样被告知什么是正确的动作、什么是错误的动作，通过试错来发现最优行为策略,.,118,基本原理：如果系统的某个动作导致环境产生正的奖赏，则系统以后产生这个动作的趋势便会加强，反之减弱。,.,119,强化学习模型,智能系统,环境,s,r,a,r:reward，回报s:state，状态a:action，动作,.,120,交互过程,系统根据从环境中检测到的状态s(sS，S为状态集)选择动作a(aA，A为动作集)，环境在动作a的作用下导致状态变为状态s，同时反馈回报值r。强化学习系统的目标是学习一个行为策略：SA，使系统能根据监测到的状态作出最佳动作。为此，需要定义一个函数描述长远观点来看什么是最佳动作，一般有以下几种形式：,.,121,.,122,.,123,有了目标函数就可以通过下式确定最优的行为策略：,0,0,100,100,0,0,0,0,0,0,G,r(s,a)立即回报值,100,100,81,90,G,V*(s)累积回报值，=0.9,90,0,0,.,124,有了目标函数，机器人在任意的环境中直接学习最优策略很难，因为没有形式为的训练样例训练数据是立即回报函数，容易学习一个定义在状态和动作上的数值评估函数，然后实现最优策略很明显，可以将V*作为待学习的评估函数由于状态s下的最优动作是使立即回报r(s,a)加上立即后继状态的V*值最大的动作a，即因此，如果具有回报函数r和状态转移函数的完美知识，就可以计算出任意状态下的最优动作,.,125,Q函数,但是在实际情况中，回报函数r和状态转移函数未知对于无法知道回报函数和状态转移函数完美知识的情形，我们使用评估函数Q评估函数Q的定义评估函数重写为,.,126,90,81,100,100,81,72,90,81,90,81,G,Q(s,a)立即回报值,81,72,90,100,100,81,90,G,最优策略,.,127,注意到因此有这个Q函数的递归定义提供了迭代逼近Q算法的基础用表示实际Q的估计，算法中用一个大表存储所有状态-动作对的值一开始所有表项填充为初始的随机值，然后利用下式更新表项，直到这些值收敛,.,128,表13-1在确定性回报和动作假定下的Q学习算法,Q学习算法对每个s,a初始化表项观察当前状态s，一直重复做：选择一个动作a并执行它接收到立即回报r观察新状态s对按照下式更新表项ss,.,129,除了Q学习算法之外还有：动态规划方法(DynamicProgramming)蒙特卡罗(MonteCarlo)瞬时差分学习算法(TemporalDifference)SARSA学习算法Dyna学习算法AHC学习算法,.,130,学习资源,http:/webdocs.cs.ualberta.ca/sutton/book/ebook/the-book.htmlReinforcementLearning:AnIntroduction(可以在线阅读),.,131,A,B,D,F,C,E,.,132,将Agent放在任何一个房间，希望它能够走出房子(到达节点对每个门设置一个回报值(图中的边)：与目标节点相关联的边的回报值为100，其他边的回报值为0.由于门是双向的，每条边关联两个方向，因此考虑两个方向。,A,B,D,F,C,E,0,0,100,0,0,0,0,100,0,0,0,0,100,.,133,假定机器人在C处，如何走到F处？每个节点代表状态，箭头代表动作，边的权重代表回报值,A,B,D,F,C,E,0,0,100,0,0,0,0,100,0,0,0,0,100,Agentnowinstate,Actiontogotostate,.,134,得到矩阵R表示环境回报系统,.,135,NowweneedtoputsimilarmatrixnameQinthebrainofouragentthatwillrepresentthememoryofwhattheagenthavelearnedthroughmanyexperiences.TherowofmatrixQrepresentscurrentstateoftheagent,thecolumnofmatrixQpointingtotheactiontogotothenextstate.Inthebeginning,putQiszeromatrix.ThetransitionruleofthisQlearningis,.,136,Ourvirtualagentwilllearnthroughexperiencewithoutteacher(thisiscalledunsupervisedlearning).Theagentwillexplorestatetostateuntilitreachesthegoal.Wecalleachexplorationasanepisode.Inoneepisodetheagentwillmovefrominitialstateuntilthegoalstate.Oncetheagentarrivesatthegoalstate,programgoestothenextepisode.Thealgorithmbelowhasbeenprovedtobeconvergence,.,137,.,138,Theabovealgorithmisusedbytheagenttolearnfromexperienceortraining.Eachepisodeisequivalenttoonetrainingsession.Ineachtrainingsession,theagentexplorestheenvironment(MatrixR),gettherewarduntilitreachthegoalstate.Thepurposeofthetrainingistoenhancethebrainofouragent(Qmatrix).MoretrainingwillgivebetterQmatrixthatcanbeusedbytheagenttomoveinoptimalway.Inthiscase,iftheQmatrixhasbeenenhanced,insteadofexploringaroundandgobackandforthtothesameroom,theagentwillfindthefastestroutetothegoalstate.,.,139,Parameterhasrangevalueof0to1.Ifiscloserto0,theagentwilltendtoconsideronlyimmediatereward.Ifisclosertoone,theagentwillconsiderfuturerewardwithgreaterweight,willingtodelaytherewardTousetheQmatrix,theagenttracesthesequenceofstates,fromtheinitialstateuntilgoalstate.ThealgorithmisassimpleasfindingactionthatmakesmaximumQforcurrentstate.,.,140,算例1,设=0.8，,.,141,Lookatthesecondrow(stateB)ofmatrixR.TherearetwopossibleactionsforthecurrentstateB,thatistogotostateD,orgotostateF.Byrandomselection,weselecttogotoFasouraction.NowweconsiderthatsupposeweareinstateF.LookatthesixthrowofrewardmatrixR(i.e.stateF).Ithas3possibleactionstogotostateB,EorF.,.,142,ThenextstateisF,nowbecomethecurrentstate.BecauseFisthegoalstate,wefinishoneepisode.OuragentsbrainnowcontainupdatedmatrixQas,.,143,Forthenextepisode,westartwithinitialrandomstate.ThistimeforinstancewehavestateDasourinitialstate.ithas3possibleactions：stateB,CandE.Byrandomselection,weselecttogotostateBasoura