Expressivity of Shallow Neural Networks Over Finite Fields

기술 요약: 유한체 위에서의 얕은 신경망의 표현력

문제 정의
본 연구는 유한체 $\mathbb{F}_q$ 위에서 모노미얼 활성화 함수 $\sigma(x) = x^r$를 갖는 얕은 다항식 신경망(PNN)의 표현력을 조사한다. 신경망의 표현력은 전통적으로 통계적 방법이나 실수/복소수 체 위에서 연구되어 왔으나, 본 논문은 유한체 맥락에서의 대수적 표현력을 다룬다. 이는 가중치 양자화(에너지 및 저장 공간 절감)의 실용적 이점과, 유한체 상의 유리점(rational points) 개수를 세는 것과 복소 다양체의 모티브 구조(motivic structure)를 연결하는 바일 추측(Weil conjectures) 사이의 이론적 연관성에 의해 동기 부여되었다.

핵심 문제는 네트워크 아키텍처의 "산술적 표현 용량(arithmetic expressive capacity)"을 정량화하는 것이다. 연속적인 체에서는 표현력이 흔히 차원이나 자리스키 밀도(Zariski density)를 통해 측정되는 것과 달리, 저자들은 유有限체 상에서의 표현력을 '뉴로매니폴드(neuromanifold)'—즉, 파라미터 맵으로부터 표현 가능한 다항식 공간으로의 이미지의 카디널리티(cardinality)—를 통해 정의한다.

방법론
저자들은 네트워크 출력을 단순히 함수가 아닌 다항식 환(polynomial ring)의 원소로 취급하는 대수 기하학적 접근 방식을 채택한다.

1. 정식화: 아키텍처 $\mathbf{d}=(n, m, k)$와 활성화 차수 $r$을 갖는 얕형 신경망은 입력 $\mathbf{x} \in \mathbb{F}_q^n$를 출력 $(\mathbb{F}_q[x_1, \dots, x_n])^k$로 매핑한다. 출력은 차수가 $r$인 동차 다항식(homogeneous polynomials)의 $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. 계수 전략: 주위 공간(ambient space)이 유한하므로, 표현력은 $|\mathcal{P}_{\mathbf{d}, r}|$의 카디널리티로 측정된다. 저자들은 다음을 활용한다:
   • 다항 계수 정리(Multinomial Congruence Theorems): 필드의 표수(characteristic) $p$에 대해 어떤 모노미얼 계수가 소거되는지 결정하기 위함.
   • 텐서 분해(Tensor Decomposition): 네트워크 출력을 대칭 텐서 분해(특히 CP-rank 및 동시 대각화)와 연결함.
   • 조합론적 계수(Combinatorial Counting): 유한체 상에서 주어진 랭크를 갖는 행렬의 개수에 대한 공식(MacWilliams, 1969) 및 $q$-이항 계수를 사용함.
   • 사영 기하학(Projective Geometry): 스케일링 불변성(scaling invariance)을 처리하기 위해 사영 공간 내 뉴로매니폴드의 구조를 분석함.

주요 기여 및 결과

1. 일반 상한(General Upper Bounds)
본 논문은 활성화 차수 $r$의 $p$-진 전개(base-$p$ expansion)에 기반한 뉴로매니폴드의 카디널리티에 대한 일반적인 상한을 설정한다. 만약 $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$): 뉴로매니폴드는 랭크가 $m$ 이하인 $n \times n$ 대칭 행렬의 집합에 대응한다. 카디디널리티는 MacWilliams의 공식을 사용하여 $0 \leq j \leq m$인 랭크 $j$를 갖는 대칭 행렬의 개수의 합이다.
• 다중 출력 ($k>1$) 및 $r=2$: 저자들은 $\mathbf{d}=(n, n, 2)$인 경우를 분석한다. 이들은 유한체와 복소수 체 사이의 극명한 대조를 보여준다. $\mathbb{C}$ 위에서 뉴로매니폴드는 자리스키 조밀(Zariski dense)하여 공간을 채운다. 반면 $\mathbb{F}_q$ 위에서 뉴로매니폴드의 산술적 표현 용량은 $q \to \infty$일 때 $1/2$에 수렴한다. 이는 합동(congruence)을 통한 대칭 행렬의 동시 대각화(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$의 경우, 저자들은 출력 텐서의 스팬(span) 차원을 기준으로 공간을 분할한다. 이들은 $r > 1$과 $r=1$에 대해 구별되는 공식을 제공하며, $r=1$의 경우 랭크-1 텐서들의 선형 결합이 여전히 랭크-1로 남기 때문에 비고유한 기저 쌍(non-unique basis pairs)으로 인해 계수가 복잡해진다는 점을 언급한다.

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 복소수 체
본 논문은 작은 아키텍처에서도 유한체 상의 뉴로매니폴드 거동이 복소수 상의 거동과 크게 다를 수 있음을 강조한다.

• 예시: $\mathbf{d}=(2, 2, 2), r=2$인 경우, $\mathbb{C}$ 위에서 뉴로매니폴드는 자리스키 열린 집합(Zariski open set)이지만, $\mathbb{F}_q$ 위에서는 주위 공간의 약 절반만을 차지한다.
• 시사점: "채움(filling)"(주위 공간으로의 전사성)과 같은 성질은 복소수 체에서 성립하더라도 유한체에서는 보장되지 않는다.

의의 및 주장
저자들은 본 연구가 양자화된 신경망의 표현력을 이해하기 위한 기초적인 대수적 프레임워크를 제공한다고 주장한다. 함수 근사에서 파라미터 맵 이미지의 카디디널리티로 초점을 전환함으로써, 필드의 표수가 부과하는 구조적 제약을 밝혀낸다.

논문은 다음과 같이 단언한다:

1. 필드 표수의 결정적 역할: 필드의 표수는 표현력에 결정적인 역할을 하며, 종종 표수 0인 체에 비해 네트워크의 용량을 감소시킨다.
2. 심층 수학과의 연결: 이러한 매니폴드를 세는 문제는 바일 추측 및 유리점 연구와 본질적으로 연결되어 있으며, 신경망 이론과 산술 기하학 사이의 가교를 제공한다.
3. 기존 이론의 한계: 본 결과는 복소수 또는 실수 값 신경망에서 얻은 직관(예: 자리스키 밀도)이 유한체로 그대로 전이되지 않을 수 있음을 시사하며, 양자화된 아키텍처를 위한 특정한 조합론적 및 대수적 도구가 필요함을 보여준다.

결론적으로 저자들은 표현 용량이 $0 < a/b < 1$인 비제로 분율로 수렴하는 아키텍처를 찾는 문제와 유한체 상의 대칭 텐서에 대한 동시 대각화 문제를 향후 과제로 제시한다. 본 논문은 새로운 훈련 알고리즘이나 실험적 벤치마크를 제안하기보다는, 표현 가능성의 이론적 한계에 집중한다.