人工智能第六章机器学习

1、第六章 机器学习,概述 实例学习 基于解释的学习 决策树学习 神经网络学习,第六章 机器学习,概述 实例学习 基于解释的学习 决策树学习 神经网络学习,机器学习 概述,参考书： Machine Learning,Tom M. Mitchell, 1997,（机械出版社） 什么是机器学习？ Simon（1983）：学习就是系统中的变化，这种变化使系统比以前更有效地去做同样的工作。 Minsky (1985)：学习是在我们头脑中（心里内部）进行有用的变化。 学习是一种具有多侧面的现象。学习的过程有：获取新的陈述性知识、通过教育或实践发展机械技能和认知能力、将新知识组织成为通用化和有效的表达形式、借

2、助观察和实验发现新的事实和新的理论。,机器学习 概述,基本形式 知识获取和技能求精。 学习的本质就是获取新的知识。包括物理系统和行为的描述和建模，构造客观现实的表示。 知识获取 通过实践逐渐改造机制和认知技能。 例：骑自行车。这些技能包括意识的或机制的协调。这种改进又是通过反复实践和从失败的行为中纠正偏差来进行的。 技能求精,机器学习 概述,知识获取的本质可能是一个自觉的过程，其结果是产生新的符号知识结构和智力模型。 而技能求精则是下意识地借助于反复地实践来实现的。 本章只涉及学习的知识获取问题。,机器学习 概述,为什么要研究机器学习？ 人工智能主要是为了研究人的智能，模仿其机理将其应用于工程

3、的科学。在这个过程中必然会问道：“人类怎样做才能获取这种特殊技能（或知识）？”。,机器学习 概述,为什么要研究机器学习？ 当前人工智能研究的主要障碍和发展方向之一就是机器学习。包括学习的计算理论和构造学习系统。 现在的人工智能系统还完全没有或仅有很有限的学习能力。系统中的知识由人工编程送入系统，知识中的错误也不能自动改正。也就是说，现有的大多数人工智能是演绎的、没有归纳推理，因而不能自动获取和生成知识。,机器学习 概述,为什么要研究机器学习？ 未来的计算机将有自动获取知识的能力，它们直接由书本学习，通过与人谈话学习，通过观察学习。 它们通过实践自我完善，克服人的存储少、效率低、注意力分散、难以

4、传送所获取的知识等局限性。一台计算机获取的知识很容易复制给任何其它机器。,机器学习 概述,实现的困难： 预测难：学习后知识库发生了什么变化，系统功能的变化的预测。 归纳推理：现有的归纳推理只保证假，不保证真。演绎推理保真。而且，归纳的结论是无限多的，其中相当多是假的，给生成的知识带来不可靠性。 机器目前很难观察什么重要、什么有意义。,机器学习 概述,发展历史 神经系统模型和决策理论 50年代开始。其特点是对开始与无初始结构和面向作业知识的通用学习系统感兴趣。包括构造多种具有随机或部分随机的初始结构的基于神经模型的机器。这些系统一般称为神经网络或自组织系统。由于当时计算机技术状态，多停留在理论和

5、硬件上。这些元件类似于神经元，他们实现简单的逻辑功能。,机器学习 概述,发展历史 神经系统模型和决策理论 1965年左右，神经网络经验模式导致了模式识别这一新学科以及机器学习的决策理论方法。这种方法中学习就是从给定的一组经过选择的例子中获得判断函数，有线性的、多项式的、或相关的形式。 当时，Samuel(1959-1963)的跳棋程序是最著名的成功的学习系统之一。达到了跳棋大师的水平。,机器学习 概述,符号概念获取 1975年左右提出的。这类学习过程通过分析一些概念的正例和反例构造出这些概念的符号表示。表示的形式一般是逻辑表达式、决策树、产生式规则或语义网络。代表有Winston的ARCH。,

6、机器学习 概述,知识加强和论域专用学习 此方法是70年代中期开始，沿着符号主义路线进行的。在原有基础上逐步加强、重于专业的专用性。强调使用面向任务的知识和它对学习过程的引导作用。 系统包括预先确定的概念、知识结构、论域约束、启发式规则和论域有关的变换。系统在开始并不具有所有的属性或概念，在学习过程中系统应得到一些新的属性或概念。 没有绝对的学习方法。许多系统体现出上述途径的组合。,机器学习 概述,机器学习进入新阶段的重要表现：（近十年）（1） 机器学习已成为新的边缘科学并在高校形成一门课程。它综合应用心理学、生物学和神经生理学以及数学、自动化和计算机科学形成机器学习理论基础。,机器学习 概述,

7、机器学习进入新阶段的重要表现：（近十年）（2） 结合各种学习方法，取长补短的多种形式的集成学习系统的研究正在兴起。特别是连接学习、符号学习的耦合可以更好地解决连续性信号处理中知识与技能的获取与求精问题而受到重视。,机器学习 概述,机器学习进入新阶段的重要表现：（近十年）（3） 机器学习与人工智能各种基础问题的统一性观点正在形成。例如：学习与问题求解结合进行，知识表达便于学习的观点产生了通用智能系统的组块学习。类比学习与问题求解结合的基于案例学习已成为经验学习的重要方向。,机器学习 概述,机器学习进入新阶段的重要表现： （近十年）（4） 各种学习方法的应用范围不断扩大，一部分已形成商品。归纳学习

8、的知识获取工具已在诊断分类性专家系统中广泛应用。连接学习在声图文识别中占优势。分析学习用于设计综合性专家系统。遗传算法与强化学习在工程控制中有较好的应用前景。与符号系统耦合的连接学习的神经网络将在企业的智能管理与智能机器人运动规划中发挥作用。,机器学习 概述,机器学习进入新阶段的重要表现：（近十年）（5） 与机器学习有关的学术活动空前活跃。国际上除每年一次的机器学习研究会外，还有计算机学习理论会议及遗传算法会议。,机器学习 概述,机器学习模型 学习是建立理论、形成假设和进行归纳推理的过程。 整个过程包括：信息的存储、知识的处理两部分。,环境,知识库,执行环节,学习环节,机器学习 概述,分类：按

9、学习策略 机械式学习，直接输入新知识（记忆学习） 学习者不需要进行任何推理或知识转换，将知识直接装进机器中。 根据示教学习（传授学习、指点学习） 从老师或其它有结构的事物获取知识。要求学习者将输入语言的知识转换成它本身的内部表示形式。并把新的信息和它原有的知识有机地结合为一体。,机器学习 概述,通过类推学习（演绎学习） 学习者找出现有知识中所要产生的新概念或技能十分类似的部分。将它们转换或扩大成适合新情况的形式，从而取得新的事实或技能。 从例子中学习（归纳学习） 给学习者提供某一概念的一组正例和反例，学习者归纳出一个总的概念描述，使它适合于所有的正例且排除所有的反例。（目前研究较多的一种方法）

10、,机器学习 概述,类比学习 演绎学习与归纳学习的组合。匹配不同论域的描述、确定公共的结构。以此作为类比映射的基础。寻找公共子结构是归纳推理，而实现类比映射是演绎推理。,机器学习 概述,研究目的 希望得到通用的算法 研究了解学习知识的模型、认知模型 解决实际问题的知识库与系统，达到工程目标 研究特点 不可预测性,第六章 机器学习,概述 实例学习 基于解释的学习 决策树学习 神经网络学习,第六章 机器学习,概述 实例学习 基于解释的学习 决策树学习 神经网络学习,实例学习,概述 50年代兴起的实例学习是归纳学习的一种。目前实例学习在某些系统中的应用已成为机器学习走向实践的先导。 环境提供给系统一些

11、特殊的实例，这些实例事先由施教者划分为正例和反例。实例学习系统由此进行归纳推理得到一般规则。 环境提供给学习环节的正例和反例是低水平的信息，这是特殊情况下执行环节的行为。学习环节归纳出的规则是高水平的信息，可以在一般情况下用这些规则指导执行环节的工作。,实例学习,实例学习的两个空间模型：,实例学习 两个空间模型,例：取实例空间为所有的人。 正例集合为张衡、华罗庚、李四光、吴有训、张光斗，反例为马克思、罗斯福、斯大林、丘吉尔。 学到的概念可以是中国人，或科学家，或中国科学家，等。而名人、已故名人、曾在20世纪生活过的人，等是不可能学到的。 学到的概念可能是不唯一的，除非正例集和反例集加起来正好等

12、于整个实例空间。,实例学习 两个空间模型,描述 例子空间的描述语言可以描述所有例子；规则空间的描述语言可以描述所有规则。 例如：计算机如何掌握扑克牌“同花”5张这个概念。 正例：(2, c), (3, c), (5, c), (J, c), (A, c), 其中c表示草花club 反例： (8, c), (3, s), (9, p), (Q, h), (3, d) 例子空间：描述一手牌的全部谓词表达式的集合。,实例学习 两个空间模型,谓词表达式可以使用下列符号表示： 谓词：SUIT(花色)，RANK（点数） 常量：A, 2, 3, , 10. J, Q, K, clubs(草花), diamo

13、nds(方块), hearts（红桃）, spades(黑桃) 表示牌的变量： c1、c2、c3、c4、c5 某些必要的自由变量：x、y、z 合取连接词， 存在量词 同花的概念可以表示为下列规则： (c1, c2, c3, c4, c5) SUIT(c1,x)SUIT(c2,x) SUIT(c3,x)SUIT(c4,x)SUIT(c5,x),实例学习 两个空间模型,例子空间 示教例子的质量：不能有错，同时提供正例和反例，逐步分批有选择地送入。 选择的条件：最有力地划分规则空间；证实肯定假设规则的集合；否定假设规则的集合。,实例学习 两个空间模型,解释例子 解释例子的目的是从例子中提出用于搜索空

14、间的信息。把示教例子变换成易于进行符号归纳的形式。 （有时很难） 例如：Winston的积木世界中的“拱”的概念。,实例学习 两个空间模型,规则空间（最根本、真正学习的部分） 定义：一套符号来规定表示规则的算符、术语，所有的描述都在其中。 归纳方法：从特殊到一般的推理 常量化为变量。例P221，从几个正例中找到共性的部分改成变量。 去掉条件。同上例，去掉牌点数这个条件 。 增加选择（析取）。例人脸牌。从RANK(c1, J), RANK(c2, K)推出，还有RANK(c3, Q)。 曲线拟合。几组值，解方程或用最小二乘法拟合成一条曲线或曲面。,实例学习 两个空间模型（规则空间）,不管是去掉还

15、是增加，都是扩大范围。把已有的知识总结归纳推广。但是要小心，越快越强的方法越容易出错。原因是归纳推理方法是保假不保真。（真 ？，假 假） 实际上没有很严格的具体方法。 因此，用归纳方法的过程就是搜索过程。找到包含在少数例子中的正确信息。归纳出错就要回溯。要经常检验，用新例子去否定归纳出的错误规则。即解释例子和选择例子的反复，反复于例子空间和规则空间之间。,实例学习 两个空间模型（规则空间）,对规则空间的要求 表示应适应于归纳。如：有谓词才可以增减；有状态空间才能拟合。不同的归纳方法要求不同的规则表示方法。如果规则空间描述的语言的表达能力较弱，可以使用的归纳方法就比较少，规则空间的搜索范围就比较

16、小，搜索就比较容易。但解决的问题就较少。因此，设计是在规则空间表达能力与规则空间搜索难度之间进行权衡。 表示和例子的一致。如相差很大，解释例子和选择例子的过程就很复杂。 引入新术语（规则空间）。当表示语言不能描述学习过程中产生的新状态时，要产生新的术语。,实例学习 两个空间模型（规则空间）,搜索规则空间的方法 最终的目的是为了搜索，先建立一个假设空间，在其中进行搜索。 方法：怎样改进假设规则集，以便求得要求的规则。 变形空间法Version-space：数据驱动 改进假设法Hypothesis-refinement：数据驱动 产生与测试Generate and Test：模型驱动 方案示例法S

17、chema Instantiation：模型驱动 选择例子 选择合适的例子，以能更好的搜索。,实例学习的分类 按搜索方法分类： 变形空间法 改进假设法 产生与测试法 方案示例法,实例学习 实例学习的分类,按论域分类： 数字表示：多用于电子工程、系统理论和模式分析 知识：多项式、矩阵； 系统：自适应系统； 任务：模式分类、自适应控制、滤波等。 符号表示：AI领域主要研究对象 知识：符号的特征向量、一阶谓词、产生式规则、框架、语义网络。,实例学习 实例学习的分类,实例学习 实例学习的分类,按任务复杂程度分类： 学习单个概念：最基本的 学习多个概念：归纳出多个相互独立的概念 学习执行单步任务： 学习

18、执行多步任务： 一个操作序列去完成任务，即执行环节对任务要规划。,学习单个概念 概念： 采用谓词逻辑的知识表示时，一个概念就是一个谓词公式。学习单个概念就是给系统一个概念的若干正例和反例，系统由此归纳出表示这个概念的谓词公式。 过程： 给定：概念的表示语言；正例和反例 寻找：一条规则。覆盖全部正例，不覆盖 全部反例。,实例学习 学习单个概念,实例学习 学习单个概念,变形空间法 变形空间方法以整个规则空间为初始的假设规则集合H。 依据示教例子中的信息，对集合H进行一般化或特殊化处理。逐步缩小集合H，最后使H收敛为只含有要求的规则 由于被搜索的空间H逐步缩小，故称为变形空间。,变形空间图,实例学习

19、 学习单个概念（变形空间法）,搜索：使用一个可能合理的假设规则的集合H，H是规则空间的子集，是规则空间中间的一段。H中最一般的元素组成的子集称为G集合，最特殊的元素组成的子集称为S集合。（H是上界G和下界S之间的一段。 ） 学习基本思想：尽可能合理的进行特殊化和一般化处理，通过搜索减小H，找到一个假设规则。 具体方法：消除候选元素法。,实例学习 学习单个概念（变形空间法）,结论 S是规则充分条件，G是规则必要条件的集合。学习结束时找到的应是充分必要条件。 正例的主要工作是对S一般化，反例是对G特殊化。搜索的过程是在例子的引导下，数据驱动。遵循的是变量优先的原则。 正例去掉G中不符合的概念，然后

20、修改S，归纳出最特殊的结果，尽量少改S。 反例去掉S中符合的概念，然后修改G，做特殊化得到最一般的结果，尽量少改G。,实例学习 学习单个概念（变形空间法）,变形空间法的优缺点： 搜索空间太大，有可能引起计算爆炸问题（规则总地来说是越扩越多） 抗干扰性差，所有数据驱动方法的通病。解决方法：例子一组一组地给。 采用析取规则，即此算法不可能发现“或”的关系。,实例学习 学习单个概念,改进假设方法 也是数据驱动的方法。用改进操作来修改规则空间中的假设，然后根据示教例子用启发式方法选择这些操作。 优点： 能发现实质变量间关系 缺点： 仅能在特殊情况下才能使用操作。变量的选样，对例子的提供很敏感,实例学习

21、 学习单个概念,产生与测试方法 模型驱动的方法 优点：比变形空间法更快，存储量更少，抗干扰。即使例子中有干扰，就选覆盖大多数例子的规则即可。 缺点：没有很完善的模型指导修剪和结束搜索。同时，因为修剪所以不完备，不一定能找到全部合格的概念。而且一次需要全部例子，不适合于逐步学习。,实例学习 学习单个概念,方案示例方法 模型驱动的方法。常用于理解性任务。如：图像、语音、自然语言理解。 优点： 可以很快找到要求规则，抗干扰性好。 缺点： 难以划分出几种方案。有的规则不能被现有的方案覆盖。每个方案要专门研究，使用不同的解释方法。,实例学习,学习多个概念 单个规则：可存在规则将空间一分为二。 规则集合有

22、相交，主要问题是重叠部分。 学习多步任务 多步学习就是选择一系列规则，去完成一系列步骤。如下棋、积分。 难点 多规则一起使用，规则之间的相互联系，影响。 奖罚分配问题 透明度,第六章 机器学习,概述 实例学习 基于解释的学习 决策树学习 神经网络学习,第六章 机器学习,概述 实例学习 基于解释的学习 决策树学习 神经网络学习,基于解释的学习,Explanation-Based Learning(EBL)是20世纪80年代出现的一种机器学习方法，属于分析学习。 基于解释的学习，不考虑很多实例，采用演绎推理，少用归纳。可以克服归纳学习的不可靠问题。 利用单个问题的求解例子，依领域知识对实例进行详细

23、分析，构造求解过程的因果解释结构，并获取控制知识，然后对解释进行推广得到一般性描述，以便用于指导以后求解类似问题。从本质上是属于演绎学习。 参考书：高级人工智能史忠植，科学出版社,基于解释的学习(简介),历史 起源于经验学习，50年代末出现用符号来标记存储结构模型的方法（神经模型）。即存储块chunk的概念。如同围棋、象棋大师脑中的棋谱。 80年代初，Newell, Rosenbloom提出通过获取任务环境中关于模型问题的知识，可以改进系统的性能。开始将chunk作为对人类行为进行模拟的模型基础。获取的是控制知识，因此，可以明显提高系统求解速度，奠定了经验学习的基础。,基于解释的学习(简介),

24、历史 最终是1983年，美国Illinois大学的Dejong提出了基于解释的学习。在经验学习的基础上，运用一个或少数个例子，加上知识库，做出解释。 1986又进一步提出了明确的定义。产生了该名词。,基于解释的学习(简介),解释： 专家系统是给用户看的，所以，推理过程要说明。 搜索过程记录下来，以便对错误决策进行追踪，发现知识库和概念的错误。 对初学者进行训练。 方法： 预制文本法； 执行追踪法； 策略解释法。,基于解释的学习(简介),可操作性 机器学习得到的知识，应该有用且有尽量大的适应范围。因此要考虑可操作性和一般性。 希望学到的概念描述有利于提高系统运行效率。 可操作：如果一个概念描述能

25、有效的用于识别相应概念的例子。 给定：一个概念描述；一个执行系统；改善系统的各种要求，应明确各要求的类型和程度。 可操作满足： 可用性。执行系统可以使用该概念描述。 效用性。执行系统使用概念描述时，系统的运行得到要求的改善。,解释学习的空间描述,外延集合,内涵属性,基于解释的学习(简介),解释空间的描述 概念空间：某个学习程序能描述的所有概念的集合，其中每一点对应例子空间的唯一的一个子集合。例：C1对应I1，I2，I3。 但概念空间的一个点可以对应概念描述空间的多个点。例：C1对应不可操作的D1和可操作的D2。 对应同一概念的两个描述称为同义词。 解释学习的任务：把不可操作的描述转化为可操作的

26、描述。例：D1是搜索的开始结点，D2是解结点，解释是空间的变换，而可操作性是搜索结束的标准。 从D1到D2的过程称作概念可操作。,解释学习的框架,执行系统,学习系统,领域知识库,基于解释的学习(简介),解释学习的模型 执行系统：PS 学习系统：EXL 领域知识库：KB(不同描述间转换的集合) 系统工作过程 EXL输入概念C1的描述D1（一般是不可操作的） 根据KB中的知识，对其进行不同的转换（搜索） PS对每个转换结果进行测试，直至转换结果是PS可以接受的描述D2（可操作的）时，学习结束，输出D2,基于解释的学习(简介),一般框架： 给定：领域知识、目标概念、训练实例和操作性准则。 领域知识：

27、描述领域的事实和规则，背景知识，用来证明训练实例为什么可作为目标概念的实例。 训练实例：为了解释学习提供的一个例子，解释学习正是从该例出发，通过运用领域知识进行证明，最终推广出目标概念的描述。 操作性准则：用于指明哪些测试在运行时容易判定，指导系统对描述目标的概念进行取舍。 找出：满足操作性准则的关于概念的充分条件,基于解释的学习(简介),步骤： 产生解释，求解问题。从知识库中寻求 规则，然后进一步对规则进行分解推理。反复进行直到求解结束。 方法： (反向推理） 目标规则1， 子目标(规则1） 规则2，子目标(规则2） 规则3， 如得到解，则证明了该例的目标可满足。并获得了构成动作序列，作为解

28、释结构。 产生解释结构： 可以，所有算子构成动作序列，作为解释结构。 也可以，自顶向下的遍历证明树结构。 结构可与解释同时生成，也可在解释完毕后再生成。 对得到的解释结构以及事件进行概括。,基于解释的学习(方法1),解释和概括交替进行 1987年由斯坦福大学Haym和Hirsh提出。 描述：用逻辑的表示方法，语义清晰 例：见书 产生解释结构：从目标开始反向推理（从上到下）。 分解：根据条件，如light 计算：条件不满足时计算得到条件,如weight 生成控制规则（ 概括化的产生式规则）（从下到上） 所有叶结点的合取作为前件，（5项） 以定点的目标概念作为后件。 略去解释结构的中间部件。 应用

29、：把叶结点查一遍，不用中间结点。,解释学习例题,学习的目标：一个物体x可以安全的放置在另一个物体y的上面”。 目标概念：Safe-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) 领域知识（安全放置的准则、条件）：

30、 Fragile(y)Safe-to-stack(x, y)、Lighter(x, y)Safe-to-stack(x, y) 乘法计算、比较计算 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）继续寻找其前件，由比较计算公式可

31、知Lighter(obj1, obj2)的前件（条件）为Weight(p1,w1) Weight(p2,w2)Smaller(w1,w2)。得到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

32、(O2,table) smaller(w1,5) 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),基于解释的学习(方法2),基于解释的详细说明法(Explanation Based Specialization) 1987年CMU的Minton和Carbonell提出。开发了PRODIGY学习系统 克服了EBG(解

33、释和概括交替进行)的过分一般化的缺点。 解释过程对每个目标概念进行详细的描述，将有关目标概念的描述转换成一条相应的控制规则。 目标概念学习:成功(preference)、失败(rejection)、唯一的选择(selection)、目标互相制约(restricted) 分析问题求解轨迹，解释为何满足该概念 有解：成功；无解：失败；选择唯一：唯一； 依赖于别的目标：互相制约 所得结果就是相应种类(成功、无解、唯一、制约)的规则,基于解释的学习(方法2),具体方法（体系结构图） 解释过程：就是详细的说明过程。 以目标概念为根，生成一棵自顶向下的证明树。解释每一步，从领域库中选择与所给例子一致的规则

34、，生成一个结点。每条规则是对结点子目标的详细描述。 学习控制规则：四种目标概念，有四种固定的控制规则模式。将某个目标概念的详细描述与规则模式匹配，就获得相应的控制规则 例见书 知识表示：领域层公理（领域规则）；构筑层公理（推理规则）,基于解释的学习(方法2),没有明显的概括化过程。领域规则，特别是问题求解器的推理规则实际上已经进行了概括化处理。即不是最原始的领域知识构成，实际上具有一定的概括性。,基于解释的学习(方法3),由外部指导学习控制chunk方法 1987年斯坦福大学与密西根大学教授提出。 （SOAR系统） 学习机制：由外部专家的指导来学习一般的搜索控制知识。 体系结构图 外部指导 直

35、接的指令式：由专家指定一个算子求解。有解可行 间接的简单直观形式：原文体按语法分解成树结构的内部表示，并附上初始状态。然后再请求专家劝告（一个直观简单问题）。 学习机制 工作存储单元收集例子并构成chunk 建立子目标后，首先将当时的状态存入工作存储单元 得到解后，系统从工作存储单元中取出子目标的初始状态删去与解无关的部分，保留部分作为前件。 以专家指定的算子或求解简单问题所得出的结算子作为结论动作， 至此生成产生式规则。,基于解释的学习(可操作性),可操作性：可操作性是一个输入要求。 可操作性标准：“概念描述应该表示为描述训练例的那些谓词或其它领域理论中挑选出来的易于估值的谓词”； “如果一

36、个概念能有效的用于识别相应的概念的例子，则它是可操作的” PRODIGY SOAR系统 MRS-EBG系统 META-LEX系统 可操作性对于基于解释的学习系统是至关重要的。但是，目前检测可操作性的方法决定于能否简化系统的性能假设（这些假设很容易在学习过程中被破坏）。尽管在这方面国内外的研究人员一直在寻找有效的处理方法，但多数只是处于理论研究阶段，应用于实际系统中的尚未达到令人满意的程度。,第六章 机器学习,概述 实例学习 基于解释的学习 决策树学习 神经网络学习,第六章 机器学习,概述 实例学习 基于解释的学习 决策树学习 神经网络学习,决策树学习,决策树(Decision Tree) 一种

37、描述概念空间的有效的归纳推理办法。基于决策树的学习方法可以进行不相关的多概念学习，具有简单快捷的优势，已经在各个领域取得广泛应用。,决策树学习（概述）,决策树学习是以实例为基础的归纳学习。 从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。 概念分类学习算法：来源于 Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概念。 1979年, J.R. Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。 Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策树节点创

38、建缓冲区，使决策树可以递增式生成，得到ID4算法。,决策树学习（概述）,1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。 1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。 另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。 其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。,决策树学习（概述）,随着决策树学习算法的广泛应用，包括C4.5和CART的各种算法得到进一步改进。 当前比较引人注目的

39、有斜超平面分割的多变决策树(Multi-Variance Decision Tree， MDT)算法，将遗传算法、神经元网络和C4.5相结合的GA-NN-C4.5 算法， SVM决策树算法。 这些改进算法旨在结合各种方案的优势，取得更合理的分类效果，总结出更通用的规则。,决策树学习（概述）,决策树学习采用的是自顶向下的递归方法。 决策树的每一层节点依照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进行比较，根据不同的比较结果向相应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。 从根节点到叶节点的每一条路经都对应着一条合理的规则，规则间各个部分（各个层的

40、条件）的关系是合取关系。整个决策树就对应着一组析取的规则。 决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练例子进行较好的标注，就能够进行学习。如果在应用中发现不符合规则的实例，程序会询问用户该实例的正确分类，从而生成新的分枝和叶子，并添加到树中。,决策树学习（决策树）,树是由节点和分枝组成的层次数据结构。节点用于存贮信息或知识，分枝用于连接各个节点。树是图的一个特例，图是更一般的数学结构，如贝叶斯网络。 决策树是描述分类过程的一种数据结构，从上端的根节点开始，各种分类原则被引用进来，并依这些分类原则将根节点的数据集划分为子集，这一划分过程直

41、到某种约束条件满足而结束。,决策树学习（决策树）,决策树学习（决策树）,可以看到，一个决策树的内部结点包含学习的实例，每层分枝代表了实例的一个属性的可能取值，叶节点是最终划分成的类。如果判定是二元的，那么构造的将是一棵二叉树，在树中每回答一个问题就降到树的下一层，这类树一般称为CART（Classification And Regression Tree）。 判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索，并在每个节点生成“IFTHEN”规则来实现。如图6-14的决策树可以转换成下规则： IF “个子大” THEN IF “脖子短” THEN IF “鼻子长” THEN 可

42、能是大象 形式化表示成：,决策树学习（决策树）,构造一棵决策树要解决四个问题： 收集待分类的数据，这些数据的所有属性应该是完全标注的。 设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。 分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。,决策树学习（决策树）,设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此在必要的时候应该停止数据集分裂： 该节点包含的数据太少不足以分裂； 继续分裂数据集对树生成的目标(例如ID3中的熵下降准则)没有贡献； 树的深度过大不宜再分。 通用的决策树分裂目标是整棵树的熵总量最小，每一步分

43、裂时，选择使熵减小最大的准则，这种方案使最具有分类潜力的准则最先被提取出来。,决策树学习（性质）,证据由属性值对表示 证据由固定的的属性和其值表示，如属性（温度），值（热）最简单的学习情况时每个属性拥有少量的不相关的值。 目标函数有离散输出值 决策树分配一个二值的树，很容易扩展成为多于两个的输出值。 需要不相关的描述 决策树原则上是表述不相关的表示 容忍训练数据的错误 对训练样本和表述样本的属性值的错误都有较强的鲁棒性。 训练数据可以缺少值 可以采用缺少属性值的样本学习。（不是所有样本都有）,决策树学习（应用）,根据病情对病人分类 根据起因对故障分类 根据付款信用情况对贷款申请者分类 这些都是

44、将输入样本分类成可能的离散集 分类问题,决策树学习（学习）,Shannon信息熵 自信息量 设信源X发出ai的概率p(ai)，在收到符号ai之前，收信者对ai 的不确定性定义为ai的自信息量I(ai)。 I(ai) = -logp(ai)。 信息熵 自信息量只能反映符号的不确定性，而信息熵用来度量整个信源整体的不确定性，定义为： 其中，r为信源X发出的所有可能的符号类型。信息熵反应了信源每发出一个符号所提供的平均信息量。,决策树学习（学习）,条件熵 设信源为X，收信者收到信息Y，用条件熵H(X|Y)来描述收信者在收到Y后对X的不确定性估计。设X的符号ai，Y的符号bj，p(ai|bj)为当Y为

45、bj时，X为ai的概率，则有： 平均互信息量 用平均互信息量来表示信号Y所能提供的关于X的信息量的大小，用I(X, Y)表示：,决策树学习（学习）,设学习的实例集为： 其中Si为学习实例，T实例集大小。对于有指导的学习，任一个Si具有明确标定的类别， 向量表示该实例的特性，即： Si的信息为，如果一个观测值具有属性则应该划归为类，应该有下面的规则总结出来： 式中xi为事件所具有的第i个属性。这里的属性和类具有广泛的意义。,第六章 机器学习,概述 实例学习 基于解释的学习 决策树学习 神经网络学习,第六章 机器学习,概述 实例学习 基于解释的学习 决策树学习 神经网络学习,人工神经元网络,概述

46、基本原理 前馈型人工神经元网络 自组织竞争人工神经网络 神经网络的应用 与人工智能原理的结合 参考书：人工神经网络的模型及其应用 复旦大学出版社，张立明,概述,什么叫人工神经网络？ 采用物理可实现的系统来模仿人脑神经细胞的结构和功能的系统。 为什么要研究神经网络？ 用计算机代替人的脑力劳动。 计算机速度为纳秒级，人脑细胞反应时间是毫秒级。而计算机不如人。 长期以来人类的梦想，机器既能超越人的计算能力，又有类似于人的识别、分析、联想等能力。,概述,发展史 1890年，美国生物学家W.James出版了Physiology（生理学）一书。首次阐明了有关人脑结构及其功能，以及相关学习、联想、记忆的基本

47、规律。指出：人脑中当两个基本处理单元同时活动，或两个单元靠得比较近时，一个单元的兴奋会传到另一个单元。而且一个单元的活动程度与他周围的活动数目和活动密度成正比。,概述 发展史,1943年McCulloch（心理学家）和Pitts（数理逻辑学家）发表文章，提出M-P模型。描述了一个简单的人工神经元模型的活动是服从二值（兴奋和抑制）变化的。总结了神经元的基本生理特性，提出了神经元的数学描述和网络的结构方法。标志神经计算时代的开始。 输出表达式：,概述 发展史,MP模型的意义： M-P模型能完成一定的逻辑运算； 第一个采用集体并行计算结构来描述人工神经元和网络工作； 为进一步的研究提供了依据 。 （

48、可以完成布尔逻辑计算）,概述 发展史,1949年Donala U.Hebb（心理学家）论著The Organization of Behavior（行为自组织），提出突触联系强度可变的假设，认为学习的过程最终发生在神经元之间的突触部位，突触的联系强度随着突触前后神经元的活动而变化。 赫布规则 多用于自组织网络的学习。即：若两个神经元输出兴奋，则它们之间的连接权加强，反之减少。,概述 发展史,赫布规则意义（提出了变化的概念）： 提出了一个神经网络里信息是储藏在突触连接的权中的概念； 连接权的学习律是正比于两个被连接神经细胞的活动状态值的乘积； 假设权是对称的； 细胞的互相连接的结构是他们权的改变

49、创造出来的。,概述 发展史,1957年Frank Rosenblatt定义了一个神经网络结构，称为感知器(Perceptron) 。 第一次把神经网络研究从纯理论的探讨推向工程实现，从而掀起了神经网络研究高潮。 在IBM704计算机上进行了模拟，证明了该模型有能力通过调整权的学习达到正确分类的结果。,概述 发展史,1969M.Minsky和S. Papert发表了Perceptrons的论著，指出感知器仅能解决一阶谓词逻辑，只能做线性划分。对于非线性或其他分类会遇到很大困难。一个简单的XOR问题的例子就证明了这一点。神经网络研究一度达到低潮。原因还有：计算机不够发达、VLSI还没出现、而人工智

50、能和专家系统正处于发展高潮。,概述 发展史,七十年代，据说全球只有几十个人在研究，但还是成功的。如：日本Fukusima的Neocognitron；芬兰Kohonen的自组织神经网络；Stephen Crossberg的共振自适应理论ART网络等 。,概述 发展史,1982年John J. Hopfield（物理学家）提出了全联接网络，离散的神经网络模型。全新的具有完整理论基础的神经网络模型。基本思想是对于一个给定的神经网络，对于一个能量函数，这个能量函数是正比于每一个神经元的活动值和神经元之间的联接权。而活动值的改变算法是向能量函数减少的方向进行，一直达到一个极小值为止。证明了网络可达到稳定

51、的离散和连续两种情况。年后AT&T等做出了半导体芯片。神经网络复兴时期开始。,概述 发展史,1986年美国的一个平行计算研究小组提出了前项反馈神经网络的Back Propagation（BP）学习算法。成为当今应用最广泛的方法之一。该方法克服了感知器非线性不可分类问题，给神经网络研究带来了新的希望。,概述 发展史,1987年在美国召开了第一届世界神经网络大会1000人参加。 IJCNN等大会 Neural Computing, IEEE Neural Network 等期刊,概述,人工智能与神经网络 共同之处：研究怎样使用计算机来模仿人脑工作过程。学习实践再学习再实践 。 不同之处： 人工智能

52、研究人脑的推理、学习、思考、规划等思维活动，解决需人类专家才能处理的复杂问题。 神经网络企图阐明人脑结构及其功能，以及一些相关学习、联想记忆的基本规则（联想、概括、并行搜索、学习和灵活性）。,概述,例如： 人工智能专家系统是制造一个专家，几十年难以培养的专家。 神经网络是制造一个婴儿，一个幼儿，一个可以学习，不断完善，从一些自然知识中汲取智慧的生命成长过程。 同样是模仿人脑，但所考虑的角度不同。成年人和婴儿。学习过程不一样。一个是总结出常人都不懂得规律；一个是没完没了向他出示、重复一样东西，就象教一个小孩子说话。,概述,基本原理神经元模型,基本原理神经元模型,神经元 每一个细胞处于两种状态。突

53、触联接有强度。多输入单输出。实质上传播的是脉冲信号，信号的强弱与脉冲频率成正比。,基本原理神经元模型,转移函数 神经细胞的输出对输入的反映。典型的转移函数是非线性的。,基本原理网络结构,人脑神经网络 人脑中约有140亿个神经细胞，根据Stubbz的估计这些细胞被安排在约1000个主要模块内，每个模块上有上百个神经网络，每个网络约有10万个神经细胞。,基本原理 网络分类,分类 前馈型 反馈型 自组织竞争 随机网络 其它,基本原理网络模型,前馈网络：每层只与前层相联接,基本原理网络模型,输入输出有反馈的前馈网络：输出层上存在一个反馈回路，将信号反馈到输入层。而网络本身还是前馈型的。,基本原理网络模

54、型,前馈内层互联网络：外部看还是一个前向网络，内部有很多自组织网络在层内互联着。,基本原理网络模型,反馈型全互联网络：所有计算单元之间都有联接。如：Hopfield网络 反馈型局部联接网络：特例，每个神经元的输出只与其周围的神经元相连，形成反馈网络。,基本原理基本属性,基本属性 非线性 非线性关系是自然界的普遍特性。大脑的智慧就是一种非线性现象。人工神经元处于激活或抑制两种不同的状态。这种行为在数学上表现为一种非线性。 非局域性 一个神经网络通常由多个神经元广泛联接而成。一个系统的整体行为不仅取决于单个神经元的特征，而且可能主要由单元之间的相互作用、相互联接所决定。通过单元之间的大量联接模拟大

55、脑的非局域性。联想记忆是非局域性的典型例子。,基本原理基本属性,非定常性 人工神经网络具有自适应、自组织、自学习能力。神经网络不但处理的信息有各种各样，而且在处理信息的同时，非线性动力系统本身也在不断变化。经常采用迭代过程描写动力系统的演化过程。 非凸性 一个系统的演化方向，在一定条件下，将取决于某个特定的状态函数，如能量函数，它的极值相应于系统比较稳定的状态。非凸性是指这种函数有多个极值，故系统具有多个较稳定的平衡态，这将导致系统演化的多样性。,基本原理优缺点,评价 优点： 信息处理的并行性 知识的分布存储 对于系统本身及环境变化的容错性 学习能力 缺点： 不适合高精度计算；学习问题没有根本

56、解决，慢；目前没有完整的设计方法，经验参数太多。,前馈型神经网,概述 最初称之为感知器。是应用最广泛的一种人工神经网络模型，最主要原因是有BP学习方法。 前馈网络结构是分层的，信息只能从下一层单元传递到相应的上一层单元。上层单元与下层所有单元相联接。转移函数可以是线性阈值的。,前馈型神经网,单层感知器,前馈型神经网,基本原理，结构简单。很少在实际应用中出现。采用阶跃函数作为传递函数。从维空间可以很显然的看出其分类功能，但Minsky等揭示的致命弱点也一目了然。关键是学习算法及网络设计方法。 输出yi等于：,(1),其中：,前馈型神经网单层感知器,分类方法： 如果输入x有k个样本，xp, p=1

57、, 2, , k, xRn 当将这些样本分别输入到单输出的感知器中，在一定的和下，输出有两种可能+1或-1。 把样本xp看作为在n维状态空间中的一个矢量，那么k个样本为输入空间的k个矢量。而方程（1）就是把这个n为空间分为SA、SB两个子空间，其分界线为n-1维的超平面。即用一个单输出的感知器通过调整参数及来达到k个样本的正确划分。 如：.,前馈型神经网单层感知器,.,则存在一组权值wij使得公式(1)满足:,则称样本集为线性可分的，否则为线性不可分的。,前馈型神经网单层感知器,例子：2维空间,希望找到一根直线，把A, B两类样本分开，其分界线为:,解有无数个。,单层感知器只能解决线性可分类的

58、样本的分类问题。如样本不能用一个超平面分开，就会产生当年Minsky等提出的不可分问题。,二维输入感知器及其在状态空间中的划分,前馈型神经网,多层感知器 多层感知器的输入输出关系与单层感知器完全相同。前一层的输出是下一层的输入。也被称为BP网络。,前馈型神经网,多层感知器 采用BP算法学习时要求传递函数为有界连续可微函数如sigmoid函数。因此，网络可以用一个连续的超曲面（而不仅仅是一个超平面）来完成划分输入样本空间的功能。 先求误差，用梯度下降的方法求误差的传递。从后往前算。,即f(x)=1/(1+e-x)。神经元的非线性作用函数。,前馈型神经网,多层感知器 n层网络可以以n-1个超曲面构

59、成一个复合曲面，弥补了单层感知器的缺陷。基于BP算法，依据大量样本通过逐步调整神经元之间的联接权重来构造网络。理论上，多层前馈网络在不考虑结果规模的前提下，可以模拟任意的输出函数。,前馈型神经网,特点 用非线性连续可微的函数来分类，结果是一种模糊概念。当输出f(u)0时，其输出不一定为，而是一个0.5(有时只是0)的值，表示所得到的概率为多少。 应用 各行各业。是应用最广泛的神经网络模型之一。,自组织竞争人工神经网络,概述 在实际的神经网络中，存在一种侧抑制的现象。即一个细胞兴奋后，通过它的分支会对周围其他神经细胞产生抑制。这种侧抑制在脊髓和海马中存在，在人眼的视网膜中也存在。,自组织竞争人工神经网络,概述 这种抑制使神经细胞之间出现竞