Why Deep Structure

course link: https://speech.ee.ntu.edu.tw/~hylee/mlds/2018-spring.html

0. 引入

在神经网络的拟合过程中，有两种参数用于判断模型大小：

• Number of units
• Number of parameters

如下图所示，可以看出，更深的网络拟合的效果也就更好.

但是，并不一定更深的Network就会有更好的效果。因此，有了以下三个问题：

• Q1: Can Shallow network fit any function?
• Q2: How to use deep to fit functions?
• Q3: Is deep better than shallow?

问题情境：当有一个需要拟合的target function，shallow network的规模也会不断扩大使其能够满足拟合target function.

1. Universality

shallow network的普适性

假设给定一个 L-Lipschitz function $f^*$,需要多少神经元来拟合$f^*$？

L-Lipschitz function的定义如下:

||f(x_1)-f(x_2)|| ≤ L||x_1-x_2||

$L$是一个具体数值，其中$f(x_1)-f(x_2)$的数值会被L限制为$x_1-x_2$的L倍。如下图所示，当输入变化较快时，则不可能是1-Lipschitz；当输入变化比较平缓的时候才可能是1-Lipschitz。即，蓝色线不是，而绿色线可能是。

当给定一个网络，需要判断的是用于训练的function与target function之间的最大差值是否超过$\epsilon$，如果不超过，则是达到了拟合的结果.

所以，问题就变成，$K$要取多大，才能满足$max_{0≤x≤1}|f(x)-f^*(x)|≤\epsilon$. 这个问题同样也可以转换为积分计算:

在$N(K)$中所有的function都是piecewise linear，要通过一个piecewise linear function $f$ 来拟合$f*$.

首先，给定一个$f^*$，在上面取点，连线，观察error与$\epsilon$的情况，如下图所示:

其中，$error ≤ l \times L$，$l$表示两点间距离，$L$由L-Lipschitz决定.

input的变化要满足：$≤l$

output的变化要满足:$≤l\times L$

即最终需要满足：$l \times L ≤ \epsilon$，$l ≤ \epsilon / L$. 因此，区间的宽度可以直接取值为$\epsilon / L$.

如何使用一个单层的hidden layer来得到上述的绿色曲线？

通过relu产生不同的值，如下图所示:

将这些蓝色的function叠起来，就可以得到绿色的function.

这个过程可以看作，使用两个神经元，一个产生function 1，一个产生function 2，两个结果相加就可以得到所需的图像，结果如下图所示:

注: 图左上部分的2，是3，宏毅老师写错了(:з」∠)

2. Why we need deep?

shallow&wide 的网络产生的参数数量约等于 deep&narrow 的情况下，shallow network的pieces要比deep的pieces少.

注: 此处的wide可以理解为在x轴上的取值范围. 大范围取值得到的线段并不如多段小范围线段取值得到的拟合结果.

在shallow network中，每一个neuron只能生成一个linear piece. 其中的有一些部分会无法使用。

对于两个relu，可以生成一个取绝对值的激活函数.

每多增加一个relu，线段数就增加2倍:

对于shallow network，每增加一个neuron，就增加一条线段；但是，对于deep network，每增加一个neuron，就增加一次2的倍数的线段.

假如宽度是$K$，深度是$H$，可以有$K^H$个pieces.

3. Using deep structure to fit functions

Q: 如何使用piecewise function来fit一个$f(x)=x^2$？

定义$f_m(x)$,大小为$2^m$个pieces. 需要讨论的是，$m$要取到多少才能满足相应的条件？计算结果如图右所示.

$f_m$的生成过程即使用初始函数不停的减去各个三角形所表示的函数，使其不断逼近$f(x)$即可. 流程如下图所示:

在已知如何使用$x \rightarrow x^2$的情况下，基于这个原理，同样可以拟合$y=x_{1}x_{2}$.

同理，假如需要拟合$y^n$，只需要多次MultiplyNet即可.

==Deep vs Shallow==

deep和shallow存在指数上的差距，达到同样的acc，deep需要的参数比shallow少一个指数级.

4. Is deep better than shallow?

• 一个relu网络是一系列的linear function
• 使用最少的分段数来拟合target function

如下图所示，当linear function处于某种假定的梦幻状态时，其error会相较于连续状态时要小，判定函数也从原先的$max_{0≤x≤1}|f(x)-f^*(x)|≤\epsilon$转换为$\sqrt{\int_{0}^{1}|f(x)-f^*(x)|^2dx}≤\epsilon$，满足第二个式子未必满足第一个式子.

所以，问题由上述转化为一个积分计算式:

method: 让两个function之间的距离最小化.

同理，该问题也可以转化为线段划分问题，即，将$l$划分为多少段可以使得最终的$E^2$最小，答案是平均分配.

==Q: 为什么取平均分配可以得到最小值？==

霍尔德不等式(:з」∠)

基Hölder不等式的计算，可以得到再上一张图中的式子:

E^2=\sum_{i=1}^{n}\frac{(1/n)^2}{180}=\frac{1}{180}\frac{1}{n^4}

因此，计算继续，可以得到$E$的值.

可以看出，即使是shallow的方法处于梦幻状态，效果仍然不如deep.