风险与 PAC 学习

01

基本想法

期望风险 R(h) = E[L(h(x), y)] 衡量假设 h 在数据分布上的表现。我们无法直接计算它，所以我们在样本上最小化经验风险 R̂(h) = (1/n) Σ L(h(xᵢ), yᵢ)。差异 R(h) - R̂(h) 有两部分：估计误差（有限样本）和近似误差（假设类）。

PAC（可能近似正确）说如果学习者以概率 ≥ 1 - δ 找到 R(h) ≤ ε 的假设，则成功。界限取决于假设类复杂度（VC 维）和样本大小 n。更复杂的类需要更多数据来泛化。

VC 维是假设类可以打散的最大点数。线性分类器在二维的VC维是3：可以打散任意3个点，但不是所有4个点的配置。更高的VC维意味着更强的表达力，但也需要更多样本来保证泛化。PAC界限形式为 R(h) ≤ R̂(h) + O(√(d/n))，其中d是VC维。这量化了复杂度-样本的权衡，是机器学习理论的基石。

02

数学

03

动手试

ε (error margin): 0.100

δ (failure probability): 0.050

|H| (hypothesis class size): 100

Sample size needed

415

m ≥ ln(2|H|/δ) / (2ε²)

m ≥ ln(4000.0) / 0.0200

Need 415 samples to ensure error ≤ 0.100 with 5.0% failure probability.

learning theory概念的交互式演示

04

我在哪用到它

05

容易出错的地方

06

参考资料

初稿于2023，2026年重写。