前言
ICLR 2017 的 Best Paper [Zhang et al. 2017] 的作者张驰远做出了相当强的批判，指出机器学习中泛化理论并不能一致的迁移到深度学习中。论文首先通过 Randomization Test 过强的 empirical claim 认为深度学习的模型之所以能够起作用是因为其粗暴的记住了全部的样本，并非真正达到了泛化。但这一结论事实上犯了推理的逻辑错误 [Kawaguchi et al. 2017]。
然而，论文中关于正则化理论的评注「explicit regularization is unneccesary」和「SGD has implicit regularization property」却似乎显得很有分量。确实，我们在实际的调参过程中应该有注意到我们常说的「overfitting」现象并不总会在深度学习模型中表现，我们经常观察到 generalization gap 随着训练时间的增加，会短暂的上升并进而继续降低或者保持不变，并不符合我们理论上对 overfitting 的理解。就这一点问题，我围绕着 overfitting 的定义以及 regularization 提出的始末进行了相关研究，发现机器学习理论基础并没有想象中的那么简单。
于是，我准备新开一个系列，来整理我阅读相关论文的心得以及个人思考。从统计学的基本原理出发，理解统计学习理论的本质。这个系列的名字叫做《理解现代统计学习理论（Understanding Modern Statistical Learning Theory）》，为了方便起见，我们缩写为 UMSLT。
阅读本系列要求读者具有较高水平的机器学习实践经验，同时对形式化数学理论有较强功底，例如对 Banach 空间观点下的概率理论有相当了解，对参数统计学相关知识非常熟悉，对其他通用领域的数学知识也有一定程度的了解。
若读者在阅读本系列的过程中发现有原则性的错误，请务必指出，谢谢。
第一个学习机器
上个世纪六十年代，F. Rosenblatt 提出了学习问题中的第一个模型（当然，人工神经元并不是他提出的，这是另一个故事了），也就是我们目前所熟知的感知器（Perceptron）。感知器的模型在现在看来相当简单，其中的神经元具有 n 个输入，最后通过一个 bias 和符号函数来输出其分类目标。从几何直观来看，感知器其实相当于定义了输入空间中取值为 -1 和 1 的两个区域，他们被分段函数分开。但是，模型提出的时候并没有我们现在所熟知的反向传播算法来统一对神经元的参数进行最优更新。人们对于感知器的理解也就仅仅局限于通过适当的参数选择，是可以把输入空间变换到一个新的空间，同时在新空间能够对输入数据进行线性分类。
那时候的学习算法也相当简陋，神经元权重的更新规则依次遍历并循环全部样本，依靠感知器输出层前一层输出值 h 与真实值 y 之间的乘积进行（$w = w + yh$，如果下一个样本分类错误，即 $yh<0$）。后来 Novikoff 证明了 [Novikoff, 1962] 在这种更新规则下， h 的范数存在某个常数上界 R，同时训练数据能够以间隔 $\rho$ 分开，并且感知器在最多 $[\frac{R^2}{\rho^2}]$ 次训练后停止。这个结论本质上是在告诉我们，模型的泛化能力来源于最小化训练集上的错误数，因为通过最小化训练集上的错误数能够保证感知器在多次训练后停止。
因此，当时的学界认为模型的泛化能力来源就是 Empirical Risk Minimization （虽然这时还没有 ERM 这个名词），从这以后对于模型学习过程的研究分割成了两个分支，其中一个是对学习过程的应用分析，另一个就是学习过程的理论分析。
应用分析学派的基本观点是：最优泛化能力取决于选择使训练错误数最小的神经元权重。并且训练过程中最小化训练误差是一个不证自明的归纳原则，从实用性的角度来说证明显得苍白无力。这也是目前深度学习领域大部分人的观点：我们应该把精力放在寻找能够同时构造全部神经元系数的方法，使训练分类误差最小。
但理论分析学派则认为：训练误差最小化并不是不证自明的，而且很有可能还存在其他归纳原理。
ill-posed 与 well-posed 问题
数学上的 ill-posed 是相对于 well-posed 的概念。一个 well-posed 的问题通常有这样三个性质：解存在、解唯一、解的行为随初始条件连续变化（请注意与病态问题的区别）。
早在二十世纪初， Hadamard 就观察到 [Hadamard. 1902] 在很一般的情况下，求解线性算子方程 $$Af = F, f \in \mathbb{F}$$ 是 ill-posed 的。使方程存在唯一解 $f^*$，如果将 $F$ 替换为 $F_\delta$ $||F-F_\delta||<\delta$，可能导致 $$||f_\delta - f||$$ 很大。
换句话说，在学习理论中，如果我们在学习过程中的 F 都是不确定的，那么在算法的加持下，方程的右侧变成了一个和 F 很接近的 $F_\delta$，即 $||F_\delta - F||$的范数（距离）可以任意小，最终得到的 $f_\delta$ 会和原来的解相差很大。因此，使得泛函 $R(f) = ||Af - F_\delta||^2$ 最小化的函数 $f_\delta$ 无法保证 $\delta$ 在趋近于 0 时收敛到真实解的一个近似解。再简单的说，只有当我们求解的问题是 well-posed 的，我们才有机会使用稳定算法（数值稳定性）在计算机上求解。
早些时候 Hadamard 以为这种 ill-posed 问题只是一个纯数学现象（就好像分析学中一些病态得只有勒贝格可积的函数在现实世界中一般不存在）。但是半个世纪过后，人们才意识到，现实生活中很多实际问题都是 ill-posed。学习理论中所希望的因果反演（从现象推测因果）就是很典型的 ill-posed 问题哪怕是因果关系形成了一一映射，它的反演问题仍然是 ill-posed 的。对于机器学习而言，这似乎是致命的，因为根据观测数据估计分布这个问题是 ill-posed 的。
直到上个世纪六十年代中期，人们 [Ivanov, 1962]、[Phillips, 1962]、[Tikhonov, 1963] 证明了如果对最小化泛函做适当修改，为其增加一个正则项，即最小化 $R^*(f) = ||Af-F_\delta||^2 + \gamma(\delta)\Omega(f)$，其中 $\Omega(f)$是否中泛函，$\gamma(\delta)$ 是某个适当的常数（依赖于噪声水平），那么就能够得到一个解序列，使得在 $\delta$ 趋向于 0 时收敛于我们希望最小化泛函 $R(f)$ 所得的解（注意，这个证明仅对线性问题成立）。
至此，我们大致了解到了正则化理论提出的始末，从感知器的诞生，到经验风险最小化产生的 ill-posed 问题，正则化理论扮演了消除经验风险最小化问题的一个很重要的角色，从某种意义上来说，正则化理论似乎表明了因果反演是可行的，这在一定程度上为建立严格的学习理论夯实了基础。
非正式个人评注
正则化理论是我们再熟悉不过的方法了，我们在机器学习理论课中，正则化方法通常以解决模型的过拟合问题来引进，在 [Goodfellow 2016] 中，其将正则化方法在深度学习中描述为：正则化是指通过修改学习算法，使其降低泛化误差。而在 [Zhang et al 2017] 中，正则化更被粗暴的描述为：正则化是任何一种能够损害训练过程的技术。No-free-lunch 定理证明了不存在最好的学习算法，我们可以类似的给出：没有最好的正则化方法。
通过回顾正则化理论的提出历史，我们可以看出，正则化理论想要解决的问题与学习理论中的「过拟合」似乎并不存在直接联系，正则化理论只希望保证在最小化泛函过程中，能够收敛到我们希望的唯一解。但「过拟合」则是在考虑当随着训练的进行模型过度适应训练数据而不能解释测试数据。换句话说，如果没有正则项，我们在训练过程中使得 $R(f)$ 变小的 f 不能明确的收敛到唯一解，但同时又能保证 $R(f)$ 在逐渐减少。随着正则项的出现，训练过程中使得 $R(f)$ 变小的 f 能够收敛到使得 $R(f)$ 最小的唯一解。
在深度学习，我们总是在使用参数量大于样本量的模型来进行训练，这时，模型的空间巨大，我们挑选到正确模型的机会就会小得多，随着正则化理论的提出，解空间受到了限制，减少了我们选择不正确模型的可能性，进而防止了过拟合的产生。那么问题来了：正则化究竟是怎么限制解空间的呢？
本文未解释的部分：
- 为什么因果反演是一个 ill-posed 问题？
- 正则化项能够保证非线性模型的 ERM 吗？
- 正则化究竟是如何限制解空间的呢？
- 正则化对解空间限制「强度」有多大？
- 模型的解空间和模型复杂度（Model Complexity）是一回事吗？
- 学习算法是否自身具备正则化的属性呢？
- 使得风险泛函最小的唯一解在非线性多层网络中是泛化最优的吗？
我们在随后的系列文章中在继续对这些问题进行讨论。
进一步阅读的参考文献
- [ Zhang et al. 2017 ] Understanding deep learning requires rethinking generalization
- [ Kawaguchi et al. 2017 ] Generalization in Deep Learning
- [ Novikoff, 1962 ] On convergence proofs on perceptrons
- [ Hadamard. 1902 ] Sur les problèmes aux dérivées partielles et leur signification physique
- [ Ivanov, 1962 ] On linear problems which are not well-posed
- [ Phillips, 1962 ] A technique for numerical solution of certain integral equation of the first kind
- [ Tikhonov, 1963 ] On solving ill-posed problem and method of regularization
- [ Goodfellow. 2016 ] Deep Learning