AI复习.md

## 第一章 绪论
- 人工智能的概念理解
- 人工智能的一般解释：人工智能就是用人工的方法在机器（计算机）上实现的智能，或称机器智能、计算 机智能（没有严格统一的定义）
- 人工智能特征：
1. 由人类设计，为人类服务，本质为计算， 基础为数据
2. 能感知环境，能产生反应，能与人交互， 能与人互补
3. 有适应特性，有学习能力，有演化迭代， 有连接扩展
- 人工智能发展历史
- 达特茅斯会议（1956）
- 曲折发展过程
- 三大学派（主要特征，争议）
- 符号主义
- 又称：逻辑主义、心理学派或计算机学派
- 原理：物理符号系统(即符号操作系统)假设和有限合理性原理
- 起源：源于数理逻辑/逻辑推理
- 学派代表：纽厄尔、西蒙和尼尔逊等
- 主要特征和缺点：
- 连接主义
- 又称：仿生学派或生理学派
- 原理：神经网络及神经网络间的连接机制与学习算法
- 起源：源于仿生学，特别是人脑模型的研究
- 神经网络和神经网络间的连接机制和学习算法能够产生智能
- 学派代表：麦克洛奇、皮茨、霍普菲尔德、鲁梅尔哈特等
- 主要特征和缺点：
- 行为主义
- 又称：进化主义或控制论学派
- 原理：控制论及感知-动作型控制系统
- 起源：源于控制论
- 学派代表作：布鲁克斯的六足行走机器人，一个基于感知-动作模式的模拟昆虫行为的控制系统
- 基本观点可以概括为：
- 争论...........
- 符号主义：
- 认为人的认知基元是符号，认知过程即符号操作过程
- 认为人是一个物理符号系统，计算机也是一个物理符号系统，因此能够用计算机来模拟人的智能行为
- 人工智能的核心问题是知识表示、知识推理和知识运用
- 连接主义
- 认为思维基元是神经元，而不是符号处理过程
- 认为人脑不同于电脑，并提出连接主义的大脑工作模式，用于取代符号操作的电脑工作模式
- 行为主义
- 认为智能取决于感知和行动（所以被称为行为主义），提出智能行为的“感知-动作”模式
- 认为智能不需要知识、不需要表示、不需要推理；人工智能可以像人类智能一样逐步进化（所以称为进化主义0）；智能行为只能在现实世界中与周围环境交互作用而表现出来
## 第二章 搜索技术
### 问题描述
- 状态空间表示法
- 问题归约表示法
- 谓词逻辑表示法
- 其他
### 问题求解
#### 导入：搜索技术
##### 1、什么是搜索？
**根据问题的实际情况不断寻找可利用的知识,构造 出一条代价较少的推理路线,使问题得到圆满解决 的过程称为搜索**
- 找到从初始事实到问题最终答案的一条推理路径
- 找到的这条路径在时间和空间上复杂度最小
##### 2、搜索方法标准
搜索方法好的标准, 一般认为有两个：搜索空间小、解最佳
##### 3、图搜索策略（状态空间搜索）
图搜索策略是一种在图中寻找路径的方法，图中每个节点对应一个状态，每条连线对应一个操作符
搜索过程的要点如下：
- 起始节点：对应于初始状态描述
- 后继节点：把适用于某个节点状态描述的一些算符用来推算该节点而得到的新节点，称为该节点的后继节点
- 指针：从每个后继节点返回指向其父辈节点

##### 4、状态空间搜索的基本思想
先把问题的初始状态作为当前扩展节点对 其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现， 则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程 ，直到目标状态出现在子节点中或者没有可供操作的节点为止。所谓对一个节点进行“扩展 ”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。
> 注：算法结束后，将生成一个图G，称为**搜索图**。同时由于每个节点都有一个指针指向父节点，这些指针指向的节点构成G 的一个支撑树，称为**搜索树**。从目标节点开始，将指针指向的状态回串起来，即找到一条**解路径**
搜索过程扩展后继节点的次序：
- 如果搜索是以接近起始节点的程度(由节点之间连结弧线的数目来衡量)依次扩展节点,称为**广(宽)度优先搜索**
- 如果搜索时首先扩展最新产生的节点，称为**深度优先搜索**
通用的搜索过程完整概括为（如下图）：
1. 把初始节点S0放入OPEN表,并建立目前只包含S0的图，记为G
2. 检查OPEN表是否为空,若为空则问题无解，退出
3. 把OPEN表的第一个节点取出放入CLOSED表，记该节点为n
4. 考察n是否为目标节点，如是则问题得解，退出
5. 扩展节点n，生成一组子节点，其中不是节点n先辈的节点记作集合M，并把这些子节点作为n的子节点加入G中
6. 针对M中子节点的不同情况，分别进行处理：
1. 对于那些未曾在G中出现过的M成员设置一个指向父节点(即n)的指针，并把它们放入OPEN表
2. 对于那些先前已在G中出现过的M成员，确定是否需要修改它指向父节点的指针
3. 对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针
7. 按某种搜索策略对OPEN表中的节点进行排序
8. 转第2步

不同搜索方法的主要不同在于第7步中对OPEN表中的节点进行排序的方法，下面介绍两类状态空间搜索的方法：盲目搜索与启发式搜索
---
#### 盲目搜索
##### 1、概念
没有启发信息的一种搜索形式（按预定的控制策略搜索，在搜索过程中获得的中间信息不用来改进控制策略）
- 适用场景：一般只适用于求解比较简单的问题
- 特点：不需重排OPEN表
- 种类：
- 按照事先规定的路线进行搜索：宽度（广度）优先、深度优先
- 按已经付出的代价决定下一步要搜索的节点：代价树的宽度搜索、代价树的深度搜索

##### 2、固定规则搜索
###### 宽度优先搜索策略
- 定义：如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索 (breadth-first search)
- 特点：这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点
- 宽度优先搜索策略框图：

- 宽度搜索案例：

###### 深度优先搜索策略
- 定义：首先扩展最新产生的（即最深的）节点的搜索策略，即为深度优先搜索(depth-first search)，其中深度相等的节点可以任意排列
- 特点：
- 首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的首先路径从起始节点向下进行下去
- 仅当搜索到达一个没有后裔的状态时，才考虑另一条替代的路径
- 节点深度：
- 定义：
- 起始节点的深度为0
- 任何其他节点的深度等于其父辈节点的深度加1
- 与宽度优先搜索算法最根本的不同：将扩展的后继节点放在OPEN表的前端。
- 算法具体过程：
1. 把起始节点S放到未扩展节点 OPEN表中。如果此节点为目标节点，则得到一个解
2. 如果OPEN为一空表，则失败退出
3. 把第一个节点（节点 n）从OPEN表移到CLOSED表
4. 如果节点n的深度等于最大深度，则转向2
5. 扩展节点n，产生其全部后裔，并把它们放入OPEN 表 的前端，如果没有后裔，则转向2
6. 如果后继节点中有任一个为目标节点，则求得一个解，成功退出，否则转向2
- 性质：
- 一般不能保证找到最优解
- 当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制
- 最坏情况时，搜索空间等同于穷举
- 改进：有界深度优先搜索
- 背景：为了防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展最大深度——深度界限。任何节 点如果达到了深度界限，那么都将把它们作为没有后继节点来处理。
- 基本思想： 对深度优先搜索引入搜索深度的界限（设为dm），当搜索深度达到了深度界限，而仍未出现目标节点时，就换一个分支进行搜索。
- 局限性：如果问题有解，且其路径长度≤dm，则上述搜索过 程一定能求得解。但是，若解的路径长度>dm,则上述搜索过程就得不到解。这说明在有界深度优先搜索中，深度界限的选择是很重要的。要恰当地给出dm的值是比较困难的。即使能求出解，它也不一定是最优解。
##### 3、等代价搜索
- 概念：等代价搜索，宽度（广度）优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展，其中搜索树中每条连接弧线上的有关代价，表示时间、距离等花费
- 符号表示：
- 起始节点记为 S
- 从节点i到它的后继节点j的连接弧线代价记为c(i,j)
- 从起始节点S到任一节点i的路径代价记为g(i)
- 算法流程：
1. 把起始节点S放到未扩展节点表OPEN中。如果此起始节点为 一目标节点，则求得一个解，否则令g(S)=0
2. 如果OPEN是个空表，则没有解而失败退出
3. 从OPEN表中选择一个节点i，使其g(i)为最小。如果有几个节点都合格，那么就要选一个目标节点作为节点i(要是有目标节点的话)，否则就从中选一个作为节点i，把节点i从OPEN表移至扩展节点表CLOSED中
4. 如果节点 i为目标节点，则求得一个解
5. 扩展节点i，如果没有后继节点，则转向第2步
6. 对于节点i的每个后继节点j，计算 g(j)=g(i)+c(i,j)，并把所有后继节点j放进OPEN表，提供回到节点i的指针
7. 转向第2步

###### 代价树的广度搜索
- 基本思想：每次从OPEN表中选择节点往CLOSED表传送时，总是选择其中代价最小的节点。也就是说，OPEN表中的节点在任一时刻都是按其代价从小到大排序的。代价小的节点排在前面，代价大的节点排在后面
- 特点：如果问题有解，代价树的广度优先搜索一定可以求得解，并且求出的是最优解
- 算法流程：
1. 把初始节点S0放入OPEN表，令g(S0)=0
2. 如果OPEN表为空，则问题无解，退出
3. 把OPEN表的第一个节点（记为节点n）取出放入CLOSED表
4. 考察节点n是否为目标节点。若是，则求得了问题的解，退出
5. 若节点n不可扩展，则转第2步
6. 扩展节点n，为每一个子节点都配置指向父节点的指针，计算各子节点的代价，并将各子节点放入OPEN 表中。按各节点的代价对OPEN表中的全部节点进行排序(按从小到大的顺序)，然后转第2步。
###### 代价树的深度搜索
- 算法流程：
1. 把初始节点S0放入OPEN表，令g(S0)=0
2. 如果OPEN表为空，则问题无解，退出
3. 把OPEN表的第一个节点（记为节点n）取出放入CLOSED表
4. 考察节点n是否为目标节点。若是，则求得了问题的解，退出
5. 若节点n不可扩展，则转第2步
6. 扩展节点n，将其子节点按代价从小到大的顺序放到OPEN表中的前端，并为每一个子节点都配置指向父节点的指针，然后转第2步
> 在**代价树的宽度优先搜索**中，每次都是从OPEN表的全体节点中选择一个代价最小的节点送入CLOSED表进行观察，而**代价树的深度优先搜索**是从刚扩展出的子节点中选一个代价最小的节点送入CLOSED表进行观察。
>
> 一般情况下这两种方法中得到的结果不一定相同。
---
#### 启发式搜索
##### 1、概念
- 背景：宽度优先、深度优先、等代价搜索等算法，其主要的差别是**OPEN表中待扩展节点的顺序问题**。人们试图找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，使搜索效率将会大为提高。
- 为什么需要启发式搜索？—— 盲目搜索的不足
- 效率低，耗费过多的计算空间与时间
- 可能带来组合爆炸
- 启发信息：进行搜索技术一般需要某些**有关具体问题的领域的特性信息**，此种信息叫做**启发信息**
- 启发式搜索：
- 特点：重排OPEN表，选择最有希望的节点加以扩展
- 种类：有序搜索、A*算法等
- 估价函数：
- 定义：估价函数 （evaluation function )，估算节点希望程度的量度
- 表示方法：f(n) — 表示节点n的估价函数值
- 建立估价函数的一般方法：
- 提出任意节点与目标集之间的距离量度或差别量度
- 在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数（这些特点被认为与向目标节点前进一步的希望程度有关）
##### 2、有序搜索
有序搜索(ordered search)，即最好优先搜索(best-first search)，选择OPEN表上f值最小的节点作为下个要扩展的节点
- 算法流程：
1. 把起始节点S放在OPEN表中，计算f(s)并把其值与节点S联系起来
2. 如果OPEN是个空表，则失败退出，无解
3. 从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i
4. 把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中
5. 如果i是个目标节点，则成功退出，求得一个解
6. 扩展节点i，生成其全部后继节点，对于i的每一个后继节点j：
1. 计算f(j)
2. 如果j既不在OPEN表中，又不在CLOSED表中，则用估价函数f把它添入OPEN表，从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一 个解答路径
3. 如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计 算过的该节点在表中的f值。如果新的f值较小，则：
1. 以此新值取代旧值
2. 从j指向i，而不是指向它的父辈节点
3. 如果节点j在CLOSED表中，则把它移回OPEN表
- 有序搜索算法框图：

- 案例：



##### 3、A*算法
- 特点：隶属于有序搜索算法的一种，其特点在于对估价函数的定义上
- 算法符号：k(ni , nj)
- 表示任意两个节点ni和nj之间最小代价路径的实际代价
- 对于两节点间没有通路的节点，函数k没有定义
- 从节点n到某个具体的目标节点ti，某一条最小代价路径的代价可由k(n, ti)给出
- h\*(n)表示整个目标节点集合{ti}上所有 k(n,ti)中最小的一个，它对于任何不能到达目标节点的节点n没有定义
- h\*(n)就是从n到目标节点最小代价路径的代价，而且从n到目标节点能够获得到该最小代价的任一路径就是一条从n到某个目标节点的最佳路径
- 估价函数的设计：
- g*(n)=k(S,n)
- f\*(n)=g\*(n)+h\*(n)
- f(n)=g(n)+h(n)（希望估价函数f是f\*的一个估计，同理，g是g\*的估计, h是h\*的估计）
> h*(n)的估计h(n)依赖于有关问题的领域的启发信息，h叫做**启发函数**
>
> 对于g(n)来说，一个明显的选择就是搜索树中从S到n这段路径的代价，这一代价可以由从n到S寻找指针时，把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)，这个定义包含了g(n)≥g*(n)
- 算法设计：
- 定义1：在图搜索过程中，如果第8步的重排OPEN表是依据f(n)=g(n)+h(n)进行的，则称该过程为A算法
- 定义2：在A算法中，如果对所有的n存在h(n)≤h\*(n)，则称h(n)为h\*(n)的下界，它表示某种偏于保守的估计
- 定义3：采用h\*(n)的下界h(n)为启发函数的A算法，称为A\*算法
> 如果算法有解， A*算法一定能够找到最优的解答。
- A*算法流程：


> **启发式搜索小结**
>
> 启发式策略就是利用与问题有关的启发信息进行搜索 的策略。
>
> 利用估价函数来估计待搜索节点的希望程度，并以此排序。估价函数一般由两部分组成：f(n)=g(n)+h(n)
>
> - g(n)是从初始节点到节点 n已付出的实际代价
> - h(n) 是从节点n到目的节点的最佳路径的估计代价，h(n)体现了搜索的启发信息。
>
> 在f(n)中，g(n)的比重越大，越倾向于宽度优先搜索， 而h(n)的比重越大，**表示启发性越强**
>
> g(n)的作用一般是不可忽略的，保持g(n)项就保持了搜索的宽度优先成分，有利于搜索的完备性，但会影响搜索的效率
#### 与/或图搜索
之前介绍的几种方法都是状态空间表示法对应的问题求解方法，下面介绍问题归约表示法下的求解方法
前者试图寻找最优路径，而后者试图判断当前问题是否有解

##### 与或树宽度优先搜索

###### 关键步骤
扩展节点n，生成其全部后继节点，送到OPEN表末端，并设置指向n的指针。

###### 算法结束的条件
- 若初始节点被标示为可解节点，算法成功结束（有解）
- 若初始节点被标示为不可解结点，则搜索失败结束（无解）
###### 算法流程

###### 算法案例

解答过程：






##### 与或树深度优先搜索

###### 特殊之处

与宽度优先算法相比，深度优先算法的特殊之处：
- 第4步要判断从open表取出来的节点的深度。如果等于深度界限，认定它为不可解节点
- 第5步将扩展出来的节点放到open的前端，即open是堆栈
###### 算法流程

###### 算法案例

**解答过程：**






对比：

---
#### 博弈搜索
##### 1、概述
博弈搜索是与或树搜索搜索的一种，体现了启发式搜索的特点
- 特征：智力竞技（这里主要是双方博弈）
- 目标：取胜（类似状态空间法里的目标，但涉及多个主体）
- 方法：Max-Min搜索、α-β剪枝
- 博弈的问题表示：博弈树表示
- 一种特殊的与或树
- 节点：博弈的格局（即棋局），相当于状态空间中的状态， 反映了博弈的信息，并且与节点或隔层交替出现
- 描述博弈过程的与或树为博弈树，特点为：
- 博弈的初始格局是初始节点
- 博弈树中，或节点与与节点逐层交替出现，自己一方扩展节点是“或”关系，对方扩展节点是“与” 关系
- 所有能使自己一方获胜的终局是本原问题，相应节点为可解节点，所有使对方获胜的都是不可解节点
##### 2、Max-Min搜索
根据问题的特征来定义一个估价函数，用来估算当前博弈树端节点的得分，当计算出端节点的估值后，再推算出父节点的得分（即计算倒推值），对或节点，选其子节点中一个最大得分作为父节点的得分；对与节点，选其子节点中一个最小得分作为父节点的得分。如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案
###### 算法流程

1. 生成k-步博弈树：Max代表机器一方/Min代表敌方，设Max面对的当前棋局为c(o)，以c(o)为根，生成k-步博弈树：

2. 评估棋局(博弈状态)：为特定的博弈问题定义一个估价函数est(c)，用以评估k-步博弈树叶节点对应的棋局c，est(c)值越大，意味着棋局c对Max越有利

3. 回溯评估：由叶节点向根节点方向回溯评估，在Max处取最大评估值(或运算)，在Min处取最小评估值(与运算)

4. 递归循环
- Max 行棋后，等待 Min 行棋
- Min 行棋后，即产生对于 Max 而言新的当前棋局 c(o)
- 返回 Step1，开始下一轮博弈
###### 算法案例

需要说明的是，**等价的 (如具有对称性的) 棋局被视为相同棋局**
定义估价函数：est(c)
- 对于非终局的博弈状态c，估价函数为：est(c)=(所有空格都放上黑色棋子之后3颗黑色棋子连成的直线总数) - (所有空格都放上白色棋子之后3颗白色棋子连成的直线总数)
- 若 c 是 Max 的胜局，则est(c) = +∞
- 若 c 是 Min 的胜局，则est(c) = -∞
---
##### 3、α-β剪枝
上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了α-β剪枝技术。α-β剪枝技术的基本思想，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必 要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率
###### 背景
实际上，就博弈而言，人类棋手的思维模式更多地表现出深度优先的特征，而不是宽度优先。因此，采用深度优先搜索策略进行k-步博弈搜索，更符合AI模拟人类智能的原则，其中k是深度优先搜索的一个自然的深度界限。深度优先搜索策略产生的k-步博弈树是可以剪枝的，因此，搜索空间较小。重要的是，这正是人类棋手约束搜索空间的特征。
###### α值与β值
- 对于一个与节点来说，它取当前子节点中的最小倒推值作为它倒推值的上界，称此为β值（β <= 最小值）
- 对于一个或节点来说，它取当前子节点中的最大倒推值作为它倒推值的下界，称此为α值（α >= 最大值）
###### α-β算法剪枝规则
- 规则一 (α剪枝规则)：任何与节点x的β值如果不能升高其父节点的α值，则对节点x以下的分支可停止搜索，并使x的倒推值为β
- 规则二 (β剪枝规则)：任何或节点x的α值如果不能降低其父节点的β值，则对节点x以下的分支可停止搜索，并使x的倒推值为α
- 由规则一形成的剪枝被称为 “α剪枝”，而由规则二形成的剪枝被称为 “β剪枝”
###### 算法案例

---
## 第三章 确定性推理
### 谓词逻辑表示法
#### 命题逻辑表示法
##### 命题与命题逻辑
命题是陈述客观外界发生事情的陈述句，是或为真或为假的陈述句。逻辑主要研究推理过程，而推理过程必须依靠命题来表达。在命题逻辑中，“命题”被看作最小单位，是数理逻辑中最基本、最简单的部分。
##### 命题的抽象
以p、q、r等表示命题，以1表示真，0表示假，命题就抽象为取值为0或1的p等符号
- 作为命题的陈述句所表达的判断结果称为命题的**真值**。真值只有真和假两种，通常记为1和0（T和F）
- 真值为真的命题称为**真命题**，真值为假的命题称为**假命题**
- 诸如“没有”、“如果··· 那么···”等连词称为**联结词**
- 由联结词和命题连接而成的更加复杂命题称为**复合命题**，不能分解为更简单命题的命题称为**简单命题**
- 简单命题和复合命题的划分是**相对的**
##### 命题联结词
一些符号化的联结词表示如下
- 否定联结词：¬，“非p”称为p的否定式，记为¬p
- 合取联结词：∧，“p而且q”称为p、q的合取式，记为p∧q
- 析取联结词：∨，“p或者q”称为p、q的析取式，记为p∨q
- 蕴涵联结词：→，“如果p，则q”称为p对q的蕴涵式，记作p→q，当且仅当p真而q假时p→q为假
- 等价联结词：↔，“p当且仅当q”称作p、q的等价式，记作p↔q，当且仅当p、q真值相同时p↔q为真
五个联结词约定的结合力强弱顺序： ¬， ∧， ∨， →， ↔，且连接词相同时，从左至右运算
> **“相容或”与“相异或”**
>
> 日常语言中“或”有两种标准用法，如：
>
> - 张三或者李四考了90分
> - 第一节课上数学课或者上英语课
>
> 当构成它们的简单命题都真时，前者为真，后者却为假，此时前者称为“相容或”，后者称为“相异或”
>
> 前者(“相容或”)可表示为p∨q，后者却不能，所以不要见了或就表示为p∨q
##### 命题公式及其解释
- 原子公式：单个命题变元、单个命题常元称为原子公式。
- 命题公式：由如下规则生成的公式称为命题公式——
1. 单个原子公式是命题公式
2. 若A和B是命题公式，则¬A, A∧B, A∨B , A→B , A↔B都是命题公式
3. 所有命题公式都是有限次应用1、2得到的符号串
- 命题公式的解释：给命题公式中每个命题变元指定一个真假值，这一组真假值，就是命题公式的一个解释，用I表示
- 如果公式在所有的解释I下，其值都为T，则称公式G为恒真的；如果其值都为F，则称公式G为恒假的（不可满足的）
- 如果将公式的所有解释及其对应真值列成表，就是G的**真值表**
---
#### **谓词逻辑表示法**
##### 知识背景
命题逻辑虽能够把客观世界的各种实事表示为逻辑命题，但具有很大局限性，即**不适合表达比较复杂的问题**；而谓词逻辑则**允许我们表达那些无法用命题逻辑表达的事情**。谓词逻辑法采用**谓词合式公式和一阶谓词演算**把要解决的问题变为一个有待证明的问题，然后采用**消解原理和消解反演**来证明一个新语句是从已知的正确语句导出的，从而证明新语句也是正确的。
##### 基本概念
- 谓词是用于刻画个体的性质、状态和个体之间关系的语言成分，因此可以用谓词来表示命题，用P(x1,x2,…xn)表示一个**n元谓词公式**，其中P为**n元谓词** ，xi为**客体变量或变元**。通常把P(x1,x2,…,xn)叫做**谓词演算的原子公式**

- 个体变元的取值范围称为它的**论域（个体域）**
- 谓词逻辑的基本组成部分是基本符号，包含谓词符号、变量符号、函数符号、 常量符号，并用括号（圆、方、花）和逗号隔开表示论域内的关系
- 原子公式由**谓词符号**和**项**组成的谓词演算，是谓词演算基本积木块

- **原子谓词公式**：用P(x1,x2,…xn)表示一个**n元谓词公式**，其中P为**n元谓词**，xi为**客体变量或变元**。通常把P(x1,x2,…,xn)叫做**谓词演算的原子公式**
- **分子谓词公式**：可以用连词把原子谓词公式组成复合谓词公式，并把它叫做**分子谓词公式**
> 这么叫的很少，感觉还是**合式公式**这个称呼更常见
##### 谓词逻辑的语法元素
在`命题逻辑`中，每个表达式**都是句子**，表示事实；在`谓词逻辑`中**也有句子，但是也有项**，表示对象。常量符号、变量和函数符号用于表示**项** ，量词和谓词符号用于构造**句子** 。谓词逻辑的语法元素表示如下：
- 个体符号或常量：A、B、张三、李四等等，通常是对象的名称
- 变量符号：习惯上用小写字母表示，如x、y、z等
- 函数符号：习惯上用小写英文字母或小写英文字母串表示，如plus、f、g
- 谓词符号：习惯上用大写英文字母或（首字母）大写英文字母串表示
- 连接词：谓词逻辑中所使用的连接词和命题逻辑中所使用的连接词一样
- 与合取（Conjunction，∧），其中的合取项是合取式的每个组成部分，如LIKE(I, MUSIC)∧LIKE(I, PAINTING)
- 或析取（Disjunction，∨），析取项是析取式的每个组成部分
- 蕴涵（Implication，⇒），表示“如果...，那么...”的语句
- 非（Not，~，有时也用¬），表示否定的语句
- 等价（Equivalence，⇔），表示两个组成部分等价的语句
- 量词：量词可以量化公式中的某个变量，分为全称量词和存在量词
- 全称量词（Universal Quantifiers，∀）
- 存在量词（Existential Quantifiers，∃）
> - 如果一个合式公式中某个变量是经过量化的，就把这个变量叫做**约束变量**，否则称其为**自由变量**
> - 一阶谓词演算不允许对谓词符号或函数符号进行量化（注：一元谓词是表示性质的谓词的符号化）
> - 多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原来的含义
##### 合式公式
合式公式 (WFF, well-formed formulas)
- 递归定义：
1. 原子谓词公式是合式公式
2. 若A为合式公式，则~A也是一个合式公式
3. 若A和B都是合式公式, 则(A ∧ B)、(A ∨ B)、(A ⇒ B)、(A ⇔ B)也都是合式公式
4. 若A是合式公式，x为A中的自由变元，则(∀x) A、(∃x) A都是合式公式
5. 只有按上述1至4规则求得的那些公式，才是合式公式
> 在合式公式中连词优先级从高到低依次为：~ ∧ ∨ ⇒ ⇔，但可通过括号改变优先级
- 等价定义：如果两个合式公式，无论如何解释，其真值表都是相同的，那么就称两合式公式是等价的
- 谓词公式案例：


- **全总个体域**：我们设想有一个集合，它包括谓词中各个变元的所有个体域，我们称它为**全总个体域**。用了全总个体域后，个体变元取值范围一致了，但不同的论述对象，需要不同的特性谓词再加以刻画。
- 对全称量词，特性谓词作为蕴含式的前件
- 对存在量词，特性谓词作为合取项

> 在不同的个体域中，谓词公式符号化的形 式可能不一样。若事先没有给出个体域，都应以全总个体域为个体域
- **“存在唯一”的表示**：


- **量词的辖域**：邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两端有括号。
> 在量词∀x，∃x辖域内变元x的一切出现叫约束出现，称这样的x为**约束变元**
>
> 变元的非约束出现称为自由出现，称这样的变元为**自由变元**
- 谓词逻辑表示的特征：
- **主要优点**：
- 自然：一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解
- 明确：有一种标准的知识解释方法，因此用这种方法表示的知识明确、易于理解
- 精确：谓词逻辑的真值只有“真”与“假”，其表示、推理都是精确的
- 灵活：知识和处理知识的程序是分开的，无须考虑处理知识的细节
- 模块化：知识之间相对独立，这种模块性使得添加、删除、修改知识比较容易进行
- **主要缺点**：
- 知识表示能力差：只能表示确定性知识，而不能表示非确定性知识、过程性知识和启发式知识
- 知识库管理困难：缺乏知识的组织原则，知识库管理比较困难
- 存在组合爆炸：由于难以表示启发式知识，因此只能盲目地使用推理规则，这样当系统知识量较大时，容易发生组合爆炸
- 系统效率低：它把推理演算与知识含义截然分开，抛弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率
##### 合式公式的性质
合式公式的一些经典性质如下：
##### 谓词公式表示
利用谓词公式进行知识表示的步骤如下：
- 定义谓词及个体，确定其含义
- 根据要表达的事物或概念，为每个谓词中的变元赋值
- 根据表达的知识的含义，用适当的连接符号将各个谓词连接起来，形成谓词公式
##### 置换和合一
表达式的置换就是在该表达式中用置换项置换变量，表达式的合一是寻找项对变量的置换，以使两表达式一致
- **置换 (Subtitution)**：是形如 {t1/x1, t2/x2, …, tn/xn} 的有限集合。其中，ti是不同于xi的项（常量、 变量、函数）， ti/xi表示用ti代换xi
> 例如：{a/x, w/y, f(s)/z}、{g(x)/x}是置换，{x/x}、{y/f(x)}不是置换
>
> 令置换 s＝{t1/x1,… ,tn/xn}，而E是一谓词公式，那么s作用于E，就是将E中出现的变量xi均以ti代入，结果以Es表示，并称为E的一个**例**
常使用的置换间的运算是**置换乘法（合成）**
- 置换是**可结合**的。用S1S2表示两个置换S1和S2的合成，L表示一表达式，则有(LS1)S2=L(S1S2) 以及(S1S2)S3=S1(S2S3)，即用S1和S2相继作用于表达式L，是同用S1S2作用于L一样的
- 一般来说，置换是**不可交换**的

- 合一 (Unification)：寻找项对变量的置换，以使两表达式一致。
> 如果一个置换s作用于表达式集{Ei}的每个元素， 则我们用{Ei}s来表示置换例的集。
>
> 如果存在一个置换s，使得：E1s= E2s= E3s=… ，称表达式集{Ei}是**可合一的**，此时我们称此s为{Ei}的**合一者**，因为s的作用是使 集合{Ei}成为单一形式。
>
>
---
### 消解原理
#### 基本概念
- **文字**：一个原子公式和原子公式的否定都叫做文字，如P(x)，¬P(x,f(x))，Q(x, g(x))
- **子句**：由文字的析取组成的公式，如P(x)∨Q(x)，¬P(x,f(x))∨Q(x,g(x))
- **空子句**：不包含任何文字的子句。空子句不含有文字，它不能被任何解释满足，所以空子句是永假的、不可满足的
- **子句集**：由子句构成的集合，如{ P(x)∨Q(x), ~P(x，f(x))∨Q(x,g(x)) }
- 消解：令L1、L2为两任意原子公式，L1和L2具有相同的谓词符号，但一般具有不同的变量，已知两个子句 L1 ∨ α 和～L2 ∨ β，如果L1和L2具有最一般合一σ，那么通过消解可以从两个父辈子句推导出一个新子句 (α∨β)σ 。 这个新子句叫做消解式。
#### 基本原理
**消解原理**，又称为**归结原理**。该原理是Robinson提出的一种基于逻辑的、采用反证法的推理方法。
消解法的基本原理是采用反证法或者称为反演推理方法，将待证明的表达式（定理）转换成为逻辑公式（谓词公式），然后再进行归结，归结能够顺利完成，则证明原公式（定理）是正确的
证明的基本思想是：
- 设F1、…、Fn、G为公式，G为F1、…、Fn的逻辑推论，当且仅当公式 ( (F1∧…∧Fn) → G) 是有效的
- 也可以采用反证法的思想，设F1、…、Fn、G为公式，G为F1、…、Fn的逻辑推论，当且仅当公式（F1∧…∧Fn∧¬G）是不可满足的
- 归结法的本质上就是一种反证法，它是在归结推理规则的基础上实现的，为了证明一个命题P恒真，它证明其反命题¬P恒假，即不存在使得¬P为真的解释
#### 消解
任何谓词公式F都可通过等价关系及推理规则化为相应的子句集S，当**消解**可使用时，消解过程被应用于母体子句对，以便产生一个导出子句。
例如，如果存在某个公理E1∨E2和另一公理\~E2∨E3，那么，那么E1∨E3在逻辑上成立，这就是**消解**，而称E1∨E3为E1∨E2和\~E2∨E3的消解式（resolvent）
#### 求子句集过程
任一谓词演算公式可以化成一个子句集。其变换过程由下列**九个步骤**组成：
1. 消去蕴涵符号，只应用∨和\~符号，以\~A∨B替换A⇒B
2. 减少否定符号的辖域，每个否定符号~最多只用到一个谓词符号上，并反复应用狄·摩根定律。例如：
（空白里应该是存在符号∃）
3. 对变量标准化，在任一量词辖域内，受该量词约束的变量为一哑元 (虚构变量)，它可以在该辖域内统一地被另一个 没有出现过的任意变量所代替，而不改变公式的真值。合式公式中变量的标准化，意味着对哑元改名以保证每个量词有其自己唯一的哑元。例如：

4. 消去存在量词
- 如果要消去的存在量词在某些全称量词的辖域内（空白里应该是存在符号∃）：

- 如果要消去的存在量词不在任何一个全称量词的辖域内，那么就使用不含变量的Skolem函数即常量。例如，(∃x)P(x)化为P(A)，其中常量符号A用来表示我们知道的存在实体。A必须是个新常量符号，它未曾在公式中其它地方使用过。
5. 化为前束形，到这一步，已不留下任何存在量词，而且每个全称量词都有自己的变量。把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。所得公式称为**前束形**。前束形公式由前缀和母式组成，前缀由全称量词串组成，母式由没有量词的公式组成，即：前束形 = (前缀)全称量词串+(母式)无量词公式
6. 把母式化为合取范式，任何母式都可写成由一些谓词公式和谓词公式的否定的析取的有限集组成的合取，这种母式叫做**合取范式**。我们可以反复应用分配律。把任一母式化成合取范式。例如，我们把A∨{B∧C}化为{A∨B}∧{A∨C}
7. 消去全称量词，到了这一步，所有余下的量词均被全称量词量化了。同时，全称量词的次序也不重要了。因此，我们可以消去前缀，即消去明显出现的全称量词
8. 消去连词符号∧，用{(A∨B), (A∨C)}代替(A∨B)∧(A∨C)，以消去明显的符号∧。反复代替的结果，最后得到一个有限集，其中每个公式是文字的析取。任一个只由文字的析取构成的合式公式叫做一个**子句**。
9. 更换变量名称，可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。例如：

#### 消解反演证明
##### 概念回顾
应用归结原理证明定理的过程称为**归结（消解）反演**。（消解）归结方法是一种机械化的、可在计算机上实现的推理方法，可认为是一种反向推理形式，提供了一种自动定理证明的方法

##### 消解反演一般过程
1. 建立子句集S
2. 从子句集S出发，仅对S的子句间使用归结推理规则
3. 如果得出空子句，则结束，否则转下一步
4. 将所得归结式仍放入S中
5. 对新的子句集使用归结推理规则
6. 转第3步
> 空子句不含有文字，它不能被任何解释满足，所以空子句是永假的、不可满足的。
>
> 归结过程出现空子句，说明出现互补文字，说明S中有矛盾，因此S是不可满足的。
##### 归结反演证明步骤
设F为已知前提的公式集，Q为目标公式(结论)，用归结反演进行证明的步骤是：
1. 否定Q，得到¬Q
2. 把¬Q并入到公式集F中，得到{F, ¬Q}
3. 把公式集{F, ¬Q}化为子句集S
4. 应用消解推理规则对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若出现了空子句，则停止归结
##### 例子
一些例子如下：
#### 反演求解过程
反演求解实际是把一棵根部有NIL的反演树变换为根部带有回答语句的一棵证明树，从反演树求取答案步骤：
- 把由目标公式的否定产生的每个子句添加到目标公式**否定之否定**的子句中去
- 按照反演树，执行和以前相同的消解，直至在根部得到某个子句停止
- 用根部的子句作为一个回答语句
> 关键想法是把问题化为一个包含某个存在量词 的目标公式，使得此存在量词量化变量表示对该问题的一个解答。如果问题可以从给出的事 实得到答案，那么按这种方法建立的目标函数在逻辑上遵循S。在得到一个证明之后，我们就试图求取存在量词量化变量的一个例，作为一个回答。

---
### 规则演绎系统
#### 基本概念
基于规则的演绎推理是一种直接的推理方法，它不像消解反演把知识转化为子句集，而是把有关 问题的知识和信息划分为规则和事实两种类型
规则由包含蕴含形式的表达式表示，事实由无蕴含形式的表达式表示，并画出相应的与或图，然后通过规则进行演绎推理
规则演绎系统可以分为规则正向演绎推理、规则逆向演绎系统和规则双向演绎系统
#### 规则正向演绎系统
##### 定义
规则正向演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的
##### 正向推理过程
1. 事实表达式的与或形变换
把事实表示为非蕴涵形式的与或形，作为系统的总数据库。具体变换步骤与前述化为子句形类似
> 注意：我们不把这些事实化为子句形，而是表示为谓词演算公式，并把这些公式变换为非蕴涵形式的与或形
>
> 与或形表达式是由符号∧和∨连接的一些文字的子表达式组成的。呈与或形的表达式并不是子句形，与子句集比起来，与或形更多的保留了公式的原始形式
>
>
2. 事实表达式的与或图表示
我们一般把事实表达式的与或图表示倒过来画，即把根节点画在最下面， 而把其后继节点往上画。
公式的与或图表示有个有趣的性质，即由变换该公式得到的子句集可作为此与或图的解图的集合(终止于叶节点)读出；也就是说，所得到的每个子句是作为解图的各个叶节点上文字的析取。


3. 与或图的F规则变换
这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：L ⇒ W （式中： L是单文字；W为与或形的公式）


4. 作为终止条件的目标公式，基于规则的正向演绎推理的基本原理是：应用F规则作用于表示事实的与或图，改变与或图的结构，从而产生新的事实，直到推出目标公式，则推理成功结束

##### 案例
证明过程
我们得到的结论是：当正向演绎系统产生一个含有以目标节点作为终止的解图时，此系统就成功地终止。

---
#### 规则逆向演绎系统
##### 定义
规则逆向演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。逆向演绎系统能够处理任意形式的目标表达式。
##### 求解过程
1. 目标表达式的与或形式
采用和变换事实表达式类似的过程，把目标公式化成与或形：
1. 消去蕴涵符号
2. 把否定符号移到每个谓词符号前面
3. 变量标准化
4. 引入Skolem函数消去全称量词
5. 将公式化为前束形
6. 删去存在量词。留在目标表达式与或形中的变量假定都已被存在量词量化
7. 重新命名变量，使同一变量不出现在不同的主要析取式中
> 用对偶形式对目标表达式进行变换
（空白里应该是存在符号∃）

2. 与或图的B规则变换
现在让我们应用B规则即逆向推理规则来变换逆向演绎系统的与或图结构。这个B规则是建立在确定的蕴涵式基础上的，正如正向系统的F规则一样。不过，我们现在把这些B规则限制为 **W⇒L** 形式的表达式。
其中，W为任一与或形公式，L为文字，而且蕴涵式中任何变量的量词辖域为整个蕴涵式。把B规则限制为这种形式的蕴涵式还可以简化匹配，使之不会引起重大的实际困难。
此外，可以把像W⇒(L1∧L2)这样的蕴涵式化为两个规则W⇒L1和W⇒L2。
3. 作为终止条件的事实节点的一致解图
逆向系统中的事实表达式均限制为**文字合取形**，它可以表示为一个文字集。当一个事实文字和标在该图文字节点上的文字相匹配时，就可把相应的后裔事实节点添加到该与或图中去。这个事实节点通过标有mgu的匹配弧与匹配的子目标文字节点连接起来。同一个事实文字可以多次重复使用(每次用不同变量)，以便建立多重事实节点。 　
逆向系统成功的终止条件是**与或图包含有某个终止在事实节点上的一致解图**。
##### 案例
---
#### 规则双向演绎系统
##### 背景知识
基于规则的正向演绎系统和逆向演绎系统的特点和局限性：
- 正向演绎系统能够处理任意形式的if表达式，但被限制在then表达式为文字析取组成的一些表达式
- 逆向演绎系统能够处理任意形式的then表达式，但被限制在if表达式为文字合取组成的一些表达式
##### 组合演绎系统构成
双向(正向和逆向)组合演绎系统具有正向和逆向两系统的优点，克服各自的缺点。
正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成，并分别用F规则和B规则来修正
双向演绎系统的主要复杂之处在于其终止条件，终止涉及两个图结构之间的适当交接处。这些结构可由标有合一文字的节点上的匹配棱线来连接。
---
#### 产生式系统
##### 定义
用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是**产生式规则**或**产生式条件**和**操作对**的概念
##### 实质
在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。 由于这类系统的知识库主要用于存储规则，因此又把此类系统称为**基于规则的系统**。
##### 组成

- 产生式规则，是一个规则库，用于存放与求解问题有关的某个领域知识的规则之集合及其交换规则。规则是一个以“如果满足这个条件，就应当采取某些操作”形式表示的语句。规则库知识的完整性、一致性、准确性、灵活性和知识组织的合理性，将对产生式系统的运行效率和工作性能产生重要影响。
- 总数据库，有时称作上下文，当前数据库或暂时存储器，用于存放求解过程中各种当前信息的数据结构。总数据库是产生式规则的注意中心。执行产生式规则的操作会引起总数据库的变化，这使其他产生式规则的条件可能被满足
- 控制策略，为一推理机构，由一组程序组成，用来控制产生式系统的运行，决定问题求解过程的推理线路，实现对问题的求解。
##### 产生式系统的推理
分为正向推理、逆向推理和双向推理



---
## 第四章 不确定性推理
### 基本概念和方法
#### 什么是不确定性推理？
- 不确定性推理是建立在非经典逻辑基础上的一种推理，它是对不确定性知识的运用与处理
- 具体地说，所谓不确定性推理就是从不确定性的初始证据（即事实）出发，通过运用不确定性的知识，最终推出具有 一定程度不确定性的结论
#### 不确定性推理中的基本问题
##### 不确定性的表示与度量
不确定性推理中的“不确定性”一般分为两类：一是**知识的不确定性**，二是**证据的不确定性**
- 知识不确定性的表示：目前在专家系统中知识的不确定性一般是由领域专家给出的，通常用一个数值表示，它表示相应知识的不确定性程度，称为知识的**静态强度**
- 证据不确定性的表示：证据不确定性的表示方法与知识不确定性的表示方法一致，通常也用一个数值表示，代表相应证据的不确定性程度，称之为**动态强度**
##### 不确定性匹配算法及阈值的选择
推理是不断运用知识的过程，为了找到所需的知识，需要在这一过程中用知识的前提与已知证据进行匹配，只有匹配成功的知识才有可能被应用
- 设计一个不确定性匹配算法
- 指定一个匹配阈值
##### 组合证据不确定性的计算方法
已知证据E1和E2的不确定性度量，求证据E1和E2的析取和合取的不确定性，常用的方法有：
- 最大最小法：
- T(E1 AND E2) = min{T(E1),T(E2)}
- T(E1 OR E2) = max{T(E1),T(E2)}
- 概率法：
- T(E1 AND E2) = T(E1)×T(E2)
- T(E1 OR E2) = T(E1)+T(E2)-T(E1)×T(E2)
- 有界法：
- T(E1 AND E2) = max{0, T(E1)＋T(E2)－1}
- T(E1 OR E2) = min{1, T(E1)＋T(E2)}
其中，T(E)表示证据E为真的程度（动态强度），如可信度、概率等。
##### 不确定性的传递算法
- 在每一步推理中，如何把证据及知识的不确定性传递给结论？
- 在多步推理中，如何把初始证据的不确定性传递给最终结论？
##### 结论不确定性的合成
用不同知识进行推理得到了相同结论，但所得结论的不确定性却不同。此时，需要用合适的算法对结论的不确定性进行合成
#### 不确定性推理方法的分类
不确定性推理方法主要可分为**模型法**与**控制法**。
其中，模型法在推理一级对确定性推理进行扩展，引入证据的不确定性及知识的不确定性模型方法又分为数值方法和非数值方法两类。数值方法对不确定性进行定量的描述，按其所依据的理论又可分为基于概率的方法和基于模糊理论 的方法。
**本文主要针对模型方法中相关的典型算法展开**
##### 逆概率法
若A1,A2,…,An构成一个完备事件组且都有正概率，对于事件B，则有以下贝叶斯概率：
例题：
逆概率法的特点：
- 优点：逆概率法有较强的理论背景和良好的数学特性，当证据彼此独立时计算的复杂度比较低
- 缺点：逆概率法要求给出结论Hi的先验概率P(Hi)及条件概率P(Ej|Hi)
##### 可信度方法
可信度方法是在确定性理论的基础上，结合概率论等提出的一种不确定性推理方法，简称C-F模型。该方法首先在医疗系统MYCIN中得到成功的应用。其中，根据经验对一个事物和现象为真的相信程度称为**可信度**。在可信度方法中，由专家给出规则或知识的可信度，从而可避免对先验概率、或条件概率的要求。
C-F模型的核心问题是三个可信度：
- 知识的可信度CF(H,E)：取值范围[-1，1]
- 证据的可信度CF(E)：取值范围[-1，1]
- 结论的可信度CF(H)：取值范围[-1，1]
###### **知识不确定性的表示**
在C-F模型中，知识是用**产生式**规则表示的，其一般形式为：IF E THEN H (CF(H,E))
其中：
- 前提E可以是命题的合取和析取组合
- 结论H可为单一命题，也可以是复合命题
- CF(H, E)为确定性因子(Certainty factor)，简称**可信度**，用以量度规则的确定性（可信）程度，取值于[-1，1]，表示E为真时，对H的支持程度。CF(H, E)值越大，E就越支持H为真。
> 产生式与蕴含式的区别：
>
> - 蕴含式的知识一定是精确的
> - 产生式的知识可以是不确定的
###### 规则可信度因子
规则可信度因子CF(H,E)定义为： CF(H,E) = MB(H,E) - MD(H,E)
- MB反映了证据对结论有利的一面。MB(Measure Belief) 表示因与E匹配的证据出现，使H为真的信任增长度
- MD反映了证据对结论不利的一面。MD(Measure Disbelief) 指不信任增长度，表示因与E匹配的证据出现，使H为真的不信任增长度

- 当P(H|E)>P(H)时：表示证据E支持结论H，MB(H,E)>0，MD(H,E)\=0
- 当P(H|E)0，MB(H,E)=0
- 当p(H/E)\=p(H)时，表示E对H无影响，则有MB\=MD\=0
可见，MB(H,E)与MD(H,E)是互斥的： 当MB(H,E)>0时，MD(H,E)\=0；当MD(H,E)>0时，MB(H,E)\=0
据此，得到**CF(H,E)的计算公式**：

CF(H,E)定性地反映了P(H|E)的大小，因此可以用 CF(H,E)近似表示P(H|E)的大小，从而描述了规则的可信度，反应了规则的**静态强度**。
###### 证据可信度因子

进一步地，设证据E所在的环境为S，则可用可信度CF(E, S)来表示E在S下的确定性程度，并有：CF(E, S) = MB(E, S) - MD(E, S)
- 若S下E为真，则CF(E,S ) = 1
- 若E为假，则CF(E,S) = -1
- 若S对E的真值无影响，则CF(E,S)= 0
> 类似于规则的不确定性，证据的可信度往往可由领域专家凭经验主观确定
>
> 证据的可信度值来源于两种情况：
>
> - 初始证据由领域专家或用户给出
> - 中间结论由不确定性传递算法计算得到
**组合证据不确定性的算法：**

###### 结论的可信度因子
介绍不确定性的传递算法、结论不确定性的合成算法
**不确定性的传递算法**
定义如下：**CF(H) = CF(H,E) ×max[0，CF(E)]**
由上式可以看出：
- CF(E)<0时，CF(H)=0，说明该模型没有考虑证据为假时对结论H所产生的影响
- CF(E)=1时，CF(H)=CF(H,E)，说明规则可信度CF(H,E)就是证据为真时的结论H的可信度
**结论不确定性的合成算法**
若由多条不同知识推出了相同的结论，但可信度不同，则可用合成算法求出综合的可信度。由于对多条知识的综合可通过两两的合成实现，所以下面只考虑两条知识的情况 。

**案例：**


该公式隐含了一个知识运用的条件, 即CF(E)>0。
整体而言，基于可信度的不确定性推理方法的特点：
- 优点：简单、直观
- 缺点：可信度因子依赖于专家主观指定，没有统一、客观的尺度，容易产生片面性；随着推理延伸，可信度越来越不可靠，误差越来越大。当推理深度达到一定深度时，有可能出现推出的结论不再可信的情况
---
#### 加权的不确定性推理
这里介绍加权的可信度方法。
##### 知识不确定性的表示
IF E1(ω1) AND E2(ω2) AND…AND En(ωn) THEN H (CF(H,E), λ)
其中ωi (i=1,2,…,n)是加权因子，λ是阈值，其值均由专家给出。加权因子的取值范围一般为[0,1]，且应满足归一条件
加权因子的引入不仅可以区分不同证据的重要性， 同时还可以解决证据不全时的推理问题。
##### 组合证据不确定性的算法
若有CF(E1)，CF(E2)，…，CF(En)，则组合证据的可信度为：

##### 不确定性的传递算法
当一条知识的CF(E)满足CF(E)≥λ时，该知识就可被应用。结论H的可信度为： CF(H)=CF(H,E)×CF(E)
##### 练习例题
例题如下：


##### 冲突消解

---
### 模糊推理
#### 模糊数学
##### 基本概念
- 模糊概念：从属于该概念到不属于该概念之间无明显分界线
- 模糊数学：用数学方法研究模糊现象
- 基本思想：用属于程度代替属于或不属于
- 模糊性与随机性之区别：
- 随机性
- 事件本身具有明确含意
- 事件是否出现的不确定性
- [0,1]上概率分布函数描述
- 模糊性
- 事物的概念本身是模糊的
- 概念的外延的模糊－不确定性：模糊性
- [0,1]上的隶属函数描述
##### 模糊数学理论
###### 经典集合
**集合**是数学中最基本的概念之一，所谓集合，是指具有某种特定属性的对象的全体。讨论某一概念的外延时总离不开一定的范围。 这个讨论的范围，称为**“论域”**，论域中的每个对象称为**“元素”**。
**集合的特征函数**

###### 模糊理论基本概念
- 模糊集合：论域U中的模糊集F用一个在区间[0,1]的取值的隶属函数来表示，即 _μ_$_F$ : _U_ → [0,1]
- _μ_$_F$ 称为F的隶属函数
- _μ_$_F$(_u_)称为u对A的隶属度
- F 可以表示为：_F_ = { _u_, _μ_$_F$(_u_) / *u* ∈ _U_ }
- 模糊子集 F 完全由其隶属函数所刻画。隶属函数把U中的每一个元素都映射为[0,1]上的一个值，表示该元素隶属于 F 的程度，值越大表示隶属的程度越高。当 _μ_ 的值**仅**为0或1时，模糊子集 F 就退化为一个普通的集合，隶属函数也就退化为特征函数。

- 模糊集的表示方法



- 集合运算
模糊集合是利用集合中的特征函数或者隶属度函数来定义和操作的，A、B是U中的两个模糊子集，隶属度函数分别为_μ_$_A$ 、_μ_$_B$ ，则：



例题：

- 模糊集合性质与运算


- 模糊集的截集
- λ截集是把模糊集向普通集合转化的一个重要概念。很简单，A归属度大于等于λ的元素就放到一个集合里，称为A的一个λ截集；若只放入大于λ的元素，则称为A的一个λ强截集。
- 其中，若λ=0，对应的λ强截集则称为A的支集（SuppA）；若λ=1，对应的λ截集则称为A的核（KerA，归属度全为1）
- 当A的核不为空，则称A为正规F集

- 模糊集合的模糊度：模糊度是模糊集模糊程度的一种度量

模糊度的直观含义：
- 是[0,1]上一个数
- 普通集合的模糊度是0，表示所刻画的概念不模糊
- 越靠近0.5就越模糊，当 μA(u)恒等于0.5时最模糊
- 模糊集A与其补集¬A有相同的模糊度
- 计算模糊度的方法
- 海明(Haming)模糊度：p=1
- 欧几里德(Euclid)模糊度：p=2
- 明可夫斯基(Minkowski)模糊度：p
- 香农模糊度


例题：

- 模糊数

- 普通集合上的关系

- 模糊关系与模糊矩阵
在普通集合上定义的“关系”都是确定性关系，u和v或者有某种关系，或者没有这种关系
但是，在现实世界中，很多事物的关系并不十分明确，如人与人之间的相像关系、人与事物之间的爱好关系等


- 模糊关系的笛卡尔积：取最小归属值

- 模糊关系的合成


#### 模糊推理
##### 概念
- 模糊命题：含有模糊概念、模糊数据的语句称为**模糊命题**。它的一般表示形式为：
​ x is A 或者 x is A(CF)
其中，A是模糊概念或者模糊数，用相应的模糊集及隶属函数刻画； x是论域上的变量，用以代表所论述对象的属性； CF是该模糊命题的可信度，它既可以是一个确定的数，也可以是一个**模糊数**或者**模糊语言值**。
> 模糊语言值是指表示大小、长短、多少等程度的一些词汇。如：极大、很大、相当大、比较大。模糊语言值同样可用模糊集描述。
>
> 模糊数：
>
> 
##### 模糊知识的表示
模糊产生式规则的一般形式是： IF E THEN H (CF, λ)
其中，E是用模糊命题表示的模糊条件，H是用模糊命题表示的模糊结论，CF是知识的可信度因子，它既可以是一个确定 的数，也可以是一个模糊数或模糊语言值。λ是匹配度的阈值，用以指出知识被运用的条件。
例如： IF x is A THEN y is B (CF, λ)
上例中可见，推理中所用的证据也用模糊命题表示，一般形式为 x is A’ 或者 x is A’ (CF)
##### 模糊推理要解决的问题
- 证据与知识的条件是否匹配
- 如果匹配，如何利用知识及证据推出结论
##### 模糊匹配与冲突消解
在模糊推理中，知识的前提条件中的A与证据中的A’不一 定完全相同，因此首先必须考虑匹配问题
例如：IF x is 小 THEN y is 大 (0.6) ， x is 较小
两个模糊集或模糊概念的相似程度称为**匹配度**。常用的计算匹配度的方法主要有贴近度、语义距离及相似度等。
1. 贴近度
2. 语义距离（注意区分模糊度计算公式）
3. 相似度
##### 构造模糊关系R
扎德提出了两种方法：一种称为条件命题的极大极小规则 ；另一种称为条件命题的算术规则，由它们获得的模糊关系 分别记为Rm和Ra 。必考。
##### 模糊判决
在推理得到的模糊集合中取一个相对最能代表这个模糊集合的单值的过程，称作解模糊（去模糊）或**模糊判决(Defuzzification)**。模糊判决可以采用不同的方法：重心法、最大隶属度方法、加权平均法、隶属度限幅元素平均法。
挺简单，但很可能考，略
---
## 第五章 进化计算
- 遗传算法基本思想
遗传算法把问题的解表示成“染色体” ，在算法中即是以一定方式编码的串。并且，在执行遗传算法之前，给出一群“染色体” ，也即假设解（候选解）。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上， 它就是问题的最优解。
- 遗传算法主要组成部分
- **编码/解码机制**，适应度函数，控制参数，遗传算子（选择、 交叉、变异）
- 选择概率、累计概率、选择次数和变异后种群编码的计算（2023这届考的）
- 遗传算法流程
- 算法停止条件
- 简单的算法流程图：
- 进化算法的三个类型（遗传算法，进化规划，进化 策略）简单了解
## 第六章 群智能
- 群智能基本概念及特点
- 群（swarm）：某种交互作用的组织或agent的结构集合
- 对于群居昆虫，如蚂蚁、蜜蜂、鱼群、鸟群等，个体在结构上是很简单的，而它们的集体行为却可能变得相当复杂。人们把群居昆虫的集体行为称作“**群智能**”，即低智能的主体通过合作表现出高智能行为的特性
- 群智能算法是一种基于生物群体行为规律的计算技术
- 特点
- 优点与不足
- 粒子群算法
- 速度、位置更新公式
- 算法流程
- 蚁群算法
- 路径选择概率计算公式 ：
其中，α是信息素重要程度因子， β是启发函数重要程度因子。 tabuk为禁忌表，表示已访问的城市集合
蚂蚁从当前城市访问下一城市的概率确定后，通常采用轮盘赌法选择下一城市
- 信息素浓度更新公式
- 算法流程

## 第七章 神经网络
- 人工神经元模型
人工神经网络（Artificial Neural Network，ANN）是由大量处理单元经广泛互连而组成的人工网络，用来模拟脑神经系统的结构和功能。而这些处理单元称作人工神经元
- 人工神经网络的特点
- 人工神经网络基本结构
- 前馈神经网络：具有递阶分层结构，神经元从一层连接至下一层，不存在同层神经元间的连接
- 反馈神经网络：反馈网络又叫做递归网络。有些神经元的输出被反馈至同层或前层神经元。其输入数据决定反馈系统的初始状态，然后系统经过一系列的状态转移后逐渐收敛于平衡状态，即为反馈神经网络经过计算后的输出结果
- 神经网络知识表示
在基于神经网络的系统中，知识的表示方法与传统人工智能系统中所用的方法（如产生式系统、框架、语义网络等）完全不同。人工智能系统中所用的方法是知识的显式表示，而神经网络中的知识是一种隐式的表示方法。在这里，知识并不像在产生式系统中那样独立地表示为每一条规则，而是将某一问题的若干知识在同一网络中表示
二层网络结构不能实现异或逻辑，那么如何实现？
- 神经网络推理过程
- 前向计算过程

---
## 其他章节
### 数据挖掘
#### 定义
#### 主要方法
#### 数据挖掘系统的分类
---
### 专家系统
----
### 机器学习
---
### 知识图谱
---
## 课后习题（部分）
---
---
---
---
？搜索技术下的PPT
---
---
---
---
---
将下列谓词公式化为子句集
---
---
---
---
---
用贴近度计算匹配度
---
## 末尾（快捷跳转）