人工智能复习

1、第一章.人工智能的定义（能力）人工智能的研究目标.人工智能的起源与发展过程；典型人物、事件.人工智能的主要学派及观点人工智能所研究的范围与应用领域5.人工智能的基本技术人工智能的定义（能力）：人工智能Artificial Intelligence （AI）, 一般解释：人工智能就是 用人工的方法在机器（计算机）上实现的智能，或称机器智能、计算机智能。近期目标：实现机器智能一一理论和技术基础 远期目标：制造智能机器一一发展方向：孕育 期（1956年前）:形成 期（1956-1970 年）:暗 淡 期（1966-1974 年）知识应用期（1970-1988年）集成发展期（1986年至今） 1956

2、年前亚里斯多（三段论至今仍然是演绎推理基本出发点）德莱布尼茨（把 形式逻辑符号化，奠定了数理逻辑的基础）图灵（人工智能之父）莫克（1946 年研制成功了世界上第一台通用电子数字计算机ENIAC）麦克洛奇和皮兹（第一 个神经网络模型（MP模型）维纳（控制论创始人） 1956-1970： AI诞生于一次历史性的聚会一达特茅斯会议（首次使用了 “人工智能”这一 术语。这是人类历史上第一次人工智能研讨会）1966-1974： 1970-1988：专家系统1986-人工智能学会1981秦元勋当选第一任理事长吴文俊院士的关于几何定理证明的“吴氏方法最为突出。人工智能的主要学派及观点：符号主义椅又称：逻辑主

3、义、心理学派或计算机学派椅原理：物理符号系统（即符号操作系统）假设和有限合理性原理椅起源：源于数理逻辑/逻辑推理椅学派代表：纽厄尔、西蒙和尼尔逊等:连接主义椅又称：仿生学派或生理学派椅 原理：神经网络及神经网络间的连接机制与学习算法。椅起源：源于仿生学，特别是人脑模型的研究。椅学派代表：麦克洛奇、皮茨、霍普菲尔德、鲁梅尔哈特等。行为主义椅又称：进化主义或控制论学派椅原理：控制论及感知一动作型控制系统椅起源：源于控制论椅学派代表作：布鲁克斯的六足行走机器人，一个基于感知-动作模 式的模拟昆虫行为的控制系统。人工智能所研究的范围与应用领域：智能感知：1、模式识别2、自然语言理解智能推理：1、问题求

4、解2逻辑推理与定理证明3、专家系统4、自动程序设计智能学习：1、机器学习2、神经网络3、计算智能与进化计算智能行动：1、机器人学2、智能控制3、智能检索4、智能调度与指挥5、分布式人工智能与Agent 6、数据挖掘与知识发现7、人工生命8、机器视觉人工智能的基本技术：推理技术搜索技术知识表示与知识库技术归纳技术联想技术第二章概念：知识及形式化描述、同构变换、同态变换知识、信息和数据的区别知识表示法应用（一阶谓词、产生式、框架、语义网络）产生式系统的基本结构语义网络中的语义联系（实例、泛化、聚集、属性、推论）推理过程中填槽的方式概念：知识及形式化描述、同构变换、同态变换知识表示就是把知识用计算机

5、可接受的符号并以某种形式描述出来，而不同的结 构形式又形成了不同的表示方法。一般来说，把有关信息关联在一起所形成的信息结构称为知识。知识表示=数据结构+处理机制知识的形式化表示：K = F + R + C其中：K表示知识项（知识项目）F表示事实，人类对客观世界、客观事物的状态、属性、特征的描述，以及 对事物之间关系的描述；R表示规则，能表达在前提与结论之间的因果关系的一种形式；C表示概念（观念），事实的含义规则、语义说明等。.：.同构变换可使问题更明确，便于求解，同构问题的解答等价于原始问题 的解答。:同态变换可使问题更加简化，易于求解。原始问题有解，则同态问题有 解，同态问题无解，则原始问题

6、无解，它们之间是蕴含关系。知识、信息和数据的区别数据是记录信息的符号，是信息的载体和表示；信息是对数据的解释， 是数据在不同场合下的具体含义。只有将有关的信息关联到一起才能使用，才称之为知识。知识表示法应用（一阶谓词、产生式、框架、语义网络）一阶谓词逻辑是谓词逻辑中最直观的一种逻辑，它以谓词形式来表达动作的主体、客体（可以有多个）PPT30:置换是指用有序对的集合s=t1/v1，t2/v2，孔/匕表示，其中v.是变量，t.是异于v.的项；v. v.，i尹j，jei，2，nti/vi表示将表达式中所有的变量v.都用项t.代替，t.可以是变量、常量或函数。PPT36设S=F1，F2,，Fn是一个原

7、子谓词集合，如果存在一个置换e，可使F10 = F2e =Fne，则称S是可合一的，e为S的一个合一转换。PPT37一个产生式系统包含事实库（工作区）、规则集（产生式规则库）和控制器（进 行规则解释，也称为推理机）三部分。语义网络可以表示事实性的知识，也可表示有关事实性知识之间的复杂联系。PPT73框架是一种组织和表示知识的数据结构。PPT95第三章1、状态空间搜索概述状态空间的图描述，搜索，正向逆向搜索，影响搜索方 向的因素2、盲目的图搜索策略图搜索、搜索树、回溯法、广度优先法、深度优先法、3、启发式图搜索策略启发信息与估价函数、A搜索算法、OPEN表、CLOSED 表4、与/或图（树）搜索

8、策略 搜索算法、解树及代价、希望树、博弈树搜索、极 大极小分析法、a P剪枝5、遗传算法的基本思想1、状态空间搜索概述 状态空间的图描述，搜索，正向逆向搜索，影响搜索方 向的因素状态空间搜索是问题求解的主要方法之一。状态空间可用有向图来描述（见图），其结点表示状态，结点间的弧表示允许使 用的操作算子搜索就是从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程(也可以反向进行)。当目标节点找到后，路径也就找到了。搜索可按两个方向进行：从初始状态出发的正向搜索，也称为数据驱动； 从目的状态出发的逆向搜索，也称为目标驱动。搜索方向开始状态与目标状态中，哪个状态多？往往从小的状态集出发朝大的

9、状 态集搜索，这样求解要容易一些。哪个方向的分枝因素小？所谓分枝因素是指从一结点出发可直接到达目 标的平均结点数。一般地，都是朝着分枝因素低的方向进行搜索。2、盲目的图搜索策略图搜索、搜索树、回溯法、广度优先法、深度优先法:用计算机来实现状态图的搜索，有两种最基本的搜索方式：树式搜索和 线式搜索。线式搜索的基本方式又可分为不回溯的和可回溯的两种。不回溯的线式搜索：对每一个节点始终都仅生成一个子节点(如果有子节点的话)。 可回溯的线式搜索：对每一个节点都仅扩展一条边，但当不能再扩展时，则退 回一个节点，然后再扩展另一条边(如果有的话)。如果搜索是以接近起始节点的程度依次扩展节点，那么这种搜索就称

10、为广度优 先搜索深度优先搜索法在搜索树的每一层始终先只扩展一个子节点，不断向纵深前进， 直到不能再前进(到达叶子节点或受到深度限制)时，才从当前节点返回到上 一级节点，沿另一方向前进。3、启发式图搜索策略启发信息与估价函数、A搜索算法、OPEN表、CLOSED 表启发式搜索要用到问题自身的某些特性信息，以指导搜索朝着最有希望的方向 前进。启发式搜索通常由两部分组成：启发方法和使用该方法搜索状态空间的算法。启发信息按其用途可分为下列3种：用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲 目地扩展。在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免 盲目地同时生成

11、所有可能的节点。用于决定某些应该从搜索树中抛弃或修剪的节点。启发信息按运用的方法可分为三种：陈述性启发信息，一般被用于更准确、更精炼地描述状态，使问题的状态空 间缩小，如待求问题的特定状况等属于此类信息。 过程性启发信息，一般被用于构造操作算子，使操作算子少而精，如一些规 律性知识等属于此类信息。控制性启发信息，它是关于表示控制策略方面的知识，包括协调整个问题求 解过程中所使用的各种处理方法、搜索策略、控制结构等有关的知识。估价函数的任务就是估计待搜索结点的“有希望”程度，并依此给它们(在 open表)排定次序。:估价函数f(n)定义为从初始结点经过n结点到达目的结点的路径的最小代 价估计值，

12、其一般形式是：f(n) = g(n) + h(n)其中：g(n)是从初始结点到n结点的实际代价，h(n)是从n结点到目的结点的最佳路径的估计代价。A搜索算法总是选择最有希望的节点作为下一个要扩展的节点。估价函数f的确定： 一个节点的希望越大，其f值就越小。被选为扩展的节点(走f值最小的路)。扩展的节点 是估价函数最小的节点。采用一个称为OPEN表的动态数据结构，来专门登记当前待考查的节点。: 一个称为CLOSED表的动态数据结构来专门记录考查过的节点。4、与/或图(树)搜索策略 搜索算法、解树及代价、希望树、博弈树搜索、极 大极小分析法、a p剪枝模拟问题归约方法的相关结构是一个与或图。与或图

13、中的节点之一起始 节点对应于原始问题描述。图中那些对应于本原问题的节点叫做终叶节 点。与或树的一般搜索过程：把原始问题作为初始结点s0,并把它作为当前结点。应用分解或等价变换算符对当前结点进行扩展。为每个子结点设置指向父结点的指针。选择合适的子结点作为当前结点，反复执行第(2)步和第(3)步，在此期间要多 次调用可解结点标示过程和不可解结点标示过程，直到初始结点被标示为可解 结点或不可解结点为止。可解结点及有关连线组成的子图(子树)称该与或图的解图或解树。解树的代价就是树根的代价。树根的代价是从树叶开始自下而上逐层计算而求 得的。解树的根对应的是初始节点s0。这些节点及其先辈节点(包括初始节点

14、So)所构成的与或树有可能成为最优解树的一部分，因此称它为“希望树”.:描述博弈过程的与或树称为博弈树。极大极小分析法(MAX/MIN搜索法)的基本思想：(1)设博弈的双方中一方为A，另一方为B。然后为其中的一方(例如A，此时A 为MAX方)寻找一个最优行动方案。为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比 较。考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。(3)为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博 弈树端节点的得分。此时估算出来的得分称为静态估值。：. a p剪枝技术的基本思想是，边生成博弈树边计算评估各节点的倒推值， 并且根

15、据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子 节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提 高了搜索效率。 a值和。值的定义：或结点(max 方)的a值等于它的当前子结点中的最大倒推值；与结点(MIN方)的P值等于它的当前子结点中的最小倒推值。PPT96由上面的例子可归纳出a-P剪枝技术的一般规则：（1）任何“与”节点x的R值如果不能升高其父节点的a值，则对节点x以下的分 枝可以停止搜索，并使x的倒推值为B。这种剪枝称为a剪枝。 任何“或”节点x的a值如果不能降低其父节点的。值，则对节点x以下的分 枝可停止搜索，并使x的倒推值为a。这种剪枝称为P剪枝。5、遗传算法

16、的基本思想3.4之传算除-遗传算法的基本原理编码与译码适应度函数.遗传操作,控制参数3.4.2遗传算威的结构简单-遗传算法的求解步骤初始化群体；计算群体上每个个体的适应度值；按由个体适应度值所决定的某个规则选择将进入下一代的个体；按概率PC进行交叉操作；按概率Pc进行突变操作；没有满足某种停|.条件，则转第）步，否 则进入。-.7）输出种群中适应度值最优的染色体作为向题的满意解或最优解第四章推理的概念、类型，推理的控制策略、正反向推理归结反演系统一归结原理、归结反演、应用归结反演求取问题的答案 的过程归结原理相关概念、置换、合一3基于规则的演绎推理（正向、反向和双向的演绎推理过程描述）1、推理

17、的概念、类型，推理的控制策略、正反向推理从初始事实出发，不断运用知识库中的已知知识，逐步推出结论的过程就是推 理。类型:逻辑基础：椅演绎推理：三段论（大前提、小前提、结论）椅归纳推理：数学归纳法椅默认（缺省）推理:知识的确定性：椅确定性推理（精确推理）椅 不确定性推理（不精确推理）过程的单调性：椅单调推理椅非单调推理搜索策略、冲突解决策略正向推理（事实驱动推理）是由已知事实出发向结论方向的推理。反向推理（目标驱动推理）以某个假设目标作为出发点的一种推理。正反向混合推理的一般过程是：先根据初始事实进行正向推理以帮助提出假设， 再用反向推理进一步寻找支持假设的证据，反复这个过程，直到得出结论为止。

18、2、归结反演系统一一归结原理、归结反演、应用归结反演求取问题的答案的过 程谓词公式化为子句集将谓词公式化为子句集的步骤如下：（1）消去蕴含符 和双条件符3。 把否定符号“”移到紧靠谓词的位置上。（3）将变量标准化，使每个量词采用不同的变量。（4）消去存在量词。将公式化为前束形。（6）母式化为合取范式。合取范式就是子句的合取式。略去全称量词。（8）消去合取符号A,把母式用子句集表示。（9）子句变量标准化，即重新命名变量，使每个子句中的变量符号不同。归结也称为消解，归结原理也称为消解原理。归结反演就是利用归结和反演实现定理的证明。PPT422、归结原理相关概念、置换、合一3、基于规则的演绎推理（正

19、向、反向和双向的演绎推理过程描述）正向演绎推理从已知事实出发，反复尝试所有可利用的规则（F规则）进 行演绎推理，直至得到某个目标公式的一个终止条件为止。基于规则的正向演绎推理应用F规则作用于表示事实的与/或图，改变与/ 或图的结构，从而产生新的事实，直至推出了目标公式，则推理就成功 结束。其推理过程为：首先用与/或图把已知事实表示出来。用F规则的左部和与/或图的叶结点进行匹配，并将匹配成功的F规则加 入到与/或图中，即利用F规则转换与/或图。重复第步，直到产生一个含有以目标结点作为终止结点的解图为止。基于规则的反向演绎推理是从目标表达式出发，通过反向运用规则（B规 则）进行演绎推理，直到得到包

20、含已知事实的终止条件为止。.：.反向演绎推理是从目标与或图出发，通过运用B规则最终得到了某个终 止在事实结点上的一致解图时，推理就成功结束。具体过程如下：用与/或图将目标表达式表示出来。在目标与/或图中，如果有一个文字能够与L合一，则可应用B规则Wf 并将1，结点通过一个标有L和L，的最简单合一者的匹配弧与L相连，再将 匹配成功的B规则加入到与/或图中。一条规则可用多次，每次应使用不同的变 量。当一个事实文字和与/或图中的一个文字可以合一时，可将该事实文字通过 匹配弧连接到与/或图中相应的文字上，匹配弧应标明两个文字的最简合一者。重复进行第步，直到与/或图中包括一个结束在事实结点上的一致解图，

21、该 解图的合一复合作用于目标表达式就是解答语句。/双向演绎推理分别从正反两个方向进行推理，两个与/或图分别扩展，最 关键也是最复杂的是如何判断推理是否结束。推理的终止处位于两个与/ 或图分别扩展后的某个交接处，当正反两个方向的与/或图对应的叶结点 都可合一时，推理就结束。L机器学习的概念、主要策略，机器学习系统的功能及结构机械学习、示例学习、类比学习、归纳学习的基本原理基本思想：基于决策树的归纳学习、强化学习、神经网络、基于8?网络的学 习L机器学习的概念、主要策略，机器学习系统的功能及结构机器学习是一门研究计算机获取新知识和新技能，并识别现有知识的学问。 机械学习。机械学习就是记忆，是最简单

22、的学习策略。这种学习策略不需要 推理，而是由教师向系统提供被记忆的信息，并用这些信息指导系统的行为。传授学习（指导学习）。由外部给系统提供抽象、一般化的信息，学习系统经 过选择和改造，把新的信息与系统原有的知识融为一体。（3）类比学习。类比学习系统只能得到完成类似任务的有关知识，因此，学习 系统必须能够发现当前任务与已知任务的相似之点，由此制定出完成当前任务的 方案，因此，它比上述两种学习策略需要更多的推理（4）通过事例学习。采用通过事例学习策略的计算机智能系统，事先完全没有 完成任务的任何规律性的信息，所得到的只是一些具体的工作例子及工作经验。 系统需要对这些例子及经验进行分析、总结和推广，

23、得到完成任务的一般性规律， 并在进一步的工作中验证或修改这些规律，因此需要的推理是最多的。功能：（1）具有适当的学习环境。（2）具有一定的学习能力。（3）能用所学的知识 解决问题。（4）能提高系统的性能。结构:机械学习、示例学习、类比学习、归纳学习的基本原理机械学习方法不要求系统具有对复杂问题求解的能力，也就是没有推理技能，系 统的学习方法就是，直接记录问题有关的信息，然后检索并利用这些存储的信息 来解决问题。示例学习也称实例学习，它是一种归纳学习。示例学习是从若干实例（包括正例 和反例）归纳出一般概念或规则的学习方法。类比学习是基于类比推理的一种学习方法。归纳学习是符号学习中研究得最为广泛的

24、一种方法。给定关于某个概念的一系列 已知的正例和反例，其任务是从中归纳出一个一般的概念描述。归纳学习能够获 得新的概念，创立新的规则，发现新的理论。基本思想：基于决策树的归纳学习、强化学习、神经网络、基于8?网络的学 习决策树学习-决策树学习是一种归纳学习.特征是由若干个具体的实例表现出来的特征 、属性中，通过比较、概括等方法而得出一 般性规律和结论。.决策树学习的过程就是由空树开始从训练集 中不断选择测试属性、逐步创建决策树的过 程。强化学习的概念强化学习就是智能系统从环境到行为映射的学习,以使奖励信号(强化信号)函数值最大。强化学习的基本模型和原理状态SI-奖夷N环境动作角反向传播(bac

25、k-propagation,BP)算法是 一种计算单个权值变化引起网络性能变 化值的较为简单的方法。 BP算法过程包含从输出节点开始，反向 地向第一隐含层传播由总误差引起的权 值修正。人工神经元的组成与分类人工神经元的组成-模拟神经元处理单元PE (processing element)有向弧则第六早专家系统的概念、理想结构模型，构建专家系统的主要步骤基于规则的专家系统的优缺点基于框架专家系统：继承、槽、方法知识发现的定义专家系统的概念、理想结构模型，构建专家系统的主要步骤专家系统是一个智能计算机程序系统，其内部含有大量的某个领域专家水平的知识与经验， 能够利用人类专家的知识和解决问题的方法来

26、处理该领域问题。理想专家系统的结构知识库综合数据库-推理机解释器接口 TOC o 1-5 h z 用F日制I| i 执行器 |4:Gw)彳调一器E* I II Ii |I1II1设计初始知识库问题知识化知识概念化概念形式化形式则化 原型机(prototype) 的开发与试验知识库的改进与归纳规则合法化控制与知识分离易于扩展相关知识的使用致性检查希确定知识的使2.基于规则的专家系统的优缺点基于规则专,家系统的优点自然表达知识模块性-智能成比例增长-从严格语法获取解释-启发性知识的使用可以合用变量基于规则专家系统的缺点必需精确匹配有不清楚的规则关系具有大量规则的专家系统可能慢对一些问题不适用3.基

27、于框架专家系统：继承、槽、方法基于框架专家系统的继承继承：后辈框架呈现其父辈框架的特征的过 程d后辈框架通过这个特征继承其父辈框架的所 有特征。,实例继承其父辈的所存属性、属性值和槽异常处理多重继承基于框架专家系统的槽-槽；框架属性有关的扩展知识。槽提供对属性值和系统操作的附加控制。类型；定义和属性相关值的类型；-默认：定义默认值：，文档：提供届性文档；约束：定义允许值；最小界限：建立居忸的下限；最大界限：建立属性的上限；-如果需要：指定如果需蹇属性值时来ik的行为；如果改变！指定如果属性值改变时采取的行为。_ -基于框架专家系统的方法方法：附加到对象中需要时执行的过程.在一些应用程序中“如果

28、需要”方法只有当需 要时才获取属性值？打如果改变”槽执行一些方法的情况下属性值 改变事件中的函数。知识发现的定义知识发现的定义数据库中的知识发现是从大量数据中辨识出有 效的、新颖的、潜在有用的、并可被理解的模式的高级处理过程（KDD is the nontrivial第七章机器人的定义、发展历程（三代）、制造原则、主要构成Agent的基本特征、BDI模型、Agent的工作过程图Agent的类型、与专家系统和对象的区别Agent通信机制：黑板和消息对话多Agent系统：特征、协调、协作1、机器人的定义、发展历程（三代）、制造原则、主要构成机器人是一种自动化的机器，所不同的是这种机器具备一些与人或

29、生物相似的 智能能力，如感知能力、规划能力、动作能力和协同能力，是一种具有高度灵活性的自动化机器”智能机器人是人工智能中的最重要的应用，机器人是一种能模拟人的行为的机械， 对它的研究经历了三代的发展过程：第一代（程序控制）机器人；第二代（自适应）机器人；第三代（智能）机器人；原则：1、机器人不应伤害人类；2、机器人应遵守人类的命令，与第一条违背的命令除外；3、机器人应能保护自己，与第一条相抵触者除外。机器人构成：机器人的身体一一机器人本体机器人的灵魂一控制系统机器人的大脑一主控系统机器人的感官一传感系统机器人智慧的来源一计算机程序2. Agent的基本特征、BDI模型、Agent的工作过程图A

30、gent的基本特性：自主性 亦称自治性，即能够在没有人或别的Agent的干预下，主动地自 发地控制自身的行为和内部状态，并且还有自己的目标或意图。反应性即能够感知环境，并通过行为改变环境。适应性即能根据目标、环境等的要求和制约作出行动计划，并根据环境 的变化，修改自己的目标和计划。社会性 即多个Agent在同一环境中协同工作。(1)理性Agent模型(BDI模型)Belief信念，Agent对环境的基本看法。Desire愿望，Agent想要实现的状态，即目标。Intention意图，目标的子集。BDI模型可以通过下列要素描述：(1) 一组关于世界的信念；Agent当前打算达到的一组目标；一个规

31、划库，描述达到目标和改变信念的方案；一个意图结构，描述当前状态如何达到目标和改变信念。工作过程：3、Agent的类型、与专家系统和对象的区别反应式Agent：反应式Agent只简单地对外部刺激产生响应，没有任何内 部状态。每个Agent既是客户，又是服务器，根据程序提出请求或做出 回答。慎思式 Agent：慎思式(deliberative)Agent 又称为认知式(cognitive) Agent，是个具有显式符号模型的基于知识的系统。跟踪式Agent:具有内部状态的反应式Agent通过找到一条条件与现有环境匹配的规 则进行工作，然后执行与规则相关的作用。这种结构叫做跟踪世界Agent或跟踪式Ag