PAC —— 概率近似正确

上级：learning-theory 前置：learning-theory —— 定义了 c、H、h、D、err(h)、ε、δ、m。

Valiant（1984）提出的框架，用来刻画"从随机样本中学习"——它给出了"可学习"这个概念的定义。

PAC 可学习（PAC-learnable）

目标概念 c 存在于一个已知的假设类 H 中；带标签的样本从一个未知分布 D 中独立同分布地抽取。如果存在一个算法，对任意精度 ε、置信度 δ 和分布 D，只用关于 1/ε 和 1/δ 呈多项式规模的样本数 m，就能输出满足下式的 h ∈ H，那么这个类就称为PAC 可学习： error(h) ≤ ε——近似正确——且概率 ≥ 1−δ——大概率。

这里有两个相互独立的容忍度：ε = 精度（h 允许错到什么程度）和δ = 置信度（整次运行允许失败的频率）。你从不要求确定无疑的精确真理——只要求落在ε 之内，并且1−δ 的时候成立。

需要多少数据？（样本复杂度）

对于一个有限的假设类，一个足够的界是

读法：假设类越丰富（ln|H| 越大），需要的数据越多；精度要求越高（1/ε），需要的数据越多；置信度要求越高（ln(1/δ)），需要的数据也稍微多一点。对于无限的 H，ln|H| 这一项被替换为 VC dimension。

具体例子——学习一个矩形

目标：一个未知的轴对齐矩形；点落在内部标记为 +，落在外部标记为 −。算法：输出恰好包住已见到的所有 + 点的最小矩形。

它可能在哪里出错？只可能出在真实矩形与（更小的）学到的矩形之间那一圈薄薄的边框上——那里的点其实是 +，却被预测成 −。把这圈边框切成 4 条带；每条带的概率会随着看到的 + 点增多而不断缩小，取 m = O((1/ε) ln(1/δ)) 个样本后，每条带的概率都以 1−δ 的置信度落在 ≤ ε/4。总误差 ≤ ε。PAC 学到了——注意这个结果也永远只是大概率地近似那个真实矩形，从来不是精确等于它。

可实现 vs 不可知（Realizable vs agnostic）

• 可实现（Realizable）： 存在某个完美的 h ∈ H（真相就在这个类里）。
• 不可知（Agnostic）： 不存在完美的 h；你退而求其次，接受一个与类内最优相差在 ε 之内的 h。保证的形式相同，样本数为 1/ε²。