1、Can shallow network fit any function?

为什么我们需要深度学习呢？

所谓深度学习，就是用层数较多的神经网络进行学习，那么浅的神经网络有何问题呢？

首先我们要知道，讨论网络的深浅，实际上是在讨论网络架构的一个属性，网络架构包括神经网络的层数、各层神经元个数以及各神经元之间的连接情况。这里我们关注层数的多少。

而神经网络的架构直接决定了假设空间（或搜索空间），一组特定的权重则对应一个具体的函数，如上图所示。

下面，我们从一个基本的问题开始，Can shallow network fit any function? 关于这个问题，其实我们早知道通用近似定理，所以答案是 yes。而今天要做的事情是，直觉地理解一下，为什么一个浅的神经网络（比如只含一个 hidden layer）可以以任意精度逼近任意函数。

这里我们对函数的平滑性作出要求，即要求函数是 L-Lipschitz 函数，具体定义如上。下面我们证明，一个包含一个 hidden layer 且激活函数为 ReLU 的神经网络可以以任意精度逼近任何一个 L-Lipschitz 函数。

为了简化证明过程，假设输入 在区间 中。

如图所示，我们希望在 区间上得到的函数 和真实函数 差值绝对值的最大值不超过任意给定的 。

为了做到这一点，我们可以从 上选择一些点，然后把这些点依次连起来得到一个函数，稍后我们会看到，这样连线得到的函数一定可以由包含一个 hidden layer 且激活函数为 ReLU 的神经网络得到。

如图所示，我们考察选取的点中相邻的两个点，若它们形成的区间长度为，则对此区间上的任意两点，有。因此可以得到。而我们的是由此区间上两点连线得到的，因此的值介于和之间。因此在此区间上只需令，即即可。

于是我们可以在区间上按的间隔选取大约个点，然后把这些点一次连起来得到满足条件的。

接下来的问题是，这个真的可以由一个 hidden layer 且激活函数为 ReLU 的神经网络得到吗？

首先，很直观的，可以由几个“阶梯状”函数组成：

不难看出，三个“阶梯状”函数叠加起来再加上一个 bias，就可以得到。

下面我们说明：每个“阶梯状”函数都可以由两个 ReLU 函数得到。

上图就是一个很直观的例子，每个“阶梯状”函数都可以由两个 ReLU 函数做差得到。

因此我们就证明了一个包含一个 hidden layer 且激活函数为 ReLU 的神经网络可以以任意精度逼近任何一个 L-Lipschitz 函数。

具体来说，如果我们希望逼近精度为，则拟合的可以由个“阶梯状”函数累加得到，即可以通过个隐层的 ReLU 神经元得到。

2、Potential of deep

上面我们已经说明了浅的神经网络也具有非常强的拟合能力，那么我们为什么还需要深的神经网络呢？

接下来我们要展示，同样数量参数的网络，深的网络可以比浅的网络拟合更复杂的模型。换个角度来说，拟合同样的函数，相比浅的网络，深的网络可以用更少的参数达到相同的拟合效果。

首先，我们可以用两个 ReLU 函数得到绝对值函数。

然后我们将绝对值函数层层叠加，可以得到锯齿状的函数：

不难看出，两个 V 形的绝对值函数通过两层叠加可以形成一个 W 形的函数。

进一步的，每增加一层的绝对值函数，都可以使得 linear pieces 个数翻倍。

回顾 Shallow Network，每增加2个 ReLU 单元，只能增加1个 linear pieces。而 Deep Network 每增加2个 ReLU 单元，可以增加1倍的 linear pieces。

直观来看，Shallow 和 Deep 是线性和指数的差别。

由每层 2 个 ReLU 单元的情形可以推广到每层 K 个 ReLU 单元的情形。

下面我们看一个具体的例子，用 Shallow Network 和 Deep Network 来拟合。

上面就是 Shallow Network 拟合到精度所需的 ReLU 单元数量的计算过程。可以看到还是一个比较大的量级。

下面我们看一下用 Deep Network 如何拟合。

首先，我们把区间等分（这里以等分成 2 段举例），然后我们可以用如图所示的方法得到这两段 linear pieces 组成的。

具体来说，

也就是说，这个分 2 段的可以由函数与一个形的绝对值函数相减得到。

进一步的，分 4 段的拟合函数实际上可由减去一个 W 形的函数得到。这一点其实很直观，因为把 4 段分成前两段和后两段，则每一段都相当于时的情形，最终把两段的 V 形函数拼在一起就构成了 W 形函数。

之前我们说过，V 形的绝对值函数以及各锯齿状的函数均可由 ReLU 单元通过层层叠加得到。

因此我们通过 Deep Network 拟合到精度只需要个 ReLU 单元即可。

好，进行到这里，可能有人会问，为什么我们要考虑拟合 这个函数呢？换个函数会不会结果就不一样了呢？

原因在于，当我们可以拟合这个函数后，可以很容易地推广到所有的多项式函数，而 Weierstrass approximation theorem 则告诉我们任意连续函数在给定区间上都可以被多项式函数以任意精度逼近。

推广过程如下：

首先我们可以由三个 Square Net 得到 Multiply Net。

然后我们可以不断使用 Multiply Net 得到更高次的多项式。

如下图所示：

至此，我们就说明了 Deep Network 可以用较少的参数来完成复杂函数的拟合。那么我们能够说 Deep 比 Shallow 好吗？毕竟 Shallow Network 在拟合过程中用的参数比 Deep 多很多。答案是还不能，因为我们不能保证目前的 Shallow 拟合方案是最好的，即用参数最少的，说不定 Shallow 里最好的拟合方案所用的参数和 Deep 差不多呢？接下来我们来进一步说明 Deep 就是比 Shallow 要好的。

3、Is Deep better than Shallow?

为了找到最好的拟合方案，我们首先要定义什么是好的。

我们采用 Euclidean 的度量来衡量近似程度，且放宽必须是上点的连线的限制，求解出在长度为的区间上的最小误差如图。

接下来问题就变成了，如何合理划分一个个小区间，使得各区间上的误差之和最小呢？答案是等分。

得到了最小误差，我们就让这个最小误差满足精度要求，进而求出所需要划分的最少的区间数。

如图，Shallow 拟合最少所需的 ReLU 单元数就是。

综上，Deep 可以用更少的参数来达到和 Shallow 同样的拟合效果，而为了便于训练，毫无疑问我们应该采用 Deep Network 来拟合函数。