Lecture 1

Lecture 1

作者: 随心所欲_b1f7 | 来源:发表于2019-06-13 11:55 被阅读0次

Deep Learning Theory 1-1: Can shallow network fit any function?

目的: 证明一个单层网络，在神经元足够多的情况下，都能任意逼近到 $Lipschitz\ function$ .
$Lipschitz\ function$ 定义:

$||f_L(x_1)-f_L(x_2)|| < L||x_1-x_2||$

假设神经网络表示的函数空间为 $N(K)$ ，其中K为神经元的数量，那么我们希望:
$\forall \epsilon > 0, \ \exists \hat{f} \in N(K),\ have \ that \ \underset{0<x<1}{max} |\hat{f}(x) - f_L(x)| < \epsilon$
思路如下:

我们构造一个线段函数 $\hat{f}(x)$ 。构造方法如下：只需要将 $f_L(x)$ 均分为 $n$ 个点，每个点的距离为 $l$ ，且满足: $l \times L<\epsilon$ ，那么将这 $n$ 个点两两相连组成线段函数 $\hat{f}(x)$ ，那么这个 $\hat{f}(x)$ 就一定满足我们的条件。原因如图1所示（利用 $Lipschitz\ function$ 函数的性质）:

图1
线段函数 $\hat{f}(x)$ 能够被一系列的"山坡函数"表示，如图2所示；而每个"山坡函数"都能被2个relu神经元表示，如图3所示。那么结论就是，可以 $2\times n=2\times (x\ domain \ len /\frac{\epsilon}{L})$ 个神经元，来逼近 $Lipschitz\ function$ 。

图2

图3

Deep Learning Theory 1-2: Potential of Deep

目的：上一节只是表明，单层神经网络，只要神经元足够多的情况下，可以逼近任意 $Lipschitz\ function$ ,但并没有证明深度网络比浅层网络好，甚至没有涉及到deep network，现在我们来整这件事。
类比：对于逻辑电路门来说，两层的逻辑电路门能产生任何逻辑函数，但实际会用更深层次的逻辑门来实现。
从上一节我们知道，对于单层网络，每两个神经元可以产生一个线段，那么个神经元，可以产生n个线段(pieces)。那么对于更深层次的网络，我们其实可以用个神经元来产生个线段。思路如下(直观思路，但一点都不严谨):
1. 可以用两个神经元构造一个 $|wx+b|$ 绝对值函数，那么一个绝对值函数可以产生2个线段，如图4所示。
  图4
2. 不断叠加这样的绝对值函数(相当于增加神经网络的层数)，n层的神经网络就可以产生 $2^n$ 个线段，如图5所示。其实就是不断叠加复合函数啦，每个复合函数相当于一种模式，模式与模式相互嵌套(类似于雪花)。
  图5
3. 最终可以证明，宽度为 $K$ ，深度为 $H$ 的神经网络，最多可以产生 $K^H$ 个线段。参考论文如图6所示:

图6

最后一篇论文做了一些有趣的实验，实验显示前面几层的参数比后面层参数要重要得多(例如只train前面几层的参数)。
目前只直观说明了deep network可以得到更多的线段，但并没有说这些线段可以fit目标函数，也没有证明deep network比shadow network更好。仅仅只是能产生更多线段而已。那么下面来证明在同样神经元数目下，deep network可以确实比shallownetwork更能fit目标函数。
先考虑目标函数为： $f(x)=x^2$ ，之后再用这个函数为基础构建更general case。令 $f_m(x)$ 为线段函数， $m$ 表示该函数有 $m^2$ 个线段，那么可以证明，在 $\epsilon$ 误差限制下， $m$ 需要满足: $m\ge -\frac{1}{2}log_2\epsilon - 1$ (这个证明稍微有点复杂，但不难，把每个分段函数都用 $f_k(x)\ k = 1,2,..,m$ 表示出来，然后求每个线段与 $f(x)=x^2$ 在对于区间的最大差值，这个求导即可，然后每个区间的最大差值小于 $\epsilon即可$ )，如图7所示。那么对于shallow的情况，所需要的神经元为 $O(\frac{1}{\sqrt{\epsilon}})$

图7

$f_m(x)$ 实际可以通过一系列的锯齿函数来构造，如图8所示。

图8
每一个锯齿函数都可以通过增加一层layer来得到，正如之前(2)中所做的那要，结果如图9所示。构造 $f_m(x)$ 所需要的神经网络结构是 $m$ 层神经元，每层 $2$ 个神经元即可，那最终神经元个数为 $O(log_2\frac{1}{\sqrt{\epsilon}})$ ，层数为 $O(log_2\frac{1}{\sqrt{\epsilon}})$
图9
现在我们知道了，当 $f(x)=x^2$ ，在同样误差下深度网络所需要的神经元个数比比浅层网络要少。现在利用 $f(x)=x^2$ 构造 $polynomial$ 的情况，先构造一个 $multiply\ net$ 来生成 $x_1\times x_2$ ，再用它来生成 $x^n$ ，最终得到 $polynomial$ ，并且神经元个数为 $O(log_2\frac{1}{\sqrt{\epsilon}})$ ，如图10和图11所示。

图10

图11

注意，构造polynomial的神经网络与我们常见的神经网络不太一样，但目前不讨论这个，这个是optimization的问题。

Deep Learning Theory 1-3: Is Deep better than Shallow?

目的: 上一节可以看到，shallow network最坏情况下要用 $O(\frac{1}{\sqrt{\epsilon}})$ 个神经元来拟合 $f(x)=x^2$ ，那最好情况下是不是也能和deep network一样或者更好呢？我们来看看。
思路: 不断放宽对shallow network的限制，用放缩法得到一个，最终会发现这个:
1. 先放宽 $\hat{f}_k(x)$ ，不用其端点刚好在 $f(x)=x^2$ 上,这样的error会更小，虽然函数是不连续的。
2. 再放宽 $error$ 限制，原来的error限制在 $\underset{0\le x \le 1 }{max }|f(x)-f^*(x)|\le \epsilon$ ，即对某一点的最大差值；现在将其放宽，变为: $\sqrt{\int_{0}^{1}|f(x)-f^*(x)^2|dx} \le \epsilon$ ，改为差值的面积。
  以上两点可以由图12所示:
  图12

令 $e^2=\int_{x_0}^{x_0+l}(x^2-(ax+b))^2dx$ ，我们想找到 $a,b$ 使得 $e^2$ 最小。对其求积分，然后对 $a,b$ 求 $e^2$ 的最优解，这个就是对多元函数求拉格朗日极值了(或者用另一种思路，用向量空间的思想，视频中有说，但我不知道如何求解)，最终可以得到 $e^2=\frac{l^5}{180}$ 。
以上是对某一个线段与 $f(x)=x^2$ 的差值求最小值，那么合起来就是对 $E^2=\sum_{i=1}^{n}(e_i)^2=\sum_{i=1}^n{\frac{(l_i)^5}{180}}$ 求最小值，当 $l_i=\frac{1}{n}$ 时， $E^2=\frac{1}{180}\frac{1}{n^4}$ 为最小值。证明过程如图13（但没有证明为什么是 $l_i=\frac{1}{n}$ 时取最小值）:

图13
目前我们得到 $E=\sqrt{\frac{1}{180}}\frac{1}{n}<\epsilon$ ，至少需要满足 $n\ge \sqrt{\frac{1}{180}}\frac{1}{\epsilon}$ 。所以我们得到shallow network的 $lower\ bound=O(log_2\frac{1}{\sqrt \epsilon})$ ，从而得到了 $shallow\ network$ 确实不如 $deep\ network$ 的结论。
以上所有都是异常简化版，直观版的解释，真正的理论要去看论文（视频中有）。

相关文章

网友评论

本文标题：Lecture 1

本文链接：https://www.haomeiwen.com/subject/nwytfctx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

热点阅读

关于我们|服务条款|联系我们|Lecture 1|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！