证明三类布尔函数复杂度定义等价，为神经网络提供理论支持
Holographic functions and neural networks
- 用随机采样恢复函数值来定义全息性质
- 三类复杂度定义在参数变化下等价
- 适用于研究神经网络与布尔函数的理论联系
模糊布尔函数是映射 $f: \cube^n \to [0,1]$，其中 $n\in\mathbb N$。我们引入并比较三种界定此类函数复杂度的方式：第一种是采样性质——函数值 $f(x)$ 可通过少量随机选择的坐标值以高概率和小误差恢复，称为全息性质；第二种是结构性质——$f$ 在有限个有界线性坐标形式上的低次多项式附近均匀接近；第三种是计算性质——$f$ 可被具有有界非输入神经元数、有界Lipschitz激活函数及有界输入权重的神经网络近似。我们证明这三种性质在参数数量级变化下等价。从全息性到多项式结构的推导依赖于超图正则性的一个弱版本变体。
原文摘要 · Abstract (English)
A fuzzy Boolean function is a map $f:\cube^n\to [0,1]$, where $n\in\mathbb N$. We introduce and compare three ways of saying that such a function has bounded complexity. The first is a sampling property: the value $f(x)$ can be recovered, up to small error and with high probability, from the values of a bounded number of randomly chosen coordinates of $x$. We call this the holographic property. The second is a structural property: $f$ is uniformly close to a bounded-degree polynomial in boundedly many bounded linear coordinate forms. The third is computational: $f$ is uniformly close to the output of a neural network with a bounded number of non-input neurons, bounded Lipschitz activation functions and bounded incoming weights. We prove that these three properties are equivalent up to quantitative changes of the parameters. The implication from holography to polynomial structure uses a variant of a weak version of hypergraph regularity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。