90分钟 · 100分 · 7道大题 · 27小问。

这是原创自学模拟卷，不是官方考试规格。题数、主题权重、计算器练习说明与评分建议均不预测官方要求。

先在独立答题纸完成全部题目，再打开解答。写出必要计算、条件与证明。可行时使用精确值，使用小数须注明舍入。特征向量或奇异向量的符号若一致配对，等价选择均可。以题目定义、归一化因子及破平局规则为准，不得无理由假定逆矩阵存在。

本次练习使用Casio fx-50FH II，可用一张双面A4速查纸；这些是练习约定，不是对当前官方考试许可的声明。先写数学目标再做标量运算，普通REG输出不代替加权、多元或正则化推导。不假定CAS或完整矩阵功能。

以下是自评评分建议，不是官方评分细则。等价正确推导应得同等分数；单一算术错误传递时保留方法分。解答区分目标、条件、计算与检查，不能只凭最终数字相同给满分。

题本 · MATH3320

Q1. 稳健损失与验证 (16)

题本 Q1

(a) [4]

先弄清正在优化什么。 四个观测是固定数字，$a\in\mathbb R$才是我们要选的一个参数；同一个$a$用于预测全部观测。残差$r_i=y_i-a$也是标量，$F(a)=\sum_i\rho(r_i)$把四次预测的代价相加。平方分支$\rho(r)=r^2/2$的导数为$r$；尾部分支$|r|-1/2$在正半轴等于$r-1/2$，在负半轴等于$-r-1/2$，故导数分别为1、−1。不能因为有绝对值就说整个函数在0不可导：0附近实际使用的是平方分支。凸表示任意两点之间的函数图像不高于连接线，并不表示处处严格凸；尾部直线正是反例。

这里的自变量是残差$r=y_i-a$，不是系数惩罚。令$\psi=\rho^{\prime}$，分段求导：

$$\psi(r)=\begin{cases}-1,&r<-1,\\r,&-1\le r\le1,\\1,&r>1.\end{cases}$$

在r=1处两侧导数都为1；在r=−1处两侧都为−1，两个连接点均可导，无须任选一侧。导数整体单调不减，所以$\rho$凸。与仿射函数$y_i-a$复合仍凸，四项求和的F也凸。

评分: 分段导数2分；两个连接点1分；凸性及传递到F的理由1分。

题本 Q1(a)

(b) [6]

为什么先试区间$[0,1]$？ 三个观测都为0，只有一个为8；先检查靠近多数观测的位置，能让三个残差落在容易求导的平方区间。这只是候选区间，不是先假定答案；求出后还要验区间及全局性。逐项看链式法则，$d\rho(-a)/da=-\psi(-a)=\psi(a)$，三项给$3\psi(a)$；第四项给$-\psi(8-a)=\psi(a-8)$。在候选解处，三个小残差各产生大小$1/3$的拉力，刚好平衡异常点饱和为1的拉力。OLS则每个残差的拉力随大小线性增加，所以大异常点会把均值明显拉走。

对残差求导带来因子−1，利用$\psi$为奇函数：

$$F^{\prime}(a)=-\sum_{i=1}^4\psi(y_i-a)=3\psi(a)+\psi(a-8).$$

在$0\le a\le1$上，$\psi(a)=a$且$\psi(a-8)=-1$，故$F^{\prime}(a)=3a-1$给$a_H=1/3$，确实在假设区间内。凸性保证零导数是全局最优。唯一性还要检查：a小于0时导数为负；[0,1]内严格递增且只过零一次；a大于1时，由单调性及$F^{\prime}(1)=2$可知导数为正。

$$G(a)=3a^2+(8-a)^2,\qquad G^{\prime}(a)=8a-16,\qquad a_{OLS}=2.$$

两个估计优化不同目标。直接检查：

$$F(1/3)=3\frac{(1/3)^2}{2}+\left(\frac{23}{3}-\frac12\right)=\frac{22}{3},\quad F(2)=10;\qquad G(2)=48,\quad G(1/3)=\frac{532}{9}>48.$$

把8改为80，在[0,1]仍有$\psi(a-80)=-1$，同一导数与唯一性论证仍给$a_H=1/3$；OLS常数则变为20。更一般，异常值B满足$B-1/3\ge1$即$B\ge4/3$时，此Huber解保持不变。这是残差导数饱和带来的受限影响，不是说损失忽略异常值或最小化RSS。

评分: 正确导数及适用区间2分；解与唯一全局最优性2分；OLS答案1分；80时不变及理由1分。

题本 Q1(b)

(c) [3]

把求导拆成两层。 对$\sqrt{1+r^2}=(1+r^2)^{1/2}$，外层导数为$\tfrac12(1+r^2)^{-1/2}$，内层导数为$2r$；相乘后才得到下面的一阶导数。尾部极限可把分子分母同除以$|r|$：$r/\sqrt{1+r^2}=\operatorname{sign}(r)/\sqrt{1+1/r^2}$。因此两端符号相反，不能两端都写1。“有界”指斜率，不是损失值；损失本身仍随$|r|$增长。

$$\widetilde\rho^{\prime}(r)=\frac r{\sqrt{1+r^2}},\qquad\lim_{r\to+\infty}\widetilde\rho^{\prime}(r)=1,\qquad\lim_{r\to-\infty}\widetilde\rho^{\prime}(r)=-1.$$ $$\widetilde\rho^{\prime\prime}(r)=\frac1{(1+r^2)^{3/2}}>0.$$

相比之下，$(r^2/2)^{\prime}=r$无界。因此大残差在伪Huber下贡献有界斜率，而平方损失下可贡献任意大斜率。伪Huber没有分段连接的拐接，但最小点不一定与Huber完全相同。

评分: 导数1分；尾部极限及平方损失比较1分；大残差意义1分。

题本 Q1(c)

(d) [3]

将“学习参数”和“应用参数”分开。 例如训练折算出均值$m_{train}$及非零标准差$s_{train}$后，验证观测$x$应变成$(x-m_{train})/s_{train}$；不能重新用验证折自己的均值，也不能预先用全体数据的均值。验证折本来用于模拟未来没见过的数据。另一方面，在多种损失中取最小CV值，相当于挑中了对这批验证数据表现最好的候选，可能也挑中了随机好运；这就是还要保留最终独立测试集的原因。

第一，全数据标准化使每个验证折参与训练预处理，即使没有用标签也会泄漏。第二，最小CV分数已用于选损失，是经过选择的验证结果，不是独立测试误差。应先留独立测试集；在开发数据做五折CV，每折仅用训练子集学习标准化及模型，再用固定变换评验证折。选定损失和超参数后，在全部开发数据重新拟合整条流程，最后在未参与选择的测试集评一次。仅改名“测试集”不会改变它参与选择的事实。

评分: 预处理泄漏1分；选择偏差及验证与独立测试区别1分；修正顺序1分。

题本 Q1(d)

Q2. 贪心拟合、重新拟合与嵌套模型 (18)

题本 Q2

(a) [2]

相关性是在比较哪两个对象？ $D$是$3\times3$矩阵，每列$d_j\in\mathbb R^3$是一种可加入预测的方向；$y,r\in\mathbb R^3$分别是观测和尚未解释的部分，$c\in\mathbb R^3$是系数。初始$c=0$，所以$r=y$。选列用$|d_j^Tr|$，取绝对值是因为正负方向都可以改善拟合。更新大小来自展开$\|r-\gamma d_j\|^2=\|r\|^2-2\gamma d_j^Tr+\gamma^2\|d_j\|^2$，对$\gamma$求导置零，才得$\gamma=d_j^Tr/\|d_j\|^2$。本题列长为1，分母才消失。

$$\|d_1\|_2^2=1,\quad\|d_2\|_2^2=(3/5)^2+(4/5)^2=1,\quad\|d_3\|_2^2=1,\qquad D^Ty=(2,2,1/5)^T.$$

前两列绝对相关性并列最大，按编号规则选$d_1$。单位范数使题设增量$d_j^Tr$适用；一般非单位列的一维最小二乘增量还需除以$\|d_j\|_2^2$。

评分: 范数及相关性1分；破平局1分。

题本 Q2(a)

(b) [5]

每轮都守住同一个账目：预测加残差等于$y$。 第一轮预测$2d_1=(2,0,0)^T$，从$y=(2,1,1/5)^T$相减得到新残差。第二轮添加的是$(4/5)d_2=(12/25,16/25,0)^T$，不是把预测替换为这一向量。所以新预测为$(62/25,16/25,0)^T$，逐坐标相减得下面残差：第一坐标$2-62/25=-12/25$，第二坐标$1-16/25=9/25$。RSS是三个残差平方之和，不是它们的和，也不是除以3后的MSE。

第一轮增量为2。第二次选择前，必须针对新残差重算相关性：

$$c^{(1)}=(2,0,0)^T,\quad r^{(1)}=(0,1,1/5)^T,\quad D^Tr^{(1)}=(0,4/5,1/5)^T.$$

因此选择$d_2$，增量$4/5$。第一个系数保持2；MP没有联合重新拟合它。

$$c_{MP}=(2,4/5,0)^T,\quad r_{MP}=r^{(1)}-\frac45d_2=\begin{pmatrix}-12/25\\9/25\\1/5\end{pmatrix},\quad\mathrm{RSS}_{MP}=\frac{144+81}{625}+\frac1{25}=\frac25.$$

评分: 第一步1分；第二步相关性与选择1分；增量及最终系数1分；残差1分；RSS1分。

题本 Q2(b)

(c) [5]

OMP多做的一步是什么？ 选中两列后，允许两个系数一起调整，所以未知数是$b=(b_1,b_2)^T\in\mathbb R^2$，$D_A$为$3\times2$。对目标求梯度得$2D_A^T(D_Ab-y)=0$，移项就是$2\times2$正规方程。右端$D_A^Ty=(2,2)^T$不是上一轮残差的相关性；相关性用于选列，原始$y$用于重新拟合，二者职能不同。两式相减实际给$(2/5)(b_1-b_2)=0$，再代回任一式得到共同系数。旧系数从2降为5/4并非“退步”，因为新列也在解释第一坐标。

第一轮OMP与MP相同，第二次仍选$d_2$。活跃矩阵及正规方程为：

$$D_A=\begin{pmatrix}1&3/5\\0&4/5\\0&0\end{pmatrix},\qquad\begin{pmatrix}1&3/5\\3/5&1\end{pmatrix}\begin{pmatrix}b_1\\b_2\end{pmatrix}=\begin{pmatrix}2\\2\end{pmatrix}.$$

目标仍为原始y，即$\min_b\|D_Ab-y\|_2^2$，不是冻结旧系数。行列式$1-9/25=16/25>0$保证唯一。两式相减得$b_1=b_2$，再代入$(8/5)b_1=2$，两者都为5/4。

$$c_{OMP}=(5/4,5/4,0)^T,\quad r_{OMP}=(0,0,1/5)^T,\quad\mathrm{RSS}_{OMP}=1/25.$$

检查前两项预测：$5/4+(3/5)(5/4)=2$，$(4/5)(5/4)=1$，恰好等于相应观测。

评分: 活跃集及正规方程2分；两个系数1分；残差1分；RSS1分。

题本 Q2(c)

(d) [3]

正交不是“看起来方向不同”，而是内积为0。 一维最小二乘更新后，$d_j^T(r-\gamma d_j)=d_j^Tr-\gamma\|d_j\|^2=0$；它只保证当前选列。再沿另一个不正交方向移动，旧内积会变为$0-\gamma_2d_1^Td_2$，本例为$-(4/5)(3/5)=-12/25$。OMP的正规方程则一次令所有活跃方向的内积为0。比较的是相同活跃列上的拟合，不能由此推出对所有未来样本或所有稀疏支持集都更优。

$$d_1^Tr_{MP}=-12/25,\qquad d_2^Tr_{MP}=\frac35\!\left(-\frac{12}{25}\right)+\frac45\frac9{25}=0,\qquad D_A^Tr_{OMP}=0.$$

MP残差只与最近更新列正交，不再与先前列正交。因为$d_1^Td_2=3/5\ne0$，沿第二列更新会改变第一坐标，破坏旧正交关系。OMP重新优化全部活跃系数，残差同时正交于两列，本例RSS因此较小。这不证明OMP总能找到稀疏问题的全局最优支持集。

评分: MP内积1分；OMP正交性1分；非正交列及联合重拟合解释1分。

题本 Q2(d)

(e) [3]

证明的关键不是“大模型通常更好”，而是旧答案没有被禁止。 $V_1,V_2$是允许的预测向量集合；扩大集合后，至少仍可以选择旧预测，因此新的最小值不可能更大。若新增方向与旧残差正交，旧预测可能仍最优，所以可以等号。在下方反例中，第二模型只能预测$(t,t,t)^T$；目标$(1-t)^2+2t^2$求导得$6t-2=0$，故$t=1/3$。MAE直接算为$((2/3)+(1/3)+(1/3))/3=4/9$，展示为何不能把RSS的结论换成另一个指标。

令$\widehat y_1\in V_1$为第一模型最优预测。由于$V_1\subseteq V_2$，它也在第二优化中可行：

$$\mathrm{RSS}_2=\min_{v\in V_2}\|y-v\|_2^2\le\|y-\widehat y_1\|_2^2=\mathrm{RSS}_1.$$

这里只保证不增，不保证严格下降，也不涉及测试误差。MAE不是所优化目标，没有相同保证。反例：$y=(1,0,0)^T$，$V_1=\{0\}$，$V_2=\operatorname{span}\{(1,1,1)^T\}$。最小二乘预测分别为0及$(1/3,1/3,1/3)^T$：

$$\mathrm{RSS}_1=1,\quad\mathrm{RSS}_2=2/3,\quad\mathrm{MAE}_1=1/3,\quad\mathrm{MAE}_2=4/9.$$

所以RSS下降而MAE上升。数值反例帮助理解，并非正确解释以外的额外作答要求。

评分: 可行集包含的完整证明2分；MAE无保证及正确解释1分。

题本 Q2(e)

Q3. 核PCA及其归一化 (17)

题本 Q3

(a) [5]

先画清三个空间。 输入$t_i$是标量，但映射$\phi(t)=(t,t^2)^T$把它变为二维向量；三个样本逐行排列，所以$\Phi,\Phi_c$均为$3\times2$。均值$\overline\phi$是$2\times1$，中心化公式为$\Phi_c=\Phi-\mathbf1\overline\phi^T$，其中$\mathbf1$是$3\times1$。例如第一行$(-1,1)-(0,2/3)=(-1,1/3)$。$K$为$3\times3$，元素$K_{ij}=\phi(t_i)^T\phi(t_j)$比较样本而不是比较特征；例如$K_{13}=(-1)(1)+(1)(1)=0$。

为什么核矩阵要左右各中心化一次？ $C=I_3-\mathbf1\mathbf1^T/3$左乘$\Phi$从每个样本减去均值；因此$(C\Phi)(C\Phi)^T=C\Phi\Phi^TC=CKC$。逐元素公式是$(K_c)_{ij}=K_{ij}-\overline K_{i\cdot}-\overline K_{\cdot j}+\overline K_{\cdot\cdot}$，最后加总均值是补回被减了两次的部分。本题行均值为$(2/3,0,2/3)$，总均值$4/9$，故$(K_c)_{11}=2-2/3-2/3+4/9=10/9$，$(K_c)_{12}=0-2/3-0+4/9=-2/9$。

先构造特征矩阵再中心化。原标量输入均值为0，不代表非线性平方特征均值为0；后者是2/3：

$$\Phi=\begin{pmatrix}-1&1\\0&0\\1&1\end{pmatrix},\quad\overline\phi=\begin{pmatrix}0\\2/3\end{pmatrix},\quad\Phi_c=\begin{pmatrix}-1&1/3\\0&-2/3\\1&1/3\end{pmatrix}.$$

每行减去同一均值行。因为$C=C^T=C^2$，Gram矩阵双中心化等于中心化特征的Gram矩阵：

$$K=\Phi\Phi^T=\begin{pmatrix}2&0&0\\0&0&0\\0&0&2\end{pmatrix},\quad K_c=CKC=\Phi_c\Phi_c^T=\frac19\begin{pmatrix}10&-2&-8\\-2&4&-2\\-8&-2&10\end{pmatrix}.$$

三行和分别为$(10-2-8)/9$、$(-2+4-2)/9$及$(-8-2+10)/9$，全为0，所以$K_c\mathbf1=0$。若不成立，先查是否只减行均值而没有完成双中心化。

评分: 特征均值与中心化矩阵2分；K1分；中心化K1分；零行和检查1分。

题本 Q3(a)

(b) [4]

这些向量不是凭空猜的。 中心化已给出$K_c\mathbf1=0$，所以常数向量是零特征方向。第一、第三个样本关于0对称，先试反对称向量$(-1,0,1)^T$；矩阵乘法给$(-18,0,18)^T/9=2(-1,0,1)^T$。再找既垂直于常数向量、又垂直于该反对称向量的向量：两端应相等且三项和为0，可取$(1,-2,1)^T$；相乘给$(6,-12,6)^T/9=(2/3)(1,-2,1)^T$。最后分别除以原长度$\sqrt2,\sqrt6,\sqrt3$，才得到单位向量。特征值衡量方向大小，单位化只改向量长度，不改特征值。

取三个两两正交的单位向量，逐个验证矩阵乘积：

$$q_1=\frac1{\sqrt2}(-1,0,1)^T,\quad q_2=\frac1{\sqrt6}(1,-2,1)^T,\quad q_3=\frac1{\sqrt3}(1,1,1)^T;$$ $$K_cq_1=2q_1,\qquad K_cq_2=\frac23q_2,\qquad K_cq_3=0.$$

它们构成$\mathbb R^3$的标准正交基，没有遗漏特征值，谱为$2,2/3,0$。最大特征值严格较大，仅剩整体符号歧义。第三分量要求为正，因此$q=q_1$、$\lambda=2$。迹检查：$\operatorname{tr}(K_c)=24/9=8/3=2+2/3+0$。

评分: 三个特征值2分；单位主特征向量1分；验证与符号1分。

题本 Q3(b)

(c) [4]

先做维数检查，再做归一化。 $q\in\mathbb R^3$的三个数给三个样本加权，不是二维特征空间中的轴；$\Phi_c^T$为$2\times3$，故$\Phi_c^Tq\in\mathbb R^2$才有正确的方向维数。其第一坐标为$(-1)(-1/\sqrt2)+0+(1)(1/\sqrt2)=\sqrt2$；第二坐标为$(1/3)(-1/\sqrt2)+0+(1/3)(1/\sqrt2)=0$。但“维数正确”不等于“长度为1”，所以还需$w=\Phi_c^Tq/\sqrt\lambda$。

投影得分$z_i$是第$i$行中心化特征与$w$的内积，一个样本得到一个标量，全部叠成$z\in\mathbb R^3$。这里$w=(1,0)^T$只保留第一特征，因而得分恰为$(-1,0,1)^T$。一般核方法未必能显式写出特征，但$z=K_cq/\sqrt\lambda$仍能计算相同训练得分。下面的长度证明同时解释了为什么必须要求$\lambda>0$。

q是样本编号空间的单位向量，w是特征空间的方向，两者维度不同。对正特征值：

$$\|w\|_2^2=\frac{q^T\Phi_c\Phi_c^Tq}{\lambda}=\frac{q^TK_cq}{\lambda}=q^Tq=1.$$ $$\Phi_c^Tq=(\sqrt2,0)^T,\qquad w=(1,0)^T,\qquad z=\Phi_cw=(-1,0,1)^T=\frac{K_cq}{\sqrt\lambda}=\sqrt\lambda\,q.$$

漏除$\sqrt\lambda$会使方向长度为$\sqrt2$，得分多乘$\sqrt2$，方差多乘2。错在改变单位方向约束，不只是记号不规范。零特征值不能放在这个分母。

评分: 单位长度证明2分；w及得分1分；遗漏归一化的后果1分。

题本 Q3(c)

(d) [4]

三个不同的量不要混成一个。 核矩阵特征值2是平方得分总量；样本方差是它再除以$n-1=2$；解释比例则是保留方差除以总方差。直接核对：得分均值为0，所以样本方差$[(-1)^2+0^2+1^2]/2=1$。特征协方差的交叉项为$[(-1)(1/3)+0(-2/3)+(1)(1/3)]/2=0$，第二对角项为$[(1/3)^2+(-2/3)^2+(1/3)^2]/2=1/3$。

重建为何要加回均值？ $z_iw$重建的是“离均值多远”，不是原特征。完整重建是$\widehat\phi_i=\overline\phi+z_iw$。这里第一坐标全保留，第二坐标全用均值2/3代替，因此只损失第二特征的偏差。重建位于二维特征空间，不必等于某个真实输入的$\phi(t)$：例如$(0,2/3)$并不是$(t,t^2)$形式。题目没有要求解这种逆映射。

题设样本协方差分母为n−1=2，不是3：

$$S_\phi=\frac12\Phi_c^T\Phi_c=\begin{pmatrix}1&0\\0&1/3\end{pmatrix},\quad\operatorname{Var}(z)=1=\frac{\lambda_1(K_c)}{n-1},\quad\eta=\frac1{1+1/3}=\frac34.$$

先用得分乘方向重建中心化特征，再加回均值：

$$\widehat\Phi_c=zw^T=\begin{pmatrix}-1&0\\0&0\\1&0\end{pmatrix},\qquad\widehat\Phi=\begin{pmatrix}-1&2/3\\0&2/3\\1&2/3\end{pmatrix}.$$ $$\|\Phi-\widehat\Phi\|_F^2=(1/3)^2+(-2/3)^2+(1/3)^2=\frac23.$$

误差可用被丢弃核特征值$\lambda_2(K_c)=2/3$核对，也可用$(n-1)\lambda_2(S_\phi)=2(1/3)$。协方差归一化改变特征值数值，不改变解释比例；总平方误差为2/3，不是1/3。

评分: 样本方差1分；比例1分；重建与误差2分。

题本 Q3(d)

Q4. 学习距离与随机投影 (16)

题本 Q4

(a) [4]

因子分解把抽象二次型变成平方长度。 $M$为$2\times2$，$h=(h_1,h_2)^T\in\mathbb R^2$，可选$L$为$1\times2$，使二维向量映射成一个数。外积$L^TL$的四项为$1,2,2,4$，正好恢复$M$。半正定要求对所有$h$有非负二次型，正定则要求每个非零$h$都严格为正；两者只差这个严格条件，却决定距离能否区分不同点。由$Lh=h_1+2h_2$可见$h=(-2,1)^T$非零却映成0，所以秩只能为1而不是2。

$$L=\begin{pmatrix}1&2\end{pmatrix},\quad L^TL=M,\quad h^TMh=\|Lh\|_2^2=(h_1+2h_2)^2\ge0.$$

这对每个h证明半正定性，不是逐元素检查正负。第二行是第一行两倍，且第一行非零，因此rank(M)=1。解$h_1+2h_2=0$得到以下零空间；其非零向量也说明M不正定。

$$\ker M=\operatorname{span}\{(-2,1)^T\}.$$

评分: L1分；半正定证明1分；秩1分；零空间1分。

题本 Q4(a)

(b) [3]

先算变换后的坐标，再算距离。 定义$d_M(x,y)=\sqrt{(x-y)^TM(x-y)}=|Lx-Ly|$。$u=(2,0)^T$与$v=(0,1)^T$在平面不同，却都落到数轴的2，因此距离为0；这是降秩映射压扁了一个方向。加$\tau I$须有$\tau>0$，其作用是给每个原方向补上$\tau$倍欧氏平方长度。最后的$5\tau$是平方距离，若问距离本身还要开方得到$\sqrt{5\tau}$。

$$Lo=0,\quad Lu=2,\quad Lv=2,\qquad d_M(o,u)=2,\quad d_M(o,v)=2,\quad d_M(u,v)=0.$$

u与v不同却距离为0，所以这是伪度量，不是全平面上的度量。失败的是分离性，不是对称或非负性。加上$\tau I$后，每个非零方向严格为正：

$$h^TM_\tau h=(h_1+2h_2)^2+\tau\|h\|_2^2>0\quad(h\ne0).$$

因为$u-v=(2,-1)^T$位于原零空间：

$$d_{M_\tau}(u,v)^2=(u-v)^TM(u-v)+\tau\|u-v\|_2^2=5\tau.$$

原先被压扁方向恢复正长度；正定二次型定义真正度量。

评分: 三个距离1分；伪度量及原因1分；5τ与正定理由1分。

题本 Q4(b)

(c) [3]

随机的是矩阵，不是这里的向量。 先固定$a\in\mathbb R^d$，再抽取$R\in\mathbb R^{k\times d}$，输出$Ra\in\mathbb R^k$。期望是对重复抽取矩阵而言。将一个坐标的平方展开：

$$\mathbb E b_\ell^2=\sum_j a_j^2\mathbb E R_{\ell j}^2+2\sum_{j<m}a_ja_m\mathbb E(R_{\ell j}R_{\ell m}).$$

零均值加独立性给$\mathbb E(R_{\ell j}R_{\ell m})=\mathbb ER_{\ell j}\mathbb ER_{\ell m}=0$，而$\mathbb E R_{\ell j}^2=\operatorname{Var}(R_{\ell j})=1/k$。所以每个输出坐标平均分到原平方长度的$1/k$，再将$k$个坐标相加便恢复原长度平方。这里只证明平方范数的期望；不能把平方根直接移进期望，断言$\mathbb E\|Ra\|=\|a\|$。

第ℓ个投影坐标写为$b_\ell=(Ra)_\ell=\sum_{j=1}^dR_{\ell j}a_j$。均值为0使$\mathbb E b_\ell=0$；独立性消去交叉项。每项方差为1/k，因此：

$$\mathbb E b_\ell^2=\operatorname{Var}(b_\ell)=\sum_{j=1}^d a_j^2\frac1k=\frac{\|a\|_2^2}{k},\qquad\mathbb E\|Ra\|_2^2=\sum_{\ell=1}^k\mathbb E b_\ell^2=\|a\|_2^2.$$

若元素方差误设为1，结果会是$k\|a\|_2^2$。期望恒等式不控制每次抽样误差，(d)另加集中概率假设。

评分: 逐坐标均值方差1分；独立性消去交叉项1分；各行求和1分。

题本 Q4(c)

(d) [6]

从“一对成功”到“全部同时成功”要付出点对数量。 对固定点对取$a=x_i-x_j$，题给单方向界控制事件$E_{ij}=\{|\|Ra\|^2-\|a\|^2|>\varepsilon\|a\|^2\}$。任意一对失败就使整体要求失败，所以整体坏事件是并集，不是交集；所有点对共用一个$R$，也不能把成功概率当独立事件相乘。

对$n\ge2$、$0<\delta<1$，取对数的中间步骤是$\log(n(n-1))-ck\varepsilon^2\le\log\delta$，再得$ck\varepsilon^2\ge\log(n(n-1))-\log\delta$。移项时负号方向要检查，最终除以正数$c\varepsilon^2$。维数是整数，向上取整才保证不低于门槛。保证的是平方距离；若要写普通距离，应取$\sqrt{1-\varepsilon}$及$\sqrt{1+\varepsilon}$因子，不能无解释地照抄平方距离界。

至多有$n(n-1)/2$对编号。重复点差向量为0，不会失败，因此保留全部编号对仍是有效上界。每个坏事件为相对平方距离误差超过ε。并集界不要求这些事件互相独立：

$$\Pr(\bigcup_{i<j}E_{ij})\le\frac{n(n-1)}2\,2e^{-ck\varepsilon^2}=n(n-1)e^{-ck\varepsilon^2}.$$

要求右边不超过δ，取自然对数再移项。k为整数，因此充分条件为：

$$k\ge\left\lceil\frac{\log\!\bigl(n(n-1)/\delta\bigr)}{c\varepsilon^2}\right\rceil.$$

于是以至少$1-\delta$概率，同一个随机矩阵同时满足：

$$(1-\varepsilon)\|x_i-x_j\|_2^2\le\|Rx_i-Rx_j\|_2^2\le(1+\varepsilon)\|x_i-x_j\|_2^2\quad\forall\,i,j.$$

这是充分上界，不是必要最小维数。即使界大于d，也不能仅凭此证明所有降维都不可能。须区分两层量词：至少$1-\delta$概率仍允许失败；点集须在抽取R之前固定。若$k<d$，任何线性映射都有非零$a\in\ker R$，于是$\|Ra\|^2=0<(1-\varepsilon)\|a\|^2$，其中$0<\varepsilon<1$。所以一个这样的映射不可能保留整个原空间的全部距离。

评分: 点对数及并集界2分；充分维数2分；仍可能抽样失败1分；全空间零空间反证1分。

题本 Q4(d)

Q5. 完整一轮高斯EM (14)

题本 Q5

(a) [4]

E步到底在问什么？ 两个$x_i$是一维观测，两个成分各有一个权重$\pi_k$、均值$\mu_k$及方差$\sigma_k^2$；隐藏的是每个观测来自哪个成分。责任度$r_{ik}$是“已见到$x_i$后，它来自成分$k$的条件概率”，不是高斯密度本身。贝叶斯公式为

$$r_{ik}=\frac{\pi_k^{old}\varphi(x_i;\mu_k^{old},(\sigma_k^2)^{old})}{\sum_{h=1}^{2}\pi_h^{old}\varphi(x_i;\mu_h^{old},(\sigma_h^2)^{old})}.$$

矩阵$r$的行是观测，列是成分；同一行分母相同，表示该观测的总混合密度。此步所有参数都用旧值，不能算完第一行就改均值。旧均值为−2、2，观测到自己对应均值距离0，到另一均值距离4；方差相同使前因子$A$可约掉，但先验$1/3,2/3$不相等，不能约掉。第二行分母为$A/6+2A/3=5A/6$，所以第一责任度$(A/6)/(5A/6)=1/5$。

令旧共同方差$s^2=8/\log2$，密度前因子$A=(2\pi s^2)^{-1/2}$。距离均值4时，密度乘以下因子：

$$\exp\!\left(-\frac{4^2}{2s^2}\right)=e^{-\log2}=\frac12.$$

两行密度为$(A,A/2)$及$(A/2,A)$。先乘不相等的旧先验，再归一化：x=−2的未归一化值为$(A/3,A/3)$，x=2为$(A/6,2A/3)$。因此：

$$(r_{ik})=\begin{pmatrix}1/2&1/2\\1/5&4/5\end{pmatrix}.$$

每行和为1。第一个观测恰在第一均值，却只有1/2责任度，因为第二成分较大先验抵销了较小密度。只按最近均值硬分配会忽略此区别。

评分: 指数密度比1分；使用先验1分；每行责任度各1分。

题本 Q5(a)

(b) [6]

M步的分母为什么有两个？ E步按行分配“一个观测的1份概率”；M步按列收集“一个成分分到多少观测”。因此$N_k=\sum_i r_{ik}$是成分有效样本量，$\pi_k^{new}=N_k/n$除以总观测数$n=2$，而均值、方差除以该成分自己的$N_k$。第一列归一化后给两个观测权重$5/7,2/7$；第二列给$5/13,8/13$。这也解释两个新均值为什么仍在观测区间$[-2,2]$内。

把第二个方差也完整算一次。 围绕新均值$6/13$，两项偏差是$-2-6/13=-32/13$、$2-6/13=20/13$。加权平方和为$(1/2)(1024/169)+(4/5)(400/169)=832/169$；再除$13/10$得$640/169$。不是除以2，也不是仍围绕旧均值2。

二阶矩捷径来自展开$\sum_i r_{ik}(x_i-\mu)^2=\sum_i r_{ik}x_i^2-2\mu\sum_i r_{ik}x_i+\mu^2N_k$，在新均值处$\sum_i r_{ik}x_i=N_k\mu$，故除以$N_k$后为加权二阶矩减$\mu^2$。旧方差相同只是初始条件，本题分别更新两个方差，并未施加“更新后必须相同”的约束。

本轮M步固定全部责任度。各列和为有效样本量，可以不是整数，但总和为2：

$$N_1=\frac12+\frac15=\frac7{10},\quad N_2=\frac12+\frac45=\frac{13}{10},\quad\pi_1^{new}=\frac7{20},\quad\pi_2^{new}=\frac{13}{20}.$$

把每个成分的责任度加权观测和除以自身有效样本量：

$$\mu_1^{new}=\frac{(-2)(1/2)+2(1/5)}{7/10}=-\frac67,\qquad\mu_2^{new}=\frac{(-2)(1/2)+2(4/5)}{13/10}=\frac6{13}.$$

两个观测的平方均为4，因此每个归一化加权二阶矩也是4。减去新均值平方得方差：

$$(\sigma_1^2)^{new}=4-(-6/7)^2=\frac{160}{49},\qquad(\sigma_2^2)^{new}=4-(6/13)^2=\frac{640}{169}.$$

这是以下方差定义的计算捷径，并非更换定义：

$$(\sigma_k^2)^{new}=\frac{\sum_i r_{ik}(x_i-\mu_k^{new})^2}{N_k}.$$

第一成分偏差为$-8/7,20/7$；加权平方和$(1/2)(64/49)+(1/5)(400/49)=112/49$，再除7/10得160/49。以下三个一致性检查分别恢复总概率、观测均值及二阶矩：

$$\sum_k\pi_k^{new}=1,\quad\sum_k\pi_k^{new}\mu_k^{new}=0,\quad\sum_k\pi_k^{new}\bigl((\sigma_k^2)^{new}+(\mu_k^{new})^2\bigr)=4.$$

评分: 有效样本量及权重2分；两个均值2分；两个方差2分。单一算术错误后仍可保留方法分。

题本 Q5(b)

(c) [2]

把“最大化似然”落实到导数。 写$S_k=\sum_i r_{ik}(x_i-\mu_k^{new})^2$，则$Q'(v)=(S_k-N_kv)/(2v^2)$。本题$S_k>0,N_k>0$，分母始终正；当$v<S_k/N_k$时导数正，超过该点时导数负，因此驻点确为最大点。若某成分$N_k=0$，这些更新不能直接相除；若$S_k=0$，可能出现零方差边界退化，不能不加条件套用正方差结论。本题两列责任度都正且两个观测不同，因此没有这两种问题。

M步在责任度固定时最大化加权对数似然。正方差参数v的相关部分为：

$$Q(v)=-\frac{N_k}{2}\log v-\frac1{2v}\sum_i r_{ik}(x_i-\mu_k^{new})^2+\mathrm{const},$$ $$Q^{\prime}(v)=-\frac{N_k}{2v}+\frac{\sum_i r_{ik}(x_i-\mu_k^{new})^2}{2v^2}=0.$$

因此分母为$N_k$，不是无偏样本修正$N_k-1$。本例$N_1=0.7$，机械除以$N_1-1$甚至会得到负方差。均值也在本轮M步优化，因此偏差须围绕新均值，不能沿用旧的−2或2。

评分: 最大似然分母1分；新均值及理由1分。

题本 Q5(c)

(d) [2]

先对成分求和，再对观测取对数求和。 一个观测可能来自任一成分，所以其密度是加权密度之和；两个独立观测的联合密度是这两个混合密度相乘，取对数才变成下面的和。不能交换“log”和成分求和。E步用旧参数算后验，使辅助下界在旧参数处贴住观测对数似然；M步提高这个固定责任度的下界，因此新的观测对数似然不低于旧值。这是软EM的改进机制，不是一次更新就找到最佳聚类的保证。下一轮才用所有新参数重新计算责任度。

$$\ell(\theta)=\sum_{i=1}^2\log\!\left[\pi_1\varphi(x_i;\mu_1,\sigma_1^2)+\pi_2\varphi(x_i;\mu_2,\sigma_2^2)\right],\qquad\ell(\theta^{new})\ge\ell(\theta^{old}).$$

当E步、M步正确执行且更新有定义时，上述不等式成立。对象是观测混合对数似然，不是最大单成分密度。它不保证唯一全局最优、正确标签或不同初始化的相同结果。交换成分标签不改变混合密度；无约束高斯混合还可能在方差趋零时退化。应更新全部指定参数，而非只更新一个成分。

评分: 正确目标与单调性1分；至少一种合理局限1分。

题本 Q5(d)

Q6. 均值漂移与密度层次 (13)

题本 Q6

(a) [4]

这里有两类位置：会动的查询点和不动的观测。 更新的是$p_t$；原始观测集合$\{0,1,2,4,8\}$保持不变。平坦核只问$|x_i-p_t|\le2$是否成立，不按距离远近给不同权重。起点4的五个距离为4、3、2、0、4，因此只取2与4，平均$(2+4)/2=3$；到3后取1、2、4，平均$(1+2+4)/3=7/3$。一次位置变化变小并不等于已停止，要再次核实邻域及下一次平均不变。

平坦核对闭半径2内原始观测等权，因此每步是这些点的普通平均：

$$p_0=4:\ \{2,4\}\longrightarrow p_1=3;\qquad p_1=3:\ \{1,2,4\}\longrightarrow p_2=7/3;$$ $$p_2=7/3:\ \{1,2,4\}\longrightarrow p_3=7/3=p_2.$$

位置3时，观测1恰好在半径2边界，必须纳入。位置7/3到0,1,2,4,8的距离为$7/3,4/3,1/3,5/3,17/3$，核实邻域不变及固定点$p^*=7/3$。不可把参考观测4改成移动后位置3；参考样本固定。

评分: 三个邻域与更新3分；明确检查固定点1分。

题本 Q6(a)

(b) [4]

本小问使用新的四点数据，别沿用(a)的五点。 这里$x_1=0,x_2=1,x_3=4,x_4=5$，下标是编号，不是数值。核心距离是以该点为中心、能覆盖三个观测（含自身）的最小半径。对于$x_2=1$，到自己为0，到0为1，到4为3，到5为4，所以第三项为3。随后每条边取$\max\{\operatorname{core}_3(x_i),\operatorname{core}_3(x_j),|x_i-x_j|\}$；例如(1,4)取$\max\{4,4,5\}=5$，而(2,3)取$\max\{3,3,3\}=3$。

先计入自身零距离，再选第三个距离：

$$\begin{array}{c|c|c}x_i&\mathrm{sort}_j|x_i-x_j|&\operatorname{core}_3(x_i)\\\hline0&0,1,4,5&4\\1&0,1,3,4&3\\4&0,1,3,4&3\\5&0,1,4,5&4\end{array}$$ $$\begin{array}{c|rrrrrr}(i,j)&(1,2)&(1,3)&(1,4)&(2,3)&(2,4)&(3,4)\\\hline |x_i-x_j|&1&4&5&3&4&1\\d_{mr}(x_i,x_j)&4&4&5&3&4&4\end{array}$$

例如(1,2)普通距离只有1，但互可达距离为$\max\{4,3,1\}=4$，反映两端密度要求。这是三项最大值，不是和；不可排除自身后仍取相同邻居编号。

评分: 四个核心距离2分；六条边权2分。

题本 Q6(b)

(c) [3]

生成树要求连通且没有环。 四个顶点的树恰有三条边，不是简单挑最小的三条边：若三边只围着三个顶点成环，第四点仍没连接。Kruskal逐条检查一条候选边的两端是否已在同一连通分量；若是就跳过。选(2,3)后分量为$\{1\},\{2,3\},\{4\}$；选(1,2)后为$\{1,2,3\},\{4\}$；此时(1,3)在同一分量内，而(2,4)连接两个分量，所以后者可选。

先按权重排序，再按题设字典序破平局：

$$(2,3):3;\quad(1,2):4,\ (1,3):4,\ (2,4):4,\ (3,4):4;\quad(1,4):5.$$

先选(2,3)，再选(1,2)。跳过(1,3)，因为它与前两边形成环。再选(2,4)，四点全部连通：

$$T=\{(2,3),(1,2),(2,4)\},\qquad w(T)=3+4+4=11.$$

这些边在原数值中连接(1,4),(0,1),(1,5)。没有破平局规定时其他同权树也可能正确，但本题已有规则，须遵守。

评分: 排序与跳环1分；树边1分；总权重1分。

题本 Q6(c)

(d) [2]

阈值切割是在图上删边，不是在数轴上按相邻间隔分组。 保留条件是互可达边权不超过3；虽然0与1的普通距离只有1，它们之间的边权是4，仍被删除。孤立顶点也是连通分量，所以必须列出两端单点。但“连通分量”只是此阈值下的图论对象，“最终簇”或“噪声”还取决于后续算法规则，两种名称不能直接互换。

权重不超过3的切割只保留边(2,3)，连通分量为：

$$\{x_1\},\ \{x_2,x_3\},\ \{x_4\}=\{0\},\ \{1,4\},\ \{5\}.$$

这只是密度层次的一个阈值切片。HDBSCAN仍需根据最小簇大小等参数压缩层次，并按稳定性选最终簇。题目未提供这些后续选择，不能仅由切片认定单点必为最终簇或噪声。

评分: 连通分量1分；指出层次压缩、稳定性与最终选择未完成1分。

题本 Q6(d)

Q7. 软区域与中位中心 (6)

题本 Q7

(a) [3]

区域边界来自“到两站点一样近”。 在0与10之间，$|t|=|t-10|$给$t=5$；插入3后，新站点与0的边界为$(0+3)/2=3/2$，与10的边界为$(3+10)/2=13/2$。先保留插入前的旧区域，再求新区间与它们的重叠，不能用更新后的旧区域，否则区域内部互不重叠。权重定义是$w_j=\operatorname{length}(R_x\cap R_j)/\operatorname{length}(R_x)$，所以分别算$(7/2)/5=7/10$及$(3/2)/5=3/10$；分母是同一个新区间长度。

旧站点0和10的中点为5，新站点3的两边界分别是它与0、10的中点：

$$R_1=(-\infty,5],\quad R_2=[5,\infty),\quad R_x=[3/2,13/2],\quad\operatorname{length}(R_x)=5.$$ $$\operatorname{length}(R_x\cap R_1)=5-3/2=7/2,\qquad\operatorname{length}(R_x\cap R_2)=13/2-5=3/2,\quad(w_1,w_2)=(7/10,3/10).$$

权重非负且和为1。共享端点长度为0，不影响答案。旧区域虽无界，新区间及重叠长度有限，不涉及无穷长度相除。这是重叠权重，不是点到站点距离的比例。

评分: 旧边界及新区间1分；两个重叠长度1分；归一化权重1分。

题本 Q7(a)

(b) [3]

先确认距离和中心允许在哪里。 本题最小化绝对距离总和，不是平方距离总和。连续中心允许任意实数$c$，medoid则只能选观测$0,2,9,11$中的一个；必须先求连续最小点集合，再与可选观测相交。对于$2\le c\le9$，$|2-c|=c-2$而$|9-c|=9-c$，所以移动$c$时左右变化正好抵消。配对下界的等号条件分别是$c\in[0,11]$和$c\in[2,9]$，交集才是全部答案。若改成平方距离，目标及导数都变了，均值5.5虽也在本题中位区间，却不能因此证明两种规则一般相同。

$$H(c)=|c|+|2-c|+|9-c|+|11-c|.$$

对每个[2,9]内的c，按符号展开得到同一值：

$$H(c)=c+(c-2)+(9-c)+(11-c)=18.$$

为证明全局最优并找齐所有最小点，配对端点并用三角不等式：

$$|c|+|11-c|\ge11,\qquad|2-c|+|9-c|\ge7.$$

总和至少18，两式同时等号恰在c属于[2,9]。因此全部连续一中位中心为[2,9]；限制为观测值时恰有两个一medoid：2和9。偶数个样本的中间两数平均只是一个最小点，不是唯一解。

$$\sum_i\|x_i-c\|_1=\sum_j\sum_i|x_{ij}-c_j|.$$

L1目标按坐标分离，因此逐坐标中位数最小化它。欧氏长度通过平方根耦合坐标，总和一般由几何中位数最小化，不能逐坐标套用。点(0,0),(2,0),(0,2)的逐坐标中位数为(0,0)，欧氏距离总和4；改取(1/2,1/2)，总和为$1/\sqrt2+\sqrt{10}\approx3.869<4$，直接否定欧氏情形的一般规则。下界证明及反例用于理解，不是额外要求的证明任务。

评分: 全部连续中心1分；全部medoid1分；区分L1及欧氏距离1分。

题本 Q7(b)

订正路线：Q1检查链式求导及损失与惩罚；Q2逐轮列残差、选择、系数与预测，OMP右端保留原始y；Q3先验零行和，再区分核特征值与特征空间方差；Q4写清固定点集、随机抽样、全部点对及失败概率；Q5分开按行责任度归一化与按列有效样本量；Q6检查参考点固定、边界计入及自身计入；Q7先写距离函数及中心允许集合，再用中位数规则。