基础知识
什么是计算学习理论
计算学习理论（Computational Learning Theory）研究机器学习的理论基础，试图回答以下关键问题：
- 在什么条件下学习是可能的？
- 需要多少训练样本才能学到好的模型？
- 学习算法的计算复杂度是多少？
- 如何刻画学习任务的难度？
计算学习理论为机器学习提供了严格的数学框架，帮助我们理解学习算法的本质和局限性。
PAC学习框架
PAC（Probably Approximately Correct）学习是Valiant于1984年提出的经典学习框架。
PAC可学习定义
对于任意 ε > 0（误差）和 δ > 0（置信度），存在学习算法 𝓛 和多项式函数 poly(·,·,·,·)， 使得对于任意分布 𝒟 和目标概念 c，当样本数量满足：
m ≥ poly(1/ε, 1/δ, size(c), size(x))
算法 𝓛 能够以至少 1-δ 的概率学习到假设 h，使得误差 error(h) ≤ ε
💡 理解PAC
- Probably（概率上）： 以高概率（1-δ）成功
- Approximately（近似地）： 误差不超过ε
- Correct（正确）： 学到的假设近似正确
PAC学习可视化
交互式调整ε和δ，观察所需样本数量的变化
🚧 开发中...
PAC学习
样本复杂度
样本复杂度（Sample Complexity）是指学习算法达到预定精度所需的最少样本数量，是PAC学习理论的核心概念。
有限假设空间的样本复杂度
对于有限假设空间 |ℋ| < ∞，要保证以1-δ的概率找到误差不超过ε的假设，样本数量需满足：
m ≥ (1/ε) · (ln|ℋ| + ln(1/δ))
这个界告诉我们：假设空间越大，需要的样本越多；要求的精度越高（ε越小）或置信度越高（δ越小），需要的样本也越多。
不可知PAC学习
标准PAC学习假设目标概念c存在于假设空间ℋ中（可实现假设）。不可知PAC学习（Agnostic PAC Learning）放宽了这一假设，允许ℋ中不存在完美的假设。
不可知PAC可学习定义
算法输出的假设h满足：
error(h) ≤ minh'∈ℋ error(h') + ε
即学到的假设h的误差与假设空间中最优假设的误差相差不超过ε
不可知PAC学习更贴近实际情况，因为真实世界中目标概念往往不在我们的假设空间中。
可实现vs不可知学习
对比可实现和不可知PAC学习场景下的学习过程
🚧 开发中...
有限假设空间
一致性学习算法
一致性（Consistent）学习算法输出的假设在训练集上零错误，即能完美拟合训练数据。
Hoeffding不等式
对于任意假设h，其训练误差和泛化误差的差异满足：
P(|error(h) - êrror(h)| > ε) ≤ 2exp(-2mε²)
其中 êrror(h) 是训练误差，error(h) 是泛化误差，m 是样本数量
Union Bound
对假设空间ℋ中所有假设应用Hoeffding不等式，利用Union Bound：
P(∃h∈ℋ: |error(h) - êrror(h)| > ε) ≤ 2|ℋ|exp(-2mε²)
令右侧 ≤ δ，解出样本数量 m ≥ (1/2ε²)(ln|ℋ| + ln(2/δ))
版本空间
版本空间（Version Space）是假设空间ℋ中所有与训练集一致的假设的集合。
候选消除算法
候选消除（Candidate Elimination）算法维护版本空间，通过训练样本逐步缩小版本空间：
- 初始化：版本空间 = 整个假设空间ℋ
- 对于每个训练样本(x, y)：
- • 从版本空间中移除所有与(x, y)不一致的假设
- 重复直到处理完所有训练样本
- 最终版本空间中的任意假设都是一致的
当版本空间只剩一个假设时，学习任务完成。实际中版本空间可能包含多个假设，需要选择策略（如投票）。
版本空间收敛过程
可视化训练样本如何逐步缩小版本空间
🚧 开发中...
VC维
VC维定义
VC维（Vapnik-Chervonenkis Dimension）是衡量假设空间复杂度的重要指标，适用于无限假设空间。
打散（Shatter）
如果假设空间ℋ能够实现数据集D上所有可能的标记（2m种），则称ℋ能够打散D。
VC维是ℋ能打散的最大数据集大小：
VC(ℋ) = max{m: ℋ能打散某个大小为m的数据集}
经典例子：线性分类器的VC维
- • 二维平面上的线性分类器：VC维 = 3
可以打散任意3个点（不共线），但无法打散某些4个点的配置（如XOR）
- • d维空间的线性分类器：VC维 = d + 1
可以打散d+1个一般位置的点
💡 VC维的意义
VC维越大，假设空间的表达能力越强，但也越容易过拟合。 VC维为学习算法的泛化能力提供了理论保证。
VC维与样本复杂度
VC维将样本复杂度的分析扩展到无限假设空间。
基于VC维的样本复杂度界
对于VC维为d的假设空间，要以1-δ的概率保证误差不超过ε，样本数量需满足：
m = O((d/ε) · log(1/ε) + (1/ε) · log(1/δ))
这个界说明：模型越复杂（d越大），需要的样本越多才能保证泛化性能。
结构风险最小化（SRM）
SRM原则：在训练误差和模型复杂度之间权衡，选择使结构风险最小的模型：
Structural Risk = Training Error + Complexity Penalty
这与正则化、奥卡姆剃刀原则的思想一致。
🎯 VC维交互演示
通过放置点和调整标签，理解线性分类器的VC维（能打散3点，不能打散4点）
二维线性分类器的VC维
可以打散！
线性分类器可以实现所有可能的标记组合
💡 VC维定义
什么是"打散"？
如果假设空间ℋ能够实现数据集上所有可能的标记（2m种）， 则称ℋ能够打散（Shatter）该数据集。
例如：3个点有8种可能的标记组合，如果都能被线性分类器正确分类，则可打散。
VC维是什么？
VC维（Vapnik-Chervonenkis Dimension）是假设空间能打散的最大数据集大小。
✓ 二维线性分类器
- • VC维 = 3
- • 可以打散任意3个点（非共线）
- • 无法打散某些4个点配置（如XOR）
📐 一般规律
- • d维空间线性分类器：VC维 = d + 1
- • VC维越大，表达能力越强
- • 但也越容易过拟合
🎯 VC维的意义
VC维提供了学习算法泛化能力的理论保证。样本复杂度与VC维成正比： 模型越复杂（VC维越大），需要的训练样本越多才能保证泛化性能。
Rademacher复杂度
Rademacher复杂度
Rademacher复杂度是另一种衡量假设空间复杂度的方法， 相比VC维更加精细，能考虑数据分布的影响。
经验Rademacher复杂度
给定样本集 S = {x₁, ..., xₘ}，假设空间ℋ的经验Rademacher复杂度定义为：
R̂ₛ(ℋ) = 𝔼σ[suph∈ℋ (1/m) Σᵢ σᵢh(xᵢ)]
其中 σᵢ 是独立的Rademacher随机变量（以0.5概率取+1或-1）
💡 直观理解
Rademacher复杂度衡量假设空间ℋ拟合随机噪声的能力。 如果ℋ能很好地拟合随机标记，说明它很容易过拟合，复杂度高。
基于Rademacher复杂度的泛化界
以至少1-δ的概率，对所有h∈ℋ：
error(h) ≤ êrror(h) + 2Rₘ(ℋ) + sqrt(ln(1/δ) / 2m)
其中 Rₘ(ℋ) 是假设空间的Rademacher复杂度
Rademacher复杂度与VC维相比：更加数据依赖，能更紧地刻画泛化能力，但计算更复杂。
Rademacher复杂度演示
可视化不同假设空间拟合随机噪声的能力
🚧 开发中...
稳定性
算法稳定性
稳定性（Stability）从算法角度分析泛化能力， 衡量训练集的微小变化对学习结果的影响。
均匀稳定性
学习算法𝓛具有β-均匀稳定性，如果对于任意两个只差一个样本的训练集S和S'：
supz |ℓ(𝓛S, z) - ℓ(𝓛S', z)| ≤ β
其中 ℓ(h, z) 是假设h在样本z上的损失
稳定性与泛化
如果算法𝓛是β-均匀稳定的，则以至少1-δ的概率：
error(𝓛S) ≤ êrror(𝓛S) + 2β + (4mβ + 1)sqrt(ln(1/δ) / 2m)
💡 提高稳定性的方法
- • 正则化：L2正则化可以提高算法稳定性
- • 集成学习：Bagging等方法通过平均降低方差，提高稳定性
- • Early Stopping：限制训练迭代次数
稳定性视角的优势： 直接分析算法本身，不依赖假设空间结构；能够解释为什么正则化、集成学习等技术能提高泛化能力。
算法稳定性对比
对比有无正则化的算法在训练集扰动下的输出变化
🚧 开发中...