DDA5001 HW2 复习笔记：从 Softmax 到过拟合

做这次作业时，我有几个地方反复停下来确认。平面上的四个点有一种标记能被直线分开，为什么还不能说它们被打散？交叉熵明明定义在概率上，为什么代码能跳过概率直接算？最后画热力图，为什么训练标签一点噪声都没有，十次模型还是可能更差？

如果已经忘得差不多，可以先扫一眼速查，再从卡住的地方往下读。每段都从题目给了什么开始。

速查

要找什么	先记住哪一步
VC 维度	固定点的位置，试遍所有标签。带截距的 $d$ 维线性分类器的 VC 维度为 $d+1$。
测试误差	测试误差是独立测试集上的平均，样本外误差是对真实分布取期望。
梯度下降	沿负梯度走，小步可以下降，大步可能跨过谷底。
Softmax 与交叉熵	全体分数减去同一个常数，概率不变。单样本损失是 $-\log q_y$。
分类梯度	对 logits 的梯度是 $q-p$。代码把样本放在行上，梯度是 $X^\top(Q-P)/n$。
三种更新	GD 和 Momentum 在当前位置算梯度，Nesterov 在外推点算梯度。
多项式回归	每个输入先变成一行基函数值，然后用 least squares 拟合系数。
解析样本外误差	对齐两组系数，缺项补零。系数差 $b_k$ 的贡献是 $b_k^2/(2k+1)$。
过拟合热力图	红色表示十次模型的平均样本外误差更大。黑线表示平均差为零。

VC 维度

Problem 1 先问二分类模型的表达能力。二维的 affine linear classifier（仿射线性分类器）用一条直线分开正负标签，直线可以平移，所以包含截距 $b$。Shatter（打散）的测试是固定一组点，换遍它们的 $2^n$ 种标签，每次都允许重新选一条直线。

三个不共线的点可以打散。三点同类时把直线放在三角形外，一点和另外两点异类时把那个顶点切出来。四点如果围成凸四边形，就给对角上的两点同一个标签。两组点各自连成的线段相交，直线无法把两组放在两侧。如果一点在另外三点的三角形内，就让内点单独为正。包含三角形三个顶点的半平面也包含内点。如果有三点共线，让中间点和两端异类即可。

做题时我想到把四边形沿周边标成 $+,-,-,+$，这确实可能分开。卡住的地方在“任意标签”这四个字。证明某组点无法打散，只要找到一种分不开的标签。

高维版也可以从这张图想起。$d+1$ 个仿射无关的点能让仿射函数分别取任意指定的 $+1$ 或 $-1$。而任取 $d+2$ 个点，增广向量 $(x_i,1)$ 必有线性依赖。把依赖式里正系数和负系数移到两侧，再各自除以系数之和，得到两组点的凸组合落在同一个位置。给这两组相反标签就无法分开，所以三维的答案是四。

测试误差

先固定已经训练好的模型。Out-of-sample error（样本外误差）问的是再从真实分布抽一个样本，平均会损失多少。Test error（测试误差）用一份独立测试集的实际平均值来估计它。同一个模型换一份测试集，估计值可能变化。训练误差用过模型拟合的那批数据，第三题会用到它和样本外误差的区别。

梯度下降

凸函数（convex function）的图像在任意两点的连线下方或与连线重合。对于可微凸函数，切平面是整个函数的下界，因此梯度为零时，该点就是全局最小点。开口朝下的抛物线是凹函数，顶点是最大点。

GD（gradient descent，梯度下降）用 $\theta_{k+1}=\theta_k-\mu\nabla L(\theta_k)$ 更新。梯度指向上升方向，减号负责转向下降。以 $L(\theta)=\theta^2$、起点 $1$ 为例，梯度是 $2$。学习率 $0.1$ 走到 $0.8$，损失从 $1$ 变成 $0.64$。学习率 $2$ 走到 $-3$，损失变成 $9$。所以凸性和一步是否下降是两回事。梯度非零时，沿负梯度的方向导数是 $-\lVert\nabla L\rVert^2$，足够小的正步长会下降。更新量很小只说明 $\mu\lVert\nabla L\rVert$ 小，曲面很平或者学习率很小也会有这种现象。

Softmax 与交叉熵

Problem 2 的多分类逻辑回归先给每一类一个分数 $z_k=\theta_k^\top x$，再用 softmax 把分数变成概率。这里 score 和 logit 都指 softmax 的输入。$q_k=e^{z_k}/\sum_j e^{z_j}$。分数最大的一类概率也最大。所有分数加同一个数，指数里的共同因子会约掉。乘同一个正数会保留排序，但通常会改变概率。

训练时用 $p$ 表示真实标签的 one-hot vector（独热向量），用 $q$ 表示预测概率。真实类别为 $y$ 时，交叉熵 $-\sum_jp_j\log q_j$ 只剩 $-\log q_y$。比如正确类概率从 $0.1$ 掉到 $0.0001$，即使两次都猜错，损失也从约 $2.30$ 涨到 $9.21$。这就是为什么交叉熵和准确率可能给出不同的排名。

代码里可以先把每个样本的最大分数减掉，记 $s_j=z_j-\max_\ell z_\ell$。把 softmax 代入交叉熵后得到

$$-\log q_y=-s_y+\log\sum_j e^{s_j}.$$

我当时卡在“怎么忽然能用 logits 算损失了”。把分式代进去展开对数就能看出来，等式两边是同一个量。对于 logits $(0,-1000)$ 且真实类别是第二类，直接算 $q_y$ 可能先舍入到零。上面的式子先留下 $-s_y=1000$，即使 $e^{-1000}$ 舍入到零，损失仍然是有限的 $1000$。

分类梯度

想更新类别 $k$ 的参数，先求损失对它的分数 $z_k$ 的导数。$z_k$ 出现在所有类别共享的分母里，因此每个 $q_j$ 都可能变化。对 $q_j$ 求导时只取交叉熵的第 $j$ 项，得到 $-p_j/q_j$。再沿 softmax 传回去：

$$\frac{\partial q_j}{\partial z_k}=q_j(\mathbf 1_{j=k}-q_k).$$

当 $j=k$ 时，分子和分母都在变，结果是 $q_k(1-q_k)$。当 $j\ne k$ 时只有分母变，结果是 $-q_jq_k$。乘上前一步并求和，

$$\frac{\partial H}{\partial z_k} =-p_k(1-q_k)+q_k\sum_{j\ne k}p_j =q_k-p_k.$$

因为 $z_k=\theta_k^\top x$，再乘一个 $x$ 就得到单样本对该类权重的梯度。若 $x$ 写成列向量，把所有类放在一起是 $x(q-p)^\top$。实际代码中 $X$ 是 $n\times d$，一行一个样本，参数 $\Theta$ 是 $d\times K$，一列一个类别。于是 $X\Theta$ 是 $n\times K$ 的 logits，$X^\top(Q-P)/n$ 是 $d\times K$ 的平均梯度。这里 $d$ 是特征数，$K$ 是类别数，$n$ 是样本数。

三种更新

记 $G$ 为梯度，$\Delta_k=\theta_k-\theta_{k-1}$ 为上一步位移。把题目的三种方法放在一起看，区别主要在用哪个位置的梯度。

方法	一步怎么走
GD	$\theta_{k+1}=\theta_k-\mu G(\theta_k)$。
Momentum（动量）	在 GD 的一步上加 $\beta\Delta_k$。
Nesterov	先算 $u_k=\theta_k+\frac{k-1}{k+2}\Delta_k$，再从 $u_k$ 走 $-\mu G(u_k)$。

可以把 Nesterov 的外推点当作“沿惯性先看一眼”。如果外推到了谷底另一侧，那里的梯度可能已经反向，这次更新就会往回修正。$\frac{k-1}{k+2}$ 是题目给定的调度系数。代码里用中心差分检查梯度，再用简单的 $G(A)=2A$ 验证两种加速方法在哪里取梯度、更新后到了哪里。

跑完 1,000 步后，Digits 上 Nesterov 的测试准确率是 $96.94\%$，但测试交叉熵约 $0.16767$，高于 Momentum 的 $0.11556$。Nesterov 的测试损失约在第 185 步达到最低，之后训练损失继续下降，测试损失却回升。Dry Bean 的结果不同，Nesterov 最终训练和测试损失都是三种方法中最低的。这里比较的是两份数据上的实测曲线。

多项式回归

Problem 3 改做回归。题目先生成一个真实函数 $g$，抽出 $n$ 个均匀分布在 $[-1,1]$ 的输入。训练标签是 $y_i=g(x_i)+\sigma\epsilon_i$，其中 $\epsilon_i$ 是标准正态噪声，所以噪声方差是 $\sigma^2$。二次和十次模型用同一批输入和标签拟合。

题目给的 Legendre polynomials（勒让德多项式）是一组基函数。前三项是 $L_0(x)=1$、$L_1(x)=x$、$L_2(x)=(3x^2-1)/2$。输入一个 $x$，算出各个 $L_k(x)$，就是这一行特征。比如 $x=0$ 时，二次模型那一行是 $(1,0,-1/2)$。模型 $f_K(x)=\sum_{k=0}^K w_kL_k(x)$ 对输入可以是弯的，对待学习的系数 $w_k$ 仍然是线性的。

把 $n$ 行堆成 $X_K$，形状是 $n\times(K+1)$。最小化 $\lVert X_Kw-y\rVert^2/n$，令梯度 $2X_K^\top(X_Kw-y)/n$ 为零，得到正规方程 $X_K^\top X_Kw=X_K^\top y$。

解为什么唯一？如果有非零 $c$ 使 $X_Kc=0$，那么 $h(x)=\sum_{k=0}^K c_kL_k(x)$ 在每个训练输入上都为零。取最高一个非零系数，它的最高次项无法被低次项抵消，所以 $h$ 是次数至多 $K$ 的非零多项式。$n\ge K+1$ 个不同输入会给它至少 $K+1$ 个不同的根，矛盾。于是 $X_K$ 满列秩，$v^\top X_K^\top X_Kv=\lVert X_Kv\rVert^2>0$ 对非零 $v$ 成立，正规方程有唯一解。

实现用 np.linalg.lstsq(X, y, rcond=None)[0] 求系数。rcond=None 使用 NumPy 的默认数值秩阈值。[0] 取的是返回元组里的整组系数。一次传入 $n\times m$ 的 labels 时，每列是一组独立拟合任务，共享同一个 $X$，返回的每列也是一组权重。

解析样本外误差

这里的 $E_{\rm out}$ 是预测与干净目标 $g$ 的平均平方差。输入均匀落在长度为 $2$ 的区间上，密度就是 $1/2$，所以取期望等于 $\tfrac12\int_{-1}^{1}(f_K-g)^2\,dx$。

先把两个函数写进同一组基。目标次数记为 $Q_g$，题目把目标的整组随机系数除以归一化因子 $C_Q$，因此目标系数为 $t_k=a_k/C_Q$。这种缩放让跨随机目标和输入的平均平方值为 $1$。实现收到的 $t_k$ 已经缩放过。对齐到 $M=\max(K,Q_g)$，缺的项补零。比如模型只有二次，目标还有三次项时，$b_3=w_3-t_3=0-t_3$。

题目直接给出 Legendre 基的 orthogonality（正交性）。可以把两个函数相乘再积分想成向量点积的连续版。不同下标的乘积积分为零，同一下标的平方积分为 $2/(2k+1)$。因此

$$E_{\rm out} =\frac12\int_{-1}^{1}\left(\sum_{k=0}^{M}b_kL_k(x)\right)^2dx =\frac12\sum_{k=0}^{M}b_k^2\frac{2}{2k+1} =\sum_{k=0}^{M}\frac{b_k^2}{2k+1}.$$

交叉项是在积分后消掉的。分母的 $2k+1$ 来自基函数的平方积分，分子上的 $2$ 刚好与均匀密度的 $1/2$ 抵消。如果误差函数恰好是 $L_0+3L_1$，结果就是 $1^2+3^2/3=4$。代码因此只需要系数。实验前用已知的无噪声二次多项式检查系数恢复，再用数值积分核对解析误差，两者的差在 $10^{-14}$ 量级。

过拟合热力图

十次模型包含二次模型，因此最优训练误差不会更大。每个格子做 1,000 次模拟，颜色表示 $\rho_e=E_{\rm out}(f_{10})-E_{\rm out}(f_2)$ 的算术平均。红色表示十次模型在样本外更差，蓝色表示更好。黑线是平均差为零的等高线。超过 $\pm0.25$ 的格子颜色会饱和，计算均值时仍保留原始数值。

横着读，固定真实函数次数 $Q_g=20$，训练点从 $80$ 增到 $120$，平均差从 $0.0874$ 变到 $-0.1193$。少量训练点对曲线的约束弱，十次曲线可以在训练点上贴得很好，在采样稀疏的地方却偏得很远。

竖着读，固定 $n=120$。当 $Q_g=1$ 或 $2$ 时，二次模型已经能表达整个目标。到 $Q_g=10$ 时，十次模型能表达二次模型够不到的那些项，平均差降到约 $-0.2964$。我当时看到再往上蓝色变浅，想到十次模型也开始跟不上了。更准确地读是两者的误差差距缩小了。两种模型都缺少十次以上的项，而且改变 $Q_g$ 时归一化也会缩放已有项。图上只有差值，读不出两边各自涨了多少。

在 $n=120$ 那一列，噪声方差从 $0$ 增到 $2$，平均差从 $-0.1469$ 升到 $0.1969$。数据少时，连底部 $\sigma^2=0$ 也有红色。比如 $n=80$ 时平均差约 $0.0168$。我当时想到的是数据点不够。这里真实函数是二十次，十次模型本来也表达不全。即使标签完全准确，少量随机选中的点仍可能让十次模型得到一条在别处偏差很大的曲线。这个例子可以用来记住，无观测噪声时也可能出现相对于二次模型的过拟合。

合上笔记再试一次

1. 四个点围成凸四边形，给出一种直线分不开的标签。解释为什么一种就够。
2. 真实类的 logit 是 $-1000$，另一类是 $0$。不先算概率，直接用稳定公式算损失。
3. 模型没有 $L_3$，目标的 $L_3$ 系数为 $2$。它对样本外误差贡献多少？

可以先口头答一遍再核对。第一题把两个对角顶点标成正类，两条对角线相交。第二题是 $1000+\log(1+e^{-1000})\approx1000$。第三题的系数差是 $-2$，平方后除以 $7$，得到 $4/7$。