第七章-机器学习

第七章机器学习§7.1基本概念1机器学习(1)学习：没有一个精确，公认的定义，主要有以下几种观点：①学习是系统改进其性能的过程，西蒙1980年提出的②学习是获取知识的过程③学习是技能的获取④学习是事物规律的发现过程学习是一个有特定目的的知识获取过程，其内在行为是获取知识、积累经验、发现规律；外部表现是改进性能、适应环境、实现系统的自我完善。(2)机器学习：使计算机能模拟人的学习行为，自动地通过学习获取知识和技能，不断改善性能，实现自我完善。机器学习的研究围绕三个方面：①学习机理的研究：对人类学习机制的研究，即人类获取知识、技能和抽象概念的天赋能力②学习方法的研究：研究人类的学习过程，探索各种可能的学习方法，建立起独立于具体应用领域的学习算法③面向任务的研究：根据特定任务的要求，建立相应的学习系统2学习系统：是能够在一定程度上实现机器学习的系统，一个学习系统应具有如下条件和能力：(1)具有适当的学习环境环境：学习系统进行学习时的信息来源

例学习系统是学生，环境就是教师、书本、各种应用、实践过程。学习系统用于专家系统的知识获取时，环境是领域专家、文字资料、图像等。博弈时，环境是博弈的对手和千变万化的棋局。(2)具有一定的学习能力通过与环境多次相互作用逐步学到有关知识，而且在学习过程中要通过实践验证、评价所学知识的正确性。(3)能应用学习到的知识求解问题能把学到的信息用于未来的估计、分类、决策或控制。(4)能提高系统的性能

通过学习，系统应能增长知识，提高技能，改善系统的性能。环境学习知识库执行与评价环境：外部信息的来源，它将为系统的学习提供有关信息。学习：系统的学习机构，它通过对环境的搜索取得外部信息，然后经过分析、综合、类比、归纳等思维过程获得知识，并将这些知识存入知识库中。知识库：用于存储由学习得到的知识，在存储时要进行适当的组织，使它既便于应用又便于维护。执行与评价：执行：用于处理系统面临的现实问题。评价：用于验证、评价执行环节的执行效果。评价环节的处理有两种：①把评价时所需的性能指标直接建立在系统中，由系统对执行环节得到的结果进行评价②由人来协助完成评价工作执行→学习：根据反馈信息从环境中索取进一步的信息进行学习，以修改、完善知识库中的知识。3机器学习的发展，分三个阶段(1)神经元模型的研究20世纪50年代中期，主要研究工作是应用决策理论的方法研制可适应环境的通用学习系统1957年罗森勃拉特提出感知器模型，由阈值性神经元组成，试图模拟动物和人脑的感知及学习能力塞缪尔研制的具有自学习，自组织，自适应能力的跳棋程序(2)符号学习的研究20世纪70年代中期，研究者们力图在高层知识符号表示的基础上建立人类的学习模型，用逻辑的演绎及归纳推理代替数值的或统计的方法莫斯托夫的指导式学习温斯顿和卡鲍尼尔的类比学习尼切尔等人的解释学习(3)连接学习的研究20世纪80年代。VLSI技术，超导技术，生物技术，光学技术发展，提出了多层网络的学习算法，进入连接学习阶段—非线性大规模并行处理为主流的神经网络的研究。连接学习适用于连续语音的语音识别及连续模式的识别符号学习在离散模式识别及专家系统的规则获取方面有较多应用目前里奇开发的集成系统将两者结合起来4机器学习的分类(1)按学习方法分类机械式学习指导式学习示例学习类比学习解释学习(2)按推理方式分类基于演绎的学习：是从已知前提逻辑地推出结论的一种推理。解释学习在其推理过程中主要是用演绎方法，归于一类基于归纳的学习：是从特殊事物或大量实例概括出一般规则或结论的一种推理，由归纳推理得到的结论是否确实是前提的逻辑结论是不能断定的。示例学习、发现学习以归纳推理为主，划归一类(3)按综合属性分类归纳学习分析学习连接学习遗传算法分类器系统§7.2机械式学习1机械式学习—死记式学习，是一种最简单、最原始的学习方法。把经过评价所取得的知识存储到知识库中，求解问题时从知识库种检索出相应的知识，直接用来求解问题例：某个计算的输入是(x1,x2,…,xn)，计算后的输出是(y1,y2,…,yn)，如果经评价得知该计算是正确的，则就把联想对[(x1,x2,…,xn),(y1,y2,…,yn)]存入知识库中。当以后又要对(x1,x2,…,xn)做同样的计算时，只要直接从知识库中检索出(y1,y2,…,yn)就可以了，不需要重复进行计算。2机械式学习实质上是用存储空间来换取处理时间，要全面权衡时间与空间的关系§7.3指导式学习—嘱咐式学习，教授式学习在这种学习方式下，由外部环境向系统提供一般性的指示或建议，系统把它们具体转化为细节知识并送入知识库中。在学习过程中要反复对形成的知识进行评价，使其不断完善。指导式学习过程有下列四步骤组成：1征询指导者的指示或建议简单征询：由指导者给出一般性的意见，系统将其具体化复杂征询：由指导者给出一般性的意见，具体鉴别知识库中可能存在的问题，给出修改意见被动征询：系统被动的等待指导者提供意见主动征询：系统不只是被动地接受指示，而且还能主动提出询问2把征询意见转换为可执行的内部形式，在转换过程中进行语法检查和语义分析3并入知识库：对知识进行一致性检查，防止出现矛盾、冗余、环路等问题4评价：用一些标准例子对新知识进行经验测试，若出现不一致，表示新知识有问题，反馈给指导者。§7.4归纳学习

分为：示例学习、观察与发现学习1归纳推理：从个别到一般，从部分到整体的一类推论行为由于在进行归纳时，多数情况下不可能考察全部有关的事例，因而归纳出的结论不能绝对保证它的正确性，只能以某种程度相信它为真，这是归纳推理的一个重要的特征例有翅膀的动物会飞，长羽毛的动物会飞但鸵鸟有羽毛、有翅膀却不会飞(1)枚举归纳

设a1,a2…是某类事物A中的具体事物，若已知a1,a2…an都有属性P，并且没有发现反例，当n足够大时，就可得出A中所有事物都有属性P的结论例张三是足球运动员，他的体格健壮李四是足球运动员，他的体格健壮

……………

刘六是足球运动员，他的体格健壮∴凡是足球运动员，他的体格一定健壮(2)联想归纳：归纳推理是一种主观不充分置信推理，因而经归纳得出的结论可能会有错误，归纳推理是非单调性的。若已知两事物a,b有n个属性相似或相同a具有属性P1,b也具有属性P1a具有属性P2,b也具有属性P2

………a具有属性Pn,b也具有属性Pna具有属性Pn+1，当n足够大时，可归纳出b也具有属性Pn+1例两个孪生兄弟，有相同的身高，体重，面貌，喜欢唱歌，跳舞，吃相同的食品，如果一个喜欢山水画，我们会联想到另一个也喜欢(3)类比归纳设A,B分别是两类事物的集合

A={a1,a2…}B={b1,b2…}

并设ai,bi总是成对出现的，且当ai有属性P时，bi就有属性Q与之对应，即

P(ai)→Q(bi)i=1,2,3..

若A,B有一对新元素a’,b’时，由P(a’)→Q(b’)(4)逆推理归纳：是一种由结论成立而推出前提以某种置信度成立的归纳方法，这种方法的模式为若H为真,则H→E必为真，或以置信度cf1成立观察到E成立或以置信度cf2成立则H以某种置信度cf成立H→Ecf1P(E/H)Ecf2HcfE→Hcf’1可按Bayes公式算出cf’1=P(H/E)=P(E/H)*P(H)/P(E)=cf1*P(H)/P(E)=cf1*cf/cf2

∴cf=cf1’*cf2/cf1(5)消除归纳对某个事物发生的原因作出若干假设，这些假设间是析取关系。随着对事物认识的不断深化，原先作出的某些假设有可能被否定，经过若干次否定后，最后剩下来未被否定的假设就可作为事物发生的原因。已知A1

A2

…Ai

…An

A1,

A2,…

Ai-1,

Ai+1,…

An结论Ai2示例学习—实例学习，从例子中学习是通过从环境中取得若干与某概念有关的例子，经归纳得出一般性概念的一种学习方法(1)示例学习的学习模型学习过程：首先从示例空间（环境）中选择合适的训练示例，然后经过解释归纳出一般性的知识，最后再从示例空间中选择更多的示例对它进行验证，直到得到可实用的知识为止。搜索解释知识库形成知识示例空间验证示例空间：所有可对系统进行训练的示例集合。示例的质量和数量将直接影响到学习的质量，示例的组织方式将影响到学习效率搜索：从示例空间中查找所需的示例解释：从搜索到的示例中抽象出所需的有关信息供形成知识使用形成知识：把经解释得到的有关信息通过综合、归纳等形成一般性的知识验证：检验所形成的知识的正确性(2)形成知识的方法变量代换常量例1花色(C1,梅花)

花色(C2,梅花)

花色(C3,梅花)

花色(C4,梅花)→同花(C1,C2,C3,C4)例2花色(C1,红桃)

花色(C2,红桃)

花色(C3,红桃)

花色(C4,红桃)→同花（C1,C2,C3,C4）规则1：花色(C1,x)

花色(C2,x)

花色(C3,x)

花色(C4,x)→同花（C1,C2,C3,C4）舍弃条件：舍去某些无关子条件花色（C1,红桃）

点数（C1,2）

花色（C2,红桃）

点数（C2,4）

花色（C3,红桃）

点数（C3,6）

花色（C4,红桃）

点数（C4,8）

→同花（C1,C2,C3,C4）∵点数与同花无关，点数舍去，红桃用x代替。如同规则1增加操作：前件析取法和内部析取法前件析取法：通过对示例的前件进行析取操作形成知识。“脸牌”示例1：点数（C1,J）→脸（C1）示例2：点数（C1,Q）→脸（C1）示例3：点数（C1,K）→脸（C1）规则2:点数(C1,J)

点数(C1,Q)

点数(C1,K)→脸（C1）内部析取法：在示例的表示中使用集合与集合间的成员关系来形成知识示例1:点数(C1)

{J}→脸(C1)示例2:点数(C1)

{Q}→脸(C1)示例3:点数(C1)

{K}→脸(C1)内部析取点数(C1)

{J,Q,K}→脸(C1)合取变析取：通过把示例中条件的合取关系变为析取关系来形成一般性知识。例：由“男同学与女同学可以组成一个班”可以归纳出“男同学或女同学可以组成一个班”归结归纳

P

E1→H

P

E2→H

可得：E1

E2→H例示例1某天下雨，且自行车在路上出了毛病需修理，所以他上班迟到示例2某天没下雨，但交通堵塞，所以他上班迟到所以，如果自行车在路上出毛病需修理或者交通堵塞，则他有可能上班迟到曲线拟合（x,y,z）x,y输入，z输出示例1（1，0，10）示例2（2，1，18）示例3（-1，-2，-6）曲线拟合Z=2x+6y+83观察与发现学习观察学习:对事例进行概念聚类，形成概念描述机器发现:发现规律，产生定律或规则①概念聚类由米卡尔斯基在1980年提出来的基本思想是把事例按一定的方式和准则进行分组，不同组代表不同的概念，对每个组进行特征概括，得到一个概念的语义符号描述例喜鹊，麻雀，布谷鸟，乌鸦，鸡，鸭，鹅…

鸟={喜鹊，麻雀，布谷鸟，乌鸦…}

家禽={鸡，鸭，鹅…}特征：鸟有羽毛，有翅膀，会飞，会叫，野生，家禽有羽毛，有翅膀，会飞，会叫，家养②机器发现是从观察的事例或经验数据中归纳出规律或规则。经验发现：从经验数据中发现规律和定律知识发现：从已观察的事例中发现新的知识§7.5类比学习

通过对相似事物进行比较所进行的一种学习。1类比推理：有新情况与记忆中的已知情况在某些方面相似，从而推出它们在其他相关方面也相似。(1)类比推理在两个相似域之间进行①源域S：过去曾经解决过且与当前问题类似的问题以及相关知识②目标域T：当前尚未完全认识的域，它是遇到的新问题(2)推理过程：S1,T1表示S与T中的某一情况，且S1与T1相似。设S2与S1相关，推出T中的T2,且T2与S2相似推理过程：①回忆与联想遇到新情况，通过回忆、联想在S中找出与当前情况相似的情况，对不止一个时，依其相似度从高到低进行排序②选择从上一步找出的相似情况中选出与当前情况最相似的情况及有关知识，相似度越高越好③建立对应关系在S与T的相似情况之间建立相似元素的对应关系，并建立相应的映射④转换在上步映射下，把S中的有关知识引到T中来，建立求解当前问题的方法或学习到关于T的新知识2属性类比学习根据两个相似事物的属性实现类比学习。源域和目标域都用框架表示，框架的槽表示事物的属性，其学习过程是把源框架中的某些槽值传递到目标框架的相应槽中去。传递分两步：(1)从源框架中选择若干槽作为候选槽候选槽：指槽值有可能传递给目标框架的那些槽①选择那些具有极端槽值的槽作为候选槽。例如“很大”，“很小”，“非常高”②选择那些已经被确认为“重要槽”的槽作为候选槽③选择那些与源框架相似的框架中不具有的槽作为候选槽。S为源框架，S’与S相似，如果S中有某些槽,而S’没有，则就选这些槽为候选槽。④选择那些相似框架中不具有这种槽值的槽作为候选槽，S为源框架，S’与S相似，如果S有某槽，其槽值为a，而S’虽有该槽，但槽值不为a，则这个槽可被选为候选槽⑤把源框架中的所有槽都作为候选槽(2)根据目标框架对候选槽进行筛选①选择那些在目标框架中还未填值的槽②选择那些在目标框架中为典型事例的槽③选择那些与目标框架有紧密关系的槽，或者与目标框架的槽类似的槽通过筛选，一般都可以得到一组槽值，分别把它们填入到目标框架的相应的槽中，就实现了原框架中某些槽值向目标框架的传递。3转换类比学习---“手段-目标分析”(EMA)法或“中间-结局分析”法，是纽厄尔、肖和西蒙在其完成的通用问题求解程序GPS中提出的一种问题求解模型。求解过程如下：(1)把问题的当前状态与目标状态进行比较，找出它们之间的差异(2)根据差异找出一个可减少差异的算符(3)如果该算符可作用于当前状态，则用该算符把当前状态变为另一个更接近于目标状态的状态；如果该算符不能用于当前状态，则保留当前状态，并生成一个子问题，然后对此子问题再应用MEA(4)当子问题被求解后，恢复保留的状态，继续处理原问题。转换类比学习主要有两个过程组成：回忆过程和转换过程回忆过程：用于找出新、旧问题间的差别新、旧问题初始状态的差别新、旧问题目标状态的差别新、旧问题路径约束的差别新、旧问题求解方法可应用度的差别转换过程：把旧问题的求解方法经适当变换，使之成为求解新问题的方法。§7.6基于解释的学习1基于解释学习的概念基于解释学习是通过运用相关的领域知识及一个训练实例来对某一目标概念进行学习，最终生成这个目标概念的一般描述，该一般描述是一个可形式化表示的一般性知识(1)这种学习方法基于如下考虑提出①人们经常能从观察或执行的单个实例中得到一个一般性的概念及规则，这就为基于解释学习的提出提供了可能性②基于解释的学习在其学习过程中运用领域知识对提供给系统的实例进行分析，保证了推理的正确性③应用基于解释学习的方法进行学习，有望提高学习效率(2)米切尔用如下框架描述解释学习给定：领域知识DT—相关领域的事实和规则目标概念TC—要学习的概念训练实例TE—为学习系统提供的实例操作性准则OC—指导学习系统对描述目标的概念进行取舍找出：满足OC的关于TC的充分条件系统进行学习时，运用领域知识DT找出训练实例TE为什么是目标概念TC之实例的证明(解释)，然后根据操作性准则OC对证明进行推广，从而得到关于目标概念TC的一个一般性描述。(3)基于解释的学习与示例学习的区别

解释学习①只要求输入一个实例②学习方法是演绎，要求提供完善的领域知识③侧重于技能提高，通过学习把非操作性的知识转换为可操作的形式化知识

示例学习①系统要求输入一组实例②学习是归纳法，不要求提供领域知识③侧重于概念的获取2基于解释学习的学习过程(1)构造解释这一步的任务是证明提供给系统的训练实例为什么是满足目标概念的一个实例。其证明过程是通过运用领域知识进行演绎实现，证明的结果是得到一个解释结构例设要学习的目标概念是“一个物体（obj1）可以安全地放置在另一个物体(obj2)上”Safe-To-Stack(obj1,obj2)训练实例描述物体obj1和obj2的下述事实On(obj1,obj2)Isa(obj1,book-AI)Isa(obj2,table-book)Volume(obj1,1)Density(obj1,0.1)领域知识:把一个物体放置在另一物体上的安全性准则

Fragile(y)→Safe-To-Stack(x,y)

Lighter(x,y)→Safe-To-Stack(x,y)Volume(p,v)

Density(p,d)

*(v,d,w)→Weight(p,w)Isa(p,table-book)→Weight(p,15)Weight(p1,w1)

Weight(p2,w2)

Smaller(w1,w2)→Ligter(p1,p2)由目标概念引导的逆向推理，获得如下一个解释结构Safe-To-Stack(obj1,obj