统计学习问题

问题协议 ​

一个批量 IID 监督学习问题需要同时固定五类对象：观测空间 $\mathcal{Z}$，允许的数据分布族 $\mathfrak{D}$，用于比较或输出的假设类 $\mathcal{H}$，损失 $\ell$，以及把样本映到预测器的学习器 $A$。常见监督学习取 $\mathcal{Z}=\mathcal{X}\times \mathcal{Y}$。环境选择未知的 $D\in \mathfrak{D}$，学习器观察

$$S=(Z_1,\dots ,Z_m)\sim D^m,$$

再输出 $h=A(S)\in \mathcal{H}$ 或预先声明的更大输出类。评价对象是样本外风险 $R_D(h)={\mathbb{E}}_D\ell (h,Z)$，不是训练过程本身。

若算法随机化，应写成 $h=A(S,U)$：高概率保证同时对样本随机性和内部种子 $U$ 取概率，而“对所有允许的 $D$”是外层量词。训练集是分布的一次实现，不等于分布。

任务图像与边界 ​

二分类用 0–1 损失评价错误概率；平方回归评价数值偏差。共同协议并未强迫预测器是有限维参数，它也可以是树、查找规则或随机决策核。

已知完整目标函数后求最小值是优化问题公理库优化问题Optimization problem在可行解集合上最小化或最大化目标函数的计算问题。；目标由未知分布定义、只能用样本近似，并须接受样本外评价时才出现学习层。假设类规定比较对象，损失规定何谓表现好，学习协议则规定算法实际看到了什么。这三层不能由某个优化器的名字代替。

IID 是本页主线而非学习的唯一可能：时间序列、自适应采样和分布漂移需要另写数据协议，不能沿用 $D^m$ 的证明。样本复杂度公理库样本复杂度、精度与置信度Sample complexity · Accuracy and confidence用 m(ε,δ) 描述达到风险精度与失败概率所需的数据量。随后把风险目标变成有限数据保证。

一项完整的统计学习问题还必须固定信息边界。设邮件分类的 $X$ 包含正文和发件域，$Y$ 表示是否为垃圾邮件；训练样本若来自旧月份，而部署风险按新月份分布计算，就不再是同一个 $D$。即使训练误差为零，原 IID 保证也没有覆盖这种分布迁移。相反，若先把某月邮件随机分成训练和测试两部分，测试集在算法完成前始终封存，测试平均才可视为对数据依赖预测器的一次独立风险估计。

量词顺序决定陈述强弱。分布无关结论形如“存在一个算法 $A$，对每个允许分布 $D$，当 $S\sim D^m$ 时以高概率成功”；它不是“对每个 $D$ 都能另选一个预先知道 $D$ 的算法”。后者把未知对象泄露给了学习器。监督学习、在线学习和 bandit 的主要差别也首先在信息协议：批学习一次拿到 $S$，在线学习逐轮揭示结果，bandit 还隐藏未选动作的反馈。

学习问题与估计问题可以互相嵌入。估计 Bernoulli 参数 $p$ 时，预测器可取常数 $a\in [0,1]$，平方损失的总体风险在 $a=p$ 处最小；于是“估参数”就是在常数函数类中学习。反过来，只给出一个神经网络训练脚本而没有数据分布、损失和样本外基准，还没有定义完整的统计学习问题。

最后还需规定允许的分布族。分布无关 PAC 允许全部 $D$，minimax 估计常把 $D$ 限制在参数族 $\{P_{\theta }\}$，协变量漂移则假定条件分布某部分保持。限制越强，可能获得越快的速率；这些速率不能回填到未受限制的根协议。

参考资料

• Shai Shalev-Shwartz, Shai Ben-David, Understanding Machine Learning, 2014, Chs. 2–3.
• Mehryar Mohri et al., Foundations of Machine Learning, 2nd ed., 2018, Ch. 2.