定义

设 $\mathcal{H}$ 是从 $X$ 到 $\{0, 1\}$ 的函数类, $C = \{c_1, \ldots, c_m\} \subset X$. $\mathcal{H}$ 在 $C$ 上的 限制 是可以从 $\mathcal{H}$ 生成的从 $C$ 到 $\{0, 1\}$ 的函数集, 即:

$$\mathcal{H}_C = \{(h(c_1), \ldots, h(c_m)) : h \in \mathcal{H}\}$$

其中我们将每个从 $C$ 到 $\{0, 1\}$ 的函数表示为一个 $\{0,1\}^{|C|}$ 向量.

定义

一个假设类 $\mathcal{H}$ 打散 一个有限集 $C \subset X$, 如果 $\mathcal{H}_C$ 是从 $C$ 到 $\{0, 1\}$ 的所有函数的集合. 即:

$$|\mathcal{H}_C| = 2^{|C|}$$

定理

设 $\mathcal{H}$ 是从 $\mathcal{X}$ 到 $\{0, 1\}$ 的假设类, $m$ 是训练集大小. 如果存在一个大小为 $2m$ 的集合 $C \subset \mathcal{X}$ 被 $\mathcal{H}$ 打散, 则对于任何学习算法 $A$, 存在一个在 $\mathcal{X} \times \{0, 1\}$ 上的分布 $\mathcal{D}$, 和一个预测器 $h \in \mathcal{H}$, 使得 $L_{\mathcal{D}}(h) = 0$, 但以至少 $\frac{1}{7}$ 的概率, 在 $S \sim \mathcal{D}^m$ 上有:

$$ L_{\mathcal{D}}(A(S)) \geq \frac{1}{8} $$

定义

假设类 $\mathcal{H}$ 的 VC 维, 记为 $\text{VCdim}(\mathcal{H})$, 是 $\mathcal{H}$ 可以打散的最大集合 $C \subset \mathcal{X}$ 的大小. 如果 $\mathcal{H}$ 可以打散任意大大小的集合, 则称 $\mathcal{H}$ 的 VC 维为无穷大.

定义

设 $\mathcal{H}$ 是从 $\mathcal{X}$ 到 $\{0, 1\}$ 的假设类. 则 $\mathcal{H}$ 的 增长函数 $\tau_{\mathcal{H}}: \mathbb{N} \to \mathbb{N}$ 定义为:

$$ \tau_{\mathcal{H}}(m) = \max_{C \subset \mathcal{X}: |C| = m} |\mathcal{H}_C| $$

定理Sauer-Shelah-Perles

设 $\mathcal{H}$ 是一个假设类, 且 $\text{VCdim}(\mathcal{H}) = d < \infty$. 则对于所有 $m$, 有:

$$ \tau_{\mathcal{H}}(m) \leq \sum_{i=0}^{d} \binom{m}{i} $$

特别地, 如果 $m > d + 1$, 则有:

$$ \tau_{\mathcal{H}}(m) \leq \left(\frac{em}{d}\right)^d $$

定理

设 $\mathcal{H}$ 是一个假设类, 且 $\tau_{\mathcal{H}}$ 是它的增长函数. 则对于每个分布 $\mathcal{D}$ 和每个 $\delta \in (0, 1)$, 在 $S \sim \mathcal{D}^m$ 的选择下, 有超过 $1 - \delta$ 的概率满足:

$$ |L_{\mathcal{D}}(h) - L_{S}(h)| \leq \frac{4 + \sqrt{\log(\tau_{\mathcal{H}}(2m))}}{\delta\sqrt{2m}} $$

定理统计学习基本定理

设 $\mathcal{H}$ 是从 $\mathcal{X}$ 到 $\{0, 1\}$ 的假设类, 且损失函数为 0-1 损失. 则以下条件等价:

1. $\mathcal{H}$ 具有一致收敛性质.
2. 任何经验风险最小化 (ERM) 规则都是 $\mathcal{H}$ 的成功不可知 PAC 学习器.
3. $\mathcal{H}$ 是不可知 PAC 可学习的.
4. $\mathcal{H}$ 是 PAC 可学习的.
5. 任何经验风险最小化 (ERM) 规则都是 $\mathcal{H}$ 的成功 PAC 学习器.
6. $\mathcal{H}$ 的 VC 维是有限的.

证明

只要证明 VC 维有限时一致收敛性质成立即可. 根据 Sauer 引理, 对于 $m > d$, 有 $\tau_{\mathcal{H}}(2m) \leq (2em/d)^d$. 结合上述定理, 得到超过 $1 - \delta$ 的概率满足:

$$ |L_{\mathcal{D}}(h) - L_{S}(h)| \leq \frac{4 + \sqrt{d \log(2em/d)}}{\delta \sqrt{2m}} $$

简化考虑 $\sqrt{d \log(2em/d)} \geq 4$ 忽略常数, 即:

$$ |L_{\mathcal{D}}(h) - L_{S}(h)| \leq \frac{1}{\delta} \sqrt{\frac{2d \log(2em/d)}{m}} $$

要保证右边不超过 $\epsilon$, 只需满足:

$$ m \geq \frac{2d \log(m)}{(\delta \epsilon)^2} + \frac{2d \log(2e/d)}{(\delta \epsilon)^2} $$

为了消去右边的 $x$, 可以证明 $x \geq 4a \log(2a) + 2b \Rightarrow x \geq a \log(x) + b$ 对于 $a \geq 1$ 和 $b > 0$ 成立, 则上述不等式的充分条件是:

$$ m \geq 4 \frac{2d}{(\delta \epsilon)^2} \log\left(\frac{4d}{(\delta \epsilon)^2}\right) + \frac{4d \log(2e/d)}{(\delta \epsilon)^2} $$

此时即可满足, 因此$\mathcal{H}$ 具有一致收敛性质.

定理统计学习基本定理量化版本

设 $\mathcal{H}$ 是从 $\mathcal{X}$ 到 $\{0, 1\}$ 的假设类, 且损失函数为 0-1 损失. 假设 $\text{VCdim}(\mathcal{H}) = d < \infty$. 则存在常数 $C_1, C_2$ 满足:

1. $\mathcal{H}$ 具有一致收敛性质, 且样本复杂度满足: $$ C_1 \frac{d + \log(1/\delta)}{\epsilon^2} \leq m_{\mathcal{H}}^{UC}(\epsilon, \delta) \leq C_2 \frac{d + \log(1/\delta)}{\epsilon^2} $$
2. $\mathcal{H}$ 是不可知 PAC 可学习的, 且样本复杂度满足: $$ C_1 \frac{d + \log(1/\delta)}{\epsilon^2} \leq m_{\mathcal{H}}(\epsilon, \delta) \leq C_2 \frac{d + \log(1/\delta)}{\epsilon^2} $$
3. $\mathcal{H}$ 是 PAC 可学习的, 且样本复杂度满足: $$ C_1 \frac{d + \log(1/\delta)}{\epsilon} \leq m_{\mathcal{H}}(\epsilon, \delta) \leq C_2 \frac{d \log(1/\epsilon) + \log(1/\delta)}{\epsilon} $$

定义

我们称假设 $h$ 关于假设 $h'$ 是 $(\epsilon, \delta)$ 可比的, 如果有超过 $1-\delta$ 的概率满足:

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

定义

一个假设类 $\mathcal{H}$ 是 非一致可学习的, 如果存在一个学习算法 $A$ 和一个函数 $m_{\mathcal{H}}^{NUL} : (0, 1)^2 \times \mathcal{H} \rightarrow \mathbb{N}$, 使得对于每个 $\epsilon, \delta \in (0, 1)$ 和每个 $h \in \mathcal{H}$, 如果 $m \geq m_{\mathcal{H}}^{NUL}(\epsilon, \delta, h)$, 则对于每个分布 $\mathcal{D}$, 在 $S \sim \mathcal{D}^m$ 上有超过 $1-\delta$ 的概率满足:

$$ L_{\mathcal{D}}(A(S)) \leq L_{\mathcal{D}}(h) + \epsilon $$

定理

如果一个假设类 $\mathcal{H}$ 可以被写成可数个假设类的并集 $\mathcal{H} = \bigcup_{n \in \mathbb{N}} \mathcal{H}_n$, 且每个 $\mathcal{H}_n$ 都是一致收敛的, 则 $\mathcal{H}$ 是非一致可学习的.

定理

一个二分类假设类 $\mathcal{H}$ 是非一致可学习的，当且仅当它是可数个不可知 PAC 可学习假设类的并集.

证明

充分性: 假设 $\mathcal{H} = \bigcup_{n \in \mathbb{N}} \mathcal{H}_n$, 其中每个 $\mathcal{H}_n$ 都是不可知 PAC 可学习的. 根据统计学习的基本定理, 每个 $\mathcal{H}_n$ 都具有一致收敛性质, 从而 $\mathcal{H}$ 是非一致可学习的.

必要性: 假设 $\mathcal{H}$ 是非一致可学习的, 使用某个算法 $A$. 对于每个 $n \in \mathbb{N}$, 令:

$$ \mathcal{H}_n = \{h \in \mathcal{H} : m_{\mathcal{H}}^{NUL}(1/8, 1/7, h) \leq n\} $$

显见 $\mathcal{H} = \bigcup_{n \in \mathbb{N}} \mathcal{H}_n$.

定理

设 $w: \mathbb{N} \to [0, 1]$ 是一个函数, 满足 $\sum_{n=1}^\infty w(n) \leq 1$. 设假设类 $\mathcal{H}$ 可以写成 $\mathcal{H} = \bigcup_{n \in \mathbb{N}} \mathcal{H}_n$, 且每个 $\mathcal{H}_n$ 都满足一致收敛性质, 具有样本复杂度函数 $m_{\mathcal{H}_n}^{UC}$. 定义 $\epsilon_n: \mathbb{N} \times (0, 1) \to (0, 1)$ 为:

$$ \epsilon_n(m, \delta) = \min \{\epsilon \in (0, 1) : m_{\mathcal{H}_n}^{UC}(\epsilon, \delta) \leq m\} $$

则对于每个 $\delta \in (0, 1)$ 和分布 $\mathcal{D}$, 在 $S \sim \mathcal{D}^m$ 上, 有超过 $1 - \delta$ 的概率满足:

$$ |L_{\mathcal{D}}(h) - L_S(h)| \leq \epsilon_n(m, w(n) \cdot \delta) $$

因此，对于每个 $\delta \in (0, 1)$ 和分布 $\mathcal{D}$, 在 $S \sim \mathcal{D}^m$ 上, 有超过 $1 - \delta$ 的概率满足:

$$ \forall h \in \mathcal{H}, L_{\mathcal{D}}(h) \leq L_S(h) + \min_{n: h \in \mathcal{H}_n} \epsilon_n(m, w(n) \cdot \delta) $$

证明

对于每个 $n$ 定义 $\delta_n = w(n) \delta$. 应用一致收敛性质的假设, 预先固定 $n$, 则对于每个 $S \sim \mathcal{D}^m$, 有超过 $1 - \delta_n$ 的概率满足:

$$ \forall h \in \mathcal{H}_n, \ |L_{\mathcal{D}}(h) - L_{S}(h)| \leq \epsilon_n(m, \delta_n). $$

则对于所有 $n = 1, 2, \ldots$, 有超过

$$1 - \sum_{n} \delta_n = 1 - \delta\left(\sum_{n} w(n)\right) \geq 1 - \delta$$

的概率满足上述不等式, 这就完成了证明.

算法结构风险最小化 (SRM)

输入: 训练集 $S \sim \mathcal{D}^m$, 置信度 $\delta$.

输出: $h \in \arg\min_{h \in \mathcal{H}} [L_S(h) + \epsilon_{n(h)}(m, w(n(h))\delta)]$.

先前知识:

• $\mathcal{H} = \bigcup_{n \in \mathbb{N}} \mathcal{H}_n$, 其中每个 $\mathcal{H}_n$ 都满足一致收敛性质, 具有样本复杂度函数 $m_{\mathcal{H}_n}^{UC}$;
• $w : \mathbb{N} \to [0, 1]$, 且 $\sum_n w(n) \leq 1$.

定义:

$$\epsilon_n(m, \delta) = \min \{ \epsilon \in (0, 1) : m_{\mathcal{H}_n}^{UC}(\epsilon, \delta) \leq m \}$$$$n(h) = \min \{ n : h \in \mathcal{H}_n \}$$

定理

设 $\mathcal{H}$ 是一个假设类, 满足 $\mathcal{H} = \bigcup_{n \in \mathbb{N}} \mathcal{H}_n$, 其中每个 $\mathcal{H}_n$ 都满足一致收敛性质, 具有样本复杂度函数 $m_{\mathcal{H}_n}^{UC}$. 令 $w: \mathbb{N} \to [0, 1]$ 是一个加权函数, 满足 $w(n) = \frac{6}{n^2 \pi^2}$. 则 $\mathcal{H}$ 是非一致可学习的, 使用 SRM 规则, 且速率为:

$$ m_{\mathcal{H}}^{NUL}(\epsilon, \delta, h) \leq m_{\mathcal{H}_{n(h)}}^{UC}\left(\epsilon/2, \frac{6\delta}{(\pi n(h))^2}\right)$$

证明

设 $A$ 是关于加权函数 $w$ 的 SRM 算法. 对于每个 $h \in \mathcal{H}$, $\epsilon$, 和 $\delta$, 令:

$$ m \geq m_{\mathcal{H}_{n(h)}}^{UC}(\epsilon, w(n(h))\delta) $$

由于 $\sum_{n} w(n) = 1$, 由如上定理, 得到在 $S \sim \mathcal{D}^m$ 的选择下, 有超过 $1 - \delta$ 的概率满足:

$$ L_{\mathcal{D}}(h') \leq L_{S}(h') + \epsilon_{n(h')}(m, w(n(h'))\delta) $$

这个不等式对于每个 $h' \in \mathcal{H}$ 都成立, 取 $h' = A(S)$, 由 SRM 得到:

$$ \begin{aligned} L_{\mathcal{D}}(A(S)) &\leq \min_{h'}[L_{S}(h') + \epsilon_{n(h')}(m, w(n(h'))\delta)] \\ &\leq L_{S}(h) + \epsilon_{n(h)}(m, w(n(h))\delta) \end{aligned} $$

如果 $m \geq m_{\mathcal{H}_{n(h)}}^{UC}(\epsilon/2, w(n(h))\delta)$, 则显然:

$$ \epsilon_{n(h)}(m, w(n(h))\delta) \leq \epsilon/2 $$

此外, 由于每个 $\mathcal{H}_n$ 都满足一致收敛性质, 有超过 $1 - \delta$ 的概率满足:

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

综上所述, 得到:

$$ L_{\mathcal{D}}(A(S)) \leq L_{\mathcal{D}}(h) + \epsilon $$