1、人工智能与专家系统 研究生课程 第一章 绪论 1.1 人工智能的定义和发展 1.2 人类智能和人工智能 1.3 人工智能的各种认知观 1.4 人工智能的研究与应用领域 1.5 课程概要 1.1.1 人工智能的定义 几种定义 智能机器（intelligent machine） 人工智能（学科） 人工智能（能力） 人工智能（拟人思维、行为 ） 人工智能（理性思维、行为 ） 1.1 定义和发展 1.1.2 人工智能的起源与发展 孕育期（1956年前） 数理逻辑学科（弗雷治、维纳等 ） 计算的新思想（丘奇、图灵 等） 形成期（1956-1970年） 1956年，第一次人工智能的研讨会 1969年，第一
2、届国际人工智能联合会议 1970年，人工智能国际杂志创刊 1.1 定义和发展 1.1.2 人工智能的起源与发展 发展期（1970年） 进一步研究AI基本原理方法和技术 进行实用化研究 专家系统与知识工程 机器定理证明 智能机器人 智能控制等 从“一枝独秀”到“百花齐放” 1.1 定义和发展 1.2 人类智能和人工智能 1.2.1 智能信息处理系统的假设 人是一种智能信息处理系统 物理符号系统的六种基本功能 物理符号系统的假设 推论一 推论二 推论三 1.2.1 智能信息处理系统的假设 人类的认知行为具有不同层次 认知生理学 认知心理学 认知信息学 认知工程学 1.2 人类智能和人工智能 1.2
3、.2 人类智能的计算机模拟 机器智能可以模拟人类智能 智能计算机 下棋 定理证明 语言翻译 新型智能计算机 神经计算机 量子计算机 1.2 人类智能和人工智能 1.2.3 人工智能的研究目标 近期目标 建造智能计算机代替人类的部 分智力劳动 远期目标 用自动机模仿人类的思维过程 和智能行为 1.2 人类智能和人工智能 1.3 人工智能的各种认知观 符号主义（Symbolicism） 基于物理符号系统假设和有限合理性原理 连接主义（Connectionism） 基于神经网络及其间的连接机制与学习算法 行为主义（Actionism） 基于控制论及感知动作型控制系统 1.4 人工智能的研究及应用领
4、域 人工智能的基本技术 知识表示（Knowledge Representation ） 状态空间法、问题归约法、谓词 逻辑法 推理搜索（Searching & Reasoning） 启发式搜索、消解原理、不确定 性推理 计算智能（Computational Intelligence ） 模糊计算、神经计算、进化计算 构成技术（系统与语言） 产生式系统、LISP语言、Prolog 语言 1.4.1 问题求解 问题的表示、分解、搜索、归约等 进行复杂的数学公式符号运算求解 1.4.2 逻辑推理与定理证明 通过对事实数据库的操作来证明定理 多种证明方法 几何定理证明的“吴氏方法” 1.4 研究及应用
5、 1.4.3 自然语言理解 语言 自然语言、人造语言、机器语言 “理解”的标准 1.4.4 自动程序设计 根据不同目的描述来编写的计算机程序 促进人工智能系统的发展 1.4 研究及应用 1.4.5 专家系统 是一个智能化的计算机程序系统 和传统的计算机程序之间有本质区别 1.4.6 机器学习 是机器获取智能的途径 学习是一个有特定目的的知识获取过程 学习的本质是对信息的理解与应用 有多种学习方法 1.4 研究及应用 1.4.7 神经网络 神经计算机 在其它领域中的广泛应用 1.4.8 机器人学 操作机器人 智能机器人 机器人的广泛应用 促进人工智能的发展 1.4 研究及应用 1.4.9 模式识
6、别 是计算机对环境识别的需要 是对人类环境的感知模拟 1.4.10 机器视觉 人类80以上的外部信息来自视觉 低层视觉与高层视觉 前沿研究领域 广泛应用 1.4 研究及应用 1.4.11 智能控制 驱动智能机器自主地实现其目标的过程 是一个定性和定量的混合控制过程 是当今自动控制的最高水平 1.4.12 智能检索 是信息时代来临的需要 智能检索系统所面临的三大问题 1.4 研究及应用 1.4.13 智能调度与指挥 寻找最佳调度和组合 NP完全类问题的求解 军事指挥系统等领域 1.4.14 分布式人工智能与Agent 是传统人工智能的延伸和扩展 研究目标是创建一种能描述自然系统和社 会系统的精确
7、概念模型 1.4 研究及应用 1.4.15 计算智能与进化计算 计算智能 包括神经计算、模糊计算、进化计算等 进化计算的理论基础是生物进化论 1.4.16 数据挖掘与知识发现 知识获取 数据库知识挖掘 数据库中知识发现的四个特征 1.4 研究及应用 1.4.17 人工生命 人工生命概念的提出 理论基础与研究方法 研究内容 1.4.18 系统与语言工具 计算机系统的一些概念得到发展 新的编程语言与专用开发工具 1.4 研究及应用 1.5 课程概要 简述人工智能的起源与发展 概括地论述知识表示的各种主要方法 讨论常用的搜索原理和推理求解技术 介绍近期人工智能技术和方法的热点 详细地分析人工智能的主
8、要应用领域 叙述人工智能的争议与展望 第二章 知识表示方法 2.1 状态空间法 2.2 问题归约法 2.3 谓词逻辑法 2.4 语义网络法 2.5 其他方法 2.6 小结 2.1状态空间法 （State Space Representation） 问题求解技术主要是两个方面： 问题的表示 求解的方法 状态空间法 状态（state） 算符（operator） 状态空间方法 2.1.1 问题状态描述 定义 状态：描述某类不同事物间的差别而引入 的一组最少变量q0，q1，qn的有序集合 。 算符：使问题从一种状态变化为另一种状 态的手段称为操作符或算符。 问题的状态空间：是一个表示该问题全部 可能状
9、态及其关系的图，它包含三种说明 的集合，即三元状态（S，F，G）。 2.1 状态空间法 2. 状态空间表示概念详释 例如下棋、迷宫及各种游戏。 Original State Middle State Goal State 2.1 状态空间法 例:三数码难题 （3 puzzle problem） 12 3 1 23 1 23 31 2 31 2 3 12 初始棋局目标棋局 2.1 状态空间法 有向图 路径 代价 图的显示说明 图的隐示说明 2.1.2 状态图示法 AB 2.1 状态空间法 2.1.3 状态空间表示举例 产生式系统（production system） 一个总数据库：它含有与具体任
10、务有关的信息随着 应用情况的不同，这些数据库可能简单，或许复杂。 一套规则：它对数据库进行操作运算。每条规则由左 部鉴别规则的适用性或先决条件以及右部描述规则应用 时所完成的动作。 一个控制策略：它确定应该采用哪一条适用规则， 而且当数据库的终止条件满足时，就停止计算。 2.1 状态空间法 状态空间表示举例 例：猴子和香蕉问题 2.1 状态空间法 解题过程 用一个四元表列（W，x，Y，z）来表示 这个问题状态. 这个问题的操作（算符）如下： 2 goto（U）表示猴子走到水平位置U 或者用产生式规则表示为 （W，0，Y，z） goto（U） （U，0，Y，z） 2.1 状态空间法 pushbo
11、x（V）猴子把箱子推到水平位置V，即有 （W，0，W，z） pushbox（V） （V，0，V，z） climbbox猴子爬上箱顶，即有 （W，0，W，z） climbbox （W，1，W， z） 2.1 状态空间法 grasp猴子摘到香蕉，即有 （c，1，c，0） grasp （c，1，c，1） 该初始状态变换为目标状态的操作序列为 goto(b),pushbox(c),climbbox,grasp 2.1 状态空间法 (b，1，b，0) （U，0，b，0） （V，0，V，0） （c，1，c，0）（U，0，V，0） （c，1，c，1） （a，0，b，0） 目标状态 goto（U） goto（
12、U） U=b，climbbox goto（U） U=b pushbox（V） 猴子和香蕉问题的状态空间图 goto（U） U=V 2.1 状态空间法 猴子和香蕉问题自动演示： 猴子 香蕉 箱子 猴子 香蕉 箱子 Ha!Ha! 2.1 状态空间法 2.2 问题归约法 （Problem Reduction Representation） 子问题1 子问题n 原始问题 子问题集 本 原 问 题 问题归约表示的组成部分： 一个初始问题描述； 一套把问题变换为子问题的操作符； 一套本原问题描述。 问题归约的实质： 从目标(要解决的问题)出发逆向推理，建立子问 题以及子问题的子问题，直至最后把初始问题归
13、约为一个平凡的本原问题集合。 2.2 问题规约法 2.2.1 问题归约描述 （Problem Reduction Description） 梵塔难题 1 23 C B A 2.2 问题规约法 解题过程（3个圆盘问题） 123 123123 123 123123 123 123 2.2 问题规约法 多圆盘梵塔难题演示 2.2 问题规约法 2.2.2与或图表示 1.与图、或图、与或图 2.2 问题规约法 A BCD 与图 A B C 或图 2.2 问题规约法 B C D EF G A H M B C D EFG A N 2.一些关于与或图的术语 2.2 问题规约法 H M B C D EFG A
14、N 父节 点 与节 点 弧线 或节 点 子节 点 终叶节 点 3.定义 2.2 问题规约法 与或图例子 t t t t t t t t t（a）（b） 有解节点 无解节点 终叶节点 不可解节点的一般定义 没有后裔的非终叶节点为不可解节点。 全部后裔为不可解的非终叶节点且含有或 后继节点，此非终叶节点才是不可解的。 后裔至少有一个为不可解的非终叶节点且 含有与后继节点，此非终叶节点才是不可 解的。 与或图构成规则 2.2 问题规约法 梵塔问题归约图 （113） （123） （111） （113） （123） （122） （111） （333） （122） （322） （111） （122） （3
15、22） （333） （321） （331） （322） （321） （331） （333） 2.2 问题规约法 2.3 谓词逻辑法 逻辑语句 形式语言 2.3.1 谓词演算 1. 语法和语义 基本符号 谓词符号、变量符号、函数符号、 常量 符号、括号和逗号 原子公式 连词和量词(Connective &Quantifiers) 连词 与及合取（conjunction) 或及析取（disjunction） 蕴涵（Implication） 非（Not） 量词 全称量词（Universal Quantifiers) 存在量词 (Existential Quantifiers) 2.3 谓词逻辑法 2
16、.3.2 谓词公式 原子公式的的定义： 用P(x1，x2，xn)表示一个n元谓 词公式，其中P为n元谓词，x1,x2,，xn为 客体变量或变元。通常把P(x1,x2,xn)叫做 谓词演算的原子公式，或原子谓词公式。 分子谓词公式 可以用连词把原子谓词公式组成复合 谓词公式，并把它叫做分子谓词公式。 2.3 谓词逻辑法 合适公式（WFF，well-formed formulas） 合适公式的递归定义 合适公式的性质 合适公式的真值 等价（Equivalence) 2.3 谓词逻辑法 2.3.3 置换与合一 置换 概念 假元推理 全称化推理 综合推理 定义 就是在该表达式中用置换项置换变量 性质
17、可结合的 不可交换的 2.3 谓词逻辑法 合一（Unification) 合一：寻找项对变量的置换，以使两表 达式一致。 可合一：如果一个置换s作用于表达式 集Ei的每个元素，则我们用Ei s来 表示置换例的集。我们称表达式集Ei 是可合一的。 2.3 谓词逻辑法 2.4 语义网络法 （Semantic Network Representation ） 语义网络的结构 定义 组成部分 词法 结构 过程 语义 表示占有关系和其它情况 例： 小燕是一只燕子，燕子是鸟；巢-1是小燕 的巢，巢-1是巢中的一个。 选择语义基元 试图用一组基元来表示知识，以便简化 表示，并可用简单的知识来表示更复杂 的知
18、识。 2.4 语义网络法 2.4. 1 二元语义网络的表示 2.4.2 多元语义网络的表示 谓词逻辑与语义网络等效 LIMINGMAN ISA ISA（LIMING，MAN）或 MAN（LIMING） （语义网络） （谓词逻辑） 2.4 语义网络法 多元语义网络表示的实质 把多元关系转化为一组二元关系的组合， 或二元关系的合取。 R(X1，X2，Xn) R12(X1，X2)R13(X1，X3) R1n(X1，Xn) . Rn-1 n(Xn-1，Xn) 可转换为 2.4 语义网络法 2.4.3 连接词和量化的表示 合取 三元变为二元组合 析取 加注析取界限，并标记DIS，以免引起混淆 。 否定
19、两种表示方式：或标注NEG界限。 2.4 语义网络法 蕴涵 在语义网络中可用标注ANTE和CONSE界 限来表示蕴涵关系。ANTE和CONSE界限 分别用来把与先决条件(antecedent)及与 结果(consequence)相关的链联系在一起 。 量化 存在量化ISA链 全称量化分割法 2.4 语义网络法 2.5其他方法（Others) 框架（Frame）表示 框架是一种结构化表示法，通常采用语义网 络中的节点-槽-值表示结构。 剧本（Script）表示 剧本是框架的一种特殊形式，它用一组槽来 描述某些事件的发生序列。 过程（Procedure）表示 过程式表示就是将有关某一问题领域的知识
20、 ，连同如何使用这些知识的方法，均隐式地 表达为一个求解问题的过程。 2.6 小结（Summary） 本章所讨论的知识表示问题是人工智能研 究的核心问题之一。知识表示方法很多， 本章介绍了其中的7种，有图示法和公式 法，陈述式表示和过程式表示等。 方法 初始问题算符目标结果 状态 空间法 归约法 谓词 逻辑法 语义 网络法 状态 结点 合适公式 结点 算符 弧 子句集 （set of clause） 置换合一 消解反演 链 目标状态 结点 根结点 目标网络 解答路径 （path） 解答树 （tree） nil 语义网络 知识表示方法间的关系 第三章 搜索推理技术 3.6 产生式系统 3.7 系
21、统组织技术 3.8 不确定性推理 3.9 非单调推理 3.10 小结 3.1 图搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 消解原理 3.5 规则演绎系统 3.1 图搜索策略 图搜索控制策略 一种在图中寻找路径的方法。 图中每个节点对应一个状态，每条连线对应一个 操作符。这些节点和连线(即状态与操作符)又分 别由产生式系统的数据库和规则来标记。求得把 一个数据库变换为另一数据库的规则序列问题就 等价于求得图中的一条路径问题。 图搜索过程图 开始 把S放入OPEN表 OPEN表为空表？ 把第一个节点(n)从OPEN表移至CLOSED表 n为目标节点吗？ 把n的后继节点放入OPEN表的
22、 末端，提供返回节点n的指针 修改指针方向 重排OPEN表 失败 成功 图3.1 图搜索过程框图 是 是 否 否 3.1 图搜索策略 3.2 盲目搜索 特点：不需重排OPEN表 种类：宽度优先、深度优先、等代价搜索等 。 3.2.1 宽度优先搜索 v 定义 以接近起始节点的程度逐层扩展节点的搜索方 法。 v 特点： 一种高代价搜索，但若有解存在，则必能找到 它。 v 算法 开始 把S放入OPEN表 OPEN表为空表？ 把第一个节点(n)从OPEN表移至CLOSED表 是否有后继节点 为目标节点？ 扩展n，把n的后继节点放入OPEN 表的末端，提供返回节点n的指针 失败 成功 图3.2 宽度优先
23、算法框图 是 否 是 否 3.2 盲目搜索 例子 八数码难题（8-puzzle problem） 1 238 4 567 123 84 567 （目标状态）（初始状态） 规定：将牌移入空格的顺序为：从空格左边开始 顺时针旋转。不许斜向移动，也不返回先辈节点 。 从图可见，要扩展26个节点，共生成46个节点之 后才求得解（目标节点）。 3.2 盲目搜索 1 238 4 567 12 38 41 238 4 56 741 23 8 567 1 2 3 841 238 4 5 6 7 1 238 4 5 6 7 1 2 3 8 4 567 6789 10111213 1 238 45 6756756
24、7 1 1 238 4 567 1 23 84 567 1 238 4 5 6 7 1 238 4 567 2345 图3.4 八数码难题的宽度优先搜索树 1 3 4 56 1 2 38 4 5671 238 4 56 71 238 4 56 7 1 23 8 4 56 7 1 2 3 8 4 567 23 2425 26 27 1 2 3 67 8 22 12 38 4 567 1 238 4 56 7 1 23 84 567 1 2 3 8 4 5671 238 4 5 6 7 1 238 45 6 7 1 2 3 8 4 567 14 151617 18 19 20 21 1 238 4
25、 5 67 3.2 盲目搜索 3.2.2 深度优先搜索 v 定义 首先扩展最新产生的(即最深的)节点。 v 算法 防止搜索过程沿着无益的路径扩展下 去，往往给出一个节点扩展的最大深度深 度界限。 与宽度优先搜索算法最根本的不同在 于：将扩展的后继节点放在OPEN表的前端。（ 算法框图见教材） 3.2 盲目搜索 3.2.3 等代价搜索 v 定义 是宽度优先搜索的一种推广，不是沿着等长 度路径断层进行扩展，而是沿着等代价路径断层 进行扩展。 搜索树中每条连接弧线上的有关代价,表 示时间、距离等花费。 v 算法 若所有连接弧线具有相等代价，则简化 为宽度优先搜索算法。 3.2 盲目搜索 开始 把S放
26、入OPEN表 OPEN表为空表？ 把具有最小g(i)值的节点i从OPEN表移 至CLOSED表 是否有后继节点 为目标节点？ 失败 成功 图3.2 等代价搜索算法框图 是 否 是 否 令g(s)=0 S是否目标节点？ 是 成功 扩展i，计算其后继节点j的 g(j)，并把后继节点放入OPEN 表 否 3.2 盲目搜索 3.3 启发式搜索 特点：重排OPEN表，选择最有希望的节点加以扩 展 种类：有序搜索、A*算法等 3.3.1 启发式搜索策略和估价函数 v盲目搜索可能带来组合爆炸 v启发式信息 用来加速搜索过程的有关问题领域的特征信 息。 估价函数 为获得某些节点“希望”的启发信息，提 供一个评
27、定侯选扩展节点的方法，以便确定哪个 节点最有可能在通向目标的最佳路径上 。 f(n)表示节点n的估价函数值 应用节点“希望”程度（估价函数值）重排OPEN 表 3.3.2 有序搜索 v实质 选择OPEN表上具有最小f值的节点作为下一个 要扩展的节点。 3.3 启发式搜索 开始 把S放入OPEN表， 计算估价函数 f (s) OPEN表为空表？ 选取OPEN表中f值最小的节点i放入CLOSED表 i为目标节点吗？ 扩展i，得后继节点j，计算f(j)，提供返回 节点i的指针，利用f(j)对OPEN表重新排 序，调整亲子关系及指针 失败 成功 图3.9 有序搜索算法框图 是 否 是 否 3.3 启发
28、式搜索 v算法 例子 八数码难题（8-puzzle problem） 123 84 567 （目标状态） 1 238 4 5 6 7 （初始状态） 八数码难题的有序搜索树见下图： 3.3 启发式搜索 57 1 4 5 6 3 1 238 4 567 1 238 4 5 6 7 1 238 4 5 6 7 （4）（6）（6） 2 1 23 8 4 567 1 238 4 567 1 238 4 567 （6） （5）（5） 1 23 84 567 1 2 3 84 567 （5）（7） 1 238 4 56 712 38 4 567 （6） （7） 1 23 8 4 567 （5） 8 132
29、4 567 1 23 84 56 7 （5） （7） 图3.10 八数码难题 的有序搜索树 1 238 46 （4） 7 3.3 启发式搜索 3.3.3 A*算法 估价函数的定义： 对节点n定义f*(n)=g*(n)+h*(n) ,表示从S开始约 束通过节点n的一条最佳路径的代价。 希望估价函数f 定义为：f(n)=g(n)+h(n) g是g*的估计 ， h是h*的估计 A*算法的定义： 定义1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表是 依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。 定义2 在A算法中，如果对所有的x存在h(x)h*(x),则 称h(x)为h*(x)的下界，它表示某种偏于保守的估计。 定义3 采用h
