人工智能（第4版）课件 机器学习简版

第14章机器学习10.1概述任何人工智能系统，特别是专家系统，在它拥有功能较强的自动化知识获取能力之前，都不会成为名符其实的强有力的智能系统。机器学习技术的应用是解决这一问题的有效途径。事实上，目前机器学习一直被公认为是设计和建造高性能专家系统的“瓶颈”，如果在这一研究领域里有所突破将成为人工智能发展史上的一个里程碑。10.1.1机器学习的定义和意义按照人工智能学家西蒙的观点，学习就是系统在不断重复的工作中对本身能力的增强或者改进，使得系统在下次执行同样的任务或类似的任务时，会比现在做得更好或效率更高。从字面上看，机器学习是研究如何使用机器来模拟人类的学习活动的一门科学。从人工智能的角度出发的观点是：机器学习是一门研究使用计算机获取新知识和技能，并能够识别现有知识的科学。10.1.2机器学习的研究简史第一阶段:(—70s)机器学习侧重于非符号的神经元模型的研究。第二阶段:(70中—80后)机器学习主要侧重于符号学习的研究，由于人工智能的新分支—专家系统的蓬勃发展，知识获取变成当务之急。

第三阶段:(80后—)机器学习的研究进入了一个全面化、系统化的时期。

特点代表成果和事件一方面，传统符号学习的各种方法已全面发展并且日臻完善，应用领域不断扩大，达到了一个巅峰时期；同时由于发现了用隐单元来计算与学习的非线性函数方法，从而克服了早期神经元模型的局限性，加之计算机硬件的飞速发展，使神经网络迅速崛起，并广泛用于声音识别、图象处理等诸多领域；计算机运行速度的提高和并行计算机的不断普及也使得演化计算的研究突飞猛进，并在机器学习领域的应用取得了很大的成功。这使得联接学习和符号学习呈现出争奇斗艳的态势。另一方面，机器学习基础理论的研究引起了人们越来越大的重视，从1988年起，美、德、日等国连续召开计算学习理论的学术会议，各种关于机器学习的杂志上也不乏这方面的学术论文。随着机器学习技术的不断成熟和计算学习理论的不断完善，机器学习必将会给人工智能的研究带来新的突破。Michalski的AQVAL(1973)，Buchana等人的Meta-Dendral(1978)，Lenat的AM(1976)，Langley的BACON(1978)，Quinlan的ID3(1983)等。1980年，第一届机器学习研讨会在Carnegie-Mellon(CMU)大学举行。1983年，由Michalski等人编辑出版了第一本有关机器学习的读物《MachineLearning：anArtificialIntelligenceApproach》第1卷(1986，1990年又分别出版了第2、3卷)。1986年，第一个机器学习杂志《MachineLearning》正式创刊。10.1.3机器学习方法的分类1.根据所采用的策略分类2.根据系统中知识表示分类3.根据学习的手段来分类死记硬背式学习(rotelearning)讲授式学习(learningbyinstruction)演绎学习(learningbydeduction)类比学习(learningbyanalogy)归纳学习(inductivelearning)；神经模型(neuralmodeling)决策理论技术(decisiontheoretictechniques)符号概念获取(symbolicconceptacquisition)特定领域的知识密集型学习(knowledge-intensivedomain-specificlearning)合成式学习(syntheticlearning)，合成式方法旨在产生新的或更好的知识，即知识获取；分析式学习(analyticlearning)，分析式方法旨在将已有知识转化为或组织成另一种针对某个目标来说更好的形式，这也可以说是知识求精。这几种分类方法是相互联系和相互渗透的。10.1.4机器学习中的推理方法在逻辑中，有三种基本的推理方法，即演绎推理、归纳推理和类比推理。目前机器学习所用到的推理方法可分为三大类：基于演绎的保真性推理；基于归纳的从个别到一般的推理；基于类比的从个别到个别的推理。1．演绎推理演绎推理是从一般到特殊的推理，从主观上讲是一种主观地充分置信的推理。基于演绎推理的学习方法主要有：自动程序设计；基于解释的学习。演绎推理是一种保真不保假的推理，即不可能由真的前提导致假的结论。形式化表示就是，设A→B是演绎推理，如果真，则必真；如果为假，则不一定为假。1．演绎推理演绎推理具有以下三个特征：接受前提的置信度被充分地转移到对结论的接受中去。具有演绎正确性，当且仅当一个推理的前提给其结论提供充分理由，即结论是前提的推断，这个推理才是演绎正确的。具有形式正确性，当且仅当一个推理的结论由前提逻辑地得出，这个推理才是形式正确的。2．归纳推理归纳推理是从特殊到一般的推理，它是一种“从事实建立理论的过程”。从主观上讲是一种主观地不充分置信的推理。与演绎正确性不同，主观地不充分置信的推理在正确性方面有程度上的差别：前提对结论的关系并不是或者支持或者不支持，而是给予强弱程度不同的支持。因此，在归纳推理中，一般用归纳强度的概念来代替正确性的概念，即一般不谈这个推理是否正确，而是评价这种推理归纳强度的高低。2．归纳推理归纳推理是一种保假不保真的推理，即由假前提必然导致假结论。形式化表示就是，设A→B是归纳推理，如果假，则必假，如果真，则不一定真。基于归纳推理的学习方法主要有：推广，即从特殊到一般的推广；逆绎，它是从结论推断前提的推理方法。3．类比推理类比推理是从个别事例到个别事例的推理方法。它是根据认识的新情况（目标）和已知情况（源）在某些方面的相似性，推断出其它相关方面的推理形式。其一般模式为：已知：S1，T1（源S1和目标T1）

S1≌T1（源和目标相似）

S1〉〉S2（源S1和源S2相关）

S2（已知源S2）结论：T2（其中T2≌S2）（类比结论T2）即已知S1，T1，S1≌T1，S1→S2，可类比结论得出T2。10.2归纳学习10.2.1归纳概念学习的定义归纳学习问题一般描述为使用训练实例以引导一般规则的搜索问题。全体可能的实例构成实例空间，而学习的任务就是要完成实例空间和规则空间之间同时的、协调的搜索。定义10.2

用来描述对象和概念的形式语言分别称为对象描述语言和概念描述语言。用指定的对象描述语言描述的对象称为对象描述，也可简称为事例；用指定的概念描述语言描述的概念称为概念描述，也可称为概念表示。定义10.3(覆盖)设有一个用概念描述语言表示的假设H和一个实例，如果满足H，则称H覆盖，或称被H覆盖。定义10.4(归纳概念学习)给定一个目标概念的实例集，寻找一个用概念描述语言表示的假设，使得，e被覆盖；，e不被覆盖。定义10.5(完备性)如果H覆盖所有正例，那么H相对于实例集是完备的。定义10.6(一致性)如果H不覆盖任何反例，那么H相对于实例集是一致的。显示图示关闭图示eee=È+-"Î+ee"Î-ee10.2.2归纳概念学习算法的一般步骤

预处理训练实例集构造分类规则对新事例分类1）离散化连续值型属性。2）过滤无关属性。3）处理“未知”属性值，有三种途径：赋一个特殊值"unknown"赋一个最可能的值按条件概率赋所有可能的值4）处理不重要的属性值。5）清理无意义的属性值。6）整理数据，从训练集中选择一个“好”的实例集，以便减少噪音和不一致性，同时使得到的实例集更具代表性。

构造分类规则分两步进行：（1）学习分类规则。反复在假设空间中进行抽象和例化搜索，直至算法终止的充分和必要条件都满足。归纳概念学习的目标是找到对于已知训练集是完备和一致的分类规则或概念描述。在满足完备性和一致性条件之前终止分类规则生成过程的机制称为“预剪枝”(pre-pruning)，下一步是另一种剪枝过程。（2）对生成的分类规则进行“剪枝”。将一新事例与分类规则进行匹配操作时有三种可能情况，即单匹配、多匹配或不匹配，分别用SINGLE，MULTIPLE，NO_MATCH来表示，如下图所示：10.2.3归纳概念学习的基本技术归纳概念学习的目的就是利用学到的概念完成下列三种任务之一：分类(classification)，即给定一些新的未知事例，要求系统能判别出它们分别属于哪些概念，或者是否属于某一概念；预测(prediction)，如果训练实例是一个序列中的相继元素，要求系统能预测出序列中下一个或第n个将是什么元素；(3)数据压缩(datacompression)，给定各种可能的实例，要求系统找到能够描述它们的概念。

10.2.3归纳概念学习的基本技术归纳学习方法可分为单概念学习和多概念学习两类:对于单概念学习，学习的目的是从概念空间（或规则空间）中寻找某个与实例空间一致的概念；多概念学习的任务是在概念空间中找出若干概念描述。对于每一概念描述，实例空间中均有相应的空间与之对应。多概念的学习任务可以划分成多个单概念学习任务来完成。

10.2.3归纳概念学习的基本技术单概念学习可以按行为方式的差异分为数据驱动、规则驱动和模型驱动等三类方法。如果按所采用的技术归纳起来有四种方法：候选项删除法、求精操作法生成—测试假设法模式例化法前两种是数据驱动的方法，后两种是模型驱动的方法。1．候选项删除法概念空间中所有合理假设称为描述空间，一个描述空间H是所有与目前所得到的训练实例一致的概念的集合，并假设空间H是所有包含可能概念的规则空间。当向程序提供训练实例时，一些与当前实例不相容的候选概念就从描述空间中删除。这样对描述空间不断求精，一旦描述空间中只剩下唯一元素时，那个候选概念就是所要发现的学习概念。1．候选项删除法

训练正例使程序进行抽象(generalization)操作，从H中删去非常特殊的概念描述；训练反例使程序进行例化(specialization)操作，使得过于一般的概念描述从H中删去。这两种操作使假设空间逐渐缩小，直到仅剩所要的概念描述为止。算法Candidate-Elimination1.G={NULL},S={}//G集合包含零描述,初始化为一个正例2.Repeat2.1ReadExample(e)；//接受一个新的训练实例2.2ifPossitive(e)thenUpdate_S(e)；//如果实例为正例，则更新S集合

elseUpdate_G(e)；//如果实例为反例，则更新G集合

UntilG=S//如果G≠S集合，重复步骤23.OutPut(G或S)//输出G或S1).难以处理有噪音的数据。难以处理有噪音是所有数据驱动算法的一个通病，当遇到一个错误的正例时，S就会过分抽象。同样，当算法遇到一个错误的反例时，G就会过分例化，这种有噪音的数据最终可能导致找不到与所有训练实例一致的概念描述。2).不能学习析取概念。不足之处算法Candidate-Elimination2.求精操作法—BACONBACON是由PatLangley开发的一系列概念学习程序。这些程序能解决许多单概念学习问题，包括"再发现"诸如欧姆定律、牛顿万有引力定律、开普勒定律等经典的科学定律。同时，这些程序还能用学到的概念预测将来的事例。基本思想：程序重复地检查数据各项之间的关系，应用合适求精操作产生新的项，直至找到一个项恒等于一个常数，这时概念就可表示为“项=常数值”的形式。假设要发现开普勒定律：行星围绕太阳运转的周期Y与它离太阳D的距离满足Y

2/D3=k

，k为常数。提供给BACON.4的训练事例如表所示。行星YDY/D(Y/D)/D((Y/D)/D×Y(((Y/D)/D)×Y)/D水星0.240.390.621.610.391.00金星0.620.720.851.180.721.00地球1.01.01.001.001.001.00火星1.881.521.230.811.521.00木星11.865.202.280.445.201.00土星29.469.543.090.329.541.00天王星84.0119.194.380.2319.171.00海王星164.830.075.480.1830.041.00冥王星248.439.526.290.1639.511.00

行星数据BACON.4的归纳过程首先，BACON.4注意到Y随D的增大(减小)而增大(减小)，因此，引发除法操作，生成Y/D项，Y/D仍随D的增大(减小)而增大(减小)。同样，引发除法操作，生成(Y/D)/D项，(Y/D)/D同Y又呈反比变化，因而又引发乘法操作，生成（（Y/D）/D）×Y项，而该项又几乎同D呈正比变化，因此再引发除法操作生成(（（Y/D）/D）×Y)/D项，该项为一常数1.00，这就是最终要找的结果，即(Y×Y)/(D×D×D)=k(常数)。实际上，BACON.4方法可总结成如下三条规则：如果X项近似为一常数，则可形成一条含X的规则；如果项X随项Y增大而增大，则产生一新的项X/Y；如果项X随项Y增大而减小，则产生一新的项X×Y。3．决策树法决策树又称为决策图。在决策树中有决策节点和状态节点两种结点。由决策节点可引出若干树枝，每个树枝代表一个决策方案，每个方案树枝连结到一个新的节点，它既可以是一个新的决策节点，也可以是一个状态节点，每个状态节点表示一个具体的最终状态。在决策树中，状态节点对应着叶节点。决策树算法中典型的代表是Quinlan在1979年提出的ID3算法，它是一种通用的规则归纳算法，它源于Earl.Hunt的CLS算法。CLS算法在CLS的决策树中，节点对应于待分类的对象的属性，由某一节点引出的弧对应于这一属性可能的取值，叶节点对应于分类的结果。同BACON一样，CLS和ID3也用属性-值表示法来描述训练实例，设x=（a1，…，an）为一个训练实例，它有n个属性，分别属于属性表（A1，…，An）中，即ai分别表示Ai的取值。又设cj∈C=（C1，…，Cn）为分类结果，则T={(x，cj)}为训练集。决策树可以通过训练集来构造，概念则用决策树表示。例如：设用“大小”(大，小)，“形状”(圆，方，三角)和“颜色”(红，兰)三个属性来描述实例，则“大红圆”的概念可表示为图10-4。形状形状三角方圆颜色颜色NONO红蓝YESNO大小大小小大NO大小算法CLS1.如果当前实例集S中实例均属于同一类或为空，则返回这个类或返回空后终止；2.从属性表中找出信息增益量最大的属性A，设它的取值为v1，…，vn，产生一新节点A

，它有n个分枝；3.根据A的取值将S划分成n个子集S1，…，Sn

，A在中Si取值；4.对每个i，用Si和新的属性表递归调用CLS算法生成Si的决策树DTi

；5.返回以属性A为根，DT1，…，DTn为子树的决策树。

由于决策树中每条由根节点到叶节点的路径都对应于不同的析取项，因此，决策树本质上是析取的，因而能表示析取概念。一次对全部训练集构造决策树的算法是低效的，特点算法ID31.随机从整个实例集中选择一个大小为W的子集，构成训练窗口，W为窗口的大小；2.用CLS算法构造当前窗口的决策树；3.用生成的决策树来分类所有训练实例，寻找出其中不能被正确分类的实例，即反例；4.把当前窗口中的实例与反例中的一些组合形成新的窗口；5.重复2-4步，直到所有实例被正确分类，即不存在反例为止。有两种产生新窗口的策略：1）保留老窗口中所有实例，同时加入由用户指定个数的不能正确分类的实例，这使得窗口逐渐增大；2）保持W不变，对生成的决策树的每个叶节点，保留一个实例，将其它实例用那些不能被分类的实例取代。这两种策略都很有效，但第2)种策略对过于复杂的概念学习问题有时不能收敛。两种策略不足之处不能处理噪音数据。如果子集中还存在不是属于同一类的实例，ID3就要对其进行划分，那些错误的属性值引起的噪音数据可能导致ID3产生过于复杂的决策树以至降低其分类精度。不能处理有未知属性值的情况。学习结果为决策树，难以理解。10.3基于类比的学习10.4.1类比学习的一般原理类比（analogy）是一种很有效的推理方法，利用它可以法清晰地表达截然不同的对象间的相似性，同时，借助这种相似性进行推理后人们可以领会或表达出来某些概念相应的内涵。人类学习过程往往也借助于类比推理来进行。

类比学习过程分为两步：

1）首先归纳找出源域和目标域的公共性质；

2）然后演绎地推出从源域到目标域映射，得出目标域的新性质。示例例如，学生在学习某个知识点时，先由老师演示例题，然后相应的习题留给学生练习。学生在练习时，将例题和习题对比，找出相似性，然后利用这种相似性进行推理找出相应的解题方法,这就是一种类比学习方法。10.3.2类比学习的表示

假设对象的知识是用框架集来表示的，则类比学习过程可描述为从一个称为源框架的槽值传送到另一个称为目标框架的槽的过程，其传递过程分为如下两个步骤：（１）利用源框架产生若干侯选槽，并将这些槽值送到目标框架中去；（２）利用目标框架中现有的信息来筛选上一步提取出来的相似性。例10.3

考虑消防车与比尔之间的相似关系，关于消防车与比尔的框架为：消防车ISA车辆比尔ISA人颜色红性别男活动级快活动级音量极高音量梯高高进取心中等燃料效率中等进取心ISA个人品质其中，消防车是源框架，比尔是目标框架。

推荐一组槽可以传递槽值，这要用到如下的几条启发式规则：（1）选择那些用极值填写的槽。（2）选择那些已知为重要的槽。（3）选择那些与源框架性质相似且还不具有的槽。（4）选择那些与源框架性质相似且不具有这种槽值的槽。（5）使用源框架中的一切槽。

在类比学习相继使用这些规则,直到找到一组相似性为止，并进行相应的传递。将以上规则应用于例10.3的结果为：用规则1，活动级槽和音量槽填有极值可以首先列选。用规则2，因本例无确认为重要的槽，所以无候选者。用规则3，将选择梯高，因为该槽不会出现在其他类型的车辆中。用规则4，颜色槽可选，因为其它卡车的颜色不是红色的。若使用最后一条规则，则消防车的所有槽都列选。10.3.3类比学习的求解

在从源框架选择的槽建立起一组可能的传送框架之后，必须用目标框架的知识加以筛选，使用这种知识的启发式规则如下：选择那些在目标框架中尚未填入的槽；选择那些出现在目标框架“典型”示例的槽；若第2步无可选者，则选择那些与目标框架有紧密关系的槽；若仍无可选者，则选择那些与目标框架类似的槽；若再无可选者，则选择那些与目标框架有紧密关系的槽类似的槽；应用规则1，将不删除任何推荐的槽；应用规则2，将选择活动级槽和音量槽，因为在关于人的框架中通常会出现这两个槽。以上的例子属于这种典型，这两个槽虽然没有值，它们还是放在比尔的框架中；若有些典型的示例槽未被推荐，则规则4会选择这些在其它关于人的框架中会出现的槽，由于人类具有身高，所以选择一个身高槽；如果活动级和音量这两个槽为清楚的标明为典型人的一部分，它们仍会被这些规则选上。由于有进取心这个槽，且已知它属于个人品德，所以其它的个人品质也应该列选；若进取心对比尔是未知的，而对其它人是已知的，则其它的个人品质槽将被选上。求解过程

以上过程结束时，描述比尔的框架为：比尔ISA人性别男活动级快音量极高身高高进取心中等10.4深度学习机器学习虽然取得了很大的进展，但对某些复杂问题的处理的效果，还远远没有达到使用的标准。而在最近的十年间，人工智能技术再次出现了前所未有的爆发性增长和繁荣期，是深度学习技术的兴起是本次人工智能繁荣大潮的重要推动力。我们可从图10.5中可以看出，第三波人工智能热潮源于机器学习的复兴和深度学习的兴起。从图中的曲线不难看出，深度学习是人工智能取得了前所未有的突破。从根本上来说，深度学习和所有机器学习方法一样，是一种用数学模型对真实世界中的特定问题进行建模，以解决该领域内相似问题的过程。首先，深度学习是一种机器学习。机器学习在解决实际问题时分为两步：第一步是特征提取；第二步是将特征向量经过学习算法进行训练或预测。这个过程可以通过图10.6描述。10.4.1什么是深度学习图10.6机器学习的过程一般说来，计算机用来学习的、反复观察的图片叫“训练数据集”；“训练数据集”中，一类数据区别于另一类数据的不同方面的属性或特质，叫作“特征”；计算机在“大脑”中总结规律的过程，即这些特征及其关联关系可以在计算机中形式化地表达出来，叫“建模”；计算机在“大脑”中总结出的规律，即形式化的表达，就是我们常说的“模型”；而计算机通过反复“看图”，总结出规律，然后学会识别和分类的过程，这就是传统的“机器学习”。特征提取是机器学习必经之路，而深度学习的方法则更进一步。深度学习能够自动地找出这个分类问题所需要的重要特征。如果深度学习能通过机器学习来完成特征提取，同时加大模型的复杂度，就有希望更好地处理一些复杂问题。深度学习的一般框架如下图10.8所示。图10.8深度学习的一般框架深度学习如何自动提取特征呢？以这个猫狗识别的例子来说，深度学习按照以下步骤来进行分类：1．首先确定出有哪些边和角跟识别出猫狗关系最大；2.然后根据上一步找出的很多小元素（边、角等）构建层级网络，找出它们之间的各种组合；3.在构建了一定的层级网络之后，确定哪些组合可以识别出猫和狗。这里描述的步骤还显得有点抽象，再以人脸识别的为例，图10.9是一个深度学习识别过程的示意图。10.4.2特征提取这个图中可以看到4层，输入的是原始数据（RawData）这个数据机器没法理解。于是，深度学习首先尽可能找到与这个头像相关的各种边，这些边就是底层特征（Low-levelfeatures），这就是人脸识别的第一步；然后，对这些底层特征进行组合，就可以看到有鼻子、眼睛、耳朵等等，它们就是中间层特征（Mid-levelfeatures），这就是人脸识别的第二步；最后，对鼻子眼睛耳朵等进行组合，就可以组成各种各样的头像了，也就是高层特征（High-levelfeatures），这个时候就可以识别出或者分类出人的各种头像了。自动特征提取就是探讨有没有可能为计算机设计一种灵活度极高的表达方式，可以指挥计算机在大规模的学习过程里（在大数据里）不断尝试和寻找，自动去总结规律，直到最终找到各层级中符合真实世界特征的一种表示方法呢？自动特征提取就是深度学习的本质所在。深度学习就是这样一种在表达能力上灵活多变，同时又允许计算机不断尝试，直到最终逼近目标的机器学习方法。10.4.3自动特征提取简单地说，深度学习就是把计算机要学习的东西看成一大堆数据，把这些数据丢进一个复杂的、包含多个层级的数据处理网络（深度神经网络）。在这多个层级的之间，上一层的输出通过各种权值参数，作为下一层的输入。通过这种方式，实现对输入的原始信息进行分级表达，然后检查经过这个网络处理得到的结果数据是不是符合实际要求。如果符合，就保留这个网络作为目标模型；如果不符合，就一次次地、锲而不舍地调整网络的参数设置，直到输出满足要求为止。

深度学习的本质可以更具体描述为，通过构建具有很多隐层的机器学习模型和海量的训练数据来