深度学习: 从理论到算法 (王力威教授)
My lecture note on 「Deep Learning: From Theory to Algorithm」
此文是关于第十八届中国机器学习及其应用研讨会中，王立威教授的讲座笔记。内容仅涉及我个人感兴趣的要点内容。
Table of Contents
王老师主要是机器学习的理论。王老师是从理论的角度来谈深度学习，并且在这个报告中提高了很多 insight 和启发。
深度学习存在的问题及其不足
Yann LeCun 曾谈到："深度学习最大的问题就是缺乏理论"。可见，深度学习现在还处在一个非常初步的一个状态。比如其中一个很典型的例子，就是经典机器学习模型都是 under-parametrization 的，然而深度神经网络确实 over-parametrization 的，即神经网络的参数个数是远远超过了训练数据的个数。在经典传统的机器学习看来，过参数化应该学不好的，应该用欠参数化的模型。但是现在深度神经网络还很好用，可见理论需要进步啊！
王老师在简述监督学习的时候谈到：
机器学习中最核心的一个假设就是：真实数据的分布是不可知的。
探索深度学习的三大角度
- 模型，网络的结构
- 优化，训练的过程（本讲重点）
- 泛化，测试的过程
关于模型
从理论的角度来对模型的表示能力进行探索的方法之一：函数逼近。
在 1989 年有一个很经典的结论，叫做 Universal Approximation Theorem：
一个只有单隐藏层的神经网络，可以在一个紧集上面任意的逼近一个连续函数。Shallow (but wide) networks are universal approximator
这说明即使是一个三层浅层神经网络，其表达能力已经很强大了。
不过这个结论只强调了无限宽的浅层网络，但是并没有对宽度有一个限制，于是王老师的另一个工作就做了相关的研究：
如果网络的宽度与数据的维数相比严格的大的话，那么就一定存在可以逼近任何连续可积函数的性质；反之，如果网络的宽度小于等于数据的维数的话，则一定存在大量的函数，使得网络即使再深也不可能逼近它们的。 Deep (and thin) ReLU networks are universal approximator (LPWHW, 2017)
可见，加深网络深度对网络的表示能力是有极大的好处，但前提是网络具备基本的宽度。
关于泛化
王老师谈到，虽然大部分深度学习的神经网络都是严重的过参数化的，但是其却没有发生 over-fitting，反而有着比较好的泛化能力。这一点对经典的机器学习理论是非常困惑的，甚至是矛盾的。
ICLR 2017 Best Paper：
王老师尤其推荐上面的一篇文献，值得大家去读一读。该文没有给出任何一个定理或者算法，但是该文是很有启发的。此文通篇都在进行实验，经过详细且深入的实验发现，经典的机器学习理论和我们今天深度学习所发生的现象是矛盾的。经典机器学习的泛化理论，是不能解释深度学习中所观察到的很多现象。可见，路漫漫兮。。。。
此后，老师讲了经典的机器学习泛化理论是怎样 fail 的，以及其他人为深度学习泛化理论所做的工作。让我印象深刻的有：
研究泛化还需要考虑其他影响，比如用的什么优化算法。如 Hardt et al. (ICML15) 里就谈到由于 SGD 算法是随机的，所以泛化才有了保证。反之，如果是用 GD，你会发现泛化能力会差很多。
王老师也在这个角度有一些工作，详情可以看 slides。
关于优化
为啥 SGD 在 highly non-convex 上优化的还挺好呢？即能找到全局最小化呢？
(DLLWZ, 2019)
王老师经过严格的理论证明，给出了如下结论：
只要深度神经网络的优化满足如下两个条件：
- 网络具有一定的宽度（足够的过参数化）
- 随机初始化的概率分布是一个高斯分布，其中的 variance 是精挑细选的。
那么从优化的初始点出发，用 GD (SGD) 这种一阶优化算法，是一定能够找到全局最优点。并且，走到全局最优点的速度是一个指数收敛速度（线性收敛速度）。
大概在同一时间里，有两个类似的工作提出了相近的结论：
Allen-Zhu et al. A convergence theory for deep learning via over-parameterization PDF
Zou et al. Stochastic gradient descent optimizes over-parameterized deep ReLU networks PDF
另外，王老师还提到一篇很有趣的文章：如果数学上假定网络的宽度是达到无限宽的极限时，此时的网络就会退化到一个经典的机器学习模型，即 kernel machine。
(NIPS2018)
小结
最后，王老师谈到上述的一系列工作背后，可以得到两个 insights：
- 当网络足够过参数化后，尽管网络的 loss landscape 是高度非凸优化的，但是其在初始化点附近的局部邻域里是有着极好的几何性质。换句话说，在初始化点的附近，虽然网络输出对于输入数据来讲是高度非线性的，但我们网络的输出对于网络的参数来讲，是一个近似线性的关系。因此，当你做一个 non-convex 优化的时候，初始点附近的邻域里面实际上是在做一个凸优化的问题；
- 由于充分过参数化，在初始点附近的小邻域里面还包含了一个全局最小点。