UCB CS188：人工智能入门

AI 简介 Intro to AI

制作出合理的 rational 机器，其中合理被定义为：做出最大化期望效用的行为

AI 历史：

• 早期
• 逻辑驱动
• 基于知识的方法
• 统计学方法

本课程分为两部分：

• 从计算中获取知识：搜索与计划，强化学习
• 从数据/经验中获取知识：概率和推理，监督学习

一致搜索 Uniformed Search

搜索问题包括：

• 状态空间
• 后继函数
• 初始态
• 目标测试

搜索树与搜索状态图

深度优先搜索和广度优先搜索

迭代加深搜索：拥有 DFS 的空间优势和 BFS 的时间优势

启发式搜索 Informed Search

启发式 heuristic 是：一个估计某状态离目标的距离的函数，为一个特定的搜索问题设计

贪心搜索：扩展看起来最近的结点

一致花费由路径花费（后向花费 $g(n)$）排序，贪心由目标邻近（前向花费 $h(n)$）排序，A* 由两者的和排序，即

$$f(n) = g(n) + h(n)$$

可接受性 admissibility

• 不可接受（消极）假设通过边缘的陷阱好计划破坏了最优性
• 可接受（积极）假设让坏计划慢下来，但是不会超过真实的花费

因此，当 $0 \le h(n) \le h^*(n)$ 时，启发式 $h$ 是积极的

启发式的一致性：启发式的每个弧花费 <= 每个弧的实际花费

一致性蕴含可接受

树搜索：

• 如果启发式是可接受的，则 A* 最优
• UCS 是一种特殊情况（h=0）

图搜索：

• 如果启发式是一致的，则 A* 最优
• UCS 是最优的（h=0 的情况是一致的）

约束满足问题 CSP

约束满足问题 Constraint Satisfaction Problems

之前的搜索问题一般都要求给出路径，而这种特殊的问题则只需要满足目标即可

本质上是给一些变量赋值，使其满足约束条件

DFS 的一种优化——回溯 backtracking search

• 一次赋值一个变量
• 每次都会检查约束

这种方法有多个优化的维度：

过滤：早期检测不可避免的失败

以下几个过滤的方法：

前向检查：删除当加入现有的分配时，会破坏约束的值

一条弧的一致性 consistent：对于每个尾部的 x，都有头部的某个 y 能够在不违反约束的情况下分配

因此当 x 少了某个值时，y 也要被更新

当然，可以进一步推广到 k 一致性，之前讲的弧一致性相当于 2-consistency，但是越大的 k 计算的开销越大

顺序上也有优化的地方：

变量顺序——最小剩余值 Minimum Remaining Values：选择域中有最少合法的剩余值的变量

• “最小”：最具有约束，失败最快

值顺序——最小约束值 Least Constraining Value：使剩余变量失效的值最少的值（引入了重新应用过滤的开销）

问题的结构：

极端情况：独立的子问题（几乎不存在）

树状 CSP：有顺序，即选择一个根变量，以父在子前的顺序排序变量

• 后向移除：移除不一致的父结点和子结点的值
• 前向分配：使子结点与父结点的值一致

对于接近树形的 CSP，可以实例化一个变量，然后移除其邻居的域，使其成为树形

CSP 的迭代算法：

• 全部分配
• 如果未解决，则
  • 变量的选择：随机选择冲突的变量
  • 值的选择：最小冲突的启发，即选择破坏了最少的约束的值，类似于爬山

因此，这种局部算法通常更快，内存效率高，但是不完备且是次优的

类比爬山

退火算法引入了概率，使其有可能走出某个次高的山峰

使用其他智能体 Search with Other Agents

零和 zero-sum 游戏：完全对抗的

某个状态的值：从那个状态出发，可到达的最好结果

某一步是自己动，会寻求最大值；下一步轮到对手，会寻求最小值，构成了对抗搜索（Minimax）

这里我们假设双方都是完美的玩家，故一定是寻求最优解

这种算法类似于完全的 DFS，是指数时间复杂度的，因此需要优化

Alpha-Beta 剪枝：即最大最小剪枝

一种算法实现：

• $\alpha$：MAX 的最优选择
• $\beta$：MIN 的最优选择

max-value(state, a, b)
	v = -INF;
	for-each successor
		v = max(v, value(successor, a, b))
		if v >= b return v
		a = max(a, v)
	return v

min-value(state, a, b)
	v = +INF;
	for-each successor
		v = min(v, value(successor, a, b))
		if v <= a return v
		b = min(b, v)
	return v

另一个方法是限制深度

评估函数，通常是线性的

接下来就要考虑到不确定性了

期望最大化 expectimax 搜索：不再是最小化结点，而是可能性结点，计算其期望效用

可以使用随机化来限制资源——蒙特卡洛树搜索 Monte Carlo Tree Search

• 使用 rollout 来估计
• 选择性搜索

核心思想是将 rollout 分配给更好的、更不确定的结点，故上界置信度 Upper Confidence Bounds 的公式为：

$$UCB1(n) = \frac{U(n)}{N(n)} + C \times \sqrt{\frac{\log_N(\operatorname{Parent}(n))}{N(n)}}$$

其中 $N(n)$ 为结点 n 的 rollout，$U(n)$ 为 n 的父结点的总效用，$C$ 是一个用于权衡的常数

马尔科夫决策过程 MDP

MDP 的定义：

• 状态集合
• 动作集合
• 转移函数
• 回报函数
• 起始状态
• 有时有终止状态

马尔科夫 Markov 意味着动作的结果只取决于当前状态（无记忆性）

我们想要得到一整个最优策略 $\pi^*: S \to A$，注意之前的搜索只能得到一个状态的动作

每个 MDP 状态都像一颗期望最大化搜索树：

我们需要确定获取奖励的顺序（多还是少，早还是晚？），为了权衡，故引入奖励逐渐减少的因子 $\gamma$（通货膨胀），当然其最大的用处还是用于帮助算法收敛

搜索树存在两大问题：

• 状态重复——缓存起来
• 树无限增长——由于 $\gamma < 1$，树的较深的部分可以不用管

得到两者的关系：

$$V^*(s) = \max Q^*(s, a)$$

$$Q^*(s, a) = \sum_{s^{\prime}} T(s, a, s^{\prime})[R(s, a, s^{\prime}) + \gamma V^*(s^{\prime})]$$

连起来得到 Bellman 等式：

$$V^*(s) = \max \sum_{s^{\prime}} T(s, a, s^{\prime})[R(s, a, s^{\prime}) + \gamma V^*(s^{\prime})]$$

一种方法是通过值迭代计算：

• $V_0(s) = 0$
• $V_{k+1}(s) = \max \sum_{s^{\prime}} T(s, a, s^{\prime})[R(s, a, s^{\prime}) + \gamma V_k(s^{\prime})]$
• 每次迭代的时间复杂度：$O(S^2A)$

当然也有别的计算方法，如

$$Q^*(s, a) = \sum_{s^{\prime}} T(s, a, s^{\prime})[R(s, a, s^{\prime}) + \gamma \max Q^*(s^{\prime}, a^{\prime})]$$

策略提取 policy extraction：

$$\pi^*(s) = \arg \max \sum_{s^{\prime}} T(s, a, s^{\prime})[R(s, a, s^{\prime}) + \gamma V^*(s^{\prime})]$$

注意到对于值迭代，每个状态的 max 经常是不变的，而且策略通常比值收敛要早得多，故可以考虑策略

对于固定了策略 $\pi(s)$，则有

$$V^\pi(s) = \sum_{s^{\prime}} T(s, \pi(s), s^{\prime})[R(s, \pi(s), s^{\prime}) + \gamma V^\pi(s^{\prime})]$$

因此策略的估计效率就成了每次迭代 $O(S^2)$，由于没有了 max，变成了线性，可以用更快的求解方式

策略迭代 policy iteration：

• 策略估计：对于某个固定的策略（不一定是最优的），计算效用直到收敛
  • $V_{k+1}^{\pi_i}(s) = \sum_{s^{\prime}} T(s, \pi_i(s), s^{\prime})[R(s, \pi_i(s), s^{\prime}) + \gamma V_k^{\pi_i}(s^{\prime})]$
• 策略改进：使用单步期望搜索更新策略，直到收敛
  • $\pi_{i+1}(s) = \arg \max \sum_{s^{\prime}} T(s, a, s^{\prime})[R(s, a, s^{\prime}) + \gamma V^{\pi_i}(s^{\prime})]$

强化学习 Reinforcement Learning

强化学习和 MDP 类似，但是不知道 T 和 R，我们需要学习这些值，即在线学习

被动的强化学习：只能得到转移的流：$(s, \pi(s), s^{\prime}, R)$

基于模型的学习：基于经验得到近似的模型，然后求解值，如先估计出 $\hat{T}$ 和 $\hat{R}$

与此相对的是无模型的学习

直接计算：直接对样本求平均值

由于不知道 T 和 R，所以无法通过公式计算策略，但可以取一次行为的结果作为样本：$sample = R(s, \pi(s), s^{\prime}) + \gamma V_k^{\pi}(s^{\prime})$

然后 $V_{k+1}^{\pi}(s) = \frac 1n \sum_i sample_i$

时序差分学习 Temporal Difference Learning：从每次经验中学习（running average）

更新的公式为：$V^{\pi}(s) = (1 - \alpha) V^{\pi}(s) + (\alpha) sample$

一般写成：

$$V^{\pi}(s) = V^{\pi}(s) + \alpha (sample - V^{\pi}(s))$$

这公式是一种指数移动平均，即使得最近的样本更加重要

在更新策略时，可以发现 Q 值更有用，所以最好是学习 Q 而不是 V：

$$sample = R(s, a, s^{\prime}) + \gamma \max Q(s^{\prime}, a^{\prime})$$

Q 学习最终会收敛与最优策略，即使并不是最优行为，这种叫做 off-policy learning

为了鼓励探索一些之前未探索的情况，最简单的是 $\varepsilon$ 贪心，即有 $\varepsilon$ 的概率随机行动

当然可以使用探索函数来平衡，如：$f(u, n) = u + k / n$

因此，新的更新 Q 变为：$Q(s, a) = R(s, a, s^{\prime}) + \gamma \max f(Q(s^{\prime}, a^{\prime}), N(s^{\prime}, a^{\prime}))$

不同的探索方案有好坏之分，可以使用 regret 来定量评估，regret 是所有失误的花费的总和

但是，实际情况中，状态实在是太多了，无法全部都训练到，也无法在内存中保存相应的表格。于是基于特征的表示 feature-based representation 出来了，可以使用特征向量来描述状态，通常是线性的，如 $Q(s, a) = w_1 f_1(s, a) + w_2 f_2(s, a) + \dots$

更新 $w_i$ 以近似 Q：$w_i = w_i + \alpha (difference) f_i(s, a)$

贝叶斯网络的表示 Representation

由于直接表示复杂的关联分布是指数级增长的，难以保存和处理，所以使用贝叶斯网络 Bayes' Net 来简化为多个简单的、局部的分布

其中的“箭头”可以理解为因果，但表示的是两个随机变量间存在一些关系或影响

贝叶斯网络是一个有向无环图，每个结点都储存着其所有的条件分布，即 $P(X|a_1, \dots, a_n)$

贝叶斯网络隐式编码了独立的分布，这在其表示出了完全的赋值中有所体现（注意到该公式和链式法则的不同，其部分假定了独立性）：

$$P(x_1, \dots, x_n) = \Pi_{i=1}^n P(x_i | parents(X_i))$$

独立性 Independence

可以使用 D-seperation 算法来求解两个随机变量是否独立

三元组是最基本的组成部分，图中涂黑的表示已知：

然后找出两个目标之间的所有路径，如果有一条路径是 active 的，则两个随机变量不独立（类似于开关的串联/并联）

拓扑结构会限制分布：添加弧会增加能够表示的分布的集合，但代价是要储存的数据增加

推理 Inference

推理：想要从大量联合分布中得到类似于 $P(Q|E_1=e_1, \dots, E_n = e_n)$

最直接的方法就是通过枚举推理，即通过 join 大量的贝叶斯网络中储存的条件概率表，得到一张大联合分布表，然后删除该表中不需要的部分，并求和得到结论

注意到每次合并时都会 join 大量不需要的东西，所以可以使用变量清除 variable elimination，即交错着合并和清理

这里引入一个概念——因子 factor，用于表示 join 和删除后得到的一张张新表，其数学表示为 $P(Y_1 \dots Y_N | X_1 \dots X_M)$，其中 $X$ 或 $Y$ 的一些值可以小写，即选中的某个维度

数学上的表达：

• 枚举：$\sum_t \sum_r P(L|t) P(r) P(t|r)$
• 变量消除：$\sum_t P(L|t) \sum_r P(r) P(t|r)$

一般的变量消除步骤：

• 选择隐藏变量 H
• join 所有有 H 的因子
• 消除（求和）H

当然，选择 H 的顺序也有关系，一般要保证尽可能不出现较大的表

采样 Sampling

有时直接计算太慢了，所以可以通过采样来较快地得到比较准确的答案

先验采样 prior sampling：按照拓扑顺序，根据每个结点中的概率来随机生成样本，最后根据采的总样本直接计算出要求的概率

拒绝采样 rejection sampling：如果采到的某个值和已知的证据不同，可以直接拒绝（停止本次采样）

可能性加权 likelihood weighting：有时某个证据发生的概率是较低的，则可能拒绝大量的样本，所以可以每次要对该变量采样时，都直接视为该证据发生了，然后对得到的样本加权，其权重为 $w(z, e) = \Pi_{i=1}^m P(e_i | \operatorname{Parents}(E_i))$

吉布斯采样 Gibbs sampling：固定证据，一次全部采样，然后每次都在其余所有随机变量发生的前提下重新采样某个变量（宣称计算此概率比较简单，因为只关系到一个变量）

决策网络 & VPI Decision Networks & VPI

决策网络包括了概率结点，由自己控制的动作，以及依赖于两者的效用

一些记号：

• EU(leave)：采取行动 leave 的期望效用
• MEU($\phi$)：在没有任何信息的情况下的最大效应

信息价值 Value of Information(VPI)：在得知某个信息的前提下，新的 MEU 比之前的多出来的部分。即

$\operatorname{VPI}(E^{\prime}|e) = \operatorname{MEU}(e, E^{\prime}) - \operatorname{MEU}(e)$

信息对计算的影响：

VPI 的性质：

• 非负
• 不可加，因为两个信息之间可能有交集
• 顺序无关，$\operatorname{VPI}(E_j|e) + \operatorname{VPI}(E_k|e, E_j) = \operatorname{VPI}(E_k|e) + \operatorname{VPI}(E_j|e, E_k)$

我们这里讨论的信息都是 perfect 的，即数据是无噪音的，没有概率；相反，inperfect 的信息是带有随机的

隐式马尔科夫模型 Hidden Markov Models

我们之前学会了根据一系列的观察推理，但是引入时间，则 belief 会改变

这里引入马尔科夫模型来模拟状态的改变：

根据马尔科夫链的特点，随着时间的推移，最初的状态不重要，会呈现稳态分布

隐式马尔科夫模型的区别在于无法直接观测到状态，而是观测到该状态带来的一些证据

Kalman 过滤的核心思想是每次根据证据更新信念 $B_t(X) = P_t(X_t | e_1, \dots, e_t)$，随着时间的推移，更新 $B(X)$

得到更新的公式：

对时间更新：

$$P(x_t|e_{1:t-1}) = \sum_{x_{t-1}} P(x_{t-1}|e_{1:t-1}) \cdot P(x_t|x_{t-1})$$

对证据更新：

$$P(x_t|e_{1:x}) \propto P(x_t|e_{1:t-1}) \cdot P(e_t|x_t)$$

粒子滤波 Particle Filtering

有时状态空间实在太大了，很难精确推断甚至储存，所以可以近似求解

• 跟踪 X 的样本（粒子 particle）
• 粒子的数量较多，但是可以并行计算

时间推移：每个粒子都根据转移的模型移动：$x^{\prime} = \operatorname{sample}(P(X^{\prime}|x))$

观察：基于证据修改权重，然后重新采样：$w(x) = P(e|x)$