我们终于在上一篇文章中形式化的定义了学习问题，并给出了能够统一描述回归问题、最小二乘法、最大似然估计等方法的一般形式：ERM 原则。实践过 SGD 的我们可能非常熟悉，在 SGD 族的优化下，我们并非一次性使用全部的观测样本，而是使用一个小批量的数据样本甚至一个单一的数据样本来计算网络的损失函数，再利用反向传播和梯度下降来进行非凸优化，实际上这是一种随机逼近的方法，并早在上个世纪五十年代就已经被 Robbins 和 Monroe 提出了。

随机逼近原则

随机逼近原则并不是一种经验风险最小化的归纳原则。这一原则在独立同分布数据 $z_1, …, z_m$ 对参数 $\alpha$ 最小化泛函 $R(\alpha) = \int{Q(z, \alpha)dF(z)}$。其中参数 $\alpha$ 采用这样的迭代过程 $\alpha_{k+1} = \alpha_{k} - \gamma_k \text{grad}{\alpha}{Q(z_k, \alpha_k)}, k=1,2,…,m$。迭代的步数等于观测样本的数目。并且可以证明，**梯度 $\text{grad}{\alpha}{Q(z_k, \alpha_k)}$ 和 $\gamma_k$ 的取值在很一般的条件下，这种方法至少对于线性模型是一致的**[Robbins et al 1951]。

根据 Novikoff 关于感知器的收敛定理 [Novikoff, 1962]，Tsypkin 和 Aizerman 在讨论了学习过程一致性的问题，研究了能够保证学习过程一致性的两种一般性归纳原则，分别是随机逼近原则和经验风险最小化原则。这两种原则都被应用到经验数据并使风险泛函最小的一般问题上，最终发展处了两种不同的一般性学习理论：

1. 对随机逼近归纳推理的一般性渐进学习理论 [Aizerman et al 1965], [Tsypkin, 1971], [Tsypkin, 1973]；
2. 对 ERM 归纳推理的一般性非渐进模式识别理论，并且推广到任意基于经验数据的风险最小化问题 [Vapnik et al 1968], [Vapnik et al 1971], [Vapnik et al 1974], [Vapnik et al 1979]。

我们很容易看到，上面的的迭代步数等于观测样本步数似乎显得对数据的过度浪费，一个很自然的推广也就是现在我们非常常见的分多个时间段、多次使用训练数据。但进而产生的问题就是：什么时候必须停止训练过程？两个可能的条件：

1. 当训练数据中所有元素梯度值都非常小，以至于学习过程无法继续，停止训练过程
2. 当学习过程没有饱和，但达到了某种停止准则时，停止学习

很容易看到，在第一种情况下，随机逼近原则仅为经验风险最小化原则的一种特殊做法。但第二种情况则形成了期望风险最小化的一种正则方法（我们知道至少对于线性模型而言，early stopping 等价于 L2 norm 正则）。因此，在不浪费的情况下，随机逼近方法可以解释为 ERM 方法的归纳特征，也可以解释为正则化方法的归纳特征。

要完成关于传统归纳推理的讨论，需要考虑贝叶斯推理。贝叶斯推理要求额外的先验信息，包括带求函数在内的参数化函数集的补充。换句话说，我们必须知道一个分布函数，它描述了容许的集合中个函数是带求函数的概率。因此，贝叶斯推理强依赖于具有先验信息（带求函数属于学习机器的函数集合）。在这个意义下，这就不是一种一般性的推理方法了。

总的来说，除了 ERM 归纳原则之外，我们还可以采用其他归纳原则。但是 ERM 原则似乎更加健壮（它更好的利用经验数据、不依赖先验信息、存在清晰的实现方法）。

非正式个人评述

一致性尝试回答的问题是对一个使经验风险最小的学习过程，在什么时候能够取得相对较小的实际风险（产生泛化），而什么情况下是不能的。换句话说，学习理论的对于学习过程一致性的研究就是寻找使其发生的充分必要条件。大部分对学习理论不以为然的人会说：既然目标是寻找从有限样本中进行学习的算法，为什么要研究渐进理论？答案是：一致性是一种渐进概念，一致性的严密化保证了建立理论的一般性，并且证明了无法从这些基本概念上对其进行进一步改进。

本文未解释的问题：

• 如何证明随机逼近原则学习的的一致性？
• 对于非线性神经网络而言，early stopping 是否还具有正则的特性？
• 具有先验的贝叶斯推理为什么不是一种一般性的推理方法？

我们将在后面的文章中进一步讨论。

进一步阅读的参考文献

• [Robbins et al 1951] A stochastic approximation method
• [Novikoff, 1962] On convergence proofs on perceptrons
• [Aizerman et al 1965] Theoretical foundations of the potential function method in pattern recognition learning
• [Tsypkin, 1971] Adaptation and learning automatic systems
• [Tsypkin, 1973] Foundation of the theory of learning systems
• [Vapnik et al 1968] On the uniform convergence of relative frequencies of events to their probabilities (Russian)
• [Vapnik et al 1971] On the uniform convergence of relative frequencies of events to their probabilities (English)
• [Vapnik et al 1974] Theory of Pattern Recognition (in Russian)
• [Vapnik et al 1979] Theorie der Zeichenerkennung (in German)