#172 什么是泛函空间的大数定律?它是机器学习理论的里程碑吗?

欧长坤初次发表于『知乎』, 转载请注明出处。

这个问题问得很深刻,人们花了很长的时间才领悟到这个问题的答案,所以解释起来有点费力。我这里尝试性地做一个解释。 首先,我们需要搞明白三件事情:什么是一个学习问题、什么是风险最小化、什么是经验风险最小化归纳原则。

什么是学习问题?

对于一个学习问题而言,给定了训练样本\((x_1,y_1),(x_2,y_2), ... , (x_l,y_l)\),而训练的样本是根据联合分布\(F(x,y)=F(x)F(y|x)\)抽取的l个独立同分布的观测。学习问题就是从给定的函数集\(f(x,\alpha),\alpha \in \Lambda\)中选出能够最好地逼近训练样本的函数,换句话说,就是用最优函数估计样本背后蕴含的统计规律——用\(f(x,\alpha)\)估计\(y\)。 注意,\(\Lambda\)是参数集合,参数\(\alpha\in\Lambda\)并不一定必须是向量,可以是任意多抽象参数。

什么是风险最小化?

风险最小化是用损失函数\(L(y,f(x,\alpha))\)表示输入的真实响应\(y\)与预测\(f(x,\alpha)\)之间的差异,它的期望又被叫做风险泛函:

\[ \begin{equation} R(\alpha)=\int_{}^{} L(y,f(x,\alpha))dF(x,y), \alpha \in \Lambda \end{equation} \]

由于我们的概率测度\(F(x,y)\)未知,所有可用的信息都来自训练样本。 所以学习,又可以说成是在经验数据(训练样本)的基础上,最小化风险泛函。

什么是经验风险最小化归纳原则?

显然,我们并不知道概率测度,所以风险泛函并不能直接的计算和最小化。 根据大数定理,人们就很自然的想到用算术平均来代替风险泛函,从而又定义了经验风险泛函

\[ \begin{equation} R_{emp}(\alpha)=\frac{1}{l}\sum_{i=1}^{l}{L(y_i,f(x_i,\alpha))} \end{equation} \]

,用使得经验风险最小的函数\(f(x,\alpha)\)逼近使得风险泛函最小的函数\(f(x,\alpha_0)\)。 这个原则就被称作经验风险最小化(之后我们简称ERM)归纳原则。 对于一个归纳原则,如果任何给定的观测数据,学习机器都依照这一原则来选择逼近,则我们就可以说这个归纳原则定义了一个学习过程。 那么关键问题来了:

为什么需要推广大数定律?

传统的概率统计,包括大数定律,研究的都是渐近理论,换句话说就是当样本数趋向于无穷大时的极限特性。同样的,传统的模式识别几乎所有的方法都是建立在大数定律基础之上。但是,一个显然的条件是,对于任何一个实际问题来说,训练样本的数量,只能是有限的。这里就隐含了一个命题:在样本趋于无穷这个假设下得到的结论,当样本数有限的时候,任然是有效的,或者,至少是一种不错的近似。 一个很自然的想法,就是利用有限样本估计分布,从而得到样本空间的分布规律,这就是传统模式识别的基本出发点。这种在分布已知或在估计分布的基础上进行推断的方式,属于演绎推理。比如Bayes决策,是基于样本的概率分布,可以获得最优结果,保证期望风险最小。 实际上,样本空间的分布规律如果已知的话,所有的学习问题在理论上都可以迎刃而解了。 所以,这时候人们发展了很多密度估计的方法,比如最大似然估计、最邻近估计等等,这些对概率分布都是很好的估计方法,是一种很不错的近似。然而,强的结果需要强的已知条件,Bayes方法、最大似然估计等都需要非常强的先验知识,在实际问题当中,这是很难满足的。 而核密度估计等非参数方法,需要的观测数目又得足够多,才能保证得到对以来关系较好的逼近,当样本数量有限时,非参数方法的渐近特性也不再成立。 基于大数定律,先估计密度,然后用估计的密度来构造待求得函数,这种策略在利用有限样本解决问题时,存在缺陷,传统的模式识别里面,发展了很多的方法去“直接”寻找待求得函数(比如LDA、NN等)。这种在分布未知并不在估计分布的基础上进行推断的方式属于归纳推理。 通用的方法,都是是建立某一标准判据函数,执行梯度下降(现在的部分Deep Learning有用的是Hinton在这个世纪提出的CD算法),达到判据最优值。 选取不同的判据函数,对于计算和收敛性就会出现不同的优劣,但都是执行相同的归纳原则——随机逼近原则。这类算法的迭代停止标准,都是当学习过程达到饱和,即对训练数据中所有元素梯度值都非常小,以至于学习过程无法继续。 然而,这些的这些,基本思想是都是用ERM代替实际中无法实现的风险泛函最小化。所以,其隐含的命题是,学习过程的一致性是显然的!也就是说,概率论中的大数定律显然能够推出:对于以给定函数序列\(Q(z,\alpha),l=1,2,...\)(其中\(z\)代表数据对\((x,y)\)),ERM收敛到最小可能的风险泛函。这一命题似乎符合人们的直观认识,但是却很长时间里没有被人们注意到,这是没有被证明的。 所以,实际上传统的模式识别的统计基础,实际上是有两个硬伤的: (1)并没有对ERM原则下统计学习的一致性进行分析,不能保证:经验风险的下确界能够概率收敛到风险泛函的下确界。 (2)大数定理能够保证算法的渐进性,但是只考虑了渐近性,解决样本有限的问题时,描述的仅仅只是一个极限过程,并没有对收敛速度进行分析,并不一定能够得到好的近似。 那么人们就迫切的需要解决这么几个问题:

  1. ERM原则成立的条件是什么;
  2. 学习过程收敛速度的界;
  3. 小样本如何进行归纳推理;
  4. 如何控制学习过程的推广能力;

对这些问题的研究,一共构成了学习理论的四个核心部分:

  1. 学习过程的一致性。
  2. 学习过程收敛速度的非渐近。
  3. 控制学习过程的推广能力。
  4. 构造学习算法。

关于泛函空间的大数定律,就包含在第一个部分当中,学习过程的一致性,注意,这就是当下所有统计学习理论的基础,所以说它是里程碑,不是泛泛而谈。

那么,如何保证学习过程的一致性?

只有当满足一致性条件,才能保证在ERM原则下得到的最优方法当样本无穷大时趋于使得风险泛函的最优结果,只有满足一致性条件,才能说明我们的学习方法是有效的。 在看一个关键性的定理之前,我们需要确切的描述到底什么才是一致: 对于损失函数集\(Q(z,\alpha),\alpha\in\Lambda\)的任意非空子集

\[ \begin{equation} \Lambda(c)=\{\alpha|\int_{}^{}Q(z,\alpha)dF(Z)>c,\alpha\in\Lambda \},c\in(-\infty,\infty) \end{equation} \]

都有

\[ \begin{equation} \inf_{\alpha\in\Lambda(c)}R_{emp}(\alpha) \xrightarrow{P} \inf_{\alpha\in\Lambda(c)}R(\alpha),(l\rightarrow\infty) \end{equation} \]

成立,我们就说ERM方法对函数集\(Q(z,\alpha),\alpha\in\Lambda\)和概率分布函数\(F(z)\)是一致的。 那么对于这个定理:

设函数集\[Q(z,\alpha ),\alpha \in \Lambda\]满足条件

\[ \begin{equation} A\leq \int_{}^{}Q(z,\alpha ) dF(z)\leq B(A\leq R(\alpha)\leq B), \end{equation} \]

那么EMR原则一致性的充分必要条件是:经验风险\(R_{emp}(\alpha)\)在函数集$Q(z,)\(上以如下意义一致收敛于期望风险\)R( )$:

\[ \begin{equation} \lim_{l\rightarrow\infty}P \{ \sup_{\alpha\in\Lambda}(R(\alpha)-R_{emp}(\alpha))>\epsilon \}=0,\forall \epsilon>0 \end{equation} \]

所达到的效果,就是把ERM方法的一致性问题转化为一个一致收敛的问题。 因此,如果函数集$Q( z,) , \(中只包含一个元素,由统计学中的大数定律可以立刻得到上述定理的成立。若函数集中包含有限个\)Q(z,),\(中包含有限数目\)N\(个元素,统计学中的大数定律,仍然可以证明出上面的定理。 可惜是,当函数集\)Q(z,),\(中存在无限多个元素时,统计学的大数定律就失效了,无法得到上面的定理。 **所以我们这才迫切的需要泛函空间的大数定律(在函数\)Q(z,),$的空间)。**

至于为什么,我想这个答案的篇幅有点长了,简短的篇幅不足以解释这些,如果题主感兴趣,可以参考最后给出的参考文献[1]。 综上所述,统计学习理论的统计基础(里程碑)是泛函空间的大数定律(在函数\(Q(z,\alpha),\alpha\in\Lambda\)的空间),而不是传统概率统计的大数定律(在样本空间中)。

进一步阅读的参考文献

[1] Vladimir N. Vapnik著. 统计学习理论的本质.

打赏催更