Абстрактная алгебра в ML

Почему свёрточные сети работают? Теорема о G-эквивариантных слоях: CNN - единственный линейный слой, эквивариантный к трансляциям. Почему трансформеры обрабатывают последовательности? Deep Sets: перестановочно эквивариантная архитектура. Абстрактная алгебра не просто «описывает» нейросети - она диктует, какие архитектуры возможны.

• AlphaFold 2: SE(3)-эквивариантная нейросеть для предсказания структуры белка - теория групп Эйлера-3
• Граф-трансформеры: attention эквивариантен к S_n через механизм масок - теорема Кэли
• JAX/автодифференцирование: AD как функтор на категории дифференцируемых программ

Предварительные знания

• Representation Theory: Advanced Topics

Симметрии и G-equivariant нейросети

**G-инвариантная функция:** f: X → Y, где G действует на X, называется инвариантной, если f(g·x) = f(x) для всех g ∈ G. **G-эквивариантная функция:** f: X → Y, где G действует и на X и на Y, эквивариантна, если f(g·x) = g·f(x). **Теорема (Мейрон и др., 2019):** Любой линейный слой, эквивариантный к действию группы G, параметризуется пространством интервинорных отображений Hom_G(X, Y) - G-эквивариантных линейных отображений. **Архитектуры:** - **CNN** - эквивариантны к трансляциям Z^d (группа трансляций) - **GNN (граф)** - эквивариантны к перестановкам узлов S_n - **E(3)-нейросети** - эквивариантны к евклидовым преобразованиям (вращения + отражения + трансляции) - важны для молекул **Теорема об универсальности:** Инвариантные нейросети (pooling + эквивариантные слои) - универсальные аппроксиматоры для непрерывных G-инвариантных функций.

**Теорема о Schur-Weyl:** Представления GL(V) и S_n на V^{⊗n} коммутируют: пространство V^{⊗n} разлагается в прямую сумму ⊕ λ W_λ ⊗ V_λ, где W_λ - неприводимые S_n-модули (таблицы Юнга), V_λ - неприводимые GL(V)-модули. Это объясняет, почему attention-механизм в трансформерах (V^{⊗n} для n токенов) эквивариантен к перестановкам.

Теорема Кэли и перестановочная эквивариантность

**Теорема Кэли:** Любая группа G изоморфна подгруппе симметрической группы Sym(G). Явно: G ↪ Sym(G) через левые умножения: g ↦ (h ↦ gh). **Следствие для ML:** Любое действие группы G на множестве X сводится к действию перестановок на элементах X. Это обосновывает, почему достаточно изучать **перестановочно эквивариантные** нейросети - они охватывают все симметрии через теорему Кэли. **Deep Sets (Zaheer et al., 2017):** Функция f: Multiset(X) → Y инвариантна к перестановкам ⟺ f({x₁,...,xₙ}) = ρ(∑ᵢ φ(xᵢ)) для некоторых φ: X→ℝ^d, ρ: ℝ^d→Y. **Архитектурный принцип:** φ - поэлементная обработка (эквивариантна к S_n), ∑ - перестановочно инвариантный aggregation, ρ - обработка агрегированного. Это полный функциональный класс инвариантных функций! **Граф-нейросети (GNN):** Для графа G = (V, E) с матрицей смежности A: GNN-слой F(X, A) перестановочно эквивариантен к перестановкам узлов ⟺ F(PXPᵀ, PAP) = PF(X,A) для любой матрицы перестановок P.

**Теорема Мейрона-Азизяна (2019):** Полный функциональный класс перестановочно инвариантных/эквивариантных функций над множествами = DeepSets-архитектура (φ+∑+ρ). Это объясняет, почему несмотря на огромное разнообразие архитектур GNN, все они сводятся к одному принципу: поэлементная φ + инвариантное агрегирование + выходная ρ.

Нормализация как гомоморфизм и обратное распространение

**Гомоморфизм как принцип нормализации:** BatchNorm, LayerNorm, GroupNorm - все они нормализуют активации линейным преобразованием. Это гомоморфизм аффинной группы: φ(x) = γ·(x-μ)/σ + β сохраняет аффинную структуру вычислений. **Аргумент симметрии:** Если обучение инвариантно к масштабированию активаций (что часто выполнено), то нормализация - проекция на орбиту группы масштабирований ℝ*. **Теория категорий и обратное распространение:** - Нейросеть = морфизм в категории гладких функций - Прямой проход = применение морфизма - Обратное распространение = применение двойственного морфизма (ко-морфизм) - Это **функтор** из категории вычислительных графов в категорию касательных пространств! **Автоматическое дифференцирование (AD):** Прямой режим: вычисляет Якобиан·вектор (JVP - Jacobian-vector product) Обратный режим: вычисляет вектор·Якобиан (VJP - vector-Jacobian product) AD - это функтор (comonad) на категории дифференцируемых программ: он сохраняет состав функций и тождественные отображения.

**Lenses и AD:** В функциональном программировании оптики (lenses) - это морфизмы в категории, где каждый морфизм f: A → B несёт пару (forward: A→B, backward: A×B→A). Это в точности структура AD. Линза = дифференцируемая функция! Библиотека JAX использует именно этот принцип: vmap, jit, grad - функторы над функциями.

Ключевые идеи

• G-эквивариантный слой: f(g·x) = g·f(x) - симметрии сохраняются
• Теорема Кэли: G ↪ Sym(G) - любая группа = группа перестановок → перестановочной эквивариантности достаточно
• Deep Sets: f({xᵢ}) = ρ(∑φ(xᵢ)) - полный класс S_n-инвариантных функций
• Обратное распространение = функтор D(f∘g) = D(f)∘D(g) - цепное правило как функториальность

Дальнейшие пути

Алгебра в ML - активная область исследований. Теория представлений объясняет архитектуры; теория категорий - автодифференцирование и компилятор ML. Дальнейшее изучение: алгебраическая геометрия для оптимизации (многообразия потерь), нонкоммутативная геометрия для квантового ML.

• Теория представлений: продвинутые темы — Теорема Шур-Вейля объясняет трансформеры: attention на V^⊗n эквивариантен к S_n через разложение Шур-Вейля
• Алгебраическая геометрия — Многообразие потерь нейросети - алгебраическое многообразие; седловые точки = особые точки; алгебраическая геометрия изучает их

Вопросы для размышления

• Докажите, что свёрточный слой (1D циклическая свёртка) является единственным линейным слоем, эквивариантным к циклическому сдвигу Z/nZ, с точностью до масштабирования.
• Реализуйте SE(2)-эквивариантный слой для 2D изображений (эквивариантный к вращениям и трансляциям на плоскости). Какую структуру должно иметь ядро?
• Объясните категориальный смысл BatchNorm: как нормализация взаимодействует с функтором дифференцирования D? Является ли BatchNorm + Linear слой D-функториальным (цепное правило применимо)?

Связанные уроки

• la-01-vectors-intro