揭示函数类逼近误差与覆盖数的关系，解释神经网络为何能突破高维瓶颈。
A result relating convex n-widths to covering numbers with some applications to neural networks
- 通过凸核的覆盖数刻画函数类逼近难度
- 证明单隐层神经网络逼近率可达O(n^{-1/d})
- 为高维学习中的低维有效表示提供理论依据
在高维输入空间中，用固定基函数的线性组合近似函数类通常很困难，最佳基集的最坏情况误差衰减速度仅为Θ(n^{-1/d})，其中n是基函数数量，d是输入维度。然而，许多高维模式识别问题（如人脸识别）中，少量特征的线性组合即可取得良好效果，表明这些函数类不受一般情形下的“维度灾难”影响。因此，有必要寻找能被小规模特征集有效近似的高维函数类的表征。本文给出一个普遍结果，将函数类的逼近误差与其“凸核”的覆盖数相关联。对于单隐层神经网络，单个隐藏节点所计算函数类的覆盖数可上界其凸核的覆盖数。结合标准结论，我们得到了神经网络类逼近率的上界。
原文摘要 · Abstract (English)
In general, approximating classes of functions defined over high-dimensional input spaces by linear combinations of a fixed set of basis functions or ``features'' is known to be hard. Typically, the worst-case error of the best basis set decays only as fast as $Θ\(n^{-1/d}\)$, where $n$ is the number of basis functions and $d$ is the input dimension. However, there are many examples of high-dimensional pattern recognition problems (such as face recognition) where linear combinations of small sets of features do solve the problem well. Hence these function classes do not suffer from the ``curse of dimensionality'' associated with more general classes. It is natural then, to look for characterizations of high-dimensional function classes that nevertheless are approximated well by linear combinations of small sets of features. In this paper we give a general result relating the error of approximation of a function class to the covering number of its ``convex core''. For one-hidden-layer neural networks, covering numbers of the class of functions computed by a single hidden node upper bound the covering numbers of the convex core. Hence, using standard results we obtain upper bounds on the approximation rate of neural network classes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。