定义

我们定义 泛化误差 为:

$$ L_{D,f}(h) = P_{X \sim D}(h(X) \neq f(X)) $$

训练误差 为:

$$ L_S(h) = \frac{1}{m} \sum_{i=1}^m \mathbb{I}(h(X_i) \neq f(X_i)) $$

定义

如果存在 $h^*$ 使得对任意 $L_{D,f}(h^*) = 0$, 则称为 $f,D$ 满足 可实现假设. 对 $1$ 的概率, 满足 $L_S(h^*) = 0$, 且对每个经验风险最小化的假设 $h_S$ 有 $L_S(h_S) =0$.

定理

设 $\mathcal{H}$ 是有限的假设空间, $\delta \in (0,1), \epsilon>0$, 设正整数 $m$ 满足:

$$ m \ge \frac{\log(|\mathcal{H}|/\delta)}{\epsilon} $$

对任意标签函数 $f$ 和任意分布 $D$, 如果可实现性假设相对于 $\mathcal{H}, \mathcal{D}, f$ 成立, 则在大小为 $m$ 的独立同分布样本 $S$ 的选择上有最低 $1-\delta$ 的概率满足: 对每个经验风险最小化的假设 $h_S$ 有:

$$ L_{D,f}(h_S) \leq \epsilon $$

证明

令 $\mathcal{H}_B$ 表示“坏”假设的集合, 即

$$ \mathcal{H}_B = \{ h \in \mathcal{H} : L_{(D, f)}(h) > \epsilon \} $$

令 $S|_x = \{ x_1, \cdots, x_m \}$ 表示训练集的实例, $M = \{S|_x : \exists h \in \mathcal{H}_B, L_S(h) = 0\}$. 注意由可实现假设:

$$ \{S|_x : L_{(D, f)}(h_S) > \epsilon\} \subseteq M = \bigcup_{h \in \mathcal{H}_B} \{S|_x : L_S(h) = 0\}. $$

因此:

$$ \begin{aligned} D^m(\{S|_x : L_{(D, f)}(h_S) > \epsilon\}) &\leq D^m(M) = D^m\left(\bigcup_{h \in \mathcal{H}_B} \{S|_x : L_S(h) = 0\}\right) \\ &\leq \sum_{h \in \mathcal{H}_B} D^m(\{S|_x : L_S(h) = 0\}) \\ &= \sum_{h \in \mathcal{H}_B} \prod_{i=1}^m D(\{x_i : h(x_i) = f(x_i)\}) \end{aligned} $$

注意到对于每个 $h \in \mathcal{H}_B$,

$$ D(\{x_i : h(x_i) = f(x_i)\}) = 1 - L_{(D, f)}(h) \leq 1 - \epsilon $$

代入上式, 再利用 $m$ 的定义可得:

$$ D^m(\{S|_x : L_{(D, f)}(h_S) > \epsilon\}) \leq |\mathcal{H}_B| (1 - \epsilon)^m \le |\mathcal{H}| e^{-\epsilon m} \le \delta $$

由此, 即 $1-D^m(\{S|_x : L_{(D, f)}(h_S) > \epsilon\}) > 1-\delta$, 得证.

定义

称假设空间 $\mathcal{H}$ 是 PAC 可学习的, 如果存在一个函数 $m_{\mathcal{H}} : (0, 1)^2 \to \mathbb{N}$ 和一个学习算法, 满足以下性质: 对于任意 $\delta, \epsilon \in (0, 1)$, 对于任意定义在 $\mathcal{X}$ 上的分布 $\mathcal{D}$, 以及对于任意标记函数 $f : \mathcal{X} \to \{0, 1\}$, 如果可实现性假设相对于 $\mathcal{H}, \mathcal{D}, f$ 成立, 那么当使用由 $\mathcal{D}$ 生成的 $m \geq m_{\mathcal{H}}(\epsilon, \delta)$ 个独立同分布样本, 并用 $f$ 标记这些样本运行该算法时, 算法将返回一个假设 $h$, 使得在样本选择上以至少 $1 - \delta$ 的概率满足

$$ L_{(\mathcal{D}, f)}(h) \leq \epsilon $$

这里, $m$ 的大小称为 样本复杂度.