计算学习理论 (2)
作者：光火
邮箱：
victor_b_zhang@163.com
计算学习理论旨在通过分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。该部分内容在机器学习中难度较高，笔者计划通过一系列文章 / 笔记，对其中的重点知识进行分析与讲解，方便有需求的读者检索、查阅
概率近似正确
-
上一篇文章中，我们讲到了有限假设空间泛化误差界。利用它，可以证明有限假设空间是 PAC-可学习的。PAC，是 Probably Approximately Correct 的缩写，即概率近似正确。在具体证明之前，我们首先给出其基本概念
-
A hypothesis space \(\mathcal{H}\) is PAC-learnable if there exists an algorithm \(\mathcal{A}\) and a polynomial function \(poly()\), such that for any \(\epsilon > 0,\delta > 0\), for all distributions \(D\) on \(\mathcal X\) and for any target hypothesis \(h \in \mathcal H\), the following holds for sample complexity \(n \geq poly(\frac{1}{\epsilon}, \frac{1}{\delta}, |\mathcal H|):\)
\(\mathcal E(h_{\mathcal{D}_n})\)：学到的模型的期望误差
\(\min_{h \in \mathcal H} \mathcal E(h)\)：期望误差中的最小值
以上两个概念均建立在数据分布 \(D\) 已知的前提下
\(D\) ：样本空间 \(\mathcal X\) 中的任意分布；\(h\) ：假设空间 \(\mathcal{H}\) 中的任意假设
\(n\) 表示样本复杂度，即为获得该不等式，至少需要多少样本
区分样本复杂度与计算复杂度：样本数目越多，计算复杂度越高，样本复杂度越小
整体理解：我们希望学到的模型所对应的期望误差，与最优期望误差之间的差距 \(\geq \epsilon\) 是一个小概率事件。方括号中的 \(\Big[\mathcal E(h_{\mathcal{D}_n}) - \min_{h \in \mathcal H} \mathcal E(h) \geq \epsilon \Big]\) 就代表了近似正确（如果是完全正确，两者相减应当为零）而差距 \(\geq \epsilon\) 的概率 \(\leq \delta\) 就代表了概率正确（误差较大的情况只以小概率发生）这就是概率近似正确的含义
- 下面，我们证明有限假设空间是 PAC-可学习的
\((1)\) 式引入经验误差的最小值 \(\hat{\mathcal{E}}_{\mathcal D_n}(h_{\mathcal D_n})\)，如此操作的原因是 PAC 可学习 描述的是期望误差间的关系，但是我们此前得出的泛化误差界，刻画的是经验误差与期望误差间的关系。为此，我们需要在该式中引入经验误差，以提供更多的参照
\((2)\) 式相较于 \((1)\) ，将 \(\hat{\mathcal{E}}_{\mathcal D_n}(h_{\mathcal D_n})\) 替换为 \(\hat{\mathcal{E}}_{\mathcal D_n}(h^*)\)，\(h^*\) 是使得期望误差最小的假设，但是它未必使得经验误差最小，因此替换后，由于 \(\hat{\mathcal{E}}_{\mathcal D_n}(h^*) \geq \hat{\mathcal{E}}_{\mathcal D_n}(h_{\mathcal D_n})\)，所以 \((1) \leq (2)\)
\((3)\) 式应用性质，两项之和不大于两项的绝对值之和。此时，\((3)\) 式的两个子式均为期望误差与经验误差相减的形式，我们取两者的上界，即可得到 \((4)\) 式（\(\big|\mathcal{E}(h_{\mathcal D_n}) - \hat{\mathcal{E}}_{\mathcal D_n}(h_{\mathcal D_n}) \big| \leq \sup_{h \in \mathcal{H}}\big|\hat{\mathcal{E}}_{\mathcal D_n}(h)- \mathcal{E}(h) \big|\)，\(\big|\hat{\mathcal{E}}_{\mathcal D_n}(h^*)- \mathcal{E}(h^*) \big| \leq \sup_{h \in \mathcal{H}}\big|\hat{\mathcal{E}}_{\mathcal D_n}(h)- \mathcal{E}(h) \big|\)，所以 \((3) \leq (4)\)
转化至此，即可应用之前推导的有限假设空间泛化误差界：\(P\big(\sup_{h\in \mathcal{H}} \big| \hat{\mathcal{E}}_{D_n}(h) - \mathcal{E}(h) \big | \geq \epsilon \big|\big) \leq 2\mathcal{|H|} \exp(-2n\epsilon^2)\)
因此，有限假设空间是 PAC-可学习的
无限假设空间泛化误差界
- 有了上述知识储备后，我们介绍无限假设空间泛化界。所谓无限假设空间，指的就是 \(|\mathcal{H}| = +\infty\) 的情况，即假设空间中存在无数个假设。在日常生活中，我们使用的机器学习模型，假设空间基本都是无穷的
- 在机器学习中，我们通过拟合数据的能力，刻画假设空间的复杂性。模型拟合数据的能力越强，它所对应的假设空间就越大
- 那该如何度量拟合数据的能力呢？我们引入两个基础概念：
- 对分：用分类器对数据进行随机的划分（为每个数据随机指定一个 label）。那么对于二分类问题，就会产生 \(2^n\) 种排列，每种排列就对应一个对分
- 打散：如果对于所有的对分，假设空间均能将其正确区分开，就称为打散（相当于完美拟合）
- 在此基础上，我们就可以尝试理解计算学习理论最为复杂的三个概念了：Rademacher Complexity、Growth Function、Vapnik-Chervonenkis Dimension，它们都是用于衡量假设空间 \(\mathcal H\) 复杂程度的机制
Rademacher Complexity
- 考虑一个给定的数据集 \(S\)，它共有 \(n\) 个样本
利用模型集 \(h\) 对其进行划分（比如 \(h\) 是一种特定的神经网络结构）
采用 \(01\) 损失函数，则经验误差
依据上述公式，可以定义预测结果和真实结果之间的相关性 \(correlation = \frac{1}{n}\sum_{i=1}^n y_ih(x_i)\)
correlation 越大，则表明模型的分类效果越好，因此我们的目标就是找到一个使得 correlation 最大的模型 \(\large \sup_{h \in \mathcal{H}} \frac{1}{n}\sum_{i=1}^n y_ih(x_i)\)
同时，考虑到不同对分所对应的难易程度不同，我们应当取所有对分（共 \(2^n\) 种）的平均相似度
这时，我们将真实结果替换为 \(Rademacher\quad variable\)，即随机样本标签
由此得到 \(Empirical\quad Rademacher\quad Complexity\)
Let \(\mathfrak{g}\) be a family of general functions mapping from \(\mathrm {Z}\) to \([0, 1]\)；Let \(\sigma_i\) be Rademacher variable；
Empirical Rademacher Complexity of \(\mathfrak{g}\) on a size-n sample set \(\mathcal{S}_n = \{z_1,z_2,...,z_n\}\)
进一步考虑不同的 sample set，得到 Expected Rademacher Complexity:
- \(Rademacher\quad Complexity\) 的性质
\(Rademacher\quad Complexity\) 是关于 \(n\) 的减函数，该证明需要用到 \(Jensen\) 不等式和重采样
\(Rademacher\quad Complexity \leq 1\) ，\(= 1\) 就对应打散的情况
- \(Rademacher\quad Complexity\quad Bound\)
基于 \(Rademacher\quad Complexity\) 的泛化误差界
Theorem: Let \(\mathfrak{g}\) be a family of general functions mapping from \(\mathrm {Z}\) to \([0, 1]\). Then, for any \(\delta > 0\), with probability at least \(1 - \delta\), the following bound holds for all \(g \in \mathfrak{g}\):
具体推导：
回忆 \(McDiarmid\) 不等式
若 \(x_1, x_2,...,x_m\) 为 \(m\) 个独立随机变量，且对任意 \(1 \leq i \leq m\)，函数 \(f\) 满足
则对任意 \(\epsilon > 0\) 有
可见，要应用 \(McDiarmid\) 不等式，应先要满足其条件。于是引入 \(\mathcal{S}'\)， \(\mathcal{S}'\) 与 \(\mathcal{S}\) 只有一个变量的取值不同
Change \(\mathcal{S}\) to \(\mathcal{S}'= \{z_1,...,z_i',..,z_n\}\) that differs only at \(z_i' \not = z_i\)
\((2)\) 式是在 \((1)\) 的基础上，通过 \(\sup\) 的性质得到的，形式很类似于三角不等式
由于 \(\mathcal{S}'\) 与 \(\mathcal{S}\) 只有一个变量的取值不同（\(z_i' \not = z_i\)），且 \(g(z_i) \leq 1\)，所以 \((3) \rightarrow (4)\)
至此，使用 \(McDiarmid\) 不等式的条件已经满足，取 \(c_i = \frac{1}{n}\)
令 \(\delta = P\Big(\Phi(\mathcal{S}) - \mathbb E_{\mathcal{S}}\Phi(\mathcal{S})\geq \epsilon \Big)\)，则有 \(\delta \leq \exp(-2n\epsilon^2)\)，解出 \(\epsilon\)，
则 With probability at least \(1 - \frac{\delta}{2}\)：\(\Phi(\mathcal{S}) \leq \mathbb E_{\mathcal{S}}[\Phi(\mathcal{S})] + \sqrt \frac{\log(2/\delta)}{2n}\quad (*)\)
在 \((*)\) 的基础上，我们进一步求 \(E_{\mathcal{S}}[\Phi(\mathcal{S})]\) 的上界
\((2)\) 采用了重采样，有如下关系成立：\(\mathbb E_D[g] = \mathbb E_{\mathcal{S}'\sim D^n}\hat{\mathbb E}_{\mathcal{S}'}[g]\)
\((3)\) 由于 \(\hat{\mathbb{E}}_{\mathcal{S}}[g]\) 与 \(\mathcal{S}'\) 无关，所以 \(\mathbb E_{\mathcal{S}'} \hat{\mathbb{E}}_{\mathcal{S}}[g] = \hat{\mathbb{E}}_{\mathcal{S}}[g]\)，因此可以将 \(\mathbb E_{\mathcal{S}'}\) 提出来
\((4)\) 在 \((3)\) 的基础上使用 \(Jensen\) 不等式
\((5)\) 在 \((4)\) 的基础上对期望进行展开
\((6)\) 式引入 \(Rademacher\quad variable\)，当 \(\sigma_i = 1\) 时，\((6)\) 和 \((5)\) 的形式一致；当 \(\sigma_i = -1\) 时，由于我们是对 \(\mathcal{S},\mathcal{S}'\) 同时求期望，此时只需交换 \(z_i\) 和 \(z_i'\) 的取值即可
\((7)\) 应用 \(\sup\) 的三角不等式 \(\sup(A + B) \leq \sup A + \sup B\)
如此，整合 \((*)\) 和 \((**)\)，得
With probability at least \(1 - \delta\)