[机器学习] 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 \]

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

\[|LS(h) - L{\mathcal D}(h)| \leq \epsilon \]

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

\[\forall h \in \mathcal H, |LS(h) - L\mathcal D(h)| \leq \epsilon \]

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

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

\[L_{\mathcal D}(hS) \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 LS(h) + \frac \epsilon 2 + \frac \epsilon 2 = L{\mathcal D}(h) + \epsilon \tag*{\(\square\)} \]

对于一个单一的假说 \(h\)，\(\mathcal D^m(S \mid |LS(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\) 生成实例，经过假说的判断后的损失的分布），则一定存在某个 \(mh\) 使得条件满足。接下来所需要的，便是考虑所有分布 \(\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, |LS(h) - L{\mathcal D}(h)| > \epsilon\}) &\leq \sum_{h \in \mathcal H} \mathcal D^m(\{(S|_x) \mid |LS(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, |LS(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) - LS(h)|\right] &= \mathbb E\left[\sup{h \in \mathcal H} |(\mathbb E{S’ \sim \mathcal D^m} L{S’}(h)) - LS(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) - LS(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) - LS(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, xi))\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, xi))\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, xi))\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, \thetam\) 有 \(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 HC}\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} ti \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 HC}\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) - LS(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\) 自身的性质有关。