研究生课程：高级人工智能-期末复习

《高级人工智能》期末复习

概述部分

人工智能的三大主义：行为主义、联结主义、符号主义

图灵测试是做什么的？给几个论断，哪些是哪些不是？

图灵测试：一个人（C）在完全不接触对方（A和B）的情况下，和对方进行一系列的问答，如果在相当长时间内，他无法根据这些问题判断对方是人（B）还是计算机（A），那么，就认为该计算机具有同人相当的智能（即计算机是能思维的）。

搜索和优化部分

选择题

g(x)为从根节点到x节点的代价总和

h(x)为从x节点到目标节点的估计代价总和

代价一致搜索 f(x) = g(x)

完备性：肯定能找到最优解
最优性：找到的解花费最小
比A*慢一些
广度优先搜索是代价一致搜索的特例

贪婪搜索 f(x) = h(x)

不完备
不保证能找到最优解
深度优先搜索是贪婪搜索的特例

A*搜索 f(x) = g(x) + h(x)

启发函数是可采纳的，那么，其中是到最近目标的真实耗散。
启发函数是可采纳的，那么A* 树搜索是最优的
A*图搜索与树搜索的区别在于图搜索不允许访问相同结点
一致的：启发函数不仅仅要是可采纳的，沿路径的节点估计耗散值单调递增。
图搜索中，如果启发函数是一致的，A* 搜索是最优的。

遗传算法

简答题

蚁群优化算法和粒子群优化算法是群体智能优化算法的两个代表，请从蚁群优化算法和粒子群优化算法中任选一个阐述其基本原理、算法过程及适用范围。

粒子群优化算法

基本原理：

粒子群优化算法中的每个粒子模拟一只鸟，代表待求解问题搜索解空间中的一个潜在解，“飞行信息”包括粒子当前的位置和速度两个状态量。每个粒子都可以获得其邻域内其它个体的信息，对所经过的位置进行评价，并根据这些信息和位置速度更新规则，改变自身的两个状态量，随着这一过程的不断进行，粒子群最终能够找到问题的近似最优解。

算法过程：

初始化
- 初始化粒子群：每个粒子的位置和速度，即和
- 和
循环执行如下三步直至满足结束条件
- 计算每个粒子的适应度：
- 更新每个粒子历史最好适应度及其相应的位置，更新当前全局最好适应度及其相应的位置
- 更新每个粒子的速度和位置

适用范围：适用于求解连续解空间的优化问题

蚁群优化算法

基本原理：

蚁群算法是一种用来寻找优化路径的概率型算法。用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

算法过程：

首先将只蚂蚁随机放置在个城市，位于城市的第只蚂蚁选择下一个城市的概率为：

其中表示边上的信息素浓度，是根据距离定义的启发信息，和反映了信息素与启发信息的相对重要性

当所有蚂蚁完成周游后，按以下公式进行信息素更新：

其中: 为常数, 表示第只蚂蚁在本轮迭代中走过的路径，为路径长度，为小于1的常数，反映信息素挥发速度

适用范围：适用于求解离散解空间的优化问题，适用于在图上寻找最优路径

应用题

A*树搜索的最优性条件

启发函数是可采纳的，那么，其中是到最近目标的真实耗散。
启发函数是可采纳的，那么A* 树搜索是最优的

A*图搜索的最优性条件

一致的：启发函数不仅仅要是可采纳的，沿路径的节点估计耗散值单调递增。
图搜索中，如果启发函数是一致的，A* 搜索是最优的。

传教士和野人问题通常描述如下：三个传教士和三个野人在河的一边，还有一条能载一个人或者两个人的船，找到一个方法让所有的人都渡到河的另一岸，要求在任何地方野人数都不能多于传教士的人数（可以只有野人没有传教士）。

(1) 精确地形式化该问题，只描述确保该问题有解所必须的特性，画出该问题的完全状态图

(2) 用一个合适的算法实现和最优地求解该问题，检查重复状态是个好主意吗?

采用先深搜索、先广搜索以及图搜索都可以，注意检查重复状态，重复状态的检测避免程序陷入死循环。

(3) 这个问题的状态空间如此简单，你认为为什么人们求解他却很困难?

虽然状态空间比较简单，但是要检测重复状态是一个困难：另外，在当前状态选取下一个合法状态，要能够不漏举所有合法状态也存在困难，当在某个状态无下一个合法状态时，需要回溯，这些都使得人为求解它变得困难

逻辑部分

选择题

简答题

命题逻辑

已知知识库里包含如下的句子：

请用归结原理证明该知识库蕴含如下的句子：$\neg A \land \neg B $

Forward chain 证明7<3+9

kb中所有句子都为definite子句，请构造一种真值指派使得kb中所有子句为真

将所有的原子命题指派为True即可。

由于是definite子句，不可能包含负文字，只能包含正文字，因此单独的文字一定为正文字，也就一定为True
由于是definite子句，每一个非文字的子句中一定有一个文字是正文字，且子句内部一定使用析取符号连接，因此正文字一定为True，子句也一定为True
综上，所有子句都为True

归结原理及证明：

设计一个可靠但不完备的规则

知识库中是全部有理数的集合
算法：，为全部自然数的集合
因此算法是可靠的，但是并不完备，因为算法无法计算出任何的小数

描述语义蕴含、的作用

语义蕴含指的是有了知识表示后，额外推出其他的知识
是命题逻辑里面的连接词，用于知识表示（实际上是可以替代的，但是引入这个符号进行知识表示比较方便）

设计A*启发式函数来使归结次数最少

构想一个A启发式函数，使得A归结结果为最优，并证明

h(n)为集合中的最短子句的长度

一阶谓词逻辑

胜者为王，败者为寇

不到长城非好汉，到了长城就是好汉；两个句子是否语义等价，并证明

成绩好的人都很刻苦，刻苦的人，一定成绩好；两个句子是否语义等价，并证明

理发师只给不给自己理发的人理发

将如下的一阶谓词逻辑的句子转化为合取范式：（不需要包含存在量词）

构造一个一阶谓词逻辑的知识库和句子，使得的归结过程永远不会停止。

模糊逻辑

（刻画模糊量词、模糊修饰词等）

很少有成绩好的学生特别贪玩

模糊谓词：贪玩、成绩好
模糊修饰词：很、特别
模糊量词：很少

很少有成绩好的学生特别喜欢玩游戏

模糊谓词：贪玩、喜欢玩游戏
模糊修饰词：很、特别
模糊量词：很少

Prolog

普通编程的步骤：了解问题-收集条件-寻找解决方法-编程解决-将问题数据化-用程序运行数据-debug

逻辑编程的步骤：了解问题-收集条件-不寻找解决方法-将条件写进KB-将问题转换为fact-问query-寻找错误的事实

C :- A,B 如果AB，则implyC（definite 子句）

[E | L]：将list拆解成第一个是E，后面的剩下

trace 和 notrace是debug的过程

DFS+backward chaining

不教程序怎么算，只列出事实

Prolog缺点：

不做occur check，因此有些事实是错的但是也可能推导出来，也就是不sound
DFS可能造成无穷递归，对的也导不出来，不complete。与语句编写的顺序也有关系

深度学习部分

选择题

GNN

谱方法：在谱空间中定义卷积：

通过图傅里叶变换和卷积原理定义卷积
- 图数据符合幂律分布，造成了极大的挑战
主要挑战是在谱空间定义的卷积在结点空间并没有局部化

空间方法：在向量空间中定义卷积

卷积被定义为目标结点到它的所有邻居的一个加权平均函数
主要挑战是邻域的大小在结点之间差异很大，可能服从幂律分布

谱方法是空间方法的特例

谱方法通过特别的空间变换定义核函数
空间方法直接定义核函数

聚合，更新是什么？

图神经网络的框架：聚合邻居节点的信息从而更新中心节点的表示

GraphSAGE：从每个结点开始随机游走，采样个结点，不用临近度指标判断。然后通过聚合函数进行参数共享

图卷积网络（GCN）：通过归一化的拉普拉斯矩阵从不固定数量的邻居结点中聚合信息，通过特征变换共享参数

应用题

证明感知机不能表示异或逻辑

异或的逻辑为：


0	0	0
1	0	1
0	1	1
1	1	0

两个变量的感知机模型为

代入上面的异或逻辑：

，则
，则
，则
，根据上面三个式子是明显不可满足的

因此感知机不能表示异或逻辑

设计用于异或问题的二层感知机

（以下简答题目答案来源于shmily）

描述BP算法

BP算法由正向传播与反向传播两个过程组成。正向传播时，输入由输入层经过隐藏层到输出层；反向传播时，输出结果与真实结果通过损失函数计算误差，误差信号再沿相反方向传播至输入层，获得各层各单元的误差信号（梯度），并将其作为修正权值的依据。通过梯度下降算法更新权值，使得网络的整体误差迭代减小。

试论述在深度神经网络中BP算法遇到的困难，并说明为什么会出现“梯度消失”问题

当网络变深时，BP算法会遇到梯度消失或者梯度爆炸的现象，此时浅层的神经元几乎接受不到来自输出层的误差信号或者误差太大，无法更新其参数或参数剧烈波动。

根据链式求导法则，浅层参数的梯度来源于深层参数梯度的乘积。由于中间梯度矩阵的范数可能远小于1，再加上许多激活函数的导数小于1，随着传播层数的增多，误差信号反向传播的过程中以指数形式衰减，当传播到浅层时便出现了梯度消失现象。

简述对抗式生成网络（GAN）的基本原理及其学习算法

GAN的思想来源于博弈论当中的均衡理论，其由生成器G与判别器D构成。生成器G希望生成更接近于真实分布的数据，判别器则希望尽可能分辨所给数据是由生成器生成的还是从真实分布中采样的。

GAN的学习算法交替地更新判别器D与生成器G：

首先训练判别器D，

从真实分布采样数据；
从高斯分布采样数据，送入生成器G生成数据；
最小化损失函数；

接着训练生成器G，

从高斯分布采样数据，送入生成器G生成数据；
最小化损失函数；

重复进行以上各步骤直至收敛。

描述ResNet（ResNet的原理和结构图）

ResNet由如下多个Residual Block堆叠构成

残差网络容易优化恒等式函数，学习优化残差映射比原始映射更加容易，随着网络加深，网络至少不会变得更差，有效地缓解了梯度消失等现象；此外，残差连接隐式地扩展了模型的特征空间，可以看作一种模型集成。

利用RNN构建一个翻译器

采用编码器-解码器结构，二者都是RNN网络，示意图如下：

其中，编码器RNN接受输入(原文token) ，并通过RNN结构编码隐藏状态。编码器编码完成后所有隐藏状态聚合为背景向量。

解码器的RNN同样编码隐藏状态，并将编码的隐藏状态映射到预测结果，计算与间的损失来完成模型的训练

预测时，通过自回归与束搜索的方式得到翻译序列。

强化学习部分

选择题

强化学习基础

多臂赌博机：

一台赌博机有多个摇臂，每个摇臂摇出的奖励大小不确定，玩家希望摇固定次数的臂所获得的期望累积奖励最大

优化目标：期望累计奖励最大化

探索和利用的关系：

利用：按照贪心策略进行选择，最大化即时奖励
探索：选择贪心策略之外的行为，短期奖励会比较低，长期奖励会比较高

策略：

贪心策略
贪心策略
- 以概率按照贪心策略进行行为选择（利用）
- 以概率在所有行为中随机选择一个（探索）
乐观初值法：未发生之前，保持乐观的心态。每次摇完臂都会失望，所以下次会换个臂摇，鼓励探索
UCB行为选择策略：对Qt(a)做估计，但因为估不准（估不准与之前尝试的次数有关，尝试次数越多估的越准），所以对它做一个上界

马尔可夫状态过程的要素：

智能体（Agent）和环境（Environment）按照离散的时间步进行交互
智能体的状态S、智能体采取的行为A、获得的奖励R

奖励假设：最终目标是通过最大化累积的Reward实现的

策略学习方法：

动态规划
- 策略迭代：从初始策略开始，迭代进行策略估值和策略提升，最终得到最优策略
  - 策略估值：解给定的策略下的值函数，也就是预测当前策略下所能拿到的值函数问题。
  - 策略提升：根据当前策略的估值函数，寻找更优的策略（如果存在）
- 估值迭代：值迭代算法是策略评估过程只进行一次迭代的策略迭代算法，从初始状态估值开始，进行估值迭代，找到最优状态估值，按照贪心方式得到最优策略
- 从运算量角度看，值迭代方法中策略评估只需要一次迭代，需要的运算量更小，应该比策略迭代更快收敛。但是，通常在策略提升中间插入需要多次迭代的策略评估的算法，收敛的更快！这可能与值迭代算法的终止条件有关。值迭代算法的终止条件对象为值函数，策略迭代算法的终止条件对象为策略，结合之前gridworld中观察的现象（策略可能比值函数收敛的更快），所以策略迭代可能比值迭代更快收敛。
蒙特卡洛：（通过采样的方式，最后用样本的平均值作估值，是一种从经验中获得的方法）
- 从真实或者模拟的经验中计算状态（行动估值函数）不需要关于环境的完整模型
- 直接根据真实经验或模拟经验计算状态估值函数
- 不同状态的估值在计算时是独立的，不依赖于“自举”方法
时序差分：非平稳情形下的蒙特卡洛方法（恒定步长）
参数近似