0. 复习优先级

第一优先级：必会大题

1. 搜索算法：BFS、DFS、UCS、贪心搜索、A* 树搜索/图搜索。
   往年和作业都反复考“写扩展顺序、边缘集、路径、总代价”。lec2 明确覆盖搜索问题、状态空间图/搜索树、通用树搜索/图搜索、非启发式搜索、启发式搜索、A* 树搜索与图搜索。

2. 对抗搜索：Minimax、Alpha-Beta 剪枝。
   作业一和 2025 回忆题都考博弈树倒推值和 α-β 剪枝。lec4 覆盖游戏、对抗搜索、极大极小、Alpha-Beta、实时决策、MCTS。

3. ID3 决策树：信息熵、条件熵、信息增益、根节点选择。
   作业二第一题和 2025 回忆题第 8 题都是“只计算根节点”。lec6 中信息增益的核心思想是：好的划分使子节点不纯度加权平均最小，也等价于最大化信息增益。

4. 卷积、池化、Attention 计算。
   作业二直接要求卷积、最大池化、Q/K/V、Attention Score 和最终输出；2025 回忆题也考 padding 后卷积、最大池化和平均池化。

5. 概率推理 / 贝叶斯网络：贝叶斯公式、联合分布分解、条件概率计算。
   lec10 覆盖概率推理、贝叶斯网络、马尔可夫随机场、D 分离、变量消元、信念传播。概率推理本质上是“建模 + 推断”。

第二优先级：主观题高频

1. lec1 AI 基本理解：自然智能、人工智能、AI/ML/DL 关系、三大学派、AI 历史。
2. lec8 RNN/Attention/Transformer 理解：序列建模、RNN 为什么共享参数、Attention 为什么能处理长依赖。
3. lec9 强化学习理解：Agent、Environment、State、Action、Reward、Policy、Value、Actor/Critic。
4. 机器学习基本概念：监督学习、泛化、过拟合/欠拟合、模型选择、KNN、线性回归、逻辑回归、SVM、随机森林。

第三优先级：往年高频但需按老师课上是否讲过决定投入

一阶谓词逻辑、合一、子句集、归结、产生式表示、语义网络。2025 回忆题前几题出现合一、子句集、谓词/产生式/语义网络表示。 如果这部分本学期课上确实讲过，必须按大题准备；如果老师明确不在范围内，可降权。

---

lec1 人工智能概论

1.1 人工智能、机器学习、深度学习

人工智能 AI：研究如何使机器模仿人类认知功能的学科，例如学习、推理、规划、感知、解决问题。PPT 中将 AI 描述为“任何使计算机能够模仿人类行为的技术”，机器学习是“无需显式编程即可具备学习能力”，深度学习是“使用神经网络学习数据中的底层特征”。

可作答：

人工智能是使机器在某些任务上表现出类似人类智能行为的技术和学科，关注感知、推理、学习、规划、决策等能力。机器学习是人工智能的一种重要方法，强调从数据中学习规律而非人工编写规则。深度学习是机器学习的一类方法，通常利用多层神经网络自动学习特征表示。

AI / ML / DL 关系

• AI 是最大集合。
• ML 是 AI 的子领域。
• DL 是 ML 的子领域。
• 传统 AI 可以依赖人工规则、搜索、逻辑推理；机器学习依赖数据；深度学习依赖多层神经网络自动提取特征。

1.2 自然智能 vs 人工智能

自然智能：人类或动物在自然进化中形成的认知、学习、推理、适应和决策能力。
人工智能：用计算机系统模拟、扩展或实现部分智能行为。

例子：

• 自然智能：人类看到红灯停下、儿童通过少量样例学会识别猫狗。
• 人工智能：AlphaGo 下围棋、自动驾驶识别道路、推荐系统预测用户点击。

答题模板：

自然智能是生物体通过神经系统、经验和环境交互形成的智能能力，具有适应性、泛化性和情境理解能力。人工智能则是由人设计的算法和系统，通过搜索、逻辑、概率建模、机器学习等方法，在特定任务中模拟或实现智能行为。例如，人类根据经验判断天气属于自然智能，而天气预测模型根据历史数据预测降雨属于人工智能。

1.3 人工智能三大学派

常考简答：

1. 符号主义 / 逻辑主义

   • 观点：智能可以通过符号、规则、逻辑推理表示。
   • 代表方法：专家系统、知识表示、逻辑推理、搜索。
   • 优点：可解释性强。
   • 缺点：知识获取困难，难处理噪声和不确定性。

2. 连接主义

   • 观点：智能来自大量简单神经元连接形成的并行计算。
   • 代表方法：神经网络、深度学习。
   • 优点：擅长感知任务、特征自动学习。
   • 缺点：可解释性较弱，需要大量数据和算力。

3. 行为主义 / 进化主义 / 控制主义

   • 观点：智能体通过与环境交互、试错、反馈形成智能行为。
   • 代表方法：强化学习、机器人控制、遗传算法。
   • 优点：适合决策、控制、游戏等交互任务。
   • 缺点：训练成本高，奖励设计困难。

1.4 AI 历史主线

PPT 中 AI 简史包含：1943 大脑布尔电路模型、1950 图灵测试、1956 达特茅斯会议、1966 第一次 AI 寒冬、1980s 专家系统、1986 BP 普及、1985 贝叶斯网络、1995 SVM、2012 AlexNet、2016 AlphaGo 等。

可按三阶段理解：

• 符号 AI 阶段：逻辑、规则、搜索、专家系统。
• 统计 AI 阶段：概率模型、贝叶斯网络、SVM 等。
• 神经 AI / 深度学习阶段：神经网络、CNN、RNN、Transformer、强化学习。

---

lec2 搜索

2.1 搜索问题形式化

PPT 中搜索问题包含：状态空间、初始状态、每个状态下的动作、状态转移模型、后继函数、目标测试函数、动作代价函数；解是到达目标状态的动作序列，最优解是代价最小的解。

记忆模板：

$$Problem = (S, s_0, A(s), Result(s,a), G(s), c(s,a,s'))$$

• $S$：状态空间
• $s_0$：初始状态
• $A(s)$：状态 $s$ 下可执行动作
• $Result(s,a)$：执行动作后的后继状态
• $G(s)$：目标测试
• $c(s,a,s')$：代价函数
• 解：动作序列
• 最优解：总代价最小的动作序列

2.2 状态空间图 vs 搜索树

状态空间图

• 每个状态只出现一次。
• 边表示状态转移。
• 通常太大，不能完整存入内存。

搜索树

• 根是初始状态。
• 节点表示到达某个状态的一条路径。
• 同一状态可能因不同路径在树中出现多次。
• 树搜索不记录 explored set，可能重复访问甚至陷入环。

考试写搜索过程时必须写清：

• Frontier / 边缘集 / OPEN 表
• Explored / 已扩展集 / CLOSED 表
• 每次扩展哪个节点
• 新加入哪些节点
• 何时命中目标
• 最终路径和总代价

2.3 BFS 广度优先搜索

核心：按深度从浅到深扩展，队列 FIFO。

适用：

• 边代价相同或不考虑代价。
• 找最浅解。

性质：

• 完备：若分支有限且目标存在，则完备。
• 最优：仅当每步代价相同。
• 时间复杂度：$O(b^d)$
• 空间复杂度：$O(b^d)$

答题格式：

初始 frontier = [S]。每次取出队首节点扩展，将其未访问子节点按题目规定顺序加入队尾。直到目标节点出队或生成，按老师要求停止。最终路径由父指针回溯得到。

2.4 DFS 深度优先搜索

核心：一路向深处走，栈 LIFO。

性质：

• 空间小。
• 不一定最优。
• 有环时若无 visited 可能不完备。
• 如果题目给定节点顺序，必须严格按顺序压栈或扩展。

答题注意：

如果“按字母序扩展”，用栈实现时要注意压栈顺序可能与扩展顺序相反；考试手写时最稳妥是直接说明“每次选择当前节点按字母序第一个未访问后继”。

2.5 UCS 一致代价搜索

核心：每次扩展当前路径代价 $g(n)$ 最小的节点。

• Frontier 是按 $g(n)$ 升序的优先队列。
• 当目标节点被“取出扩展”时，得到最优解。
• 如果发现到同一节点的更小代价路径，要更新 frontier。

性质：

• 若所有边代价非负，UCS 完备且最优。
• 等价于 Dijkstra 的搜索版本。

答题格式：

$$frontier = {(node, path, g)}$$

每一步写：

1. 取出 $g$ 最小节点。
2. 加入 explored。
3. 扩展后继。
4. 若新路径更优，则更新 frontier。
5. 目标出队，停止。

2.6 贪心搜索

评价函数：

$$f(n)=h(n)$$

只看启发式估计 $h(n)$，不看已走代价 $g(n)$。

特点：

• 速度可能快。
• 不保证最优。
• 若启发式很差，可能走错。

2.7 A* 搜索

评价函数：

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

• $g(n)$：从起点到当前节点的实际代价。
• $h(n)$：当前节点到目标的估计代价。
• $f(n)$：经过该节点到目标的估计总代价。

A* 树搜索

不记录 explored set，同一状态可能重复出现。 若 $h(n)$ admissible，即不高估真实代价，则 A* 树搜索最优。

A* 图搜索

记录 explored set。 若要保证最优，通常要求启发式函数 consistent / monotone：

$$h(n) \le c(n,a,n') + h(n')$$

也就是满足三角不等式。

A* 作答模板

步骤	扩展节点	$g$	$h$	$f=g+h$	frontier
0	S	0	h(S)	h(S)	…

每次选 $f$ 最小的节点扩展。若 $f$ 相同，按题目规则，如字母序。

---

lec3 CSP 与局部搜索

3.1 CSP 定义

lec3 将 CSP 作为一种“识别问题”：目标本身重要，路径不重要；CSP 状态是结构化的变量赋值，目标测试是一组约束。

形式化：

$$P=(X,D,C)$$

• $X={X_1,\dots,X_n}$：变量
• $D={D_1,\dots,D_n}$：值域
• $C$：约束集合

PPT 中 CSP 解定义为“一致且完全的赋值”。

关键概念：

• 赋值 Assignment：给部分或全部变量赋值。
• 完全赋值 Complete assignment：所有变量都有值。
• 一致赋值 Consistent assignment：不违反任何约束。
• 解 Solution：完全且一致的赋值。

3.2 典型 CSP 例子

1. 地图着色

   • 变量：地区，如 WA, NT, Q, NSW, V, SA, T。
   • 值域：颜色集合 ${R,G,B}$。
   • 约束：相邻区域颜色不同。

2. N 皇后

   • 变量：每列皇后的行坐标 $Q_k$。
   • 值域：${1,\dots,N}$。
   • 约束：任意两个皇后不同行、不同列、不同对角线。

3. 数独

   • 变量：格子。
   • 值域：1–9。
   • 约束：行、列、宫满足 Alldiff。

3.3 回溯搜索 Backtracking

基本流程：

1. 选择一个未赋值变量。
2. 给它选择一个可能值。
3. 检查是否违反约束。
4. 若违反，回退。
5. 若所有变量赋值完且一致，得到解。

3.4 动态排序启发式

作业一 CSP 判断题涉及两个高频启发式：MRV 和 LCV。

MRV：Minimum Remaining Values

• 选择剩余合法取值最少的变量。
• 也叫“最受约束变量优先”。
• 目的：尽早暴露失败，减少搜索。

LCV：Least Constraining Value

• 对某个变量选值时，优先选择对其他未赋值变量限制最少的值。
• 目的：为后续变量保留更多选择。

注意：改变变量赋值顺序不会改变搜索树深度，因为深度通常等于变量数；但会改变搜索树规模，即减少实际访问节点数。这是作业一类似判断题的坑点。

3.5 弧一致性 AC-3

二元约束 $X_i, X_j$ 下，如果 $X_i$ 的每个取值都能在 $X_j$ 中找到至少一个兼容取值，则称弧 $X_i \to X_j$ 一致。

AC-3 思路：

1. 将所有弧加入队列。
2. 取出一条弧 $(X_i,X_j)$。
3. 删除 $D_i$ 中没有支持的值。
4. 若 $D_i$ 被修改，则把所有指向 $X_i$ 的相关弧重新入队。
5. 若某个值域为空，则无解。

3.6 局部搜索

区别于路径搜索，局部搜索通常维护一个完整赋值，然后不断改进。

• 爬山法：每次移动到更好的邻居；缺点是容易陷入局部最优、平台、山脊。
• 模拟退火：允许以一定概率接受更差解，温度逐渐降低；前期探索，后期收敛。
• 局部束搜索：同时保留 $k$ 个候选状态。
• 遗传算法：选择、交叉、变异，适合组合优化。

---

lec4 博弈与对抗搜索

4.1 游戏类型

lec4 将游戏定义为“包含超过 1 个智能体的任务环境”，分类维度包括确定性/随机性、完全信息/不完全信息、双人/多人、回合制/同时行动、零和/非零和。

标准博弈：确定性、回合制、双人、零和、完全信息。典型例子：国际象棋、跳棋、围棋。PPT 的标准博弈形式化包括初始状态、玩家函数、动作、转移模型、终止测试、效用函数。

形式化：

$$(s_0, Player(s), Actions(s), Result(s,a), TerminalTest(s), Utility(s))$$

4.2 零和博弈

零和博弈更准确说是“常数和博弈”：

• 一个玩家收益增加，另一个玩家收益减少。
• MAX 玩家希望最大化效用。
• MIN 玩家希望最小化效用。

4.3 Minimax 极大极小算法

递推定义：

$$V(s)= \begin{cases} Utility(s), & s \text{ 是终止节点}\\ \max_{a \in Actions(s)} V(Result(s,a)), & s \text{ 是 MAX 节点}\\ \min_{a \in Actions(s)} V(Result(s,a)), & s \text{ 是 MIN 节点} \end{cases}$$

考试题做法：

1. 从叶子节点往上倒推。
2. MAX 层取子节点最大值。
3. MIN 层取子节点最小值。
4. 根节点值就是最优对弈下的结果。
5. 根节点选择使值最优的动作。

4.4 Alpha-Beta 剪枝

核心思想：剪掉不会影响最终决策的分支。PPT 明确指出 Alpha-Beta 的核心是“剪除那些对最终决策不产生影响的搜索分支”，且节点探索顺序会影响剪枝效果。

定义：

• $\alpha$：当前路径上，MAX 已经能保证的最好值。
• $\beta$：当前路径上，MIN 已经能保证的最好值。

剪枝条件：

$$\alpha \ge \beta$$

也可记作：

• MAX 节点更新 $\alpha=\max(\alpha, 当前值)$。
• MIN 节点更新 $\beta=\min(\beta, 当前值)$。
• 一旦 $\alpha \ge \beta$，后续兄弟分支可剪。

作答时必须写：

• 当前访问顺序：从左到右。
• 每个内部节点值。
• 哪些叶子被剪。
• 剪枝发生时的 $\alpha$ 或 $\beta$ 值。

---

lec5 机器学习基础

5.1 机器学习定义

lec5 中机器学习定义为：赋予计算机无需显式编程即可从数据中学习的能力。

Tom Mitchell 定义：

对任务 $T$、性能指标 $P$、经验 $E$，如果系统在任务 $T$ 上的性能 $P$ 随经验 $E$ 增加而提升，则称系统从经验中学习。

考试答法：

• 任务 $T$：要完成什么。
• 性能 $P$：如何评价。
• 经验 $E$：训练数据或交互经历。

例子：

垃圾邮件分类：

• $T$：判断邮件是否垃圾。
• $P$：分类准确率、召回率、F1。
• $E$：带标签的历史邮件。

5.2 监督学习基本框架

数据集：

$$D={(x_1,y_1),\dots,(x_N,y_N)}$$

• $x_i$：输入特征。
• $y_i$：标签。
• $f:X\to Y$：未知真实函数。
• $h:X\to Y$：学习得到的假设。

目标：找到 $h\approx f$，使其在未见样本上表现好。

5.3 训练集、验证集、测试集

• 训练集：训练参数。
• 验证集：选择模型和调超参数。
• 测试集：最终评估泛化性能。

不能用测试集调参，否则测试结果失真。

5.4 欠拟合与过拟合

欠拟合

• 模型太简单。
• 训练误差高，测试误差也高。
• 解决：增加模型复杂度、增加特征、减少正则化、训练更久。

过拟合

• 模型过度记忆训练集噪声。
• 训练误差低，测试误差高。
• 解决：正则化、增加数据、数据增强、早停、降低模型复杂度。

5.5 KNN

KNN 思想：

1. 给定测试样本。
2. 计算它与训练样本距离。
3. 找最近的 $k$ 个邻居。
4. 分类任务投票，回归任务取平均。

特点：

• 非参数模型。
• 训练简单，预测慢。
• 对距离度量和特征尺度敏感。
• $k$ 小容易过拟合，$k$ 大容易欠拟合。

5.6 线性回归

模型：

$$\hat{y}=w^T x+b$$

平方损失：

$$L(w)=\sum_{i=1}^{n}(\hat{y}_i-y_i)^2$$

正则化：

$$L(w)=\sum_{i=1}^{n}(w^Tx_i-y_i)^2+\lambda \Omega(w)$$

• L2：$\Omega(w)=||w||_2^2$，使权重更平滑。
• L1：$\Omega(w)=||w||_1$，可产生稀疏权重。

---

lec6 分类、SVM、决策树、随机森林

lec6 大纲包含线性分类、逻辑回归、Softmax 回归、SVM、软间隔 SVM、核软间隔 SVM、决策树、随机森林。

6.1 逻辑回归

用于二分类。

Sigmoid 函数：

$$\sigma(t)=\frac{1}{1+e^{-t}}$$

模型：

$$P(y=1|x)=\sigma(w^Tx+b)$$

决策规则：

$$P(y=1|x)>0.5 \Rightarrow y=1$$

交叉熵损失：

$$L=-\sum_i[y_i\log \hat{y}_i+(1-y_i)\log(1-\hat{y}_i)]$$

理解：

• 输出不是类别，而是属于正类的概率。
• 交叉熵对“自信但错误”的预测惩罚很大。
• 线性可分时权重可能发散，因此需要正则化。

6.2 Softmax 回归

用于多分类。

$$P(y=k|x)=\frac{e^{w_k^Tx+b_k}}{\sum_j e^{w_j^Tx+b_j}}$$

交叉熵：

$$L=-\sum_i \log P(y_i|x_i)$$

6.3 SVM

核心思想：找最大间隔分类超平面。

线性可分硬间隔：

$$\min \frac{1}{2}||w||^2$$

约束：

$$y_i(w^Tx_i+b)\ge 1$$

软间隔引入松弛变量：

$$\min \frac{1}{2}||w||^2+C\sum_i \xi_i$$

约束：

$$y_i(w^Tx_i+b)\ge 1-\xi_i,\quad \xi_i\ge0$$

理解：

• $C$ 大：更重视训练错误，间隔可能小，过拟合风险大。
• $C$ 小：允许更多错误，间隔更大，泛化可能更好。

核 SVM：

• 用核函数隐式映射到高维空间。
• 常见核：多项式核、RBF 核。
• 用于处理非线性可分数据。

6.4 决策树与 ID3

熵

对于分类集合 $D$，若类别比例为 $p_1,\dots,p_K$：

$$H(D)=-\sum_{k=1}^{K}p_k\log_2p_k$$

二分类：

$$H(D)=-p\log_2p-(1-p)\log_2(1-p)$$

特殊值：

• 全是同一类：$H=0$
• 二分类各一半：$H=1$

条件熵

按属性 $A$ 划分：

$$H(D|A)=\sum_{v\in Values(A)}\frac{|D_v|}{|D|}H(D_v)$$

信息增益

$$Gain(D,A)=H(D)-H(D|A)$$

ID3 选择信息增益最大的属性作为划分属性。

ID3 大题模板

1. 统计总样本中各类别数量。

2. 计算父节点熵 $H(D)$。

3. 对每个属性：

   • 按属性取值分组。
   • 统计每组类别数量。
   • 计算每组熵。
   • 加权求条件熵。
   • 计算信息增益。

4. 比较所有 Gain。

5. 选择 Gain 最大的属性为根节点。

6.5 随机森林

随机森林 = 多棵决策树的集成。

两个随机性：

• 样本随机：Bootstrap 抽样。
• 特征随机：每次分裂只考虑部分特征。

优点：

• 降低单棵树过拟合。
• 泛化能力强。
• 对噪声较稳健。

---

lec7 深度学习、MLP、AE、CNN

lec7 覆盖深度学习、多层感知机 MLP、自动编码器 AE、卷积神经网络 CNN。

7.1 深度学习基本思想

PPT 定义：深度学习是通过多个非线性变换组成的架构，对数据中的高层抽象进行建模。

理解：

• 浅层特征：边缘、颜色、纹理。
• 中层特征：局部结构、部件。
• 高层特征：对象、语义概念。
• 深度网络可以自动学习层级特征，减少手工特征设计。

7.2 感知机与 MLP

单个感知机：

$$\hat{y}=g(w^Tx+b)$$

• $w^Tx+b$：线性组合。
• $g$：非线性激活函数，如 sigmoid、tanh、ReLU。

MLP：

• 输入层。
• 一个或多个隐藏层。
• 输出层。
• 层与层之间全连接。
• 多个非线性层叠加后可表示复杂函数。

为什么需要非线性激活？

如果没有非线性，多层线性变换仍然等价于一层线性变换，无法表示复杂非线性决策边界。

7.3 自动编码器 AE

结构：

$$x \rightarrow encoder \rightarrow z \rightarrow decoder \rightarrow \hat{x}$$

目标：

$$\min ||x-\hat{x}||^2$$

作用：

• 学习低维表示。
• 降噪。
• 表征学习。
• 异常检测。

7.4 CNN

PPT 中 CNN 典型结构是：输入层、卷积 + ReLU、池化、再卷积、再池化、后续层。

卷积计算

给定输入矩阵 $X$ 和卷积核 $K$，无 padding、stride=1 时：

$$Y_{ij}=\sum_{u,v}X_{i+u,j+v}K_{u,v}$$

输出尺寸：

$$H_{out}=\frac{H+2P-K_H}{S}+1$$ $$W_{out}=\frac{W+2P-K_W}{S}+1$$

其中：

• $H,W$：输入高宽。
• $K_H,K_W$：卷积核高宽。
• $P$：padding。
• $S$：stride。

注意：课上一般默认是深度学习里的 cross-correlation，即不翻转卷积核；考试按 PPT/作业示例来算，不要自行翻核。

Padding

作用：

• 保持空间尺寸。
• 让边缘像素也充分参与计算。
• 增大输出尺寸。

池化

最大池化：

$$Y_{ij}=\max(\text{窗口内元素})$$

平均池化：

$$Y_{ij}=\text{mean}(\text{窗口内元素})$$

作用：

• 降采样。
• 减少参数和计算。
• 增强局部平移不变性。
• 抑制过拟合。

---

lec8 RNN、Attention、Transformer

lec8 覆盖 RNN、带注意力的 RNN、Transformer 架构和 Self-Attention。

8.1 序列建模

语言模型目标：

$$P(w_i|w_1,\dots,w_{i-1})$$

也就是根据前文预测下一个词的概率分布。

PPT 中序列建模例子包括语言建模、语音识别、问答系统。

8.2 RNN 基本思想

RNN 处理输入序列：

$$x_1,x_2,\dots,x_T$$

隐藏状态：

$$h_t=f(W h_{t-1}+U x_t)$$

输出：

$$y_t=Vh_t$$

PPT 中 $h_t$ 被解释为编码来自所有过去时间步的信息。

两个核心假设：

1. 局部依赖 / 历史编码 过去信息可以压缩进隐藏状态 $h_t$。

2. 时间平稳性 / 参数共享 同一组参数 $W,U,V$ 在不同时间步复用。

优点：

• 适合序列数据。
• 参数不随序列长度线性增长。
• 可处理变长输入。

缺点：

• 长距离依赖困难。
• 梯度消失/爆炸。
• 串行计算，不易并行。

8.3 Attention

Attention 的本质：

对每个 query，根据它与所有 key 的匹配程度，对 value 加权求和。

Q、K、V：

$$q_i=W_Qx_i$$ $$k_i=W_Kx_i$$ $$v_i=W_Vx_i$$

对某个 $q_i$，注意力分数：

$$score_{ij}=q_i^Tk_j$$

Softmax 权重：

$$\alpha_{ij}=\frac{\exp(score_{ij})}{\sum_j\exp(score_{ij})}$$

输出：

$$y_i=\sum_j\alpha_{ij}v_j$$

缩放点积注意力：

$$Attention(Q,K,V)=softmax\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$

lec8 PPT 明确给出了这个公式，并说明缩放因子 $1/\sqrt{d_k}$ 用于缓解点积过大导致 softmax 梯度过小的问题。

8.4 Multi-Head Attention

多头注意力：

$$MultiHead(Q,K,V)=Concat(head_1,\dots,head_h)W^O$$ $$head_i=Attention(QW_i^Q,KW_i^K,VW_i^V)$$

理解：

• 每个 head 学习不同表示子空间的信息。
• 类似 CNN 的多个通道。
• 比单头更有表达力。
• PPT 中说明多头注意力允许模型在不同位置共同处理来自不同表示子空间的信息。

8.5 Transformer

核心结构：

• Embedding
• Positional Encoding
• Multi-Head Self-Attention
• Feed Forward Network
• Residual Connection
• Layer Normalization
• Encoder / Decoder stack

Self-Attention 优点：

• 任意两个位置之间路径短。
• 易并行。
• 更适合长距离依赖。
• 可通过 mask 防止 decoder 看到未来信息。

---

lec9 强化学习

lec9 强化学习内容包括 Agent、Environment、State、Action、Reward、Policy、State transition、Return、Value、Value-based、Policy-based、Actor-Critic。PPT 中总结了这些术语，并说明智能体可以由策略 $\pi(a|s)$ 或最优动作价值函数 $Q^*(s,a)$ 控制。

9.1 强化学习基本框架

交互流程：

1. Agent 观察状态 $s_t$。
2. 根据策略选择动作 $a_t$。
3. Environment 转移到新状态 $s_{t+1}$。
4. Environment 给出奖励 $r_t$。
5. Agent 根据奖励更新策略。

核心元素：

• Agent：智能体
• Environment：环境
• State $s$：状态
• Action $a$：动作
• Reward $r$：奖励
• Policy $\pi(a|s)$：状态下选择动作的概率
• Transition $p(s'|s,a)$：状态转移概率

PPT 中 policy 被定义为给定状态 $s$ 时采取动作 $a$ 的概率，且智能体动作可以是随机的。

9.2 Return 与价值函数

回报：

$$U_t=R_t+\gamma R_{t+1}+\gamma^2R_{t+2}+\cdots$$

动作价值函数：

$$Q^\pi(s_t,a_t)=\mathbb{E}[U_t|s_t,a_t]$$

最优动作价值函数：

$$Q^*(s,a)=\max_\pi Q^\pi(s,a)$$

状态价值函数：

$$V^\pi(s)=\mathbb{E}_{A\sim\pi}[Q^\pi(s,A)]$$

9.3 Value-based、Policy-based、Actor-Critic

Value-based

学习 $Q^*(s,a)$，选择：

$$a=\arg\max_a Q^*(s,a)$$

代表：Q-learning、DQN。

特点：

• 更像“先评估动作价值，再选最优动作”。
• 若使用 $\arg\max$，执行可以是确定性的。
• 训练时常加入 $\epsilon$-greedy 探索，因此训练过程可能随机。

Policy-based

直接学习策略：

$$\pi(a|s;\theta)$$

根据策略采样动作：

$$a_t \sim \pi(\cdot|s_t;\theta)$$

特点：

• 可自然表达随机策略。
• 适合连续动作或多峰策略。
• 训练用 policy gradient。

Actor-Critic

Actor：策略网络，输出动作分布 $\pi(a|s;\theta)$。 Critic：价值网络，估计 $V(s)$ 或 $Q(s,a)$，为 Actor 提供学习信号。

PPT 中明确：Actor 近似策略函数，Critic 近似动作价值函数；训练时 Agent 由 Actor 控制，Critic 为 Actor 提供监督，训练后通常只用 Actor 控制智能体。

9.4 “这些方法是否具有随机性”答题思路

这类题 2025 回忆题第 10 题出现过：强化学习控制智能体的方式有哪些，这几类方法具有随机性吗。

答法：

强化学习中控制智能体常见方式包括基于价值的方法、基于策略的方法和 Actor-Critic 方法。基于价值的方法学习 $Q(s,a)$，执行时若总选择 $\arg\max_a Q(s,a)$，策略本身可以是确定性的；但训练时常用 $\epsilon$-greedy 探索，因此训练过程具有随机性。基于策略的方法直接学习 $\pi(a|s)$，若输出动作概率分布并采样动作，则具有随机性；若取最大概率动作，则执行时可变成确定性。Actor-Critic 中 Actor 通常输出策略分布，因此训练时通常具有随机性；Critic 负责评估状态或动作价值，不直接控制动作。除此之外，环境转移 $p(s'|s,a)$ 本身也可能具有随机性。

---

lec10 概率推理与图模型

10.1 概率推理 = 建模 + 推断

lec10 明确写到：概率推理 = 建模 + 推断。建模关注如何紧凑指定联合分布，推断关注如何高效计算条件概率 $p(R|C)$。

• 建模：构造联合分布 $p(x_1,\dots,x_D)$。
• 推断：给定证据 $C$，求查询变量 $R$ 的概率 $p(R|C)$。

10.2 贝叶斯公式

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

其中：

$$P(B)=P(B|A)P(A)+P(B|\neg A)P(\neg A)$$

医学检测题模板：

$$P(病|阳)=\frac{P(阳|病)P(病)}{P(阳|病)P(病)+P(阳|\neg病)P(\neg病)}$$

注意：

• 发病率低时，即使检测准确率高，阳性后真患病概率也可能不高。
• 必须区分 $P(A|B)$ 和 $P(B|A)$。

10.3 贝叶斯网络

贝叶斯网络是有向无环图 DAG，将联合分布分解为局部条件分布乘积：

$$p(x_1,\dots,x_K)=\prod_{s=1}^{K}p(x_s|x_{\Gamma(s)})$$

其中 $\Gamma(s)$ 是 $x_s$ 的父节点集合。

例：

若有结构：

$$B\to A,\quad E\to A,\quad E\to R$$

则：

$$P(B,E,A,R)=P(B)P(E)P(A|B,E)P(R|E)$$

10.4 条件独立

贝叶斯网络中的一条边表示直接依赖；没有边不代表绝对独立，而是可能在给定某些变量后条件独立。

常见结构：

1. 链式结构

   $$X\to Y\to Z$$

   给定 $Y$，$X$ 与 $Z$ 条件独立。

2. 共同原因

   $$X\leftarrow Y\to Z$$

   给定 $Y$，$X$ 与 $Z$ 条件独立。

3. 共同结果 / v-structure

   $$X\to Y\leftarrow Z$$

   未给定 $Y$ 时，$X$ 与 $Z$ 独立；给定 $Y$ 或其后代后，$X$ 与 $Z$ 反而相关。

10.5 变量消元

目标：

$$P(Query|Evidence)$$

步骤：

1. 写出联合分布因子分解。
2. 代入证据。
3. 对非查询、非证据变量求和消去。
4. 归一化。

通用形式：

$$P(Q|e)=\alpha \sum_{hidden}\prod_i factor_i$$

其中 $\alpha$ 是归一化常数。

---

往年高频补充：逻辑、合一、子句集、知识表示

这部分虽然不在你描述的“lec1、lec8、lec9 不做计算”里，但 2025 回忆题出现合一、子句集、谓词/产生式/语义网络表示，因此建议至少保留一页复习。

A. 一阶谓词逻辑表示

常用符号：

• $\forall x$：任意 $x$
• $\exists x$：存在 $x$
• $\neg$：非
• $\land$：且
• $\lor$：或
• $\to$：蕴含

例：

“所有猫都喜欢爬树”：

$$\forall x(Cat(x)\to LikeClimbTree(x))$$

“有些学生喜欢红楼梦”：

$$\exists x(Student(x)\land Like(x, HongLouMeng))$$

“不是所有学生都喜欢徒步和登山”：

$$\neg \forall x(Student(x)\to (LikeHiking(x)\land LikeClimbing(x)))$$

等价：

$$\exists x(Student(x)\land \neg(LikeHiking(x)\land LikeClimbing(x)))$$

B. 合一 Unification

目标：找一个置换 $\theta$，使两个谓词公式相同。

例：

$$P(f(a),x),\quad P(y,f(y))$$

第一项要求：

$$y=f(a)$$

第二项要求：

$$x=f(y)=f(f(a))$$

所以可合一：

$$\theta={y/f(a),x/f(f(a))}$$

不可合一常见原因：

• 函数符号不同。
• 常量不同。
• 出现 occurs check：变量要等于包含自身的项，如 $x=f(x)$。

C. 子句集转换

一般步骤：

1. 消去蕴含： $$A\to B \equiv \neg A\lor B$$
2. 否定内移。
3. 变量标准化。
4. 前束化。
5. Skolem 化，消去存在量词。
6. 去掉全称量词。
7. 化为合取范式 CNF。
8. 拆成子句集。

D. 归结推理

证明 $G$ 是 $F$ 的逻辑结论：

1. 将 $F$ 转为子句集。
2. 将 $\neg G$ 加入子句集。
3. 反复归结。
4. 若推出空子句 $\Box$，则 $F \models G$。

E. 产生式表示

形式：

$$IF\ 条件\ THEN\ 结论/动作$$

例：

IF $x$ 是导盲犬 THEN $x$ 是狗 且 $x$ 能为盲人带路。

优点：规则直观、模块化。 缺点：规则冲突、规模大时维护困难。

F. 语义网络

用节点表示对象、概念、属性，用边表示关系。

常见继承关系：

• AKO / is-a：类与类关系，如 Goldfish is-a Fish。
• instance-of：实例与类关系，如 小明 instance-of Student。
• part-of / has-a：整体与部分关系，如 Dog has-a Tail。

---

常考大题答题模板

1. 搜索题模板

题目要求 BFS/DFS/UCS/A* 时，按以下格式写：

1. 说明算法规则：

   • BFS：队列，按深度。
   • DFS：栈，按深度。
   • UCS：按 $g(n)$ 最小。
   • A*：按 $f(n)=g(n)+h(n)$ 最小。

2. 写初始 frontier。

3. 每一步写：

   • 扩展节点
   • 新生成节点
   • frontier 变化
   • explored 变化

4. 到目标时写：

   • 路径
   • 总代价
   • 是否最优

2. Alpha-Beta 模板

1. 先用 Minimax 倒推所有内部节点。

2. 再从左到右模拟：

   • MAX 更新 $\alpha$
   • MIN 更新 $\beta$
   • 若 $\alpha\ge\beta$，剪枝

3. 标出被剪叶子。

4. 写剪枝发生时的 $\alpha,\beta$。

3. ID3 模板

$$H(D)=-\sum_kp_k\log_2p_k$$ $$H(D|A)=\sum_v\frac{|D_v|}{|D|}H(D_v)$$ $$Gain(D,A)=H(D)-H(D|A)$$

最后一句：

因为属性 $A$ 的信息增益最大，所以根节点选择 $A$。

4. 贝叶斯题模板

1. 定义事件。
2. 写贝叶斯公式。
3. 用全概率公式展开分母。
4. 代入数字。
5. 给结论，并解释直觉。

5. 卷积题模板

1. 先写 padding 后矩阵。
2. 确定输出尺寸： $$\frac{N+2P-F}{S}+1$$
3. 每个位置取窗口，与卷积核对应相乘求和。
4. 池化则按窗口取最大或平均。

6. Attention 计算模板

1. 计算： $$Q=XW_Q,\quad K=XW_K,\quad V=XW_V$$
2. 对指定 query 计算 score： $$score_i=q^Tk_i$$
3. Softmax： $$\alpha_i=\frac{e^{score_i}}{\sum_j e^{score_j}}$$
4. 输出： $$y=\sum_i\alpha_iv_i$$

---

最后冲刺建议

按你给出的考试范围，建议这样分配时间：

• 搜索 + 博弈树 + ID3 + 卷积/池化 + 贝叶斯公式/贝叶斯网络：必须能完整手算。
• lec1、lec8、lec9：按主观题准备，重点是“能解释为什么、有什么作用、流程是什么、区别是什么”。
• lec5–lec7：重点掌握概念、公式和典型计算。尤其是逻辑回归/SVM/决策树/CNN。
• 往年逻辑题：若老师课上讲过，合一、子句集、归结、语义网络至少各练一道；若没讲，可作为低优先级保险。