西瓜书第12章：计算学习理论

---

概述

一些概念及记号

$D$ 是 $\mathcal{D}$ 的独立同分布采样，因此 $h$ 的经验误差的期望等于其泛化误差。

泛化误差：

$$E(h ; \mathcal{D})=P_{x \sim \mathcal{D}}(h(\boldsymbol{x}) \neq y)$$

经验误差：

$$\hat{E}(h ; D)=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(h\left(\boldsymbol{x}_{i}\right) \neq y_{i})\right.$$

经验误差与泛化误差之间逼近程度：

一致与不一致：若 $h$ 在数据集 $D$ 上的经验误差为0, 则称 $h$ 与 $D$ 一致, 否则不一致。

概率近似正确（Probably Approximately Correct)

PAC学习

什什么是“可学习的”

假设空间复杂性

有限假设空间

⽆无限假设空间：VC维

⽆无限假设空间：Rademacher复杂度

稳定性