《机器学习》PPT课件.ppt

第六章 机器学习 6.1 机器学习概念6.2 示例学习6.2.1示例学习的两个空间模型6.3 基于解释的学习6.4基于案例的推理6.5 加强学习 6.1 机器学习的概念6.1.1 机器学习的发展历史1.神经元模型研究阶段这个时期主要技术是神经元模型以及基于该模型的决策论和控制论;机器学习方法通过监督（有教师指导的）学习来实现神经元间连接权的自适应调整，产生线性的模式分类和联想记忆能力。具有代表性的工作有FRosenblaft的感知机（1958年）；NRashevsky数学生物物理学（1948年）；WSMcCullouch与WPitts的模式拟神经元的理论（1943年）;RMFriedberg对生物进化过程的模似等。 v2符号概念获取研究阶段60年代初期，机器学习的研究进入了第二阶段，在这个阶段，心理学和人类学习的模似占有主导地位，其特点是使用符号而不是数值表示来研究学习问题，其目标是用学习来表达高级知识的符号描述。在这一观点的影响下，主要技术是概念获取和各种模式识别系统的应用；研究人员一方面深入探讨学习的简单概念，另一方面则把大量的领域知识并入学习系统，以便它们发现高深的概念。这个阶段代表性的工作是温斯顿（Winston，1975）的基于示例归纳的结构化概念学习系统。 v3基于知识的各种学习系统研究阶段机器学习发展的第三个阶段始于70年代中期，这个阶段不再局限于构造概念学习系统和获取上下文知识，结合了问题求解中的学习、概念聚类、类比推理及机器发现的工作。相应的有关学习方法相继推出，比如示例学习、示教学习、 观察和发现学习、类比学习、基于解释的学习。工作特点强调应用面向任务的知识和指导学习过程的约束，应用启发式知识于学习任务的生成和选择，包括提出收集数据的方式、选择要获取的概念、控制系统的注意力等。 v4联结学习和符号学习共同发展阶段80年代后期以来，形成了联结学习和符号学习共同发展的局的第四个阶段。在这个时期，发现了用隐单元来计算和学习非线性函数的方法，从而克服了早期神经元模型的局限性，同时，由于计算机硬件的迅速发展，使得神经网络的物理实现变成可能，在声间识别、图像处理等领域，神经网络取得了很大的成功。在这个进期，符号学习伴随人工智能的进展也日益成熟，应用领域不断扩大，最杰出的工作有分析学习（特别是解释学习）、遗传算法、决策树归纳等。现在基于计算机网络的各种自适应、具有学习功能的软件系统的研制和开发,将机器学习的研究推向新的高度。 6.1.2什么是机器学习什么是机器学习，到今仍没有严格定义，不同学派对机器学习有不同的定义 准确、完整地给出机器学习的定义很困难，综合上述三种观点可以得出，学习是对某一个特定目标的知识获取的智能过程，系统的内部表现为新知识结构的建立和改进，外部表现为系统性能的改善，变得更快、更精确、更健全。 v一个机器学习系统应具有以下特点：v1.具有适当的学习环境v学习系统中环境并非指通常的物理条件，而是指学习系统进行学习时所必需的信息来源。v2.具有一定的学习能力v一个好的学习方法和一定的学习能力是取得理想的学习效果的重要手段。所以，学习系统应模拟人的学习过程，使系统通过与环境反复多次相互作用，逐步学到有关知识，并且要使系统在学习过程中通过实践验证、评价所学知识的正确性。v3.能用所学的知识解决问题v学习的目的在于应用，学习系统能把学到的信息用于对未来的估计、分类、决策和控制。 v4.能提高系统的性能v提高系统的性能是学习系统最终目标。通过学习，系统随之增长知识，提高解决问题的能力，使之能完成原来不能完成的任务，或者比原来做得更好。v学习系统至少应有环境、知识库、学习环节和执行环节四个基本部分。一种典型的机器学习系统（迪特里奇（Dietterich）学习模型）如图6-1所示。环境向系统的学习部件提供某些信息，学习环节利用这些信息修改知识库，增进执行部件的效能；执行环节根据知识库完成任务，同时把获得的信息反馈给学习部件。下面介绍其主要组成部分的功能。 1.环境v系统中的环境包括工作对象和外界条件。比如在医疗系统中，环境就是病人当前的症状，物化检验的报告和病历等信息；在模式识别中，环境就是待识别的图形或影物；在控制系统中，环境就是受控的设备或生产流程。v环境提供给系统的信息水平和质量对于学习系统有很大的影响。信息的水平是指信息的一般性程度，也就是适用范围的广泛性，高水平的信息往往比较抽象，适用面更广泛。v信息的质量指信息的正确性、信息选择的适宜性和信息组织的合理性。信息质量对学习难度有明显的影响。 2.学习环节v学习环节是系统的学习机构，是学习系统的核心。它通过对环境的搜索取得外部信息，然后经分析、综合、类比、推理等思维过程获得知识，并将这些知识送入知识库，供执行环节使用。v事实上，由于环境提供的信息水平与执行环节所需的信息水平之间往往有差距，学习环节的任务就是解决这个水平差距问题。如果环境提供较高水平的信息，学习环节就去就去补充遗漏的细节，以便执行环节能用于具体情况。如果环境提供较具体的低水平信息，即在特殊情况执行任务的实例，学习环节就要上此归纳规则，以便系统能完成更为一般的任务。 3.知识库v学习系统设计的另一个重要问题就是知识库的形成设计以及其内容。学习系统实质上就是对原有知识的扩充和完善。 4.执行环节v执行环节实际上是由执行环节和评价两部分组成，执行环节用于处理系统面临的现实问题，比如定理证明、智能控制、自然语言处理、机器人行动规划等；评价环节用来验证、评价执行环节执行的效果，比如结果的正确性等。评价环节的处理方法有两种，一种是把评价时所需的性能指标直接建立在系统中，由系统对执行环节所做出的结论进行评价；另一种是由人类协助完成评价工作。v另外，从执行环节到学习环节心须要有反馈信息。这们，学习环节就可以根据反馈信息决定是否要从环境中获取进一步的信息进行再学习，以便修改、完善知识库中的知识。 6.1.3机器学习分类v当前国际上流行的机器学习分类方法主要有四种：按应用领域分类：主要的应用领域有专家系统、认知模拟、规划和问题求解、数据挖掘、网络信息服务、图象识别、故障诊断、自然语言理解、机器人和博弈等。v按获取的知识的表示分类：有形式逻辑表达式、形式文法、代数表达式参数、图和网络、框架和模式、计算机程序和其它的过程编码、产生式规则、决策树、框架、神经网络等；v按推理策略分类：如演绎推理和归纳推理。v按学习系统性综合分类的方法：考虑了事物的历史渊源、知识表示、推理策略和应用领域等因素，是对前面三种分类方法的综合。 （一）基于推理策略的分类v一个学习过程实质上是学习系统把环境所提供的信息转换成新的形式，以便存储和使用。这种信息的转换就是种推理，而推理的性质确定了学习策略的类型。在学习过程中，学生所使用的推理越少，他对教师的依赖就越大，因而教师的负担就越重，反过来，学生使用的推理越多，教师的负担就越轻。显然，基于推理策略分类方法可以按学生使用推理的多少和难易程度进行。下面分别进行讨论。 v1.机械学习（Rote Learning）v机械学习是最简单的学习方法，它亦被称为记忆学习或死记硬背式学习。这种学习方法不需要推理，而是由教师向系统提供被记忆的信息，学习者无需任何推理或其它的知识转换，直接吸取环境所提供的信息，并用这些信息指导系统行为。v 机械学习是记忆，它仅保存新的知识以便使用。这里是个检索问题，而不是重复计算、推理或查询。机械学习可以认为是基本的学习方式，它本身并不能实现智能学习，但是它是其他学习系统所固有重要组成部分。在机械学习系统中，知识已经以某种方式获取，并且是一种直接可使用的形式。所有学习系统都是建立在机械学习的基础之上，即对知识库中的知识进行存储、维护和检索。 v2. 示教学习（Learning from Instruction or Learning by being told）v示教学习中，教师以某种形式（教导和建议）提出和组织知识，以使学生拥有的知识可以不断地增加。学生把知识转换成内部可使用的表示形式，并将新的知识和原有知识有机地结合为一体；示教系统中，由外部给系统提供抽象的、一般化的信息，学习系统经过选择和改造，把新的信息与系统原有的知识融为一体。由于外部提供的信息过于抽象，它的水平高于执行时所用信息的水平，因此学习环节要把把较高水平的知识转换为较低水平的知识，这种转换称为实用化。 v研究示教学习的途径主要有两种。一是在开发系统时接收抽象的、高级的信息，并将它变换成规则，以便批指导执行部分。二是开发完善的工具，比如知识库的编辑和调试辅助程序，使得专家们可以很方便地将专门知识转换成详细的规则。 v3. 演绎学习（Deductive Learning）v这种学习方法是一种常规的逻辑推理方法。其推理的过程通常从公理出发，经过逻辑变换，推导出结论。演绎学习包括知识改造、知识编译、生成宏操作、保持等价操作和其他的一些保真变换。 v4. 解释学习(Explanation-based Learning)v解释学习利用问题求解的示例，依赖领域知识构造出求解过程的因果解释结构，并获取控制知识，为以后类似问题求解提供指导。v解释学习过程可分成两个步骤：v首先产生解释结构：输入实例后，系统首先对问题进行求解。 v再用解释结构对得到的解释结构和事例进行概括：概括通常采取的方法是将常量转换成变量，且去掉某些不重要的信息，仅仅保留求解时所必需的那些关键信息，经过一定的方式进行组合形成产生式规则，从而获得概括性的控制知识。 v5. 类比学习（Learning by Analogy）v类比学习利用二个不同领域（源域、目标域）中的知识相似性，通过类比，从源域的知识（包括相似的特征和其它性质）推导出目标域的相应知识。例如：未开过货车的司机有开小车的知识就可完成开货车的任务；v类比学习是演绎和归纳学习的组合。它对不同论域的描述进行匹配，确定公共的子结构，以此作为类比映射。寻找公共子结构是归纳推理，而实现类比映射是演绎推理。 v6. 归纳学习（Inductive learning）v归纳学习由教师或环境提供某概念的一些实例或反例，学生通过归纳推理得出该概念的一般描述。归纳学习可分为示例学习和观察与发现学习。v示例学习（Learning from Examples ）v示例学习也称为概念获取（Concept Acquisition）。是由教师提供给系统某种概念的正例集合反例集合，学习通过归纳推理产生覆盖所有正例并排除所有反例的该概念的一般描述。这些正例是由已知概念的教师或者是学生做实验时从系统中得到的反馈信息而提供的。 v观察与发现学习（Learning from Observation and Discovery）v观察与发现学习是由环境提供一组观察事例，学生构造一个一般的概念描述（即理论）来覆盖所有或大多数事例。这是一种无导师学习。这类学习又分为观察学习与机器发现两类。 v（1）观察学习 观察学习是学生将已知事例进行分类，同时产生每一类的一般概念描述。观察学习又可根据是否渐近（incremental）方式而分为va概念聚类 b概念形成 v(2)机器发现（Machine Discovery）v学生从观察的事例或经验数据中进行归纳产生规律或规则，这就是机器发现。机器发现是观察与发现学习的最困难、最富有创造性的一种学习形式。机器发现包括有经验发现和知识发现两种类型。 （二）基于系统综合性的分类v基于系统性分类，机器学习可分为四种类型，即：归纳学习、分析学习、联接学习、遗传算法与分类系统。 v1分析学习（Analytie Learning）分析学习是针对几个实际例子，应用领域知识进分析来学习。 v2联结学习(connection based learning)联结学习的目标是区分输入模式的等价类。一个联结模型是由一些类似神经元的简单单元带权互边而组成的网络。 v3遗传算法（Genetic Algorithm）遗传算法似生物繁殖的突变（互换、倒位、点突变等）和达尔文的自然选择（在每一生态环境中适者生存）。 v4.加强学习（reinforcement learning）加强学习的学习目标是寻找一个合适的动作选择策略，使产生的动作序列可获得某种最优的结果（如累计立即回报最大）。基本方法是通过与环境的试探性（trial and error）交互来确定和优化动作的选择。 6.2示例学习v示例学习属于归纳学习，是目前机器学习方法中最成熟的方法之一。示例学习要求环境能够从一些特殊的实例（这些实例事先由教师划分为正例和反例两类），并由这些实例进行归纳推理，导出一般性的规则。 v6.2.1示例学习的两个空间模型v示例学习的模型如图6-2所示。例子空间是所有可能的正、反例构成的空间；假设空间（又称概念空间）是所有可能的概念描述（称为假设）构成的空间。v 假设空间中的每一假设都对应于例子空间中的一个子集，使得该子集中的例子均是该假设的例子。 v在图6-2中，除描绘从例子学习的实例空间规则空间外，还描绘了解释实例和实验规划过程。v在这个模型中，首先由示教者给实例空间提供一些初始示教例子，然后程序对示教例子进行解释。由于示教例子的形式往往不同于规则形式，所以有必要对例子进行解释。往后再利用被解释的示教例子支搜索规则空间。一般情况下不能一次就从规则空间中搜索到要求的规则，因此还要寻找一些新的示教例子，这个过程就是选择例子。此过程如此循环，直到搜索到要求的规则。 v（一）实例空间v考虑扑克牌中“同花”概念的问题，同花是五张同一花色所组成的手牌。在这个学习问题中，实例空间是五张牌的全部各手牌的集合。我们可以把这个空间中单个的点表示为一组五个有序对，比如：v （2，梅花），（3，梅花），（5，梅花），（J，梅花），（K，梅花）v每一有序对指明一张牌的点数和花色。整个实例空间是所有这样的五张牌集合的空间。高质量的示教例子是无二义性的，它可以为规则空间的搜索提供可靠的指导。低质量的示教例子会引起互相矛盾的解释，其结果仅为规则空间的搜索提供试探性的指导。示教例子排列次序也会影响学习的质量。 v一般情况下认为实例是同时提供的，也可以主动地选择另外一些附加的实例，以便修正假设，这种方法称为补充学习。还有的程序直接搜索实例空间，这种方法称主动选择例子。 v（二）规则空间v定义规则空间的目的是指定表示规则的操作符和术语。所谓规则空间是用指定的描述语言可以表示的所有规则(概念假设)的集合。对规则空间有三个方面的要求，即规则的表示形式应适应归纳推理，规则的表示与实例的表示一致，规则空间应包含要求的规则。 v三）解释例子v解释示教例子的基本目的是提取指导规则空间搜索有用的信息。通常是把示数例子转换成易于进行符号归纳的形式。不过，这种转换也许是困难的，尤其是在感性的学习中。 v (四）实验规则v一旦学习环节根据示教例子搜索规则空间，并产生可能合理的假设规则集合H后，程序就可能需要收集更多的训练实例加以测试和修改集合H。当实例空间和规则空间是以不相同的方法表示时，就需要判断训练哪些实例和怎样才能获得它们，这是一个复杂的过程。比如，假定一个遗传学习程序要想发现DNA的哪一部分是最重要的，为了测试几个高级假设（即假设的规则）要安排复杂的试验。这些试验合成DNA的特殊成分，并把它插入到适当的细菌细胞中，以观察细胞的最后动作。 v搜索规则空间的方法有：特化搜索既从最泛化的假设（概念描述）出发，每次取用一个新的例子，就产生一些特化的描述，直到将初始最泛化的假设特化为解描述。泛化搜索即从最特化的假设（相应于例子空间中的一个例子）开始，每次取用一个新的例子时，就产生一些泛化的描述，直到产生出足够泛化的解描述。大多数示例学习方法都采用这二种方法或这二个方法的结合。下面介绍搜索规则空间的几种方法。这些方法都具有一个假设规则的集合H，不同的仅仅是对H的改进，以便得到要求的规则。 v（1）变型空间法（version-space methold）v变型空间法是TMMitchell于1977年提出的一种数据驱动型的学习方法。v该方法以整个规则空间为初始的假设规则集合H。依据示教例子中的信息，系统对集合H进行一般化或特殊化处理，逐步缩小集合H。最后使得H收敛到只含有要求的规则。由于被搜索的空间H逐渐缩小，故称为变型空间法。 v 1规则空间的结构v在规则空间中，表示规则的点与点之间存在着一种由一般到特殊的偏序关系。我们定义为覆盖，例如，color(X,Y)覆盖color(ball,Z)，于是又覆盖color(ball,red)。v作为一个简单的例子，考虑有这样一些属性和值的对象域：v Sizes=large,smallv Colors=red,white,bluev Shapes=ball,brick,cubev这些对象可以用谓词obj(Sizes,Color,Shapes)来表示。用变量替换常量这个泛化操作定义 v如图6-3的空间。 v图6-3表示了一个规则空间偏序关系的一部分。我们可以把归纳学习看成是对同所有训练实例相一致的概念空间的搜索。在搜索规则空间时，使用一个可能合理的假设规则的集合H，是规则空间的子集，从图6-4可知，H中最一般的元素构成的子集为G，H中最特殊的元素构成的子集为S。在规则空间中，H是以G为上确界和以S为下确界的一段。因此，可以用G和要来表示集合H。 v2修选删除算法v Mitchell的学习算法称为候选删除算法。在这种算法中，把尚未被数据排除的假设称为可能假设，把所有可能假设构成的集合H称为变型空间。v 算法一开始，变型空间H包含所有的概念随着向程序提供示教正例后，程序就从变v型空间中删除候选概念。当变型空间仅包含有一个候选概念时，就找到了所要求的概念。v该算法分为四个步骤： (1)把H初始化为整个规则空间。这时G仅包含空描述。S包含所有最特殊的概念。v实际上，为避免S集合过大，算法把S初化为仅包含第一个示教正例。（2）接受一个新的示教例子。如果这个例子是正例，则从G中删除不包含新例的概念，然后修改S为由新正例和S原有元素同归纳出最特殊化的泛化。这个过程称为对集合S的修改过程。如果这个例子是反例，则从S中删去包含新例的概念，再对G作尽量小的特殊化，使之不包含新例。这个过程称为集合G的修改过程。（3）重复步骤，直到G=S，且使这两个集合都只含有一个元素为止。（4）输出H中的概念（即输出G或S）。 v3方法讨论v变型空间法还存在有一些弱点，需要加以改进。该方法的主要缺点是：v（1）抗干扰能力差v （2）无法发现析取概念 2.改进假设法v改进假设法（hypothesis-rfinement methold）也是一种数据驱动方法。这种方法表示规则和实例的形式不统一。程序根据例子选择一种操作，用该操作去改进假设规则集H中的规则。 v3.产生与测试法v产生与测试法（generate and test）是一种模型驱动方法（model-driven methold）。这种方法针对示教例子反复产生和测试假设的规则。在产生假设规则时，使用基于模型的知识，以便只产生可能合理的假设。 v4.方案示例法v方案示例法（schema instantiation）也是一种模型驱动方法。该方法使用规则方案的集合来约束可能合理的规则的形式，其中最符合示教例子的规则方案被认为是最合理的规则。数据驱动方法的优点是可以逐步接受示教例子，以渐近方式学习，特别是变型空间法，它很容易修改集合H，不要求程序回溯就可以考虑新的实例。而模型驱动方法难以逐步学习，它是通过检查全部实例来测试假设。在使用新假设时，它必须回溯或重新搜索规则空间。因为原来对假设的测试已不适用于新实例加入后的情况。 6.2.2示例学习的一个变种决策树学习算法 v 1 决策树v决策树归纳算法主要是通过一组输入输出样本构建决策树的有指导学习方法。一个典型的决策树学习系统采用的确是自顶向下的方法，在部分搜索空间中搜索解决方案。它可以确保求出一个简单的决策树，但未必是最简单的。v决策树一个属性节点的输出分枝和该节点的所有可能的检验结果相对应。图6-6给出了有两个输出属性X和Y的样本分类的一个简单决策树。所有属性值X和Y=B的样本属于类2。不论属性Y的值是多少，值X1的样本都属于类1。对于树中的非叶节点，可以沿着分枝继续分区样本，每一个子节点得到它相应的样本子集。 v生成决策树的一个著名的算法是Quinlan的ID3算法，它有一个改进版本叫C4.5。vID3算法从树的根节点处的所有训练样本开始，选取一个属性来分区这些样本。对属性的每一个值产生一个分枝。分枝属性值的相应样本子集被移到新生成的子节点上。 v自顶向下的决策树的生成算法的关键性决策是对节点属性值的选择。ID3和C4.5算法的属性选择的基础是基于节点所含的信息熵最小化。ID3的属性选择是根据一个假设，即：决策树的复杂度和所给属性值表达的信息量是密切相关的。基于信息论的方法，对一个样本进行分类时所做检验的数量最小，要选择的分类属性是可以给出最高信息增益的属性，即信息熵最小化的属性。ID3的扩展是C4.5算法，C4.5算法把分类属性扩展到数字属性。 v2 C4.5算法：生成一个决策树vC4.5算法最重要的部分是由一组训练样本生成一个初始决策树的过程。该算法生成一个决策树形式的分类器，决策树节点具有两种类型的结构：一个叶节点，表示一个类，一个决策点，它指定要在单个属性值上进行的检验，对检验的每个可能输出有一个分枝和子树。 v决策树可以用来对一个新鲜样本进行分类，这种分类从该树的根节点开始，然后移动样本直至达叶节点。在每个非叶决策点处，确定该节点的属性检验结果，把注意力转移到所选择子树的根节点上。例如，图6-7a中的决策树的分类模型问题，待分类的样本如图6-7b所示，然后，该算法将生成一条通过节点A，C，F（叶节点）的路径直到得出最终分类决策，即类2为止。 v 图6-7 基于决策树模型的一个新样本的分类 v C4.5算法的构架是基于享特的CLS方法，其通过一组训练样本T构造一个决策树。我们用 C1，C2，CK来表示这些类。集合T所含的内容信息有3种可能性：v 1T包含一个或更多的样本，它们全部属于单个的类Cj。那么T的决策树是由类C1标识的一个叶节点。v 2T不包含样本。决策树也是一个叶，但和该叶关联的类由不同于T的信息决定，如T中的绝大多数类。C4.5算法以在所给节点的双亲上出现最频繁的类作为准则。v 3T包含属于不同类的样本。这种情况下，是把T精化成朝向一个单类样本集的样本子集。根据某一个属性，选择具有一个或更多互斥的输出 O1，O2，On 的合适检验。T被分区成子集T1，T2，Tn，其中Ti包括T中所选择的检验的输出是Oi的所有样本。T的决策树包括标识检验的一个决策点和每个可能输出的一个分枝（图6-7a中的决策树的节点A，B和C是这种类型节点的例子）。 6.3 基于解释的学习v基于解释的学习是八十年代中期兴起的新型机器学习方法，是分析学习的主要方式，与基于大量训练例作归纳推理的数据密集型学习方法不同，基于解释的学习是知识密集型的，可克服归纳学习因缺乏领域知识的引导而面临的问题。基于解释的学习通过应用领域理论（领域知识）对单一事例所作的分析，构造出求解过程的因果解释结构，并获取控制知识，用于指导以后求解类似的问题。 v一、基于解释学习的工作原理v 基于解释学习也是属于通过实例学习的方法，与通过实例学习的方法与众不同之处在于学习系统除了实例之外，还需要具备有关领域的知识，并且能够根据这些知识对实例进行分析，从而构成解释，产生规则。 v 1986年Mitchell等人提出了基于解释学习的系统工作步骤：v 1产生解释v系统得到实例后首先进行问题求解，由目标反向推理，从领域知识库存中寻找有关规则，使基后件与目标匹配。找到这样的规则后，就把目标作为后件，该规则作为前件，并记录这一因果关系。然后以规则的前件作为子目标，进一步反复分解。如此反复沿着因果链进行，直到求解结束。一旦得到解，便证明了该例的目标是可满足的由此也得到证明的因果解释结构。v v2对解释结构的概括v对所得到的解释结构以及事件进行概括，是采用将常量转换为变量，去掉一些不重要的信息，仅保留求解所心需的那些关键信息，再由组合形成产生式规则，从而获得概括性的控制信息。vMitchell等人综合了以前各种基于解释的概括方法，提出了一个般化，独立具体领域的基于解释的学习方法基于解释的概括（EXPlanation-Bosed Generalization，简称EBG） v 给定：v 目标概念：对于所学概念的一个初始描述（其尚不满足可操作准则）；v 训练例子：目标概念的一个正例；v 领域理论：解释训练例子为何是目标概念正例时可用的规则和事实集合；v 可操作准则：学到的知识（对于目标概念的解释）所需遵从的表示形式，以使这些知识能用于问题求解活动。 v 获取：v对于目标概念的一个特化描述，其是训练例子的泛化，且满足可操作准则。v基于解释的概括过程有二个阶段：v (1) 解释：使用领域理论建立一个证明训练例子满足目标概念定义（初始描述）的解释结构；该结构可表示为一颗证明推理树，又称解释树，其每个分枝的叶节点上的表达式都必须满足可操作准则。v (2) 泛化：通过将解释结构中的常量变换为变量（实现对于训练例子的泛化），获得对于目标概念的一个特化描述，使其满足可操作准则：v * 基于解释结构对目标概念进行回归(regressing)， v * 对回归所得的表达式（相应于解释结构中的叶节点）加以合取 6.3.2基于解释学习的方法的举例 v1问题的逻辑描述v2. 产生解释结构 v3. 概括 6.4基于案例的推理v基于案例的推理（case-based reasoning，CBR）同人类的日常推理活动十分接近，它来自于人类的认知心理活动不同于传统的基于知识系统，CBR系统所信赖的知识主要是系统所存储的相关领域中以前解决问题的具体记录。 v1.CBR系统的特点v罗杰沙克（Roger Schank）是CBR研究的开创者，沙克（Schank）指出，CBR方法研究的原始动机，主要来源于对人类推理活动中“回忆”的重要地位的认识 v传统的基于知识系统（主要指知识表示采用产生式规则或框架架或语义网络的专家系统，ES）存在一定的困难，如：v知识获取的瓶颈问题v知识库维护的困难v推理链不能太长v固定的求解范围 vCBR方法在以下方面对基于规则的系统做出了改进：v以下讨论都假定非CBR知识系统的知识表示都采用产生式规则。1.知识获取2.知识库维护3.解决问题的范围5.解质量4.求解过程 v2.CBR系统的体系结构v一个CBR推理和学习过程可以分解为下面四个步骤：vstep1.从案例库中检索出与新案例最相似的案例或案例集；vstep2.把step1获得的案例（或案例集）中的信息和知识复用到新问题上；vstep3.修正所建议的解答；vstep4.把该次获得的经验保存起来，以备将来来使用。 6.4.3学习方法v基于案例的推理通过下面几种方法来完成它的大部分学习：v新案例的积累。保存成功的和失败的新案例。 v建立、修改和撤消指向案例的索引路径，完善索引机制。 v归纳学习。 vCBR方法的实现一般包含下面几个主要步聚：案例表示，索引和存储，检索，适应修改，评估和学习等。v(1)案例表示v基于案例的推理系统利用案例记录以前的问题求解的情况，应该包括与问题的解答有关的一切重要信息。v从问题求解角度来看，案例应包含对问题整体情况的描述，还应包含对问题的解或解决方法的描述。所以案例可被表成一个有序对：。 v（2）索引v案例库的索引（indexing）的目标是提供一种案例库的搜索机制，使得在将来的检索中能够快速找出符合需要的案例或案例集。v一个案例的索引就是这个案例的重要关键字的集合，这些关键字可以将这个案例同其他案例区分开来 v索引问题的主要任务包括：选择什么类型的索引、如何定义索引词汇表、如何构建索引的搜索空间等。 v(3)案例检索v检索任务开始于一个描述待求问题的新案例，利用案例库索引机制，根据相似性度量方法，在某种相似性程度阈值下，从案例库中找出一组与新案例匹配较好的旧案例，并从中选择出一个最佳的案例。v检索任务的子任务包括：特性鉴别（indentify feature），初始匹配（initially match），搜(search)和选择(select)。 v(4)相似性度量v相似性度量（similarity measure）在CBR系统中十分重要，合适的度量方法可以迅速、准确地找到所需要的案例。vCBR系统的相似性度量方法主要使用基于距离（基于计算）的方法，考虑到具体应用环境的特点扩展了的相似性度量方法和最近邻法（NNh,the nearest neighbor method）。 v(5)适应性修改v适应性修改可以被简单地理解为把解决文案的一部分用其他的内容替换，或者修改整个解决方案。适应性修改可以有几种形式苛以直接向解决方案中插入一些新内容，也呆以从解决方案中删除一些内容，可以替换解决方案的某一部分内容，也可以将某一部分内容改造。但是，要使CBR系统得到足够的适应性修改知识(Adaptation knowledge)是一件十分困难的任务。 v科洛德（Kolodner）提出了十种适应性修改的方法。v .重新例化v .参数调整v .局部搜索v询问/查询记忆（v .特殊化搜索v .基于案例的替换v .常识转化v .模型制导的修改补v .特定目的的修改和修补 v .推导重放上述的1至6属替换方法，7和8属于转化方法 v(6)评估和学习v评估任务需要在现实环境中应用该案例解答的结果，可以通过询问专家或在现实世界中具体执行任务来实现。这通常是CBR系统外部的一个步骤。根据应用的类型，评估结果可能需要一段时间。当某案例的评估结果没有得出时，该案例应标记为未评估案例。v学习过程把新案例中有意义的部分保存到系统的知识库中。它包括从案例中选择哪种信息进行保存，以什么形式保存，为新案例建立哪些索引，如何建立这些索引，如何存储新案例等等。 v 4. 结论v基于案例的推理是人工智能领域中较新出现的一种重要的基于知识的问题求解和学习方法。作为一种基于经验的问题求解技术，基于案例的推理（CBR）可以理解为修改旧的解决方案满足新的需要；使用旧案例解释新情况、评价新方案、构造新问题的解答。学习是CBR推理行为的副产品，它获得过去的经验并在以后的推理中能够回忆起来，这样它的推理能力和效率都能得到提高。v基于案例的推理系统的推理质量取决它具有的经验，即在那些旧经验的基础上理解新情况的能力、修改的能力、以及评价和改错的能力。基于案例的推理程序的主要过程是案例存储、检索、修改及审查。 6.5加强学习v加强学习是一种以环境反馈作为输入的、特殊的、适应环境的机器学习方法。所谓加强学习是指从环境状态到行为映射的学习，以使系统行为从环境中获得的累积奖赏值最大。 v加强学习通常包括两个方面的含义：一方面是将加强学习作为一类问题；另一方面是指解决这类问题的一种技术。v加强学习（reinforcement learning）又称再励学习或评价学习，是一种重要的机器学习方法，在智能控制机器人及分析预测等领域有许多应用。 6.5.1加强学习基本方法v在加强学习技术中首先对随机的、离散状态、离散时间这一类问题进行数学建模。在实际应用中，最常采用的是马尔可夫模型。表2中给出最常用的几种马氏模型。 v表2 常用的几种马氏模型 是否智能系统行为控制环境状态转移？ 马氏模型 否 是 否 马尔可夫链 马氏决策过程 是否环境为部 分可感知？ 是 隐马尔可夫模型 部分感知马氏决策过程 v下面给出马氏决策过程（Markov Decision Process，MDP）建模的形式化定义：v马氏决策过程 由四元组定义。包含一个环境状态集S，系统行为集合A，奖赏函数R：SA和状态转移函数P：SAPD（S）。记R（s，a，s）为系统在状态s采用a动作使环境状态转移到s获得的瞬时奖赏值；记P（s，a，s）为系统在状态s采用a动作使环境状态转移到s的概率。 v马氏决策过程的本质是：当前状态向下一状态转移的概率和奖赏值只取决于当前状态和选择的动作，而与历史状态和历史动作无关。因此在已知状态转移概率函数P和奖赏函数R的()环境模型知识下，可以采用动态规划技术求解最优策略。而加强学习着重研究在P函数和R函数未知的情况下，系统如何学习最优行为策略。加强学习可以简化为图6-13的结构。 v图6-13 加强学习结构 6.5.2加强学习技术目前主要研究方向v 1部分感知马氏决策过程中的强化学习v在实际的问题中，系统往往无法完全感知环境状态信息。即使环境属于马尔可夫型，但由于感知的不全面，对于状态之间的差异也无法区别。因此部分感知问题属于非马尔可夫型环境。在部分感知问题中，如果不对强化学习算法进行任何处理就加以应用的话，学习算法将无法收敛。v在部分感知模型中，不仅考虑动作的不确定性，同时也考虑状态的不确定性。这种环境描述更接近现实世界，因此应用面比马氏决策模型更广。解决部分感知问题的基本思路是将部分感知环境转换为马氏决策模型描述，即假设存在部分可观测（或不可观测）的隐状态集S满足马尔可夫属性。 v2加强学习中的函数估计v对于大规模MDP或连续空间MDP问题中，加强学习不可能遍历所有状态。因此要求加强学习的值函数具有一定泛化能力。加强学习中的映射关系包括：SA、SR、SAR、SAS等等。加强学习中的函数估计本质就是用参数化的函数逼近这些映射。 v3分层加强学习v经典马氏决策过程模型只考虑了决策的顺序性而忽略决策的时间性。基于马氏决策过程的加强学习都假设动作在单个时间步完成，因而无法处理需要在多个时间步完成的动作。为解决此问题，引入半马氏决策过程（SMDP，Semi-MDP）模型。在SMDP模型中，每个行为动作的时间间隔作为变量（整数或实数），并进一步可以细分为连续时间-离散事件SMDP和离散时间SMDP两种模型。在后者中，行为决策只在单位时间片的正整数倍做出，较前者模型简单。 v4 多agent加强学习v多agent加强学习是加强学习研究中非常重要的研究方向之一。在多agent系统中，环境在多个agent的联合动作下进行状态的迁移。对于单个agent来讲，由于其只能确定自身agent的行为动作，因此体现出一种行为动作上的“部分感知”，从而产生出另一种形式的非标准马尔可夫环境。多agent加强学习机制被广泛应用到各个领域，例如游戏、邮件路由选择、电梯群控系统以及机器人设计等等。 6.5.3结论v本部分综述了加强学习技术基本原理和目前主要研究方向。尽管在过去的二十年中，加强学习技术研究取得了突破性进展，但目前仍然存在许多有待解决的问题。在今后的若干年中，以下方面也将成为强化学习研究的重要研究内容。 1.加强学习与其他学习技术相结合的研究 v众所周知，加强学习的一个主要缺点是收敛慢。其根本原因在于学习过程仅仅从经验获得的奖赏中进行策略的改进，而忽略了大量其他有用的领域信息。因此，如何结合其他机器学习技术，如神经网络、符号学习等技术，来帮助系统加快学习速度是强化学习研究和应用的重要方向。目前，结合技术研究的主要难点在于：如何从理论上证明和保证学习算法的收敛性。 v2.非马氏决策过程中的新型加强学习算法研究 v经典的马氏决策模型是相当简单的，除了部分感知、连续状态、半马氏决策过程等模型外，在实际应用中还存在大量更加复杂的模型。例如，在图象的马尔可夫随机场模型中，状态的迁移是由历史多个相邻状态决定。因此，在更复杂马氏决策模型中发展有效的加强学习算法也将是未来重要的研究方向之一。 v3.加强学习应用研究v目前，加强学习的应用主要可以分为四类：制造过程控制、各种任务调度、机器人设计和游戏。另外，加强学习在学习分类器（Learning Classifier System）中的应用也逐渐成为研究的热点。从当前看来，加强学习的应用逐步向一些新的机器学习任务上拓展，如Web Log Mining、Web Crawling、Classification等等。因此，如何在新应用上快速、有效地部署和应用加强学习技术也是放在研究人员面前的挑战之一。