从这篇文章开始，是我在UW学习高等统计推断课的第二学期的总结. 这个学期的课程中我收获最大的内容就是关于经验过程。这一工具对于有些理论问题，有时甚至有着降维打击的功效. 这我想要从比较高的观点上理解经验过程理论的相关内容，作为这学期期末考试的复习提纲.
我们首先以大数定律为例，对于独立同分布的变量 \(X_1,X_2,\cdots,X_n\) 在某些矩条件成立的时候有 \[ |\frac{1}{n}\sum_{i=1}^nX_i-\mathbb{E}X|=|(P_n-P)id|=o_p(1) \] 这里我们把随机变量 \(X\) 的期望 \(P(id)=\int xdP\) 看成了一个作用在某个函数 \(f=id\) , 依赖于分布\(P\) 的泛函. 相应的\(P_n(id)=\int id(x)dP_n=\frac{1}{n}\sum_{i=1}^nid(X_i)\). 实际上对任何一个固定的函数 \(f\) 在矩条件得到满足的时候，大数定律都可以告诉我们 \(|(P_n-P)f|=o_p(1)\) .
然而有时候，固定一个函数的收敛性结果是不够用的. 我们有时候会希望讨论在一族函数中的一致收敛性. 在这方面一个源头性的定理是Glivenko-Cantelli定理. 也即是说\(f(t)=1_{(-\infty,t]}(X)\) 的情况. 这个时候 \(P_nf,Pf\) 就是经验分布函数和一个分布的累积分布函数. GC定理告诉我们的是 \(\sup_t|(P_n-P)f|=o_p(1)\). 这相当于取了一个由 \(t\)作为指标的一个函数类. 这个结果是在这个函数类上的一致收敛.
我在这里写一个来自机器学习Empirical Risk Minimization框架的例子，来说明我们为什么会对函数类上的一致收敛感兴趣.
很多监督学习的算法目标是可以写成，在一个函数类中最小化某个损失函数的形式(暂时忽略正则项) \[ \mathcal{R}(f):=\min_{f\in\cal F} \mathbb{E}\ell(Y,f(X)),\quad (X,Y)\sim P \] 但是这个优化问题实际上是不可计算的，因为我们并不知道真实的分布\(P\)是什么. 所以现在训练实际考虑 \[ \mathcal{R}(f):=\min_{f\in\cal F} \mathbb{E}\ell(Y,f(X)),\quad (X,Y)\sim P \] 现在的问题是求解 \(\mathcal{R}_n(f)\)得到的解\(\widehat{f}\)如果和求\(\mathcal{R}(f)\)的最优解\(f^*\)不同的话，我们会有多大的损失呢？ \[ \begin{align} \mathcal{R}(\widehat{f})-\mathcal{R}(f^*)&\leq P(\ell(Y,\widehat{f}(X))-P(\ell(Y,f^*(X))-P_n(\ell(Y,\widehat{f}(X))+P_n(\ell(Y,f^*(X))\\ &\leq (P_n-P)(\ell(Y,f^*(X))-l(Y,\widehat{f}(X)))\\ &\leq |(P_n-P)\ell(Y,f^*(X))|+|(P_n-P)\ell(Y,f(X))|\\ &\leq 2\sup_{f\in\cal F}|(P_n-P)\ell(Y,f(X))| \end{align} \] 当然这个上界是非常粗糙的. 通过一系列更复杂的经验过程理论，我们可以对这个它进行更细致的控制. 如果我们希望这个界是可以随着样本量增加收敛到零的，那么经验过程的基础理论，作为在函数类上的一致收敛版本的大数定律，就可以对最后一项提供一个控制.
在这个过程中，函数类本身的性质对一致收敛是至关重要的. 例如，通常函数类越复杂，表达能力越强，那么这个一致的大数定律的上界可能就会越高. 有很多刻画的工具，例如VC dimension，Rademacher complexity，bracketing number, covering and packing number, 各种entropy等等. 在下一篇文章中，我们会回顾这些概念，并介绍如何通过它们来给泛化误差提供一个上界.