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年，第一届国际人工智能联合会议 1970年，
2、人工智能国际杂志创刊1.1 定义和发展1.1.2 人工智能的起源与发展发展期（1970年）进一步研究AI基本原理方法和技术 进行实用化研究 专家系统与知识工程 机器定理证明 智能机器人 智能控制等 从“一枝独秀”到“百花齐放”1.1 定义和发展1.2 人类智能和人工智能1.2.1 智能信息处理系统的假设 人是一种智能信息处理系统 物理符号系统的六种基本功能 物理符号系统的假设 推论一 推论二 推论三1.2.1 智能信息处理系统的假设 人类的认知行为具有不同层次 认知生理学 认知心理学 认知信息学 认知工程学1.2 人类智能和人工智能1.2.2 人类智能的计算机模拟 机器智能可以模拟人类智能 智
3、能计算机 下棋 定理证明 语言翻译 新型智能计算机 神经计算机量子计算机1.2 人类智能和人工智能 1.2.3 人工智能的研究目标 近期目标建造智能计算机代替人类的部分智力劳动 远期目标用自动机模仿人类的思维过程和智能行为1.2 人类智能和人工智能1.3 人工智能的各种认知观 符号主义（Symbolicism）基于物理符号系统假设和有限合理性原理 连接主义（Connectionism）基于神经网络及其间的连接机制与学习算法 行为主义（Actionism）基于控制论及感知动作型控制系统 1.4 人工智能的研究及应用领域 人工智能的基本技术 知识表示（Knowledge Representatio
4、n）状态空间法、问题归约法、谓词逻辑法 推理搜索（Searching&Reasoning）启发式搜索、消解原理、不确定性推理 计算智能（Computational Intelligence）模糊计算、神经计算、进化计算 构成技术（系统与语言）产生式系统、LISP语言、Prolog语言1.4.1 问题求解 问题的表示、分解、搜索、归约等 进行复杂的数学公式符号运算求解1.4.2 逻辑推理与定理证明 通过对事实数据库的操作来证明定理 多种证明方法 几何定理证明的“吴氏方法”1.4 研究及应用1.4.3 自然语言理解 语言 自然语言、人造语言、机器语言“理解”的标准1.4.4 自动程序设计 根据不同
5、目的描述来编写的计算机程序 促进人工智能系统的发展1.4 研究及应用1.4.5 专家系统 是一个智能化的计算机程序系统 和传统的计算机程序之间有本质区别1.4.6 机器学习 是机器获取智能的途径 学习是一个有特定目的的知识获取过程 学习的本质是对信息的理解与应用 有多种学习方法1.4 研究及应用1.4.7 神经网络 神经计算机 在其它领域中的广泛应用1.4.8 机器人学 操作机器人 智能机器人 机器人的广泛应用 促进人工智能的发展1.4 研究及应用1.4.9 模式识别 是计算机对环境识别的需要 是对人类环境的感知模拟1.4.10 机器视觉 人类80以上的外部信息来自视觉 低层视觉与高层视觉 前
6、沿研究领域 广泛应用1.4 研究及应用1.4.11 智能控制 驱动智能机器自主地实现其目标的过程 是一个定性和定量的混合控制过程 是当今自动控制的最高水平1.4.12 智能检索 是信息时代来临的需要 智能检索系统所面临的三大问题1.4 研究及应用1.4.13 智能调度与指挥 寻找最佳调度和组合 NP完全类问题的求解 军事指挥系统等领域1.4.14 分布式人工智能与Agent 是传统人工智能的延伸和扩展 研究目标是创建一种能描述自然系统和社会系统的精确概念模型1.4 研究及应用1.4.15 计算智能与进化计算 计算智能包括神经计算、模糊计算、进化计算等 进化计算的理论基础是生物进化论1.4.16
7、 数据挖掘与知识发现 知识获取 数据库知识挖掘 数据库中知识发现的四个特征1.4 研究及应用1.4.17 人工生命 人工生命概念的提出 理论基础与研究方法 研究内容1.4.18 系统与语言工具 计算机系统的一些概念得到发展 新的编程语言与专用开发工具1.4 研究及应用1.5 课程概要 简述人工智能的起源与发展 概括地论述知识表示的各种主要方法 讨论常用的搜索原理和推理求解技术 介绍近期人工智能技术和方法的热点 详细地分析人工智能的主要应用领域 叙述人工智能的争议与展望 第二章 知识表示方法2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法2.4 语义网络法2.5 其他方法2.6 小结2.1
8、状态空间法（State Space Representation）问题求解技术主要是两个方面：问题的表示 求解的方法 状态空间法 状态（state）算符（operator）状态空间方法2.1.1 问题状态描述 定义 状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。2.1 状态空间法2.状态空间表示概念详释例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState2.
9、1 状态空间法例:三数码难题（3 puzzle problem）123123123312312312初始棋局目标棋局2.1 状态空间法有向图路径代价图的显示说明图的隐示说明2.1.2 状态图示法AB2.1 状态空间法2.1.3 状态空间表示举例产生式系统（production system）一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2.1 状态空间法 状
10、态空间表示举例状态空间表示举例例：猴子和香蕉问题2.1 状态空间法解题过程 用一个四元表列（W，x，Y，z）来表示这个问题状态.这个问题的操作（算符）如下：2 goto（U）表示猴子走到水平位置U或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）2.1 状态空间法pushbox（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）该初始状态变换为目标状态的
11、操作序列为goto(b),pushbox(c),climbbox,grasp2.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（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉问题的状态空间图猴子和香蕉问题的状态空间图goto（U）U=V2.1 状态空间法猴子和香蕉问题自动演示：猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!2.1 状态空间法2.2 问题归约法（Problem Reduction Representa
12、tion）子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题 问题归约表示的组成部分：一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2 问题规约法2.2.1 问题归约描述（Problem Reduction Description）梵塔难题123CBA2.2 问题规约法解题过程（3个圆盘问题）1231231231231231231231232.2 问题规约法多圆盘梵塔难题演示2.2 问题规约法2.2.2与或图表示 1.与图
13、、或图、与或图2.2 问题规约法ABCD与图ABC或图2.2 问题规约法BCDEFGAHMBCDEFGAN2.一些关于与或图的术语2.2 问题规约法HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点3.定义2.2 问题规约法与或图例子与或图例子ttttttttt（a）（b）有解节点无解节点终叶节点不可解节点的一般定义没有后裔的非终叶节点为不可解节点。全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。与或图构成规则2.2 问题规约法梵塔问题归约图（113）（123）（111）（113）（12
14、3）（122）（111）（333）（122）（322）（111）（122）（322）（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.
15、3 谓词逻辑法2.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 置换与合一置换概念假元推理全称化推理综合推理定义就是在该表达式中用置换项置换变量性质可结合的不可交换的2.3 谓词逻辑
16、法合一（Unification)合一：寻找项对变量的置换，以使两表达式一致。可合一：如果一个置换s作用于表达式集Ei的每个元素，则我们用Ei s来表示置换例的集。我们称表达式集Ei是可合一的。2.3 谓词逻辑法2.4 语义网络法 （Semantic Network Representation）语义网络的结构定义组成部分词法结构过程语义表示占有关系和其它情况例：小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。选择语义基元试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。2.4 语义网络法2.4.1 二元语义网络的表示2.4.2 多元语义网络的表示谓词逻
17、辑与语义网络等效LIMINGMANISAISA（LIMING，MAN）或）或 MAN（LIMING）（语义网络）（语义网络）（谓词逻辑）（谓词逻辑）2.4 语义网络法多元语义网络表示的实质把多元关系转化为一组二元关系的组合，或二元关系的合取。R(XR(X1 1，X X2 2，X Xn n)R R1212(X(X1 1，X X2 2)R)R1313(X(X1 1，X X3 3)R R1n1n(X(X1 1，X Xn n).R Rn-1 nn-1 n(X(Xn-1n-1，X Xn n)可转换为可转换为2.4 语义网络法2.4.3 连接词和量化的表示合取三元变为二元组合析取加注析取界限，并标记DIS
18、，以免引起混淆。否定两种表示方式：或标注NEG界限。2.4 语义网络法蕴涵在语义网络中可用标注ANTE和CONSE界限来表示蕴涵关系。ANTE和CONSE界限分别用来把与先决条件(antecedent)及与结果(consequence)相关的链联系在一起。量化存在量化ISA链全称量化分割法2.4 语义网络法2.5其他方法（Others)框架（Frame）表示框架是一种结构化表示法，通常采用语义网络中的节点-槽-值表示结构。剧本（Script）表示剧本是框架的一种特殊形式，它用一组槽来描述某些事件的发生序列。过程（Procedure）表示过程式表示就是将有关某一问题领域的知识，连同如何使用这些知
19、识的方法，均隐式地表达为一个求解问题的过程。2.6 小结（Summary）本章所讨论的知识表示问题是人工智能研究的核心问题之一。知识表示方法很多，本章介绍了其中的7种，有图示法和公式法，陈述式表示和过程式表示等。方法 初始问题算符目标结果 状态 空间法 归约法 谓词逻辑法 语义网络法状态状态结点结点合适公式合适公式结点结点算符算符弧弧 子句集子句集（set of clause）置换合一置换合一消解反演消解反演链链目标状态目标状态结点结点根结点根结点目标网络目标网络解答路径解答路径 （path）解答树解答树 （tree）nil语义网络语义网络知识表示方法间的关系知识表示方法间的关系第三章 搜索推
20、理技术3.6 产生式系统3.7 系统组织技术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为目标节点
21、吗？为目标节点吗？把把n的后继节点放入的后继节点放入OPEN表的表的末端，提供返回节点末端，提供返回节点n的指针的指针修改指针方向修改指针方向重排重排OPEN表表失败失败成功成功图图3.1 图搜索过程框图图搜索过程框图是是是是否否否否3.1 图搜索策略3.2 盲目搜索 特点：不需重排OPEN表种类：宽度优先、深度优先、等代价搜索等。3.2.1 宽度优先搜索v 定义 以接近起始节点的程度逐层扩展节点的搜索方法。v 特点：一种高代价搜索，但若有解存在，则必能找到它。v 算法开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSE
22、D表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的末端，提供返回节点表的末端，提供返回节点n的指针的指针失败失败成功成功图图3.2 宽度优先算法框图宽度优先算法框图是是否否是是否否3.2 盲目搜索 例子八数码难题（8-puzzle problem）1238456712384567（目标状态）（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。3.2 盲目搜索1238456712384123845674123856
23、712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图3.4 八数码难题的宽度优先搜索树13456123845671238456712384567123845671 238456723242526271236782212384567123845671 238456712 3845671238456712384567123845671415161718192021123845673.2 盲目搜索3.2.2 深度优先搜索v 定义 首先扩展最新产生的(即最深的)节点
24、。v 算法 防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）3.2 盲目搜索3.2.3 等代价搜索v 定义 是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。v 算法 若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。3.2 盲目搜索开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失败成功图图3.2 等
25、代价搜索算法框图等代价搜索算法框图是是否否是是否否令令g(s)=0S S是否目标节点是否目标节点？是是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表否否3.2 盲目搜索3.3 启发式搜索特点：重排OPEN表，选择最有希望的节点加以扩展种类：有序搜索、A*算法等3.3.1 启发式搜索策略和估价函数v盲目搜索可能带来组合爆炸v启发式信息 用来加速搜索过程的有关问题领域的特征信息。估价函数 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)表示节点n的估价函数值 应用节点“希望”程度（估价函数值）重排OPEN
26、表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 启发式搜索v算
27、法 例子八数码难题（8-puzzle problem）12384567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：3.3 启发式搜索5714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712 384567（5）（7）1238456712384567（6）（7）12384567（5）813245671 2384567（5）（7）图3.10 八数码难题的有序搜索树123846（4）73.3 启发式搜索3.3.3 A*算法估价函数的定义：对节点n定义f f*(n)=
28、g(n)=g*(n)+h(n)+h*(n)(n),表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f 定义为：f(n)=g(n)+h(n)g是g*的估计，h是h*的估计A*算法的定义：定义定义1 1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。定义定义2 2 在A算法中，如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定义定义3 3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。3.3 启发式搜索3.4
29、消解原理回顾：原子公式（atomic formulas）文字一个原子公式及其否定。子句由文字的析取组成的合适公式。消解对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。3.4.1 子句集的求取v 步骤：共9步。v 例子:将下列谓词演算公式化为一个子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)开始：(1)消去蕴涵符号 只应用和符号，以AB替换AB。(1)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)3.4 消解原理(2)减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。(3)对变量标准化 对哑元（虚构变
30、量）改名，以保证每个量词有其自己唯一的哑元。3.4 消解原理(2)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(3)(x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w)(4)消去存在量词 以Skolem函数代替存在量词内的约束变量，然后消去存在量词(5)化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形=前缀 母式 全称量词串 无量词公式(4)(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)）P(g(x)式中，w=g(x)为一Skolem函数。(5)(x)(y)P(x)P(y)P(f(x,y
31、)Q(x,g(x)P(g(x)3.4 消解原理(6)把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。(7)消去全称量词 所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。3.4 消解原理(6)(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(7)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(8)消去连词符号 用A,B代替(AB)，消去符号。最后得到一个有限集，其中每个公式是文字的析取。(9)更换变量名称 可以更换变量符号的名称，使一个变量符号不出现在一个
32、以上的子句中。3.4 消解原理(8)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(9)P(x1)P(y)Pf(x1,y)P(x2)Qx2,g(x2)P(x3)Pg(x3)3.4.2 消解推理规则消解式的定义令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1和L2,如果L1和L2具有最一般合一，那么通过消解可以从这两个父辈子句推导出一个新子句()。这个新子句叫做消解式。v 消解式求法取各子句的析取，然后消去互补对。3.4 消解原理3.4.3 含有变量的消解式 要把消解推理规则推广到含有变量的子句，必须找到一个作用于父辈
33、子句的置换，使父辈子句含有互补文字。v 含有变量的子句之消解式v 例子Px,f(y)Q(x)Rf(a),y Pf(f(a),zR(z，w)Q f(f(a)R(f(a)，y)R(f(y)，w)=f(f(a)/x,f(y)/z3.4 消解原理3.4.4 消解反演求解过程消解反演 给出S，L 否定L，得L；把L添加到S中去；把新产生的集合L，S化成子句集；应用消解原理，力图推导出一个表示矛盾的空子句v 例子储蓄问题 前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱3.4 消解原理(1）规定原子公式：S(x,y)S(x,y)表示“x储蓄y”M(x)M(x)表示“x是钱”I(x)
34、I(x)表示“x是利息”E(xE(x，y)y)表示“x获得y”(2）用谓词公式表示前提和结论：前提：前提：(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)结论：结论：(x)I(x)(x)(y)(M(y)S(x,y)(3)化为子句形证明证明：3.4 消解原理把前提化为子句形：1)S(x,y)M(y)I(f(x)2)S(x,y)M(y)E(x,f(x)把结论化为子句形：3)I(z)4)S(a,b)5)M(b)(4)消解反演求NIL图3.12 储蓄问题反演树子句（1）子句（3）f(x)/zM(b)NIL子句（5）子句（7）子句（4）a/x,b/yS(x,y)M(y)子句子句（6）3.4
35、 消解原理反演求解过程从反演树求取答案步骤把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。用根部的子句作为一个回答语句。实质把一棵根部有NIL的反演树变换为根部带有回 答语句的一棵证明树。3.4 消解原理3.5 规则演绎系统 定义 基于规则的问题求解系统运用IfThen规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个if部分为前项，称每个then部分为后项
36、。3.5.1 规则正向演绎系统定义 正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。求解过程事实表达式的与或形变换 在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。3.5 规则演绎系统事实表达式的与或图表示Q(w,A)R(v)P(v)S(A,v)Q(w,A)R(v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(v)图3.15 一个事实表达式的与或树表示3.5 规则演绎系统与或图的F规则变换 这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型
37、限制为下列形式：L W 式中：L是单文字；W为与或形的唯一公式。3.5 规则演绎系统3.5.2 规则逆向演绎系统定义 逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。求解过程目标表达式的与或形式与或图的B规则变换作为终止条件的事实节点的一致解图3.5 规则演绎系统 正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图结构分别用正向系统的F规则和逆向系统的B规则来修正。3.5.3 规则双向演绎系统3.5 规则演绎系统3.6 产生式系统定义定义：用来描述若干个不同的以一个基本概念为基础的
38、系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。实质：实质：在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统。3.6.1 产生式系统的组成控制策略图3.22 产生式系统的主要组成总数据库产生式规则3.6 产生式系统选择规则到执行操作的步骤 1 匹配 把当前数据库与规则的条件部分相匹配。2 冲突 当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。3 操作 操作就是执行规则的操作部分。3.6 产生式系
39、统3.6.2 产生式系统的推理 正向推理：从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。逆向推理：从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。双向推理：双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。3.6 产生式系统3.7 系统组织技术3.7.1 议程表系统组织技术首先将一个大系统或复杂系统中的知识划分为一组相对独立的模块，然后考虑各子模块间在求解时的合作问题。v议程表是一个系统能够执行的任务表列。与每个任务有关的有两件事
40、，即提出该任务的理由和表示对该任务是有用的证据总权的评价。3.7.2 黑板法 黑板法由一组称为知识资源(KS)的独立模块和一块黑板组成求解系统。知识资源含有系统中专门领域的知识，而黑板则是一切KS可以访问的公用数据结构。3.7 系统组织技术3.7.3-极小搜索法 v提供了一种选择最有希望假设的技术。3.8 不确定性推理v以模糊集理论为基础的方法v以概率为基础的方法3.8.1 关于证据的不确定性 不确定性推理是研究复杂系统不完全性和不确定性的有力工具。有两种不确定性，即关于证据的不确定性和关于结论的不确定性。3.8.2 关于结论的不确定性 关于结论的不确定性也叫做规则的不确定性，它表示当规则的条
41、件被完全满足时，产生某种结论的不确定程度。3.8.3 多个规则支持同一事实时的不确定性 v基于模糊集理论的方法v基于概率论的方法3.8 不确定性推理3.9 非单调推理 定义 非单调推理用来处理那些不适合用谓词逻辑表示的知识。它能够较好地处理不完全信息、不断变化的情况以及求解复杂问题过程中生成的假设，具有较为有效的求解效率。3.9.1 缺省推理定义1：如果X不知道，那么得结论Y。定义2：如果X不能被证明，那么得结论Y。定义3：如果X不能在某个给定的时间内被证明，那么得结论Y。3.9 非单调推理3.9.2 非单调推理系统v正确性维持系统用以保持其它程序所产生的命题 之间的相容性。一旦发现某个不相容
42、，它就调出 自己的推理机制，面向从属关系的回溯，并通过 修改最小的信念集来消除不相容。3.10 小结 经典搜索推理技术图搜索技术消解反演 高级搜索推理技术规则演绎系统产生式系统系统组织技术不确定性推理非单调推理第四章第四章 计算智能计算智能(1)神经计算神经计算模糊计算模糊计算4.1 概述概述信息科学与生命科学的相互交叉、相互渗透和相互促进是现代科学技术发展的一个显著特点。计算智能涉及神经网络、模糊逻辑、进化计算和人工生命等领域，它的研究和发展正反映了当代科学技术多学科交叉与集成的重要发展趋势。什么是计算智能 把神经网络（NN）归类于人工智能（AI）可能不大合适，而归类于计算智能（CI）更能说
43、明问题实质。进化计算、人工生命和模糊逻辑系统的某些课题，也都归类于计算智能。计算智能取决于制造者（manufacturers）提供的数值数据，不依赖于知识；另一方面，人工智能应用知识精品（knowledge tidbits）。人工神经网络应当称为计算神经网络。4.1 概述计算智能与人工智能的区别和关系 输入输入人类知识人类知识()传感输入传感输入知识知识()传感数据传感数据计算计算()传感器传感器C数值的数值的A符号的符号的B生物的生物的输入输入复杂性复杂性复杂性复杂性BNNBPRBIANNAPRAICNNCPRCI4.1 概述AArtificial，表示人工的（非生物的）；BBiologic
44、al，表示物理的化学的 （？）生物的；CComputational，表示数学计算机 计算智能是一种智力方式的低层认知，它与人工智能的区别只是认知层次从中层下降至低层而已。中层系统含有知识（精品），低层系统则没有。4.1 概述当一个系统只涉及数值（低层）数据，含有模式识别部分，不应用人工智能意义上的知识，而且能够呈现出：（1）计算适应性；（2）计算容错性；（3）接近人的速度；（4）误差率与人相近，则该系统就是计算智能系统。当一个智能计算系统以非数值方式加上知识（精品）值，即成为人工智能系统。4.1 概述1960年年威德罗和霍夫率先把神经网络用于自威德罗和霍夫率先把神经网络用于自动控制研究。动控制
45、研究。60年代末期至年代末期至80年代中期年代中期，神经网络控制与，神经网络控制与整个神经网络研究一样，处于低潮。整个神经网络研究一样，处于低潮。80年代后期以来年代后期以来，随着人工神经网络研究的，随着人工神经网络研究的复苏和发展，对神经网络控制的研究也十分复苏和发展，对神经网络控制的研究也十分活跃。这方面的研究进展主要在神经网络自活跃。这方面的研究进展主要在神经网络自适应控制和模糊神经网络控制及其在机器人适应控制和模糊神经网络控制及其在机器人控制中的应用上。控制中的应用上。4.2 神经计算4.2.1 人工神经网络研究的进展人工神经网络的特性并行分布处理非线性映射通过训练进行学习适应与集成硬
46、件实现4.2 神经计算 nijijijxwfty1)()(图图4.2 神经元模型神经元模型4.2.2 人工神经网络的结构图图4.2中的神经元单元由多个输入中的神经元单元由多个输入xi，i=1,2,.,n和一个输出和一个输出y组成。中间状态由输入信号的权组成。中间状态由输入信号的权和表示，而输出为和表示，而输出为（4.1）式中，式中，j为神经为神经元元 单元的偏置，单元的偏置，wji为为 连接权系数连接权系数4.2 神经计算图图4.3 神经元中的某些变换（激发）函数神经元中的某些变换（激发）函数(a)二值函数二值函数(b)S形函数形函数 (c)双曲正切函数双曲正切函数n为输入信号数目，为输入信号
47、数目，yj为神经元输出，为神经元输出，t为为时间，时间，f(_)为输出变换函数，如图为输出变换函数，如图4.3。4.2 神经计算人工神经网络的基本特性和结构人工神经网络是具有下列特性的有向图：对于每个节点 i 存在一个状态变量xi；从节点 j 至节点 i，存在一个连接权系统数wij；对于每个节点 i，存在一个阈值 i；对于每个节点 i，定义一个变换函数fi；对于最一般的情况，此函数取 形式。)(jijijixwf 4.2 神经计算图图4.4 反馈网络反馈网络 图图4.5 前馈网络前馈网络递归（反馈）网络递归（反馈）网络:在递归网络中，多个神经在递归网络中，多个神经元互连以组织一个互连神经网络，
48、如图元互连以组织一个互连神经网络，如图5.3。前馈网络前馈网络:前馈网络具有递阶分层结构，由同前馈网络具有递阶分层结构，由同层神经元间不存在互连的层级组成，如图层神经元间不存在互连的层级组成，如图5.4。4.2 神经计算人工神经网络的主要学习算法有师学习算法：能够根据期望的和实际的网有师学习算法：能够根据期望的和实际的网络输出（对应于给定输入）间的差来调整神络输出（对应于给定输入）间的差来调整神经元间连接的强度或权。经元间连接的强度或权。无师学习算法：不需要知道期望输出。无师学习算法：不需要知道期望输出。强化学习算法：采用一个强化学习算法：采用一个“评论员评论员”来评价来评价与给定输入相对应的
49、神经网络输出的优度与给定输入相对应的神经网络输出的优度（质量因数）。强化学习算法的一个例子是（质量因数）。强化学习算法的一个例子是遗传算法（遗传算法（GA）。）。4.2 神经计算表 4.2 人工神经网络的典型模型 模型名称 有师或无师 学习规则 正向或反向传播 应用领域 AG 无 Hebb 律 反向 数据分类 SG 无 Hebb 律 反向 信息处理 ART-I 无 竞争律 反向 模式分类 DH 无 Hebb 律 反向 语音处理 CH 无 Hebb/竞争律 反向 组合优化 BAM 无 Hebb/竞争律 反向 图象处理 AM 无 Hebb 律 反向 模式存储 ABAM 无 Hebb 律 反向 信号
50、处理 CABAM 无 Hebb 律 反向 组合优化 FCM 无 Hebb 律 反向 组合优化 LM 有 Hebb 律 正向 过程监控 DR 有 Hebb 律 正向 过程预测，控制 LAM 有 Hebb 律 正向 系统控制 人工神经网络的典型模型4.2 神经计算续前表：续前表：OLAM 有 Hebb 律 正向 信号处理 FAM 有 Hebb 律 正向 知识处理 BSB 有 误差修正 正向 实时分类 Perceptron 有 误差修正 正向 线性分类，预测 Adaline/Madaline 有 误差修正 反向 分类，噪声抑制 BP 有 误差修正 反向 分类 AVQ 有 误差修正 反向 数据自组织
