© 2026 LIN TIANYU. All rights reserved. Preview Version.

Powered bynextjs-blog

GitHub LinkedIn

ArticlePDF机器学习

泛化（Generalization）

PublishedJuly 24, 2026Document10 pages

Contents

真误差 / 泛化误差 (True Error / Generalization Error)
记忆 = 学习：背下训练集的反例 (Memorization Is Not Learning)
反例一：把训练集抄回来的学习者
反例二：背下训练集的决策树
用留出集估计真误差 (Estimating True Error with a Hold-out Set)
陷阱：反复使用 H 就是过拟合 (Reusing H = Over-fitting)
权衡模型复杂度：势函数 (Trading Off Model Complexity)
MDL：最小描述长度原则 (Minimum Description Length)
PAC 学习模型 (The PAC Model of Learning)
模型的组成要件
学习器的目标（完整陈述）
为什么需要"以概率 1-"？
名字的由来：Probably Approximately Correct
一致性算法 A 与学习流程 (The Consistency Algorithm A)
高层学习流程
弹珠游戏：失败概率的直觉 (The Marble Game)
算法与分析
失败概率
有限假设类的样本复杂度（完整证明） (Sample Complexity for Finite Hypothesis Classes)
第一步：界定"坏事件"
第二步：固定一个坏假设，算它"蒙混过关"的概率
第三步：联合界(Union Bound)合并所有坏假设
第四步：令上界，解出 |S|
核心洞察：对数依赖 (The Logarithmic Insight)
易错点：为什么必须做联合界？

1

2

3

4

5

6

7

8

9

10

Thanks for reading.