Линейная алгебра

Умножение матриц: движок нейросетей

Цели урока

Знать формулу $C_{ij} = \sum_k A_{ik} B_{kj}$ и правило размерностей $(m \times n) \cdot (n \times p) = (m \times p)$
Понимать, почему $AB \neq BA$, но $(AB)C = A(BC)$ - и как ассоциативность даёт 50x ускорение в LLM
Видеть в Linear-слое, attention и forward pass нейросети одну и ту же matmul-операцию
Применять правила $(AB)^T = B^T A^T$ и $(AB)^{-1} = B^{-1} A^{-1}$ в backprop и нормальном уравнении
Различать наивный $O(n^3)$, Штрассен $O(n^{2.807})$ и GPU GEMM по практической применимости

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

Векторы и операции с ними (сложение, скалярное умножение)
Скалярное произведение (dot product) и его геометрический смысл
Базовое представление о матрицах и Linear-слое нейросети

GPT-4 делает 1.8 триллиона операций умножения матриц на один токен. Не "математических операций вообще" - именно matmul. Каждый Linear слой, каждый attention head, каждый батч в любой нейросети мира - это одна и та же примитивная операция, разогнанная до 989 TFLOPS на H100.

**Linear layer** (PyTorch nn.Linear): $y = Wx + b$ - базовый строительный блок BERT, GPT, ResNet, ViT, всех нейросетей
**Self-attention** (Transformer): три matmul на один head ($X W_q$, $QK^T$, $\text{attn} \cdot V$); 96 слоёв × 96 голов в GPT-4
**cuBLAS GEMM** (NVIDIA, 1990-е): A100 = 312 TFLOPS, H100 = 989 TFLOPS FP16; весь deep learning сводится к этой библиотеке
**FlashAttention** (Tri Dao, 2022): IO-aware tiling в SRAM - 5-10x ускорение и 20x меньше памяти; основа Llama-3, Mistral
**Batched matmul на TPU MXU**: 128×128 systolic array Google - один такт даёт 16 384 умножения; обучение PaLM, Gemini
**MoE sparse matmul** (Mixtral, GPT-4): только 2 из 8 экспертов активны на токен - 4x меньше FLOPs при том же качестве

Сильвестр и Кэли - рождение матричной алгебры

В 1850 году Джеймс Джозеф Сильвестр впервые употребил слово "матрица" (matrix) в современном математическом смысле - в статье о определителях. Через восемь лет, в 1858 году, его друг Артур Кэли опубликовал "A Memoir on the Theory of Matrices" - первую систематическую работу, формализовавшую умножение матриц именно в той форме "строка на столбец", которую мы используем сегодня. Кэли заметил, что матрицы можно складывать, умножать и обращать - и эти операции образуют алгебру, в которой коммутативность нарушена. Через 90 лет, в 1943 году, Маккаллок и Питтс предложили модель искусственного нейрона как взвешенной суммы - то есть как одной строки матричного умножения. От Кэли до GPT-4 - прямая линия в 166 лет.

Современный deep learning - это компьютерная реализация ассоциативной некоммутативной алгебры Кэли на параллельном железе

Что такое умножение матриц

**GPT-4 делает 1.8 триллиона операций умножения матриц на один токен.** Не "математических операций" вообще - именно matmul. Каждый Linear слой, каждый шаг self-attention, каждый батч через сеть - это перемножение матриц. Правило смотрится странно (строки на столбцы, порядок важен), но именно эта странность делает matmul идеальным языком для композиции линейных функций - того самого, на чём построены нейросети и LLM.

**Формула:** $C_{ij} = \sum_k A_{ik} B_{kj}$. Элемент $C_{ij}$ - это скалярное произведение i-й строки матрицы A на j-й столбец матрицы B. Иначе говоря, dot product всех пар строка/столбец, упакованный в одну операцию.

Правило размерностей

ПРАВИЛО: (m x n) * (n x p) = (m x p) ^-------^ Должны совпадать! ЧТО СОВПАДАЕТ: число столбцов первой = числу строк второй ПРИМЕРЫ из реального ML: (32 x 768) * (768 x 3072) = (32 x 3072) OK [batch * W_ff в трансформере] (32 x 64) * (64 x 64) = (32 x 64) OK [batched attention head] (32 x 768) * (512 x 768) = ОШИБКА! FAIL [несовпадение] В ATTENTION-БЛОКЕ: Q: (seq x d_k), K: (seq x d_k) Q * K^T: (seq x d_k) * (d_k x seq) = (seq x seq) Получается квадратная матрица внимания seq x seq

Linear layer как первое применение

W = [[w11 w12 w13] x = [x1] b = [b1] [w21 w22 w23]] [x2] [b2] [x3] y = W*x + b: y1 = w11*x1 + w12*x2 + w13*x3 + b1 y2 = w21*x1 + w22*x2 + w23*x3 + b2 КАЖДЫЙ ВЫХОД - взвешенная сумма ВСЕХ входов. ДЛЯ GPT-2 FFN (n=768, m=3072): - W содержит 768*3072 = 2 359 296 весов - Один forward: 2.3M умножений-сложений - Батч из 512 токенов: ~1.2 миллиарда операций НА ОДИН СЛОЙ - 96 слоёв * 1.2B = 115 миллиардов операций на батч

**Почему правило "строка на столбец" именно такое**: это не случайность. Это единственный способ определить умножение так, чтобы оно совпало с **последовательным применением линейных функций**. Сеть из 96 слоёв GPT-4 - это 96-кратная композиция, записанная как произведение 96 матриц.

AB = BA - умножение матриц должно быть коммутативным как умножение чисел

В общем случае AB ≠ BA. Порядок матриц определяет порядок применения линейных трансформаций

Матрица - это функция из одного пространства в другое. AB означает "сначала B, потом A". "Повернуть, потом отразить" даёт не тот же результат, что "отразить, потом повернуть". Числа коммутируют, потому что это скаляры; матрицы - это операторы, и в общем случае операторы не коммутируют. Простой контрпример: для матриц поворота на 90° R и зеркального отражения F композиции R·F и F·R дают разные финальные ориентации.

Произведение матриц A (4 × 7) и B (7 × 3) имеет какой размер?

Свойства: что сохраняется, что нет

Не каждое привычное свойство арифметики сохраняется. Коммутативность - погибла. Ассоциативность - уцелела и стала важнейшим инструментом оптимизации в LLM-инференсе. Дистрибутивность работает. Транспонирование переворачивает порядок. Каждое свойство имеет прямую цену в TFLOPS на A100.

Свойство	Формула	ML-применение
Ассоциативность	$(AB)C = A(BC)$	Matmul fusion в PyTorch/XLA: компилятор переставляет порядок ради экономии FLOPs
Дистрибутивность	$A(B+C) = AB + AC$	Разделение веса: $W \cdot x = W_1 \cdot x + W_2 \cdot x$ при разбиении весов на чипы
Identity	$AI = IA = A$	Residual connections (ResNet, Transformer): $\text{out} = x + F(x)$
Транспонирование	$(AB)^T = B^T A^T$	Backpropagation: градиент через matmul - умножение на транспонированную матрицу
Обратная	$(AB)^{-1} = B^{-1} A^{-1}$	Нормальное уравнение, ridge regression, undistortion камеры
Определитель	$\det(AB) = \det A \cdot \det B$	Normalizing flows: log-det Jacobian для вероятностей
Не коммутативно	$AB \neq BA$	Порядок слоёв нейросети не переставляется - другая архитектура

Ассоциативность как 55-кратное ускорение

ЗАДАЧА: посчитать A * B * C, где A: (100 x 10) B: (10 x 100) C: (100 x 1) СПОСОБ 1: (A*B)*C A*B = (100x10)*(10x100) = (100x100) -> 100*10*100 = 100 000 операций (A*B)*C = (100x100)*(100x1) = (100x1) -> 100*100*1 = 10 000 операций ИТОГО: 110 000 операций СПОСОБ 2: A*(B*C) B*C = (10x100)*(100x1) = (10x1) -> 10*100*1 = 1 000 операций A*(B*C) = (100x10)*(10x1) = (100x1) -> 100*10*1 = 1 000 операций ИТОГО: 2 000 операций ВЫИГРЫШ: 55x при идентичном математическом результате Это matrix chain multiplication - классическая DP-задача (O(n^3) на оптимизацию). PyTorch JIT и XLA-компилятор находят оптимальный порядок автоматически.

**Главная ловушка транспонирования**: $(AB)^T = B^T A^T$, **НЕ** $A^T B^T$. Порядок переворачивается. Это критично в backpropagation: градиент по входу слоя $W \cdot x$ - это $W^T \cdot \nabla y$, и при цепочке слоёв порядок умножений в прямом и обратном проходе зеркально противоположный.

$(AB)^T = A^T B^T$ - транспонирование распределяется по умножению как обычно

$(AB)^T = B^T A^T$ - порядок переворачивается

Это прямое следствие правила композиции функций: транспонирование меняет роли строк и столбцов, а значит меняет роль "входа" и "результата" каждой матрицы. Аналогично с обратной: $(AB)^{-1} = B^{-1} A^{-1}$ - чтобы откатить "сначала B, потом A", нужно сначала откатить A, потом B (как при снимании двух свитеров). Эта переворачиваемость прямо проявляется в backprop: forward $y = W_3 W_2 W_1 x$, backward $\nabla_x = W_1^T W_2^T W_3^T \nabla_y$ - порядок зеркальный.

Геометрия: композиция линейных карт

Матрица $W$ размера $(m \times n)$ - это **линейная функция** из n-мерного пространства в m-мерное. Применить функцию к вектору - это умножить на него. Произведение матриц - это **композиция** функций. Двигатель сети из 96 слоёв буквально читается как $W_{96} \cdot W_{95} \cdot \ldots \cdot W_1 \cdot x$, где каждая матрица переводит представление из одного латентного пространства в следующее.

v -> A*v -> B*(A*v) = (B*A)*v ПОРЯДОК ПРИМЕНЕНИЯ: Сначала A (стоит правее), потом B (стоит левее) Читаем СПРАВА НАЛЕВО В НЕЙРОСЕТИ: out = W3 * (W2 * (W1 * x)) = (W3 * W2 * W1) * x Сначала W1 (ближайший к x), потом W2, потом W3 В записи слева направо это смотрится "задом наперёд" ГЕОМЕТРИЯ: R(theta) = поворот на theta S(k) = масштабирование в k раз R(45) * S(2): сначала растягиваем, потом вращаем S(2) * R(45): сначала вращаем, потом растягиваем Итоговая ориентация фигуры - разная!

Поворот на 90° + масштабирование в 2 раза

R = [[0, -1], [1, 0]] - поворот на 90° против часовой S = [[2, 0], [0, 2]] - масштабирование в 2 раза Точка p = (1, 0). R*S*p: S*p = (2, 0) R*(S*p) = (0, 2) - сначала растянули в (2,0), потом повернули в (0,2) S*R*p: R*p = (0, 1) S*(R*p) = (0, 2) - повернули в (0,1), потом растянули в (0,2) ЗДЕСЬ результат СОВПАЛ - но это особый случай: масштабирование изотропно (одинаково по осям) и коммутирует с поворотом. Стоит сделать масштабирование анизотропным diag(2, 1) - и результат разойдётся.

**Собственные векторы переживают композицию.** Если $v$ - собственный вектор A с собственным значением $\lambda$, то $A^n v = \lambda^n v$ - направление сохраняется при любом числе применений A. Это основа собственных векторов, PageRank (доминантный собственный вектор графа ссылок) и спектральной кластеризации.

В записи $W_3 W_2 W_1 x$ какая матрица применяется к вектору $x$ первой?

Matmul в ML-стеке: от Linear до FlashAttention

**Весь современный deep learning сводится к одной операции - matmul.** Linear слой, attention head, embedding lookup, batched inference - всё одна и та же primitive, разогнанная до 312 TFLOPS на A100, 989 TFLOPS на H100. NVIDIA построила империю на cuBLAS GEMM. Google - на TPU MXU (matrix multiply unit). FlashAttention переписала весь attention ради одного: больше matmul на меньшем кэше.

Self-attention: три matmul на один токен

**Бухгалтерия трансформера**: один attention head = 3 проекции + 2 attention matmul = 5 matmul. GPT-4 имеет ~96 слоёв × ~96 голов × 5 ≈ 46 080 matmul на forward pass одного токена. Плюс FFN (2 matmul на слой) - итого ~50К matmul на токен. Умножение матриц - не одна из операций, а **главная и почти единственная**.

Стек ускорения matmul

Уровень	Технология	Что делает
Алгоритм	Naive O(n³) → Strassen O(n^2.807)	Менее операций; редко используется - плохо параллелится
Библиотека CPU	OpenBLAS, MKL, BLIS	SIMD-оптимизация, cache blocking, ~50-100x от наивного Python
GPU kernel	cuBLAS GEMM (CUDA)	Tensor Cores: A100 = 312 TFLOPS, H100 = 989 TFLOPS на FP16
TPU hardware	MXU (128×128 systolic array)	Один такт = 16 384 умножения; vMAC за такт
Sparsity	Block-sparse, MoE	Mixtral, GPT-4: только 2 из 8 экспертов активны - 4x меньше matmul
IO-aware	FlashAttention (Tri Dao, 2022)	Tile attention в SRAM - 5-10x ускорение, 20x меньше памяти
Quantization	INT8 / FP8 GEMM	В 2-4x быстрее FP16 на тех же транзисторах

Batched matmul: одна операция на весь батч

**FlashAttention переворачивает игру.** Стандартный attention хранит матрицу $QK^T$ размера seq×seq в HBM (медленная VRAM). Для seq=8192 это 256 МБ на голову - не помещается в SRAM (быстрый кэш ~20 МБ на A100). FlashAttention плиточно считает softmax-блоки прямо в SRAM, никогда не материализуя полную матрицу. Результат - 5-10x ускорение и 20x меньше памяти при том же ответе. На этом построены Llama-3 и Mistral.

ОДИН FORWARD GPT-4 НА 1 ТОКЕН (~1.8 триллиона matmul-операций): Naive Python (3 вложенных цикла): ~10^12 операций / 10^7 ops/sec = 100 000 секунд = 28 часов на токен NumPy через MKL (Intel, 1 CPU): ~10^12 / 10^11 ops/sec = 10 секунд на токен GPU A100 cuBLAS (312 TFLOPS): ~10^12 / 3*10^14 ops/sec = ~3.3 миллисекунды на токен (на самом деле medium-batch ~30-50 мс - bottleneck в HBM, а не в счёте) H100 SXM с FlashAttention-2 (FP8): ~1 миллисекунда на токен РАЗНИЦА Python vs H100: 10^8 раз. Восемь порядков.

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

Если все архитектуры нейросетей сводятся к одной операции matmul, что определяет различия между ResNet, Transformer и Diffusion модели - геометрия весов, порядок умножений или нелинейности между слоями?

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

la-01-vectors-intro — Матрица - это набор векторов; умножение строится на скалярном произведении строки и столбца
la-02-dot-product — Каждый элемент произведения C[i,j] - это dot product i-й строки A и j-го столбца B
la-13-eigenvectors — Собственные векторы сохраняют направление при матричном умножении - база PCA и PageRank
la-15-svd — SVD раскладывает любую матрицу в произведение трёх специальных матриц - low-rank approximation, LoRA
aie-03-llm-fundamentals — Каждый Linear слой и каждый attention head в LLM - это matmul; основа inference и обучения
ml-25-neural-networks — Forward pass нейросети - это цепочка W·x + b с активацией между слоями
alg-01-big-o — Наивный matmul - O(n^3), Штрассен - O(n^2.807); анализ сложности объясняет, почему GPU важен
stats-21