神经网络的万能逼近定理已经发展到什么地步了？ 第1页

简而言之, 自 Hornik 在 1991 年证明三层神经网络的表示能力比两层神经网络有优越性 (关于参数个数的 exponential separation) 之后, 过了将近三十年, 证明四层神经网络和三层神经网络之间的表示能力的 separation 仍然是 open problem.

2020 年 7 月补: 几周前 Gal Vardi 和 Ohad Shamir 证明了对某些类型的神经网络, 用 层的多项式规模网络需要任意大的 weight, 但是用 层的多项式规模网络只需要多项式大小的 weight:

看起来除了广为人知的三层比两层的网络有优越性的结果外, 此前最好的结果是多项式层的网络比常数层有优越性.

我从没做过 learning theory 但是上过两门课, 第二门大概就是体验被神经网络支配的恐惧吧 -- 其中一部分的讲的主要结果, 是 Amit Daniely 自己搞的三层神经网络的表示能力比两层有优越性的简化证明 (COLT 2017):

尽管 Hornik theorem 是 1991 年的工作, 但看起来似乎是经久不衰的 topic. 这定理大体是说存在一些函数 (满足某些分布), 用三层的神经网络来表示只需要多项式个参数, 但是用两层的神经网络来表示则需要指数个参数, 不同工作的细节 (比如说哪些函数关于哪些分布能做 separation, 证明本身用到了哪些技术) 上会有一些出入.

我试着胡扯几句证明相关的 -- 论文里说用了球面上的调和分析, 其实上课的时候的打开方式稍有不同. 机器学习里常见的一个东西叫做 reproducing kernel Hilbert space, 这里有关于 reproducing kernel function 的一一对应关系. RKHS 当然是个内积空间, 下面的打开方式就不太常见了 -- 有作用 (action) 的地方都可以找个群, 如果定义在集合 X 上的 reproducing kernel function 是关于有限交换群 G 保持不变的话, 那么可以证明对应的 RKHS 是 G 的群表示. 借助有限群的表示 (特征标理论), 我们还可以知道一些这个 RKHS 的结构, 做合适的 normalization 之后, 就可以看到这些 reproducing kernel functions 是正交多项式. 不同的集合 X 和群 G 对应不同的正交多项式, 比如说跟球面有关的球谐函数 (spherical harmonics). 在此基础上, 可以定义 random feature scheme (跟某个概率分布有关的内积空间), 然后就可以讨论具体函数和它的 random feature scheme 近似之间的关系, 在此基础上可以给出 Hornik theorem 的简化证明 (通过一系列不等式).

这课的最后一节给了一些 open problems, 多是一些听起来在技术上细枝末节的题目, 比如说如何做四层和三层的神经网络的 separation -- 是的, 过了将近三十年这玩意竟然还是 open problem......

作为脚注的是, 真不知道我当时是如何在完全看不懂的情况下写完作业的 (x