Геометрическая структура, скрытая в сложении по модулю p
Примечание о переводе: Данный перевод выполнен языковой моделью (LLM), а не Джереми Кэрроллом. Все учебные материалы на русском языке в рамках курса будут написаны и озвучены Джереми Кэрроллом лично, без использования машинного перевода.
Предварительные сведения: ключевые понятия для начинающих
Прежде чем погружаться в тему, установим чёткие определения для читателей, незнакомых с машинным обучением или модулярной арифметикой.
Что такое модулярное сложение?
Модулярное сложение — это «часовая арифметика». Когда числа достигают предела, они сбрасываются в ноль.
Представьте циферблат часов с 12 делениями. Если сейчас 10 часов и вы прибавляете 5 часов, вы не получите 15 часов — вы получите 3 часа. Числа «оборачиваются», когда достигают 12.
Обычное сложение: 10 + 5 = 15 Часовая арифметика: 10 + 5 = 3 (mod 12)
В математической записи a + b mod p означает:
- Сложить a и b обычным образом
- Разделить на p
- Оставить только остаток
Примеры для mod 5 (представьте часы только с 5 делениями: 0, 1, 2, 3, 4):
1 + 2 = 3 mod 5 (3 < 5, без переполнения) 3 + 4 = 2 mod 5 (3 + 4 = 7, а 7 = 5 + 2, остаток 2) 4 + 4 = 3 mod 5 (8 = 5 + 3, остаток 3) 2 + 3 = 0 mod 5 (5 = 5 + 0, остаток 0)
Ключевой вывод: модулярная арифметика циклична. Числа образуют круг, а сложение означает вращение по этому кругу.
Терминология машинного обучения
Обучение нейронной сети означает подстройку её внутренних чисел до тех пор, пока она не начнёт выдавать правильные ответы.
Веса (weights): Настраиваемые числа внутри нейронной сети. Думайте о весах как о «ручках», которые сеть может крутить. Каждая ручка влияет на то, как сеть обрабатывает информацию. В сети могут быть миллионы таких ручек, и обучение означает поиск правильных настроек.
Функция потерь (training loss): Число, измеряющее, насколько неправильны ответы сети. Чем меньше — тем лучше. Если сеть предсказывает «7», когда ответ «3», потери возрастают. Цель обучения — минимизировать эти потери.
Переобучение (overfitting): Когда сеть запоминает конкретные обучающие примеры вместо изучения общих закономерностей. Как студент, который запоминает «ответ на вопрос 1 — это C» вместо понимания материала — он отлично сдаёт пробный тест, но проваливает настоящий экзамен с другими вопросами.
Регуляризация (regularization): Методы, препятствующие переобучению. Затухание весов (weight decay) — один из таких методов: он штрафует большие значения весов, поощряя более простые решения. Думайте об этом как о «налоге на сложность» — сеть платит за сложность, что подталкивает её к элегантным решениям, которые обобщаются.
MLP (многослойный перцептрон): «Думающая» часть нейронной сети. MLP — это стопка слоёв, где каждый слой — это набор нейронов (также называемых перцептронами). Каждый нейрон делает три вещи:
- Вычисляет взвешенную сумму входов (умножает каждый вход на вес, складывает)
- Добавляет смещение (константу)
- Применяет нелинейную функцию (например, ReLU, которая обнуляет отрицательные значения)
ОДИН НЕЙРОН (ПЕРЦЕПТРОН)
═══════════════════════════════════════════════════════════════
Входы Веса Сумма + Смещ. Нелинейность Выход
x₁ ──────────── w₁ ─────╲
╲
x₂ ──────────── w₂ ───────●────→ Σ + b ────→ ReLU ────→ y
╱
x₃ ──────────── w₃ ─────╱
y = ReLU(w₁x₁ + w₂x₂ + w₃x₃ + b)
ReLU(z) = max(0, z) ← выдаёт z, если положительно, иначе 0
MLP складывает много нейронов в слои и несколько слоёв в глубину:
АРХИТЕКТУРА MLP
═══════════════════════════════════════════════════════════════
Входной Скрытый слой 1 Скрытый слой 2 Выходной
слой (много нейронов) (много нейронов) слой
●─────────────● ●─────────────●
╲ ╱
●───────────────●─────────────────●───────────────●
╱ ╲ ╱ ╲
●─────────────●───●─────────────●───●─────────────●
╲ ╱ ╲ ╱
●───────────────●─────────────────●───────────────●
╱ ╲
●─────────────● ●─────────────●
Каждая стрелка представляет обучаемый вес.
«Глубокое обучение» = много скрытых слоёв.
Магия: набирая достаточно нейронов с нелинейностями, MLP может научиться вычислять почти ЛЮБУЮ функцию — включая тригонометрические тождества!
O-нотация: как масштабируются алгоритмы
O-нотация (O большое) описывает, как время работы алгоритма растёт с увеличением размера входных данных. Она отвечает на вопрос: «Если я удвою вход, насколько дольше это займёт?»
O-НОТАЦИЯ — ТИПИЧНЫЕ СКОРОСТИ РОСТА
═══════════════════════════════════════════════════════════════
O(1) Константа Одинаковое время независимо от размера входа
Пример: Поиск элемента по индексу в массиве
O(log N) Логарифм Удвоение входа добавляет фиксированную работу
Пример: Бинарный поиск (уменьшение области вдвое на каждом шаге)
O(N) Линейная Удвоение входа удваивает работу
Пример: Однократный проход по списку
O(N log N) Лог-линейная Чуть хуже линейной
Пример: Быстрые алгоритмы сортировки (сортировка слиянием, быстрая)
O(N²) Квадратичная Удвоение входа учетверяет работу
Пример: Сравнение каждой пары элементов (вложенные циклы)
O(2^N) Экспоненц. Добавление одного элемента удваивает работу
Пример: Проверка всех подмножеств
ВИЗУАЛИЗАЦИЯ РОСТА (время vs. размер входа N):
Время│ · O(N²)
│ ·
│ ·
│ ·
│ · ···· O(N log N)
│ · ····
│ · ····
│ · ···· ________ O(N)
│ · ··· _______
│ · ··· _____
│ · · ··· ______ ............ O(log N)
│ · ··· _____.............................
│····____........................................ O(1)
└─────────────────────────────────────────────────→ N
Почему это важно для данной статьи: Когда мы говорим, что квантовое преобразование Фурье выполняется за O((log N)²) по сравнению с O(N²) для классического ДПФ, мы имеем в виду:
- Классическое: 1000 точек → 1 000 000 операций
- Квантовое: 1000 точек → 100 операций (так как log₂(1000) ≈ 10)
Это ускорение в 10 000 раз — и разрыв растёт экспоненциально с N!
Кто такой Фурье?
Жан-Батист Жозеф Фурье (1768–1830) — французский математик и физик. Его жизнь охватила Французскую революцию (его дважды чуть не гильотинировали), египетский поход Наполеона (где он помог основать Институт Египта) и реставрацию монархии.
Великое открытие (1807): Изучая, как тепло распространяется через твёрдые тела, Фурье выдвинул революционное утверждение: любая периодическая функция, какой бы ломаной или нерегулярной она ни была, может быть записана как сумма гладких синусоидальных и косинусоидальных волн.
ОТКРЫТИЕ ФУРЬЕ
═══════════════════════════════════════════════════════════════
Любой периодический сигнал: Можно разложить на:
╱╲ ╱╲ ∿∿∿∿∿∿ (медленная волна)
╱ ╲ ╱ ╲ + ∿∿∿∿∿∿∿∿ (средняя волна)
╱ ╲ ╱ ╲ + ∿∿∿∿∿∿∿∿∿∿ (быстрая волна)
╱ ╲╱ ╲ + ...
«Прямоугольная волна» = Сумма синусоид на
частотах 1, 3, 5, 7, ...
Хронология:
- 1807: Фурье представляет свои идеи Французской академии (отклонено как недостаточно строгое!)
- 1822: Публикует Théorie analytique de la chaleur (Аналитическая теория тепла)
- 1820-е — наши дни: Методы Фурье становятся незаменимыми в физике, инженерии, обработке сигналов и теперь… в нейронных сетях
Ряды Фурье vs. преобразование Фурье:
- Ряды Фурье (1807): Разлагают периодические сигналы (повторяющиеся бесконечно)
- Преобразование Фурье (разработано позже): Расширяет идею на непериодические сигналы
- Дискретное преобразование Фурье (ДПФ): Версия для конечных списков чисел (то, что используют компьютеры)
Нейронная сеть в грокинге переоткрывает 200-летнее открытие Фурье: циклические паттерны естественно выражаются как суммы волн!
Что такое преобразование Фурье?
Преобразование Фурье — это математический инструмент, который раскладывает сигналы на составляющие частоты — как разделение белого света на радугу.
Основная идея: Любой паттерн, каким бы сложным он ни был, можно построить, складывая простые волны (синусоиды и косинусоиды) разных частот.
Сложный сигнал = (медленная волна) + (средняя волна) + (быстрая волна) + ...
Почему «частоты»? Представьте звуковую волну. Чистая музыкальная нота — это простая синусоида. Аккорд — это несколько нот (частот), сложенных вместе. Преобразование Фурье говорит вам, какие ноты составляют аккорд.
Синус и косинус: строительные блоки
Прежде чем идти дальше, визуализируем две фундаментальные волны:
ВОЛНЫ СИНУСА И КОСИНУСА (один полный цикл, 0° до 360°)
═══════════════════════════════════════════════════════════════════════════
cos(θ) sin(θ)
│ │
1 │ ╭───╮ 1 │ ╭───╮
│ ╱ ╲ │ ╱ ╲
│ ╱ ╲ │ ╱ ╲
0 ───┼─╱─────────╲───────── и 0 ────┼──────╱─────────╲──────
│╱ ╲ ╱ │ ╱ ╲ ╱
│ ╲ ╱ │ ╱ ╲ ╱
-1 │ ╰───╯ -1 │ ╱ ╰─╯
└──────────────────────→ θ └──────────────────────→ θ
0° 90° 180° 270° 360° 0° 90° 180° 270° 360°
начинается с 1 начинается с 0
пик при 0° пик при 90°
Ключевое наблюдение: Косинус и синус — это ОДНА И ТА ЖЕ волна, только сдвинутая на 90°!
ОБЕ ВОЛНЫ ВМЕСТЕ — Косинус опережает Синус на 90°
═══════════════════════════════════════════════════════════════════════════
1 │ C S
│ ╱ ╲ ╲ ╱ ╲
│ ╱ ╲ ╲ ╱ ╲
│ ╱ ╲ ╲ ╱ ╲
0 ├─╱───────╲────╲─────────────────────────╱───────╲─────────
│╱ ╲ ╲ ╱ ╲ ╱
│ ╲ ╲ ╱ ╲ ╱
-1 │ ╲ S C ╲──╱
└─────────────────────────────────────────────────────────→ θ
0° 90° 180° 270° 360°
C = cos(θ) ─── (сплошная)
S = sin(θ) - - (пунктирная)
При θ=0°: cos=1, sin=0 ← косинус на пике, синус на нуле
При θ=90°: cos=0, sin=1 ← косинус на нуле, синус на пике
При θ=180°: cos=-1, sin=0 ← косинус в минимуме, синус на нуле
При θ=270°: cos=0, sin=-1 ← косинус на нуле, синус в минимуме
Это фазовое соотношение в 90° критически важно — оно означает, что косинус и синус вместе могут описать ЛЮБУЮ точку на окружности!
Единичная окружность: где живут синус и косинус
Теперь красивая связь. Вместо того чтобы строить волны по времени, построим их как координаты:
ЕДИНИЧНАЯ ОКРУЖНОСТЬ — cos(θ) это x-координата, sin(θ) это y-координата
═══════════════════════════════════════════════════════════════════════════
90° (π/2)
sin(θ) = 1
│
│ • Точка под углом θ
╭───┼───╮ /
╱ │ ╲
╱ │ / ╲
╱ │ / ╲
│ │ / │
180° (π) ─────────┼─────────●─/──────┼───────── 0° (0)
cos(θ) = -1 │ │╱ │ cos(θ) = 1
│ │ │
╲ │ ╱
╲ │ ╱
╲ │ ╱
╰───┼───╯
│
sin(θ) = -1
270° (3π/2)
Любая точка на окружности: (cos θ, sin θ)
θ = 0°: (1, 0) ← крайняя правая точка
θ = 90°: (0, 1) ← верх
θ = 180°: (-1, 0) ← крайняя левая точка
θ = 270°: (0, -1) ← низ
θ = 45°: (0.71, 0.71) ← диагональ
Глубокое понимание: Точка, движущаяся по окружности с постоянной скоростью, вычерчивает ОБЕ волны — синуса и косинуса — одновременно, по одной для каждой координаты!
Понимание ‘i’ — мнимой единицы
Теперь нам нужно поговорить о i, мнимой единице. Не дайте названию вас обмануть — она совершенно реальна и необходима.
Проблема: Какое число, возведённое в квадрат, даёт -1?
- 1² = 1 (не -1)
- (-1)² = 1 (не -1)
- Никакое «обычное» число не работает!
Решение: Определим новое число i такое, что:
i² = −1
или эквивалентно: i = √(−1)
Что такое i на самом деле? Думайте о нём как об операторе поворота на 90°:
- Умножить на i один раз: поворот на 90° против часовой стрелки
- Умножить на i дважды: поворот на 180° (это i² = -1, что меняет знак!)
- Умножить на i трижды: поворот на 270°
- Умножить на i четырежды: поворот на 360° (вернулись в начало, i⁴ = 1)
СТЕПЕНИ i — Вращение в комплексной плоскости
═══════════════════════════════════════════════════════════════════════════
i
│
│ i¹ = i (поворот на 90°)
│
│
i² = -1 ──────────────┼────────────── i⁰ = 1
(180°) │ (0° / 360°)
│
│
│ i³ = -i (поворот на 270°)
-i
i⁴ = 1 (полный круг, вернулись в начало!)
Комплексные числа: Объединяют действительную и мнимую части:
z = a + bi
где a — это «действительная часть» (x-координата), а b — «мнимая часть» (y-координата).
Это даёт нам комплексную плоскость — двумерное пространство, где каждая точка — это число!
Понимание ‘e’ — числа Эйлера
e ≈ 2.71828… — это особое число, которое появляется повсюду в математике, особенно там, где речь идёт о росте и изменениях.
Что делает e особенным? Это единственное число, где скорость роста равна текущему значению. Если у вас есть e^x, его производная (скорость изменения) тоже равна e^x. Никакое другое основание не имеет этого свойства!
Формула Эйлера — самое красивое уравнение
Леонард Эйлер открыл поразительную связь:
e^(iθ) = cos(θ) + i·sin(θ)
Это означает: возведение e в мнимую степень даёт вам точку на единичной окружности!
ВИЗУАЛИЗАЦИЯ ФОРМУЛЫ ЭЙЛЕРА
═══════════════════════════════════════════════════════════════════════════
e^(iθ) = cos(θ) + i·sin(θ)
═══════════════════════════
Мнимая ось
│
│ • e^(iθ)
sin(θ) /│
│ / │
│ / │
│ / │
│ / θ │
Действ. ось ────────────────┼──●─────┴────────
│ └─────┘
│ cos(θ)
│
Точка e^(iθ) находится на единичной окружности под углом θ
Её координаты — (cos θ, sin θ)
Частные случаи:
e^(i·0) = 1 (угол 0°, точка (1,0))
e^(iπ/2) = i (угол 90°, точка (0,1))
e^(iπ) = -1 (угол 180°, точка (-1,0)) ← Тождество Эйлера!
e^(i·3π/2) = -i (угол 270°, точка (0,-1))
e^(i·2π) = 1 (угол 360°, вернулись в начало)
Почему это важно? Умножение комплексных экспонент СКЛАДЫВАЕТ их углы:
e^(iθ₁) × e^(iθ₂) = e^(i(θ₁ + θ₂))
Вот почему представление Фурье делает модулярное сложение простым — сложение чисел становится сложением углов!
Дискретное преобразование Фурье (ДПФ)
Теперь мы можем понять ДПФ. Оно работает с конечными списками чисел, выражая их через p различных частот:
Исходные: [a₀, a₁, a₂, ..., a_{p-1}]
↓ Преобразование Фурье
Частоты: [F₀, F₁, F₂, ..., F_{p-1}]
Каждая частотная компонента F_k соответствует волне, которая делает k полных циклов при обходе p точек.
Почему это важно для грокинга? Нейронная сеть обнаруживает, что модулярное сложение становится простым в базисе Фурье. В исходном представлении (сырые числа) сложение по модулю p кажется произвольным. В представлении Фурье (точки на окружности) сложение — это просто вращение — геометрически естественная операция.
Связь с единичной окружностью: корни из единицы
ДПФ использует корни из единицы — p равномерно расположенных точек на единичной окружности в комплексной плоскости.
Для mod 5 нам нужны корни 5-й степени из единицы: числа, которые дают 1 при возведении в 5-ю степень.
Это: ωᵏ = e^(2πik/5) для k = 0, 1, 2, 3, 4
КОРНИ 5-Й СТЕПЕНИ ИЗ ЕДИНИЦЫ — Правильный пятиугольник на единичной окружности
═══════════════════════════════════════════════════════════════════════════
ω⁰ = 1
(0°)
●
╱ ╲
╱ ╲
╱ ╲
ω¹ ╱ ╲ ω⁴
(72°) ● ● (288°)
╲ ╱
╲ ╱
╲ ╱
╲ ╱
╲ ╱
ω² ●───────● ω³
(144°) (216°)
Позиция Угол Форма Эйлера Координаты (cos, sin)
─────────────────────────────────────────────────────────────────────
0 0° e^(0) = 1 ( 1.000, 0.000)
1 72° e^(2πi/5) ( 0.309, 0.951)
2 144° e^(4πi/5) (-0.809, 0.588)
3 216° e^(6πi/5) (-0.809, -0.588)
4 288° e^(8πi/5) ( 0.309, -0.951)
─────────────────────────────────────────────────────────────────────
Ключевое свойство: ω⁵ = e^(2πi·5/5) = e^(2πi) = 1 (вернулись в начало!)
Поэтому это называется «mod 5» — после 5 шагов возвращаемся в начало.
Сложение как вращение
Вот волшебство: сложение чисел mod 5 = сложение углов = вращение вокруг пятиугольника!
ПРИМЕР: 1 + 3 = 4 (mod 5) как Вращение
═══════════════════════════════════════════════════════════════════════════
Начинаем в позиции 1 (угол 72°): Добавляем 3 (поворот на 216°):
0 0
● ●
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
● ● ● ●
1 ←(СТАРТ) 4 1 4 ←(ФИНИШ)
╲ ╱ ╲ ╱
╲ ╱ ╲ ╱
2───3 2───3
↑
(поворот через
позиции 2, 3)
Вычисление углов:
Позиция 1: θ₁ = 72°
Позиция 3: θ₃ = 216° (это «величина» поворота)
Сумма: θ₁ + θ₃ = 72° + 216° = 288° = позиция 4 ✓
Комплексное умножение:
e^(2πi·1/5) × e^(2πi·3/5) = e^(2πi·4/5)
(позиция 1) (позиция 3) (позиция 4)
Сеть это открывает! Вместо запоминания таблицы сложения 5×5 она учится:
- Помещать каждое число на его угол на окружности (эмбеддинг)
- Складывать углы с помощью тригонометрических тождеств (MLP)
- Считывать, на какую позицию попал результат (анэмбеддинг)
КАК MLP СКЛАДЫВАЕТ УГЛЫ — Пример тригонометрического тождества для 1 + 3 mod 5
═══════════════════════════════════════════════════════════════════════════
MLP не знает об углах напрямую. Он видит только координаты:
Вход 1: embed(1) = (cos 72°, sin 72°) = ( 0.309, 0.951)
Вход 3: embed(3) = (cos 216°, sin 216°) = (-0.809, -0.588)
Нейроны MLP учатся вычислять эти ПРОИЗВЕДЕНИЯ:
┌─────────────────────────────────────────────────────────────────┐
│ cos(72°) × cos(216°) = (0.309) × (-0.809) = -0.250 │
│ sin(72°) × sin(216°) = (0.951) × (-0.588) = -0.559 │
│ sin(72°) × cos(216°) = (0.951) × (-0.809) = -0.769 │
│ cos(72°) × sin(216°) = (0.309) × (-0.588) = -0.182 │
└─────────────────────────────────────────────────────────────────┘
│
▼
Затем КОМБИНИРУЮТ их, используя формулы сложения углов:
┌─────────────────────────────────────────────────────────────────┐
│ │
│ cos(72° + 216°) = cos(72°)cos(216°) − sin(72°)sin(216°) │
│ = (-0.250) − (-0.559) │
│ = -0.250 + 0.559 │
│ = 0.309 ✓ │
│ │
│ sin(72° + 216°) = sin(72°)cos(216°) + cos(72°)sin(216°) │
│ = (-0.769) + (-0.182) │
│ = -0.951 ✓ │
│ │
└─────────────────────────────────────────────────────────────────┘
│
▼
Выход: (0.309, -0.951)
│
▼
Это совпадает с позицией 4 на пятиугольнике!
(cos 288°, sin 288°) = (0.309, -0.951) ✓
═══════════════════════════════════════════════════════════════════════════
КЛЮЧЕВОЙ ВЫВОД: Нейроны MLP не «знают» тригонометрию.
Они просто выучивают веса, которые ОКАЗЫВАЮТСЯ реализующими эти формулы,
потому что это самый простой способ решить задачу!
Запоминание всех 25 пар вход-выход: требует ~25 «ячеек» памяти
Изучение трюка Фурье: требует ~4 нейрона (для произведений)
Затухание весов штрафует сложность → сеть находит элегантное решение.
Часть I: Открытие грокинга
Наблюдение OpenAI (2022)
Алетея Пауэр и её коллеги из OpenAI обучали небольшие трансформерные сети на простых алгоритмических задачах: модулярное сложение, модулярное деление, композиция перестановок.
Они заметили нечто странное.
Сети быстро запоминали обучающие данные — потери падали почти до нуля, точность на обучении достигала 100%. По стандартам машинного обучения: прекращай обучение, ты закончил.
Но они продолжали обучение. Ещё тысячи эпох ничего не происходило. Точность на тесте оставалась на уровне случая. Сеть запомнила, но не обобщила.
Затем внезапно — иногда после 10 000+ эпох — точность на тесте взлетала с ~0% до ~100% всего за несколько сотен шагов.
Они назвали это грокингом: внезапный переход от запоминания к обобщению, задолго после того, как обучающие данные были идеально подогнаны.
Почему «грокинг»?
Термин происходит из романа Роберта Хайнлайна «Чужак в чужой стране» (1961). «Грокнуть» означает понять что-то настолько глубоко, что вы становитесь с этим единым целым.
Сеть не просто запоминает — она грокает лежащую в основе структуру.
Ключевые условия
Грокинг требует:
- Маленький датасет: Большие датасеты не переобучаются полностью
- Затухание весов: Регуляризация, штрафующая большие веса
- Достаточное время обучения: Намного дольше, чем насыщение потерь на обучении
- Алгоритмическая задача: Проблемы с лежащей в основе структурой для открытия
Без затухания весов грокинг редко происходит. Сеть с удовольствием остаётся в своём запоминающем решении навсегда.
Часть II: Что внутри сети?
Архитектура
Стандартная установка для изучения грокинга на модулярной арифметике:
Вход: (a, b) как one-hot векторы
↓
Эмбеддинг слой: one-hot → плотные векторы
↓
Трансформер блок(и): внимание + MLP
↓
Выход: логиты по {0, 1, ..., p-1}
Для a + b mod p входы — два целых числа, выход — их сумма по модулю p.
Подробная диаграмма архитектуры: Вычисление 1 + 3 mod 5
═══════════════════════════════════════════════════════════════════════════════════
НЕЙРОННАЯ СЕТЬ ДЛЯ МОДУЛЯРНОГО СЛОЖЕНИЯ
═══════════════════════════════════════════════════════════════════════════════════
ВХОД ЭМБЕДДИНГ ВНИМАНИЕ MLP
(One-Hot) (Единичн. окр.) (Поток (Перцептроны) АНЭМБЕДДИНГ
информ.) (Выход)
┌─────────────┐ ┌─────────────┐ ┌───────────┐ ┌─────────────┐ ┌─────────┐
│ a=1 b=3 │ │ Позиция │ │ │ │ Триг. │ │ Логиты │
│ │ │ на окружн. │ │ Объедин. │ │ тождества │ │ │
├──┬──┬──┬────┤ ├─────────────┤ │ a и b │ │ в нейронах │ ├─────────┤
│0 │1 │ОП│ 0 │ │ •1 │ │ │ │ │ │ 0: 0.1 │
├──┼──┼──┼────┤ ══> │ · · │ ══> │ Q K V │ ══> │ cos×cos │ ══> ├─────────┤
│1 │0 │ │ 0 │ │ 0• •2 │ │ ↓ ↓ ↓ │ │ sin×sin │ │ 1: 0.2 │
├──┼──┼──┼────┤ │ · · │ │ Вним. │ │ cos×sin │ ├─────────┤
│0 │0 │ │ 0 │ │ •4 │ │ │ │ sin×cos │ │ 2: 0.1 │
├──┼──┼──┼────┤ │ 3• │ │ ↓ │ │ ↓ │ ├─────────┤
│0 │0 │ │ 1 │ ├─────────────┤ │ Выход │ │ Комбин. │ │ 3: 0.1 │
├──┼──┼──┼────┤ │ embed(1)= │ │ [e₁,e₃] │ │ со знак. │ ├─────────┤
│0 │0 │ │ 0 │ │(0.31, 0.95) │ │ │ │ ↓ │ │ 4: 0.5 │◄── МАКС
├──┼──┼──┼────┤ │ embed(3)= │ └───────────┘ │ (cos,sin) │ └─────────┘
│ │ │+ │ │ │(-0.81,-0.59)│ │ суммы │ ↓
└──┴──┴──┴────┘ └─────────────┘ └─────────────┘ Ответ: 4
═══════════
Механистическая интерпретируемость Нила Нанды (2023)
Нил Нанда и его коллеги вскрыли обученные сети, чтобы увидеть, как они вычисляют модулярное сложение. Их статья «Progress Measures for Grokking via Mechanistic Interpretability» раскрыла механизм.
Ответ: сеть изучает анализ Фурье.
Часть III: Механизм Фурье
Где живёт окружность?
Представление единичной окружности возникает в нескольких слоях, но каждый играет свою роль:
1. Эмбеддинг слой
Каждое входное число k ∈ {0, 1, …, p-1} отображается в вектор в ℝ^d.
После грокинга эти эмбеддинг-векторы содержат компоненты Фурье:
embed(k) ≈ Σf ( af·cos(2πfk/p), bf·sin(2πfk/p) )
Эмбеддинг учится размещать числа вокруг окружностей на разных частотах f.
Ключевой вывод: Эмбеддинг выполняет дискретное преобразование Фурье!
2. Слой внимания (если присутствует)
В трансформерах с вниманием этот слой в основном занимается:
- Перемещением информации между позициями (два входных числа)
- Не много «вычислений» для сложения — внимание полезнее для задач, требующих сравнения или копирования
Для простого сложения сеть ТОЛЬКО с MLP (без внимания) может грокнуть. Внимание полезно, но не обязательно для этой задачи.
3. MLP слои — где происходит магия
MLP — это место, где происходит фактическое вычисление (a + b) mod p.
MLP изучает тригонометрические формулы сложения:
cos(a + b) = cos(a)·cos(b) − sin(a)·sin(b)
sin(a + b) = sin(a)·cos(b) + cos(a)·sin(b)
Нейроны MLP реализуют эти тождества:
- Некоторые нейроны вычисляют произведения: cos(a) × cos(b), sin(a) × sin(b) и т.д.
- Другие нейроны вычисляют комбинации с соответствующими знаками
- Результат: cos(a+b) и sin(a+b) для различных частот
4. Анэмбеддинг слой
Финальный слой считывает угол и преобразует обратно в дискретный класс.
Он сравнивает вычисленные (cos(a+b), sin(a+b)) с каждой возможной выходной позицией на окружности и возвращает ближайшую.
Часть IV: Многомерная геометрия
Визуализация «куска пиццы»
Представьте пространство эмбеддингов (обычно d = 128 или 256 измерений).
В этом многомерном пространстве есть 2D-подпространство, содержащее окружность. Числа p расположены как вершины правильного p-угольника на этой окружности.
Но на самом деле таких окружностей НЕСКОЛЬКО — по одной для каждой частоты Фурье, которую использует сеть.
Многомерное пространство эмбеддингов (d = 128)
|
|--- 2D подпространство для частоты f=1: окружность с p точками
|--- 2D подпространство для частоты f=2: окружность с p точками (удвоенная частота)
|--- 2D подпространство для частоты f=3: ...
|--- ... (другие подпространства для других признаков)
Почему несколько частот?
Одной частоты достаточно для точного вычисления. Но сеть часто изучает несколько частот, потому что:
- Избыточность повышает устойчивость
- Разные частоты возникают независимо во время обучения
- Ландшафт потерь имеет несколько допустимых решений
Часть V: Внезапный переход
Фазовый переход
Грокинг происходит резко. Почему?
Во время обучения конкурируют ДВА решения:
- Запоминающий контур: Отображает каждый обучающий вход напрямую на его выход
- Обобщающий контур: Использует представление Фурье для всех входов
Оба присутствуют в сети одновременно! Веса содержат оба паттерна наложенными друг на друга.
Конкуренция
Раннее обучение:
- Запоминающий контур доминирует (быстрее учится, меньше начальные потери)
- Обобщающий контур зарождается, веса малы
- Потери на обучении: низкие. Потери на тесте: высокие.
Затухание весов постепенно разрушает запоминающий контур:
- Запоминание требует O(N) параметров для хранения N примеров
- Представление Фурье требует O(√N) параметров
- Затухание весов штрафует сложность → запоминание становится «дорогим»
Переход:
- В некоторой критической точке обобщающий контур становится выгоднее
- Сеть быстро переключается с одного решения на другое
- Точность на тесте скачет с ~0% до ~100% за десятки-сотни шагов
Измерение контуров
Нанда и др. разработали «меры прогресса» — способы обнаружить обобщающий контур до того, как произойдёт грокинг.
Ключевая мера: Компоненты Фурье в эмбеддинге
Даже когда точность на тесте равна нулю, можно измерить, насколько эмбеддинги похожи на моды Фурье. Этот сигнал растёт постепенно, а затем ускоряется прямо перед грокингом.
Вывод: Обобщение строится постепенно, но проявляется внезапно.
Часть VI: Пример — 1 + 3 mod 5
Проследим вычисление:
Входы
- a = 1, b = 3, p = 5
- Правильный ответ: 4
Эмбеддинг
Сначала установим позиции на единичной окружности для mod 5:
Позиция k → угол θₖ = 2πk/5 k=0: θ = 0° → (cos 0°, sin 0°) = ( 1.000, 0.000) k=1: θ = 72° → (cos 72°, sin 72°) = ( 0.309, 0.951) k=2: θ = 144° → (cos 144°, sin 144°) = (-0.809, 0.588) k=3: θ = 216° → (cos 216°, sin 216°) = (-0.809, -0.588) ← третья четверть! k=4: θ = 288° → (cos 288°, sin 288°) = ( 0.309, -0.951)
Примечание: 216° находится в третьей четверти, где И синус, И косинус отрицательны.
Для наших входов:
embed(1) ≈ (cos 72°, sin 72°) = ( 0.309, 0.951) embed(3) ≈ (cos 216°, sin 216°) = (-0.809, -0.588)
Вычисление MLP
MLP использует тригонометрические формулы сложения. Для углов θ₁ = 72° и θ₃ = 216°:
cos(θ₁ + θ₃) = cos(θ₁)cos(θ₃) - sin(θ₁)sin(θ₃)
= (0.309)(-0.809) - (0.951)(-0.588)
= -0.250 - (-0.559)
= -0.250 + 0.559
= 0.309 ✓
sin(θ₁ + θ₃) = sin(θ₁)cos(θ₃) + cos(θ₁)sin(θ₃)
= (0.951)(-0.809) + (0.309)(-0.588)
= -0.769 + (-0.182)
= -0.951 ✓
Результат: (0.309, -0.951)
Анэмбеддинг
Выход (0.309, -0.951) сравнивается с каждой позицией на окружности:
k=0: ( 1.000, 0.000) — расстояние от (0.309, -0.951): 1.23 k=1: ( 0.309, 0.951) — расстояние от (0.309, -0.951): 1.90 k=2: (-0.809, 0.588) — расстояние от (0.309, -0.951): 1.90 k=3: (-0.809, -0.588) — расстояние от (0.309, -0.951): 1.23 k=4: ( 0.309, -0.951) — расстояние от (0.309, -0.951): 0.000 ← ТОЧНОЕ СОВПАДЕНИЕ!
Позиция 4 побеждает! И действительно, 1 + 3 = 4 mod 5. ✓
Почему это работает
Углы складываются напрямую:
- Вход 1: угол = 72° = 2π/5 радиан
- Вход 3: угол = 216° = 6π/5 радиан
- Сумма: 72° + 216° = 288° = 8π/5 радиан
- Позиция 4 имеет угол: 288° = 8π/5 радиан ✓
Это эквивалентно умножению комплексных экспонент:
e^(2πi·1/5) × e^(2πi·3/5) = e^(2πi·4/5)
Сеть выучивает, что сложение индексов mod p — это то же самое, что сложение углов, что то же самое, что умножение точек на единичной окружности.
Часть VII: Связь с треугольниками и квантовой механикой
Треугольник как минимальный случай
Для mod 3:
0 = e^0 = 1
/\
/ \
/ \
1------2
1 = e^(2πi/3) 2 = e^(4πi/3)
Это И ЕСТЬ треугольник. Сложение mod 3 — это поворот на 120°.
Кубические корни из единицы:
- ω = e^(2πi/3) = -1/2 + i√3/2
- ω² = e^(4πi/3) = -1/2 – i√3/2
- ω³ = 1
Они удовлетворяют: 1 + ω + ω² = 0 (вершины в сумме дают ноль — глубокое свойство!)
Фаза в квантовой механике
Квантовые амплитуды — комплексные числа. Суперпозиция включает их сложение:
ψ_total = ψ₁ + ψ₂ = A₁·e^(iφ₁) + A₂·e^(iφ₂)
Фазы φ₁, φ₂ определяют интерференцию. Это в точности арифметика корней из единицы!
Когда квантовый компьютер выполняет сложение в суперпозиции, он использует ту же структуру Фурье, которую открыла нейронная сеть.
Реляционная интерпретация
В нашей реляционной рамке:
- Числа mod p — это не «вещи», это ОТНОШЕНИЯ (позиции на цикле)
- Операция (сложение) — это преобразование, сохраняющее структуру цикла
- Нейронная сеть обнаружила, что фундаментальны отношения, а не объекты
Треугольник в гильбертовом пространстве: квантовые связи
Структура единичной окружности, которую мы исследовали, не просто полезна для нейронных сетей — она основа квантовой механики. Та же геометрия, которая делает модулярное сложение элегантным, объясняет суперпозицию, принцип неопределённости и квантовое туннелирование.
Что такое гильбертово пространство?
Гильбертово пространство — это математическая арена, где происходит квантовая механика. Думайте о нём как об обобщении обычного пространства на потенциально бесконечное число измерений, где:
- Состояния — это векторы (стрелки) в этом пространстве
- Длина вектора представляет вероятность (должна равняться 1 для физических состояний)
- Углы между векторами представляют, насколько состояния «различны» или «перекрываются»
Ключевая особенность: квантовые амплитуды — комплексные числа — они имеют величину И фазу, как точки на единичной окружности!
Простейшая квантовая система: кубит
Кубит (квантовый бит) живёт на сфере Блоха, которая по сути является нашей единичной окружностью, расширенной до 3D:
СФЕРА БЛОХА — Пространство состояний кубита
═══════════════════════════════════════════════════════════════════════════
|0⟩ (спин вверх)
●
/│\
/ │ \
/ │ \
/ │ \
/ │ \ ← Любая точка на сфере
●─────┼─────● — допустимое состояние кубита!
/ │ \
/ │ \
/ │ \
/ │ \
●──────────●──────────●
/│\
/ │ \
/ │ \
●
|1⟩ (спин вниз)
Северный полюс: |0⟩ = определённо «0» (спин вверх)
Южный полюс: |1⟩ = определённо «1» (спин вниз)
Экватор: равная суперпозиция |0⟩ и |1⟩
Каждая другая точка: некоторая суперпозиция с ФАЗОЙ
Экватор сферы Блоха — это И ЕСТЬ наша единичная окружность! Точки на экваторе:
|ψ⟩ = (1/√2)(|0⟩ + e^(iφ)|1⟩)
Этот e^(iφ) — в точности тот фазовый множитель, который мы изучали!
Суперпозиция: быть в нескольких точках одновременно
В классических вычислениях (и в нашей нейронной сети) состояние — это ОДНА точка на окружности.
В квантовой механике состояние может быть суперпозицией — взвешенной суммой нескольких точек:
СУПЕРПОЗИЦИЯ — Квантовое отличие
═══════════════════════════════════════════════════════════════════════════
Классическое (нейросеть): Квантовое:
0 0
● ●
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
● ● ◐ ◐
1 4 1 4
╲ ╱ ╲ ╱
╲ ╱ ╲ ╱
2───3 2───3
↑
ОДНА позиция НЕСКОЛЬКО позиций
(ответ — 3) одновременно!
Классич.: Состояние — позиция 3 |ψ⟩ = α|0⟩ + β|1⟩ + γ|2⟩ + δ|3⟩ + ε|4⟩
Квантовое: Состояние — СУПЕРПОЗИЦИЯ где |α|² + |β|² + |γ|² + |δ|² + |ε|² = 1
всех позиций, каждая (вероятности должны суммироваться в 1)
с комплексной амплитудой
Почему существует суперпозиция: Уравнение Шрёдингера ЛИНЕЙНО. Если |ψ₁⟩ и |ψ₂⟩ — допустимые состояния, то α|ψ₁⟩ + β|ψ₂⟩ тоже допустимо. В математике ничто не принуждает к единственному ответу!
Принцип неопределённости: сопряжённые окружности
Вот где преобразование Фурье становится глубоким.
Положение и импульс в квантовой механике связаны преобразованием Фурье:
ψ̃(p) = (1/√(2πℏ)) ∫ ψ(x) e^(−ipx/ℏ) dx
Принцип неопределённости возникает потому, что:
- Состояние, локализованное в положении (острый пик), имеет РАЗМАЗАННЫЙ импульс (много частот)
- Состояние, локализованное в импульсе (одна частота), имеет РАЗМАЗАННОЕ положение
ПРИНЦИП НЕОПРЕДЕЛЁННОСТИ — Двойственность Фурье
═══════════════════════════════════════════════════════════════════════════
Пространство положений: Пространство импульсов:
(где частица?) (как быстро движется?)
СЛУЧАЙ 1: Точное положение
│ │ ∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿
│ ╱╲ │∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿
│ ╱ ╲ │∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿
└────╱────╲────→ x └─────────────────→ p
«Я знаю ГДЕ она» «ПОНЯТИЯ НЕ ИМЕЮ как быстро»
(узкий пик) (все частоты присутствуют)
СЛУЧАЙ 2: Точный импульс
│ ∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿ │
│∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿ │ ╱╲
│∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿ │ ╱ ╲
└─────────────────→ x └────╱────╲────→ p
«ПОНЯТИЯ НЕ ИМЕЮ где» «Я знаю КАК БЫСТРО»
(размазана везде) (одна частота)
ПРЕДЕЛ ГЕЙЗЕНБЕРГА: Δx · Δp ≥ ℏ/2
НЕЛЬЗЯ иметь одновременно точное положение И точный импульс.
Это не проблема измерения — это встроено в волновую структуру!
Квантовое туннелирование: когерентность фазы через барьеры
Туннелирование — квантовое явление, при котором частицы проходят через барьеры, которые классически не могли бы преодолеть. Единичная окружность объясняет почему.
КВАНТОВОЕ ТУННЕЛИРОВАНИЕ — Фаза делает это возможным
═══════════════════════════════════════════════════════════════════════════
Классическая частица, ударяющаяся о стену:
●→→→→│█████│ Частица отскакивает назад.
│█████│ У неё недостаточно энергии,
│█████│ чтобы перепрыгнуть барьер.
Квантовая частица, ударяющаяся о стену:
│█████│
∿∿∿∿∿∿∿→ │█████│ →∿∿
(волна с │█████│ (меньшая волна
амплитудой A) │█████│ амплитуда B)
│█████│
БАРЬЕР
Волна не останавливается на барьере — она ЭКСПОНЕНЦИАЛЬНО затухает внутри,
но если барьер достаточно тонкий, часть амплитуды просачивается!
Почему это происходит? Внутри барьера волновая функция становится:
ψ(x) = A·e^(−κx)
Волна не осциллирует — она затухает. Но она не становится мгновенно нулём. Если барьер достаточно тонкий, на другой стороне остаётся ненулевая амплитуда.
Связь с фазой: Вероятность туннелирования зависит от ФАЗОВЫХ соотношений — УГОЛ θ (фаза) сохраняется при туннелировании!
Треугольник как минимальная квантовая система
Почему треугольник продолжает появляться? Потому что это минимальная нетривиальная циклическая структура.
ТРЕУГОЛЬНИК: ПРОСТЕЙШИЙ КВАНТОВЫЙ ЦИКЛ
═══════════════════════════════════════════════════════════════════════════
Mod 2 (два состояния): Mod 3 (три состояния):
|0⟩ |0⟩
● ●
│ ╱ ╲
│ ← Просто переворот! ╱ ╲
│ (похоже на классич.) ╱ ╲
● ●───────●
|1⟩ |1⟩ |2⟩
Только две фазы: 0 и π Три фазы: 0, 2π/3, 4π/3
Мало места для ТЕПЕРЬ есть место для
квантовой странности настоящей интерференции!
ТРЕУГОЛЬНИК — это где квантовое поведение по-настоящему начинается:
|ψ⟩ = α|0⟩ + β|1⟩ + γ|2⟩
где α, β, γ — комплексные числа с |α|² + |β|² + |γ|² = 1
Фазы α, β, γ могут интерферировать конструктивно или деструктивно.
Это источник квантового вычислительного преимущества!
Кутрит: Трёхуровневая квантовая система (кутрит) использует именно эту треугольную структуру. Кутриты могут кодировать информацию эффективнее кубитов в некоторых протоколах, именно потому что треугольник допускает более богатые фазовые соотношения.
Итоги: от нейронных сетей к квантовой механике
Одна и та же математическая структура лежит в основе обоих:
| Грокинг нейросети | Квантовая механика |
|---|---|
| Числа mod p | Квантовые состояния в p-мерном гильбертовом пространстве |
| Эмбеддинг на единичной окружности | Комплексные амплитуды с фазой |
| Преобразование Фурье | Двойственность положение ↔ импульс |
| Сложение = вращение | Временная эволюция = вращение фазы |
| Пятиугольник (mod 5) | 5-уровневая квантовая система |
| Треугольник (mod 3) | Кутрит |
Нейронная сеть открыла то, что физики знали уже столетие: окружность — естественная геометрия циклических явлений, будь то модулярная арифметика или квантовая фаза.
Часть VII-Б: Квантовые вычисления и квантовое машинное обучение
Квантовые вычисления: родной язык окружностей
Классические компьютеры манипулируют битами (0 или 1). Квантовые компьютеры манипулируют кубитами — суперпозициями, живущими на единичной окружности.
КЛАССИЧЕСКИЕ vs КВАНТОВЫЕ ВЫЧИСЛЕНИЯ
═══════════════════════════════════════════════════════════════════════════
КЛАССИЧЕСКИЙ БИТ: КВАНТОВЫЙ КУБИТ:
Либо 0, либо 1 |ψ⟩ = α|0⟩ + β|1⟩
●───────● |0⟩
0 1 ●
/│\
Одно состояние за раз / │ \ ← Живёт на сфере Блоха
/ │ \
●───┼───●
│
●
|1⟩
КЛАССИЧ. ГЕЙТ (NOT): КВАНТОВЫЙ ГЕЙТ (Адамара H):
0 → 1 |0⟩ → (|0⟩ + |1⟩)/√2
1 → 0 |1⟩ → (|0⟩ - |1⟩)/√2
Переворачивает бит Создаёт СУПЕРПОЗИЦИЮ
Обе возможности сразу!
Квантовые гейты как вращения
Каждый квантовый гейт — это вращение на сфере Блоха. Та же геометрия, что лежит в основе грокинга!
РАСПРОСТРАНЁННЫЕ КВАНТОВЫЕ ГЕЙТЫ КАК ВРАЩЕНИЯ ═══════════════════════════════════════════════════════════════════════════ X гейт (NOT): Поворот на 180° вокруг оси X |0⟩ ↔ |1⟩ Z гейт: Поворот на 180° вокруг оси Z Меняет фазу: |1⟩ → -|1⟩ H гейт: Поворот на 90° + отражение Создаёт суперпозицию Rz(θ): Поворот на θ вокруг оси Z |1⟩ → e^(iθ)|1⟩ Та же ТРИГОНОМЕТРИЯ, которую открыл грокинг, встроена в квантовое железо!
Квантовое преобразование Фурье (КПФ)
Вот где становится красиво. Точное преобразование Фурье, которое нейронные сети изучают во время грокинга, является нативной квантовой операцией под названием Квантовое преобразование Фурье.
КВАНТОВОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ ═══════════════════════════════════════════════════════════════════════════ Классическое ДПФ на N точках: O(N²) операций Быстрое Преобр. Фурье: O(N log N) операций Квантовое Преобр. Фурье: O((log N)²) операций ← Экспоненциально быстрее! Выход: Равная суперпозиция всех |k⟩ с фазами e^(2πijk/N) Это ТОЧНО тот эмбеддинг Фурье, который выучила нейронная сеть!
КПФ преобразует вычислительные базисные состояния в фазовые состояния — КПФ АВТОМАТИЧЕСКИ размещает числа на единичной окружности!
Квантовое машинное обучение: грокинг со скоростью света
Квантовое машинное обучение (КМО) сочетает квантовые вычисления с архитектурами нейронных сетей. Ключевой вывод: если грокинг открывает представления Фурье, а квантовые компьютеры нативно выполняют преобразования Фурье, то квантовые компьютеры должны грокать естественно.
ВАРИАЦИОННАЯ КВАНТОВАЯ СХЕМА (ВКС)
═══════════════════════════════════════════════════════════════════════════
ВКС похожа на квантовую нейронную сеть:
Классич. нейросеть: Вариационная квантовая схема:
─────────────────── ────────────────────────────
Вход x Вход |x⟩ (закодирован как квант. состояние)
│ │
▼ ▼
┌─────────┐ ┌─────────┐
│ Слой 1 │ веса W₁ │ U(θ₁) │ углы поворота θ₁
│ ReLU │ │ (гейты) │
└────┬────┘ └────┬────┘
│ │
▼ ▼
┌─────────┐ ┌─────────┐
│ Слой 2 │ веса W₂ │ U(θ₂) │ углы поворота θ₂
│ ReLU │ │ (гейты) │
└────┬────┘ └────┬────┘
│ │
▼ ▼
Выход Измерение
Обучаемые параметры — это УГЛЫ ПОВОРОТА на сфере Блоха.
Это по своей сути «дружественно к Фурье» — представление встроено!
Квантовое преимущество для модулярного сложения
Для обучения модулярному сложению конкретно квантовые схемы имеют структурные преимущества:
ПОЧЕМУ КВАНТОВЫЕ СХЕМЫ ГРОКАЮТ «ЕСТЕСТВЕННО»
═══════════════════════════════════════════════════════════════════════════
Путь классической сети:
Вход (1,3) → Эмбеддинг → Внимание → MLP → Выход
учить учить учить
окружности «какой?» триг. тожд.
Должна ВЫУЧИТЬ представление Фурье с нуля
Занимает ~10⁵ шагов обучения для грокинга
Путь квантовой схемы:
Вход |1⟩|3⟩ → КПФ → Фазовый гейт → Обратн. КПФ → Измерение |4⟩
встр. встроенное встроенное
в! сложение!
Представление Фурье АВТОМАТИЧЕСКОЕ
Сложение — это фазовый гейт: e^(iθ₁) × e^(iθ₃) = e^(i(θ₁+θ₃))
Структуру, которую классическая сеть должна ОТКРЫТЬ,
квантовая схема ИМЕЕТ С САМОГО НАЧАЛА.
Как сделать грокинг «сверхъестественным»
Вопрос: Можем ли мы использовать квантовые эффекты, чтобы сделать грокинг не просто быстрее, а качественно другим?
1. Обучение в суперпозиции
Классическое обучение исследует одну конфигурацию весов за раз. Квантовый обучающийся мог бы исследовать все конфигурации одновременно:
СУПЕРПОЗИЦИЯ ПО ГИПОТЕЗАМ
═══════════════════════════════════════════════════════════════════════════
Классическое обучение: Квантовое обучение:
Шаг 1: Пробуем веса W₁ Шаг 1: Суперпозиция ВСЕХ весов
→ Получаем потери L₁ |ψ⟩ = Σᵢ |Wᵢ⟩
Шаг 2: Пробуем веса W₂ Шаг 2: Параллельная оценка
→ Получаем потери L₂ Σᵢ Loss(Wᵢ)|Wᵢ⟩
...10⁵ шагов... Шаг 3: Интерференция
Хорошие веса усиливаются
Шаг N: Наконец сходится! Плохие веса гасятся
Шаг 4: Измерение → Хорошие веса!
«Переход грокинга» мог бы произойти за ОДИН квантовый шаг
вместо тысяч классических шагов.
2. Квантовая интерференция выбирает решение Фурье
В классическом грокинге затухание весов медленно толкает сеть от запоминания к обобщению. Квантовая интерференция могла бы сделать это мгновенным:
КВАНТОВАЯ ИНТЕРФЕРЕНЦИЯ В ОБУЧЕНИИ
═══════════════════════════════════════════════════════════════════════════
Два конкурирующих решения:
ЗАПОМИНАНИЕ: ОБОБЩЕНИЕ:
└── Большой ||W|| └── Маленький ||W||
└── Случайная структура └── Структура Фурье
└── Работает на обучении └── Работает везде
Классич.: Затухание весов медленно штрафует запоминание
Грокинг занимает ~10⁵ шагов
Квант.: Подготовить суперпозицию обоих решений
Решение Фурье имеет ФАЗОВУЮ КОГЕРЕНТНОСТЬ
Решение-запоминание имеет СЛУЧАЙНЫЕ ФАЗЫ
После интерференции:
Когерентное (Фурье) → Усилено (конструктивная)
Некогерентное (память) → Погашено (деструктивная)
Элегантное решение побеждает благодаря ФИЗИКЕ, а не медленной оптимизации!
3. Квантовые ядерные методы
Многообещающий подход КМО: использовать квантовые схемы для вычисления ядерных функций, которые естественно захватывают циклическую структуру:
КВАНТОВОЕ ЯДРО ДЛЯ MOD p
═══════════════════════════════════════════════════════════════════════════
Классическое ядро: K(x, y) = мера сходства между x и y
Квантовое ядро: K(x, y) = |⟨φ(x)|φ(y)⟩|²
где |φ(x)⟩ — квантовое кодирование x
Для mod p сложения используем КПФ кодирование:
|φ(x)⟩ = КПФ|x⟩ = (1/√p) Σₖ e^(2πixk/p) |k⟩
Тогда ядро:
K(x, y) = |⟨φ(x)|φ(y)⟩|² = |(1/p) Σₖ e^(2πi(y-x)k/p)|²
= 1 если x = y
= 0 иначе (ортогональны на окружности!)
Это ядро ТОЧНО захватывает модулярную структуру.
Обучение не требуется — оно встроено в квантовое кодирование!
Схема для треугольника: минимальный квантовый грокинг
Для mod 3 (треугольник) мы можем построить явную квантовую схему:
СХЕМА СЛОЖЕНИЯ ДЛЯ ТРЕУГОЛЬНИКА (mod 3)
═══════════════════════════════════════════════════════════════════════════
Используем КУТРИТ (3-уровневая система): |0⟩, |1⟩, |2⟩
│1⟩
●
╱ ╲
╱ ╲
╱ ╲
●───────●
│0⟩ │2⟩
Вход: |a⟩|b⟩ (два кутрита)
Схема:
┌─────┐ ┌───────────────┐ ┌──────┐
|a⟩ ─────┤ КПФ ├─────┤ ├─────┤ КПФ† ├───── |a+b mod 3⟩
└─────┘ │ Управляемый │ └──────┘
│ фазовый │
┌─────┐ │ │
|b⟩ ─────┤ КПФ ├─────┤ гейт ├───────────────── (отбрасывается)
└─────┘ └───────────────┘
Управляемый фазовый гейт складывает углы:
|ω^a⟩|ω^b⟩ → |ω^(a+b)⟩|ω^b⟩
где ω = e^(2πi/3)
Эта схема выполняет сложение mod 3 за O(1) операций!
Грокинг МГНОВЕНЕН, потому что структура встроена.
Итоги: от классического грокинга к квантовому
ЭВОЛЮЦИЯ «ПОНИМАНИЯ» МОДУЛЯРНОГО СЛОЖЕНИЯ
═══════════════════════════════════════════════════════════════════════════
Уровень 0: Человеческое запоминание
«1+2=3, 2+2=4, 3+2=0, ...»
Нет структуры, просто таблица поиска
Уровень 1: Классическая нейросеть (до грокинга)
Запоминает обучающие примеры
Проваливается на тестовых примерах
Уровень 2: Классическая нейросеть (после грокинга)
Открывает представление Фурье
Обобщает идеально
Занимает ~10⁵ шагов, чтобы найти структуру
Уровень 3: Квантовая нейросеть
Структура Фурье встроена в КПФ
Сложение нативно (умножение фаз)
Грокает за O(1) с экспоненциально меньшим числом параметров
Уровень 4: Чистая квантовая схема
Обучение вообще не нужно!
mod p сложение — это просто: КПФ → Фазовый гейт → КПФ†
Мгновенный «грокинг» — или скорее, нет грокинга, потому что
представление никогда НЕ БЫЛО не-Фурье
Прогрессия:
МЕДЛЕННОЕ ОБУЧЕНИЕ → ГРОКИНГ → НАТИВНОЕ ПОНИМАНИЕ
Квантовая механика делает циклическую структуру «сверхъестественной»,
потому что квантовая механика И ЕСТЬ циклическая структура (фазы, окружности, волны).
Открытые вопросы в квантовом грокинге
- Квантовое преимущество: Может ли квантовое МО продемонстрировать доказуемое ускорение для открытия алгебраической структуры?
- Устойчивость к шуму: Реальные квантовые компьютеры имеют ошибки. Выживает ли структура Фурье при декогеренции?
- За пределами циклических групп: Грокинг работает для mod p. Могут ли квантовые методы расшириться на неабелевы группы? (Подсказка: это связано с алгоритмом Шора!)
- Гибридные подходы: Могут ли классические сети с квантово-вдохновлёнными слоями (КПФ регуляризация) грокать быстрее?
- Мета-вопрос: Если квантовые компьютеры «понимают» модулярное сложение нативно, что это говорит о природе математического понимания?
Часть VIII: Почему это важно
Для интерпретируемости ИИ
Грокинг показывает, что нейронные сети могут открывать элегантные математические структуры — но только после продолжительного обучения. Обучение представлениям отделено от подгонки данных.
Это имеет значение для:
- Как долго обучать модели
- Роли регуляризации
- Понимания того, что сети «действительно знают»
Для математики
Сеть независимо открыла анализ Фурье, 200-летнюю математическую технику. Это предполагает:
- Математические структуры «естественны» — открываемы из примеров
- Может существовать единственное (или небольшой набор) оптимальное представление для данных задач
- Нейронные сети как инструменты математического открытия?
Для физики
Круговое представление для циклических групп отражает:
- Квантовую фазу (U(1) симметрия)
- Вращательную симметрию (SO(2))
- Связь между алгеброй и геометрией
Сеть нашла ту же структуру, которую используют физики.
Упражнения
- Проверьте эмбеддинг Фурье: Для mod 7 выпишите корни 7-й степени из единицы. Проверьте, что 3 + 5 = 1 mod 7 соответствует правильному сложению фаз.
- Свойство треугольника: Докажите, что 1 + ω + ω² = 0 для ω = e^(2πi/3). (Подсказка: геометрическая прогрессия или прямое вычисление)
- Затухание весов: Если запоминание требует ||W|| ~ N, а обобщение требует ||W|| ~ √N, и потери = L_data + λ||W||², объясните, почему большое λ благоприятствует обобщению.
- Фазовый переход: В статистической механике фазовые переходы происходят, когда свободная энергия F = E – TS меняет свой минимум. По аналогии, что играет роль энергии и энтропии в грокинге?
- Внимание vs MLP: Разработайте эксперимент для определения того, необходимо ли внимание для грокинга mod p сложения. Что бы вы варьировали?
Литература
- Power, A. et al. (2022). “Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets.” arXiv:2201.02177
- Nanda, N. et al. (2023). “Progress Measures for Grokking via Mechanistic Interpretability.” ICLR 2023.
- Liu, Z. et al. (2022). “Towards Understanding Grokking: An Effective Theory of Representation Learning.” NeurIPS 2022.
- Heinlein, R. (1961). Stranger in a Strange Land. (Происхождение «grok»)
Резюме
Грокинг был открыт в 2022 году, когда исследователи OpenAI обнаружили, что нейронные сети внезапно обобщают задолго после запоминания обучающих данных. Механистическая интерпретируемость раскрыла механизм: сети изучают представления Фурье, где числа mod p становятся вершинами правильного p-угольника на единичной окружности в пространстве эмбеддингов. Эмбеддинг-слой учится размещать входы на окружности; MLP-слои учат тригонометрические тождества для вычисления сложения; анэмбеддинг считывает результат. Переход внезапен, потому что два контура (запоминающий и обобщающий) конкурируют, при этом затухание весов постепенно благоприятствует более простому решению Фурье. Когда обобщающий контур становится выгоднее, производительность скачет дискретно — фазовый переход от механического запоминания к подлинному пониманию.
Треугольник (mod 3) — минимальный случай: три кубических корня из единицы, 120° друг от друга, замкнутые относительно сложения.