2023年7月28日发(作者：)

⼈⼯智能复习参考0511⼈⼯智能、学派、知识、谓词⼈⼯智能，是对⼈的意识活动、思维过程的模拟，它是⼀门研究、开发⽤于模拟、延伸和扩展⼈的智能的理论及应⽤系统的技术科学。该领域的研究包括机器⼈、语⾔识别、图像识别、⾃然语⾔处理和专家系统等，除了计算机科学以外，⼈⼯智能还涉及信息论、控制论、⾃动化、仿⽣学、⽣物学、⼼理学、数理逻辑、语⾔学、医学和哲学等多门学科。⼈⼯智能的基本技术：（1）知识表⽰技术（2）知识推理、计算和搜索技术（3）系统实现技术。AI的基本内容（1）从⼈⼯智能的定义出发，基本内容可包括：感知与交流的模拟，记忆、联想、计算、思维的模拟，输出效应或⾏为模拟等。（2）从知识⼯程的⾓度出发，⼈⼯智能的基本内容是:知识的获取、知识的处理以及知识的运⽤。AI的研究⽬标：近期⽬标：实现机器智能。即先部分地或某种程度地实现机器智能，从⽽使现有的计算机更灵活好⽤和更聪明有⽤。////终极⽬标：⼈⼯智能的终极⽬标是要实现通⽤⼈⼯智能。⼈类智能+计算智能+数据智能=通⽤⼈⼯智能AI的学派：符号学派：使⽤基于规则的符号系统做推理，Lisp 和Prolog 的⽅法。连接学派：认为智能起源于⾼度互联的简单机制，神经⽹络，深度学习。进化学派：应⽤进化的过程，例如交叉和突变以达到⼀种智能⾏为，遗传算法。贝叶斯学派：使⽤概率规则及其依赖关系进⾏推理。概率图模型（PGM）是这⼀派通⽤的⽅法，主要的计算机制是⽤于抽样分布的蒙特卡罗⽅法。这种⽅法与符号学⽅法的相似之处在于，可以以某种⽅式得到对结果的解释。优点是存在可以在结果中表⽰的不确定性的量度。核保守派：利⽤核⽅法，使⾮线性分离问题变成线性问题，SVM。现代的划分⽅法：1.符号智能流派2.计算智能流派3.群体智能流派AI的诞⽣和发展：1956年达特茅斯会议：⼈⼯智能学诞⽣。1956-1974年⼀发。1974-1980年⼀低。1980-1987年⼆发。1987-1993年⼆低。1993-2010年复苏。2010⾄今⾼速增长。⼈⼯智能新⼀轮的增长源于⼤数据、云计算和算法（深度学习）三个核⼼要素。2-1. 什么是知识？知识的要素有哪些？知识的表⽰⽅法有哪些？知识要素：事实（有关问题环境的⼀些事物的知识，常以“…是…”的形式出现）。规则（有关问题中与事物的⾏动、动作相联系的因果关系知识，是动态的，常以“如果…那么…”形式出现）。控制（有关问题的求解步骤、技巧性知识，告诉怎么做⼀件事）。元知识（有关知识的知识，是知识库中的⾼层知识。包括怎样使⽤规则，解释规则、校验规则、解释程序结构等知识）。知识表⽰⽅法：⼀阶逻辑表⽰法，产⽣式知识表⽰法，框架表⽰法，语义⽹络表⽰法，⾯向对象表⽰法⼀阶谓词逻辑表⽰法：⼀种重要的知识表⽰⽅法，它以数理逻辑为基础，是到⽬前为⽌能够表达⼈类思维和推理的⼀种最精确的形式语⾔。它的表现⽅式和⼈类⾃然语⾔⾮常接近，它能够被计算机作精确推理。谓词公式既可表⽰事物的状态、属性和概念等事实性的知识，也可表⽰事物间具有因果关系的规则性知识。联结词：：“⾮”或者“否定”。表⽰对其后⾯的命题的否定∧：“合取”。表⽰所连结的两个命题之间具有“与”的关系。∨：“析取”。表⽰所连结的两个命题之间具有“或”的关系→ ：“条件”或“蕴含”。表⽰“若…则…”的语义。读作“如果P，则Q”其中，P称为条件的前件，Q称为条件的后件。 ：称为“双条件”。它表⽰“当且仅当”的语义。即读作“P当且仅当Q”。例如，对命题P和Q，P?Q表⽰“P当且仅当Q”，量词：倒A：全称量词，意思是“所有的”、“任⼀个”反E：存在量词，意思是“⾄少有⼀个”、“存在有”例题：定义谓词：T (x)：表⽰x 是教师。S (y)：表⽰y是学⽣。TS(x, y)：表⽰x是y的⽼师。表⽰知识：(倒Ax)( 反E y)(T (x)→ TS(x, y) ∧S (y))可读作：对所有x，如果x是⼀个教师，那么⼀定存在⼀个个体y，y的⽼师是x，且y是⼀个学⽣。表⽰知识“所有的整数不是偶数就是奇数”。定义谓词：I(x)：x是整数，E(x)：x是偶数，O(x)：x是奇数表⽰知识：(倒A x)(I(x) → E(x)∨O(x))谓词逻辑表⽰的优缺点：优点（⾃然、明确、精确、灵活、模块化）缺点（知识表⽰能⼒差：只能表⽰确定性知识，⽽不能表⽰⾮确定性知识、过程性知识和启发式知识。知识库管理困难：缺乏知识的组织原则。存在组合爆炸：由于难产⽣式、框架法、语意⽹络、推理什么是产⽣式知识表⽰法？产⽣式系统由哪些部分组成？说明各部分的功能。⼜称为产⽣式规则表⽰法，它和图灵机有相同的计算能⼒。产⽣式表⽰法已成为⼈⼯智能中应⽤最多的⼀种知识表⽰⽅法。产⽣式系统由三部分组成，数据库（⽤来存放输⼊事实、外部数据库输⼊的事实以及中间结果和最后结果）、规则库（⽤于描述某领域内知识的产⽣式集合，是某领域知识（规则）的存储器）和推理机（由⼀组程序组成，⽤来控制协调规则库与数据库的运⾏，包含了推理⽅式和控制策略）。事实的表⽰：确定性知识，可⽤如下三元组表⽰：（对象，属性，值）或（关系，对象1，对象2）。⾮确定性知识，可⽤如下四元组表⽰：（对象，属性，值，可信度因⼦）。产⽣式的基本形式：P→Q或者IF P THEN Q。与蕴涵式的主要区别：(1) 蕴涵式表⽰的知识只能是精确的，产⽣式表⽰的知识可以是不确定的。原因是蕴涵式是⼀个逻辑表达式，其逻辑值只有真和假。(2) 蕴含式的匹配⼀定要求是精确的，⽽产⽣式的匹配可以是不确定的。原因是产⽣式的前提条件和结论都可以是不确定的，因此其匹配也可以是不确定的。与条件语句的主要区别：(1) 前件结构不同，产⽣式的前件可以是⼀个复杂的的结构，传统程序设计语⾔中的左部仅仅是⼀个布尔表达式。(2) 控制流程不同，产⽣式系统中满⾜前提条件的规则被激活后，不⼀定被⽴即执⾏，能否执⾏将取决于冲突消解策略，传统程序设计语⾔中是严格地从⼀个条件语句向其下⼀个条件语句传递。产⽣式推理⽅式：正向推理：从⼀组表⽰事实的谓词或命题出发，使⽤⼀组产⽣式规则，⽤以证明该谓词公式或命题是否成⽴。逆向推理：从表⽰⽬标的谓词或命题出发，使⽤⼀组产⽣式规则证明事实谓词或命题成⽴，即⾸先提出⼀批假设⽬标，然后逐⼀验证这些假设。双向推理：双向推理的推理策略是同时从⽬标向事实推理和从事实向⽬标推理，并在推理过程中的某个步骤，实现事实与⽬标的匹配。2-6. 如何⽤框架表⽰法表⽰知识？如何⽤语义⽹络法表⽰知识？框架表⽰法是以框架理论为基础发展起来的⼀种结构化的知识表⽰，它适⽤于表达多种类型的知识。框架理论的基本观点是：⼈脑已存储有⼤量的典型情景，当⾯临新的情景时，就从记忆中选择⼀个称作框架的基本知识结构，其具体内容依新的情景⽽改变，形成对新情景的认识⼜记忆于⼈脑中。语义⽹络表⽰知识：⼀般由⼀些最基本的语义单元组成。这些最基本的语义单元被称为语义基元，可⽤如下三元组来表⽰为（节点1，弧，节点2）AKO:表⽰⼀个事物是另⼀个事物的⼀种类型。AMO:表⽰是另⼀个事物的成员。ISA:表⽰是另⼀个事物的实例。⽤语义⽹络系统主要有两⼤部分组成，⼀部分是由语义⽹络构成的知识库，另⼀部分是⽤于问题求解的推理机。语义⽹络的推理过程主要有两种：继承推理和匹配推理。继承是指把对事物的描述从抽象结点传递到具体结点。通过继承可以得到所需结点的⼀些属性值，它通常是沿着ISA、AKO、AMO等继承弧进⾏的。所谓匹配就是在知识库的语义⽹络中寻找与待求问题相符的语义⽹络模式。⽤语义⽹络表⽰知识的步骤1 确定问题总所有对象和各对象的属性。2 确定所讨论对象间的关系。3 根据语义⽹络中所涉及的关系，对语义⽹络中的节点及弧进⾏整理，包括增加节点、弧和归并节点等。4 将各对象作为语义⽹络的⼀个节点，⽽各对象间的关系作为⽹络中各节点的弧，连接形成语义⽹络。语意⽹络的特点：结构性、联想性、⾮严格性、⾃然性、⾃索引性。第3部分知识推理推理是按某种策略由已知事实出发推出结论的过程。推理所⽤的事实：初始证据：推理前⽤户提供的。中间结论：推理过程中所得到的。推理过程：由推理机来完成。分类：演绎推理：从已知的⼀般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是⼀种由⼀般到个别的推理⽅法，其核⼼是三段论，如假⾔推理、拒取式和假⾔三段论。归结推理：⼀种由个别到⼀般的推理⽅法。按照所选事例的⼴泛性可分为完全归纳推理和不完全归纳推理按照推理所使⽤的⽅法可分为枚举、类⽐、统计和差异归纳推理等。类⽐归纳推理：是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的⼀种归纳推理。演绎推理与归纳推理的区别演绎是在已知领域内的⼀般性知识的前提下，通过演绎求解⼀个具体问题或者证明⼀个结论的正确性。它所得出的结论实际上早已蕴含在⼀般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不能增殖新知识。归纳所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出⼀般性知识的过程，是增殖新知识的过程。推理过程不仅依赖于所⽤的推理⽅法，同时也依赖于推理的控制策略：是指如何使⽤领域知识使推理过程尽快达到⽬标谓词表⽰、⾃然演绎推理、归结演绎推理、Skolem谓词的知识表⽰※a⽐他哥学习努⼒。定义谓词：SH(x,y)：x⽐y学习努⼒定义函数：B(x) ：x的哥谓词公式表⽰为：SH(a,b(a))※对所有⾃然数都有x+y≥x 定谓：N(x):x是⾃然数，GE(x,y):x⼤于等于y 定函：sum(x,y):x与y的和谓词公式表⽰为：?x?y(N(x)∧N(y) →GE(sum(x,y),y))※某些⼈对⾷物过敏。定谓：M(x):x是⼈;F(x):x是⾷物;定函S(x,y):x对y过敏谓词公式：⼹x⼹y(M(x)∧F(y)∧S(x,y))※例 3.4设在房⾥，a和b是两桌⼦，a桌放有盒⼦box，c处有⼀个机器⼈R，让机器⼈从c出发把盒⼦从a拿到b 桌，再回到c，⽤谓词逻辑描述从初始状态到⽬标状态的机器⼈操作过程。解：定义谓词Table(x)：表⽰x是桌⼦ * Empty(R)：表⽰机器⼈R⼿是空的 * At(R,x)：表⽰机器⼈R在x处Holds(R,Box)：机器⼈R拿着Box * On(Box,x)：积⽊块在x上初态：Empty(R),Table(a),Table(b),On(Box,a) ⽬标：Table(a),Table(b),On(Box,b)机器⼈拿起a：条件：On(Box,a),At(R,a)Empty(R) 删除：Empty(R),On(Box,a) 增加：Holds(R,Box)⾃然演绎推理:利⽤⼀阶谓词推理规则的符号表⽰形式，可以把关于⾃然语⾔的逻辑推理问题，转化为符号表达式的推演变换。这种推理⼗分类似于⼈们⽤⾃然语⾔推理的思维过程，因⽽称为⾃然演绎推理优点：定理证明过程⾃然，易于理解，并且有丰富的推理规则可⽤。缺点：是容易产⽣知识爆炸，推理过程中得到的中间结论⼀般按指数规律递增，对于复杂问题的推理不利，甚⾄难以实现。归结演绎推理是⼀种基于鲁宾逊归结原理（亦称为消解原理）的机器推理技术。是⼀种基于逻辑的“反证法”。在⼈⼯智能中，很多的问题都可以转化为⼀个定理证明问题。定理证明的实质，就是要对前提P和结论Q，证明P→Q永真。要证明P→Q永真，就是要证明P→Q在任何⼀个⾮空的个体域上都是永真的。这将是⾮常困难的，甚⾄是不可实现的。为此，⼈们进⾏了⼤量的探索，后来发现可以采⽤反证法的思想，把关于永真性的证明转化为关于不可满⾜性的证明。即要证明P→Q永真，只要能够证明P∧﹁Q是不可满⾜的就可以了(原因是﹁ (P→Q) ?﹁(﹁P∨Q) ?P∧﹁ Q 。这⽅⾯最有成效的⼯作就是鲁宾逊归结原理。它使定理证明的机械化成为现实。3-2. 什么是替换？什么是合⼀？什么是归结？置换：置换可简单的理解为是在⼀个谓词公式中⽤置换项去替换变量。当⽤g(y)置换x,⽤f(g(y))置换y 时，既没有消去x，也没有消去y。若改为{g(a)/x, f(x)/y}即可，原因是⽤g(a)置换x ，⽤f(g(a))置换y ，则消去了x 和y。合⼀：合⼀可理解为是寻找项对变量的置换，使两个谓词公式⼀致。归结：在谓词公式，某些推理规则以及置换合⼀等概念的基础上，能够进⼀步研究消解原理，有些专家把它叫做归结原理。问题:为什么受全称量词约束的要⽤Skolem函数替换?⽽不能⽤常量替换？实际上，引⼊Skolem函数，是由于存在量词在全称量词的辖域之内，其约束变元的取值完全依赖于全称变量的取值。⽽Skolem函数反映了这种依赖关系。但Skolem标准型与原公式⼀般并不等价。消去存在量词(Skolem化）,同时进⾏变元替换原则：①若该存在量词不在任何全称量词的辖域内，则⽤⼀个常量符号代替该存在量词辖域内的相应约束变元，这个常量叫Skolem常量；②若该存在量词在全称量词的辖域内，则⽤这些全称量词指导变元的⼀个函数代替该存在量词辖域内的相应约束变元，这样的函数称为Skolem函数谓词公式与⼦句集有哪些区别（⼦句集的特征）？没有蕴含词、等值词；“?”作⽤原⼦谓词；没有量词( ?、? )；合取范式；元素之间变元不同；集合形式3-3. 化为⼦句形有哪些步骤? 请结合例⼦说明之。1消去蕴含词和等值词：A->B《=》~AVB、A<-> B <=> ()2使否定词仅作⽤于原⼦公式；3适当改名使量词间不含同名指导变元；4消去存在量词5消去全称量词6化公式为合取范式7适当改名使⼦句间⽆同名变元8消去合取词以⼦句为元素组成⼀个集合S化⼦句集、鲁宾逊归结原理、归结法证明、归结策略要证明⼀个谓词公式是不可满⾜的，只要证明其相应的标准⼦句集是不可满⾜的就可以了。⾄于如何证明⼀个⼦句集的不可满⾜性，由下⾯的海伯伦理论和鲁宾逊归结原理来解决鲁滨逊归结原理基本思想：⾸先把欲证明问题的结论否定，并加⼊⼦句集，得到⼀个扩充的⼦句集S'。然后设法检验⼦句集S'是否含有空⼦句，若含有空⼦句，则表明S'是不可满⾜的；若不含有空⼦句，则继续使⽤归结法，在⼦句集中选择合适的⼦句进⾏归结，直⾄导出空⼦句或不能继续归结为⽌。鲁滨逊归结原理包括：命题逻辑归结原理；谓词逻辑归结原理归结原理⼜称消解原理,1965年鲁滨逊提出，从理论上解决了定理证明问题。归结原理提出的是⼀种证明⼦句集不可满⾜性，从⽽实现定理证明的⼀种理论及⽅法。3-5. 简述⽤归结法证明定理的过程（消解反演求解过程）。给出⼀个公式集S和⽬标公式L，通过反证或反演来求证⽬标公式L，其证明步骤如下：（1）否定L，得到~L；（2）把~L添加到S中去；（3）把新产⽣的集合{~L，S}化成⼦句集F；（4）反复归结⼦句集F中的⼦句，若出现了空⼦句，则停⽌归结，此时就证明了L永真归结策略：归结演绎推理时，如果盲⽬的全⾯进⾏归结的⽅法，不仅会产⽣许多⽆⽤的归结式，更严重的是会产⽣组核爆炸问题。因此，需要有效的归结策略来解决这些问题。⽬前，常⽤的归结策略可分为两⼤类，⼀类是删除策略，另⼀类是限制策略。删除策略是通过删除某些⽆⽤的⼦句来缩⼩归结范围；限制策略是通过对参加归结的⼦句进⾏某些限制，来减少归结的盲⽬性，以尽快得到空⼦句。3-7. 与/或形演绎推理有哪⼏种推理⽅式? 简述推理过程与/或形演绎推理推理⽅式：正向演绎、逆向演绎、双向演绎；正向演绎：从已知事实出发，正向地使⽤蕴含式(F规则)进⾏演绎推理，直⾄得到某个⽬标公式的⼀个终⽌条件为⽌。推理过程：1⽤与/或树把已知事实表⽰出来2⽤F规则的左部和与/或树的叶节点进⾏匹配，并将匹配成功的F规则加⼊到与/或树中3重复第(2)步，直到产⽣⼀个含有以⽬标节点作为终⽌节点的解图为⽌逆向演绎推理：从待证明的问题(⽬标)出发，通过逆向地使⽤蕴含式(B规则)进⾏演绎推理，直到得到包含已知事实的终⽌条件为⽌。推理过程：1⽤与/或树把⽬标公式表⽰出来2⽤B规则的右部和与/或树的叶节点进⾏匹配，并将匹配成功的B规则加⼊到与/或树中3重复进⾏第(2)步，直到产⽣某个终⽌在事实节点上的⼀致解图为⽌与/或形双向演绎推理：由表⽰⽬标及表⽰已知事实的两个与/或树结构组成，这些与/或树分别由正向演绎的F规则及逆向演绎的B规则进⾏操作，并且仍然限制F规则为单⽂字的左部，B规则为单⽂字的右部。不确定性、Bayes定理、逆概率、贝叶斯⽹络、机器学习3-8. 什么是不确定性?有哪⼏种不确定性?知识和信息中含有的不肯定、不可靠、不准确、不精确、不严格、不严密、不完全甚⾄不⼀致的成分。按性质、产⽣的原因及表现形式分类：随机不确定性；模糊不确定性；不完全性；不⼀致性（课件）意义：使计算机对⼈类思维的模拟更接近于⼈类的真实思维过程。不确定性推理是⼀种建⽴在⾮经典逻辑基础上的基于不确定性知识的推理，它从不确定性的初始证据出发，通过运⽤不确定性知识，推出具有⼀定程度的不确定性的和合理的或近乎合理的结论。有两种不确定性，即关于证据的不确定性和关于结论的不确定性。在什么情况下需要采⽤不确定推理?选择不确定性表⽰⽅法时应考虑的因素：充分考虑领域问题的特征；恰当地描述具体问题的不确定性；满⾜问题求解的实际需求；便于推理过程中对不确定性的推算。简述确定性理论（可信度⽅法）的特点。优点：通过简单的计算，就可以使⽤系统各⽅⾯的不确定性得到传播，最终得到系统的结果Bayes定理，逆概率求不确定性求P(肺炎|咳嗽)可能⽐较困难，但统计P(咳嗽|肺炎)可能⽐较容易(因为要上医院)假设先验概率P(肺炎)=1|10000，⽽P(咳嗽)=1|10，90%的肺炎患者都咳嗽，P(咳嗽|肺炎)=0.9,则：P(肺炎|咳嗽)= （P(咳嗽|肺炎)* P(肺炎)）/（P(咳嗽)）=0.0009主观Bayes推理⽅法主观贝叶斯⽅法是Duda等⼈1976年提出的⼀种不确定性推理模型，并成功地应⽤于地质勘探专家系统PROSPECTOR。其核⼼思想是：根据：Ⅰ.证据的不确定性（概率）P(E);Ⅱ.规则的不确定性（LS，LN）；LS：E 的出现对H 的⽀持程度，LN：E 的出现对H 的不⽀持程度。把结论H 的先验概率更新为后验概率P(H|E)；简述主观Bayes⽅法中，LS和LN的意义。LN表⽰必要性因⼦，它表⽰~E 对Ｈ的⽀持程度。LS表⽰充分性因⼦，它表⽰E 对H 的⽀持程度。什么是贝叶斯⽹络？按推理⽅向不同，贝叶斯⽹络推理包括哪⼏种推理模式？掌握贝叶斯⽹络的推理计算⽅法。贝叶斯⽹络是⼀种以随机变量为节点，以条件概率为节点间关系强度的有向⽆环图推理模式: 因果推理、诊断推理、辩解推理、混合推理贝叶斯⽹络的构造⽅法：确定包含哪些结点；建⽴反映条件独⽴的有向⽆环图；指派局部概率分布，即CPT。如果CPT包含了⾜够的条件概率，可以计算出任何联合概率，则称此⽹络是可计算的贝叶斯⽹络不允许包含循环因果关系！6-1 什么是学习和机器学习?为什么要研究机器学习?机器学习：机器学习是研究如何使⽤机器来模拟⼈类学习活动的⼀门学科。稍为严格的提法是：机器学习是⼀门研究及其获取新知识和新技能，并识别现有知识的学问。机器学习的重要性：机器学习是⼈⼯智能的主要核⼼研究领域之⼀, 也是现代智能系统的关键环节和瓶颈；很难想象: ⼀个没有学习功能的系统能被称具有智能的系统；来⾃⽣物、⾦融与⽹络等各领域的数据，迫切需要分析或建⽴模型。6-2 试述机器学习系统的基本结构，并说明各部分的作⽤。基本结构：环境，（学习环节，知识库，执⾏环节）。环境：包括⼯作对象和外界条件。学习环节：通过对环境的搜索取得外部信息，然后经分析、综合、类⽐、推理等思维过程获得知识，并将这些知识送⼊知识库，供执⾏环节使⽤。知识库：系统学习得到的信息。环境向系统的学习部分提供某些信息，学习部分利⽤这些信息修改知识库，以增进系统执⾏部分完成任务的效能，执⾏部分根据知识库完成任务，同时把获得的信息反馈给学习部分。在具体的应⽤中，环境、知识库和执⾏部分决定了具体的⼯作内容，学习部分所需要解决的问题完全由上述三部分确定。6-7 主要的机器学习算法有哪些？（1）决策树（2）回归和分类（3）SVM⽀持向量机（4）Apriori 算法，关联规决策树、ID3、信息增益、回归和分类、贝叶斯分类、朴素贝叶斯分类器、K近邻、集成学习boosting6-4 简述决策树的概念、决策树学习⽅法及其使场合；在构造决策树的过程中，测试属性的选取采⽤什么原则？如何实现？决策树也称判定树，它是由对象的若⼲属性、属性值和有关决策组成的⼀棵树。其中的节点为属性（⼀般为变量），分枝（边）为相应的属性值（⼀般为变量值）。决策树学习是⼀种逼近离散值⽬标函数的⽅法，在这种⽅法中学习到的函数被表⽰为⼀棵决策树。学习得到的决策树也能再被表⽰为多个if-then 的规则，以提⾼可读性。决策树对给定实例的分类过程是按照实例各属性取值情况，在已建好的决策树上从根节点到叶⼦节点的匹配过程。具体步骤如下：步1 从树的根节点开始，测试当前节点指定的属性；步2按照给定实例该属性的取值对应的树枝向下移动，到达下⼀个节点；步3 在以新节点为根的⼦树上重复步1、2，直到到达叶⼦节点，得到该实例的正确分类。给定⼀些训练样本，应该⽣成什么样的决策树？选择与数据匹配的最⼩的决策树（树的深度最浅或树的节点最少）基本的ID3学习算法是通过⾃顶向下构造决策树来完成的：⾸先，按照某标准选取⼀个属性，以该属性作为根节点，以这个属性的全部不同取值作为根节点的分枝，向下增长树，同时按这个属性的不同取值将实例集划分为⼦集，与相应的分⽀节点相关联。然后，考察所得的每⼀个⼦类，看其中的所有实例的⽬标值是否完全相同：如果完全相同，则以这个相同的⽬标值作为相应分枝路径末端的叶⼦节点；否则，选取⼀个不同于祖先节点的属性，重复上⾯过程，直到每个⼦集中的全部实例的⽬标值完全相同，得到所有的叶⼦节点为⽌。ID3最关键的问题就是属性选择问题，整个构建过程是从“哪⼀个属性将在根节点被测试？”开始的。信息增益是⽤信息论中⼴泛使⽤的⼀个度量标准“熵”来定义的⽤熵度量样例的均⼀性：熵是⽆序性（或不确定性）的度量指标。信息熵刻画了任意样例集的纯度，熵越⼩表⽰样本对⽬标属性的分布越纯，反之熵越⼤表⽰样本对⽬标属性分布越混乱。样例集中只有正例或只有反例时，熵为0，正反例各占⼀半时，熵为1。通常情况下，熵为0到1之间的值ID3算法优缺点：优点：理论清晰，⽅法简单，学习能⼒较强。缺点：(1)算法只能处理离散型数据，⽆法处理连续型数据；(2)算法对测试属性的每个取值相应产⽣⼀个分⽀，且划分相应的数据样本集,这样的划分会导致产⽣许多⼩的⼦集。随着⼦集被划分得越来越⼩，划分过程将会由于⼦集规模过⼩所造成的统计特征不充分⽽停⽌；(3)ID3算法中使⽤信息增益作为决策树节点属性选择的标准，由于信息增益在类别值多的属性上计算结果⼤于类别值少的属性上计算结果，这将导致决策树算法偏向选择具有较多分枝的属性，因⽽可能导致过度拟合。回归和分类的区别：他们都有预测的功能，但是：分类预测的输出为离散或标称的属性；回归预测的输出为连续属性值；例⼦：预测未来某银⾏客户会流失或不流失，这是分类任务；预测某商场未来⼀年的总营业额，这是回归任务。贝叶斯分类⽅法是⼀种利⽤概率统计知识进⾏学习分类的⽅法。基于如下的假定：待考察的量遵循某概率分布，且可根据这些概率及已观察到的数据进⾏推理，以作出最优的决策。主要算法有：朴素贝叶斯分类算法；贝叶斯信念⽹络分类算法等。例题：AB两队⾜球⽐赛：假设过去的⽐赛中，65%的⽐赛A对取胜，35%的⽐赛B对取胜。A对胜的⽐赛中只有30%是在B队的主场，B队取胜的⽐赛中75%是在主场。如果下⼀场⽐赛在B队的主场进⾏，哪⽀球队最有可能胜出？解答：根据贝叶斯定理,假定：随机变量X代表东道主，X取值范围为{A,B}；随机变量Y代表⽐赛胜者，取值范围为{A,B}。已知：A取胜的概率为0.65，表⽰为：P(Y=A)=0.65；B对取胜的概率为0.35 ，表⽰为：P(Y=B)=0.35B取胜时作为东道主的概率是0.75，⽰为：P(X=B|Y=B) = 0.75；A取胜时B作为东道主的概率是0.3,⽰为:P(X=B|Y=A) = 0.3, 计算：下⼀场⽐赛在B主场，同时A胜出的概率表⽰为：P(Y=A|X=B)P(Y=A|X=B) = P(X=B|Y=A)*P(Y=A)/P(X=B)= (0.3*0.65)/0.4575=0.4262下⼀场⽐赛在B主场，同时B胜出的概率表⽰为：P(Y=B|X=B)P(Y=B|X=B)=P(X=B|Y=B)*P(Y=B)/P(X=B)=(0.75*0.35)/0.4575=0.5737根据计算结果，可以推断出，下⼀场最有可能是B胜出。朴素贝叶斯分类器：是⼀种实⽤性很⾼的贝叶斯学习器/ 某些应⽤中性能与神经⽹络和决策树相当。按照极⼤后验概率取值的原则，其输出⽬标值应满⾜最⼤后验概率公式朴素贝叶斯优缺点：优点：容易实现；在⼤多数情况下所获得的结果⽐较好。缺点：算法成⽴的前提是假设各属性之间互相独⽴；当数据集满⾜这种独⽴性假设时，分类准确度较⾼；⽽实际领域中，数据集可能并不完全满⾜独⽴性假设K-最近邻分类算法是⼀种基于实例的学习算法，它不需要先使⽤训练样本进⾏分类器的设计，⽽是直接⽤训练集对数据样本进⾏分类，确定其类别标号。基本思想是：对于未知类标号的样本，按照距离找出它在训练集中的k个最近邻，将未知样本赋予k最近邻中出现次数最多的类别号。K近邻优缺点：优点：算法思想简单，易于实现。缺点：最近邻分类对每个属性指定相同的权重，⽽数据集中的不同属性可能需要赋予不同的权值；由于K-NN存放所有的训练样本，直到有新的样本需要分类时才建⽴分类，因此当训练样本数量很⼤时，该学习算法的时间复杂度为n2。Boosting、⼈⼯神经⽹络、BP神经⽹络、深度学习、遗传算法、强化学习构建集成分类器的⽅法：Boosting是⼀种最⼴泛使⽤的集体学习⽅法，其核⼼思想是加权训练（1）⼀般的学习算法获得的结果通常包含不少错误(甚⾄可以要求仅强于随机猜想即只要>1/2的正确率)—该算法可以被称为“弱学习”或者“基本学习”算法。（2）Boosting算法多次调⽤这个弱学习算法，⽤不同的训练⼦集(每个样例赋予不同权值)每次从被调⽤算法获得⼀个弱假设（3）算法最终把上述弱假设组合起来，产⽣⼀个更加精确的单⼀假设，以获得更好的预测结果。Boosting是⼀个迭代的过程，⽤于⾃适应地改变训练样本的分布，使得基分类器聚焦在那些很难分的样本上。给每⼀个训练样本赋予⼀个权值，⽽且可以在每⼀轮提升过程结束时⾃动地调整权值。Boosting两个基本问题：(1)每次调⽤弱学习算法，如何选择训练⼦集？选择那些被弱学习算法分类错误的实例，增加其权值.(2)如何把弱假设组合为⼀个单⼀规则？采⽤简单多数表决的原则装袋和Boosting的区别① bagging的训练集是随机的，各训练集是独⽴的；⽽boosting训练集的选择不是独⽴的，每⼀次选择的训练集都依赖于上⼀次学习的结果。② bagging的每个预测函数都没有权重；⽽boosting根据每⼀次训练的训练误差得到该次预测函数的权重。③ bagging的各个预测函数可以并⾏⽣成；⽽boosting只能顺序⽣成。（对于神经⽹络这样极为耗时的学习⽅法，bagging可通过并⾏训练节省⼤量时间开销）什么是⼈⼯神经⽹络ANN：是由具有适应性的简单单元组成的⼴泛并⾏互连的⽹络，它的组织能够模拟⽣物神经系统对真实世界物体所作出的交互反应。⼈⼯神经⽹络算法学习的过程：神经⽹络在外界输⼊样本的刺激下不断改变⽹络的连接权值,以使⽹络的输出不断地接近期望的输出。学习的本质：对各连接权值的动态调整。学习规则：权值调整规则，即在学习过程中⽹络中各神经元的连接权变化所依据的⼀定的调整规则。BP神经⽹络的特点：⾮线性映射能⼒：能学习和存贮⼤量输⼊-输出模式映射关系，⽽⽆需事先了解描述这种映射关系的数学⽅程。只要能提供⾜够多的样本模式对供⽹络进⾏学习训练，它便能完成由n维输⼊空间到m维输出空间的⾮线性映射。泛化能⼒：当向⽹络输⼊训练时未曾见过的⾮样本数据时，⽹络也能完成由输⼊空间向输出空间的正确映射。这种能⼒称为泛化能⼒。容错能⼒：输⼊样本中带有较⼤的误差甚⾄个别错误对⽹络的输⼊输出规律影响很⼩。深度学习是机器学习研究中的⼀个新的领域，其动机在于建⽴、模拟⼈脑进⾏分析学习的神经⽹络，它模仿⼈脑的机制来解释数据，例如图像，声⾳和⽂本。深度学习的实质，是通过构建具有很多隐层的机器学习模型和海量的训练数据，来学习更有⽤的特征，从⽽最终提升分类或预测的准确性。BP算法作为传统训练多层⽹络的典型算法，实际上对仅含⼏层⽹络，该训练⽅法就已经很不理想。存在的问题：（1）梯度越来越稀疏：从顶层越往下，误差校正信号越来越⼩；（2）收敛到局部最⼩值：尤其是从远离最优区域开始的时候（随机值初始化会导致这种情况的发⽣）；（3）⼀般，我们只能⽤有标签的数据来训练：但⼤部分的数据是没标签的，⽽⼤脑可以从没有标签的的数据中学习；深度学习训练过程：1）使⽤⾃下上升⾮监督学习（就是从底层开始，⼀层⼀层的往顶层训练）：2）⾃顶向下的监督学习（就是通过带标签的数据去训练，误差⾃顶向下传输，对⽹络进⾏微调）：6-6 遗传算法的基本操作。遗传算法的构成要素？什么是选择，交叉和变异？基本操作：复制：从当前群体中选择⼀定⽐例的个体直接进⼊下⼀代群体。交叉：将两个双亲染⾊体中对应的某些基因进⾏交换，从⽽产⽣新的后代。变异：对染⾊体的某⼀基因或某些基因取反，得到新的染⾊体。构成要素：（1）染⾊体编码⽅法（2）个体适应度评价（3）遗传算⼦：基本遗传算法使⽤下述三种遗传算⼦：①选择运算:使⽤⽐例选择算⼦；②交叉运算:使⽤单点交叉算⼦；③变异运算:使⽤基本位变异算⼦或均匀变异算⼦。（4）基本遗传算法的运⾏参数。有下述4个运⾏参数需要提前设定：M：群体⼤⼩，即群体中所含个体的数量，⼀般取为20~100；G：遗传算法的终⽌进化代数，⼀般取为100~500；Pc：交叉概率，⼀般取为0.4~0.99；Pm：变异概率，⼀般取为0.0001~0.1。强化学习：⼜称为增强学习，是种从环境状态到⾏为映射的学习，⽬的是使动作从环境中获得的累积回报值最⼤。强化学习围绕如何与环境交互学习的问题，在⾏动——评价的环境中获得知识，从⽽改进⾏动⽅案以适应环境达到预想的⽬的。强化学习系统：基本框架主要由两部分组成，即环境和智能体（Agent）。智能体可以通过传感器（Sensor）感知所处环境，并通过执⾏器（Actuator）对环境施加影响。强化学习原理：如果智能体（Agent）的某个⾏为策略导致环境对智能体正的奖赏（Reward），则智能体以后采取这个⾏为策略的趋势会加强。反之，若某个⾏为策略导致了负的奖赏，那么智能体此后采取这个动作的趋势会减弱。强化学习的特点：（1）强化学习是⼀种弱的学习⽅式，体现为：Agent 通过与环境不断的试错交互来进⾏学习；强化信息可能是稀疏且合理延迟的；不要求（或要求较少）先验知识；Agent在学习中所使⽤的反馈是⼀种数值奖赏形式，不要求有提供正确答案的教师；（2）强化学习是⼀种增量式学习，并可以在线使⽤；（3）强化学习可以应⽤于不确定性环