神经网络拟合能力1

2017-02-20

神经网络相关拟合能力的证明历史。

原创文章，转载请注明：转自Luozm's Blog

　　最近在学习神经网络模型，对神经网络的逼近性质非常感兴趣，顺手整理了证明过程的历史，供大家参考。如有理解不到位的地方请帮我指出，我会立即改正，谢谢。由于过程较长，全文大概分3次左右发出。

1. 问题的起源

　　Hilbert¹在1900年《数学问题》的著名讲演中提出了23个最重要的数学问题，其中第13个问题是：不可能用仅有两个变量的函数解一般的七次方程，即：

$$x^7+ax^3+bx^2+cx+1=0$$

方程的根 x（系数a，b，c的三元函数），不能被表示成二元代数函数（后改为连续函数）的有限和。

　　Kolmogorov²奠定了解决这个问题的基础，他证明任意多元连续函数均可用有限个三元连续实值函数来建构，即：令$E^n$表示$n$维单位立方体，$0\le x_i\le1(i=1,2,\dots,n)$。对于任意$n\ge3$存在$E^{n-1}$中的连续实值函数：

$$g_{11},g_{12},\dots,g_{1n};g_{21},g_{22},\dots,g_{2r}$$

使得任意定义在$E^n$中的多元连续函数$f$可以写成：

$$f(x_1,\dots,x_n)=\sum_{r=1}^nh_{fr}[x_n,g_{11}(x_1,\dots,x_{n-1}),g_{2r}(x_1,\dots,x_{n-1})]$$

其中$h_{fr}$给定并在$E^3$中连续。

　　接着，Kolmogorov的学生Arnold³证明了任意三元连续实值函数均可用有限个二元连续函数建构，即：任意$E^3$中的连续实值函数$f(x_1,x_2,x_3)$可以被表示成如下形式：

$$f(x_1,x_2,x_3)=\sum_{i=1}^3\sum_{j=1}^3h_{ij}[\varphi_{ij}(x_1,x_2),x_3]$$

其中$h_{ij}$和$\varphi_{ij}$是二元连续实值函数。Kolmogorov和Arnold的结果在一起证明了任意多元的连续函数可以表示为有限个二元连续函数的叠加，因此Hilbert在第13问题中的推测至少对于连续函数是不正确的。

　　此后不久，Kolmogorov⁴发现了新的结构，避免了使用功能树，并极大地改进了证明，提出了柯尔莫哥洛夫叠加定理（Kolmogorov Superposition Theorem，KST）：任意n元连续函数$f(x_1,\dots,x_n)$都可以用一元连续函数的叠加来表示。即：对于任意整数$n\ge2$,存在定义在区间$[0,1]$上的连续单调增实值函数$\psi^{pq}(x)(p=1,2,\dots,n;q=1,2,\dots,2n+1)$，使得$E^n$中的任意连续函数$f(x_1,\dots,x_n)$可以被写成：

$$f(x_1,\dots,x_n)=\sum_{q=0}^{2n}\chi_q(\sum_{p=1}^n\psi^{pq}(x_p))$$

其中$\chi_q(y)$也是连续实值函数。

参考文献