Expressivity of Shallow Neural Networks Over Finite Fields

技術要約：有限体上の浅いニューラルネットワークの表現力

問題提起
本研究は、有限体 $\mathbb{F}_q$ 上における単項式活性化関数 $\sigma(x) = x^r$ を用いた浅い多項式ニューラルネットワーク（PNN）の表現力を調査するものである。ニューラルネットワークの表現力は、伝統的に統計的手法や実数・複素数体を用いて研究されてきたが、本論文は有限体の文脈における代数的な表現力に対処している。これは、重みの量子化（エネルギーとストレージの削減）による実用的な利点と、有限体上の有理点の計数と、複素多様体のモチーフ構造に関連するヴェイユ予想との理論的なつながりに動機付けられている。

核心となる問題は、「ニューロマニフォールド（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}$ は、重み空間 $\mathbb{F}_q^{m(n+k)}$ から、同次多項式の空間の積 $(S_r(\mathbb{F}_q^n))^k$ へのパラメータ写像 $\Psi_{\mathbf{d}, r}$ の像として定義される。
3. 計数戦略: 包含空間が有限であるため、表現力は $\mathcal{P}_{\mathbf{d}, r}$ の濃度 $|\mathcal{P}_{\mathbf{d}, r}|$ によって測定される。著者らは以下を利用する：
   • 多項係数定理: 多項式の係数が、体の標数 $p$ に対してどのようになるかを決定するための多項係数の性質。
   • テンソル分解: ネットワークの出力を対称テンソル分解（特にCPランクおよび同時対角化）に関連付ける。
   • 組合せ論的計数: 有限体上の特定のランクを持つ行列の数に関する公式（MacWilliams, 1969）や、$q$-二項係数を用いる。
   • 射影幾何学: スケーリング不変性を扱うために、射影空間におけるニューロマニフォールドの構造を分析する。

主要な貢献と結果

1. 一般的な上界
本論文は、活性化次数の $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$ の対称行列の集合に対応する。その濃度は、MacWilliamsの公式を用いて、$0 \leq j \leq m$ の範囲のランク $j$ を持つ対称行列の数の総和となる。
• 多出力 ($k>1$) かつ $r=2$: 著者らは $\mathbf{d}=(n, n, 2)$ のケースを分析している。彼らは、有限体と複素体との間の著しい対比を示している。$\mathbb{C}$ 上では、ニューロマニフォールドは（空間を埋め尽くす）ザリスキー稠密である。一方、$\mathbb{F}_q$ 上では、算術的表現容量は $q \to \infty$ のとき $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 \pmod p$ と、有限体が完全体であるという事実を用いて証明される。これにより、複雑なケースをより単純なケースへと簡約することが可能になる。

• 特殊なケース ($r=p$): $r=p$ のとき、ニューロマニフォールドは正確に、最大ランクが $m$ である $k \times n$ 行列の集合に対応する。

4. 構造的な違い：有限体 vs 複素体
本論文は、小さなアーキテクチャであっても、有限体におけるニューロマニフォールドの挙動が複素体におけるものとは劇的に異なる可能性があることを強調している。

• 例: $\mathbf{d}=(2, 2, 2), r=2$ の場合、$\mathbb{C}$ 上のニューロマニフォールドはザリスキー開集合（空間を充填している）であるが、$\mathbb{F}_q$ 上では、周囲の空間の約半分しか占めていない。
• 示唆: 「充填（surjectivity）」のような性質は、たとえ $\mathbb{C}$ 上で成立する場合でも、有限体上では保証されない。

意義と主張
著者らは、本研究が量子化されたニューラルネットワークの表現力を理解するための基礎的な代数的枠組みを提供するものであると主張している。関数近似からパラメータ写像の像の濃度へと焦点を移すことで、場の特性によって課される構造的な制約を明らかにしている。

論文は以下の通り断言している：

1. 場の特性が決定的に重要である: 場の特性は表現力において決定的な役割を果たし、多くの場合、特性ゼロの場と比較してネットワークの容量を減少させる。
2. 深い数学との接続: これらの多様体を計数する問題は、ヴェイユ予想および有理点の研究と本質的に結びついており、ニューラルネットワーク理論と算術幾何学の間の架け橋を提供している。
3. 現行理論の限界: これらの結果は、複素数または実数値のネットワークから得られる直感（例えばザリスキー稠密性に関するもの）が、有限体上の量子化アーキテクチャには必ずしも転用できないことを示唆しており、特定の組合せ論的および代数的なツールの必要性を提示している。

本論文は、表現容量が非ゼロの分数 $0 < a/b < 1$ に収束するアーキテクチャの探索や、有限体上の対称テンソルに対する同時対角化問題の解決といった未解決問題を特定して締めくくっている。本研究は、新しい学習アルゴリズムや実験的ベンチマークを提案するのではなく、表現可能性の理論的限界に焦点を当てている。