学习问题的形式化：假设空间、经验风险与泛化
一句话定义
学习问题的形式化把「从数据学规律」表述为：在假设空间 ℋ 中，依据训练集上的经验风险最小化（ERM）选出一个假设 f，并使其泛化误差（对真实数据分布的期望损失）尽可能小。
为什么重要
不做形式化就无法严谨讨论「学得好」。为什么训练误差小不等于模型好？为什么需要正则化和验证集？这些问题的答案都在形式化框架里。掌握它之后，后面每一个模型都可以被统一地理解为「换一个假设空间 + 换一个损失 + 换一个优化方法」。
前置知识
什么是机器学习：定义、三种范式与术语地图 的术语与范式；期望与方差的概率直觉。
核心概念
- 输入空间/输出空间：x ∈ 𝒳，y ∈ 𝒴。
- 联合分布：数据由未知分布 𝒟(x, y) 独立同分布（i.i.d.）采样。
- 假设空间（hypothesis space）：算法可选择的函数集合 ℋ，如「所有线性函数」「深度为 3 的所有决策树」。
- 泛化误差：R(f) = 𝔼𝒟[L(y, f(x))]，对真实分布的期望损失。
- 经验风险：训练集上的平均损失 R̂(f)。
- 泛化误差界：连接经验风险与泛化风险的桥（见下）。
直观类比
考试刷题：训练集是刷过的题，测试集是新题。经验风险是「刷题错误率」，泛化误差是「新题错误率」。假设空间像「允许使用的答题套路集合」——套路太少（欠拟合）会漏解，套路太多且题太少（过拟合）会把题目里的偶然规律也背下来。
原理与机制
经验风险最小化在大样本时是泛化风险的合理代理，但小样本时会失真。统计学习理论用泛化误差界刻画这种失真：对有限假设空间 |ℋ|，以至少 1-δ 的概率有
读出三个结论：(1) 训练误差小不保证泛化好，中间隔着与假设空间复杂度、样本量有关的间隙；(2) 假设空间越大，越需要更多数据撑住（样本复杂度）；(3) 学习的可行性与「没有免费午餐定理」相关——不引入对问题的先验偏好（如平滑性、稀疏性），任何算法在某些分布上都会表现糟糕，因此所有正则化本质上都是先验偏好。
公式与推导
经验风险定义（监督情形，损失 L 如平方损失）：
由大数定律，当 n → ∞ 时 R̂(f) → R(f)（对固定 f）；误差界把这一收敛对「从 ℋ 中挑选最优 f」这一操作的风险做了额外校正（同时考察 |ℋ| 个假设的 union bound），于是得到上面 √ln|ℋ|/n 项。这条线随后发展为 VC 维理论（对无限假设空间的复杂度度量）与 PAC 学习（Probably Approximately Correct，以 1-δ 概率达到 1-ε 精度）。
图示
泛化误差
▲
│＼ ／
│ ＼ 训练误差 ↓ ↓ ↓ ／
│ ＼______________／ ← 理想复杂度区间
│ 假设空间复杂度 ──▶
└────────────────────────▶
欠拟合区 过拟合区实例或案例
在 20 个样本上拟合 19 次多项式：经验误差可以精确为 0（插值），但对新样本误差巨大——|ℋ| 相对样本量过大，误差界间隙失控。反之用一次多项式拟合二次真函数：两类误差都降不下去（欠拟合）。这两个极端展示了「假设空间复杂度要与数据量、问题真实复杂度匹配」。
常见误区
- 把泛化误差界当成可计算的精确值：它是保守上界，用于定性推理而非数值报告。
- 认为 i.i.d. 假设可有可无：数据有时间漂移或组间相关时，普通随机划分的评估会失真（见 kp-025）。
- 混淆经验风险最小化与结构风险最小化：后者是前者加正则项（见 kp-008）。
与其他知识点的关系
损失函数：从 0-1 损失到代理损失 定义本节中的 L；偏差-方差分解与过拟合 把泛化误差进一步分解为偏差-方差-噪声；交叉验证与数据划分策略 说明实践中如何用交叉验证估计 R(f)。
自测题
- 为什么最小化经验风险不等价于最小化泛化风险？
- 要点：经验风险是有限样本的均值估计，存在估计方差；算法还在 ℋ 中做了选择，会「利用」训练集的随机性，需加上与 ℋ 复杂度和 n 相关的间隙。
- 误差界公式中各项分别提醒我们控制什么？
- 要点：R̂(f) 项要训练充分；ln|ℋ| 项提示控制模型复杂度（正则化）；n 项提示收集更多数据；δ 体现概率保证。
- 「没有免费午餐」对工程选型意味着什么？
- 要点：不存在万能算法，必须结合领域先验（特征设计、归纳偏置、模型族选择）才能赢。
延伸阅读
李航《统计学习方法》第 1 章；Hastie 等《The Elements of Statistical Learning》第 2、7 章。