人工智能与专家系统

null人工智能与专家系统人工智能与专家系统研究生课程第一章 绪论第一章 绪论 1.1 人工智能的定义和发展 1.2 人类智能和人工智能 1.3 人工智能的各种认知观 1.4 人工智能的研究与应用领域 1.5 课程概要1.1.1 人工智能的定义1.1.1 人工智能的定义几种定义 智能机器（intelligent machine） 人工智能（学科） 人工智能（能力） 人工智能（拟人思维、行为 ） 人工智能（理性思维、行为 ）1.1 定义和发展1.1.2 人工智能的起源与发展1.1.2 人工智能的起源与发展 孕育期（1956年前） 数理逻辑学科（弗雷治、维纳等 ） 计算的新思想（丘奇、图灵 等） 形成期（1956--1970年） 1956年，第一次人工智能的研讨会 1969年，第一届国际人工智能联合会议 1970年，《人工智能》国际杂志创刊1.1 定义和发展1.1.2 人工智能的起源与发展1.1.2 人工智能的起源与发展发展期（1970年~） 进一步研究AI基本原理方法和技术 进行实用化研究 专家系统与知识工程 机器定理证明 智能机器人 智能控制等 从“一枝独秀”到“百花齐放”1.1 定义和发展1.2 人类智能和人工智能1.2 人类智能和人工智能1.2.1 智能信息处理系统的假设 人是一种智能信息处理系统 物理符号系统的六种基本功能 物理符号系统的假设 推论一 推论二 推论三1.2.1 智能信息处理系统的假设1.2.1 智能信息处理系统的假设 人类的认知行为具有不同层次 认知生理学 认知心理学 认知信息学 认知工程学1.2 人类智能和人工智能1.2.2 人类智能的计算机模拟1.2.2 人类智能的计算机模拟 机器智能可以模拟人类智能 智能计算机 下棋 定理证明 语言翻译 新型智能计算机 神经计算机 量子计算机1.2 人类智能和人工智能 1.2.3 人工智能的研究目标 1.2.3 人工智能的研究目标 近期目标 建造智能计算机代替人类的部分智力劳动 远期目标 用自动机模仿人类的思维过程和智能行为1.2 人类智能和人工智能1.3 人工智能的各种认知观1.3 人工智能的各种认知观 符号主义（Symbolicism） 基于物理符号系统假设和有限合理性原理 连接主义（Connectionism） 基于神经网络及其间的连接机制与学习算法 行为主义（Actionism） 基于控制论及感知—动作型控制系统 1.4 人工智能的研究及应用领域1.4 人工智能的研究及应用领域 人工智能的基本技术 知识 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示（Knowledge Representation） 状态空间法、问题归约法、谓词逻辑法… 推理搜索（Searching & Reasoning） 启发式搜索、消解原理、不确定性推理… 计算智能（Computational Intelligence） 模糊计算、神经计算、进化计算… 构成技术（系统与语言） 产生式系统、LISP语言、Prolog语言… 1.4.1 问题求解1.4.1 问题求解 问题的表示、分解、搜索、归约等 进行复杂的数学公式符号运算求解 1.4.2 逻辑推理与定理证明 通过对事实数据库的操作来证明定理 多种证明方法 几何定理证明的“吴氏方法” 1.4 研究及应用1.4.3 自然语言理解1.4.3 自然语言理解 语言 自然语言、人造语言、机器语言 “理解”的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 1.4.4 自动程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 根据不同目的描述来编写的计算机程序 促进人工智能系统的发展1.4 研究及应用1.4.5 专家系统1.4.5 专家系统 是一个智能化的计算机程序系统 和传统的计算机程序之间有本质区别 1.4.6 机器学习 是机器获取智能的途径 学习是一个有特定目的的知识获取过程 学习的本质是对信息的理解与应用 有多种学习方法1.4 研究及应用1.4.7 神经网络1.4.7 神经网络 神经计算机 在其它领域中的广泛应用 1.4.8 机器人学 操作机器人 智能机器人 机器人的广泛应用 促进人工智能的发展1.4 研究及应用1.4.9 模式识别1.4.9 模式识别 是计算机对环境识别的需要 是对人类环境的感知模拟 1.4.10 机器视觉 人类80％以上的外部信息来自视觉 低层视觉与高层视觉 前沿研究领域 广泛应用1.4 研究及应用1.4.11 智能控制1.4.11 智能控制 驱动智能机器自主地实现其目标的过程 是一个定性和定量的混合控制过程 是当今自动控制的最高水平 1.4.12 智能检索 是信息时代来临的需要 智能检索系统所面临的三大问题1.4 研究及应用1.4.13 智能调度与指挥1.4.13 智能调度与指挥 寻找最佳调度和组合 NP完全类问题的求解 军事指挥系统等领域 1.4.14 分布式人工智能与Agent 是传统人工智能的延伸和扩展 研究目标是创建一种能描述自然系统和社会系统的精确概念模型1.4 研究及应用1.4.15 计算智能与进化计算1.4.15 计算智能与进化计算 计算智能 包括神经计算、模糊计算、进化计算等 进化计算的理论基础是生物进化论 1.4.16 数据挖掘与知识发现 知识获取 数据库知识挖掘 数据库中知识发现的四个特征1.4 研究及应用1.4.17 人工生命1.4.17 人工生命 人工生命概念的提出 理论基础与研究方法 研究内容 1.4.18 系统与语言工具 计算机系统的一些概念得到发展 新的编程语言与专用开发工具1.4 研究及应用1.5 课程概要1.5 课程概要 简述人工智能的起源与发展 概括地论述知识表示的各种主要方法 讨论常用的搜索原理和推理求解技术 介绍近期人工智能技术和方法的热点 详细地 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 人工智能的主要应用领域 叙述人工智能的争议与展望 第二章 知识表示方法第二章 知识表示方法2.1 状态空间法 2.2 问题归约法 2.3 谓词逻辑法 2.4 语义网络法 2.5 其他方法 2.6 小结2.1状态空间法 （State Space Representation）2.1状态空间法 （State Space Representation）问题求解技术主要是两个方面： 问题的表示 求解的方法 状态空间法 状态（state） 算符（operator） 状态空间方法2.1.1 问题状态描述2.1.1 问题状态描述定义 状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合。 算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。 问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。2.1 状态空间法2. 状态空间表示概念详释2. 状态空间表示概念详释例如下棋、迷宫及各种游戏。Middle StateGoal State2.1 状态空间法例:三数码难题 （3 puzzle problem）例:三数码难题 （3 puzzle problem）初始棋局目标棋局2.1 状态空间法2.1.2 状态图示法2.1.2 状态图示法有向图 路径 代价 图的显示说明 图的隐示说明AB2.1 状态空间法2.1.3 状态空间表示举例2.1.3 状态空间表示举例产生式系统（production system） 一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。 一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。 一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2.1 状态空间法 状态空间表示举例 状态空间表示举例例：猴子和香蕉问题2.1 状态空间法解题过程解题过程 用一个四元表列（W，x，Y，z）来表示这个问题状态.这个问题的操作（算符）如下： 2 goto（U）表示猴子走到水平位置U 或者用产生式规则表示为 （W，0，Y，z） goto（U） （U，0，Y，z）2.1 状态空间法nullpushbox（V）猴子把箱子推到水平位置V，即有 （W，0，W，z） pushbox（V） （V，0，V，z）climbbox猴子爬上箱顶，即有 （W，0，W，z） climbbox （W，1，W，z）2.1 状态空间法nullgrasp猴子摘到香蕉，即有 （c，1，c，0） grasp （c，1，c，1） 该初始状态变换为目标状态的操作序列为 {goto(b),pushbox(c),climbbox,grasp}2.1 状态空间法null2.1 状态空间法猴子和香蕉问题自动演示：猴子和香蕉问题自动演示：2.1 状态空间法2.2 问题归约法 （Problem Reduction Representation）2.2 问题归约法 （Problem Reduction Representation）null 问题归约表示的组成部分： 一个初始问题描述； 一套把问题变换为子问题的操作符； 一套本原问题描述。问题归约的实质： 从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2 问题规约法2.2.1 问题归约描述 （Problem Reduction Description）2.2.1 问题归约描述 （Problem Reduction Description）梵塔难题2.2 问题规约法解题过程（3个圆盘问题）解题过程（3个圆盘问题）2.2 问题规约法多圆盘梵塔难题演示多圆盘梵塔难题演示2.2 问题规约法2.2.2与或图表示2.2.2与或图表示1.与图、或图、与或图2.2 问题规约法null2.2 问题规约法2.一些关于与或图的术语2.一些关于与或图的术语2.2 问题规约法3.定义3.定义2.2 问题规约法null不可解节点的一般定义 没有后裔的非终叶节点为不可解节点。 全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。 后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。 与或图构成规则2.2 问题规约法梵塔问题归约图梵塔问题归约图（322） （333） 2.2 问题规约法2.3 谓词逻辑法2.3 谓词逻辑法逻辑语句 形式语言2.3.1 谓词演算 1. 语法和语义 基本符号 谓词符号、变量符号、函数符号、 常量符号、括号和逗号 原子公式null连词和量词(Connective &Quantifiers) 连词 与及合取（conjunction) 或及析取（disjunction） 蕴涵（Implication） 非（Not） 量词 全称量词（Universal Quantifiers) 存在量词 (Existential Quantifiers)2.3 谓词逻辑法null2.3.2 谓词公式 原子公式的的定义： 用P(x1，x2，…，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,…，xn为客体变量或变元。通常把P(x1,x2,…,xn)叫做谓词演算的原子公式，或原子谓词公式。 分子谓词公式 可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。2.3 谓词逻辑法null合适公式（WFF，well-formed formulas） 合适公式的递归定义 合适公式的性质 合适公式的真值 等价（Equivalence)2.3 谓词逻辑法2.3.3 置换与合一2.3.3 置换与合一置换 概念 假元推理 全称化推理 综合推理 定义 就是在该表达式中用置换项置换变量 性质 可结合的 不可交换的2.3 谓词逻辑法null合一（Unification) 合一：寻找项对变量的置换，以使两表达式一致。 可合一：如果一个置换s作用于表达式集{Ei}的每个元素，则我们用{Ei} s来表示置换例的集。我们称表达式集{Ei}是可合一的。 2.3 谓词逻辑法2.4 语义网络法 （Semantic Network Representation）2.4 语义网络法 （Semantic Network Representation）语义网络的结构 定义 组成部分 词法 结构 过程 语义2.4. 1 二元语义网络的表示2.4. 1 二元语义网络的表示表示占有关系和其它情况 例： 小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。选择语义基元 试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。 2.4 语义网络法2.4.2 多元语义网络的表示2.4.2 多元语义网络的表示谓词逻辑与语义网络等效2.4 语义网络法null多元语义网络表示的实质 把多元关系转化为一组二元关系的组合，或二元关系的合取。2.4 语义网络法2.4.3 连接词和量化的表示2.4.3 连接词和量化的表示合取 三元变为二元组合 析取 加注析取界限，并标记DIS，以免引起混淆。 否定 两种表示方式：～或标注NEG界限。2.4 语义网络法null蕴涵 在语义网络中可用标注ANTE和CONSE界限来表示蕴涵关系。ANTE和CONSE界限分别用来把与先决条件(antecedent)及与结果(consequence)相关的链联系在一起。 量化 存在量化—ISA链 全称量化—分割法2.4 语义网络法2.5其他方法（Others)2.5其他方法（Others)框架（Frame）表示 框架是一种结构化表示法，通常采用语义网络中的节点-槽-值表示结构。 剧本（Script）表示 剧本是框架的一种特殊形式，它用一组槽来描述某些事件的发生序列。 过程（Procedure）表示 过程式表示就是将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐式地表达为一个求解问题的过程。2.6 小结（Summary）2.6 小结（Summary）本章所讨论的知识表示问题是人工智能研究的核心问题之一。知识表示方法很多，本章介绍了其中的7种，有图示法和公式法，陈述式表示和过程式表示等。null第三章 搜索推理技术第三章 搜索推理技术3.6 产生式系统 3.7 系统组织技术 3.8 不确定性推理 3.9 非单调推理 3.10 小结3.1 图搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 消解原理 3.5 规则演绎系统3.1 图搜索策略 3.1 图搜索策略 图搜索控制策略 一种在图中寻找路径的方法。 图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。 图搜索过程图null开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1 图搜索过程框图是是否否3.1 图搜索策略3.2 盲目搜索 3.2 盲目搜索 特点：不需重排OPEN表 种类：宽度优先、深度优先、等代价搜索等。null开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点 为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功图3.2 宽度优先算法框图是否是否3.2 盲目搜索null 例子 八数码难题（8-puzzle problem） （初始状态） 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 ：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。 从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。3.2 盲目搜索null1图3.4 八数码难题的宽度优先搜索树3.2 盲目搜索null3.2.2 深度优先搜索 定义 首先扩展最新产生的(即最深的)节点。 算法 防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度——深度界限。 与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）3.2 盲目搜索null3.2.3 等代价搜索 定义 是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。 搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。 算法 若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。3.2 盲目搜索null开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点 为目标节点？失败成功图3.2 等代价搜索算法框图是否是否令g(s)=0S是否目标节点？是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表否3.2 盲目搜索3.3 启发式搜索3.3 启发式搜索特点：重排OPEN表，选择最有希望的节点加以扩展 种类：有序搜索、A*算法等3.3.1 启发式搜索策略和估价函数盲目搜索可能带来组合爆炸 启发式信息 用来加速搜索过程的有关问题领域的特征信息。null估价函数 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上 。 f(n)——表示节点n的估价函数值 应用节点“希望”程度（估价函数值）重排OPEN表3.3.2 有序搜索实质 选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。3.3 启发式搜索null开始把S放入OPEN表，计算估价函数 f (s)OPEN表为空表？选取OPEN表中f值最小的节点i放入CLOSED表i为目标节点吗？扩展i，得后继节点j，计算f(j)，提供返回节点i的指针，利用f(j)对OPEN表重新排序，调整亲子关系及指针失败成功图3.9 有序搜索算法框图是否是否3.3 启发式搜索算法null 例子八数码难题（8-puzzle problem）八数码难题的有序搜索树见下图：3.3 启发式搜索null57145632图3.10 八数码难题的有序搜索树3.3 启发式搜索3.3.3 A*算法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*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。 3.3 启发式搜索3.4 消解原理3.4 消解原理回顾： 原子公式（atomic formulas） 文字—一个原子公式及其否定。 子句—由文字的析取组成的合适公式。 消解—对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。 例子: 例子: 将下列谓词演算公式化为一个子句集 (x)｛P(x)｛(y)［P(y)P(f(x,y))］∧ ～(y)［Q(x,y)P(y)］｝｝开始： 消去蕴涵符号 只应用∨和～符号，以～A∨B替换AB。(1) (x)｛～P(x)∨{(y)［~P(y)∨P(f(x,y))］∧～(y)［~Q(x,y)∨P(y)］}}3.4 消解原理null(2) 减少否定符号的辖域 每个否定符号～最多只用到一个谓词符号上，并反复应用狄·摩根定律。 (3) 对变量标准化 对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。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)］｝｝null(4) 消去存在量词 以Skolem函数代替存在量词内的约束变量，然后消去存在量词 化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。 前束形={前缀} {母式} 全称量词串 无量词公式(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))］∧［Q(x,g(x))∧～P(g(x))］｝｝3.4 消解原理null把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。 (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))］｝null (8) 消去连词符号∧ 用{A,B}代替(A∧B)，消去符号∧。最后得到一个有限集，其中每个公式是文字的析取。 (9) 更换变量名称 可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。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)∨P［f(x1,y)］ ～P(x2)∨Q［x2,g(x2)］ ～P(x3)∨～P［g(x3)］3.4.2 消解推理规则3.4.2 消解推理规则消解式的定义 令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1∨α和～L2∨β,如果L1和L2具有最一般合一σ，那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β)σ。这个新子句叫做消解式。 消解式求法取各子句的析取，然后消去互补对。3.4 消解原理3.4.3 含有变量的消解式3.4.3 含有变量的消解式3.4 消解原理3.4.4 消解反演求解过程3.4.4 消解反演求解过程消解反演 给出{S}，L 否定L，得～L； 把～L添加到S中去； 把新产生的集合｛～L，S｝化成子句集； 应用消解原理，力图推导出一个表示矛盾的空子句 例子—储蓄问题 前提：每个储蓄钱的人都获得利息。 结论：如果没有利息，那么就没有人去储蓄钱3.4 消解原理null(1）规定原子公式： S(x,y) 表示 “x储蓄y” M(x) 表示 “x是钱” I(x) 表示 “x是利息” E(x，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 消解原理null把前提化为子句形： 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 储蓄问题反演树3.4 消解原理null反演求解过程 从反演树求取答案步骤 把由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中去。 按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。 用根部的子句作为一个回答语句。 实质 把一棵根部有NIL的反演树变换为根部带有回 答语句的一棵证明树。3.4 消解原理3.5 规则演绎系统3.5 规则演绎系统 定义 基于规则的问题求解系统运用If→Then规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个if部分为前项，称每个then部分为后项。 3.5.1 规则正向演绎系统3.5.1 规则正向演绎系统定义 正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。 求解过程 事实表达式的与或形变换 在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。3.5 规则演绎系统null事实表达式的与或图表示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 规则演绎系统null与或图的F规则变换 这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式： L  W 式中：L是单文字；W为与或形的唯一公式。3.5 规则演绎系统3.5.2 规则逆向演绎系统3.5.2 规则逆向演绎系统定义 逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。 求解过程 目标表达式的与或形式 与或图的B规则变换 作为终止条件的事实节点的一致解图3.5 规则演绎系统3.5.3 规则双向演绎系统3.5.3 规则双向演绎系统 正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图结构分别用正向系统的F规则和逆向系统的B规则来修正。3.5 规则演绎系统3.6 产生式系统3.6 产生式系统定义：用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。 实质：在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统。3.6.1 产生式系统的组成3.6.1 产生式系统的组成控制策略图3.22 产生式系统的主要组成总数据库产生式规则3.6 产生式系统null选择规则到执行操作的步骤 1 匹配 把当前数据库与规则的条件部分相匹配。 2 冲突 当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。 3 操作 操作就是执行规则的操作部分。3.6 产生式系统3.6.2 产生式系统的推理 3.6.2 产生式系统的推理 正向推理：从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。 逆向推理：从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。 双向推理：双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。3.6 产生式系统3.7 系统组织技术3.7 系统组织技术系统组织技术首先将一个大系统或复杂系统中的知识划分为一组相对独立的模块，然后考虑各子模块间在求解时的合作问题。3.7.1 议程表议程表是一个系统能够执行的任务表列。与每个任务有关的有两件事，即提出该任务的理由和表示对该任务是有用的证据总权的评价。3.7.2 黑板法3.7.2 黑板法黑板法由一组称为知识资源(KS)的独立模块和一块黑板组成求解系统。知识资源含有系统中专门领域的知识，而黑板则是一切KS可以访问的公用数据结构。3.7 系统组织技术3.7.3 Δ-极小搜索法 提供了一种选择最有希望假设的技术。3.8 不确定性推理3.8 不确定性推理不确定性推理是研究复杂系统不完全性和不确定性的有力工具。有两种不确定性，即关于证据的不确定性和关于结论的不确定性。以模糊集理论为基础的方法 以概率为基础的方法3.8.1 关于证据的不确定性 3.8.2 关于结论的不确定性 3.8.2 关于结论的不确定性 关于结论的不确定性也叫做规则的不确定性，它表示当规则的条件被完全满足时，产生某种结论的不确定程度。3.8.3 多个规则支持同一事实时的不确定性 基于模糊集理论的方法 基于概率论的方法3.8 不确定性推理3.9 非单调推理3.9 非单调推理 定义 非单调推理用来处理那些不适合用谓词逻辑表示的知识。 它能够较好地处理不完全信息、不断变化的情况以及求解复杂问题过程中生成的假设，具有较为有效的求解效率。3.9.1 缺省推理3.9.1 缺省推理定义1：如果X不知道，那么得结论Y。 定义2：如果X不能被证明，那么得结论Y。 定义3：如果X不能在某个给定的时间内被证明，那么得结论Y。 3.9 非单调推理3.9.2 非单调推理系统 正确性维持系统用以保持其它程序所产生的命题 之间的相容性。一旦发现某个不相容，它就调出 自己的推理机制，面向从属关系的回溯，并通过 修改最小的信念集来消除不相容。3.10 小结3.10 小结 经典搜索推理技术 图搜索技术 消解反演 高级搜索推理技术 规则演绎系统 产生式系统 系统组织技术 不确定性推理 非单调推理第四章 计算智能(1)第四章 计算智能(1)神经计算 模糊计算 4.1 概述4.1 概述信息科学与生命科学的相互交叉、相互渗透和相互促进是现代科学技术发展的一个显著特点。 计算智能涉及神经网络、模糊逻辑、进化计算和人工生命等领域，它的研究和发展正反映了当代科学技术多学科交叉与集成的重要发展趋势。 什么是计算智能 什么是计算智能 把神经网络（NN）归类于人工智能（AI）可能不大合适，而归类于计算智能（CI）更能说明问题实质。进化计算、人工生命和模糊逻辑系统的某些课题，也都归类于计算智能。 计算智能取决于制造者（manufacturers）提供的数值数据，不依赖于知识；另一方面，人工智能应用知识精品（knowledge tidbits）。人工神经网络应当称为计算神经网络。 4.1 概述计算智能与人工智能的区别和关系 计算智能与人工智能的区别和关系 输入人类知识 (＋)传感输入知识 (＋)传感数据计算 (＋)传感器C－数值的A－符号的B－生物的输入复杂性复杂性BNNBPRBIANNAPRAICNNCPRCI4.1 概述nullA－Artificial，表示人工的（非生物的）；B－Biological，表示物理的＋化学的＋ （？）＝生物的； C－Computational，表示数学＋计算机 计算智能是一种智力方式的低层认知，它与人工智能的区别只是认知层次从中层下降至低层而已。中层系统含有知识（精品），低层系统则没有。4.1 概述null当一个系统只涉及数值（低层）数据，含有模式识别部分，不应用人工智能意义上的知识，而且能够呈现出： （1）计算适应性； （2）计算容错性； （3）接近人的速度； （4）误差率与人相近， 则该系统就是计算智能系统。 当一个智能计算系统以非数值方式加上知识（精品）值，即成为人工智能系统。 4.1 概述4.2 神经计算 4.2.1 人工神经网络研究的进展4.2 神经计算 4.2.1 人工神经网络研究的进展1960年威德罗和霍夫率先把神经网络用于自动控制研究。 60年代末期至80年代中期，神经网络控制与整个神经网络研究一样，处于低潮。 80年代后期以来，随着人工神经网络研究的复苏和发展，对神经网络控制的研究也十分活跃。这方面的研究进展主要在神经网络自适应控制和模糊神经网络控制及其在机器人控制中的应用上。人工神经网络的特性人工神经网络的特性并行分布处理 非线性映射 通过训练进行学习 适应与集成 硬件实现4.2 神经计算4.2.2 人工神经网络的结构4.2.2 人工神经网络的结构 图4.2 神经元模型图4.2中的神经元单元由多个输入xi，i=1,2,...,n和一个输出y组成。中间状态由输入信号的权和表示，而输出为 （4.1） 式中，j为神经元 单元的偏置，wji为 连接权系数 4.2 神经计算nulln为输入信号数目，yj为神经元输出，t为时间，f(_)为输出变换函数，如图4.3。图4.3 神经元中的某些变换（激发）函数(a) 二值函数 (b) S形函数 (c) 双曲正切函数4.2 神经计算人工神经网络的基本特性和结构人工神经网络的基本特性和结构人工神经网络是具有下列特性的有向图： 对于每个节点 i 存在一个状态变量xi ； 从节点 j 至节点 i ，存在一个连接权系统数wij； 对于每个节点 i ，存在一个阈值 i； 对于每个节点 i ，定义一个变换函数fi ；对于最一般的情况，此函数取 形式。4.2 神经计算null递归（反馈）网络:在递归网络中，多个神经元互连以组织一个互连神经网络，如图5.3。 前馈网络:前馈网络具有递阶分层结构，由同层神经元间不存在互连的层级组成，如图5.4。图4.4 反馈网络 图4.5 前馈网络4.2 神经计算人工神经网络的主要学习算法人工神经网络的主要学习算法有师学习算法：能够根据期望的和实际的网络输出（对应于给定输入）间的差来调整神经元间连接的强度或权。 无师学习算法：不需要知道期望输出。 强化学习算法：采用一个“评论员”来评价与给定输入相对应的神经网络输出的优度（质量因数）。强化学习算法的一个例子是遗传算法（GA）。4.2 神经计算人工神经网络的典型模型人工神经网络的典型模型4.2 神经计算null续前表：4.2 神经计算4.2.4 基于神经网络的知识表示与推理 4.2.4 基于神经网络的知识表示与推理 基于神经网络的知识表示 在这里，知识并不像在产生式系统中那样独立地表示为每一条规则，而是将某一问题的若干知识在同一网络中表示。例如，在有些神经网络系统中，知识是用神经网络所对应的有向权图的邻接矩阵及阈值向量表示的。 4.2 神经计算基于神经网络的推理 基于神经网络的推理 基于神经网络的推理是通过网络计算实现的。把用户提供的初始证据用作网络的输入，通过网络计算最终得到输出结果。 一般来说，正向网络推理的步骤如下： 把已知数据输入网络输入层的各个节点。 利用特性函数分别计算网络中各层的输出。 用阈值函数对输出层的输出进行判定，从而得到输出结果。4.2 神经计算4.3 模糊计算 4.3.1 模糊集合、模糊逻辑及其运算4.3 模糊计算 4.3.1 模糊集合、模糊逻辑及其运算定义4.1 模糊集合(Fuzzy Sets)论域U到[0,1]区间的任一映射 ， 即 ，都确定U的一个模糊子集F； 称为F的隶属函数或隶属度。在论域U中，可把模糊子集表示为元素u与其隶属函数 的序偶集合，记为： (4.7)定义4.2 模糊支集、交叉点及模糊单点定义4.2 模糊支集、交叉点及模糊单点若模糊集是论域U中所有满足 的元素u构成的集合，则称该集合为模糊集F的支集。 当u满足 ，称为交叉点。 当模糊支集为U中一个单独点，且u满足 则称模糊集为模糊单点。4.3 模糊计算定义4.3 模糊集的运算定义4.3 模糊集的运算设A和B为论域U中的两个模糊集，其隶属函数分别为 和 ，则对于所有 ，存在下列运算： A与B的并（逻辑或）记为 ，其隶属函数定义为： (4.10) A与B的交（逻辑与）记为 ，其隶属函数定义为： (4.11) A的补（逻辑非）记为 ，其传递函数定义为： (4.12)4.3 模糊计算null定义4.4 直积（笛卡儿乘积，代数积） 若 分别为论域 中的模糊集合，则这些集合的直积是乘积空间 中一个模糊集合，其隶属函数为： (4.13)定义4.5 模糊关系 若U，V是两个非空模糊集合，则其直积U×V中的模糊子集R称为从U到V的模糊关系，表示为： (4.14)4.3 模糊计算定义4.6 复合关系定义4.6 复合关系 若R和S分别为U×V和V×W中的模糊关系，则R和S的复合是一个从U到W的模糊关系，记为： (4.15)其隶属函数为： (4.16)式(4.9)中的 * 号可为三角范式内的任意一种算子，包括模糊交、代数积、有界积和直积等。4.3 模糊计算定义4.7 正态模糊集、凸模糊集和模糊数定义4.7 正态模糊集、凸模糊集和模糊数 以实数R为论域的模糊集F，若其隶属函数满足 则F为正态模糊集；若对于任意实数x，a