泛化、核方法与数学学习理论

学习算法从观测产生预测器。数学评估需输入空间、输出空间、损失及样本 Z=(X,Y) 的分布 P。假设类 H 是允许的预测规则集合。总体风险 R_P(h)=E_P ℓ(h;Z) 是 P 的新抽样期望损失；经验风险 R_hat_S(h) 是 n 个观测的损失均值。即使损失公式相同，两个量仍不同。

样本模型与算法同样重要。本课有限类集中论证要求 n 个观测来自同一 P 且独立，候选规则在这些观测前固定，损失在 [0,1]。零一分类误差符合范围；平方损失、NLL 通常不符合。没有额外假设或明确变换，不能将无界损失代入同一 Hoeffding 公式。

训练数据和优化器随机性使预测器随机。一旦它在新测试样本之外固定，可条件于训练历史，用固定预测器律分析测试损失。测试估计描述测试生成分布下的风险，不自动适用于不同标签、患病比例、输入或收集方式的未来分布。独立性属于抽样单位：复制图像、同患者记录和重复行可能使行计数失效。

训练拟合参数与变换；验证选惩罚、核宽、成分数、停止时刻；最终测试估计冻结结果。把反复查看的数据叫“测试”不保留选择独立性。按测试结果选阈值、特征变换或报告规则也是选择。查看最终标签前建立含指标和阈值的完整协议；新测试声明需新评估，或能处理适应性的有效程序。

ERM 在 H 选经验风险最小者，不说明训练风险等于总体风险，也不说明 H 包含最优总体规则。有限类可提供归纳结构，过度灵活的类则可匹配偶然模式。区分类的逼近限制、估计抽样变化，以及未找到经验最小值的优化误差；它们需要不同证据。

这里候选预先指定，随机分数不是总体不明的新训练模型。若候选由独立训练数据产生，可条件于训练数据，对固定候选池应用验证界。若候选在看了被约束样本后才构造，仅数最终短名单不够；要控制更大的搜索或数据依赖。

条件化明确了独立性：候选池可任意依赖训练标签，新验证行仍 IID。若每个合格训练历史下失败概率均有界，对历史平均仍保留界。若预处理或目标编码使用验证标签，该条件下候选不再固定。拆分名称不能覆盖实际信息流，应追踪变换和人为选择依赖。

固定 h 的 IID 有界损失满足双侧 Hoeffding 界 P(|R_hat−R|≥ε)≤2exp(−2nε²)，模块 24 已介绍该带条件定理。它控制一个预先规则，而非查看样本后任意胜者。并集界可以变成有限预先类的同时声明，无需各模型分数独立。

H 有 M 规则，为每个定义经验与总体风险相差至少 ε 的坏事件。任一坏则并事件发生；次可加性给至多 2Mexp(−2nε²)。令它等于 δ，解得 ε=sqrt(log(2M/δ)/(2n))。概率至少 1−δ 时，所有规则偏差不超过 ε。使用自然 log，因为指数以 e 为底。

h_hat 最小化经验风险，h_star 最小化有限类总体风险。在同时好事件上 R(h_hat)≤R_hat(h_hat)+ε≤R_hat(h_star)+ε≤R(h_star)+2ε。中间一步正是 ERM。若优化距经验最小值至多 τ，再加 τ。比较对象是 H 中最好者，不是类外任意最优规则；估计界不消除逼近误差。

同时性允许选择结果依赖 S，因为在选择前所有成员都已受控。它不允许看 S 后任意改变 H。n 应为声明总体的独立例子，M 应为受控类或独立构造池。模型分数相关不妨碍并集；样本行相关破坏各模型 Hoeffding 前提。

风险都在 [0,1]，半径超过一可截到一，但不能有效区分模型。松界大既不证明学习失败，也不精确预测实践所需数据。一起报告目标事件、损失范围和置信。置信是重复样本概率，不是对实现后固定未知风险赋后验概率，除非另建 Bayesian 模型。

[a,b] 有界损失先除范围归一化，应用单位界后乘 b−a；b=a 的常损失无抽样误差。若模型约束每个真标签概率≥q_min>0，NLL 在零到 −log q_min，范围因子改变。但强制约束或裁剪改变模型、指标，需说明。没有限制时，自信错误预测有任意大 NLL，分类误差界不能直接成为 NLL 界。

可数类可预先分配正权重 π_h、总和一，给每规则 δπ_h 失败预算，再并集得包含 log(2/(δπ_h)) 的规则半径。这展示复杂度偏好怎样影响同时保证。一般无限类未在此推导，不能以参数数目替代 M；连续类离散网格还需连接网格与网格外风险的逼近论证。

偏差方差分解不同于集中界。固定 x，让 f_hat_D(x) 随训练数据 D 变化，也可纳入明确优化器随机性。新 Y=f_star(x)+ε，条件均值零、方差 σ²(x)，在该 x 独立于拟合历史。m(x)=E_D f_hat_D(x)，偏差 m−f_star，方差 E_D(f_hat_D−m)²，要求相关矩存在。

展开 f_hat−Y=(f_hat−m)+(m−f_star)−ε。平方期望留下三项：预测中心化使与固定偏差交叉项零，噪声条件均值与独立性使其交叉项零。故新平方误差期望=预测方差+偏差平方+σ²。按指定输入律积分，在可积时得到总体分解。

这是带条件精确恒等式，不是模型大小总使方差单调增长、正则化总改善风险的定理。惩罚可减方差增偏差；样本量、噪声、算法和类都影响二者。灵活插值模型可好可坏，训练误差不识别总体分量，一次拆分也不能直接测训练分布期望。

固定 D 的种子变化只测条件算法变化。新 D 还增加抽样变化。全方差拆成 E_D Var_seed(f_hat|D) 与 Var_D E_seed(f_hat|D)。同一数据重复种子不能建立第二项，相关拆分也不创造独立未来例子。区分评估样本不确定性与拟合流程变化。

恒等式特指平方误差和距离目标。分类误差与 NLL 几何不同；模块 27 用熵加 KL 连接期望 NLL，需要支撑与条件概率。风险恒等式、估计风险的置信声明、降低训练损失的优化声明是三件事。

九个等距点可确定八次多项式，训练残差几乎零，中间却振荡。实验 3 与二次多项式在已知函数的确定性稠密网格比较；本例高次训练误差小，网格误差大。它是指定函数、域的逼近诊断，不是 IID 置信估计，也不是高次模型通用判决。

条件均值逐点最小化平方误差：任意固定 a，有 E[(a−Y)²|x]=(a−f_star(x))²+σ²(x)，由中心化噪声展开。H 可能不能表示此均值，数据无限、优化完美也有逼近误差。因此模型选择不只是经验拟合与估计半径竞争，还要声明逼近目标和应用成本。

有限类可用基数度量容量，许多有用类却有无限参数值。若类能实现某有限输入集的全部二元标记，就称打散该集。VC 维是最大可打散大小，无有限最大则无穷。定义关心可表示模式，不是优化成功、观测训练准确率或数值参数原始数目。

固定方向阈值 h_t(x)=1[x≥t] 可通过 t 在单点上方、下方实现两种标签，故打散单点。任意 x1<x2，(1,0) 不可实现：t≤x1 必也≤x2。没有两点集可打散，所以 VC 维一，虽然阈值无限。这完整例子说明无限基数不必阻碍可学习性。

一般 VC 一致收敛需更多工具，在此只作为命名结果。其声明仍含样本、损失、置信和复杂度条件。现代大网络的粗参数计数界可极松，有用分析可能涉及范数、间隔、稳定性、压缩或数据相关复杂度。本入门课没有证明网络泛化的通用解释，不能把容量叙述扩成条件外定理。

偏移改变评估总体。源 P 与目标 Q 的 R_P、R_Q 可不同，即使固定预测器风险在源上测得完美。协变量偏移指输入律改变而 Y|X 保持；标签、概念变化改变联合律其他部分。这些是要调查的建模假设，源测试成功不自动确认。源置信区间量化 P 下抽样变动，不约束任意未来 Q。

Q 相对 P 绝对连续时，目标风险可写 E_P[w(Z)ℓ]，w=dQ/dP。源缺支撑则不能直接表示。权重可能大、未知或需估计，范围与方差改变集中问题。协变量偏移且条件律保留时仅需输入密度比；假设错则校正失效。公式不证明有限数据能准确估权重。

类别比例也改变准确率含义：总报零在正类比例 .05 时准确率 .95，在 .95 时仅 .05。条件灵敏度、特异度、校准、NLL 和决策成本回答不同问题。报告应用所需总体和指标；在有限数据精确计算的指标仍可能误导部署解释。

φ 将输入映到内积空间，k(x,z)=φ(x)ᵀφ(z)。有限点 Gram K_ij=k(x_i,x_j) 对称，任意 c 满足 cᵀKc=||Σc_iφ(x_i)||²≥0，故半正定。有效实核必须在每个有限输入集如此。单数据数值 PSD 只检查该集，不证明任意相似函数全球有效。

二维 φ(t)=(1,t) 给 k=1+st。在 0,1,−1 上 Gram 行为 (1,1,1),(1,2,0),(1,0,2)，特征值 0,2,3。零模态允许，PSD 不需正定。对角一、非对角二的对称矩阵有特征值三、负一；c=(1,−1) 给二次型 −2，精确否定核有效性。

一维 RBF exp(−(s−t)²/(2ℓ²))、ℓ>0 也 PSD。拆成 exp(−s²/(2ℓ²)) exp(−t²/(2ℓ²)) exp(st/ℓ²)，展开末项，每项为正系数乘 s-only、t-only 特征积。有限输入二次型是收敛平方和，故非负。它证明实验 2 标量核；向量版有类似论证。ℓ 声明输入尺度，选择不能用测试。

有限维特征岭最小化均值半平方误差加 λ||w||²/2，λ>0。w 分解到训练特征张成空间与正交补。补不改变训练预测，只增加惩罚，所以最优在张成空间，w=Σα_iφ_i。代入目标 ||Kα−y||²/(2n)+λαᵀKα/2。一般无限空间表示定理还需 Hilbert 空间条件。

导数 K(Kα−y)/n+λKα=0，充分解为 (K+nλI)α=y。K PSD、λ>0 使平移矩阵正定可逆，即使 K 奇异。系数最小化者可差 K 零空间，但表示特征向量和预测相同。代码用 solve；新预测 k_xᵀα，k_x 含到训练输入的相似度。预处理、尺度都是拟合模型的一部分。

公式中的逆是数学表达，不要求代码形成逆。稠密 K 存 n² 项，一般稠密解 n³ 工作；小显式特征可便宜。核中心化和无罚截距需训练拟合变换。实验 2 明确固定训练均值偏移后拟合残差，不称自由截距联合优化。核有效性、数值条件、总体性能是三种问题。

核幅度也影响惩罚：K→cK、λ→cλ，c>0 时 α→α/c，新 k_x→ck_x，预测不变。只改幅度不改 λ 通常改变拟合；改输入单位不对应改 RBF 长度也改变相似度。记录幅度、长度、预处理及均值或总和归约；不同尺度下相同 λ 数字不代表相同正则强度。

y∈{−1,1}，f=wᵀφ+b 按符号和声明平局规则预测。w≠0 时有符号几何距离 y f/||w||。同时将 w,b 乘正常数不改分类，所以函数分数尺度不是几何间隔。硬间隔选 y_i f_i≥1 并最小化 ||w||²/2，需要特征空间可分。

证明距离：移动特征向量 d 至分数零，需要 wᵀd=−f。Cauchy–Schwarz 给 ||d||≥|f|/||w||，d=−f w/||w||² 达等号。间隔是带标签符号的特征空间垂直距离，非线性映射后未必是原始输入距离。w=0 时公式未定义，可讨论分数与松弛，不应虚构距离。

不可分数据、同特征反标签使硬约束不可行。软间隔引 ξ_i≥0、y_i f_i≥1−ξ_i，最小化 ||w||²/2+CΣξ_i，C>0。固定 w,b 时最小 ξ_i=max(0,1−y_i f_i)，即 hinge。乘 1/(nC) 得均值 hinge 加 λ||w||²/2，其中 λ=1/(nC)。

此约束入门对未学模块 20 的 AI 路线自足；完整对偶拓展需该模块。α_i≥0 对间隔约束，μ_i≥0 对非负 ξ。驻点给 w=Σα_i y_iφ_i、自由截距给 Σα_i y_i=0、C−α_i−μ_i=0，故 0≤α_i≤C。代入得最大化 Σα_i−Σ_i,j α_iα_j y_i y_j K_ij/2，含箱约束和截距等式。

凸性与严格可行 w=b=0、ξ_i=2 支持模块 20 的 Slater 强对偶结果。PSD 核使对偶二次型凹。互补松弛解释支持向量，但这里不声称实现了 SVM 求解器；实验 2 实现核岭。核化改变特征表示，训练间隔本身仍不证明无限模型类的有限类界。

报告应连接类、目标、优化、数值实现和评估，说明是本课证明、带条件命名结果、精确有限计算还是诊断实验。松界说明充分性，过拟合解释具体选择或逼近机制，不从一张图推普遍规则。后面综合项目要求在完整可执行流程中答辩这些区别。

比较两个冻结预测器应保留配对观测：同一独立测试例子的损失差方差包含协方差。将两个标准误当独立可能误报差异。有界差按实际范围缩放集中界；bootstrap 一起重抽独立例子对。这沿用模块 26 单位纪律。核与基线共享测试支持配对比较，但反复调参又使比较成为选择。

实验 A · 已知总体风险的选择乐观性

固定 NumPy 环境，预测候选数与验证最大值。精确二项计数模拟独立公平比特特征和标签，每规则总体 .5。重复平均与单样本一致半径分开报告。

下载 lab1_selection_optimism.py

"""A predeclared finite null class; each true classification accuracy is .5.

X contains independent fair bits and Y is an independent fair bit; h_j(X)=X_j.
Validation error counts are independent Binomial(n,.5) under this model.
The count sampler implements that exact distribution without storing all rows.
"""
import math
import numpy as np

rng = np.random.default_rng(30030)
repeats, n, ntest = 1000, 100, 2000
for candidates in (1, 20, 200):
    validation = rng.binomial(n, .5, size=(repeats, candidates))/n
    winner = validation.max(axis=1)
    # Every selected candidate still has population accuracy .5; fresh test is independent.
    test = rng.binomial(ntest, .5, size=repeats)/ntest
    epsilon = math.sqrt(math.log(2*candidates/.05)/(2*n))
    print(f'M={candidates}; mean selected validation={winner.mean():.6f}; mean independent test={test.mean():.6f}; uniform radius={epsilon:.6f}')
print('The repeat average is an experiment summary; the bound is for one IID sample and all fixed candidates.')

M=1; mean selected validation=0.497960; mean independent test=0.500209; uniform radius=0.135810
M=20; mean selected validation=0.592690; mean independent test=0.499582; uniform radius=0.182820
M=200; mean selected validation=0.636930; mean independent test=0.500013; uniform radius=0.211981
The repeat average is an experiment summary; the bound is for one IID sample and all fixed candidates.

实验 B · 核岭求解与冻结比较

40/25/25 不重叠独立合成观测，原始 x 单位和训练固定偏移。验证选 RBF 长度、均值惩罚，测试只评一次所选模型及常数基线。PSD 数值容差是解析有效核的诊断。

下载 lab2_kernel_ridge.py

"""RBF kernel ridge, mean-loss convention; choose only on validation."""
import numpy as np

rng = np.random.default_rng(30031)
x = rng.uniform(-2, 2, 90)
y = np.sin(3*x)+rng.normal(0, .15, 90)
train, val, test = np.arange(40), np.arange(40,65), np.arange(65,90)
offset = y[train].mean()  # Fixed training-only offset, not a separately optimised intercept.
def kernel(a, b, length):
    return np.exp(-((a[:,None]-b[None,:])**2)/(2*length**2))
records = []
for length in (.2, .6, 1.5):
    K = kernel(x[train], x[train], length)
    assert np.linalg.eigvalsh(K).min() > -1e-10
    for penalty in (.0001, .01, .1):
        alpha = np.linalg.solve(K+len(train)*penalty*np.eye(len(train)), y[train]-offset)
        prediction = offset+kernel(x[val], x[train], length)@alpha
        mse = np.mean((prediction-y[val])**2)
        records.append((mse, length, penalty, alpha))
        print(f'length={length:.1f}; lambda={penalty:g}; validation MSE={mse:.6f}')
_, length, penalty, alpha = min(records, key=lambda row: row[0])
prediction = offset+kernel(x[test],x[train],length)@alpha
print(f'frozen choice: length={length}; lambda={penalty}; test MSE={np.mean((prediction-y[test])**2):.6f}')
print(f'training-mean baseline test MSE={np.mean((offset-y[test])**2):.6f}')
print('40/25/25 independent rows; raw x units; fixed training-only offset; no final-test selection.')

length=0.2; lambda=0.0001; validation MSE=0.052735
length=0.2; lambda=0.01; validation MSE=0.054247
length=0.2; lambda=0.1; validation MSE=0.258900
length=0.6; lambda=0.0001; validation MSE=0.016715
length=0.6; lambda=0.01; validation MSE=0.039747
length=0.6; lambda=0.1; validation MSE=0.246924
length=1.5; lambda=0.0001; validation MSE=0.119131
length=1.5; lambda=0.01; validation MSE=0.383195
length=1.5; lambda=0.1; validation MSE=0.526769
frozen choice: length=0.6; lambda=0.0001; test MSE=0.025248
training-mean baseline test MSE=0.658235
40/25/25 independent rows; raw x units; fixed training-only offset; no final-test selection.

实验 C · 相似性、偏移及插值

给精确负二次型，检查特征 Gram 微小负舍入特征值，反转标签机制，并在确定网格比较插值。说明每项挑战不同条件。

下载 lab3_similarity_shift_and_interpolation.py

"""Indefinite similarity, changed labels, and zero-training-error diagnosis."""
import numpy as np

bad = np.array([[1.,2.],[2.,1.]])
c = np.array([1.,-1.])
print('symmetric positive-diagonal similarity eigenvalues:', np.linalg.eigvalsh(bad))
print('witness c.T K c:', c@bad@c)
assert c@bad@c < 0
phi = np.array([[1.,0.],[1.,1.],[1.,-1.]])
good = phi@phi.T
print('feature-map Gram eigenvalues:', np.linalg.eigvalsh(good))
assert np.linalg.eigvalsh(good).min() > -1e-12
x = np.array([-1.,1.])
prediction = x>0
source_y = x>0
target_y = x<0
print('same feature masses, changed label mechanism: source accuracy=',np.mean(prediction==source_y),'; target accuracy=',np.mean(prediction==target_y))
print('always-zero accuracy under class-1 prevalence .05/.95:', .95, .05)
t = np.linspace(-1,1,9)
y = 1/(1+25*t*t)
grid = np.linspace(-1,1,1001)
truth = 1/(1+25*grid*grid)
for degree in (2,8):
    design = np.vander(t, degree+1, increasing=True)
    beta = np.linalg.lstsq(design,y,rcond=None)[0]
    fitted = design@beta
    dense = np.vander(grid,degree+1,increasing=True)@beta
    print(f'degree={degree}; training MSE={np.mean((fitted-y)**2):.6e}; dense-grid MSE={np.mean((dense-truth)**2):.6e}')
print('Dense-grid error is a deterministic interpolation diagnostic, not a confidence estimate from an IID test sample.')

symmetric positive-diagonal similarity eigenvalues: [-1.  3.]
witness c.T K c: -2.0
feature-map Gram eigenvalues: [-4.4408921e-16  2.0000000e+00  3.0000000e+00]
same feature masses, changed label mechanism: source accuracy= 1.0 ; target accuracy= 0.0
always-zero accuracy under class-1 prevalence .05/.95: 0.95 0.05
degree=2; training MSE=4.503752e-02; dense-grid MSE=3.946358e-02
degree=8; training MSE=1.474889e-27; dense-grid MSE=1.356205e-01
Dense-grid error is a deterministic interpolation diagnostic, not a confidence estimate from an IID test sample.

作者 Understanding Machine Learning 的第 4、6、15、16 章，与官方 Cornell ERM、SVM 比较。本课实际推导有限类、阈值、PSD 和岭，更广容量结果标为命名拓展。

结业任务：推风险半径和 ERM 比较，证 PSD 与阈值容量，诊断选择和偏移，声明核岭、SVM 目标。

可以继续：满足先修后完成模块 31 CS 或模块 32 AI 综合项目。回到课程概览。