湘潭大学 人工智能课件 非经典推理 pa

• 如果按推理中是否运用与问题有关的启发性知识， 推理可分为启发式推理和非启发式推理。
• （1）启发式推理：如果在推理过程中，运用与问 题有关的启发性知识，如解决问题的策略、技巧 及经验等，以加快推理过程，提高搜索效率，这 种推理过程称为启发式推理。如A、A*等算法。
• （2）非启发式推理。如果在推理过程中，不运用 启发性知识，只按照一般的控制逻辑进行推理， 这种推理过程称为非启发式推理。(推理效率较低， 容易出现“组合爆炸”问题。)
（4）将公式化为前束式，并略去全称量词,可变为
P（x，y，f（x，y）） Q（x，u）
（5）恢复为蕴含式。利用等价关系 PQ 与 PQ 将上式
变为
P（x，y，f（x，y）） Q（x，u）
Artificial Intelligence
3、目标公式的表示形式
要求目标公式用文字的析取式(子句)表示，否则就要化 为子句形式。
止节点的解图为止，当一个目标文字和与或图中的一个
文字匹配时，可以将表示该目标文字的节点(目标节点)
通过匹配连接到与或图中相应的文字节点上。当演绎产
生的与或图包括一个目标节点上结束的解图时，推理便
成功结束。
Artificial Intelligence
1)、命题逻辑的情况
• 应用规则的匹配过程比较简单。设已知事实的与 或形表达式为：（（PQ）R）（S （TU））
Artificial Intelligence
X
Y
匹配弧
XY
Z
P
Q
S
T
U
（PQ）
R
S
（TU）
（PQ）R
S （TU）
[（PQ）RA] r[Stif（icTiaUl ）In] telligence

语义网络法
❖ 二元关系：二元语义网络表示
✓ 例如： 我椅子的颜色是咖啡色的； 椅子包套是皮革； 椅子是一种家具； 座位是椅子的一部分； 椅子的所有者是X X是个人
语义网络法
PERSON
ISA X
FURNITURE ISA
CHAIR ISA PART ISA
OWNER MY CHAIR COLOR COVERING
例如：用语义网络表示“书不在桌子上”
¬Located-on
书
桌子
语义网络法
❖ 连接词和量词的表示 ✓ 否定的表示： 一般语义关系的否定：可通过引进“非”节点来表 例如： 用语义网络表示 “小王没有给小林一本书”
小王
Giver
一本书 Gift
给
Receiver
小林
非
语义网络法
❖ 连接词和量词的表示
❖ 语义网络的简单例子
例如：用于一网络表示“鸵鸟是一种鸟”
是一种
鸵鸟
鸟
❖ 语义网络的表示能力
✓ 事实的表示：
颜色
雪
白
例如：“雪的颜色是白的”
✓ 规则的表示：
例如：“规则R：如果 A 则B” A
R
B
语义网络法
❖ 语义网络的基本语义关系
✓ （1）类属关系
类属关系体现的是“具体与抽象”的概念，通常指 具有共同属性的不同事物之间的实例关系、成员关 系或分类关系。
湘潭大学 人工智能课件 知识表示方法 part3
内容提要
第二章：知识表示与推理
一、知识表示方法 二、确定性推理
内容提要
第二章：知识表示与推理 一、知识表示方法
1.状态空间法 2.问题归约法 3.谓词逻辑法 4.语义网络法

模糊推理
模糊命题 模糊知识表示 模糊匹配与冲突消解 模糊推理的基本模式 简单模糊推理
模糊命题
模糊命题
含有模糊概念、模糊数据的语句称为模糊命题。它的 一般表示形式为：
x
或者 x
is
is
A
A ( CF )
其中，A是模糊概念，用模糊集及隶属函数刻画；
x是论域上的变量，用以代表所论述对象的属性； CF是模糊命题的可信度。
模糊知识表示
模糊产生式规则的一般形式是：
IF E THEN H ( CF, λ ) 其中，E是用模糊命题表示的模糊条件；
H是用模糊命题表示的模糊结论；
CF是知识的可信度因子； λ是匹配度的阈值，用以指出知识被运用的条件。 模糊推理要解决的问题： 证据与知识的条件是否匹配
A°R = B
称为模糊变换。 例如：设A={0.2,0.5,0.3}
0.2 0.7 0.1 0 R 0 0.4 0.5 0.1 0.2 0.3 0.4 0.1
B (v) { A (u ) R(u, v)}
则：B A R {0.2,0.4,0.5,0.1}
模糊计算的过程

有如下4条规则被激活：
•
a. 若温度为高且湿度为小，则运转时间为长。
•
• •

b. 若温度为中且湿度为中，则运转时间为中。
c. 若温度为中且湿度为小，则运转时间为长。 d. 若温度为高且湿度为中，则运转时间为中。
(2) 计算模糊控制规则的强度：这一步骤属于“推理方
法”模块。采用不同的推理方法具体步骤也不相同。
模糊推理的基本模式
3. 模糊三段论推理

Artificial Intelligence (AI)
人工智能
第二章：知识 表示与推理
内容提要
第二章：知识表示与推理
二、确定性推理
1.推理的基本概念
2.搜索策略 3.自然演绎推理 4.消解演绎推理 5.基于规则的演绎推理
搜索策略
搜索策略
搜索的基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性与效率
与/或树的启发式搜索
与/或树的启发式搜索过程
(5) 如果节点n不是终止节点，但可扩展，则： ①扩展节点n，生成n的所有子节点；
②把这些子节点都放入OPEN表中，并为每一个子 节点设置指向父节点n的指针；
③计算这些子节点及其先辈节点的h值；
④转第(2)步。
与/或树的启发式搜索
与/或树的启发式搜索过程
与/或树的搜索策略
与/或树的搜索策略
与/或树的一般搜索过程 与/或树的广度优先搜索 与/或树的深度优先搜索 与/或树的启发式搜索
博弈树的启发式搜索
α-β剪枝技术
与/或树的启发式搜索
与/或树的启发式搜索
与/或树的启发式搜索过程实际上是一种利用搜 索过程所得到的启发性信息寻找最优解树的过 程。 算法的每一步都试图找到一个最有希望成为最 优解树的子树。 最优解树是指代价最小的那棵解树。 它涉及到解树的代价与希望树。
与/或树的启发式搜索
与/或树的启发式搜索过程
(4)如果节点n为终止节点，则： ①标记节点n为可解节点；
②在T上应用可解标记过程，对n的先辈节点中的所 有可解解节点进行标记；
③如果初始解节点S0能够被标记为可解节点，则T就 是最优解树，成功退出； ④否则，从OPEN表中删去具有可解先辈的所有节点。 ⑤转第(2)步。

传送时，总是选择其中代价最小的节点。也就是说， OPEN表中的节点在任一时刻都是按其代价从小到大排 序的。代价小的节点排在前面，代价大的节点排在后 面，而不管节点在代价树中处于什么位置上。 如果问题有解，代价树的广度优先搜索一定可以求得 解，并且求出的是最优解。
该算法应用的条件：该算法是针对代价树的算法。
为了采用该算法对图进行搜索，必须先将图转换为代 价树。
代价树的广度优先搜索
代价树的广度优先搜索算法流程：
• • • • (1) 把初始节点S放入OPEN表中，置S的代价g(S)=0； (2) 如果OPEN表为空，则问题无解 ，失败退出； (3) 把OPEN表的第一个节点取出放入CLOSED表，并记该节 点为n； (4) 考察节点n是否为目标。若是，则找到了问题的解，成功 退出； (5) 若节点n不可扩展，则转第(2)步；否则转第(6)步； (6)扩展节点n，为每一个子节点都配置指向父节点的指针， 计算各子节点的代价，并将各子节点放入OPEN表中。并根 据各子结点的代价对OPEN表中的全部结点按由小到大的顺 序排序。然后转第(2)步。
Artificial Intelligence (AI)
人工智能
第二章：知识 表示与推理
内容提要
第二章：知识表示与推理
二、确定性推理
1.推理的基本概念
2.搜索策略 3.自然演绎推理 4.消解演绎推理 5.基于规则的演绎推理
搜索策略
搜索策略
搜索的基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性与效率
有界深度优先搜索
八数码难题：dm=4
有界深度优先搜索
有界深度优先搜索：
问题：如果问题有解，且其路径长度≤ dm ，则 上述搜索过程一定能求得解。但是，若解的路 径长度> dm,则上述搜索过程就得不到解。这说 明在有界深度优先搜索中，深度界限的选择是 很重要的。 要恰当地给出 dm的值是比较困难的。即使能求 出解，它也不一定是最优解。

小王是个高
4
自然界中的不确定现象
随机 模糊 混沌 分形 复杂网络
5
随机性和模糊性是不确定性的基本内涵
✓随机性(偶然性)和随机数学
❖以贝叶斯公式为基础的贝叶斯理论,在人工智能中一直
是处理不确定性的重要工具
❖带可信度的不确定推理
❖证据理论
10
4.1 不确定性推理基本理论
●为什么要研究不确定性推理？ 现实世界的问题求解大部分是不良结构; 对不良结构的知识描述具有不确定性: 1) 问题证据(初始事实,中间结论)的不确定性; 2) 专门知识(规则)的不确定性.
11
什么是不确定性推理
不确定性推理是指从不确定性的初 始证据出发，通过运用不确定性 的知识，最终推理出具有一定程 度的不确定性，但又是合理或者 似乎合理的结论的思维过程。
9
思维的不确定性
思维有精确的一面，更有不 确定的一面。 人类习惯于用自然语言进行思维，思维的结果 往往是可能如何、大概如何等定性的结论。
人类还擅长通过联想的、直觉的、创造的 形象思维来思考，很少象计算机一样做精确的 数学运算或者逻辑推理，但是这并不妨碍人类 具有发达的、灵活的智能，并不妨碍人类具有 发达的、灵活的模式识别能力。
12
不确定性推理中的基本问题
在不确定性推理中,知识和证据都具有某种程度 的不确定性,这就为推理机的设计与实现增加了 复杂性和难度。除了要解决推理方向、推理方 法、控制策略等基本问题外，还需要解决以下 问题 ： ● 不确定性的表示和量度 ● 不确定性匹配 ● 不确定性的传递算法 ● 不确定性的合成
13
◆不确定性推理与通常的确定性推理的差别：
(1) 不确定性推理中规则的前件能否与证据事实匹配成功， 不但要求两者的符号模式能够匹配（合一），而且要求证据事 实所含的信度必须达“标”，即必须达到一定的限度。这个限 度一般称为“阈值”。

轴突：输出信号
突触：与另一个神经元相联系的特殊部位
神经网络
生物神经网络
神经元的基本工作机制（简化）：
一个神经元有两种状态：兴奋和抑制； 平时处于抑制状态的神经元，其树突和胞体接收其他 神经元由突触传来的兴奋电位，多个输入在神经元中 以代数和的方式叠加； 如果输入兴奋电位总量超过某个阈值，神经元会被激 发进入兴奋状态，发出输出脉冲，并由突触传递给其 他神经元。 神经元被触发后进入不应期，在不应期不能被触发， 然后阈值逐渐下降，恢复兴奋性。
进化计算：是一种对人类智能的演化模拟方法，它
是通过对生物遗传和演化过程的认识，用进化算法去 模拟人类智能的进化规律的。
模糊计算：是一种对人类智能的逻辑模拟方法，它
是通过对人类处理模糊现象的认知能力的认识，用模 糊逻辑去模拟人类的智能行为的。
神经网络
人工神经网络（ ANN）是反映人脑结构及功能的 一种抽象数学模型，是由大量神经元节点互连而 成的复杂网络，用以模拟人类进行知识的表示与 存储以及利用知识进行推理的行为。
适应与集成：自适应和信息融合能力；
硬件实现：快速和大规模处理能力。
神经网络
生物神经系统是人工神经网络的基础。人工神经网络是对人脑神经 系统的简化、抽象和模拟，具有人脑功能的许多基本特征。
1. 生物神经系统简介
2. 人工神经网络简介
神经网络
生物神经网络
神经元结构包括四个部分：
胞体：神经细胞的本体，维持细胞生存功能 树突：接收来自其他神经元的信号（输入）
简单地讲，它是一个数学模型，可以用电子线路 来实现，也可以用计算机程序来模 为： 物理结构，计算模拟，存储与操作，训练
人工神经网络的发展

40、人类法律，事物有规律，这是不 容忽视 的。— —爱献 生
46、我们若已接受最坏的，就再没有什么损失。——卡耐基 47、书到用时方恨少、事非经过不知难。——陆游 48、书籍把我们引入最美好的社会，使我们认识各个时代的伟大智者。——史美尔斯 49、熟读唐诗三百首，不会作诗也会吟。——孙洙 50、谁和我一样用功，谁就会和我一样成功。——莫扎特
湘潭大学 人工智能课件 机器学习
36、如果我们国家的法律中只有某种 神灵， 而不是 殚精竭 虑将神 灵揉进 宪法， 总体上 来说， 法律就 会更好 。—— 马克·吐 温 37、纲纪废弃之日，便是暴政兴起之 时。— —威·皮 物特
38、若是没有公众舆论的支持，法律 是丝毫 没有力 量的。 ——菲 力普斯 39、一个判例造出另一个判例，它们 迅速累 聚，进

谓词逻辑法
谓词
在n元谓词 P(x1,x2,…,xn)中，若每个个体均为常量、变 元或函数，则称它为一阶谓词。 如果某个个体本身又是一个一阶谓词，则称它为二阶 谓词，如此类推。 个体变元的取值范围称为个体域。个体域可以是有限 的，也可以是无限的。例如用I（x）表示“x是整数”， 则个体域为所有整数，是无限的。 谓词与函数不同，谓词的真值是“T”或“F”，而函 数的值是个体域中的一个个体，无真值可言。
谓词逻辑法
谓词公式
例2：用谓词逻辑描述右图中的房子的概念
个体 ：A , B 谓词 ： SUPPORT( x,y )：表示 x 被 y支撑着 WEDGE ( x )：表示 x 是楔形块 BRICK( y )：表示 y 是长方块 其中 x , y是个体变元，它们的个体域｛A,B｝ 房子的概念可以表示成一组合式谓词公式的合取式： SUPPORT(A,B) ∧WEDGE( A ) ∧BRICK( B )
谓词逻辑法
谓词
在谓词逻辑中，命题是用形如P(x1,x2,…,xn)的谓词来表 述的。一个谓词可分为谓词名与个体两个部分
个体： 是命题的主语，表示独立存在的事物或某个抽 象的概念
“x1,x2,…,xn”是个体，一般用小写字母表示
个体可以是个体常量、变元或函数
谓词名：表示个体的性质、状态或个体之间的关系
谓词逻辑法
置换与合一
置换 推理规则：用合式公式的集合产生新的合式公式
– 假元推理
W1 W1 W2
W2
– 全称化推理
(x) W(x) 任意常量A W(A)
寻找A对x的置 换，使W1(A) 与W1(x)一致
– 综合推理
W1(A) (x) [W1(x) W2(x)] W2(A)

原子谓词公式及其否定统称为文字。
例如: P(x)、Q(x)、﹁ P(x)、 ﹁ Q(x)等都是文字。
任何文字的析取式称为子句。
例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子 句。
子句集及其化简
子句和子句集 不含任何文字的子句称为空子句。
由于空子句不含有任何文字，也就不能被任何解释 所满足，因此空子句是永假的，不可满足的。 空子句一般被记为NIL。
例如：
(1)如果下雨，则地上会湿 (2)没有下雨 (3)所有，地上不湿 事实上，如果向地上洒水，地上也是会湿的。这就 是使用了否定前件的推理，违反了经典逻辑的逻辑 规则。
自然演绎推理
自然演绎推理的例子
设已知如下事实：A, B, A→C, B∧C→D, D→Q 求证：Q为真。 证明：
子句集及其化简
Step 9：消去合取词，就得到子句集。 例如：消去合取词后，上式 (﹁P(x , f(x))∨Q(x , g(x)) ∧(﹁P(y , f(y))∨﹁R(y , g(y))) 就变为下述子句集
﹁P(x , f(x))∨Q(x , g(x)) ﹁P(y , f(y))∨﹁R(y , g(y))
由子句或空子句所构成的集合称为子句集。
在子句集中，子句之间是合取关系 子句集中的变元受全称量词的约束 任何谓词公式都可通过等价关系及推理规则化为相 应的子句集
子句集及其化简
把谓词公式化成子句集的步骤
Step 1： 利用等价关系消去“→”和“↔” 反复使用如下等价公式：
– P→Q ⇔﹁ P∨Q – P↔Q ⇔ (P∧Q)∨(﹁P∧﹁Q)
空子句是不可满足的。因此，一个子句集中如果包含有 空子句，则此子句集就一定是不可满足的。