人工智能大抄

2 智能体

0. AI 定义与理性智能体

0.1. AI 的四种定义视角

教材常把 AI 定义分成四类：

本课更偏向：理性智能体 (rational agent)，即在给定感知和知识下，选择期望性能最好的行动。

0.2. 图灵测试

图灵测试关注机器是否能表现出与人类不可区分的智能行为。需要能力：

• 自然语言处理。
• 知识表示。
• 自动推理。
• 机器学习。
• 若是 Total Turing Test，还包括感知和机器人行动。

0.3. 理性智能体

理性不等于全知。理性智能体根据：

• 当前感知序列。
• 已有知识。
• 可执行行动。
• 性能度量。

选择能最大化期望性能的行动。

1. 智能体基础

1.1. 智能体定义

智能体通过传感器感知环境，通过执行器作用于环境。

1

agent = sensors + actuators + agent program

智能体函数：$f: \text{percept sequence} \to \text{action}$。注意输入是感知序列，不只是当前感知。

1.2. 理性智能体

理性智能体对每个可能感知序列，选择能最大化期望性能度量的行动。理性取决于：

• 性能度量。
• 先验知识。
• 可执行行动。
• 当前感知序列。

理性不等于：全知；永远成功；事后看最优。

1.3. PEAS

PEAS 用于描述任务环境：

• P Performance measure：性能度量。
• E Environment：环境。
• A Actuators：执行器。
• S Sensors：传感器。

例：自动驾驶出租车

• P：安全、准时、舒适、盈利、守法。
• E：道路、行人、车辆、交通灯、天气。
• A：方向盘、油门、刹车、喇叭、显示屏。
• S：摄像头、雷达、GPS、速度计、麦克风。

2. 环境与智能体类型

2.1. 环境类型

• 完全可观测：传感器能获得决策所需全部状态。
• 部分可观测：有隐藏状态或传感器噪声。
• 单智能体：只需考虑自身行动。
• 多智能体：其他智能体也会行动，可能合作或竞争。
• 确定性：当前状态和行动完全决定下一状态。
• 随机性：结果有概率分布。
• 片段式 (episodic)：每次决策互不影响。
• 序贯式 (sequential)：当前行动影响未来。
• 静态：智能体思考时环境不变。
• 动态：环境会变化。
• 半动态 (semidynamic)：环境不变但性能随时间变化，如限时考试。
• 离散：状态、时间、行动有限或可数。
• 连续：变量连续，如自动驾驶位置和速度。
• 已知：智能体知道行动结果模型。
• 未知：需要学习模型。

2.2. 智能体类型

2.2.1. 简单反射智能体
基于当前感知选择行动：if condition then action。适用于完全可观测环境。缺点：没有记忆。

2.2.2. 基于模型的反射智能体
维护内部状态：internal state = update(previous state, action, percept)。适用于部分可观测环境。

2.2.3. 基于目标的智能体
使用目标信息选择行动，常需要搜索/规划。例：目标 = 到达 Bucharest。

2.2.4. 基于效用的智能体
不只判断是否达成目标，还比较不同结果好坏。最大化期望效用：$\arg\max_a E[U(\text{Result}(a))]$。

2.2.5. 学习智能体
能通过经验改进性能。包含：performance element、learning element、critic、problem generator。

2.3. LLM Agentic AI（隔壁班补充）

隔壁班课件提到大语言模型驱动的 Agentic AI。可理解为：

• LLM 负责理解任务、规划步骤。
• 工具调用负责执行搜索、代码、数据库、网页等操作。
• 记忆模块保存上下文。

低概率概念题，了解即可。

3. 考试速查

3.1. 常见判断题

• 智能体函数输入是感知序列：对。
• 性能度量由智能体自己随意定义：错，通常由任务设计者给出。
• 简单反射智能体适合部分可观测复杂环境：错。
• 基于效用的智能体能处理目标之间的权衡：对。

3.2. 最后一分钟版

• PEAS：Performance, Environment, Actuators, Sensors。
• 理性 = 在给定信息下最大化期望性能。
• 环境分类：可观测/确定/片段/静态/离散/单智能体/已知。
• 智能体类型：简单反射、模型反射、目标、效用、学习。

3 问题求解与无信息搜索

问题建模，BFS，UCS，DFS，DLS，IDS，手画搜索树

目录：0. 快速定位 · 1. 基本概念 · 2. 无信息搜索算法 · 3. 建模与手算模板 · 4. 考试速查

0. 快速定位

• 题目问"怎样表示问题"：看"问题形式化五要素"。
• 题目问"哪个算法最优/完备/省空间"：看"搜索算法对比表"。
• 题目给搜索树问下一步扩展谁：看"队列规则"。
• 题目要求自己建模，如 2020 三位数变换题：看"状态必须包含什么"。

1. 基本概念

1.1. 问题求解智能体

问题求解智能体通常是 goal-based agent：先给出目标，再把当前世界抽象成状态空间，在状态空间中搜索一条从初始状态到目标状态的行动序列。

课件特别强调：这是 offline problem solving，即先搜索完整计划，再闭眼执行。若执行中才获得新信息，则属于 online problem solving，不是本章重点。

1.2. 问题形式化五要素

一个良定义问题通常包含：

1. 状态空间 (state space)：所有可能状态的集合。
2. 初始状态 (initial state)：搜索起点。
3. 行动/后继函数 (actions/successor function)：在某状态能做什么，做完到哪里。
4. 目标测试 (goal test)：判断状态是否满足目标。
5. 路径代价 (path cost)：路径总代价，通常是单步代价累加。

标准写法：$\text{Problem} = (\text{States, InitialState, Actions, TransitionModel, GoalTest, PathCost})$。课件有时把后继函数写成：$S(x) = \langle \text{action, successor state} \rangle, \dots$，其中单步代价写作 $c(x, a, y) \geq 0$。

1.2.1. 状态与节点不要混淆

• 状态 (state)：世界的一种配置，例如"人在 Arad"，“水壶水量为 $(0,8,3)$”。
• 节点 (node)：搜索树中的数据结构，通常包含：state、parent、action、path-cost $g(n)$、depth。

同一个状态可能在搜索树中出现多次，因为它可能由不同路径到达。

考试常见坑：如果题目有"上一步不能操作同一位"之类限制，这个限制会影响未来后继，因此必须放进状态，而不只是节点注释。

例：2020 三位数搜索题。状态不能只写三位数 567，还要写"上一次改变的是哪一位"：

1

state = (number, last_changed_digit)

初始状态可写：(567, None)，否则无法判断下一步是否违反"连续两步不可操作同一位"。

1.3. 搜索树与状态空间图

状态空间图：每个状态是一个节点；每个合法行动是边；图可能有环。

搜索树：根是初始状态；每条从根到某节点的路径表示一个候选计划；节点可以重复包含同一个状态；实际问题通常无法展开整棵树。

• 树搜索不检查重复状态，容易陷入环。
• 图搜索使用 explored/closed 集合，避免重复扩展。

1.4. 通用搜索框架

1
2
3
4
5
6
7
8
9
10
11
12

frontier = [initial node]
explored = empty
while frontier not empty:
    n = choose_node(frontier, strategy)
    if goal_test(n.state): return solution_path(n)
    add n.state to explored
    for each successor s of n.state:
        if s not in explored/frontier:
            add child node to frontier
        else if new path is better:
            update frontier
return failure

不同搜索算法本质区别在于 choose_node 和 frontier 的组织方式。

• 生成 (Generate)：计算出一个后继节点，并把它放进 frontier 里等待。
• 扩展 (Expand)：从 frontier 中按照 choose_node 取出要扩展的节点，并计算它所有的后继节点。

1.5. 评价搜索策略的四个指标

• 完备性 (completeness)：若存在解，是否一定能找到。
• 最优性 (optimality)：是否保证找到最低路径代价的解。
• 时间复杂度：通常用分支因子 $b$、最浅目标深度 $d$、最大深度 $m$ 表示。
• 空间复杂度：搜索过程中最多存多少节点。

符号：

• $b$：branching factor，每个节点最多后继数。
• $d$：最浅目标深度。
• $m$：搜索树最大深度，可能无限。
• $C^*$：最优解代价。
• $\varepsilon$：最小正单步代价。

2. 无信息搜索算法

2.1. 无信息搜索算法对比表

无信息搜索仅使用从问题定义中获取到的信息（初始状态，状态转移规则，目标状态测试条件），没有任何其他启发式信息。

• 2021 选择题：所有边代价为 1，没有启发式，又要求省空间并保证最优，选迭代加深 DFS。
• 2020 判断题：BFS 是 UCS 的特例。若每条边单步代价相同，UCS 按 $g$ 递增扩展，等价于按深度扩展，因此正确。

2.2. 广度优先搜索（BFS）

BFS 用队列：

1
2

1. pop from front
2. push children to back

性质：

• 按深度逐层扩展。
• 当所有边代价相同，第一次找到目标就是最浅目标，也是最优解。
• 空间爆炸严重，因为要保存整层 frontier。

考试手算规则：

1. 从左到右生成子节点。
2. 同层先生成者先扩展。
3. 若题目规定并列按字母序，按题目来。

2.3. 代价一致搜索（UCS）

BFS 的升级版，应对每步代价不同的情况。UCS 每次扩展 $g(n)$ 最小的节点，使用优先队列来选出 $g(n)$ 最小的节点：

$$g(n) \triangleq \text{从初始节点到 } n \text{ 的已知路径代价} = \text{父节点 } g + \text{cost}(p, n)$$

操作步骤：

1. 初始化：将起点放入优先队列，累计代价设为 0。准备一个空的"已探索集合"（记录去过的地方，防止绕圈）。
2. 循环检查队列：
   • 如果优先队列空了，说明找不到路，宣告失败。
   • 弹出队列中代价最小的节点。
   • 目标测试：如果这个节点是终点，宣告成功！直接输出到达这里的路径。
3. 扩展节点：
   • 将刚弹出的节点加入"已探索集合"。
   • 观察它的所有邻居节点，计算到达每个邻居的新累计代价（当前节点累计代价 + 走到邻居的单步代价）。
4. 状态更新（UCS 最关键的一步）：
   • 如果邻居既不在队列里，也不在已探索集合里 → 直接作为新发现加入优先队列。
   • 如果邻居已经在优先队列里，但你刚算出的新代价比队列里记录的代价更低 → 发现了一条抄近道的路！立即更新队列里该节点的代价和父节点信息。
5. 返回第 2 步继续循环。

性质：

• 只要所有单步代价非负，且存在最小正代价，就完备。
• 保证最优。
• BFS 是"所有单步代价相同"的 UCS。

关键细节：

• 目标测试应该在弹出 frontier 准备扩展时做，而不是刚生成目标时就停。因为刚生成的目标路径不一定是最低代价。
• 若发现到同一状态的更低代价路径，需要更新 frontier。

2.4. 深度优先搜索（DFS）

DFS 用栈：

1
2

1. pop from top
2. push children so that leftmost child is expanded first

性质：

• 空间低，只保存当前路径和旁支。
• 不完备：无限深路径会卡住。
• 不最优：先找到的深层解可能代价很差。

适合：状态空间很大但解很深；只需要一个解；有深度上界或不会出现无限分支。

2.5. 深度有限搜索（DLS）

DLS 给 DFS 加深度限制 $l$：

• 深度超过 $l$ 不再展开。
• 可以返回三种结果：success、failure、cutoff。
• 若 $l < d$，找不到解；若 $l$ 太大，又退化为 DFS。

2.6. 迭代加深搜索（IDS）

IDS 依次运行：

1
2
3
4

DLS(limit=0)
DLS(limit=1)
DLS(limit=2)
...

为什么重复搜索仍然不亏？因为树中绝大多数节点在最深层，浅层重复展开的代价相对小。

性质：

• BFS 的完备性和单位代价最优性。
• DFS 的低空间复杂度。
• 单位代价搜索中非常常考。

2.7. 双向搜索

思路：同时从初始状态和目标状态搜索，直到两个 frontier 相遇。

复杂度：理想情况下从 $O(b^d)$ 降为 $O(b^{d/2})$。

限制：

• 必须能反向生成前驱。
• 目标状态要明确。
• 要能快速检测两个 frontier 是否相交。

3. 建模与手算模板

3.1. 状态空间建模模板

3.1.1. 罗马尼亚路径规划

• 状态：所在城市。
• 初始状态：Arad。
• 行动：沿道路开往相邻城市。
• 转移模型：$\text{Result}(\text{In(Arad)}, \text{Go(Sibiu)}) = \text{In(Sibiu)}$。
• 目标测试：是否在 Bucharest。
• 路径代价：道路距离之和。

3.1.2. 水壶问题

三壶容量为 12、8、3，加水目标 1 加仑：

1
2
3
4
5
6

state = (V12, V8, V3)
0 <= Vi <= Ci
initial = (0,0,0)
goal = any Vi == 1
actions = Fill(i), Empty(i), Pour(i,j)
path cost = 每步 1

倒水动作：

1
2
3

amount = min(Vi, Cj - Vj)
Vi' = Vi - amount
Vj' = Vj + amount

3.1.3. 传教士与野人

1
2
3

state = (M_left, C_left, Boat_left)
initial = (3,3,1)
goal = (0,0,0)

合法状态必须满足两岸安全：

1
2

M_left == 0 or M_left >= C_left
M_right == 0 or M_right >= C_right

动作：$\text{Cross}(m, c),\; 1 \leq m + c \leq 2$。该题检查重复状态非常必要，因为动作可逆，树搜索会反复过河。

3.2. 2020 三位数 A* 题的状态设计

题意：从三位数 $S$ 到 $G$，每步对某一位加 1 或减 1，不能进位/借位，不能进入 bad 集合，连续两步不能改同一位。

状态必须写：state = (digits, last_position)，例如：

1
2
3

(567, None)
(667, hundreds)
(677, tens)

后继函数：

1
2
3
4
5
6
7
8

for pos in {百位, 十位, 个位}:
    if pos == last_position: continue
    for delta in {-1,+1}:
        new_digit = digit[pos] + delta
        if 0 <= new_digit <= 9:
            new_number = replace(number, pos, new_digit)
            if new_number not in bad:
                successor = (new_number, pos)

路径代价：

1
2

每步 cost = 1
g(n) = 已移动步数

可采纳启发函数：$h(n) = |\text{当前百位} - \text{目标百位}| + |\text{当前十位} - \text{目标十位}| + |\text{当前个位} - \text{目标个位}|$。

理由：每一步只能改变一位且只能改变 1，因此至少需要各位数字差值之和这么多步。bad 集合和"不可连续改同一位"只会增加所需步数，不会让它更少。

若想更紧但仍简单，可考虑由于"不能连续改同一位"造成的额外等待，但考试一般写曼哈顿数字差即可。

3.3. 搜索题手算答题框架

对任何搜索树题：

1. 写 frontier 的排序依据。
2. 写已扩展节点。
3. 对每个 frontier 节点标关键值：
   • BFS/DFS：深度和生成顺序。
   • UCS：$g(n)$。
   • Greedy：$h(n)$。
   • A*：$f(n)=g(n)+h(n)$。
4. 选最优先节点。
5. 并列时按题目规则：左到右、字母序、深度优先等。

3.4. 搜索树绘制

按照题目给定的扩展顺序。扩展一个结点时，给出所有合法的后继结点；节点按照扩展顺序进行标号，只有被扩展的节点标号，目标节点被扩展时停止。

4. 考试速查

4.1. 常见判断题

• BFS 在单位代价下最优：对。
• DFS 不一定完备：对，可能无限深。
• DFS 扩展节点一定不少于 A*：错，具体取决于图和启发式。
• UCS 可以处理非单位代价并保证最优：对，要求非负代价。
• 图搜索比树搜索一定更快：不绝对，但避免重复状态通常更稳。

4.2. 最后一分钟版

• 问题形式化：状态、初始、行动/转移、目标测试、路径代价。
• 节点比状态多：父节点、动作、路径代价、深度。
• BFS：单位代价最优，空间爆炸。
• UCS：按 $g$，非负代价最优。
• DFS：省空间，不完备不最优。
• IDS：单位代价最优且省空间，考试很爱。
• 有历史限制的题，历史变量要放入状态。

4 有信息搜索

A*，启发式函数，局部搜索

目录：0. 快速定位 · 1. 最佳优先与 A* 基础 · 2. 启发式性质与证明 · 3. 局部搜索 · 4. 考试速查

0. 快速定位

• 手算 A*：看"A* 搜索流程"和"罗马尼亚例题模板"。
• 判断启发式是否 admissible/consistent：看"两个定义"。
• 多个启发式比较：看"启发式支配关系"。
• 局部搜索：看"爬山/模拟退火/束搜索/遗传算法"。

1. 最佳优先与 A* 基础

1.1. Best-First Search

最佳优先搜索维护一个优先队列 frontier，每次扩展评价函数 $f(n)$ 最小的节点：

1
2
3
4
5
6
7

best_first_search(problem, f):
    frontier = priority queue ordered by f
    insert initial node
    while frontier not empty:
        n = pop_min(frontier)
        if goal(n): return solution
        expand n and insert/update children

不同的 $f(n)$ 得到不同算法：

• 贪心最佳优先搜索：$f(n)=h(n)$。
• A* 搜索：$f(n)=g(n)+h(n)$。
• UCS：$f(n)=g(n)$。

1.2. 启发函数 h(n)

$h(n)$ 估计从节点 $n$ 到目标的最小剩余代价，如果 $n$ 是目标，则 $h(n)=0$。

例：罗马尼亚地图中，$h(n)$ 可取城市到 Bucharest 的直线距离。启发式越接近真实剩余代价 $h^*(n)$，搜索越少；但如果高估，A* 最优性可能丢失。

1.3. Greedy Best-First Search

评价函数：$f(n) = h(n)$。

特点：

• 只看"离目标看起来多近"。
• 通常很快。
• 不保证最优。
• 在图搜索中若避免重复，有限状态空间下完备；树搜索遇到环或无限空间不一定完备。

常见错误：贪心不看已经走过多远，所以可能为了小 $h$ 绕远路。

1.4. A* Search

评价函数：$f(n) = g(n) + h(n)$，其中：

• $g(n)$：从初始状态到 $n$ 的已知实际路径代价。
• $h(n)$：从 $n$ 到目标的估计最小剩余代价。
• $f(n)$：经过 $n$ 到目标的总路径代价估计。

A* 每次扩展 $f$ 最小的节点。

1.5. A* 搜索流程

1
2
3
4
5
6
7
8
9
10
11
12

frontier = priority queue by f=g+h
explored = empty
while frontier not empty:
    n = pop node with smallest f
    if goal(n): return path
    add n.state to explored
    for each successor child:
        compute g(child), h(child), f(child)
        if child.state not seen:
            push child
        else if new g is smaller:
            update parent/g/f

若题目要求手算，每个节点写：Node: g=?, h=?, f=g+h=?。并列规则按题目给定；若没给，一般按生成顺序或字母序说明即可。

2. 启发式性质与证明

2.1. 可采纳启发式 Admissible Heuristic

定义：$0 \leq h(n) \leq h^*(n)$，即永不高估真实最小剩余代价。

结论：

• 树搜索 A* 使用可采纳启发式，保证最优。
• 图搜索 A* 通常还需要一致性来简单保证最优；若只可采纳但不一致，需要允许节点重开。

典型可采纳例子：

• 八数码错位块数：不在同一位置的块的数目。
• 八数码曼哈顿距离，水平竖直移动，由于每次只能移动一个棋子，不能交换两枚棋子的位置。
• 地图路径中的直线距离。
• 三位数变换题的各位数字差绝对值之和。

2.2. 一致启发式 Consistent Heuristic

定义，也叫单调性：$h(n) \leq c(n, a, n') + h(n')$（通过 $a$ 到达 $n'$），并且 $h(\text{goal}) = 0$。

直观：估计距离满足三角不等式。

重要结论：一致性 ⇒ 可采纳。

证明套路：沿着从 $n$ 到目标的最优路径反复套用三角不等式，中间的 $h$ 抵消，得到 $h(n) \leq h^*(n)$。

一致性的好处：

• A* 图搜索第一次从 frontier 弹出某状态时，该状态的最优 $g$ 已确定。
• 不需要重新打开 closed 节点。

2.3. 可采纳但不一致例子

构造路径：$A \xrightarrow{1} B \xrightarrow{10} G$

真实代价：$h^*(A) = 11,\; h^*(B) = 10,\; h^*(G) = 0$。

定义：$h(A) = 10,\; h(B) = 5,\; h(G) = 0$。

• 可采纳：$10 \leq 11,\; 5 \leq 10$。
• 不一致：

$$h(A) \leq c(A,B) + h(B) \\ 10 \leq 1 + 5 \quad \text{（错）}$$

2.4. 启发式支配关系（占优）

若两个启发式都可采纳，且对所有节点：$h_2(n) \geq h_1(n)$，则 $h_2$ 支配 $h_1$，通常扩展节点不多于 $h_1$，因为它更接近真实代价。

2021 判断题：若 $h_1$、$h_2$ 都可采纳：

$$h_3(n) = \max(h_1(n), h_2(n)) \\ h_4(n) = \min(h_1(n), h_2(n))$$

$h_3$ 仍可采纳，而且支配 $h_4$。所以在 A* 中通常更好。但"更好"若被严格理解为所有情况下扩展节点严格更少，则不一定严格；考试一般判断"max 不差于 min"。

2.5. A* 最优性证明核心

设最优解代价为 $C^*$。若 $h$ 可采纳，则最优路径上任意 frontier 节点 $n$ 有：

$$f(n) = g(n) + h(n) \leq g(n) + h^*(n) = C^*$$

任何次优目标 $G'$ 的：$f(G') = g(G') = C' > C^*$，所以 A* 不会在所有最优路径节点被处理前选中次优目标。

2.6. 加权启发式路径算法

作业题给：$f(n) = (2-w)g(n) + wh(n)$。

若 $0 \leq w < 2$，除以正数 $(2-w)$：$f'(n) = g(n) + [w/(2-w)]h(n)$。

为了保证最优，启发项系数不能超过 1：

$$\frac{w}{2-w} \leq 1 \;\Rightarrow\; w \leq 1$$

所以 $0 \leq w \leq 1$ 保证最优。

特殊情况：

• $w=0$：$f=2g$，等价 UCS。
• $w=1$：$f=g+h$，标准 A*。
• $w=2$：$f=2h$，等价贪心搜索。

2.7. 高估不超过 c 的启发式

若：$h(n) \leq h^*(n) + c$，则 A* 返回解代价 $C'$ 满足：$C' \leq C^* + c$。

证明模板：

1. A* 终止时选择目标 $G'$，所以 $C'=f(G')$。
2. 最优路径上存在 frontier 节点 $n$。
3. $f(n)=g(n)+h(n) \leq g(n)+h^*(n)+c = C^*+c$。
4. A* 选择 $G'$，所以 $C'=f(G') \leq f(n)$。
5. 得 $C' \leq C^*+c$。

2.8. 2020 三位数 A* 手算模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(1) 567(0) [g=0, h=3, f=3]
├── 467(1) [g=1, h=4, f=5]
├── 557(2) [g=1, h=4, f=5]
├── 568(3) [g=1, h=4, f=5]
├── 566(3) [g=1, h=4, f=5]
└── (2) 577(2) [g=1, h=2, f=3]
    ├── 477(1) [g=2, h=3, f=5]
    ├── 578(3) [g=2, h=3, f=5]
    ├── 576(3) [g=2, h=3, f=5]
    └── (3) 677(1) [g=2, h=1, f=3]
        ├── 678(3) [g=3, h=2, f=5]
        ├── 676(3) [g=3, h=2, f=5]
        └── (4) 687(2) [g=3, h=2, f=5]   <-- 注：此步 f=5 且 g=3 的节点有三个，这里随机选
            ├── 587(1) [g=4, h=3, f=7]
            ├── 688(3) [g=4, h=3, f=7]
            ├── 686(3) [g=4, h=3, f=7]
            └── (5) 787(1) [g=4, h=1, f=5]
                ├── 797(2) [g=5, h=2, f=7]
                ├── 788(3) [g=5, h=2, f=7]
                ├── 786(3) [g=5, h=2, f=7]
                └── (6) 777(2) [g=5, h=0, f=5]   <-- 目标节点

2.9. 2021 搜索树题通法

题目给一棵已经扩展 A、B 的树，问不同算法下一步扩展谁：

• DFS：看当前最深、最左/最右规则。
• UCS：算 $g(n)$，选最小。
• Greedy：看 $h(n)$，选最小。
• A*：算 $f(n)=g(n)+h(n)$，选最小。

注意：题目常规定"子节点从左到右展开；并列按字母序"，必须照做。

3. 局部搜索

3.1. Local Search 局部搜索

局部搜索不关心完整路径，只关心当前状态本身。适合：

• 状态空间巨大。
• 只要最终配置，不需要行动序列。

典型：N 皇后、排课、布局优化。

核心思想：

1
2
3

current = some state
repeat:
    move to a neighbor according to objective function

3.2. Hill-Climbing 爬山法

每步选择邻居中评价最好的状态。

优点：内存极小；实现简单。

缺点：

• 局部最优 (local maximum/minimum)。
• 平台 (plateau)：邻居评价一样，走不动。
• 山脊 (ridge)：需要一串绕行才能上升，单步贪心困难。

变体：

• 随机重启爬山：从多个随机初始点开始。
• first-choice hill climbing：随机看邻居，找到更好就走。
• stochastic hill climbing：按改进程度概率选择。

3.3. Simulated Annealing 模拟退火

允许以一定概率走向更差状态，避免局部最优。接受更差状态的概率：$P = \exp(\Delta E / T)$。若是最大化问题，$\Delta E = \text{value(new)} - \text{value(current)}$，更差时为负。温度 $T$ 越高越容易接受坏动作，越低越像爬山。

流程：

1
2
3
4
5
6
7
8

current = initial
for t = 1..:
    T = schedule(t)
    if T == 0: return current
    next = random neighbor
    DeltaE = value(next) - value(current)
    if DeltaE > 0: current = next
    else current = next with probability exp(DeltaE/T)

理论：若降温足够慢，可收敛到全局最优；实际中用于近似优化。

3.4. Local Beam Search 局部束搜索

同时保留 $k$ 个状态：

1
2
3
4

start with k random states
repeat:
    generate all successors of k states
    choose best k among all successors

区别于随机重启：

• 随机重启是多条搜索互不交流。
• 束搜索中好的状态会占据资源，信息会共享。

缺点：容易所有束集中到同一区域，失去多样性。

3.5. Genetic Algorithm 遗传算法

基本元素：

• 个体：候选解，通常编码为字符串。
• 适应度函数 (fitness)：评价个体好坏。
• 选择 (selection)：适应度高的更容易繁殖。
• 交叉 (crossover)：两个父代片段组合。
• 变异 (mutation)：随机修改少量基因。

流程：

1
2
3
4
5
6
7

population = random individuals
repeat:
    evaluate fitness
    select parents
    crossover
    mutate
    form next generation

优点：全局探索能力强。缺点：参数多、收敛慢、不保证最优。

4. 考试速查

4.1. 常见判断题

• 可采纳启发式永不高估：对。
• 一致启发式一定可采纳：对。
• 可采纳启发式一定一致：错。
• $\max(h_1, h_2)$ 若二者可采纳，仍可采纳：对。
• 贪心最佳优先搜索一定最优：错。
• A* 中 $g$ 是已经走过的代价，$h$ 是估计剩余代价：对。

4.2. 最后一分钟版

• Greedy：$f=h$，快但不最优。
• A*：$f=g+h$，$h$ 可采纳/一致时保证最优。
• Admissible：$h \leq h^*$。
• Consistent：$h(n) \leq c(n, n') + h(n')$。
• 一致推出可采纳。
• max 组合启发式比 min 更强。
• 局部搜索不保路径，只保当前状态；爬山怕局部最优，退火能偶尔走差。

5 约束满足问题

重点是回溯搜索、MRV/LCV、前向检查、AC-3、树结构 CSP。

目录：0. 快速定位 · 1. CSP 基础 · 2. 回溯与约束传播 · 3. 结构与典型题 · 4. 考试速查

0. 快速定位

• 题目让定义 CSP：看"CSP 三要素"。
• 手工求解地图染色/密码算术：看"回溯搜索改进"。
• 题目提 AC-3/弧相容：看"Arc Consistency 和 AC-3"。
• 问复杂度：看"复杂度常用结论"。

1. CSP 基础

1.1. CSP 三要素

约束满足问题由三部分组成：$\text{CSP} = (X, D, C)$

• $X = \{X_1, \dots, X_n\}$：变量集合。
• $D = \{D_1, \dots, D_n\}$：每个变量的取值域。
• $C$：约束集合，限制变量之间可同时取哪些值。

目标：给每个变量赋值，使所有约束同时满足。

例：地图染色

• 变量：每个地区，如 WA, NT, SA, Q, NSW, V, T。
• 域：$\{red, green, blue\}$。
• 约束：相邻地区颜色不同，如 $WA \neq NT$。

1.2. CSP 与普通搜索的区别

• 普通搜索状态可能是世界任意配置；CSP 状态通常是部分赋值：$WA = red,\; NT = green$。
• 行动是给一个尚未赋值变量赋值。
• 目标测试是所有变量都有值且所有约束满足。
• CSP 的优势：约束结构明确，可以用通用推理减少搜索。

1.3. 约束类型

• 一元约束：只涉及一个变量，如 $X \neq red$。
• 二元约束：涉及两个变量，如 $WA \neq NT$。
• 高阶约束：涉及多个变量，如 $\text{Alldiff}(A,B,C,D)$。

高阶约束常可转为二元约束，但可能引入额外变量。

2. 回溯与约束传播

2.1. 回溯搜索 Backtracking

朴素 DFS 会考虑变量顺序的排列，浪费巨大。CSP 通常用回溯：

1
2
3
4
5
6
7
8
9
10
11
12

BACKTRACK(assignment):
    if assignment complete: return assignment
    var = SELECT-UNASSIGNED-VARIABLE(assignment)
    for value in ORDER-DOMAIN-VALUES(var):
        if value consistent with assignment:
            add var=value
            inferences = INFERENCE(...)
            if inferences not failure:
                result = BACKTRACK(assignment + inferences)
                if result != failure: return result
                remove var=value and inferences
    return failure

回溯搜索一次只给一个变量赋值，不重复考虑变量排列。

2.2. 变量选择：MRV

MRV = Minimum Remaining Values，最少剩余值。选择当前合法取值最少的未赋值变量。

直觉：先处理最容易失败的变量，早点剪枝。

例：若 SA 只剩 1 种颜色，Q 还剩 3 种，则先选 SA。

2.3. 变量选择：Degree Heuristic

度启发式选择与最多未赋值变量相连的变量。常作为 MRV 并列时的 tie-breaker。

直觉：约束别人最多的变量越早赋值，越能减少后续分支。

2.4. 值选择：LCV

LCV = Least Constraining Value，最少约束值。选择对其他变量剩余取值删得最少的值。

直觉：保留后续灵活性。

与 MRV 的方向不同：

• MRV 选变量：优先最危险的变量。
• LCV 选值：优先最温和的值。

2.5. 前向检查 Forward Checking

每赋值一个变量，就删除邻居变量域中不再合法的值。若某个未赋值变量域变空，立刻回溯。

例：地图染色，赋 $WA=red$ 后，从 NT 和 SA 的域中删掉 red。

优点：简单有效。缺点：只看一步邻居，不能发现更深层的隐含冲突。

2.6. Arc Consistency 弧相容

对二元约束 $X_i \to X_j$，若对 $X_i$ 域中每个值 $x$，都存在 $X_j$ 域中某个值 $y$ 使约束满足，则称弧 $X_i \to X_j$ 相容。

若某个 $x$ 找不到支持值，就从 $D_i$ 中删除 $x$。

注意方向性：$X_i \to X_j$ 相容不代表 $X_j \to X_i$ 相容。

2.7. AC-3 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

AC3(csp):
    queue = all arcs (Xi, Xj)
    while queue not empty:
        (Xi, Xj) = pop(queue)
        if REVISE(Xi, Xj):
            if Di empty: return false
            for each Xk in Neighbors(Xi) except Xj:
                add (Xk, Xi) to queue
    return true

REVISE(Xi, Xj):
    revised = false
    for x in Di:
        if no y in Dj satisfies constraint(Xi=x, Xj=y):
            delete x from Di
            revised = true
    return revised

何时用：

• 搜索前先跑 AC-3，缩小域。
• 回溯中每次赋值后维护弧相容，称 MAC。

2.8. AC-3 复杂度

若：$n$ 个变量；每个变量域大小最多 $d$；$c$ 条二元约束。

• 每次 REVISE 最多 $O(d^2)$，每条弧最多被重新检查 $O(d)$ 次，常见结论：$O(cd^3)$。
• 树结构 CSP 可在线性量级求解，常见教材结论：$O(nd^2)$。作业题若问"树结构 CSP 上 AC-3 最坏复杂度"，通常写 $O(nd^2)$，因为树中边数 $O(n)$，每条边处理受限。

3. 结构与典型题

3.1. 树结构 CSP

若约束图是树，可以不回溯地求解：

1. 任选根，给变量排序，使父节点在子节点之前。
2. 从叶子到根，对每条边执行 RemoveInconsistent(Parent, Child)。
3. 从根到叶依次赋值：父节点定值后，给子节点选任一与父值相容的值。

复杂度：$O(nd^2)$。

若约束图不是树，可以考虑：

• cutset conditioning：枚举少量变量，使剩余图变成树。
• tree decomposition：树分解。

3.2. 局部搜索解 CSP

常用 min-conflicts：

1
2
3
4
5

start with complete random assignment
repeat:
    if assignment satisfies all constraints: return it
    choose a conflicted variable
    assign it a value minimizing number of conflicts

适合 N 皇后等大规模 CSP。缺点：不保证最优，也可能卡住，需要随机重启。

3.3. 密码算术题思路

例如：

1
2
3

  SEND
+ MORE
= MONEY

• 变量：S, E, N, D, M, O, R, Y。
• 域：数字 0–9。
• 约束：
  • $\text{Alldiff}(S,E,N,D,M,O,R,Y)$。
  • 首字母 $S \neq 0,\; M \neq 0$。
  • 每列加法和进位约束。

求解技巧：先写进位变量；使用 MRV（例如最高位常能推 $M=1$）；使用前向检查删域。

4. 考试速查

4.1. 常见考试问法

4.1.1. MRV、Degree、LCV 分别是什么？

• MRV：选剩余合法值最少的变量。
• Degree：选约束最多的变量。
• LCV：选排除别人合法值最少的值。

4.1.2. 前向检查与 AC-3 区别？

• 前向检查只在已赋值变量到未赋值邻居之间删值。
• AC-3 维护所有相关弧相容，能传播更远。

4.1.3. 弧相容是否保证全局一致？

不保证。弧相容只是局部一致，仍可能无解。

4.1.4. 为什么 CSP 回溯比普通 DFS 少？

因为赋值顺序的排列不会被当作不同路径重复搜索；同一部分赋值只考虑一次。

4.2. 最后一分钟版

• CSP = 变量 + 域 + 约束。
• 状态 = 部分赋值。
• MRV 选变量，LCV 选值。
• Forward checking：赋值后删邻居域。
• AC-3：维护弧相容，REVISE 删没有支持的值。
• 树结构 CSP 可 $O(nd^2)$ 求解。

6 博弈

Minimax，alpha-beta 剪枝

目录：0. 快速定位 · 1. 博弈建模与 Minimax · 2. Alpha-Beta 剪枝 · 3. 资源限制与扩展 · 4. 考试速查

0. 快速定位

• 给博弈树求值：看"Minimax 手算规则"。
• 问剪枝叶子：看"Alpha-Beta 手算规则"。
• 深度限制和评估函数：看"资源限制搜索"。
• MCTS：考试重点写不考，只保留概念。

1. 博弈建模与 Minimax

1.1. 博弈问题定义

问题定义：

• 两人轮流行动：玩家（MAX）试图最大化游戏结果，玩家（MIN）则试图最小化游戏结果。
• 零和：输、赢、平。
• 完全信息：两人都可以看到整个游戏的全部状态。
• 确定性：行动的结果是确定的。

例如井字棋、国际象棋、围棋。

形式化包含：

• 初始状态。
• 当前状态 $s$，游戏中棋盘或环境的当前配置。
• 当前行动方 $\text{Player}(s)$。
• 合法行动 $\text{Actions}(s)$。
• 转移模型 $\text{Result}(s,a)$，表示 $s$ 经过 $a$ 的后继状态。
• 终止测试 $\text{Terminal-Test}(s)$，用于判断游戏是否已经到达终局。
• 效用函数 $\text{Utility}(s, \text{player})$，当游戏结束时，用于评估当前终止状态的 player 最终得分或收益。

零和意味着：$\text{Utility}(s, \text{MAX}) + \text{Utility}(s, \text{MIN}) = 0$。

1.2. Minimax 原理

Minimax 算法是一个悲观算法，其假设对手非常强大，招招致命，为了让自己死得不太难看，选择能够最优化最坏结果的策略。

• 输入：当前状态 $s$，游戏规则 rule。
• 输出：下一步的行动 $a$，该行动能够让我的最低收益最大化，选择其他行动的最坏结果不可能比这个好。

操作：

1. 从 $s$，根据 rule 推导出全部的对局可能（博弈树）。
2. 从叶子节点往上，算出所有节点的 Minimax 值。
3. return $\arg\max_a \text{MinimaxValue}(\text{Result}(s, a))$。

MinimaxValue 计算方式：

1. 叶子节点：其效用值就是 Minimax 值。
2. Max 节点：取子节点中的最大值作为 Minimax 值。
3. Min 节点：取子节点中的最小值作为 Minimax 值。

1.3. Minimax 特性

• 完备性：如果博弈树是有限的，该算法是完备的。
• 最优性：当对手采用最优策略时，该算法保证能找到最优解。
• 时间复杂度：$O(b^m)$，其中 $b$ 是分支因子，$m$ 是树的最大深度。
• 空间复杂度：因为该算法基于深度优先探索，空间复杂度为 $O(bm)$。

2. Alpha-Beta 剪枝

2.1. 原理

Alpha-beta 返回与 minimax 完全相同的结果，但不展开不可能影响最终决策的分支。

含义：

• alpha：记录 Max 当前在探索博弈树的过程中，所能取得到的最好的最坏结果（最大值），如果探索某分支时发现所能取得的最好的最坏结果比 alpha 还小，直接剪掉该分支。
• beta：记录 Min 当前探索中，所能取得到的最好的最坏结果（最小值），若比 beta 大，则剪掉。

Minimax 的推导，采用深度优先遍历，有一个向下传递（给子节点提供初值）和向上汇报（给父节点提供更新依据）的过程。

初值：

• 根节点：$\alpha = -\infty,\; \beta = +\infty$。
• 其他节点：父节点提供初值。

更新：

• Max：$\alpha = \max(\alpha, \text{Min 返回值})$，比 $\alpha$ 大就更新。
• Min：$\beta = \min(\beta, \text{Max 返回值})$，比 $\beta$ 小就更新。

剪枝：

• 一句话：当在一个节点得到子节点返回值 $v$ 并更新后，若 $\alpha \geq \beta$，该节点不再探索后续子节点，也不向父节点返回值。
• 两句话：
  • MAX 节点：若当前值 $v \geq \beta$，剪掉剩余子节点。
  • MIN 节点：若当前值 $v \leq \alpha$，剪掉剩余子节点。

2.2. Alpha-Beta 手算规则

从左到右搜索时：

1. 根节点：$\alpha = -\infty,\; \beta = +\infty$。
2. 下传当前 $(\alpha, \beta)$ 窗口。
3. 从左到右依次看子节点的值 $v$。
4. MAX 节点不断更新 $\alpha = \max(\alpha, v)$。
5. MIN 节点不断更新 $\beta = \min(\beta, v)$。
6. 一旦 $\alpha \geq \beta$，当前节点后面没看的兄弟分支全部剪掉，该节点不用返回值，返回也不会导致父节点更新。
7. 若没有发生剪枝，照常返回 Minimax 值，更新父节点的 $\alpha$ 或 $\beta$。

答题时要注意：

• 看清当前节点是 Max 还是 Min，不要更新错了，尤其是回传的时候对父节点的更新。
• 哪个节点处剪枝。
• 被剪掉的是哪些叶子或子树。
• 已经访问过的节点不能算剪枝。

2.3. 正确性分析

若在 MIN 节点发现 $v \leq \alpha$：

• MAX 的祖先已经有一个选择能保证至少 $\alpha$。
• 当前 MIN 节点最终值只会更小或相等。
• MAX 永远不会选择这条路，所以剩余子节点无关。

若在 MAX 节点发现 $v \geq \beta$：

• MIN 的祖先已经有一个选择能把结果压到至多 $\beta$。
• 当前 MAX 节点最终值只会更大或相等。
• MIN 永远不会允许这条路，所以剩余子节点无关。

2.4. 剪枝效率

• 最坏排序：几乎不剪，$O(b^m)$。
• 最优排序：约 $O(b^{m/2})$，相当于深度翻倍。

所以实际程序常先用启发式排序，把看起来好的行动放前面。

3. 资源限制与扩展

3.1. 资源限制搜索

完整 minimax 太深时，用深度限制：

1
2

Cutoff-Test(s, depth)
Eval(s)

当达到深度限制或状态足够稳定时，用评估函数估计效用。

典型写法：

1
2
3
4

H-Minimax(s, depth):
    if terminal(s): return utility(s)
    if depth == 0: return Eval(s)
    ...

2020 题问深度为 3 和深度为 4 时选择不同，原因通常是：深度限制下叶子值只是评估值，不一定等于真实终局效用；看得更深后会修正浅层误判。

3.2. 评估函数

评估函数应：

• 与真实胜率/效用相关。
• 计算快。
• 对非终局状态给出合理排序。

井字棋作业例子：$\text{Eval}(s) = 3X_2(s) + X_1(s) - (3O_2(s) + O_1(s))$

其中：

• $X_n$：恰好有 $n$ 个 X 且无 O 的行/列/对角线数。
• $O_n$：恰好有 $n$ 个 O 且无 X 的行/列/对角线数。

3.3. Horizon Effect 水平线效应

深度限制可能把必然发生的坏事推到搜索边界之外，导致评估函数看不见。

缓解：

• quiescence search：在局面剧烈变化时继续搜到稳定局面。
• iterative deepening：逐步加深并保留当前最好结果。

3.4. 随机博弈 Expectiminimax

若有随机事件，如掷骰子，加入 chance 节点。递归：

• MAX 节点取最大。
• MIN 节点取最小。
• Chance 节点取期望：$\sum_i P(i) * \text{value}(\text{child}_i)$。

低概率考，记住 chance 节点不是 max/min，而是加权平均。

3.5. 不完全信息博弈

如牌类游戏，玩家不知道完整状态。核心概念：

• belief state：对可能真实状态的概率分布。
• information set：玩家无法区分的一组状态。

本课只需概念了解。

3.6. MCTS 蒙特卡洛树搜索（不考）

来源：隔壁班 MCTS.pdf。考试重点写"蒙特卡洛不考"，这里只保留概念。

MCTS 四步：

1. Selection：从根按策略选择到叶子。
2. Expansion：扩展一个新节点。
3. Simulation/Rollout：随机模拟到终局。
4. Backpropagation：把结果回传更新访问次数和价值。

常用 UCB/UCT 平衡探索与利用：$\text{UCT} = \text{exploitation} + \text{exploration}$。

直观：

• exploitation：选择平均回报高的动作。
• exploration：给访问次数少的动作机会。

AlphaGo 使用过 MCTS，但细节不作为本课考试重点。

4. 考试速查

4.1. 常见判断题

• Minimax 假设对手也最优：对。
• Alpha-beta 会改变 minimax 的最终值：错。
• Alpha-beta 剪枝效果与节点顺序无关：错。
• MAX 节点取子节点最大值，MIN 节点取最小值：对。
• 随机节点取最大值：错，应取期望。

4.2. 最后一分钟版

• Minimax：MAX 取 max，MIN 取 min，自底向上回传。
• Alpha：MAX 已知最好下界；Beta：MIN 已知最好上界。
• 剪枝条件：$\alpha \geq \beta$。
• MAX 节点 $v \geq \beta$ 可剪；MIN 节点 $v \leq \alpha$ 可剪。
• Alpha-beta 不改变答案，只减少展开。
• 深度限制时叶子值是评估值，不一定是真实终局值。

概率与贝叶斯网络大抄

主线：现实中的智能体不能只靠"真/假/未知"行动；概率给出信念程度，完整联合分布原则上能回答所有概率查询，但规模太大；独立性和条件独立性压缩联合分布；贝叶斯网络把条件独立结构画成图，并用枚举、变量消元、朴素贝叶斯等方法做推理和分类。

目录：0. 一句话总图 · 1. 为什么 AI 需要概率 · 3. 概率分布 · 4. 条件概率/乘法/链式 · 5. 用完整联合分布做推理 · 7. 条件独立 · 8. 贝叶斯公式 · 9. 多证据贝叶斯和朴素贝叶斯 · 10. 概率分布从哪里来 · 11. 贝叶斯网络 · 12. d-separation · 13. 如何构建贝叶斯网络 · 14. 精确推理 · 15. 按图写联合分布和按图判独立 · 16. 朴素贝叶斯作为贝叶斯网络 · 17. 考试速查 · 18. 常见坑 · 19. 最后一页压缩版

0. 一句话总图

逻辑推理问的是：$KB \models \alpha$

概率推理问的是：$P(\alpha \mid e)$

也就是"已经看到证据 $e$ 后，结论 $\alpha$ 有多可信"。第 13 章先给概率语言本身，第 14 章再给一种紧凑表示概率分布的图模型：贝叶斯网络。

这两章的知识可以串成一条链：

1. 不确定性来自部分可观察、传感器噪声、行动结果不确定、模型太复杂、惰性和无知。
2. 概率把"不确定的命题"变成 $[0, 1]$ 中的信念程度。
3. 完整联合分布能回答一切查询，但对 $n$ 个布尔变量需要指数规模。
4. 边缘化、条件化、乘法规则、链式法则是概率推理的代数工具。
5. 独立和条件独立能把巨大联合分布分解成小块。
6. 贝叶斯网络用有向无环图表达条件独立，用每个节点的 CPT 定义完整联合分布。
7. 查询时用枚举或变量消元把隐藏变量求和消去，最后归一化。
8. 朴素贝叶斯是最简单的贝叶斯网络之一，用强条件独立假设换取高效分类。

1. 为什么 AI 需要概率

1.1 逻辑不够用的地方

现实智能体很少能完全确定世界状态。例如出发去机场时，智能体要考虑路况、其他司机、天气、轮胎、交通报告和许多无法完整建模的因素。

如果只用逻辑规则，容易出现两个极端：

• 规则太强，会推出错误结论，例如"提前 25 分钟出发一定能赶上飞机"。
• 规则太弱，必须列出所有例外，最后得到难以行动的条件句，例如"如果桥上没事故、不下雨、轮胎没坏、路上不堵……那么可以赶上"。

概率推理把这种问题改写成：

$$P(\text{OnTime} \mid \text{Leave25}, e) = 0.04$$

这句话不保证一定到达，也不说完全不知道，而是给出在当前证据 $e$ 下的信念程度。

课件开头用三个任务提醒你：手写数字识别、文本分类、图像分割本质上都不是"确定地套规则"，而是在证据不完整、特征有噪声、类别边界不绝对清楚时做判断。概率模型就是给这些分类判断提供统一语言。

1.2 不确定性的来源

课件把不确定性来源分成几类：

• 真实随机性：有些过程本身就是概率性的，例如掷骰子、抛硬币。
• 惰性：严格列举所有例外太费劲，规则太大也难以使用。
• 理论无知：领域没有完整一致的理论，例如医学诊断。
• 实践无知：理论上相关因素存在，但当前个案没有收集到所有信息。
• 传感器噪声：观测结果不一定等于真实状态。
• 行动结果不确定：同一行动在不同隐藏状态下可能产生不同结果。

所以概率不是"世界必然随机"的同义词，它也可以表示智能体因为信息不足而产生的主观信念。

1.3 频率主义与贝叶斯观点

频率主义把概率看作长期重复试验中的极限频率：

$$P(A) = \lim_{N \to \infty} \frac{n_A}{N}$$

其中 $n_A$ 是事件 $A$ 在 $N$ 次机会中发生的次数。这个解释适合抛硬币、抽样检测等可重复实验。

贝叶斯观点把概率看作在不完整知识下对事件可信度的度量。例如"第三次世界大战发生的概率"无法靠大量重复试验定义，但仍可以讨论给定证据下的主观可信度。

AI 中常用贝叶斯观点，因为智能体面对的往往是单次决策、单个病人、单封邮件或单张图片。

1.4 概率和效用分工

概率回答"我相信什么"：$P(\text{ArriveOnTime} \mid a, e)$

效用回答"我偏好什么"：$U(\text{arrive, wait, miss})$

决策论把二者合起来：

$$\text{Decision theory} = \text{Probability theory} + \text{Utility theory}$$

如果提前 1440 分钟出发几乎一定赶上飞机，但要在机场过夜，是否值得取决于效用，而不只取决于概率。

3. 概率分布

3.1 先验概率和概率分布

先验概率是在没有新证据时对命题的信念：$P(\text{Cavity} = \text{true}) = 0.1$。

一个随机变量的概率分布给出它所有可能取值的概率。例如：

$$P(\text{Weather}) = \langle 0.72, 0.10, 0.08, 0.10 \rangle$$

它是归一化的：$\sum_w P(\text{Weather} = w) = 1$。

3.2 完整联合分布

完整联合分布给出一组随机变量每种完整赋值的概率。若变量为 $X_1, \dots, X_n$，完整联合分布就是：

$$P(X_1, \dots, X_n)$$

对 $n$ 个布尔变量，需要 $2^n$ 个原子事件概率；因为总和必须为 1，独立参数数目是：$2^n - 1$。

完整联合分布的优点是原则上能回答所有查询。缺点也非常致命：变量稍多就无法存储、无法人工填写、无法高效求和。

3.3 边缘分布和边缘化

边缘化就是把不关心的变量求和消掉。若有联合分布 $P(A, B)$，则：

$$P(A) = \sum_b P(A, b)$$

若变量更多：

$$P(A) = \sum_b \sum_c P(A, b, c)$$

更一般地，对命题 $\varphi$：

$$P(\varphi) = \sum_{\omega:\, \omega \models \varphi} P(\omega)$$

其中 $\omega$ 是原子事件。

4. 条件概率、乘法规则和链式法则

4.1 条件概率

条件概率表示在证据 $B$ 已知为真后，对 $A$ 的信念：

$$P(A \mid B) = \frac{P(A, B)}{P(B)}$$

前提是：$P(B) > 0$。条件概率也满足概率公理。例如 $0 \leq P(A \mid e) \leq 1$。对变量 $A$ 的所有取值 $a_1, \dots, a_k$：$\sum_{i=1}^{k} P(A = a_i \mid e) = 1$。布尔变量有：$P(\lnot a \mid e) = 1 - P(a \mid e)$。

4.2 乘法规则

条件概率定义可改写为乘法规则：

$$P(A \land B) = P(A \mid B)P(B)$$

也可以写成：$P(A \land B) = P(B \mid A)P(A)$。因此：$P(A \mid B)P(B) = P(B \mid A)P(A)$。

4.3 链式法则

链式法则由乘法规则反复使用得到：

$$P(X_1, \dots, X_n) = \prod_{i=1}^{n} P(X_i \mid X_1, \dots, X_{i-1})$$

例如：

$$P(A, B, C) = P(A \mid B, C)\,P(B \mid C)\,P(C)$$

也可以按其他顺序写：$P(A, B, C) = P(C \mid A, B)\,P(B \mid A)\,P(A)$。

没有独立性假设时，不能随便把联合概率拆成 $P(A)P(B)P(C)$。但链式法则永远成立，只是条件项可能很复杂。

5. 用完整联合分布做推理

5.1 枚举推理思想

如果手里有完整联合分布，任何查询都可以通过枚举原子事件来做。查询 $P(Y \mid E = e)$，设隐藏变量为 $H = X - Y - E$，则：

$$P(Y \mid E = e) = \alpha\, P(Y, E = e)$$

其中：

$$P(Y, E = e) = \sum_h P(Y, E = e, H = h)$$

归一化常数 $\alpha$ 让查询变量所有取值的概率和为 1。

5.2 归一化

很多推理题不必先算分母，可以先算未归一化向量。例如：

$$P(\text{Cavity} \mid t) = \alpha\, P(\text{Cavity}, t)$$

若求和得到 $P(\text{Cavity}, t) = \langle 0.12, 0.08 \rangle$，则归一化：

$$\alpha = \frac{1}{0.12 + 0.08} = 5$$

所以：$P(\text{Cavity} \mid t) = \langle 0.6, 0.4 \rangle$。

考试中常写成 $Q(x) = P(x, e)$，再用：

$$P(x \mid e) = \frac{Q(x)}{\sum_{x'} Q(x')}$$

5.3 完整联合分布推理的问题

若最大变量取值数为 $d$，变量数为 $n$，枚举完整联合分布最坏时间复杂度为 $O(d^n)$，存储完整联合分布也需要 $O(d^n)$。

此外还要问：这些 $O(d^n)$ 个概率从哪里来？这直接引出独立性、条件独立性和贝叶斯网络。

7. 条件独立

7.1 条件独立的定义

$A$ 和 $B$ 在给定 $C$ 后条件独立，记为 $A \perp B \mid C$，等价写法：

$$P(A \mid B, C) = P(A \mid C)$$

$$P(B \mid A, C) = P(B \mid C)$$

$$P(A, B \mid C) = P(A \mid C)P(B \mid C)$$

含义：在已经知道 $C$ 后，$B$ 不再给 $A$ 提供额外信息。

7.2 条件独立不等于独立

报警器例子：

• JohnCalls：John 打电话。
• MaryCalls：Mary 打电话。
• Alarm：警报响。

不观测警报时，John 打电话会提高 Mary 打电话的概率，因为它暗示警报可能响了：

$$P(\text{MaryCalls} \mid \text{JohnCalls}) \neq P(\text{MaryCalls})$$

但若已经知道警报状态，John 是否打电话不再影响 Mary 是否打电话：

$$P(\text{MaryCalls} \mid \text{Alarm, JohnCalls}) = P(\text{MaryCalls} \mid \text{Alarm})$$

所以二者不独立，但在给定 Alarm 后条件独立。

8. 贝叶斯公式

8.1 贝叶斯公式

由乘法规则 $P(A \land B) = P(A \mid B)P(B) = P(B \mid A)P(A)$ 得到贝叶斯公式：

$$P(A \mid B) = \frac{P(B \mid A)P(A)}{P(B)}$$

若把假设写成 $H$，证据写成 $e$：

$$P(H \mid e) = \frac{P(e \mid H)P(H)}{P(e)}$$

其中：

• $P(H)$ 是先验。
• $P(e \mid H)$ 是似然。
• $P(H \mid e)$ 是后验。
• $P(e)$ 是证据概率，也是归一化分母。

常用归一化写法：$P(H \mid e) = \alpha\, P(e \mid H)P(H)$。

8.2 为什么贝叶斯公式重要

很多领域中，因果概率容易给出，诊断概率才是我们想问的。

• 因果方向：$P(\text{Effect} \mid \text{Cause})$
• 诊断方向：$P(\text{Cause} \mid \text{Effect})$

贝叶斯公式把二者联系起来：

$$P(\text{Cause} \mid \text{Effect}) = \frac{P(\text{Effect} \mid \text{Cause})P(\text{Cause})}{P(\text{Effect})}$$

这也是为什么很多 AI 系统（如语音识别和机器翻译）会把难求的后验转为更容易估计的似然和先验。

8.3 全概率公式展开分母

若 $B_1, \dots, B_k$ 构成互斥完备划分，则：

$$P(A) = \sum_i P(A \mid B_i)P(B_i)$$

布尔情形：$P(A) = P(A \mid B)P(B) + P(A \mid \lnot B)P(\lnot B)$。

贝叶斯题里分母通常就是用全概率公式展开。

9. 多证据贝叶斯和朴素贝叶斯

9.1 多证据贝叶斯

若一个原因 $C$ 产生多个证据 $E_1, \dots, E_n$，贝叶斯公式给出：

$$P(C \mid E_1, \dots, E_n) = \alpha\, P(E_1, \dots, E_n \mid C)P(C)$$

如果给定原因 $C$ 后，各证据条件独立 $E_i \perp E_j \mid C$，则：

$$P(E_1, \dots, E_n \mid C) = \prod_i P(E_i \mid C)$$

于是：

$$P(C \mid E_1, \dots, E_n) = \alpha\, P(C) \prod_i P(E_i \mid C)$$

这就是朴素贝叶斯的核心。

9.2 朴素贝叶斯假设

朴素贝叶斯假设是：给定类别 $Y$ 后，所有属性 $X_1, \dots, X_n$ 条件独立。

$$P(X_1, \dots, X_n \mid Y) = \prod_i P(X_i \mid Y)$$

分类时：

$$\hat{y} = \arg\max_y P(y \mid x_1, \dots, x_n)$$

由贝叶斯公式：

$$\hat{y} = \arg\max_y P(y) \prod_i P(x_i \mid y)$$

注意：朴素贝叶斯不是说特征无条件独立，而是说它们在给定类别后条件独立。

9.3 文本分类

文本分类中：

• $C$：文档类别。
• $W_i$：第 $i$ 个词是否出现。

模型参数：$P(C = c)$、$P(W_i = \text{true} \mid C = c)$。

训练时：

$$P(C = c) = \frac{\#\{\text{类别为 } c \text{ 的文档}\}}{\#\{\text{全部文档}\}}$$

$$P(W_i = \text{true} \mid C = c) = \frac{\#\{\text{类别 } c \text{ 中包含词 } i \text{ 的文档}\}}{\#\{\text{类别为 } c \text{ 的文档}\}}$$

分类新文档：

$$\text{score}(c) = P(C = c) \prod_i P(W_i = w_i \mid C = c)$$

为避免连乘下溢，实际常取对数：

$$\log \text{score}(c) = \log P(C = c) + \sum_i \log P(W_i = w_i \mid C = c)$$

需要平滑，否则某个词从未出现会让整个乘积变成 0。最常见是拉普拉斯平滑：

$$P(W_i = \text{true} \mid C = c) = \frac{N_{ic} + 1}{N_c + 2}$$

其中 $N_{ic}$ 是类别 $c$ 中包含词 $i$ 的文档数，$N_c$ 是类别 $c$ 的文档数，布尔词特征有两个取值。

9.4 数字识别例子

手写数字识别可以把每个像素位置作为一个特征：$F_{ij} \in \{\text{on, off}\}$，类别是数字 $D \in \{0, 1, \dots, 9\}$。

朴素贝叶斯模型：

$$P(D, F_{11}, F_{12}, \dots) = P(D) \prod_{i,j} P(F_{ij} \mid D)$$

要学习的是类别先验 $P(D)$ 和每个数字下每个像素亮灭的条件概率表。它忽略了相邻像素之间的相关性，但换来了非常简单的学习和推理。

10. 概率分布从哪里来

10.1 三种来源

课件给了三种来源：

1. 专家给出：例如医生、工程师或领域专家直接估计条件概率。
2. 简单概率事实加代数推导：用乘法规则、链式法则、独立假设组合出联合分布。
3. 从数据中学习：机器学习的很大一部分就是学习概率模型的参数或结构。

专家估计并不简单，例如问"冷天时下雨概率是多少"就可能很难稳定回答。

10.2 最大似然估计

估计一个离散随机变量 $X$ 的分布时，最大似然估计使用经验频率：

$$\hat{P}(X = x) = \frac{N_x}{N}$$

其中 $N_x$ 是观测到 $X = x$ 的次数，$N$ 是总观测次数。这个估计最大化观测数据出现的似然：$L(\theta) = P(D \mid \theta)$。

10.3 最大似然的问题和先验

如果只抛一次硬币且结果为正面，最大似然会给 $\hat{P}(\text{Heads}) = 1$，这显然过于激进。课件强调一个基本思想：

• 证据很少时，估计应更多受先验影响。
• 证据很多时，估计应更多听数据。

这也是平滑和贝叶斯参数估计的动机。朴素贝叶斯中文本分类必须加平滑，就是为了避免小样本下把未见事件估为 0。

11. 贝叶斯网络

11.1 图模型是什么

概率图模型把概率分布和图论结合起来：

• 节点表示随机变量或变量组。
• 边表示变量之间的概率关系。

图结构帮助人理解模型，也帮助算法设计高效推理。图模型的价值：

1. 可视化复杂概率模型结构。
2. 从图中读出条件独立性质。
3. 把复杂推理和学习变成图上的操作。

有向图模型包括贝叶斯网络；无向图模型包括马尔可夫随机场。贝叶斯网络更常用于表示因果关系，马尔可夫随机场更适合表示软约束。

11.2 贝叶斯网络的语法

贝叶斯网络是一个有向无环图，即 DAG。它包含：

• 一组节点，每个节点对应一个随机变量。
• 有向边，$A \to B$ 表示 $A$ 直接影响 $B$，$A$ 是 $B$ 的父亲。
• 如果两个节点之间没有直接的边相连，这意味着它们在给定某些其他变量的条件下是条件独立的。

每个节点有一个条件概率分布：$P(X_i \mid \text{Parents}(X_i))$。注意是 $P(X_i \mid \text{Parents}(X_i))$ 即所有父亲的组合条件概率。离散情形中，这个条件概率分布通常写成 CPT（条件概率表），若没有父亲，就是先验概率。

11.3 贝叶斯网络的全局语义

贝叶斯网络的拓扑结构和所有 CPT 一起定义完整联合分布：

$$P(X_1, \dots, X_n) = \prod_i P(X_i \mid \text{Parents}(X_i))$$

这是贝叶斯网络最常用公式。题目给图和 CPT，要求写联合概率时，先按每个节点的父节点列出这一乘积。

例：若图为 $A \to C \leftarrow B,\; C \to D$，则：

$$P(A, B, C, D) = P(A)\,P(B)\,P(C \mid A, B)\,P(D \mid C)$$

若求某个具体原子事件，如 $P(a, \lnot b, c, d)$，就把对应真假值代入每个 CPT；遇到假值要用补概率：$P(\lnot X \mid u) = 1 - P(X \mid u)$。

11.4 参数量优势

完整联合分布对 $n$ 个布尔变量需要 $2^n - 1$ 个独立参数。

若每个布尔节点最多有 $k$ 个布尔父节点，每个 CPT 有 $2^k$ 行，每行只需一个参数：$O(n \cdot 2^k)$。如果 $k$ 很小，贝叶斯网络随变量数近似线性增长。

课件的报警器网络有五个布尔变量：Burglary、Earthquake、Alarm、JohnCalls、MaryCalls。完整联合分布需要 $2^5 - 1 = 31$ 个独立参数。按因果网络：

• Burglary → Alarm
• Earthquake → Alarm
• Alarm → JohnCalls
• Alarm → MaryCalls

参数数目为：$1 + 1 + 4 + 2 + 2 = 10$。这就是结构化表示的威力。

11.5 贝叶斯网络的局部语义

局部语义：给定父节点后，一个节点与它的所有非后代节点条件独立。若节点为 $X_i$，父节点为 $\text{Parents}(X_i)$，非后代集合为 $\text{NonDescendants}(X_i)$，则：

$$X_i \perp \text{NonDescendants}(X_i) \mid \text{Parents}(X_i)$$

课件结论：local semantics ⟺ global semantics。也就是说，局部条件独立断言和全联合分布的乘积分解是等价的。

12. 贝叶斯网络节点独立性判断（d-separation）

12.1 链式结构

结构：$X \to Y \to Z$

不观测 $Y$ 时，$X$ 可能影响 $Z$，二者通常相关。给定 $Y$ 后，路径被阻断：$X \perp Z \mid Y$。

直觉：如果已经知道中间状态 $Y$，更早的原因 $X$ 对更晚结果 $Z$ 不再提供额外信息。

12.2 共同原因结构

结构：$X \leftarrow Y \to Z$

$Y$ 是 $X$ 和 $Z$ 的共同原因。不观测 $Y$ 时，$X$ 和 $Z$ 通常相关；给定 $Y$ 后，路径被阻断：$X \perp Z \mid Y$。

直觉：如果已经知道共同原因，两个结果之间的相关性被解释掉。

12.3 共同结果结构

结构：$X \to Y \leftarrow Z$

$Y$ 是 collider，也叫共同结果或 V-structure。

• 不观测 $Y$ 及其后代时，路径阻断：$X \perp Z$。
• 但若观测 $Y$ 或 $Y$ 的后代，路径被打开：$X \not\perp Z \mid Y$。

这叫 explaining away。例子：下雨和球赛都会导致交通堵塞；若看到堵车，知道有球赛会降低"下雨导致堵车"的后验概率。

12.4 d-separation 判断步骤

判断 $A$ 与 $B$ 在给定证据集合 $E$ 后是否条件独立：

1. 把有向图当成无向图，列出 $A$ 到 $B$ 的所有路径。
2. 对每条路径检查是否被阻断。
3. 链式节点和共同原因节点若被观测，则阻断路径。
4. collider 节点若自身及其后代都未被观测，则阻断路径。
5. 只有所有路径都被阻断，才有条件独立。

考试记忆：

• 链和 fork：观测中间点会堵住。
• collider：默认堵住，观测它或它的后代会打开。

12.5 马尔可夫毯

一个节点的马尔可夫毯包括：父节点；子节点；子节点的其他父节点。

给定马尔可夫毯后，该节点与网络中其他所有节点条件独立：

$$X \perp \text{rest} \mid MB(X)$$

这是贝叶斯网络中局部推理和采样算法的重要概念；若考试只考概念，记清楚"父、子、子之父"。

13. 如何构建贝叶斯网络

13.1 一般构建算法

课件给出构建网络的方法：

1. 选择变量顺序：$X_1, \dots, X_n$。
2. 对 $i = 1$ 到 $n$，把 $X_i$ 加入网络。
3. 从更早变量 $X_1, \dots, X_{i-1}$ 中选择父节点，使：

$$P(X_i \mid \text{Parents}(X_i)) = P(X_i \mid X_1, \dots, X_{i-1})$$

4. 尽量选择满足这个条件的最小父集。

这样做保证：

$$P(X_1, \dots, X_n) = \prod_i P(X_i \mid X_1, \dots, X_{i-1}) = \prod_i P(X_i \mid \text{Parents}(X_i))$$

第一步来自链式法则，第二步来自父节点选择。

13.2 为什么因果顺序通常更好

若网络反映真实因果模式，通常：节点父节点更少；人更容易判断条件概率；专家更容易给出 CPT；网络更紧凑，推理可能更高效。

报警器例子用因果方向只需 10 个参数。如果采用非因果顺序（如先加 MaryCalls、再加 JohnCalls、再加 Alarm 等），判断条件独立会更难，参数可能增加到 13 个。

13.3 箭头不一定等于因果

贝叶斯网络的箭头真正编码的是条件独立结构，不一定是世界中的真实因果关系。如果模型里缺少关键变量，或者领域本身没有清晰因果结构，箭头可能只是在表达相关性。正确态度是：

• 因果方向常常更自然、更紧凑。
• 但 BN 的数学语义是联合分布分解和条件独立，不是因果干预语义。

13.4 望远镜作业题

变量：

• $N$：真实恒星数。
• $F_1, F_2$：两个望远镜是否失焦。
• $M_1, M_2$：两次测量结果。

合理因果结构：$N \to M_1,\; F_1 \to M_1,\; N \to M_2,\; F_2 \to M_2$。