第7讲 机器学习-1

人工智能中国农业大学信息与电气工程学院第7讲机器学习

机器学习一、概述二、机器学习系统的基本模型三、机械学习四、实例学习五、解释学习六、决策树学习七、神经网络学习一、概述到目前为止的大多数人工智能系统还完全没有或仅有有限的学习能力。系统中的知识是由人工编程送入的，知识中的错误也不能自动改正。一、概述否定意见：机器是人造的，其性能和动作是由设计者规定的，因此无论如何其能力也不会超过设计者本人。对于不具备学习能力的机器来说是正确的，可是对于具备学习能力的机器就值得考虑了。机器学习的不可预测问题。机器的能力是否能超过人的能力？一、概述20世纪50年代末，阿瑟.塞缪尔（samuel）编写了著名的跳棋程序。启发式搜索技术，跳棋程序可以向前看几步然后再走棋。可以从经验中学习，从棋谱中学习。不断调整棋盘评价函数，提高自己的棋艺。经过三年的学习，打败了Samuel，又三年，打败了州冠军。同时刺激了“搜索”和“机器学习”这两个人工智能的重要领域的发展。跳棋程序一、概述一、概述--塞缪尔的人生1901年生于美国堪萨斯州的恩波利亚，恩波利亚学院上学1923年大学毕业以后，他进入MIT念研究生，1926年取得硕士学位。留校工作两年以后，他加盟贝尔实验室，从事电子器件的研究。二次世界大战爆发以后，他的研究工作集中于雷达技术。战争结束后，到伊利诺大学电气工程系任教，积极参与了该校研制电子计算机的工作。1949年即转至IBM公司在普凯泼茜的研发实验室工作，参与其第一台大型科学计算机701的开发。一、概述--塞缪尔的人生塞缪尔在下棋程序方面的工作对IBM公司早期计算机的指令系统产生了很大影响。由于下棋程序是计算机应用中最早的一种典型的非数值计算，因此在701中加入了许多逻辑指令，这类指令后来迅速被所有计算机的设计者所采用和推广，成为计算机指令集中的基本成分。1966年塞缪尔从IBM公司退休以后，到斯坦福大学从事教学和研究工作，指导博士生，直到1982年。塞缪尔晚年得了帕金森综合症。病中他开始撰写自传，但只写到20世纪60年代中期，即于1990年7月29日在加利福尼亚州的家中撒手西去。塞缪尔生前除了获得IZEE的计算机先驱奖以外，没有别的荣誉和奖励。一、概述Simon认为“学习就是系统中的变化，这种变化使系统比以前更有效地去做同样的工作”。Minsky认为“学习是在我们的头脑中进行有用的变化”。有的观点认为“机器学习就是知识的获取”，但获取的知识有时不会使系统有所改善。什么是机器学习？一、概述知识获取学习的本质就是获取新的知识，包括物理系统、行为的描述和模型的建立，构造客观现实的表示。技能求精通过实践改造机制和认知技能。这些技能包括意识的或机制的。这种改变是通过反复实践和从失败中纠正错误来进行的。学习骑自行车。学习的基本形式一、概述人工智能主要是为了研究人的智能，模仿其机理将其应用于工程的科学，在这个过程中，必然会问到“人类怎么做才能获得这种特殊技能（或知识）？”当前的人工智能研究的主要障碍和发展方向之一就是机器学习。包括学习的计算理论和构造学习系统。为什么要研究机器学习？未来的计算机将有自动获取知识的能力，直接从书本中学习，通过与人谈话学习，通过观察学习。通过实践自我完善。克服人的存储少，效率低，注意力分散，难以传送所获取知识等局限性。一台计算机获取的知识很容易复制给任何其他机器。一、概述为什么要研究机器学习？机器学习实现的困难预测难：学习后知识库发生了什么变化，系统功能的变化的预测。归纳推理：现有的归纳推理保假，不保真。演绎推理保真。而且，归纳的结论是无限多的，其中相当多的是假的，给生成知识带来不可靠性。机器目前很难观察什么重要，什么有意义。一、概述一、概述---机器学习的发展史

第一阶段是在50年代中叶到60年代中叶，属于热烈时期。在这个时期，所研究的是“没有知识”的学习，即“无知”学习；其研究目标是各类自组织系统和自适应系统；指导本阶段研究的理论基础是早在40年代就开始研究的神经网络模型。在这个时期，我国研制了数字识别学习机。一、概述---机器学习的发展史

第二阶段在60年代中叶至70年代中叶，被称为机器学习的冷静时期。

本阶段的研究目标是模拟人类的概念学习过程，并采用逻辑结构或图结构作为机器内部描述。这个时期正是我国“史无前例”的十年，对机器学习的研究不可能取得实质进展。一、概述---机器学习的发展史

第三阶段从70年代中叶至80年代中叶，称为复兴时期。

在这个时期，人们从学习单个概念扩展到学习多个概念，探索不同的学习策略和各种学习方法。本阶段已开始把学习系统与各种应用结合起来，中国科学院自动化研究所进行质谱分析和模式文法推断研究，表明我国的机器学习研究得到恢复。1980年西蒙来华传播机器学习的火种后，我国的机器学习研究出现了新局面。一、概述---机器学习的发展史机器学习的最新阶段始于1986年。一方面，由于神经网络研究的重新兴起，另一方面，对实验研究和应用研究得到前所未有的重视。我国的机器学习研究开始进入稳步发展和逐渐繁荣的新时期。一、概述---机器学习的主要策略学习过程与推理过程是紧密相连的，按照学习中使用推理的多少，机器学习所采用的策略大体上可分为：机械学习、传授学习、演绎学习、类比学习和归纳学习。学习中所用的推理越多，系统的能力越强。机械学习机械学习又称为记忆学习，是最简单的学习策略。这种学习策略不需要任何推理过程。外面输入知识的表示方式与系统内部表示方式完全一致，不需要任何处理和变化。一、概述---机器学习的主要策略传授学习传授学习又称指导式学习或指点学习。在使用传授学习系统时，外界输入知识的表达方式与系统内部表达方式不完全一致，系统在接受外部知识时，需要一点推理、翻译和转化工作。一、概述---机器学习的主要策略演绎学习在演绎学习中，学习系统由给定的知识进行演绎的保真推理，并存储有用的结论。一、概述---机器学习的主要策略归纳学习归纳学习是应用归纳推理进行学习的一类学习方法。按其又无教师的指导，可以分为实例学习及观察与发现学习。一、概述---机器学习的主要策略实例学习实例学习又称为概念获取，它是通过向学习者提供某一概念的一组正例和反例，使学习者从这些正反例中归纳推理出概念的一般描述，这个描述应能解释所有给定的正例并排除所有给定的反例这些正反例是由信息源提供的，信息源可能是已经知道概念的教师，也可以是学习者本身，还可能是学习者以外的外部环境。一、概述---机器学习的主要策略类比学习类比学习就是在遇到新的问题时，可以学习以前解决过的类似问题的解决方法，来解决当前的问题。所以寻找与当前问题相似的已知问题就很重要，并且必须要能够发现当前任务与已知任务的相似之点，由此制定出完成当前任务的方案。类比学习可以由系统已有的某一领域知识得到另一领域中类似的知识。一、概述---机器学习的主要策略观察与发现学习观察与发现学习又称为描述的一般化。这类学习没有教师的指导，它要产生对所有或大多数观察到的规律和规则的解释。这类学习包括概念聚类、构造分类、曲线拟合（使方程符合数据）、发现并解释观察到的定律并形成理论。一、概述---机器学习的主要策略二、机器学习系统的基本模型以西蒙关于学习的定义作为出发点，建立机器学习系统的基本模型。环境学习环节知识库执行环节二、机器学习系统的基本模型环境和知识库是以某种知识表示形式表达的信息的集合，分别代表外界信息来源和系统所具有的知识；“学习环节”和“执行环节”代表两个过程。“环境”向系统的“学习环节”提供某些信息，而“学习环节”则利用这些信息对系统的“知识库”进行改进，以增进系统“执行环节”完成任务的效能，“执行环节”根据知识库中的知识来完成某种任务，同时把获得的信息反馈给“学习环节”。二、机器学习系统的基本模型环境可以是系统的工作对象，也可以包括工作对象和外界条件。例如在医疗系统中，环境就是病人当前的症状、检验的数据和病历。在模式识别中，环境就是待识别的图形或景物。环境就是为学习系统提供获取知识所需的信息。信息的水平和质量，对学习系统获取知识的能力有很大的影响。二、机器学习系统的基本模型学习环节通过获得外部信息，并将这些信息与执行环节所反馈回的信息进行比较。一般情况下环境提供的信息水平与执行环节所需的信息水平之间往往有差距，经分析、综合、类比、归纳等思维过程，学习环节就要从这些差距中获取相关对象的知识，并将这些知识存入知识库中。二、机器学习系统的基本模型知识库用于存放由学习环节所学到的知识。影响学习系统设计的第二个因素是知识库的形式和内容。知识库的形式就是知识表示的形式。选择知识表示方法要考虑下列准则：可表达性、推理难度、可修改性和可扩充性。二、机器学习系统的基本模型执行环节是整个机器学习系统的核心。执行环节用于处理系统面临的现实问题，即应用知识库中所学到的知识求解问题，如智能控制、自然语言理解和定理证明等，并对执行的效果进行评价，将评价的结果反馈回学习环节，以便系统进一步的学习。执行环节的问题复杂性、反馈信息和执行过程的透明度都对学习环节有影响。二、机器学习系统的基本模型执行部分是整个学习系统的核心，因为执行部分的动作就是学习部分力求改进的动作。同执行部分有关的问题有3个：复杂性、反馈和透明性。复杂的任务比简单的任务需要更多的知识，对于这类简单任务，有一条分组规则就可以了。有的要使用几百条规则。对于通过例子学习的计算机系统，最简单的执行任务是按照单一的概念或规则进行分类或预测。比较复杂一点的任务涉及多个概念。学习系统最复杂的任务是小型计划任务，系统必须给出一组规则序列，执行部分依次执行这些规则。三、机械学习机械学习是最简单的机器学习方法。机械学习就是记忆，即把新的知识存储起来，供需要时检索调用，而不需要计算和推理。机械学习又是最基本的学习过程。任何学习系统都必须记住它们获取的知识。在机械学习系统中，知识的获取是以较为稳定和直接的方式进行的，不需要系统进行过多的加工。三、机械学习当机械学习系统的执行部分解决好问题之后，系统就记住该问题及其解。我们可把学习系统的执行部分抽象地看成某个函数，该函数在得到自变量输入值(X1,X2,…,Xn)之后，计算并输出函数值(Y1,Y2,…,Yp)。机械学习在存储器中简单地记忆存储对((X1,X2,…,Xn),(Y1,Y2,…,Yp))。当需要f(X1,X2,…,Xn)时,执行部分就从存储器中把(Y1,Y2,…,Yp)简单地检索出来而不是重新计算它。三、机械学习---主要问题（1）存储组织信息：采用适当的存储方式，使检索速度，尽可能地快，是机械学习中的重要问题。（提高检索速度）（2）环境的稳定性与存储信息的适用性问题：机械学习系统必须保证所保存的信息适应于外界环境变化的需要，这也就是所谓的信息适用性问题。（3）存储与计算之间的权衡：对于机械学习来说很重要的一点是它不能降低系统的效率四、实例学习实例学习又称为示例学习或通过事例学习。它是通过例子，经归纳得出一般性概念的一种方法。在这种学习方法中，外部环境提供给系统一些特殊的实例，这些实例事先又被施教者划分为正例和反例。实例学习系统由此进行归纳推理，得到一般的规则或一般性的知识，这些一般性知识应能解释所有给定的正例，并排除所有给定的反例。四、实例学习---两个空间模型实例学习中有两个重要的概念：例子空间和规则空间。例子空间就是向系统提供的训练例子集合，如教系统识别狗时提供的狗、其它动物和物品。规则空间是事物所具有的某种规律，例如“狗有四条腿”、“狗有两只眼睛”、“狗有一条尾巴”等四、实例学习---两个空间模型例子空间要考虑的问题例子空间的组织和搜索方法：选择适当的例子以便证实或否决规则空间中某些假设规则集。为了提高搜索效率，需要设计合适的搜索算法，并把它与例子空间的组织结构进行统筹考虑。四、实例学习规则空间要考虑的问题所谓规则空间用规定的描述语言可以表示的所有规则的集合即为规则空间。与规则空间有关的两个问题是对规则空间的要求和规则空间的搜索方法。规则的表示与实例的表示一致。规则的表示形式应适应归纳推理。规则空间中应包括所有可能产生的规则。四、实例学习常用的几种归纳推理方法常量化成变量去掉条件增加选择曲线拟合四、实例学习常量化成变量示例1：花色(C1,梅花)∧花色(C2,梅花)∧花色(C3,梅花)∧花色(C4,梅花)∧花色(C5,梅花)→同花(C1,C2,C3,C4,C5)示例2：花色(C1,红桃)∧花色(C2,红桃)∧花色(C3,红桃)∧花色(C4,红桃)∧花色(C5,红桃)→同花(C1,C2,C3,C4,C5)其中示例1表示5张梅花牌是同花，示例2表示5张红桃牌是同花。把常量“梅花”和“红桃”换成变量x，就归纳出一条假设规则。规则1：花色(C1,x)∧花色(C2,x)∧花色(C3,x)∧花色(C4,x)∧花色(C5,x)→同花(C1,C2,C3,C4,C5)去掉条件去掉条件就是把示例中的某些无关的子条件去掉。如：示例3：花色(C1,红桃)∧点数(C1,3)∧花色(C2,红桃)∧点数(C2,5)∧花色(C3,红桃)∧点数(C3,7)∧花色(C4,红桃)∧点数(C4,10)∧花色(C5,红桃)∧点数(C5,K)→同花(C1,C2,C3,C4,C5)为了得到上述规则1，不但要把常量“红桃”化为变量x，而且要去掉所有的“点数”谓词。增加选择例如要程序来学习“人面牌”的概念，“人面牌”是指点数为J、Q、K的牌。提供的两个真例是：示例4：点数（C1，J）→人面牌（C1）示例5：点数（C1，K）→人面牌（C1）将两个示例的前件进行析取合并后等价地得到点数（C1，J）∨点数（C1，K）→人面牌（C1）如果在析取条件中增加一种选择，就得到要求的规则规则2：点数（C1，J）∨点数（C1，Q）∨点数（C1，K）→人面牌（C1）增加选择就是在析取条件中增加一个新的析取项。“常量化成变量”是一种由具体到一般的演变或归纳；“去掉条件”就是去掉合取项，也就是去掉部分约束；“增加选择”就是增加析取项，也就是扩大范围。后两种方法都是直接扩大范围，但方法①更强，归纳过快，因此更容易出错，方法③较弱，不易出错，但归纳较慢。例如对示例4和示例5使用方法①就会得到下列错误：点数（C1，x）→人（C1）.....(错误)归纳推理这个结果说明归纳过程很容易出错，归纳推理不是保真的，是保假的（前提为真则结论不一定为真，前提为假则结论一定为假）。归纳过程就是从多种归纳方法中选择正确的方法，以得到正确的结果。因此归纳过程就是搜索过程，在归纳的过程中，出现错误后要进行回溯。发现错误的方法，一般是选用新的例子去否定归纳出的错误规则，在实例学习的两个空间模型中也正是这样表示的。五、解释学习解释学习是20世纪80年代出现的一种机器学习方法。属于分析学习。从本质上讲属于演绎学习。由美国Illinois大学Dejong提出。解释学习是在经验学习的基础上提出的。解释学习与实例学习不同，解释学习分析一个或少数几个例子，加上给定的领域知识，进行保真的的演绎推理，存储有用的结论，经过知识的求精和编辑，产生适合以后求解类似问题的控制知识。五、解释学习解释学习的步骤：1.通过分析一个求解实例来产生解释结构。2.对该结构进行泛化，获取一般的控制规则。五、解释学习解释学习的可操作性如果给定：1.一个概念描述；2.一个执行系统，它利用概念描述改善执行情况；3.改善执行系统的各种要求，应明确各要求的类型和程度。如果，满足下面两个条件：1.可用性（执行系统可利用该概念描述）。2.有用性（执行系统利用该概念描述时，系统的运行得到要求的改善）。则：该概念描述是可操作的。五、解释学习解释学习的空间模型例子空间：例子的集合概念空间：某个学习程序能描述的所有概念的集合。概念描述空间：对概念描述的集合。解释学习的方法1987年斯坦福大学Haym和Hirsh提出的解释和概括交替并行的EBG方法。六、决策树学习决策树学习是应用最广的归纳推理算法之一其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。决策树学习是以实例为基础的归纳学习。从一类无序、无规则的事物（概念）中推理出决策树表示的分类规则。六、决策树学习六、决策树学习概念分类学习算法：来源于Hunt,Marin和Stone于1966年研制的CLS学习系统，用于学习单个概念。1979年,J.R.Quinlan给出ID3算法，并在1983年和1986年对ID3进行了总结和简化，使其成为决策树学习算法的典型。Schlimmer和Fisher于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。1988年，Utgoff在ID4基础上提出了ID5学习算法，进一步提高了效率。1993年，Quinlan进一步发展了ID3算法，改进成C4.5算法。另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。六、决策树学习大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间当前比较引人注目的有斜超平面分割的多变决策树(Multi-VarianceDecisionTree，MDT)算法，将遗传算法、神经元网络和C4.5相结合的GA-NN-C4.5算法，SVM决策树算法。六、决策树学习决策树学习采用的是自顶向下的递归方法。决策树的每一层节点依照某一属性值向下分为子节点，待分类的实例在每一节点处与该节点相关的属性值进行比较，根据不同的比较结果向相应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。从根节点到叶节点的每一条路经都对应着一条合理的规则，规则间各个部分（各个层的条件）的关系是合取关系。整个决策树就对应着一组析取的规则。六、决策树学习树是由节点和分枝组成的层次数据结构。节点用于存贮信息或知识，分枝用于连接各个节点。树是图的一个特例，图是更一般的数学结构，如贝叶斯网络。决策树是描述分类过程的一种数据结构，从上端的根节点开始，各种分类原则被引用进来，并依这些分类原则将根节点的数据集划分为子集，这一划分过程直到某种约束条件满足而结束。

根结点个子大可能是松鼠可能是老鼠可能是大象在水里会吱吱叫鼻子长脖子长个子小不会吱吱叫鼻子短脖子短可能是长颈鹿在陆地上可能是犀牛可能是河马六、决策树学习判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索，并在每个节点生成“IF…THEN”规则来实现。如上图的决策树可以转换成下规则：

IF“个子大”THENIF“脖子短”THENIF“鼻子长”THEN可能是大象形式化表示成六、决策树学习决策树学习的应用根据病情对病人分类根据起因对故障分类根据付款信用情况对贷款申请者分类七、神经网络学习什么叫人工神经网络采用物理可实现的系统来模仿人脑神经细胞的结构和功能的系统。为什么要研究神经网络用计算机代替人的脑力劳动。计算机速度为纳秒级，人脑细胞反应时间是毫秒级。而计算机不如人。长期以来人类的梦想，机器既能超越人的计算能力，又有类似于人的识别、分析、联想等能力。七、神经网络学习—发展史发展史1890年，美国生物学家W.James出版了《Physiology》（生理学）一书。首次阐明了有关人脑结构及其功能，以及相关学习、联想、记忆的基本规律。指出：人脑中当两个基本处理单元同时活动，或两个单元靠得比较近时，一个单元的兴奋会传到另一个单元。而且一个单元的活动程度与他周围的活动数目和活动密度成正比。1943年McCulloch（心理学家）和Pitts（数理逻辑学家）发表文章，提出M-P模型。描述了一个简单的人工神经元模型的活动是服从二值（兴奋和抑制）变化的。总结了神经元的基本生理特性，提出了神经元的数学描述和网络的结构方法。——标志神经计算时代的开始输出表达式七、神经网络学习—发展史1949年DonalaU.Hebb（心理学家）论著《TheOrganizationofBehavior（行为自组织）》，提出突触联系强度可变的假设，认为学习的过程最终发生在神经元之间的突触部位，突触的联系强度随着突触前后神经元的活动而变化。1957年FrankRosenblatt定义了一个神经网络结构，称为感知器(Perceptron)。

规则学习

意义：第一次把神经网络研究从纯理论的探讨推向工程实现，在IBM704计算机上进行了模拟，证明了该模型有能力通过调整权的学习达到正确分类的结果。掀起了神经网络研究高潮。1969M.Minsky和S.Papert发表了《Perceptrons》的论著，指出感知器仅能解决一阶谓词逻辑，只能做线性划分。对于非线性或其他分类会遇到很大困难。一个简单的XOR问题的例子就证明了这一点。——神经网络研究一度达到低潮。原因还有：计算机不够发达、VLSI还没出现、而人工智能和专家系统正处于发展高潮。七、神经网络学习—发展史七十年代：日本Fukusima的Neocognitron；芬兰Kohonen的自组织神经网络；StephenCrossberg的共振自适应理论ART网络等。1982年JohnJ.Hopfield（物