人工智能引论

一、判断题

1. α-β剪枝的剪枝数目与扩展节点的顺序有关。
2. 如果启发函数 $h_1$ 是一致的，$h_2 = h_1 + c$（$c$ 为正常数），那么用 A* 搜索得到的结果满足 $f_2 \le f_1 + c \cdot d$，其中 $d$ 为最优路径的深度。
3. kNN 是非参数模型，决策树是参数模型。
4. 逻辑回归使用的不是线性模型。
5. （有一张图，图中标出了某点梯度）判断图上标出的梯度是否正确。
6. 一批大小为 N、通道数为 5、尺寸为 32×32 的图像，经过 5 个 7×7 滤波器（无填充，步长为 1）后，输出特征图的维度为 (N, 5, 26, 26)。判断这一说法是否正确。
7. 两条不共面且不穿过小孔的直线，在小孔成像后必然相交（或其延长线相交）。

二、概率论

已知随机变量 $X$ 的分布函数为：

$$F(x)=\{\begin{array}{ll}0,& x<0\\ \frac{1}{4},& 0\le x<1\\ 1-e^{-x},& x\ge 1\end{array}$$
F(x) =
\begin{cases}
0, & x < 0 \
\frac{1}{4}, & 0 \le x < 1 \
1 - e^{-x}, & x \ge 1
\end{cases}

请计算：
(1) $X$ 落在闭区间 $[0, 1]$ 的概率；
(2) $X$ 落在开区间 $(0, 1)$ 的概率；
(3) $X$ 的数学期望 $E(X)$。

三、数字华容道（8-puzzle）

在一个 3×3 的棋盘上有 8 个数字方块和一个空格。给定初始状态和目标状态。已知初始状态为：

1 2 3
8 _ 5
4 7 6

(1) 写出一个可用的启发函数，并证明使用该启发函数的 A* 搜索能得到最优解。
(2) 画出从初始状态开始，前三步的搜索树（包括根节点）。

四、决策树

给定包含 8 个样本的数据集，样本有 A、B、C 三种属性，标签共 3 种类别。

(1) 请使用基尼系数构建一棵深度为 2 的决策树。
(2) 现有一个新样本，其属性 A、B、C 的取值已知，请用所建决策树预测其标签。
(3) 简述用随机森林对该数据进行训练和预测的整体流程。

五、CYK 算法

给定上下文无关文法：

S → AB | aBC
A → AA | a
B → CD | b
C → c
D → De | d

(1) 将该文法改写为乔姆斯基范式（CNF）。
(2) 使用 CYK 算法判断某个句子是否符合该文法。

六、蒙特卡洛树搜索（MCTS）

某不太聪明的大模型被询问：“交通事故应该参考什么法律？” 它每次只在尚未输出的 token 中完全随机地选择一个输出。全部可选 token 为：“中华人民共和国”、“刑法”、“修正案”、“民法典”、“EOF”（可能还有别的）。对回答序列有对应的打分函数，例如序列（“中华人民共和国”，“刑法”，“EOF”）的打分值为 0.9。

现已构建好一棵三层的搜索树，各节点数据已在树上标出。

(1) 计算给出的三个第三层子节点的 UCB 值，并选择应扩展的节点。
(2) 若超参数 $c$ 减小，算法是更倾向于扩展（exploitation）还是探索（exploration）？
(3) 将 (1) 中所选节点继续向下随机生成，直到无法继续生成而得到一个完整回答，用打分函数进行评分；设每次选择合法 token 是等概率的，用打分函数的期望值作为随机模拟值，沿搜索树进行回溯更新。

七、反向传播

给定合页损失函数（向量机）：
$$L=\max (0,1-y({\mathbf{w}}^T\mathbf{x}+b))$$
L = \max(0,, 1 - y(\mathbf{w}^T\mathbf{x} + b))

其中 $\mathbf{w}, \mathbf{x}$ 均为列向量，$y$ 为标量标签。

(1) 求 $L$ 对 $\mathbf{w}$、$\mathbf{x}$、$b$ 的偏导数；并代入所给的特殊数值计算出具体偏导值。
(2) 已知某复合关系形如 $\mathbf{x} = e^{\mathbf{x}} + \mathbf{x}$，请用链式求导法则计算相应的偏导数。
(3) 若在损失函数中加入 L2 正则化项，重新计算偏导数（与(2)无关）。