定义

我们定义 泛化误差 为:

$$ L_{\mathcal{D},f}(h) = P_{X \sim \mathcal{\mathcal{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_{\mathcal{D},f}(h^*) = 0$, 则称为 $f,\mathcal{D}$ 满足 可实现假设.

定理

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

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

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

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

证明

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

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

因此:

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

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

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

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

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

由此, 即 $1-\mathcal{D}^m(\{S|_x : L_{(\mathcal{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{\mathcal{D}}$, 以及对于任意标记函数 $f : \mathcal{X} \to \{0, 1\}$, 如果可实现性假设相对于 $\mathcal{H}, \mathcal{\mathcal{D}}, f$ 成立, 那么当使用由 $\mathcal{\mathcal{D}}$ 生成的 $m \geq m_{\mathcal{H}}(\epsilon, \delta)$ 个独立同分布样本, 并用 $f$ 标记这些样本运行该算法时, 算法将返回一个假设 $h$, 使得在样本选择上以至少 $1 - \delta$ 的概率满足

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

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

定义

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

$$ L_{\mathcal{\mathcal{D}}}(h) \le \min_{h' \in \mathcal{H}} L_{\mathcal{\mathcal{D}}}(h') + \epsilon $$

特别地, 我们称假设空间 $\mathcal{H}$ 是关于集合 $Z$ 和损失函数 $\ell: \mathcal{H} \times Z \to \mathbb{R}_+$ 不可知 PAC 可学习的, 如果在上述定义中 $\mathcal{\mathcal{D}}$ 是 $Z$ 上的分布, 且不等式中 $L_{\mathcal{\mathcal{D}}}(h) = \mathbb{E}_{z \sim \mathcal{\mathcal{D}}}[\ell(h, z)]$.

定义

训练集 $S$ 被称为关于域 $Z$, 假设空间 $\mathcal{H}$, 损失函数 $\ell$ 和分布 $\mathcal{\mathcal{D}}$ 是 $\epsilon$-典型的, 如果

$$ \forall h \in \mathcal{H}, |L_S(h) - L_{\mathcal{\mathcal{D}}}(h)| \leq \epsilon $$

定理

假设训练集 $S$ 是 $\epsilon/2$-典型的, 则对于任意 $ERM_\mathcal{\mathcal{H}}(S)$ 算法的输出, 即任意 $h_S \in \argmin_{h \in \mathcal{H}} L_S(h)$, 有:

$$ L_{\mathcal{\mathcal{D}}}(h_S) \leq \min_{h \in \mathcal{H}} L_D(h) + \epsilon $$

证明

利用定义可知

$$ L_{\mathcal{\mathcal{D}}}(h_S) \le L_S(h_S) + \epsilon/2 \le L_S(h) + \epsilon/2 \le L_{\mathcal{\mathcal{D}}}(h) + \epsilon $$

定义

称假设空间 $\mathcal{H}$ 关于域 $Z$, 损失函数 $\ell$ 具有 一致收敛性, 如果存在一个函数 $m_{\mathcal{H}}^{UC}: (0, 1)^2 \to \mathbb{N}$, 使得对于任意 $\epsilon, \delta \in (0, 1)$ 和任意 $Z$ 上的分布 $\mathcal{\mathcal{D}}$, 如果 $S$ 是从 $\mathcal{\mathcal{D}}$ 中独立同分布抽取的大小为 $m \geq m_{\mathcal{H}}^{UC}(\epsilon, \delta)$ 的样本, 则以至少 $1 - \delta$ 的概率, $S$ 是 $\epsilon$-典型的.

定理

如果假设空间 $\mathcal{H}$ 对于 $m_{\mathcal{H}}^{UC}(\epsilon, \delta)$ 具有一致收敛性, 则 $\mathcal{H}$ 是不可知 PAC 可学习的, 且样本复杂度满足:

$$ m_{\mathcal{H}}(\epsilon, \delta) \leq m_{\mathcal{H}}^{UC}(\epsilon/2, \delta) $$

在这种情况下, $ERM_\mathcal{H}(S)$ 算法是 $\mathcal{H}$ 的不可知 PAC 学习算法.

定理Hoeffding 不等式

设 $\theta_1, \cdots, \theta_m$ 是独立同分布随机变量, 且 $\mathbb{E}[\theta_i] = \mu$, $P(\theta_i \in [a, b]) = 1$. 则对于任意 $\epsilon > 0$, 有:

$$ P\left(\left|\frac{1}{m} \sum_{i=1}^m \theta_i - \mu\right| > \epsilon\right) \leq 2 \exp\left(-\frac{2m\epsilon^2}{(b-a)^2}\right) $$

定理

设 $\mathcal{H}$ 是有限的假设空间, $Z$ 是一个域, $\ell : \mathcal{H} \times Z \to [0, 1]$ 是一个损失函数. 则 $\mathcal{H}$ 具有一致收敛性, 且样本复杂度满足:

$$ m_{\mathcal{H}}^{UC}(\epsilon, \delta) \leq \left\lceil \frac{\log(2|\mathcal{H}|/\delta)}{2\epsilon^2} \right\rceil $$

且此时 $\mathcal{H}$ 是不可知 PAC 可学习的, 且样本复杂度满足:

$$ m_{\mathcal{H}}(\epsilon, \delta) \leq m_{\mathcal{H}}^{UC}(\epsilon/2, \delta) \leq \left\lceil \frac{2\log(2|\mathcal{H}|/\delta)}{\epsilon^2} \right\rceil $$

证明

固定 $\epsilon, \delta$, 我们要找 $m$ 使得对任意 $\mathcal{\mathcal{D}}$, 至少 $1 - \delta$ 的概率, $S$ 是 $\epsilon$-典型的. 即:

$$ \mathcal{\mathcal{D}}^m(\{ S: \forall h \in \mathcal{H}, |L_S(h)-L_{\mathcal{\mathcal{D}}}(h)| \le \epsilon \}) \ge 1 - \delta $$

注意由 Hoeffding 不等式:

$$ \begin{aligned} &\mathcal{\mathcal{D}}^m(\{ S: \forall h \in \mathcal{H}, |L_S(h)-L_{\mathcal{\mathcal{D}}}(h)| > \epsilon \}) \\ & \le \sum_{h \in \mathcal{H}} \mathcal{\mathcal{D}}^m(\{ S: |L_S(h)-L_{\mathcal{\mathcal{D}}}(h)| > \epsilon \}) \\ & \le \sum_{h \in \mathcal{H}} 2 e^{-2m\epsilon^2} = 2|\mathcal{H}| e^{-2m\epsilon^2} \end{aligned} $$

我们只要取:

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

即得:

$$ \mathcal{\mathcal{D}}^m(\{ S: \forall h \in \mathcal{H}, |L_S(h)-L_{\mathcal{\mathcal{D}}}(h)| > \epsilon \}) \le \delta $$

从而得证.

定理无免费午餐

设 $A$ 是在域 $X$ 上的 $0-1$ 误差函数二分类学习算法, 训练集大小 $m$ 是小于 $|X|/2$ 的任意数. 则存在一个在 $X \times \{0, 1\}$ 上的分布 $\mathcal{\mathcal{D}}$ 使得:

1. 存在一个函数 $f : X \to \{0, 1\}$ 使得 $L_{\mathcal{\mathcal{D}}}(f) = 0$.
2. 选择 $S \sim \mathcal{\mathcal{D}}^m$ 时, 有至少 $1/7$ 的概率满足 $L_{\mathcal{\mathcal{D}}}(A(S)) \geq 1/8$.

定理

设 $\mathcal{X}$ 是一个无限域, $\mathcal{H}$ 是从 $\mathcal{X}$ 到 $\{0, 1\}$ 的所有函数的集合. 则 $\mathcal{H}$ 不是 PAC 可学习的.

证明

假设 $\mathcal{H}$ 是 PAC 可学习的, 选 $\epsilon < 1/8, \delta < 1/7$, 则存在一个算法 $A$ 和一个整数 $m=m_{\mathcal{H}}(\epsilon, \delta)$, 对任意 $\mathcal{X} \times \{0, 1\}$ 上的分布 $\mathcal{D}$, 如果对于某个函数 $f: \mathcal{X} \to \{0, 1\}$, $L_{\mathcal{\mathcal{D}}}(f) = 0$, 则当 $A$ 在 $S \sim \mathcal{\mathcal{D}}^m$ 上运行时, 有至少 $1 - \delta$ 的概率满足: $L_{\mathcal{\mathcal{D}}}(A(S)) \leq \epsilon$.

但根据无免费午餐定理, 由于 $|X|>2m$, 对于算法 $A$, 存在一个分布 $\mathcal{\mathcal{D}}$ 使得有至少 $1/7>\delta$ 的概率满足 $L_{\mathcal{\mathcal{D}}}(A(S)) \geq 1/8>\epsilon$, 矛盾.