人工智能复习提纲

小管

复习

发布于：Dec 9, 2020

次浏览

5.3k words

20 min

0  

第一章

1. 什么是人工智能

2. 人工智能研究的基本内容有那些？

3. 人工智能有那些主要的研究领域？

第二章

1. 什么是知识、命题、产生式？

2. 掌握谓词公式的五个连接词

1. $\neg$ : 非 或 否定，表示否定位于它之后的命题
2. $\vee$ ：析取，表示被它连接的二个命题具有“或”关系
3. $\wedge$ : 合取，表示被它连接的二个命题具有“与”关系
4. $\rightarrow$ : 蕴涵 或 条件，$P\rightarrow Q$ 表示“$P$ 蕴涵$Q$”，即表示“如果$P$，则$Q$”。其中，$P$称为条件的前件，$Q$称为条件的后件。
5. $\leftrightarrow$ : 等价 或 双条件，$P \leftrightarrow Q$ 表示“$P$当且仅当$Q$”

3. 掌握存在量词、全程量词

1. 全程量词$(\forall x)$: 表示“对于个体域中的所有（或任一个）个体 $x$ ”
2. 存在量词$(\exists x)$: 表示“对于个体域中存在个体$x$”

4. 自然语句改写成相应的谓词公式

例 2.1 用一阶谓词公式表示“每个储蓄钱的人都得到利息”。

解 定义谓词：$save(x)$表示$x$储蓄钱，$interest(x)$表示$x$获得利息。

则“每个储蓄钱的人都得到利息”可以表示为：$(\forall x)(save(x)\rightarrow interest(x)) $

习题2.4 用谓词逻辑表达描述一下列推理：

（1）如果张三比李四大，那么李四比张三小。

（2）甲和乙结婚列，则甲为男，乙为女或者甲为女，乙为男

（3）如果一个人是老实人，他就不会说谎；张三说了谎，所以张三不是老实人。

（1）Older(x,y)：x 比 y 大。Older(Zhang, Li) → ¬Older(Li, Zhang)
（2）Man(x): x 为男；¬Man(x): x 为女；Marry(x, y)：x 和 y 结婚。
    Marry(甲，乙)→(Man(甲) ∧ ¬Man(乙)) ∨ (Man(乙) ∧ ¬Man(甲))
（3）Honest(x)：x 是老实人；Lie(x)：x 说谎。
    Honest(x) → ¬Lie(x);Lie(Zhang) → ¬Honest(Zhang)
    

5. 熟练运用产生式表达法

1. 确定性规则知识的产生式表示：

$IF$$P$$THEN$$Q$ 或者 $P\rightarrow Q$

例如： IF 动物会飞 AND 会下蛋 THEN 该动物是鸟

2. 不确定性规则知识的产生式表示：

$IF$$P$$THEN$$Q$（置信度）或者$P\rightarrow Q（置信度）$

3. 确定性事实知识的产生式表示：

一般用三元组表示：$(对象，属性，值)$ 或者 $(关系，对象1，对象2)$

例如：老李的年龄是 40 岁，表示为$（Li，Age，40）$ 。老李和老王是朋友，表示为$（Friend, Li, Wang）$

4. 不确定性事实知识的产生式表示：

一般用四元组表示：$(对象，属性，值，置信度)$或者$(关系，对象1，对象2，置信度)$

例如：老李的年龄很可能是 40 岁，表示为$（Li，Age，40，0.8）$ 。老李和老王是朋友，表示为$（Friend, Li, Wang，0.2）$

习题2.5 产生式表达异或$(XOR)$逻辑。

 
    IF   x1 = 0        AND    x2 = 0    THEN    y = 0
    IF   x1 = 1        AND    x2 = 0    THEN    y = 1
    IF   x1 = 0        AND    x2 = 1    THEN    y = 1
    IF   x1 = 1        AND    x2 = 1    THEN    y = 0
    

第三章

1. 什么是子句、空子句？

2. 什么是确定性推理？

3. 掌握谓词公式化为子句集的方法。

谓词公式化为子句集的一般步骤：

例3.3：将下列谓词公式化为子句集

​ $(\forall x){[\neg P(x) \vee \neg Q(x)]\rightarrow (\exists y)[S(x,y)\wedge Q(x)]}\wedge(\forall x)[P(x)\vee B(x)]$

1. 消去蕴涵符号

   $(\forall x){\neg [\neg P(x) \vee \neg Q(x)]\vee (\exists y)[S(x,y)\wedge Q(x)]}\wedge(\forall x)[P(x)\vee B(x)]$

2. 把否定符号移到每个谓词的前面

   $(\forall x){ [ P(x) \wedge Q(x)]\vee (\exists y)[S(x,y)\wedge Q(x)]}\wedge(\forall x)[P(x)\vee B(x)]$

3. 变量标准化

   $(\forall x){ [ P(x) \wedge Q(x)]\vee (\exists y)[S(x,y)\wedge Q(x)]}\wedge(\forall w)[P(w)\vee B(w)]$

4. 消去存在量词
   设 y 的 Skolem 函数为 $f(x)$,则

   $(\forall x){ [ P(x) \wedge Q(x)]\vee [S(x,f(x))\wedge Q(x)]}\wedge(\forall w)[P(w)\vee B(w)]$

5. 化为前束型

   $(\forall x)(\forall w){ {\lbrack P(x)\wedge Q(X)\rbrack\vee\lbrack S(x,f(x))\wedge Q(x)\rbrack}\wedge\lbrack P(w)\vee B(w)\rbrack}$

6. 化为 Skolem 标准形

   $(\forall x)(\forall w){ Q(x) \wedge [S(x,f(x))\vee P(x)]\wedge[P(w)\vee B(w)]}$

7. 略去全程量词

   ${ Q(x) \wedge [S(x,f(x))\vee P(x)]\wedge[P(w)\vee B(w)]}$

8. 消去合取词，把母式用子句集表示

   ${ Q(x) , S(x,f(x))\vee P(x),P(w)\vee B(w)}$

9. 子句变量标准化，即使每个子句中的变量符号不同

   ${ Q(x) , S(y,f(y))\vee P(y),P(w)\vee B(w)}$

例3.4 P63

习题3.4（3） p74

4. 熟练运用鲁滨逊归结原理进行归结反演以及求解问题

例3.9 p68

例3.10 p69

例3.11 p70

例3.12 p71

习题3.7 3.10 P75

第四章

1. 什么是不确定性推理、可信度、C-F模型？

2. 熟练运用组合证据不确定性的算法

合取 取小

析取 取大

3. 熟练运用结论不确定性的合成算法

例4.1 P82

4. 掌握概率分配函数、信任函数、似然函数、概率分配函数的正交和

P84-P6

5. 了解模糊集合的定义、表达方法

P90-P91

6. 什么是隶属函数

​ 隶属集合中所有的元素的隶属度全体构成模糊集合的隶属函数

7. 模糊集合的运算

1. 模糊集合的包含关系

   ​ 若$\mu_A(x)\geq\mu_B(x)$，则$A\ni B$

2. 模糊集合的相等关系

   ​ 若$\mu_A(x)=\mu_B(x)$，则$A=B$

3. 模糊集合的交并补运算

   1. 交运算 $A\cap B$

      $\mu_{A\cap B}(x)=min\lbrace\mu_A(x),\mu_B(x)\rbrace=\mu_A(x)\wedge\mu_B(x)$

   2. 并运算 $A\cup B$

      $\mu_{A\cup B}(x)=max\lbrace\mu_A(x),\mu_B(x)\rbrace=\mu_A(x)\vee\mu_B(x)$

   3. 补运算 $\overline A$

      $\mu_\overline A(x)=1-\mu_A(x)$

4. 模糊集合的代数运算

   1. 代数积：

      $ \mu_{AB}(x)=\mu_A(x)\mu_B(x) $

   2. 代数和

      $\mu_{A+B}(x)=\mu_A(x)+\mu_B(x)-\mu_{AB}(x)$

   3. 有界和

      $\mu_{A\oplus B}(x)=min\lbrace 1,\mu_A(x)+\mu_B(x)\rbrace=1\wedge\lbrack\mu_A(x)+\mu_B(x)\rbrack$

   4. 有界积

      $\mu_{A\otimes B}(x)=max\lbrace 1,\mu_A(x)+\mu_B(x) \rbrace=0\vee\lbrack\mu_A(x)+\mu_B(x)-1\rbrack$

8. 模糊关系的叉积表示

P95

9. 模糊关系的合成

P96

10. 模糊决策的三种方法

P99

1. 最大隶属度法

   在模糊向量中，取隶属度最大的量作为推理结果。

2. 加权平均判决法
   $$
   U=\frac{\displaystyle\sum_{i=1}^n\mu(u_i)u_i}{\displaystyle\sum_{i=1}^n\mu(u_i)}
   $$
   例如：
   $$
   U’ = 0.1/2+0.6/3 + 0.5/4 + 0.4/5 + 0.2/6
   $$

   $$
   U=\frac{0.1\times2+0.6\times3+0.5\times4+0.4\times5+0.2\times6}{0.1+0.6+0.5+0.4+0.2}
   $$

3. 中位数法

   中位数法就是把模糊集的中位数作为系统控制变量。

   当论域为有限离散点时，中位数$u^*$可以用下列公式求取
   $$
   \sum_{u_1}^{u^\ast}\mu(u_i)=\sum_{u^\ast+1}^{u_n}\mu(u_i);
   $$
   例如： $U’=0.1/-4+0.5/-3+0.1/-2+0.0/-1+0.1/0+0.2/1+0.4/2+0.5/3+0.1/4);$

   当$u^*=6$ 时，$\sum_{u_1}^{u_6}\mu(u_i)=\sum_{u_7}^{u_9}\mu(u_i)=1$，所以中位数为$u^* = u_6 = 1$，则$U=1$。

第五章

1. 搜索的基本问题与主要过程

搜索中需要解决的基本问题：

搜索的主要过程：

2. 什么是状态空间

3. 什么是回溯决策

4. 宽度优先搜索策略和深度优先搜索策略

宽度优先搜索策略是按照下图所示的次序来搜索状态的，由$S$0生成状态1，2，然后扩展状态1，生成状态3，4，5，接着扩展状态2，生成状态6，7，8，该层扩展完后，再进入下一层，对状态3进行扩展，如此一层层地扩展下去，直到搜索到目的状态（如果目的状态存在）。

在实际的宽度优先搜索时，为了保存空间搜索的轨迹，用到了两个表：open表和closed表。open表与回溯算法中的NPS表相似，包含已经生成出来但其子状态未被搜索的状态。open表中状态的排列次序就是搜索的次序。closed表记录了已被生成扩展过的状态，它相当于回溯算法中PS表和NSS表的合并。

深度优先搜索策略是按下图所示的次序来搜索状态的。搜索从$S$0出发，沿一个方向一直扩展下去，如状态1，2，3，直到达到一定的深度（这里假定为3层）。如果未找到目的状态或无法再扩展时便回溯到另一条路径（状态4）继续搜索；若还未找到目的状态或无法再扩展时，再回溯到另一条路径（状态5，6）搜索……

在深度优先搜索中，当搜索到某一个状态时，它所有的子状态以及子状态的后裔状态都必须先于该状态的兄弟状态被搜索。 为了保证找到解，应选择合适的深度限制值，或采取不断加大深度限制值的办法，反复搜索，直到找到解。

5. 启发信息和估价函数

启发信息：

启发信息的分类：

估价函数：

A算法是基于估价函数的一种加权启发式图搜索算法，具体步骤如下：

1. 把附有$f(S_0)$的初始结点$S_0$放入open表；

2. 若open表为空，则搜索失败，退出；

3. 移出open表中第一个结点N放入closed表中，并顺序编号n；

4. 若目标结点把y附有$f(S_0)$的初始$S_g=N$，则搜索成功，结束；

5. 若N不可扩展，则转步骤2；

6. 扩展N，生成一组附有$f(x)$的子结点，对这组子结点做如下处理：

   ​ a.考察是否有已在open表或closed表中存在的结点。若有则再考察其中有无N的先辈结点，若有则删除之，对于其余结点也删除之，但由于它们又被第二次生成，因此需要考虑是否修改已经存在于open表中的这些结点及其后裔的返回指针和$f(x)$的值。修改原则是：选$f(x)$值小的路径走。

   ​ b.为其余子结点配上指向N的返回指针后放入open表中，并对open表按$f(x)$值以升序排序，转步骤2。

A* 算法：定义$h^*(n)$为状态n到目的状态的最优路径的代价，则当A搜索算法的启发函数$h(n)$小于等于$h^*(n)$，即满足
$$
h(n)\leq h^*(n)，对所有结点n
$$
时，被称为A*搜索算法。

八数码问题: P124

第六章

1. 什么是进化算法

2. 什么是基本遗传算法？理解编码、初始群体的设定、适应度函数、选择、交叉、变异

编码等见书135页。

3. 遗传算法的一般步骤、遗传算法的基本流程图

一般步骤：

1. 使用随机方法或者其他方法，产生一个有$N$个染色体的初始群体$pop(1)$,$t:=1$;
2. 对群体中的每一个染色体$pop_i(t)$,计算其适应值$f_i=fitness(pop_i(t))$
3. 若满足停止条件，则算法停止；否则，以概率$p_i=f_i/\sum_{j=1}^Nf_j$从$pop(t)$中随机选择一些染色体构成一个新种群$newpop(t+1)={pop_j(t)\vert j=1,2,\cdots,N}$
4. 以概率$p_c$进行交叉产生一些新的染色体，得到一个新的群体$crosspop(t+1)$。
5. 以一个较小的概率$p_m$使染色体的一个基因发生变异，形成$mutpop(t+1)$;t:=t+1,成为一个新的群体$pop(t+1)$;返回Step 2。

流程图：

4. 什么是群智能算法

5. 粒子群智能优化算法的基本原理

6. 粒子群算法流程

1. 初始化每个粒子。即在允许范围内随机设置每个粒子的初始位置和速度。

2. 评价每个粒子的适应度。计算每个粒子的目标函数

3. 设置每个粒子的$p^i$。对每个粒子，将其适应度与其经历过的最好的位置$p^i$进行比较，如果优于$p^i$，则将其作为该粒子的最好位置$p^i$。

4. 设置全局最优值$p^g$。对每个粒子，将其适应度与群体经历过的最好位置$p^g$进行比较，如果优于$p^g$，则将其最为当前群体的最好位置$p^g$。

5. 更新粒子的速度和位置。根据式(7.1)更新粒子的速度和位置。

6. 检查终止条件。如果未达到设定条件(预设误差或者迭代的次数)，则返回第二步。

第七章

1. 什么是专家系统？专家系统的特点

定义：

特点：

2. 专家系统的工作原理

3. 专家系统的一般结构

4. 什么是机器学习？了解机器学习的分类

​ 定义：

​ 分类：

第八章

1. 什么是人工神经网络？

2. 了解神经网络的结构和工作方式

结构：

• 前馈型（ 前向型）

  

• 反馈型

  

工作方式：

3. 掌握BP神经网络结构以及BP学习算法

结构：

多层前馈型

BP学习算法： P214

BP 学习算法是通过反学习过程使误差最小，因此选择目标函数为$minJ=\frac12\sum_{j=1}^{P_m}{(y_j^m-y_{xj})}^2$即选择神经网络权值使输出期望出$y_{sj}$与神经网络实际输出$y_j^m$之差的平方和最小。

4. 了解BP算法程序流程图

5. 掌握离散型Hopfield神经网络

P221

6. 会利用Hopfield神经网络设计分类器

P238 例8.2

更新于：Jul 28, 2022

AI