计算学习理论 (1)
作者：光火
邮箱：victor_b_zhang@163.com
计算学习理论旨在通过分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。该部分内容在机器学习中难度较高，笔者计划通过一系列文章 / 笔记，对其中的重点知识进行分析与讲解，方便有需求的读者检索、查阅
基础知识
-
目前机器学习的主流仍为统计机器学习，而统计机器学习的基本假设就是：训练样本、测试样本均是从某一未知分布中随机采样得到的，且不同样本间没有关联，不会相互影响（独立同分布假设）
-
期望误差：\(\large{\varepsilon (h) = E_{(x,y)\sim D(x,y)}\ell (h(x), y)}\)
经验误差：\(\large{\hat \varepsilon_{\mathcal{D_n}} (h) = \frac{1}{n}\sum_{i=1}^n\ell(h(x_i),y_i)}\)
下标 \((x,y) \sim D(x,y)\) 表示数据 \((x,y)\) 是从分布 \(D\) 中采样得到的
-
直观理解：期望误差就相当于对分布 \(D\) 上的所有样本（无穷个）对应的损失函数值求期望。倘若我们能够使得期望误差达到最小，就意味着我们找到了一个对于整个分布 \(D\) 都行之有效的假设函数 \(h(x)\)
-
由于期望误差无法计算，因此在实际编程中，我们一般采用经验误差，对采样到的有限条样本计算损失函数值，并求平均（受算力等因素影响，更为常见的做法是在一个 batch 上计算损失）
-
经验误差是期望误差的无偏估计。测试误差则是我们人为对期望误差做的一个近似，我们希望它能够较好地反映出期望误差
-
贝叶斯错误率：倘若我们知道样本是从哪个分布中采样得到的，就可以依据该分布，计算出样本对应的条件概率，并取其中的最大值作为样本的标签，即 \(h_{Bayes}(x) = \arg \max \mathbb{P} [y|x]\)。这就是所谓的贝叶斯决策准则
如果你认为自己设计的模型足够优秀，就可以尝试在某一已知分布上采样，并将得到的样本送入你的模型，比较最终计算结果与贝叶斯错误率之间的差异
很多人会觉得，我都知道目标分布了，这不相当于开卷考试吗？给定输入，我直接代入目标分布得到输出，正确率应该 \(100\%\) 啊，怎么还会有错？这是因为标签 \(y\) 往往是带噪音的，所以就算你利用真值函数去预测 \(y\)，也会存在错误。因此，贝叶斯错误率又称最优错误率
- 具体推导：假设在某一回归问题中，对于给定输入 \(x\)，我们利用 \(h_{\mathcal{D_n}}(x)\) 计算它所对应的输出 \(y\)
\(h_{\mathcal{D_n}}\) 就表示在数据集 \(\mathcal{D_n}\) 上训练得到的模型， \(\mathcal{D_n}\) 本身则是从分布 \(D\) 中随机采样得到的。对于不同的 \(\mathcal{D_n}\)，我们采样得到的数据集是不一样的。因此，\(h_{\mathcal{D_n}}(x)\) 是一个随机变量，可以对其求期望与方差
进一步，定义 \(Regression \quad function:\) \(f^{*}(x) = \mathbb{E}_y[y|x]\)，表示在已知样本的生成分布 \(D\) 时，对于给定的数据 \(x\)，输出值 \(y\) 的期望，这也是所有的回归任务希望逼近的目标（上标 \(*\) 就代表最优）
对于回归问题，我们可以采用 \(L2\) 作为损失函数
\[
\mathbb{E}_{D_n, y} \big [ \big(h_{D_n}(x) - y \big)^2 | x\big ] =
\mathbb{E}_{D_n, y} \big [ \big(h_{D_n}(x) - f^*(x) + f^*(x) - y \big)^2 | x\big ] \quad (1)
\\
= \mathbb{E}_{D_n, y}\big [\big(h_{D_n}(x) - f^*(x)\big)^2 + \big(f^*(x) -y\big)^2 + 2\big(h_{D_n}(x) - f^*(x)\big)\big(f^*(x) -y\big) |x \big ] \quad (2)
\\
= \mathbb{E}_{D_n} \big [\big(h_{D_n}(x) - f^*(x)\big)^2 |x\big] +
\mathbb{E}_{y}\big[(f^*(x) -y\big)^2|x \big ] +
2\mathbb{E}_{D_n, y}\big[\big(h_{D_n}(x) - f^*(x)\big)\big(f^*(x) -y\big)|x\big ] \quad(3)
\]
\[
2\mathbb{E}_{D_n, y}\big[\big(h_{D_n}(x) - f^*(x)\big)\big(f^*(x) - y\big)|x\big ] =
2\mathbb{E}_{D_n}\big[h_{D_n}(x) - f^*(x)|x\big ]\mathbb{E}_{y}\big[f^*(x) - y|x\big ]
\\
\because Regression \quad function: f^{*}(x) = \mathbb{E}_y[y|x]
\\
\therefore \mathbb{E}_{y}\big[f^*(x) - y|x\big ] = \mathbb{E}_{y}\big[f^*(x)|x\big ] - \mathbb{E}_{y}\big[y|x\big ] = 0\quad (4)
\\
(3) = \mathbb{E}_{D_n} \big [\big(h_{D_n}(x) - f^*(x)\big)^2 |x\big] +
\mathbb{E}_{y}\big[(f^*(x) -y\big)^2|x \big ]
\]
其中，\(\mathbb{E}_{ y}\big[(f^*(x) -y\big)^2|x \big ]\) 就是贝叶斯错误率的来源，即 \(y\) 中存在噪音。根据方差及 \(f^*(x)\) 的定义 ，该式也可写作 \(Var(y|x)\)
继续考察第一项 \(\mathbb{E}_{D_n} \big [\big(h_{D_n}(x) - f^*(x)\big)^2 |x\big]\)，我们采用相同的方法对其进行处理
\[
\mathbb{E}_{D_n} \big [\big(h_{D_n}(x) - f^*(x)\big)^2 |x\big]
\\
= \mathbb{E}_{D_n} \big [\big(h_{D_n}(x) - {E}_{D_n} \big [ h_{D_n}(x)\big ] + {E}_{D_n} \big [h_{D_n}(x) \big ]- f^*(x) \big)^2|x\big]
\\
= \mathbb{E}_{D_n} \big [\big(h_{D_n}(x) - {E}_{D_n} \big [ h_{D_n}(x)\big ]\big)^2|x\big ] +
\mathbb{E}_{D_n} \big [\big( {E}_{D_n} \big [h_{D_n}(x) \big ]- f^*(x) \big)^2|x\big ]
\\
+2\mathbb{E}_{D_n} \big [h_{D_n}(x) - {E}_{D_n} \big [ h_{D_n}(x)\big ]|x\big ]
\cdot
\mathbb{E}_{D_n} \big [ {E}_{D_n} \big [h_{D_n}(x) \big ]- f^*(x) |x\big ]
\quad (5)
\]
\[
\mathbb{E}_{D_n} \big [h_{D_n}(x) - {E}_{D_n} \big [ h_{D_n}(x)\big ]|x\big ] =
\mathbb{E}_{D_n} \big [h_{D_n}(x)|x \big]-\mathbb{E}_{D_n} \big [h_{D_n}(x)|x \big] = 0
\\
(5) = \mathbb{E}_{D_n} \big [\big(h_{D_n}(x) - {E}_{D_n} \big [ h_{D_n}(x)\big ]\big)^2|x\big ] +
\mathbb{E}_{D_n} \big [\big( {E}_{D_n} \big [h_{D_n}(x) \big ]- f^*(x) \big)^2|x\big ]
\]
其中，\(\mathbb{E}_{D_n} \big [\big(h_{D_n}(x) - {E}_{D_n} \big [ h_{D_n}(x)\big ]\big)^2|x\big ]\) 形式上就是方差的定义式，记作 \(Var_{D}[h_{D}(x)|x]\) （由于是对所有的 \(D_n\) 求期望，因此得到的就是 \(D\)）该式可以反映模型对分布 \(D\) 上的不同数据集的鲁棒性
\(\mathbb{E}_{D_n} \big [\big( {E}_{D_n} \big [h_{D_n}(x) \big ]- f^*(x) \big)^2|x\big ]\) 则是偏差平方，即从训练集学习到的 \(h_{D_n}\) 与真值函数 \(f^*\) 之间的差距
\[
\large \varepsilon_{L2}(x) = Var(y|x) + Bias\big[h_D(x)|x \big]^2 + Var_{D}\big[h_D(x)|x\big]
\]
反映在实际操作中：简单模型偏差大、方差小；复杂模型偏差小、方差大
- 上述推导是在回归问题下进行的，更为通用的概念是近似误差和估计误差
\[
giva\quad a \quad target\quad function\quad f,\quad for \quad any\quad h\in \mathcal{H}
\\
\large \varepsilon(h) - \varepsilon^*(f) = \big[\varepsilon(h) - \varepsilon(h^*)\big] + \big[\varepsilon(h^*) - \varepsilon^*(f)\big]
\]
第一项为估计误差、第二项为近似误差
选用简单的函数族：近似误差大、估计误差小
选用复杂的函数族：近似误差小、估计误差大
常用不等式
- \(Jensen\) 不等式：对于凸函数，函数值的期望 \(\geq\) 期望值的函数
\[
\text{if $f$ is convex},
\\
\text{then}\quad f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]
\]
\[
P(z \geq \epsilon) \leq \frac{\mathbb{E}[Z]}{\epsilon}
\]
切比雪夫不等式是一个典型的集中不等式
\[
P(\big|Z-\mathbb E[Z]\big| \geq \epsilon) \leq \frac{Var(Z)}{\epsilon^2}
\]
若 \(x_1, x_2,...,x_m\) 为 \(m\) 个独立随机变量，且满足 \(0 \leq x_i \leq 1\)，则对任意 \(\epsilon > 0\)，有
\[
\large P\big(\frac{1}{m}\sum_{i=1}^m x_i - \frac{1}{m}\sum_{i=1}^m \mathbb E(x_i) \geq \epsilon\big) \leq \exp(-2m\epsilon^2)
\\
\large P\big(\bigg|\frac{1}{m}\sum_{i=1}^m x_i - \frac{1}{m}\sum_{i=1}^m \mathbb E(x_i) \bigg| \geq \epsilon \big) \leq 2\exp(-2m\epsilon^2)
\]
另外一种常用形式：
\[
for\quad a_i \leq X_i \leq b_i
\\
P\bigg(\bigg|\sum_{i=1}^n \big(X_i - \mathbb EX_i \big) \bigg| \geq \epsilon \bigg) \leq 2 \exp \bigg[ - \frac{2\epsilon^2}{\sum_{i=1}^n (b_i - a_i)^2} \bigg]
\]
若 \(x_1, x_2,...,x_m\) 为 \(m\) 个独立随机变量，且对任意 \(1 \leq i \leq m\)，函数 \(f\) 满足
\[
\large \sup_{x_1, ..., x_m, x'_i} |f(x_1, ...,x_m) - f(x_1,...,x_{i-1},x'_i,x_{i+1},...,x_m)| \leq c_i
\]
则对任意 \(\epsilon > 0\) 有
\[
P\big(f(x_1,...,x_m) - \mathbb E(f(x_1,...,x_m))\geq \epsilon \big) \leq \exp(\frac{-2\epsilon^2}{\sum_{i=1}c_i^2})
\\
P\big(\big| f(x_1,...,x_m) - \mathbb E(f(x_1,...,x_m)) \big |\geq \epsilon \big) \leq 2\exp(\frac{-2\epsilon^2}{\sum_{i=1}c_i^2})
\]
有限假设空间泛化误差界
\[
P\bigg(\bigg|\sum_{i=1}^n \big(X_i - \mathbb EX_i \big) \bigg| \geq \epsilon \bigg) \leq 2 \exp \bigg[ - \frac{2\epsilon^2}{\sum_{i=1}^n (b_i - a_i)^2} \bigg]
\]
这里我们要求随机变量 \(X_i\) 是有界的，其下界为 \(a_i\)，上界为 \(b_i\)
- 在机器学习中，损失函数 \(\ell (h(x_i), y_i)\) 是我们关注的重点（期望误差就是样本损失函数的期望，经验误差就是有限条样本损失函数的均值）于是取 \(X_i = \ell (h(x_i), y_i)\) （这里的 \(x_i\)、\(y_i\) 是随机采样得到的，随机变量的函数仍旧是随机变量，因此可以代入 \(X\)）
\[
\sum_{i=1}^n \big(X_i - \mathbb EX_i \big)
\\
= n\bigg\{\bigg[\frac{1}{n}\sum_{i=1}^n \ell(h(x_i), y_i) \bigg]- \mathbb E_{(x,y)\sim D}\ell(h(x), y) \bigg\} \quad (*)
\\
= n\big(\hat{\varepsilon}_{D_n}(h) - \varepsilon (h) \big)
\]
\((*)\) 式通过提出 \(n\) 并引入 \(\frac{1}{n}\) ，构造出经验误差的表达式。将上述结果带回 \(Hoeffding\) 不等式，并假设使用 \(01\) 损失函数，即 \(1[h(x) \not = y]\)，则 \(a_i = 0, b_i = 1\)，于是有
\[
\large P\big( n \big| \hat{\varepsilon}_{D_n}(h) - \varepsilon (h)\big| \geq \epsilon \big) \leq 2 e^{-\frac{2\epsilon^2}{n}}
\]
上式的 \(n\) 有些多余，利用变量替换法，将 \(\epsilon\) 替换为 \(n\epsilon\)，完成消去
\[
\large P\big( n \big| \hat{\varepsilon}_{D_n}(h) - \varepsilon (h)\big| \geq n\epsilon \big) \leq 2 e^{-\frac{2\epsilon^2n^2}{n}}
\\
= \large P\big(\big| \hat{\varepsilon}_{D_n}(h) - \varepsilon (h)\big| \geq \epsilon \big) \leq 2 e^{-2n\epsilon^2}
\]
我们希望 \(\big| \hat{\varepsilon}_{D_n}(h) - \varepsilon (h)\big| \geq \epsilon\) 是一个小概率事件，如此就能保证我们在一个有限的数据集上训练得到的模型，其经验误差偏离期望误差较大的情况，发生可能性很小（简单理解：我们能在采样得到的数据集上训练出靠谱的模型）
\[
Let\quad \delta = P\big(\big| \hat{\varepsilon}_{D_n}(h) - \varepsilon (h)\big| \geq \epsilon \big)
\\
Then\quad \delta \leq 2 e^{-2n\epsilon^2} \Rightarrow \epsilon \leq \frac{\log \frac{2}{\delta}}{2n}
\]
因此，\(\varepsilon (h) \leq \hat{\varepsilon}_{D_n}(h) + \frac{\log \frac{2}{\delta}}{2n}\) 至少以 \(1 - \delta\) 的概率发生（其实就是 \(\big| \hat{\varepsilon}_{D_n}(h) - \varepsilon (h)\big| \leq \epsilon\) 至少以 \(1 - \delta\) 的概率发生，然后代入刚刚得到的不等式）
- 上述推导中，我们假设 \(h\) 是固定的，但在实际场景中，\(h\) 实则是一个随机变量，我们一般取 \(h\) 为
\[
\mathcal{D_n} \rightarrow h_{\mathcal{D_n}} = \arg \min_{h \in \mathcal{H} } \hat{\varepsilon}_{\mathcal{D_n}}(h)
\]
即在函数族 \(\mathcal{H}\) 中，选择于 \(\mathcal{D_n}\) 上经验误差最小的 \(h\)
- 这时，我们就应采用保守学习的思想，考虑最坏情况，获得一个相对松弛的上界 (uniform bound)
\[
P\big(\exists h \in \mathcal{H}, \big| \hat{\varepsilon}_{D_n}(h) - \varepsilon(h) \big | \geq \epsilon\big) = P\big(\sup_{h\in \mathcal{H}} \big| \hat\varepsilon_{D_n}(h) - \varepsilon(h) \big | \geq \epsilon \big|\big)\quad (1)
\\
= P\big(\big[\big| \hat{\varepsilon}_{D_n}(h_1) - \varepsilon(h_1) \big| \geq \epsilon \big] \vee ... \vee \big[\big| \hat{\varepsilon}_{D_n}(h_{\mathcal{|H|}}) - \varepsilon(h_{\mathcal{|H|}})\big| \geq \epsilon \big]\big) \quad (2)
\\
\leq \sum_{h \in \mathcal{H}} P\big(\big| \hat{\varepsilon}_{D_n}(h) - \varepsilon(h) \big | \geq \epsilon \big) \leq 2\mathcal{|H|} \exp(-2n\epsilon^2) \quad (3)
\]
\((1)\) 式是概率的一个性质，\(\sup\) 就是在考虑最差情况
\((2)\) 式是对 \(\exists\) 的展开，\((3)\) 式在其基础上，利用 union bound 性质，并使用 \(Hoeffding\) 不等式
\[
Let\quad \delta = \sum_{h \in \mathcal{H}} P\big(\big| \hat{\varepsilon}_{D_n}(h) - \varepsilon(h) \big | \geq \epsilon \big)
\\
Then\quad \delta \leq 2\mathcal{|H|} \exp(-2n\epsilon^2)
\\
\epsilon \leq \sqrt{\frac{\log \mathcal{|H|} + \log(\frac{2}{\delta})}{2n}}
\]
Let \(\mathcal{H}\) be a finite hypothesis space, \(\mathcal{H} < \infty,\) then for any \(\delta > 0,\) with probability at least \(1 - \delta\)
\[
\forall h \in \mathcal{H}， \varepsilon(h) \leq \hat\varepsilon_{D_n}(h) +
\sqrt{\frac{\log|\mathcal{H}| + \log \frac{2}{\delta}}{2n}}
\]
利用该式可以解释很多现象，例如为什么当样本数 \(n\) 增多后，模型效果会变好（右侧第二项减小，经验误差与期望误差之间的差距减小，说明模型的泛化性会更好）。以及关于模型容量的期望误差曲线为何是 U 形（当假设空间 \(\mathcal{H}\) 增大时，尽管模型的拟合能力更强，\(\hat\varepsilon_{D_n}(h)\) 更小， \(\sqrt{\frac{\log|\mathcal{H}| + \log \frac{2}{\delta}}{2n}}\) 却更大了，因此期望误差先减后增）
- 最后解释为何我们总是执着于计算期望误差与经验误差之间的差距 —— 因为两者的差距就代表了模型泛化能力的强弱。我们希望在自己有限的数据集上训练得到的模型，能够顺利得到应用，即便是面对它未曾接触过的输入，也可以给出正确合理的答案，这就是泛化
本站总访问量次