DL Published: Sep 2026

Reprezentacje grup cyklicznych w sieciach neuronowych

Abstract

Rozważamy zadanie dodawania modulo \( p \) jako punkt wyjścia do analizy, w jaki sposób sieci neuronowe kodują strukturę symetrii grupowej. Nawiązując do pracy Chughtai i in. [1], wyprowadzamy postać nierozkładalnych reprezentacji grupy cyklicznej \( \mathbb{Z}_p \) dwiema niezależnymi drogami: poprzez teorię charakterów oraz przez diagonalizację operatora przesunięcia cyklicznego. Na przykładzie grupy \( \operatorname{SO}(2) \) pokazujemy, że odwołanie się do liczb zespolonych jest tu koniecznością algebraiczną, nie kwestią notacyjnej wygody. Na tej podstawie odtwarzamy konstruktywny dowód Gromova [3], wiążąc jego wagi Fourierowskie z wyprowadzoną wcześniej przestrzenią niezmienniczą \( V_m \), i pokazujemy, że architektura jednowarstwowego perceptronu realizuje dodawanie jako przesunięcie fazowe w tej przestrzeni. Wyniki analityczne konfrontujemy z wagami rzeczywistej, wytrenowanej sieci.

Wstęp

Dodawanie modulo \( p \) stanowi zasadniczy problem analityczny w badaniu geometrii wewnętrznych reprezentacji sieci neuronowych. Choć sam problem może się wydawać elementarny, kryje on w sobie nietrywialną strukturę algebraiczną.

Schemat rozumowania podzielono na dwie główne części. W pierwszej analizujemy, jaką strukturę reprezentacji wymusza symetria operacji dodawania modulo. W drugiej sprawdzamy, czy i w jaki sposób sieć neuronowa do niej dąży podczas optymalizacji.

Dlaczego Liczby Zespolone

Zanim przejdziemy do formalnego dowodu, warto zapytać: czy do opisu tego zachowania liczby rzeczywiste w ogóle wystarczają? Rozważmy więc na początek grupę \( \operatorname{SO}(2) \) reprezentowaną przez macierz:

R(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos \theta \end{bmatrix}.

Geometryczną interpretacją tej macierzy jest obrót wektora o kąt \( \theta \). Znajdźmy teraz dla tej macierzy wartości własne. Z równania charakterystycznego \( \det(R(\theta) - \lambda I) = 0 \):

\begin{vmatrix} \cos\theta - \lambda & -\sin\theta \\ \sin\theta & \cos \theta - \lambda \end{vmatrix} = 0

(\cos\theta - \lambda)^2 + \sin^2\theta = 0

\cos^2\theta - 2\lambda\cos\theta + \lambda^2 + \sin^2\theta = 0

\lambda^2 - 2\lambda\cos\theta + 1 = 0

Licząc deltę:

\Delta = 4\cos^2\theta - 4 = 4(\cos^2\theta - 1)

Oznacza to, że równanie to ma rzeczywiste rozwiązania dla \( \lambda \) tylko przy warunku \( \cos^2\theta = 1 \), a więc dla parametru \( \theta = 0 \) (przekształcenie tożsamościowe) i \( \theta = \pi \) (obrót o \( 180^\circ \), symetria środkowa względem początku układu współrzędnych). Geometrycznie są to dokładnie te przypadki, w których wektor obrócony jest współliniowy z wektorem wyjściowym. Dla dowolnego innego kąta obrotu wektor obrócony nigdy nie jest równoległy do wektora wyjściowego, więc nie istnieje rzeczywista wartość własna. Macierz \( R(\theta) \) jest diagonalizowalna tylko nad \( \mathbb{C} \):

\lambda_{\pm} = \cos\theta + i\sin\theta = e^{\pm i\theta}.

To pokazuje, że wprowadzenie liczb zespolonych w tym problemie nie jest kwestią wygody notacji, a koniecznością wynikającą z algebraicznej domkniętości \( \mathbb{C} \). Zbiór ten gwarantuje istnienie pełnego zestawu wartości własnych dla macierzy ortogonalnych.

Kąt obrotu θ °

Kąt wektora φ °

Ustaw θ na 0° lub 180°, aby zobaczyć rzeczywisty wektor własny.

Wektor \( v \) (niebieski) i jego obraz \( R(\theta)v \) (czerwony) na płaszczyźnie \( \mathbb{R}^2 \).

Wartości własne \( \lambda_\pm = e^{\pm i\theta} \) na okręgu jednostkowym płaszczyzny zespolonej \( \mathbb{C} \).

Zjawisko to nie jest specyficzne dla \( SO(2) \). Każdy operator realizujący cykliczne przesunięcie (a więc również działanie grupy \( \mathbb{Z}_p \) na przestrzeni funkcji, do którego dojdziemy w dalszej części) napotyka tę samą przeszkodę i wymaga analogicznego rozszerzenia do \( \mathbb{C} \).

Charaktery grupy cyklicznej

Rozważmy grupę cykliczną \( (\mathbb{Z}_p, +) \), czyli zbiór reszt z dzielenia przez \( p \) z działaniem dodawania modulo \( p \), gdzie \( p \) jest liczbą pierwszą.

W ogólnej teorii reprezentacji szukamy homomorfizmów \( \rho : G \rightarrow \operatorname{GL}(V) \), które przypisują elementom grupy \( G \) odwracalne macierze. Charakter takiej reprezentacji definiuje się formalnie jako ślad przypisanej macierzy, czyli \( \chi_\rho(g) = \operatorname{Tr}(\rho(g)) \). W przypadku grupy \( \mathbb{Z}_p \) zachodzi jednak kluczowe uproszczenie. Ponieważ dodawanie modulo \( p \) jest działaniem przemiennym, \( \mathbb{Z}_p \) jest grupą abelową. Z lematu Schura wynika, że nad ciałem liczb zespolonych wszystkie nierozkładalne reprezentacje grup abelowych są jednowymiarowe [2].

Oznacza to, że nasza przestrzeń wektorowa \( V \) sprowadza się do \( \mathbb{C}^1 \), a macierze z grupy \( \operatorname{GL}(V) \) redukują się do pojedynczych, niezerowych skalarów. Ponieważ ślad macierzy rozmiaru \( 1 \times 1 \) jest równy jej jedynemu elementowi, wielowymiarowa reprezentacja i jej charakter stają się tym samym obiektem matematycznym (\( \rho \equiv \chi_\rho \)). Dzięki temu możemy całkowicie pominąć aparat macierzowy i zdefiniować charakter bezpośrednio jako odwzorowanie w zbiór liczb zespolonych \( \mathbb{C}^* \).

Aby zrozumieć, jaką postać mogą przyjmować te reprezentacje w sieci neuronowej, rozpocznijmy od wyprowadzenia ich analitycznej formy. Ponieważ \( \rho \) jest homomorfizmem, \( \chi \) dziedziczy tę własność bezpośrednio:

\chi(g + h) = \chi(g) \cdot \chi(h), \qquad \forall g, h \in G

Aby wyznaczyć postać takiej funkcji dla \( G = \mathbb{Z}_p \), zaobserwujmy najpierw jej podstawowe własności. Po pierwsze, każdy element \( k \in \mathbb{Z}_p \) można zapisać jako \( k \)-krotną sumę elementu \( 1 \), z własności homomorfizmu otrzymujemy:

\begin{aligned} \chi(k) &= \chi(\underbrace{1+1+\dots+1}_{k \text{ razy}}) \\ &= \chi(1)\cdot\chi(1)\cdots\chi(1) = \chi(1)^k. \qquad (1) \end{aligned}

Dodatkowo możemy zaobserwować, że skoro grupa \( \mathbb{Z}_p \) ma rząd \( p \), zachodzi \( p \cdot 1 \equiv 0 \pmod{p} \). Podstawiając \( k = p \) do \( (1) \) i korzystając z \( \chi(0) = 1 \) (co wynika wprost z warunku homomorfizmu dla \( g=h=0 \)), otrzymujemy

\chi (1)^p = \chi(0) = 1

Oznaczając \( z := \chi(1) \), dochodzimy do warunku:

$$ z^p = 1, $$

czyli \( \chi(1) \) musi być pierwiastkiem stopnia \( p \) z jedynki. Równanie \( z^p = 1 \) ma dokładnie \( p \) rozwiązań w dziedzinie liczb zespolonych. Korzystając ze wzoru Eulera, można je zapisać jako:

z_m = e^{2\pi i m/p}, \qquad m = 0, 1, \dots, p - 1.

Każdy wybór \( m \) daje inną wartość \( \chi(1) \), a więc inny charakter, stąd oznaczenie \( \chi_m(1) := z_m =e^{2\pi i m/p} \). Podstawiając to do wzoru \( (1) \) z poprzedniego fragmentu, \( \chi(k) = \chi(1)^k \), otrzymujemy zupełną rodzinę charakterów grupy \( \mathbb{Z}_p \):

\chi_m(k)= \left( e^{2\pi i m /p} \right)^k = e^{2\pi i mk /p}

Liczba pierwsza p

Parametr m

Parametr k

Wybierz m i k, aby zobaczyć wartość charakteru.

Orbita \( \chi_m(0), \dots, \chi_m(p-1) \) na okręgu jednostkowym; podświetlony punkt to wybrane \( \chi_m(k) \).

Podejście Algebry Liniowej

Analogicznie można podejść do problemu ze strony czystej algebry liniowej. Rozważmy przestrzeń funkcji \( V := \operatorname{Fun}(\mathbb{Z}_p, \mathbb{C}) \) oraz działanie elementu \( h \in \mathbb{Z}_p \) na funkcjach \( f: \mathbb{Z}_p \rightarrow \mathbb{C} \) przez przesunięcie argumentu \( f \mapsto f(\cdot - h) \). Dla dowolnego elementu \( h \in \mathbb{Z}_p \) definiujemy operator \( S_h \) jako \( (S_hf)(k) := f(k - h \pmod p) \).

Naszym celem jest znalezienie bazy przestrzeni \( V \), która będzie optymalna do reprezentowania działania tej grupy. W ujęciu algebry liniowej oznacza to poszukiwanie funkcji, które nie zmieniają swojej postaci pod wpływem przesunięcia, a jedynie skalują się o pewną wartość. Szukamy zatem wspólnych wektorów własnych dla całej rodziny operatorów \( S_h \).

Struktura grupy cyklicznej sprawia, że działanie całej rodziny operatorów \( S_h \) jest w całości zdeterminowane przez działanie generatora \( S_1 \).

Dowód

Wynika to z faktu, że działanie grupy \( \mathbb{Z}_p \) na przestrzeni funkcji to odwzorowanie \( \rho : \mathbb{Z}_p \rightarrow \operatorname{GL}(V) \), gdzie \( \rho(h):=S_h \). Analogicznie do \( \chi \), funkcja \( \rho \) spełnia własność homomorfizmu, co można zapisać w postaci:

S_{g + h} = S_g \circ S_h

Po wyborze bazy przestrzeni \( V \) złożenie operatorów \( \circ \) odpowiada zwykłemu mnożeniu macierzy, więc kontynuujemy dalej na notacji \( S_g \cdot S_h \). Bazując na analogicznych działaniach na charakterach, wyprowadzamy:

S_h = S_{\underbrace{1+1+\dots+1}_{h \text{ razy}}} = \underbrace{S_1\cdot S_1 \cdot \dots \cdot S_1}_{h \text{ razy}} = S_1^h

Oznacza to, że wystarczy zbadać własności samego operatora \( S_1 \). Jeśli \( f \) jest wektorem własnym \( S_1 \) z wartością własną \( \lambda \), to jest on automatycznie wektorem własnym każdego \( S_h \), z wartością własną \( \lambda^h \).

Wyznaczając wektory własne operatora \( S_1 \), formalnie szukamy takiego \( f \), że \( S_1f = \lambda f \), czyli \( f(k - 1) = \lambda f(k) \) dla wszystkich \( k \in \mathbb{Z}_p \). Operator \( S_1 \) odpowiada cyklicznej macierzy permutacji rozmiaru \( p \times p \). Z jej równania charakterystycznego \( \det(S_1 - \lambda I) = 0 \) otrzymujemy:

(-1)^{p}(\lambda^p - 1) = 0

\lambda^p = 1

Oznacza to, analogicznie do warunku charakterystyki, że \( \lambda \) musi być pierwiastkiem \( p \)-tego stopnia z jedynki.

Konstrukcja rzeczywistej bazy reprezentacji

Mając do dyspozycji zupełną bazę, możemy zacząć nasze rozważania w kontekście reprezentacji w sieciach neuronowych. Po pierwsze warto zauważyć, że wartości, na jakich bazują modele sieci neuronowych, są rzeczywiste. Fakt ten wymusza przekształcenie reprezentacji zespolonej na jej rzeczywisty odpowiednik. Korzystając ze wzoru Eulera, charakter możemy zapisać jako:

\begin{aligned} \chi_m(k)&= e^{2\pi i mk /p} \\ &= \cos{\left(\frac{2\pi m k}{p}\right)} + i\sin{\left(\frac{2\pi m k}{p}\right)} \end{aligned}

Możemy teraz skorzystać z sumy charakteru \( \chi_m(k) \) i jego sprzężenia \( \overline{\chi_m(k)} \). Operacja ta jest dopuszczalna w obrębie naszej bazy, ponieważ sprzężenie charakteru to po prostu charakter z ujemnym indeksem: \( \overline{\chi_m(k)} = \overline{e^{2\pi i mk /p}} = e^{-2\pi i mk /p} = \chi_{-m}(k) \). Dodając te wyrażenia do siebie, otrzymujemy:

\begin{aligned} \chi_m(k) + \overline{\chi_m(k)} &= \cos{\left(\frac{2\pi m k}{p}\right)} + i\sin{\left(\frac{2\pi m k}{p}\right)} \\ &\quad + \cos{\left(\frac{2\pi m k}{p}\right)} - i\sin{\left(\frac{2\pi m k}{p}\right)} \\ &= 2\cos{\left(\frac{2\pi m k}{p}\right)} \end{aligned}

Dzieląc ten wynik przez \( 2 \), odzyskujemy czystą funkcję cosinus. Analogicznie postępujemy dla sinusa, odejmując sprzężenie:

\begin{aligned} \chi_m(k) - \overline{\chi_m(k)} &= \cos{\left(\frac{2\pi m k}{p}\right)} + i\sin{\left(\frac{2\pi m k}{p}\right)} \\ &\quad - \cos{\left(\frac{2\pi m k}{p}\right)} + i\sin{\left(\frac{2\pi m k}{p}\right)} \\ &= 2i\sin{\left(\frac{2\pi m k}{p}\right)} \end{aligned}

Dzieląc wyrażenie \( \chi_m(k) - \overline{\chi_m(k)} \) przez stałą \( 2i \), otrzymujemy rzeczywistą reprezentację:

\sin{\left(\frac{2\pi m k}{p}\right)}

Para funkcji \( \left\{\cos\left(\frac{2\pi m k}{p}\right), \sin\left(\frac{2\pi m k}{p}\right)\right\} \) stanowi więc rzeczywistą bazę, rozpinającą dwuwymiarową przestrzeń \( V_m \), na której grupa \( \mathbb{Z}_p \) działa bez konieczności odwoływania się do liczb zespolonych.

Należy wspomnieć, że sam \( \cos(2\pi m k / p) \) nie wystarcza. Działanie operatora \( S_h \) nie skaluje po prostu wyrażenia, a przekształca je w kombinację liniową cosinusa i sinusa. Wynika to bezpośrednio z tożsamości trygonometrycznej \( \cos(\alpha - \beta) = \cos\alpha\cos\beta + \sin\alpha\sin\beta \):

\begin{aligned} (S_h \cos)(k) &= \cos\left(\frac{2\pi m (k - h)}{p}\right) \\ &= \cos{\left(\frac{2\pi m k}{p}\right)} \cos{\left(\frac{2\pi m h}{p}\right)} + \sin{\left(\frac{2\pi m k}{p}\right)} \sin{\left(\frac{2\pi m h}{p}\right)} \end{aligned}

Obserwacja ta implikuje fakt, że przestrzeń rozpięta przez sam cosinus nie jest niezmiennicza względem działania grupy \( S_h \), ponieważ przekształca on wynik do przestrzeni zawierającej także sinus. Dopiero para \( \left\{\cos\left(\frac{2\pi m k}{p}\right), \sin\left(\frac{2\pi m k}{p}\right)\right\} \) rozpina przestrzeń \( V_m \), która jest niezmiennicza, ponieważ dla dowolnego elementu \( h \in \mathbb{Z}_p \) i dowolnego elementu \( v \in V_m \) zachodzi \( S_h(v) \in V_m \).

Liczba pierwsza p

Parametr m

Przesunięcie h

Ustaw h = 0, aby zobaczyć, że tylko wtedy wynik jest czystym cosinusem.

\( (S_h\cos)(k) \) (słupki) na tle \( \cos(2\pi m k/p) \) (przerywana linia), dla \( k = 0, \dots, p-1 \).

Współczynniki \( (S_h\cos)(k) \) w bazie \( \{\cos, \sin\} \) — punkt opuszcza oś cosinusa dla każdego \( h \neq 0 \).

Reprezentacja w Sieciach

Mając analitycznie wyprowadzoną reprezentację grup cyklicznych, możemy przejść do głównego problemu naszej analizy: czy sieci neuronowe samoistnie odkrywają i kodują te struktury w podobny sposób. Istotnych wniosków w tym zakresie dostarcza publikacja Andreya Gromova „Grokking modular arithmetic”[3], w której autor bada to zagadnienie w kontekście dynamiki opóźnionej generalizacji. W niniejszej pracy odtwarzamy jego konstrukcyjny argument dotyczący struktury rozwiązania, świadomie pomijając wątek grokkingu jako wykraczający poza zakres tego artykułu. Interesuje nas wyłącznie mechanika formowania się reprezentacji, nie tempo jej powstawania w czasie.

Rozważmy dwuwarstwowy perceptron bez obciążenia (biasu), zdefiniowany w parametryzacji średniego pola (ang. mean-field parametrization) jako:

\begin{aligned} h^{(1)}_k(x) &= \frac{1}{\sqrt{D}} \sum_{j=1}^D W_{kj}^{(1)}x_j, \\ z_k^{(1)} &= \phi(h_k^{(1)}(x)), \\ h^{(2)}_q(x) &= \frac{1}{N} \sum_{k=1}^N W_{qk}^{(2)} z_k^{(1)}(x) \end{aligned}

gdzie:

\( N \) jest szerokością warstwy ukrytej, a \( k \in \{1, \dots, N\} \) indeksuje jej poszczególne neurony,
\( D \) oznacza wymiar wejścia,
\( q \in \{0, \dots, p - 1\} \) indeksuje klasy wyjściowe (reszty modulo \( p \)),
\( \phi \) jest nieliniową funkcją aktywacji.

Macierze wag inicjalizowane są standardowym rozkładem normalnym: \( W^{(1)}, W^{(2)} \sim \mathcal{N}(0, 1) \).

Autor bada dodawanie modulo \( p \) w kontekście zadania klasyfikacji. Przyjmuje ustaloną liczbę (niekoniecznie pierwszą) \( p \) oraz zbiór \( \mathbb{Z}_p = \{0, 1, \dots, p - 1\} \). Każda liczba wejściowa (\( a \) oraz \( b \)) jest kodowana w postaci wektora one-hot o długości \( p \). Oznacza to, że wejście modelu ma wymiar \( 2p \) (złożenie dwóch wektorów \( p \)-elementowych), a wyjście ma wymiar \( p \) z funkcją softmax.

W celach analitycznych przyjmujemy nieliniowość kwadratową \( \phi(u) = u^2 \). Wybór ten zachowuje nieliniowy charakter sieci, a jednocześnie pozwala na ścisłe, algebraiczne analizowanie interakcji między wagami bez konieczności aproksymacji szeregiem Taylora (co dla funkcji ReLU wymaga pośredniego przejścia przez jej gładką aproksymację, np. funkcję Swish \( x \cdot \sigma (\beta x) \), zbieżną do ReLU przy \( \beta \rightarrow \infty \) ). W takiej konfiguracji sieć można bardzo prosto przedstawić algebraicznie:

f(x) = \frac{1}{DN}W^{(2)}\bigg( W^{(1)} x \bigg)^{\odot 2}

gdzie \( (\cdot)^{\odot 2} \) oznacza podniesienie każdego elementu wektora do kwadratu (kwadrat Hadamarda).

Analiza Warstwy \( W^{(1)} \)

Na wejściu sieci podajemy dwie liczby, \( a \) i \( b \), z których każda reprezentowana jest jako wektor typu one-hot. Oznacza to, że macierz wag pierwszej warstwy, \( W^{(1)} \), możemy naturalnie podzielić na dwa pionowe bloki: \( W_A^{(1)} \) odpowiadający za przetwarzanie wejścia \( a \) oraz \( W_B^{(1)} \) dla wejścia \( b \).

Przy takim podziale możemy łatwo zidentyfikować pojedyncze wagi: zmienna \( W_{A, k, a}^{(1)} \) to waga łącząca aktywny element \( a \)-tego wejścia z \( k \)-tym neuronem w warstwie ukrytej (analogicznie dla bloku \( B \)).

Ponieważ wektor one-hot działa jak selektor (wybiera jedną wartość, a resztę zeruje), możemy pominąć pełne mnożenie macierzowe. Stan \( k \)-tego neuronu przed aktywacją redukuje się do przeskalowanej sumy tych dwóch wybranych wag:

h_k^{(1)}(a, b) = \frac{1}{\sqrt{2p}} \left( W_{A, k, a}^{(1)} + W_{B, k, b}^{(1)} \right)

Dowód

Wektor wejściowy \( x \in \mathbb{R}^{2p} \) to konkatenacja dwóch wektorów one-hot dla liczb \( a, b \in \{0, \dots, p - 1 \} \):

$$ x = [e_a; e_b] $$

gdzie \( e_a \in \mathbb{R}^p \) posiada wartość \( 1 \) na pozycji \( a \) i \( 0 \) na pozostałych (analogicznie \( e_b \)).

Macierz wag pierwszej warstwy \( W^{(1)} \in \mathbb{R}^{N \times 2p} \) składa się z 2 niezależnych bloków wielkości \( N \times p \):

W^{(1)} = \begin{bmatrix} W_A^{(1)} & W_B^{(1)} \end{bmatrix}

Podstawiając ten podział do wzoru na aktywację liniową warstwy ukrytej, otrzymujemy:

\begin{aligned} h^{(1)}(a, b) &= \frac{1}{\sqrt{2p}} W^{(1)} x \\ &= \frac{1}{\sqrt{2p}} \begin{bmatrix} W_A^{(1)} & W_B^{(1)} \end{bmatrix} \begin{bmatrix} e_a \\ e_b \end{bmatrix} \\ &= \frac{1}{\sqrt{2p}} \left( W_A^{(1)} e_a + W_B^{(1)} e_b \right) \end{aligned}

Iloczyn macierzy z wektorem jednostkowym \( W_A^{(1)} e_a \) to operacja wybrania \( a \)-tej kolumny macierzy \( W_A^{(1)} \). Przechodząc z zapisu wektorowego do poziomu pojedynczego, \( k \)-tego neuronu, uzyskujemy bezpośrednio:

h_k^{(1)}(a, b) = \frac{1}{\sqrt{2p}} \left( W_{A, k, a}^{(1)} + W_{B, k, b}^{(1)} \right)

Stosując przyjętą funkcję aktywacji \( \phi(u) = u^2 \), wyjście \( k \)-tego neuronu przyjmuje postać:

\begin{aligned} z_k^{(1)}(a, b) &= \left( h_k^{(1)}(a, b) \right)^2 \\ &= \frac{1}{2p} \left( W_{A, k, a}^{(1)} + W_{B, k, b}^{(1)} \right)^2 \end{aligned}

Rozpisując powyższy kwadrat ze wzoru skróconego mnożenia:

z_k^{(1)}(a, b) = \frac{1}{2p} \left[ \left( W_{A, k, a}^{(1)} \right)^2 + \left( W_{B, k, b}^{(1)} \right)^2 + 2 W_{A, k, a}^{(1)} W_{B, k, b}^{(1)} \right]

Następnym krokiem jest podstawienie założenia o częstotliwościach Fouriera (\( W_{A,k,a} \propto \cos(\omega_m a + \phi_k) \) i \( W_{B,k,b} \propto \cos(\omega_m b + \psi_k) \)):

W_{A,k,a}^{(1)} = c_k \cos{(\omega_k a + \phi_k)}, \quad W_{B,k,b}^{(1)} = c_k\cos{(\omega_k b + \psi_k)}

gdzie \( \omega_k = \frac{2\pi m_k}{p} \), a \( c_k \) jest amplitudą składowej.

Rozpisujemy kwadrat sumy:

\begin{aligned} z_k^{(1)}(a, b) = \frac{c_k^2}{2p} \Big( &\cos^2(\omega_k a + \phi_k) + \cos^2(\omega_k b + \psi_k) \\ &+ 2\cos(\omega_k a + \phi_k)\cos(\omega_k b + \psi_k) \Big) \end{aligned}

Stosujemy tożsamości trygonometryczne:

\( \cos^2(\alpha) = \dfrac{1 + \cos(2\alpha)}{2} \)
\( 2\cos(\alpha)\cos(\beta) = \cos(\alpha + \beta) + \cos(\alpha - \beta) \)

Podstawiając je do wzoru:

\begin{aligned} z_k^{(1)}(a, b) = \frac{c_k^2}{2p} \Big[ &1 + \frac{1}{2}\cos(2\omega_k a + 2\phi_k) + \frac{1}{2}\cos(2\omega_k b + 2\psi_k) \\ &+ \cos\big(\omega_k(a+b) + \phi_k + \psi_k\big) + \cos\big(\omega_k(a-b) + \phi_k - \psi_k\big) \Big] \end{aligned}

Kluczowa jest tu implikacja tej nieliniowości. Podniesienie do kwadratu sumy sygnałów sprawiło, że w wyrazie mieszanym otrzymaliśmy \( \cos\big(\omega_k(a+b) + \phi_k + \psi_k\big) \), który w swoim argumencie fizycznie realizuje dodawanie wejściowych liczb \( a \) oraz \( b \).

Analiza Warstwy \( W^{(2)} \)

Pełna aktywacja wyjściowa \( q \)-tego logitu (dla przewidywanej klasy \( q \in \mathbb{Z}_p \)) ma postać:

h^{(2)}_q(a, b) = \frac{1}{N} \sum_{k=1}^N W_{qk}^{(2)} z_k^{(1)}(a, b)

Dla wyjścia odpowiadającego klasie \( q \in \{0, 1, \dots, p-1\} \), waga łącząca \( k \)-ty neuron z \( q \)-tym logitem charakteryzuje się niezależną, wyuczalną fazą, którą oznaczymy jako \( \xi_k \):

W_{q, k}^{(2)} = d_k \cos(\omega_k q + \xi_k)

Podstawiając \( W_{q, k}^{(2)} \) oraz \( z_k^{(1)}(a, b) \), otrzymujemy:

\begin{aligned} h_q^{(2)}(a, b) &= \frac{1}{2pN} \sum_{k=1}^N c_k^2 d_k \cos(\omega_k q + \xi_k) \\ &\quad \cdot \Big[ 1 + \frac{1}{2}\cos(2\omega_k a + 2\phi_k) + \frac{1}{2}\cos(2\omega_k b + 2\psi_k) \\ &\quad\quad + \cos\big(\omega_k(a+b) + \phi_k + \psi_k\big) + \cos\big(\omega_k(a-b) + \phi_k - \psi_k\big) \Big] \end{aligned}

Aby rozwinąć ten iloczyn na pojedyncze składowe uśredniane przez sieć, wymnażamy człon \( \cos(\omega_k q + \xi_k) \) przez każdy element w nawiasie kwadratowym, stosując tożsamość trygonometryczną:

\cos(X)\cos(Y) = \frac{1}{2}\big[\cos(X-Y) + \cos(X+Y)\big]

Pełne rozwinięcie

\begin{aligned} h_q^{(2)}(a,b) &= \frac{1}{2pN} \Bigg[ \\ &\quad \frac{1}{4} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(2a - q) + 2\phi_k - \xi_k\Big) \\ &\quad + \frac{1}{4} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(2a + q) + 2\phi_k + \xi_k\Big) \\ &\quad + \frac{1}{4} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(2b - q) + 2\psi_k - \xi_k\Big) \\ &\quad + \frac{1}{4} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(2b + q) + 2\psi_k + \xi_k\Big) \\ &\quad + \frac{1}{2} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(a+b-q) + \phi_k + \psi_k - \xi_k\Big) \\ &\quad + \frac{1}{2} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(a+b+q) + \phi_k + \psi_k + \xi_k\Big) \\ &\quad + \frac{1}{2} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(a-b-q) + \phi_k - \psi_k - \xi_k\Big) \\ &\quad + \frac{1}{2} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(a-b+q) + \phi_k - \psi_k + \xi_k\Big) \\ &\quad + \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k q + \xi_k\Big) \Bigg] \end{aligned}

W rozwiniętym równaniu interesuje nas głównie część z wyrażeniem

\cos\Big(\omega_k(a+b-q) + \phi_k + \psi_k - \xi_k\Big)

Aby pozbyć się fazy, przyjmujemy \( \xi_k = \psi_k + \phi_k \), otrzymując

\cos\Big(\omega_k(a+b-q)\Big)

Pełne rozwinięcie

\begin{aligned} h_q^{(2)}(a,b) &= \frac{1}{2pN} \Bigg[ \\ &\quad \frac{1}{4} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(2a - q) + \phi_k - \psi_k\Big) \\ &\quad + \frac{1}{4} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(2a + q) + 3\phi_k + \psi_k\Big) \\ &\quad + \frac{1}{4} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(2b - q) - \phi_k + \psi_k\Big) \\ &\quad + \frac{1}{4} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(2b + q) + \phi_k + 3\psi_k\Big) \\ &\quad + \frac{1}{2} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(a+b-q)\Big) \\ &\quad + \frac{1}{2} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(a+b+q) + 2\phi_k + 2\psi_k\Big) \\ &\quad + \frac{1}{2} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(a-b-q) - 2\psi_k\Big) \\ &\quad + \frac{1}{2} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(a-b+q) + 2\phi_k\Big) \\ &\quad + \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k q + \phi_k + \psi_k\Big) \Bigg] \end{aligned}

Kolejną kwestią jest zbadanie, co dzieje się z pozostałymi wyrażeniami. Wszystkie te wyrazy mają w członie \( \cos \) przesunięcie fazowe \( \phi_k, \psi_k \). Fazy te są inicjalizowane losowo i zachowują się jak niezależne zmienne losowe.

W konsekwencji, przy sumowaniu po dużej szerokości warstwy ukrytej \( N \), wartości tych zmiennych ulegają interferencji destruktywnej. Zgodnie z Centralnym Twierdzeniem Granicznym (CTG) oraz mechaniką błądzenia losowego, suma takich wyrazów rośnie w tempie \( \mathcal{O}(\sqrt{N}) \). Ponieważ przed całym nawiasem znajduje się czynnik normalizujący zawierający \( 1/N \), ostateczny wkład tych ośmiu wyrazów do logitu skaluje się jako \( \mathcal{O}(1/\sqrt{N}) \) i statystycznie dąży do zera dla dużych sieci.

Liczba neuronów N

Błądzenie losowe \( \sum_{k=1}^N (\cos\theta_k, \sin\theta_k) \) dla losowych faz \( \theta_k \) (czerwony) na tle sumy spójnej bez losowej fazy (niebieski).

Znormalizowana moc \( |\text{suma}| / N \) w funkcji \( N \): składnik spójny zostaje na poziomie \( 1 \), losowy zanika jak \( 1/\sqrt{N} \).

Jedynym składnikiem, który nie ulega wygaszeniu, jest wyraz całkowicie wolny od zmiennych losowych:

\frac{1}{2} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(a+b-q)\Big)

Dla każdego neuronu \( k \) nastrojonego na daną częstotliwość \( \omega_k \), sygnał ten jest deterministyczny i dodaje się konstruktywnie. Jego suma rośnie w tempie \( \mathcal{O}(N) \), co w połączeniu z normalizacją \( 1/N \) przed nawiasem daje stabilną wartość rzędu \( \mathcal{O}(1) \).

Po odrzuceniu wygasających członów szumowych, wynik uśredniania redukuje całe, wieloliniowe wyrażenie do pojedynczego sumowania. Włączając mnożnik \( \frac{1}{2} \) do stałej przed sumą (\( \frac{1}{2pN}\cdot\frac{1}{2} = \frac{1}{4pN} \)), otrzymujemy ostateczną postać aktywacji wyjściowej logitu:

h_q^{(2)}(a, b) \approx \frac{1}{4pN} \sum_{k=1}^N c_k^2 d_k \cos\Big(\omega_k(a+b-q)\Big)

Zakładając, że neurony grupują się w klastry nastrojone na wspólne częstotliwości \( \frac{c_k^2 d_k}{4p} \approx \gamma \):

h_q^{(2)}(a, b) \approx \gamma \sum_{m \in S_{\text{active}}} \cos\left( \frac{2\pi m}{p} (a + b - q) \right)

Przejście od sumy po neuronach do sumy po częstotliwościach zakłada, że wiele neuronów \( k \) nastrojonych jest na tę samą częstotliwość \( \omega_k \). Ich wkłady zostały tu zagregowane we wspólną amplitudę \( \gamma \), przypisaną danej częstotliwości \( m \), zamiast pojedynczemu neuronowi. Prowadzi to do zbioru \( S_{\text{active}} \subset \{0, 1, \dots, p-1\} \) częstotliwości Fouriera, na które nastrojone są neurony sieci. Konstrukcja nie przesądza, ile ani które częstotliwości zostaną wyselekcjonowane w procesie uczenia. Zależy to od architektury, funkcji aktywacji i przebiegu optymalizacji (analizy mechanistyczne w pracy[4] wskazują na przypadki zbieżności do zaledwie kilku składowych).

Składnik \( \cos\left( \frac{2\pi m}{p} (a + b - q) \right) \), traktowany jako funkcja \( q \), należy do rzeczywistej przestrzeni \( V_m \) rozpiętej przez parę \( \{\cos, \sin\} \), która, jak pokazaliśmy w pierwszej części analizy, jest dla \( m \neq 0 \) podprzestrzenią niezmienniczą względem cyklicznych operatorów przesunięcia, nierozkładalną nad \( \mathbb{R} \). Dodawanie \( a+b \) jest w niej realizowane jako przesunięcie fazowe. Konstrukcja ta pokazuje więc, że architektura perceptronu jest w stanie zrealizować dodawanie modulo \( p \) w bazie nierozkładalnych reprezentacji grupy \( \mathbb{Z}_p \), z dokładnością do członów zanikających jak \( \mathcal{O}(1/\sqrt{N}) \). Nie rozstrzyga natomiast, czy optymalizacja prowadzi do takiego rozwiązania. To pytanie empiryczne, któremu poświęcona jest część 2 (w trakcie opracowania).

Liczba pierwsza p

Liczba aktywnych częstotliwości \( |S_{\text{active}}| \)

Idealny wynik \( \frac{1}{M}\sum_{m=1}^{M}\cos\left(\frac{2\pi m}{p}(a+b-q)\right) \) dla każdego \( q \); zielony słupek to poprawna odpowiedź \( (a+b) \bmod p \).

Wytrenowana Sieć

Poniżej znajduje się wizualizacja rzeczywistej, wytrenowanej sieci MLP (\( \operatorname{FN}_0 : \mathbb{R}^{2p} \to \mathbb{R}^{142} \), \( x^2 \), \( \operatorname{FN}_2 : \mathbb{R}^{142} \to \mathbb{R}^{p} \), bez wyrazów wolnych) rozwiązującej dodawanie modulo \( p = 71 \). Prezentowana sieć została wytrenowana z użyciem AdamW, współczynnikiem uczenia \( 10^{-3} \), bez regularyzacji L2, na \( 100\% \) wszystkich par \( (a, b) \), przez \( 4\,000 \) epok. Pełny zbiór danych, celowo bez podziału na trening i test, ponieważ interesuje nas wyłącznie struktura rozwiązania, a nie dynamika dochodzenia do niego (jak wspomniano wyżej, świadomie pomijamy tu wątek grokkingu).

PCA kolumn \( \operatorname{FN.0.weight} \): każdy punkt to kierunek wejściowy dla \( a=k \) (kółko) lub \( b=k \) (romb), kolor koduje \( k \).

PCA wierszy \( \operatorname{FN.2.weight} \): każdy punkt to kierunek wyjściowy dla wyniku \( r \), kolor koduje \( r \).

Cała macierz \( \operatorname{FN.0.weight} \) (142 neurony \( \times \) 142 wejścia); pionowa linia rozdziela część \( a \) od \( b \).

Widmo DFT: łączna moc widmowa \( |\hat{w}_a(m)|^2 + |\hat{w}_b(m)|^2 \) zsumowana po wszystkich neuronach, dla każdej częstotliwości \( m \).

Neuron warstwy ukrytej

Ładowanie wag modelu…

Wektor wag wejściowych \( \operatorname{FN}_0 \) dla wybranego neuronu, rozbity na część \( a \) i \( b \).

Aktywacja wybranego neuronu (po \( x^2 \)) jako funkcja pary wejściowej \( (a, b) \) albo, po przełączeniu, współrzędnych \( \big((a+b) \bmod p,\ (a-b) \bmod p\big) \).

Rozkład prawdopodobieństwa (softmax) na wyjściu sieci dla wybranej pary \( (a, b) \); zielony słupek to poprawna odpowiedź \( (a+b) \bmod p \).

References

Chughtai, B., Chan, L., & Nanda, N. (2023). A Toy Model of Universality: Reverse Engineering how Networks Learn Group Operations. ICML.
Serre, J-P. (1977). Linear Representations of Finite Groups. Graduate Texts in Mathematics, vol. 42. Springer.
Gromov, A. (2023). Grokking modular arithmetic. arXiv:2301.02679.
Nanda, N., Chan, L., Lieberum, T., Smith, J., & Steinhardt, J. (2023). Progress measures for grokking via mechanistic interpretability. ICLR.