1、第六章 机器学习,概述实例学习基于解释的学习决策树学习神经网络学习,第六章 机器学习,概述实例学习基于解释的学习决策树学习神经网络学习,机器学习 概述,参考书：Machine Learning,Tom M. Mitchell, 1997,（机械出版社）什么是机器学习？Simon（1983）：学习就是系统中的变化，这种变化使系统比以前更有效地去做同样的工作。 Minsky (1985)：学习是在我们头脑中（心里内部）进行有用的变化。学习是一种具有多侧面的现象。学习的过程有：获取新的陈述性知识、通过教育或实践发展机械技能和认知能力、将新知识组织成为通用化和有效的表达形式、借助观察和实验发现新的事实
2、和新的理论。,机器学习 概述,基本形式知识获取和技能求精。 学习的本质就是获取新的知识。包括物理系统和行为的描述和建模，构造客观现实的表示。 知识获取通过实践逐渐改造机制和认知技能。 例：骑自行车。这些技能包括意识的或机制的协调。这种改进又是通过反复实践和从失败的行为中纠正偏差来进行的。 技能求精,机器学习 概述,知识获取的本质可能是一个自觉的过程，其结果是产生新的符号知识结构和智力模型。而技能求精则是下意识地借助于反复地实践来实现的。 本章只涉及学习的知识获取问题。,机器学习 概述,为什么要研究机器学习？人工智能主要是为了研究人的智能，模仿其机理将其应用于工程的科学。在这个过程中必然会问道：
3、“人类怎样做才能获取这种特殊技能（或知识）？”。,机器学习 概述,为什么要研究机器学习？当前人工智能研究的主要障碍和发展方向之一就是机器学习。包括学习的计算理论和构造学习系统。现在的人工智能系统还完全没有或仅有很有限的学习能力。系统中的知识由人工编程送入系统，知识中的错误也不能自动改正。也就是说，现有的大多数人工智能是演绎的、没有归纳推理，因而不能自动获取和生成知识。,机器学习 概述,为什么要研究机器学习？未来的计算机将有自动获取知识的能力，它们直接由书本学习，通过与人谈话学习，通过观察学习。它们通过实践自我完善，克服人的存储少、效率低、注意力分散、难以传送所获取的知识等局限性。一台计算机获取
4、的知识很容易复制给任何其它机器。,机器学习 概述,实现的困难： 预测难：学习后知识库发生了什么变化，系统功能的变化的预测。 归纳推理：现有的归纳推理只保证假，不保证真。演绎推理保真。而且，归纳的结论是无限多的，其中相当多是假的，给生成的知识带来不可靠性。 机器目前很难观察什么重要、什么有意义。,机器学习 概述,发展历史 神经系统模型和决策理论50年代开始。其特点是对开始与无初始结构和面向作业知识的通用学习系统感兴趣。包括构造多种具有随机或部分随机的初始结构的基于神经模型的机器。这些系统一般称为神经网络或自组织系统。由于当时计算机技术状态，多停留在理论和硬件上。这些元件类似于神经元，他们实现简单
5、的逻辑功能。,机器学习 概述,发展历史 神经系统模型和决策理论1965年左右，神经网络经验模式导致了模式识别这一新学科以及机器学习的决策理论方法。这种方法中学习就是从给定的一组经过选择的例子中获得判断函数，有线性的、多项式的、或相关的形式。当时，Samuel(1959-1963)的跳棋程序是最著名的成功的学习系统之一。达到了跳棋大师的水平。,机器学习 概述,符号概念获取1975年左右提出的。这类学习过程通过分析一些概念的正例和反例构造出这些概念的符号表示。表示的形式一般是逻辑表达式、决策树、产生式规则或语义网络。代表有Winston的ARCH。,机器学习 概述,知识加强和论域专用学习此方法是7
6、0年代中期开始，沿着符号主义路线进行的。在原有基础上逐步加强、重于专业的专用性。强调使用面向任务的知识和它对学习过程的引导作用。系统包括预先确定的概念、知识结构、论域约束、启发式规则和论域有关的变换。系统在开始并不具有所有的属性或概念，在学习过程中系统应得到一些新的属性或概念。 没有绝对的学习方法。许多系统体现出上述途径的组合。,机器学习 概述,机器学习进入新阶段的重要表现：（近十年）（1） 机器学习已成为新的边缘科学并在高校形成一门课程。它综合应用心理学、生物学和神经生理学以及数学、自动化和计算机科学形成机器学习理论基础。,机器学习 概述,机器学习进入新阶段的重要表现：（近十年）（2）结合各
7、种学习方法，取长补短的多种形式的集成学习系统的研究正在兴起。特别是连接学习，符号学习的耦合可以更好地解决连续性信号处理中知识与技能的获取与求精问题而受到重视。,机器学习 概述,机器学习进入新阶段的重要表现：（近十年）（3）机器学习与人工智能各种基础问题的统一性观点正在形成。例如：学习与问题求解结合进行，知识表达便于学习的观点产生了通用智能系统的组块学习。类比学习与问题求解结合的基于案例学习已成为经验学习的重要方向。,机器学习 概述,机器学习进入新阶段的重要表现：（近十年）（4）各种学习方法的应用范围不断扩大，一部分已形成商品。归纳学习的知识获取工具已在诊断分类性专家系统中广泛应用。连接学习在声
8、图文识别中占优势。分析学习用于设计综合性专家系统。遗传算法与强化学习在工程控制中有较好的应用前景。与符号系统耦合的神经网络连接学习将在企业的智能管理与智能机器人运动规划中发挥作用。,机器学习 概述,机器学习进入新阶段的重要表现：（近十年）（5）与机器学习有关的学术活动空前活跃。国际上除每年一次的机器学习研究会外，还有计算机学习理论会议及遗传算法会议。,机器学习 概述,机器学习模型学习是建立理论、形成假设和进行归纳推理的过程。 整个过程包括：信息的存储、知识的处理两部分,环境,学习环节,知识库,执行环节,机器学习 概述,分类：按学习策略机械式学习，直接输入新知识（记忆学习）学习者不需要进行任何推
9、理或知识转换，将知识直接装进机器中。根据示教学习（传授学习、指点学习）从老师或其它有结构的事物获取知识。要求学习者将输入语言的知识转换成它本身的内部表示形式。并把新的信息和它原有的知识有机地结合为一体。.,机器学习 概述,.通过类推学习（演绎学习）学习者找出现有知识中所要产生的新概念或技能十分类似的部分。将它们转换或扩大成适合新情况的形式，从而取得新的事实或技能。从例子中学习（归纳学习）给学习者提供某一概念的一组正例和反例，学习者归纳出一个总的概念描述，使它适合于所有的正例且排除所有的反例。（目前研究较多的一种方法）.,机器学习 概述,. 类比学习演绎学习与归纳学习的组合。匹配不同论域的描述、
10、确定公共的结构。以此作为类比映射的基础。寻找公共子结构是归纳推理，而实现类比映射是演绎推理。,机器学习 概述,研究目的希望得到通用的算法 研究了解学习知识的模型、认知模型 解决实际问题的知识库与系统，达到工程目标 研究特点不可预测性,第六章 机器学习,概述实例学习基于解释的学习决策树学习神经网络学习,第六章 机器学习,概述实例学习基于解释的学习决策树学习神经网络学习,实例学习,概述50年代兴起的实例学习是归纳学习的一种。目前实例学习在某些系统中的应用已成为机器学习走向实践的先导。环境提供给系统一些特殊的实例，这些实例事先由施教者划分为正例和反例。实例学习系统由此进行归纳推理得到一般规则。环境提
11、供给学习环节的正例和反例是低水平的信息，这是特殊情况下执行环节的行为。学习环节归纳出的规则是高水平的信息，可以在一般情况下用这些规则指导执行环节的工作。,实例学习,实例学习的两个空间模型,实例学习 两个空间模型,例：取实例空间为所有的人。 正例集合为张衡、华罗庚、李四光、吴有训、张光斗，反例为马克思、罗斯福、斯大林、丘吉尔。 学到的概念可以是中国人，或科学家，或中国科学家，等。而名人、已故名人、曾在20世纪生活过的人，等是不可能学到的。 学到的概念可能是不唯一的，除非正例集和反例集加起来正好等于整个实例空间。,实例学习 两个空间模型,描述例子空间的描述语言可以描述所有例子；规则空间的描述语言可
12、以描述所有规则。 例如：纸牌， 同花5张正例：(2, c), (3, c), (5, c), (J, c), (A, c), 其中c，草花club 规则：描述一手牌的全部谓词表达式的集合。 符号：SUIT(花色)，RANK（点数）常量：A, 2, 3, , 10. J, Q, K, clubs(草花), diamonds(方块), hearts（红桃）, spades(黑桃) 合取连接词， 存在量词所以有规则：对c1, c2, c3, c4, c5SUIT(c1, *)SUIT(c2, *)SUIT(c3, *)SUIT(c4, *)SUIT(c5, *),实例学习 两个空间模型,例子空间示教
13、例子的质量：不能有错，同时提供正例和反例，逐步分批由选择地送入。选择的条件：最有力地划分规则空间；证实肯定假设规则的集合；否定假设规则的集合。,实例学习 两个空间模型,解释例子解释例子的目的是从例子中提出用于搜索空间的信息。把示教例子变换成易于进行符号归纳的形式。 （有时很难）例如：Winston的积木世界中的“拱”的概念。,实例学习 两个空间模型,规则空间（最根本，真正学习的部分）定义：一套符号来规定表示规则的算符、术语，所有的描述都在其中。 归纳方法：从特殊到一般的推理 常量化为变量。例P189，从几个正例中找到共性的部分改成变量。 去掉条件。同上例。去掉牌点数这个条件 增加选择（析取）。
14、例人脸牌。从RANK(c1, J), RANK(c2, K)推出还有RANK(c3, Q)曲线拟合。几组值，解方程或用最小二乘法拟合成一条曲线或曲面。,实例学习 两个空间模型（规则空间）,不管是去掉还是增加，都是扩大范围。把已有的知识总结归纳推广。但是要小心。越快越强的方法越容易出错。原因是归纳推理方法是保假不保真。（真 ？，假 假）实际上没有很严格的具体方法。因此，用归纳方法的过程就是搜索过程。找到包含在少数例子中的正确信息。归纳出错就要回溯。要经常检验，用新例子去否定归纳出的错误规则。即解释例子和选择例子的反复，反复于例子空间和规则空间之间。,实例学习 两个空间模型（规则空间）,对规则空间
15、的要求表示应适应于归纳。如：有谓词才可以增减；有状态空间才能拟合。不同的归纳方法要求不同的规则表示方法。如果规则空间描述的语言的表达能力较弱，可以使用的归纳方法就比较少，规则空间的搜索范围就比较小，搜索就比较容易。但解决的问题就较少。因此，设计是在规则空间表达能力与规则空间搜索难度之间进行权衡。 表示和例子的一致。如相差很大，解释例子和选择例子的过程就很复杂。 引入新术语（规则空间）。当表示语言不能描述学习过程中产生的新状态时，要产生新的术语。,实例学习 两个空间模型（规则空间）,搜索规则空间的方法 最终的目的是为了搜索，先建立一个假设空间，在其中进行搜索。方法：怎样改进假设规则集，以便求得要
16、求的规则。 变形空间法Version-space：数据驱动 改进假设法Hypothesis-refinement：数据驱动 产生与测试Generate and Test：模型驱动 方案示例法Schema Instantiation：模型驱动 选择例子。 选择合适的例子，以能更好的搜索。,实例学习,实例学习的分类 按搜索方法分类：变形空间法；改进假设法；产生与测试法；方案示例法 按论域分类： 数字表示：多用于电子工程、系统理论和模式分析 知识：多项式、矩阵； 系统：自适应系统； 任务：模式分类、自适应控制、滤波等。符号表示：AI领域主要研究对象。 知识：符号的特征向量、一阶谓词、产生式规则、 框
17、架、语义网络；,实例学习 实例学习的分类,按任务复杂程度分类： 学习单个概念：最基本的 学习多个概念：归纳出多个相互独立的概念 学习执行多步任务：一个操作序列去完成任务，即执行环节对任务要规划。,实例学习,学习单个概念概念： 采用谓词逻辑的知识表示时，一个概念就是一个谓词公式。学习单个概念就是给系统一个概念的若干正例合反例，系统由此归纳出表示这个概念的谓词公式。 过程：给定：概念的表示语言；正例和反例寻找：一条规则。覆盖全部正例，不覆盖 全部反例。,实例学习 学习单个概念,变形空间法变形空间方法以整个规则空间为初始的假设规则集合H。依据示教例子中的信息，对集合H进行一般化或特殊化处理。逐步缩小
18、集合H，最后使H收敛为只含有要求的规则由于被搜索的空间H逐步缩小，故称为变形空间。,变形空间图,实例学习 学习单个概念（变形空间法）,搜索：使用一个可能合理的假设规则的集合H，H是规则空间的子集，是规则空间中间的一段。H中最一般的元素组成的子集称为G集合，最特殊的元素组成的子集称为S集合。（H是上界G和下界S之间的一段。 ）学习基本思想：尽可能合理的进行特殊化和一般化处理，通过搜索减小H，找到一个假设规则。 具体方法：消除候选元素法。,实例学习 学习单个概念（变形空间法）,结论S是规则充分条件，G是规则必要条件的集合。学习结束时找到的应是充分必要条件。 正例的主要工作是对S一般化，反例是对G特
19、殊化。搜索的过程是在例子的引导下，数据驱动。遵循的是变量优先的原则。 正例去掉G中不符合的概念，然后修改S ,归纳出最特殊的结果,尽量少改S。 反例去掉S中符合的概念，然后修改G,做特殊化得到最一般的结果,尽量少改G.,实例学习 学习单个概念（变形空间法）,变形空间法的优缺点： 搜索空间太大，有可能引起计算爆炸问题（规则总地来说是越扩越多） 抗干扰性差，所有数据驱动方法的通病。解决方法：例子一组一组地给。 采用析取规则，即此算法不可能发现“或”的关系。,实例学习 学习单个概念,改进假设方法也是数据驱动的方法。用改进操作来修改规则空间中的假设。然后根据示教例子用启发式方法选择这些操作。 优点：能
20、发现实质变量间关系缺点：仅能在特殊情况下才能使用操作。变量的选样，对例子的提供很敏感,实例学习 学习单个概念,产生与测试方法 模型驱动的方法。优点：比变形空间法更快，存储量更少，抗干扰。即使例子中有干扰，就选覆盖大多数例子的规则即可。 缺点：没有很完善的模型指导修剪和结束搜索。同时，因为修剪所以不完备，不一定能找到全部合格的概念。而且一次需要全部例子，不适合于逐步学习。,实例学习 学习单个概念,方案示例方法 模型驱动的方法。常用于理解性任务。如：图像、语音、自然语言理解。优点：可以很快找到要求规则，抗干扰性好缺点：难以划分出几种方案。有的规则不能被现有的方案覆盖。每个方案要专门研究，使用不同的
21、解释方法。,实例学习,学习多个概念单个规则：可存在规则将空间一分为二规则集合有相交，主要问题是重叠部分。学习多步任务多步学习就是选择一系列规则，去完成一系列步骤。如下棋，积分。 难点 多规则一起使用，规则之间的相互联系，影响。 奖罚分配问题 透明度,第六章 机器学习,概述实例学习基于解释的学习决策树学习神经网络学习,第六章 机器学习,概述实例学习基于解释的学习决策树学习神经网络学习,基于解释的学习,Explanation-Based Learning(EBL).也是由实例学习。是近几年出现的机器学习方法。基于解释的学习，不考虑很多实例，采用演绎推理，少用归纳。可以克服归纳学习的不可靠问题。利用
22、单个问题的求解例子，依领域知识对实例进行详细分析，构造求解过程的因果解释结构，并获取控制知识，然后对解释进行推广得到一般性描述，以便用于指导以后求解类似问题。从本质上是属于演绎学习。参考书：高级人工智能史忠植，科学出版社,基于解释的学习(简介),历史:起源于经验学习，50年代末出现用符号来标记存储结构模型的方法（神经模型）。即存储块chunk的概念。如同围棋、象棋大师脑中的棋谱。80年代初，Newell, Rosenbloom提出通过获取任务环境中关于模型问题的知识，可以改进系统的性能。开始将chunk作为对人类行为进行模拟的模型基础。获取的是控制知识，因此，可以明显提高系统求解速度，奠定了经
23、验学习的基础。 最终是1983年，美国Illinois大学的Dejong提出了基于解释的学习。在经验学习的基础上，运用一个或少数个例子，加上知识库，做出解释。1986又进一步提出了明确的定义。产生了该名词。,基于解释的学习(简介),解释：专家系统是给用户看的，所以，推理过程要说明搜索过程记录下来，以便对错误决策进行追踪，发现知识库和概念的错误。对初学者进行训练。 方法：预制文本法；执行追踪法；策略解释法。,基于解释的学习(简介),可操作性机器学习得到的知识，应该有用且有尽量大的适应范围。因此要考虑可操作性和一般性。希望学到的概念描述有利于提高系统运行效率。可操作：如果一个概念描述能有效的用于识
24、别相应概念的例子。给定：一个概念描述；一个执行系统；改善系统的各种要求，应明确各要求的类型和程度。可操作满足：可用性。执行系统可以使用该概念描述。效用性。执行系统使用概念描述时，系统的运行得到要求的改善。,解释学习的空间描述,外延集合,内涵属性,基于解释的学习(简介),解释空间的描述概念空间：某个学习程序能描述的所有概念的集合，其中每一点对应例子空间的唯一的一个子集合。例：C1对应I1，I2，I3。但概念空间的一个点可以对应概念描述空间的多个点。例：C1对应不可操作的D1和可操作的D2。对应同一概念的两个描述称为同义词。解释学习的任务：把不可操作的描述转化为可操作的描述。例：D1是搜索的开始结
25、点，D2是解结点，解释是空间的变换，而可操作性是搜索结束的标准。从D1到D2的过程称作概念可操作。,解释学习的框架,基于解释的学习(简介),解释学习的模型执行系统：PS学习系统：EXL领域知识库：KB(不同描述间转换的集合)系统工作过程EXL输入概念C1的描述D1（一般是不可操作的）根据KB中的知识，对其进行不同的转换（搜索）PS对每个转换结果进行测试，直至转换结果是PS可以接受的描述D2（可操作的）时，学习结束，输出D2,基于解释的学习(简介),一般框架：给定：领域知识、目标概念、训练实例和操作性准则。领域知识：描述领域的事实和规则，背景知识，用来证明训练实例为什么可作为目标概念的实例。训练
26、实例：为了解释学习提供的一个例子，解释学习正是从该例出发，通过运用领域知识进行证明，最终推广出目标概念的描述。操作性准则：用于指明哪些测试在运行时容易判定，指导系统对描述目标的概念进行取舍。找出：满足操作性准则的关于概念的充分条件,基于解释的学习(简介),步骤：产生解释，求解问题。从知识库中寻求 规则，然后进一步对规则进行分解推理。反复进行直到求解结束。方法： (反向推理） 目标规则1， 子目标(规则1） 规则2，子目标(规则2） 规则3， 如得到解，则证明了该例的目标可满足。并获得了构成动作序列，作为解释结构。产生解释结构：可以，所有算子构成动作序列，作为解释结构。也可以，自顶向下的遍历证明
27、树结构。结构可与解释同时生成，也可在解释完毕后再生成。对得到的解释结构以及事件进行概括。,基于解释的学习(方法1),解释和概括交替进行1987年由斯坦福大学Haym和Hirsh提出。描述：用逻辑的表示方法，语义清晰例：见书产生解释结构：从目标开始反向推理（从上到下）。分解：根据条件，如light计算：条件不满足时计算得到条件,如weight生成控制规则（ 概括化的产生式规则）（从下到上）所有叶结点的合取作为前件，（5项）以定点的目标概念作为后件。略去解释结构的中间部件。应用：把叶结点查一遍，不用中间结点。,解释学习例题,学习的目标：一个物体x可以安全的放置在另一个物体y的上面”。目标概念：Sa
28、fe-to-stack(x，y) x在y上安全堆放训练实例：前提：重量、体积、密度，Weight(obj1, 0.1)、Weight(obj2, 5)、Volume(obj1，1)、Density(obj1, 0.1)条件： Lighter(obj1, obj2)、状态： On(obj1，obj2)是什么： Is-a(obj1，book) 、Is-a(obj2，table)、 Is-a(p, table)Weight(p, 5)领域知识（安全放置的准则、条件）：Fragile(y)Safe-to-stack(x, y)、Lighter(x, y)Safe-to-stack(x, y)乘法计算、
29、比较计算Volume(p, v)Density(p, d)Product(v, d, w)Weight(p, w)Weight(p1, w1)Weight(p2, w2)Smaller(w1, w2)Lighter(p1, p2),1）由Safe-to-stack(obj1, obj2)，寻找其条件（前件）。因为没有Fragile(y)，所以选择Lighter(x, y)。得到Lighter(obj1, obj2)。 2）继续寻找其前件，由比较计算公式可知Lighter(obj1, obj2)的前件（条件）为Weight(p1, w1)Weight(p2, w2)Smaller(w1, w2)
30、。得到Weight(obj1, 0.1)Weight(obj2, 5)Smaller(0.1, 5)。 3）在继续分别寻找各个元素的前件。有前件就填上前件，没有前件，该结点就是叶子结点。直到全部结点都是叶子结点，便得到了解的解释结构树。,Safe-to-stack(obj1, obj2)的解释结构,Safe-to-stack(O1, O2)的概括化解释结构,规则是Volume(O1,v1)Density(O1,d1)Product(v1,d1,w1)Is-a(O2,table) smaller(w1,5)Safe-to-stack(O1,O2)学习后的结果使用时把叶结点查一查就可以了，叶结点满
31、足了即可（不考虑中间结点）例如：满足条件Volume(O1,v1)Density(O1,d1)Product(v1,d1,w1)Is-a(O2,table) smaller(w1,5)即可推出Safe-to-stack(O1,O2),基于解释的学习(方法2),基于解释的详细说明法(Explanation Based Specialization)1987年CMU的Minton和Carbonell提出。开发了PRODIGY学习系统克服了EBG（解释和概括交替进行）的过分一般化的缺点。解释过程对每个目标概念进行详细的描述，将有关目标概念的描述转换成一条相应的控制规则。目标概念学习:成功(prefe
32、rence)、失败(rejection)、唯一的选择(selection)、目标互相制约(restricted)分析问题求解轨迹，解释为何满足该概念有解：成功；无解：失败；选择唯一：唯一；依赖于别的目标：互相制约得到的结果就是相应种类（成功、无解、唯一、制约）的规则,基于解释的学习(方法2),具体方法（体系结构图）解释过程：就是详细的说明过程。以目标概念为根，生成一棵自顶向下的证明树。解释每一步，从领域库中选择与所给例子一致的规则，生成一个结点。每条规则是对结点子目标的详细描述。学习控制规则：四种目标概念，有四种固定的控制规则模式。将某个目标概念的详细描述与规则模式匹配，就获得相应的控制规则例
33、见书知识表示：领域层公理（领域规则）；构筑层公理（推理规则）没有明显的概括化过程。领域规则，特别是问题求解器的推理规则实际上已经进行了概括化处理。即不是最原始的领域知识构成，实际上具有一定的概括性。,基于解释的学习(方法3),由外部指导学习控制chunk方法1987年斯坦福大学与密西根大学教授提出。 （SOAR系统）学习机制：由外部专家的指导来学习一般的搜索控制知识。体系结构图外部指导直接的指令式：由专家指定一个算子求解。有解可行间接的简单直观形式：原文体按语法分解成树结构的内部表示，并附上初始状态。然后再请求专家劝告（一个直观简单问题）。学习机制工作存储单元收集例子并构成chunk建立子目标
34、后，首先将当时的状态存入工作存储单元得到解后，系统从工作存储单元中取出子目标的初始状态删去与解无关的部分，保留部分作为前件。以专家指定的算子或求解简单问题所得出的结算子作为结论动作，至此生成产生式规则。,基于解释的学习(可操作性),可操作性：可操作性是一个输入要求。可操作性标准：“概念描述应该表示为描述训练例的那些谓词或其它领域理论中挑选出来的易于估值的谓词”；“如果一个概念能有效的用于识别相应的概念的例子，则它是可操作的”PRODIGYSOAR系统MRS-EBG系统META-LEX系统可操作性对于基于解释的学习系统是至关重要的。但是，目前检测可操作性的方法决定于能否简化系统的性能假设（这些假设很容易在学习过程中被破坏）。尽管在这方面国内外的研究人员一直在寻找有效的处理方法，但多数只是处于理论研究阶段，应用于实际系统中的尚未达到令人满意的程度。,
