DDA5001 HW1：从最小二乘到 Pocket

这次 HW1 我在好几道题上都卡在“公式好像认识，但不知道证明从哪一步开始”。我把做题时问过的问题和后来跑出来的结果串在一起，留一份可以回头查公式的笔记。前面是速查，后面按线性代数、损失函数、感知机的顺序展开。

速查

公式卡

要查什么	公式 / 结论	条件或提醒
满列秩最小二乘	$\hat\theta=(X^\top X)^{-1}X^\top y$	$X$ 满列秩时解唯一
欠定最小二乘	$\theta=U_1\Sigma_1^{-1}V^\top y+U_2b$	$n<d$ 且 $\operatorname{rank}(X)=n$；任意 $b$ 都给出零残差解
岭回归	$\hat\theta=(X^\top X+\lambda I)^{-1}X^\top y$	$\lambda>0$ 时解唯一
高斯噪声 MLE	$\arg\min_\theta\|X\theta-y\|_2^2$	独立同方差高斯噪声
Laplace 噪声 MLE	$\arg\min_\theta\|X\theta-y\|_1$	独立同分布 Laplace 噪声
Huber 梯度	$\nabla L(\theta)=X^\top\psi_\mu(X\theta-y)$	按作业定义逐样本求和，梯度维度是 $d$
Perceptron 更新上界	$k\le R^2\|\theta^\star\|_2^2/\rho^2$	只对严格线性可分数据给出保证
Pocket 训练错误	$E_{\rm in}(\hat\theta_k)=\min_{0\le j\le k}E_{\rm in}(\theta_j)$	只保证训练错误不增加，不保证测试错误

题目路线图

题目	原题在检查什么	这部分要连起来的知识
Problem 1	分辨学习任务、回归与分类，并判断关于最小二乘等方法的说法	预测目标、矩阵秩、唯一性与结论的适用条件
Problem 2	在欠定矩阵的 SVD 下写出所有最小二乘解，再推导加入 $L_2$ 惩罚后的解	行空间、零空间、正规方程与正定性
Problem 3	从 Laplace 误差推出 MLE；推导 Huber 梯度并用数值结果核对	条件密度、独立样本似然、链式法则与有限差分
Problem 4	对线性可分数据证明 Perceptron 错误更新次数有上界	margin 下界、参数范数上界与 Cauchy–Schwarz
Problem 5	实现并观察 Pocket 算法在训练集与测试集上的表现	当前参数、历史最佳 checkpoint，以及训练/测试的区别

下面按题目出现的顺序补背景和推导。Problem 1 的若干判断会在 Problem 2–4 中得到更扎实的解释，所以读时可以把它看作整份作业的概念预检。

预测目标

监督学习有输入和对应的目标；无监督学习只有输入，目标是从数据中找结构。回归和分类的区别则在预测目标：数值还是类别。

Problem 1(a) 让我们用例子区分 supervised learning 和 unsupervised learning；同题判断题又把回归、分类、最小二乘和学习算法的性质放在一起。最可靠的起点是看两件事：训练数据有没有目标值，模型最后预测的是数值还是类别。

我一开始把“regression 用来拟合曲线”记得很牢，却在选择题里把它和 categorical labels 混到了一起。拟合一条曲线通常是在预测连续数值；类别标签属于分类问题。监督学习的例子可以是拿带类别的图片训练分类器，无监督学习则可能从没有标签的数据里学到相似性或低维表示。

这也解释了另外两个容易混的判断：感知机不保证对同一数据集总能得到唯一分类器；最小二乘也不是任何噪声分布下的最大似然估计。后者取决于噪声模型，下一节会把这层关系写开。

秩与零空间

最小二乘解是否唯一，关键看 $X$ 有没有非零零空间方向；而 $X$ 满列秩时，$X^\top X$ 正定，才可以放心求逆。

这部分对应 Problem 1 里“样本数少于特征数时，最小二乘解是否唯一”的判断，以及 Problem 2 的两个小题。Problem 1 只需解释为什么不唯一；Problem 2(a) 要写出全部解，Problem 2(b) 则通过正则项消除自由度。

先统一符号。$X\in\mathbb R^{n\times d}$ 有 $n$ 行、$d$ 列；每行是一个样本，每列是一种特征，参数 $\theta\in\mathbb R^d$，预测是 $X\theta\in\mathbb R^n$。当 $n<d$ 时，约束数量少于参数方向数量。数据只通过 $X\theta$ 观察参数，所以任何落在零空间里的改变量都不可见。

rank（秩）是矩阵中线性独立方向的数量；null space（零空间，也叫 kernel，核）是 $X$ 会映成零的向量集合：$\operatorname{null}(X)=\{v:Xv=0\}$。rank–nullity theorem（秩-零化度定理）给出 $d=\operatorname{rank}(X)+\dim\operatorname{null}(X)$。因为 $\operatorname{rank}(X)\le n<d$，零空间里必有非零方向。

先看 $n<d$ 的情形。$X$ 有 $d$ 列，但秩最多是 $n$，所以由秩-零化度定理，$\operatorname{null}(X)$ 至少有一个非零向量 $v$。对任意参数 $\theta$ 和实数 $t$，

$$X(\theta+tv)=X\theta+tXv=X\theta.$$

沿着 $v$ 移动不会改变预测，也不会改变最小二乘目标值；因此只要有一个最小化解，就有无穷多个。若进一步假设 $\operatorname{rank}(X)=n$，作业给出的 SVD 形式可以把这些解写成速查表中的表达式。$U_2b$ 落在 $X$ 的零空间里，所以它改变参数，却不改变 $X\theta$。此时 $X$ 满行秩，任意 $y$ 都能被拟合，最优残差为零。

Problem 2(a) 给了 SVD $X=V\Sigma_1U_1^\top$，并要求描述所有 minimizers（最小化解）。本题的字母顺序与常见教材 $X=U\Sigma V^\top$ 相反：这里 $V$ 是 $n\times n$ 正交矩阵，$\Sigma_1$ 可逆，$U_1$ 的列张成参数空间中能被 $X$ 看见的方向，$U_2$ 张成 $\operatorname{null}(X)$。

把 $\theta$ 写成 $U_1a+U_2b$。因为 $XU_2=0$，参数中的 $b$ 不影响预测；而 $X\theta=V\Sigma_1a$。$X$ 满行秩时，令 $V\Sigma_1a=y$ 就能把每个观测完全拟合，解得 $a=\Sigma_1^{-1}V^\top y$。代回后就是所有最小二乘解。再代回 $X\theta$ 检查，得到 $VV^\top y=y$，所以残差为零，最优目标值为零。这里 $b$ 可以任意，不是“答案里可以随便加东西”，而是 $U_2b$ 正好处在矩阵看不见的零空间里。

Problem 2(b) 加入 $\lambda\|\theta\|_2^2$ 是 ridge regression（岭回归）：第一项鼓励拟合数据，第二项惩罚参数太大。对 $f(\theta)=\|X\theta-y\|_2^2+\lambda\|\theta\|_2^2$ 求梯度，得到 $2X^\top(X\theta-y)+2\lambda\theta$；令它为零并除以 $2$，就得到正规方程。$I$ 是 $d\times d$ 单位矩阵，必须乘在标量 $\lambda$ 后才能与 $X^\top X$ 相加。

加上 $\lambda\|\theta\|_2^2$ 后，岭回归的一阶条件是

$$(X^\top X+\lambda I)\theta=X^\top y.$$

这里的 $I$ 不能省略：$X^\top X$ 是 $d\times d$ 矩阵，而 $\lambda$ 是标量。对于任意非零 $z$，$z^\top(X^\top X+\lambda I)z=\|Xz\|_2^2+\lambda\|z\|_2^2>0$，所以矩阵可逆，解唯一。

正定（positive definite）表示任意非零方向 $z$ 上都有 $z^\top Az>0$。在岭回归中，

$$z^\top(X^\top X+\lambda I)z=\|Xz\|_2^2+\lambda\|z\|_2^2>0,$$

因为 $\lambda>0$。因此矩阵可逆、解唯一。可以用一维例子建立直觉：$X=[1], y=2, \lambda=1$ 时，目标是 $(\theta-2)^2+\theta^2$，最小值在 $\theta=1$；惩罚把参数向零拉，但不会强迫参数等于零。

反过来看满列秩的情形：线性独立意味着 $Xz\ne0$ 对所有非零 $z$ 成立，于是

$$z^\top X^\top Xz=(Xz)^\top(Xz)=\|Xz\|_2^2>0.$$

这正是正定的定义，也说明最小二乘目标在这个情形下是严格凸的，唯一解来自正规方程。

易混点：我当时还问过“正定是不是行列式为正”。不是。正定要求每个非零向量 $z$ 都满足 $z^\top Az>0$；行列式为正本身不足以推出正定，例如 $\operatorname{diag}(-1,-1)$ 的行列式是正数，但它不是正定矩阵。

噪声与似然

先指定误差的分布，再写观测数据的似然；换一种噪声分布，最大似然对应的损失也会换。

Problem 3(a) 给出 $y=X\theta+e$ 和 Laplace（拉普拉斯）误差密度，要求从误差分布推导 likelihood（似然），再找 maximum-likelihood estimator，MLE（最大似然估计）。它不是让我们猜损失形式；要从模型的概率假设出发。

在线性模型 $y=X\theta+e$ 里，单个残差是 $e_i=y_i-x_i^\top\theta$。先分清 probability density（概率密度）和 likelihood（似然）。给定输入 $x_i$ 与参数 $\theta$，$p(y_i\mid x_i;\theta)$ 描述可能观测值 $y_i$ 的条件密度。数据观测以后，固定这组 $y_i$，再把不同的 $\theta$ 代进去比较，这个关于参数的函数才叫似然。似然不是天然归一化的参数概率分布；后者还需要贝叶斯推断里的先验等信息。

题目假设 errors are i.i.d.（误差独立同分布）。独立让联合密度拆成每个样本密度的乘积，同分布则让每一项使用同一个误差分布公式。比如两次独立观测同时落在各自小区间的联合密度，是两项密度相乘；不是取平均，也不是把一个概率乘以样本数。

把它代入误差密度，就得到给定输入和参数时观测 $y_i$ 的条件密度 $p(y_i\mid x_i;\theta)$。误差独立时，整组观测同时出现的联合密度是各项密度的乘积：

$$L(\theta)=\prod_{i=1}^n p(y_i\mid x_i;\theta).$$

取负对数会把乘积变成和，再去掉与 $\theta$ 无关的常数，就留下要最小化的损失。

• 这也是 Problem 1 中“最小二乘是否总是 MLE”这一类判断的依据：只有在独立、同方差、零均值 Gaussian noise（高斯噪声）等相应假设下，负对数似然才与平方残差和等价。换成 Laplace 噪声，残差绝对值进入负对数似然，于是得到 $L_1$ 目标。

若误差是独立同分布的 $\mathcal N(0,\sigma^2)$，负对数似然中与参数有关的部分正比于 $\sum_i(y_i-x_i^\top\theta)^2$，所以 MLE 是最小二乘解。

• 若误差是独立同分布的 Laplace$(0,b)$，则 $-\log L(\theta)=n\log(2b)+\frac1b\sum_i|y_i-x_i^\top\theta|$。忽略常数和正比例系数后，MLE 最小化绝对误差之和，也就是 $L_1$ 损失。

我在这里曾把“似然”想成“参数 $\theta$ 的概率分布”。更准确地说，数据已经观测到以后，$L(\theta)$ 是一个关于参数的函数：比较不同 $\theta$ 对这组已观测数据的支持程度。它本身不是 $\theta$ 的概率分布；要得到参数的后验分布，还需要贝叶斯模型里的先验等内容。

Huber 验证

Huber 把绝对值函数在零附近的尖角换成二次曲线；验证梯度时，有限差分的步长不能只图小，损失的 sum/mean 约定也要保持一致。

Problem 3(b) 要求先写逐点 Huber 函数的导数，再用链式法则求参数梯度；Problem 3(c) 和 (d) 接着要求通过代码与有限差分检查梯度，并比较 sum loss 和 mean loss。因此这题把手推、编程实现和数值验证放在同一条线上。

Huber loss（Huber 损失）是 robust loss（稳健损失）：残差小的时候用二次函数，保留平方损失在零附近的平滑性质；残差大时改用线性增长，降低离群点对梯度的支配。作业中 $\mu$ 是中心二次区间的宽度，函数在 $z=\pm\mu$ 两侧接合。

作业定义的平滑函数在 $|z|<\mu$ 时为 $z^2/(2\mu)+\mu/2$，在外侧为 $|z|$。它的导数是

$$h_\mu'(z)= \begin{cases} -1,&z\le -\mu,\\ z/\mu,&|z|<\mu,\\ 1,&z\ge \mu. \end{cases}$$

对 $L(\theta)=\sum_i h_\mu((X\theta-y)_i)$ 用链式法则，先对每个残差算导数，再乘上残差对参数的 Jacobian $X$：

$$\nabla L(\theta)=X^\top h_\mu'(X\theta-y)\in\mathbb R^d.$$

也可以按坐标验证链式法则。令 $r=X\theta-y$，那么 $\partial r_i/\partial\theta_j=X_{ij}$。对 $L=\sum_i h_\mu(r_i)$，有 $\partial L/\partial\theta_j=\sum_i h_\mu'(r_i)X_{ij}$；把每个参数方向的偏导排起来，正是 $X^\top h_\mu'(r)$。所以转置来自“把残差空间的变化传回参数空间”，而不只是维度凑巧合适。

左乘 $X^\top$ 不只是为了“把维度凑成 $d$”。它是链式法则：残差向量对 $\theta$ 的导数是 $X$，把残差空间里的梯度传回参数空间就得到 $X^\top$。

我用中心有限差分估计方向 $v$ 上的导数：

$$\frac{L(\theta+tv)-L(\theta-tv)}{2t}\approx \nabla L(\theta)^\top v.$$

finite difference（有限差分）是用函数值变化近似导数。中心差分同时取 $\theta+tv$ 与 $\theta-tv$，用两点损失之差除以 $2t$，近似 directional derivative（方向导数）$\nabla L(\theta)^\top v$。一阶 Taylor expansion（泰勒展开）说明小步长下二者应该接近。

在作业的 $n=5$ 小例子里，解析方向导数是 $1.1$。当 $\mu=10^{-5}$ 时，步长 $10^{-7}$ 的有限差分误差约为 $4.0\times10^{-14}$，步长再缩到 $10^{-9}$，误差反而约为 $2.4\times10^{-12}$。步长太大时，局部线性近似不够好；太小时，两个很接近的损失相减会损失浮点精度，再除以小步长会放大误差。这和 Taylor 展开里“有限步长有截断误差、极小步长有舍入误差”的权衡一致。

为什么误差会先降后升？步长较大时，局部线性近似不够准，截断误差明显；步长极小时，两个很接近的浮点损失值相减会损失有效数字，再除以很小的 $2t$ 会放大舍入误差。因此有限差分不是步长越小越好。作业中的解析方向导数是 $1.1$；$\mu=10^{-5}$ 时，$t=10^{-7}$ 的绝对误差约 $4.0\times10^{-14}$，$t=10^{-9}$ 时约 $2.4\times10^{-12}$。

还有一个简单但重要的缩放关系：$L_{\rm mean}=L_{\rm sum}/n$，所以 $\nabla L_{\rm sum}=n\nabla L_{\rm mean}$。在同一个参数点使用相同学习率，平均损失的更新幅度会小 $n$ 倍；要得到同样的更新，平均损失对应的学习率需要乘 $n$。作业代码实现的是 sum loss；小例子里的比值也约为 $5$。

sum loss 和 mean loss 的比例也可以从公式直接读出：$L_{\rm mean}=L_{\rm sum}/n$，所以 $\nabla L_{\rm mean}=\nabla L_{\rm sum}/n$。当 $n=5$ 时比值应为 $5$。若比较同一个参数点的普通梯度下降更新，mean 版本要把学习率乘 $n$ 才有同样的更新幅度；这项换算假设没有其它正则项缩放、梯度裁剪或自适应优化器机制混进来。

完整实验使用 $\mu=10^{-5}$、学习率 $0.001$、1000 次更新和随机种子 $0$。以真实参数计算的误差只用于评估，不参与拟合或选取迭代点。最小二乘估计误差约为 $59.51$；Huber 参数误差从初始化时的 $8.9899$ 降到第 1000 次更新后的 $5.6187$。这里的下降是训练过程中的变化，$\mu$ 一直固定，并不是因为把 $\mu$ 调小了。

易混点：Huber 参数里的 $\mu$ 控制二次区间宽度；有限差分里的 $t$ 是数值求导步长。它们都可能取很小的数，但作用完全不同。

Perceptron 收敛

线性可分时，每次犯错都会让参数朝一个固定分离方向前进；参数范数增长又有上界，两者合起来就能推出犯错次数有限。

Problem 4 的前提是训练数据严格线性可分，标签为 $y_i\in\{-1,+1\}$。题目给出每次犯错时的更新公式，让我们逐步证明错误更新次数有上界。几个小题不是各自独立的技巧：先得到分离方向上的进展下界，再控制参数范数的增长，最后用不等式把两边夹起来。

margin（间隔）$y_i\theta^{\star\top}x_i$ 把正负样本的“正确方向”统一写成正数；值越大，样本离分界面越远。因为训练集有限，所有正 margin 中最小的一个仍为正数，记作 $\rho$。如果训练集无限，“每个 margin 都大于零”并不足以保证它们的下确界大于零，所以有限样本是证明 $\rho>0$ 的必要条件。

设存在 $\theta^\star$，使每个训练样本都满足 $y_i\theta^{\star\top}x_i>0$。样本数有限，因此这些正数的最小值

$$\rho=\min_i y_i\theta^{\star\top}x_i$$

仍然大于零。这是证明的起点；“每个都大于零”要靠有限样本才能推出“最小值也大于零”。

在第 $k$ 次犯错时，更新为 $\theta_k=\theta_{k-1}+y_{k-1}x_{k-1}$。与分离方向做内积：

$$\theta_k^\top\theta^\star =\theta_{k-1}^\top\theta^\star+y_{k-1}x_{k-1}^\top\theta^\star \ge \theta_{k-1}^\top\theta^\star+\rho.$$

这就是 (b) 的作用：每发生一次 mistake update，当前参数在 $\theta^\star$ 方向上的投影至少增加 $\rho$。$\theta_0=0$ 是题目给定的算法初始化；若从非零参数开始，递推式要额外包含初始内积 $\theta_0^\top\theta^\star$。

从 $\theta_0=0$ 递推 $k$ 次，就有 $\theta_k^\top\theta^\star\ge k\rho$。另一方面，展开更新后的平方范数：

$$\|\theta_k\|_2^2 =\|\theta_{k-1}\|_2^2+2y_{k-1}\theta_{k-1}^\top x_{k-1}+\|x_{k-1}\|_2^2.$$

这是 (c) 与 (d) 要得到的另一半：展开 $\|\theta_k\|_2^2$ 后，交叉项不为正，标签平方 $y^2=1$，而输入范数不超过 $R$，所以每次最多把平方范数增加 $R^2$。累积 $k$ 次得到 $\|\theta_k\|_2^2\le kR^2$。按作业的零分数 tie-breaking，负类在分数恰为零时仍算错分，但交叉项等于零；所以这里要证明的是 $\le0$，不是严格小于零。

被选中的样本当前是错分的，所以按作业的零分数约定，$y_{k-1}\theta_{k-1}^\top x_{k-1}\le0$。再用 $\|x_i\|_2\le R$ 和 $\theta_0=0$ 递推，得到 $\|\theta_k\|_2^2\le kR^2$。这就是 (e) 中 Cauchy–Schwarz inequality（柯西–施瓦茨不等式）的用法：任何两个向量的内积绝对值都不超过它们的范数乘积。结合内积至少为 $k\rho$、参数范数至多为 $\sqrt{k}R$，可知 $k\rho\le\sqrt{k}R\|\theta^\star\|_2$。因为 $k>0$，除以正数 $\sqrt{k}\rho$ 后得到错误次数上界。单独有范数上界推不出收敛；还必须同时有沿分离方向不断增长的下界。

最后由 Cauchy–Schwarz 不等式，

$$k\rho\le \theta_k^\top\theta^\star \le \|\theta_k\|_2\|\theta^\star\|_2 \le \sqrt{k}R\|\theta^\star\|_2,$$

因此 $k\le R^2\|\theta^\star\|_2^2/\rho^2$。犯错次数不可能超过这个有限上界，感知机就必须停下来。

举一个带 bias coordinate 的小例子：$x_+=(1,1),y_+=1$，$x_-=(1,-1),y_-=-1$，取 $\theta^\star=(0,1)$。两个样本的 margin 都是 $1$，所以 $\rho=1$；$R=\sqrt2$，$\|\theta^\star\|=1$，上界是 $k\le2$。从零向量出发，零分数按规则预测 $+1$，先错分负类样本，更新一次后两个样本都分对了，实际一次就停。

易混点：零分数预测 $+1$。所以负类样本的分数为零时也算错分，但这时 $y\theta^\top x=0$，不是严格负数。证明只需要交叉项小于等于零，不需要小于零。这个保证也只适用于严格线性可分数据；不可分时不能照搬。

Pocket

Pocket 保留的是训练错误最低的历史参数，而当前感知机继续沿着自己的轨迹更新；因此 Pocket 训练错误不增，测试错误却可能上升。

Problem 5 面对的是更实际的设置：真实图片特征不一定严格线性可分，普通 Perceptron 可能在训练中持续犯错。Pocket 的目标不是改变单步更新规则，而是在当前感知机继续运行时，额外保存迄今训练错误最低的一组参数。

P5 在数字 1 和 6 上构造了两个特征：平均像素强度和左右不对称度，再加上常数 bias，形成 $\tilde x=(1,\text{intensity},\text{asymmetry})$。bias（偏置）是常数坐标带来的截距：$\theta^\top\tilde{x}=\theta_0+\theta_1\,\text{intensity}+\theta_2\,\text{asymmetry}$。令分数为零就是分类边界；若没有常数坐标，这条直线会被限制为经过原点。作业用平均像素强度和左右不对称度两个手工特征来展示线性边界，而不是在所有原始像素上训练复杂模型。

分类边界是 $\theta_0+\theta_1\text{intensity}+\theta_2\text{asymmetry}=0$；bias 让直线可以平移，不必经过原点。

把算法看成两个状态会更清楚：当前参数 $\theta$ 每轮照常更新；Pocket 参数 $\hat\theta$ 只在新训练错误严格下降时才被替换。替换时要复制 weights（权重），而不是保存一个之后仍会被原地修改的引用。错误相同或上升都不触发替换，但当前参数仍继续向前走，不会重置回 Pocket。

每次从当前参数里随机挑一个错分训练样本，执行 $\theta\leftarrow\theta+y_i\tilde x_i$。Pocket 只在新训练错误严格更低时替换，并复制一份权重；如果错误持平或变大，就保留旧 Pocket。下一步仍从当前参数继续，不会回到 Pocket 参数重启。

toy trace（小型轨迹）把规则单独隔离出来：当前训练错误从 $0.50$ 降到 $0.25$ 后，又能在下一次更新回升到 $0.50$；Pocket 仍留着之前错误为 $0.25$ 的参数。它保存的是历史最好值，不是当前参数，也不是要求当前模型从此不再犯错。

toy trace 里，Pocket 的训练错误序列是 $[0.50,0.50,0.25,0.25,0.25,0.25,0.25]$，等于当前感知机训练错误的历史最小值。第 3 次更新后，当前错误从 $0.25$ 涨到 $0.50$，Pocket 仍保存错误为 $0.25$ 的旧权重。这不是“停在 0.25 不动”的 bug，而是它的选择规则在工作。

当前模型错误率的下降不是单调的；Pocket 的训练错误之所以单调不增，是由“仅当训练错误严格降低才替换”这条代码规则直接保证的。测试错误没有用于挑 Pocket，因而可能上升。它是独立样本上的泛化表现估计，不是训练集最优化目标；一次测试错误上升本身不能说明 Pocket 更新规则错了。

完整实验使用 seed $0$、最多 2000 次错误更新。筛出的训练集和测试集分别有 1669 和 434 个样本。当前感知机训练错误从 $0.397843$ 结束于 $0.040144$，中间会波动；Pocket 训练错误单调不增，结束于 $0.032355$。但 Pocket 测试错误确实有两次上升：第 54 到 55 次更新从 $0.066820$ 到 $0.069124$，第 453 到 454 次从 $0.059908$ 到 $0.064516$。测试错误没有参与 Pocket 选择，所以它上升本身不能说明实现错了。

这道题我最后决定保留实现。检查 toy trace 的运行最小值、保存权重和错误计数后，Pocket 规则都对得上；测试错误的上升则是算法允许出现的结果。

易混点：训练集和测试集不是同一批样本。Pocket 最小化训练错误，不等于每个 checkpoint 都会有更低的测试错误；测试结果只是对泛化表现的评估，不能反过来参与训练时选 Pocket。

中英术语

中文	English	在作业中的含义
监督学习 / 无监督学习	supervised / unsupervised learning	是否有目标标签；是否从无标签数据找结构
回归 / 分类	regression / classification	预测连续数值 / 离散类别
秩 / 零空间	rank / null space (kernel)	独立方向数 / 被矩阵映成零的参数方向
满列秩 / 满行秩	full column rank / full row rank	列向量独立 / 行向量独立
奇异值分解	singular value decomposition (SVD)	用正交方向和缩放拆解矩阵
正定矩阵	positive definite matrix	任意非零 $z$ 满足 $z^\top Az>0$
岭回归	ridge regression	在拟合误差上加 $L_2$ 参数惩罚
概率密度 / 似然	probability density / likelihood	参数给定时的数据密度 / 数据给定后的参数函数
最大似然估计	maximum-likelihood estimation (MLE)	使观测数据似然最大的参数估计
独立同分布	independent and identically distributed (i.i.d.)	样本独立且共享同一分布
稳健损失 / 间隔	robust loss / margin	降低离群残差影响 / 带符号的分类间隔
有限差分 / 方向导数	finite difference / directional derivative	用有限步长估计特定方向的变化率
柯西–施瓦茨不等式	Cauchy–Schwarz inequality	$\lvert a^\top b\rvert\le\|a\|_2\|b\|_2$
口袋算法 / 检查点	Pocket algorithm / checkpoint	保存训练错误最低的历史参数

References

• DDA5001 Machine Learning, Homework 1: Problems 1–5 and the supplied P3/P5 code and data.
• DDA5001 Lecture 1–2 slides: linear algebra, first-order Taylor approximation, and gradient-based optimization.