Expressivity of Shallow Neural Networks Over Finite Fields

技术摘要：有限域上浅层神经网络的表达能力

问题陈述
本研究调查了在有限域 $\mathbb{F}_q$ 上，采用单项式激活函数 $\sigma(x) = x^r$ 的浅层多项式神经网络（PNN）的表达能力。虽然神经网络的表达能力传统上是通过统计方法或在实/复数域上进行研究，但本文在有限域的背景下探讨了代数表达能力。这一研究动机源于权重量化带来的实际优势（降低能耗和存储），以及计数有限域上有理点与韦伊猜想（Weil conjectures）之间的理论联系，后者与复变体的动机结构（motivic structure）相关。

核心问题在于量化一种网络架构的“算术表达容量”。与通过维度或扎里斯基稠密性（Zariski density）来衡量连续域表达能力的传统方法不同，作者通过“神经流形”（neuromanifold）的基数来定义有限域上的表达能力——即从网络权重到可表示多项式空间的参数映射的像。

方法论
作者采用代数几何方法，将网络输出视为多项式环中的元素而非仅仅是函数。

1. 形式化： 一个架构为 $\mathbf{d}=(n, m, k)$ 且激活度为 $r$ 的浅层网络，将输入 $\mathbf{x} \in \mathbb{F}_q^n$ 映射到输出空间 $(\mathbb{F}_q[x_1, \dots, x_n])^k$。其输出是一个 $r$ 次齐次多项式的 $k$ 元组。
2. 神经流形定义： 神经流形 $\mathcal{P}_{\mathbf{d}, r}$ 被定义为参数映射 $\Psi_{\mathbf{d}, r}$ 的像，该映射从权重空间 $\mathbb{F}_q^{m(n+k)}$ 到齐次多项式空间乘积 $(S_r(\mathbb{F}_q^n))^k$。
3. 计数策略： 由于环境空间是有限的，表达能力通过基数 $|\mathcal{P}_{\mathbf{d}, r}|$ 来衡量。作者利用了：
   • 多项式同余定理： 用于确定哪些单项式系数在模场特征 $p$ 时消失。
   • 张量分解： 将网络输出与对称张量分解（特别是 CP-秩和同时对角化）联系起来。
   • 组合计数： 使用关于有限域上给定秩的矩阵数量的公式（MacWilliams, 1969）以及 $q$-二项式系数。
   • 射影几何： 通过分析射影空间中的神经流形结构来处理缩放不变性。

主要贡献与结果

1. 一般上界
论文根据激活度 $r$ 的基于 $p$ 的展开式，建立了神经流形基数的通用上界。若 $r = \sum r_t p^t$，则非零单项式系数的数量为 $\gamma_{n,p}(r) = \prod \binom{r_t+n-1}{r_t}$。因此，基数被限制在：
$$|\mathcal{P}_{\mathbf{d}, r}| \leq q^{\gamma_{n,p}(r) \cdot k}$$
该界限的产生是因为多项式系数在模 $p$ 时对于某些指数元组会消失，从而降低了可表示空间的有效维度。

2. 特定架构的精确基数
作者推导出了几种架构的精确公式：

• 单输出（$k=1$）与平方激活（$r=2, p \neq 2$）： 神经流形对应于秩 $\leq m$ 的 $n \times n$ 对称矩阵集合。其基数是秩为 $j$（其中 $0 \leq j \leq m$）的对称矩阵数量之和，利用了 MacWilliams 公式。
• 多输出（$k>1$）与 $r=2$： 作者分析了架构 $\mathbf{d}=(n, n, 2)$。他们展示了有限域与复数域之间的鲜明对比。在 $\mathbb{C}$ 上，神经流形是扎里斯基稠密的（填满了整个空间）；而在 $\mathbb{F}_q$ 上，其算术表达容量趋近于 $1/2$。这与通过合同变换实现对称矩阵同时对角化（SDC）的问题有关，因为在有限域上，一定比例的矩阵对无法实现同时对角化。
• $m=1$ 和 $m=2$ 的架构：
  • 对于 $m=1$，基数通过射影空间的乘积导出：$|\mathcal{P}_{\mathbf{d}, r}| = |\mathcal{P}_{(n,1,1), r}| \cdot |\mathbb{P}^{k-1}|$。
  • 对于 $m=2$，作者根据输出张量生成的张量空间的维数对空间进行划分。他们提供了针对 $r > 1$ 和 $r=1$ 的不同公式，并指出对于 $r=1$，秩-1 张量的线性组合仍为秩-1 张量，由于基对的不唯一性，这使得计数变得复杂。

3. 特征整除性（$p \mid r$）
一个重要的理论结果是，当激活度被特征整除时，表达能力会发生退化。若 $r = i \cdot p$，则神经流形的基数等于激活度为 $i$ 的网络的基数：
$$|\mathcal{P}_{\mathbf{d}, ip}| = |\mathbf{\mathcal{P}}_{\mathbf{d}, i}|$$
这通过利用特征 $p$ 下的恒等式 $(a+b)^p \equiv a^p + b^p$ 以及有限域是完美域（perfect field）的事实得到了证明。这允许将复杂情况简化为更简单的情况。

• 特例（$r=p$）： 当 $r=p$ 时，神经流形恰好对应于秩至多为 $m$ 的 $k \times n$ 矩阵集合。

4. 结构差异：有限域 vs. 复数域
论文强调，即使是对于小型架构，有限域上的神经流形行为也可能与复数域表现出巨大差异。

• 示例： 对于 $r=2$ 的 $\mathbf{d}=(2, 2, 2)$ 架构，$\mathbb{C}$ 上的神经流形是扎里斯基开集（填满了空间），而 $\mathbb{F}_q$ 上的神经流形仅占据约一半的环境空间。
• 启示： 即使在复数域上成立的“填充”（surjectivity onto the ambient space）属性，在有限域上也不一定得到保证。

意义与主张
作者声称，这项工作为理解量化神经网络的表达能力提供了一个基础性的代数框架。通过将重点从函数逼近转向参数映射像的基数，他们揭示了由特征场所施加的结构性约束。

论文断言：

1. 特征场至关重要： 特征场在表达能力方面起着决定性作用，通常会降低网络相对于特征为零的场的容量。
2. 与深层数学的联系： 计数这些流形的问题本质上与韦伊猜想及有理点研究相关联，为神经网络理论与算术几何之间搭建了桥梁。
3. 现有理论的局限性： 研究结果表明，从复数或实数网络中获得的直觉（例如关于扎里斯基稠密性的直觉）可能无法转移到有限域，这需要针对量化架构使用特定的组合与代数工具。

论文最后指出了一些开放性问题，例如寻找表达容量收敛于非零比例 $0 < a/b < 1$ 的架构，以及解决有限域上对称张量的同时对角化问题。它并未提出新的训练算法或实验基准，而是专注于研究表示能力的理论极限。