[机器学习] 5. 一致收敛性 Uniform Convergency

回顾不可知 PAC 的定义

定义 一个假设类 \(\mathcal H\) 是不可知 PAC 可学习的，如果存在函数 \(m_{\mathcal H} : (0, 1)^2 \to \mathbb N\) 和一个学习算法满足，对任意 \(\epsilon, \delta \in (0, 1)\)、\(\mathcal X \times \{0, 1\}\) 上的分布 \(\mathcal D\)，学习算法接收长度为 \(m \geq m_{\mathcal H}(\epsilon, \delta)\) 的训练集可以给出一个假设 \(h\)，使得有至少 \(1 – \delta\) 的概率

\[L_{\mathcal D}(h) \leq \min_{h’ \in \mathcal H} L_{\mathcal D}(h’) + \epsilon \]

其总是关心泛化的结果，而不在乎其过程。但一般地讲来，所谓泛化能力，是指在有限的测试集（就是上文的训练集，但此时不关注训练）上能够体现真实分布上的损失的能力。即

\[|L_S(h) – L_{\mathcal D}(h)| \leq \epsilon \]

定义 一个数据集 \(S\) 被称作（关于作用域 \(\mathcal Z\)，假设类 \(\mathcal H\)，损失函数 \(\ell\)，分布 \(\mathcal D\)）\(\epsilon\)-representative 的，如果

\[\forall h \in \mathcal H, |L_S(h) – L_\mathcal D(h)| \leq \epsilon \]

这是看似比 PAC 更严的条件。因为其不仅仅要求了找到好的假说的能力，还要求了所有假说的泛化能力。

推论 \(S\) 是 \(\epsilon / 2\)-representative 的，则

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

证明

\[L_{\mathcal D}(h_S) \leq L_S(h_S) + \frac \epsilon 2 \leq L_S(h) + \frac \epsilon 2 + \frac \epsilon 2 = L_{\mathcal D}(h) + \epsilon \tag*{$\square$} \]

对于一个单一的假说 \(h\)，\(\mathcal D^m(S \mid |L_S(h) – L_{\mathcal D}(h)| > \epsilon) \to 0\) 的条件，便是采样的均值随着采样数增大高概率 \(\epsilon\)-靠近分布的期望的条件，即 Measure Concentration。这一点在概统中有相当多的结论（注意 Chernoff bound 描述的是两者的比值而不是差，所以这里不用）

引理 (Hoeffding’s Ineq) 令 \(\theta_1, \ldots, \theta_m\) 为独立同分布随机变量，\(\mathbb E[\theta_i] = \mu, \mathbb P[a \leq \theta_i \leq b] = 1\)，则对任意 \(\epsilon> 0\)，

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

于是对任意 \(\epsilon, \delta \in (0, 1)\)，对每一个 \(h \in \mathcal H\) 考虑 \(\theta\) 取自分布 \(\ell \circ (h \times \mathcal D)\)（即按照分布 \(\mathcal D\) 生成实例，经过假说的判断后的损失的分布），则一定存在某个 \(m_h\) 使得条件满足。接下来所需要的，便是考虑所有分布 \(\ell \circ (\mathcal H \times \mathcal D)\) 关于由 \(\mathcal D\) 生成的随机变量的一致性。即，对于某个固定的 \(S\)，\(\sup_{h \in \mathcal H} |L_{\mathcal D}(h) – L_S(h)| < \epsilon\)。由于这里并不再假设 \(\mathcal H\) 是有限的，不能套用 Union bound，这一条件并不直接满足。

定义 称假设类 \(\mathcal H\) 具有一致收敛性 (Uniform Convergence property)，如果存在函数 \(m^{\text{UC}}_{\mathcal H} : (0, 1)^2 \to \mathbb N\) 满足，对任意 \(\epsilon, \delta \in (0, 1)\)、\(\mathcal Z\) 上的分布 \(\mathcal D\)，长度为 \(m \geq m^{\text{UC}}_{\mathcal H}(\epsilon, \delta)\) 的训练集 \(S\) 有至少 \(1 – \delta\) 的概率是 \(\epsilon\)-representative 的。

推论 假设类 \(\mathcal H\) 关于函数 \(m_{\mathcal H}^{\text{UC}}\) 具有一致收敛性，则该假设类是关于 \(m_{\mathcal H}(\epsilon, \delta) \leq m_{\mathcal H}^{\text{UC}}(\epsilon / 2, \delta)\) 不可知 PAC 可学习的，且 ERM 策略生效。

命题 0-1 loss 下的有限假设类一致收敛的，因此是不可知 PAC 可学习的。

证明 Union bound + Hoeffding’s Ineq.

令 \(\theta_{h, i} = \ell(h, x_i)\)，则

\[\begin{aligned} \mathcal D^m(\{(S|_x) \mid \exists h \in \mathcal H, |L_S(h) – L_{\mathcal D}(h)| > \epsilon\}) &\leq \sum_{h \in \mathcal H} \mathcal D^m(\{(S|_x) \mid |L_S(h) – L_{\mathcal D}(h)| > \epsilon\}) \\ &= \sum_{h \in \mathcal H} \mathbb P\left[\left|\frac 1m \sum_{i=1}^m \theta_{h, i} – \mu\right | > \epsilon\right] \\ &\leq 2 |\mathcal H| \exp(-2m \epsilon^2) \end{aligned}\]

令

\[m \geq \frac{\log (2 |\mathcal H| / \delta)}{2\epsilon^2} \]

则有 \(\mathcal D^m(\{S \mid \exists h \in \mathcal H, |L_S(h) – L_{\mathcal D}(h)| > \epsilon\}) \leq \delta\)。故

\[m_{\mathcal H}(\epsilon, \delta) \leq m^{\text{UC}}_{\mathcal H}(\epsilon / 2, \delta) \leq \left\lceil \frac{2 \log(2|\mathcal H| / \delta)}{\epsilon^2}\right\rceil \tag*{$\square$} \]

需要注意的是，一致收敛性是仅对 \(\mathcal H\) 和 \(\ell\) 说的，\(\mathcal D\) 是任意的。能这么说的底气在于以下几点

• 当考虑一个测试集 \(S\) 时，可以只需要考虑

  \[\mathbb E_{S \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} |L_{\mathcal D}(h) – L_S(h)|\right] \]

  关于 \(m\) 收敛的条件。

根据 Markov’s Ineq，

\[\mathbb P_{S \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} |L_{\mathcal D}(h) – L_S(h)| \geq \epsilon\right] \leq \delta \]

其中

\[\epsilon = \frac {\mathbb E_{S \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} |L_{\mathcal D}(h) – L_S(h)|\right]}{\delta} \]

• 我们可以由式子中 \(\mathbb E + \sup\) 的机制去除 \(L_{\mathcal D}\)，而转化为两组测试集的差。

定义 \(C = \{c_1, \ldots, c_m\} \subset \mathcal X\) 是实例集合的一个有限子集，称假设类 \(\mathcal H\) 在 \(C\) 上的 restriction 为

\[\begin{aligned} \mathbb E_{S \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} |L_{\mathcal D}(h) – L_S(h)|\right] &= \mathbb E\left[\sup_{h \in \mathcal H} |(\mathbb E_{S’ \sim \mathcal D^m} L_{S’}(h)) – L_S(h)|\right] \\ &\leq \mathbb E_{S \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} \mathbb E_{S’ \sim \mathcal D^m} |L_{S’}(h) – L_S(h)|\right] && |\mathbb EX| \leq \mathbb E|X| \\ &\leq \mathbb E_{S \sim \mathcal D^m}\left[\mathbb E_{S’ \sim \mathcal D^m}\left[\sup_{h \in \mathcal H} |L_{S’}(h) – L_S(h)|\right]\right] && \sup_{h \in \mathcal H} \mathbb E X(h) \leq \mathbb E \sup_{h \in \mathcal H} X(h) \\ &= \mathbb E_{S, S’ \sim \mathcal D^m} \left[\sup_{h \in \mathcal H} \frac 1m \left|\sum_{i=1}^m (\ell(h, x_i’) – \ell(h, x_i))\right|\right] \end{aligned}\]

此时，\(S, S’\) 对称。于是我们可以通过交换两者进行配对，这样每一对的期望是 \(0\)，于是可以用 Hoeffding’s Ineq 控制。

• 在有限的测试集上，我们可以仅关心那些出现过的实例。更关键的是，由于是两者相减且经过配对，\(\ell\) 具体为多少无关紧要，因此只要没有重复元素，无论基于什么分布生成的任何实例集都是平等的。

\[\begin{aligned} \mathbb E_{S, S’ \sim \mathcal D^m} \left[\sup_{h \in \mathcal H} \frac 1m \left|\sum_{i=1}^m (\ell(h, x_i’) – \ell(h, x_i))\right|\right] &= \mathbb E_{\bm \sigma \in \{\pm 1\}^m}\mathbb E_{S, S’ \sim \mathcal D^m} \left[\sup_{h \in \mathcal H} \frac 1m \left|\sum_{i=1}^m \sigma_i(\ell(h, x_i’) – \ell(h, x_i))\right|\right] \\ &= \mathbb E_{S, S’ \sim \mathcal D^m}\mathbb E_{\bm \sigma \in \{\pm 1\}^m} \left[\sup_{h \in \mathcal H} \frac 1m \left|\sum_{i=1}^m \sigma_i(\ell(h, x_i’) – \ell(h, x_i))\right|\right] && \text{Fubini} \\ &= \mathbb E_{S, S’ \sim \mathcal D^m}\mathbb E_{\bm \sigma \in \{\pm 1\}^m} \left[\sup_{h \in \mathcal {\mathcal H}_C} \frac 1m \left|\sum_{i=1}^m \sigma_i(\ell(h, x_i’) – \ell(h, x_i))\right|\right] && C = \{x_i\} \cup \{x_i’\} \\ \end{aligned}\]

其中，\(\mathcal H_C = \{(h(c_1), \ldots, h(c_m)) \mid h \in \mathcal H\}\) 称为 \(\mathcal H\) 在 \(C \subset \mathcal X\) 上的 restriction。

令 \(\theta_i = \sigma_i (\ell(h, x_i’) – \ell(h, x_i))\)，若 \(\mathcal X\) 为无限集，则 \(\theta_1, \ldots, \theta_m\) 有 \(1\) 的概率是 i.i.d. 的，且 \(\mathbb E_{\sigma_i \sim \{\pm 1\}} [\theta_i] = 0\)，而如果考虑 0-1 loss，则 \(-1 \leq \theta_h \leq 1\)，根据 Hoeffding’s Ineq 可知

\[\mathbb P_{\bm \sigma \in \{\pm 1\}^m}\left[\left|\frac 1m\sum_{i=1}^m \sigma_i (\ell(h, x_i’) – \ell(h, x_i))\right| > \rho\right] \leq 2 \exp\left(-\frac 12 m \rho^2\right) \]

\[\mathbb P_{\bm \sigma \in \{\pm 1\}^m}\left[\max_{h \in \mathcal H_C}\left|\frac 1m\sum_{i=1}^m \sigma_i (\ell(h, x_i’) – \ell(h, x_i))\right| > \rho\right] \leq 2|\mathcal H_C| \exp\left(-\frac 12 m \rho^2\right) \]

现在把它积成 \(\mathbb E\) 的形式。

引理 若存在 \(a > 0, b \geq e\) 使得对所有 \(t \geq 0\) 有 \(\mathbb P[|X – x’| > t] \leq 2b \exp(-t^2 / a^2)\)，则 \(\mathbb E[|X – x’|] \leq a\left(2 + \sqrt{\log b}\right)\)。

证明 令 \(t_i = a \left(i + \sqrt{\log b}\right)\)，\(t_i\) 单调增，因此

\[\begin{alignat}{2} \mathbb E[|X – x’|] &\leq a \sqrt{\log b} + \sum_{i=1}^{\infty} t_i \mathbb P[|X – x’| > t_{i-1}] \notag \\ &\leq a \sqrt{\log b} + 2ab \sum_{i=1}^{\infty} \left(i + \sqrt{\log b} \right) \exp\left(-\left(i – 1 + \sqrt{\log b}\right)^2\right) \notag \\ &\leq a \sqrt{\log b} + 2ab \int_{1 + \sqrt{\log b}}^{\infty} x \exp(-(x – 1)^2) \mathrm dx \notag \\ &= a \sqrt{\log b} + 2ab \int_{\sqrt{\log b}}^{\infty} (x + 1) e^{-x^2} \mathrm dx \notag \\ &\leq a \sqrt{\log b} + 4ab \int_{\sqrt{\log b}}^{\infty} x e^{-x^2} \mathrm dx & b \geq e \notag \\ &= a \left(2 + \sqrt{\log b}\right) \tag*{$\square$} \end{alignat}\]

我们不关心常数，直接用 \(4|\mathcal H_C| > e\) 来做，则

\[\mathbb E_{\bm \sigma \in \{\pm 1\}^m}\left[\max_{h \in \mathcal H_C}\left|\frac 1m\sum_{i=1}^m \sigma_i (\ell(h, x_i’) – \ell(h, x_i))\right|\right] \leq \frac{\left(2 + \sqrt{2 + \log|\mathcal H_C|}\right)\sqrt 2}{\sqrt m} \leq \frac{4 + 2\sqrt{\log |\mathcal H_C|}}{\sqrt m} \]

定义 假设类 \(\mathcal H\) 在实例 \(\mathcal X\) 上的增长函数 \(\tau_{\mathcal H} : \mathbb N \to \mathbb N\) 定义为

\[\tau_{\mathcal H}(m) := \max_{|C| = m} |\mathcal H_C| \]

定理 对任意 \(\mathcal D, \delta \in (0, 1)\)，有至少 \(1 – \delta\) 的概率有

\[|L_{\mathcal D}(h) – L_S(h)| \leq \frac{4 + 2\sqrt{\log(\tau_{\mathcal H}(2m))}}{\delta\sqrt m} \]

由此，我们得到

定理 对 0-1 loss，若

\[\lim_{m \to \infty} \frac{\log(\tau_{\mathcal H}(m))}{m} = 0 \]

则 \(\mathcal H\) 是不可知 PAC 可学习的。

这是一个相当一般的结论，其不依赖于 \(\mathcal D\)，只与 \(\mathcal H\) 自身的性质有关。