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

Тензорные разложения: SVD для многомерных данных

Видеозапись 1080p 60fps за 1 час - терабайты данных. Tucker и CP разложения сжимают тензор видео с потерей качества, управляемой рангом. В ML тензорные разложения используются для сжатия весов нейросетей (MobileNet v3 прокомпрессировали в 10x) и анализа многоканальных временных рядов.

  • Сжатие весов: Tucker-разложение свёрточных ядер (C_in, C_out, kH, kW) уменьшает параметры в 5-10x
  • Рекомендательные системы: User-Item-Context тензор, CP-разложение для предсказания
  • Нейронауки: fMRI-данные (x, y, z, время) - Tucker для разделения пространственных и временных факторов
  • Химия: тензор взаимодействий атомов в молекуле для Graph Neural Networks
  • Traffic prediction: тензор (узлы, время, признаки) - STAEformer использует тензорные операции

CP-разложение: сумма рангов-1

**ResNet-50 весит 100 МБ. Tucker-разложение его свёрточных слоёв даёт 25 МБ при той же точности на ImageNet.** Spotify хранит предпочтения 600 миллионов пользователей по миллионам треков в разных контекстах - не как гигантскую таблицу, а как CP-разложение трёхмерного тензора. Tensor Train сжимает embedding-слой с 10^30 до 20 000 параметров. Всё это - одна идея: обобщить SVD на тензоры.

**О чём этот урок на самом деле**: SVD разложила матрицы - и наука изменилась. Но данные бывают трёхмерными (пользователь × товар × время), четырёхмерными (батч × каналы × H × W), n-мерными. Тензорные разложения - это SVD в мире высоких размерностей. Три метода, три компромисса, один принцип.

CP-разложение: тензор как сумма рангов-1

Матрица ранга 1 - это произведение двух векторов: M = a·bᵀ. Тензор ранга 1 - произведение трёх: T = a ⊗ b ⊗ c. **CP-разложение** (CANDECOMP/PARAFAC) представляет произвольный тензор как сумму R таких слагаемых - это прямая аналогия с разложением матрицы в сумму ранг-1 матриц из SVD.

ТЕНЗОР: T ∈ R^{I×J×K} CP-РАЗЛОЖЕНИЕ РАНГА R: T[i,j,k] ≈ Σ_{r=1}^R a[i,r] · b[j,r] · c[k,r] ПАРАМЕТРЫ: Оригинал: I·J·K CP ранга R: R·(I + J + K) ПРИМЕР: тензор 100×100×100 Оригинал: 1 000 000 параметров CP, R=20: 20·300 = 6 000 параметров (167x сжатие) КОГДА РАБОТАЕТ: когда данные имеют низкоранговую структуру (например, предпочтения пользователей, физические поля)

**Ловушка тензорного ранга**: в отличие от матричного ранга, вычисление точного тензорного ранга - NP-сложная задача. Более того, множество тензоров ранга ≤ R не является замкнутым - последовательность тензоров ранга r может сходиться к тензору ранга r+1. На практике используют приближённые итеративные алгоритмы (ALS - Alternating Least Squares).

Чем тензорный ранг в CP-разложении принципиально отличается от матричного?

Для матрицы ранг легко найти через SVD за O(mn min(m,n)). Для тензора порядка ≥3 проблема нахождения точного ранга - NP-сложна (Hillar & Lim, 2013). На практике используют приближённые алгоритмы (ALS - alternating least squares) с фиксированным целевым рангом.

Tucker-разложение и сжатие сетей

Tucker-разложение: сжатие весов нейросетей

Tucker - более гибкое обобщение: вместо одного скалярного ранга R вводится отдельный ранг для каждой моды. Ядро (core tensor) G захватывает взаимодействия между модами, матрицы факторов A, B, C проецируют каждую ось в малое пространство. **Именно Tucker используется для сжатия свёрточных слоёв** в production-задачах: слой 3×3 с 256 входными и 256 выходными каналами можно сжать в 4 раза без ощутимой потери точности.

TUCKER ранга (R1, R2, R3): T[i,j,k] ≈ Σ_{p,q,r} G[p,q,r] · A[i,p] · B[j,q] · C[k,r] ПАРАМЕТРЫ: Оригинал: I·J·K Tucker: R1·R2·R3 + I·R1 + J·R2 + K·R3 ПРИМЕР: свёрточный слой (256, 256, 3, 3) Оригинал: 256·256·3·3 = 589 824 Tucker (64,64,3,3): 64·64·3·3 + 256·64 + 256·64 = 36 864 + 16 384 + 16 384 = 69 632 ≈ 8.5x меньше, потеря точности < 1% CP = Tucker с диагональным ядром (частный случай)

**Как Tucker применяется на практике**: Tucker-разложение весов уже обученной CNN даёт низкоранговую аппроксимацию. Затем модель дообучается несколько эпох (fine-tuning) - и восстанавливает почти всю потерянную точность. Именно так делается compression для deployment на мобильных устройствах.

В чём принципиальное отличие Tucker от CP-разложения?

CP представляет тензор как сумму r слагаемых a_k ⊗ b_k ⊗ c_k с одинаковым числом слагаемых для всех осей. Tucker раскладывает как ядро S ∈ R^(r1×r2×r3) умножить на ортогональные проекционные матрицы по каждой оси. Это даёт гибкость: разные оси могут иметь разную «эффективную размерность».

Tensor Train: цепочка матриц

Tensor Train: экспоненциальное сжатие

Embedding-слой GPT хранит 50 000 токенов × 12 288 размерностей = 614 миллионов параметров. Tensor Train (TT) разлагает матрицу как цепочку небольших тензоров - и параметров становится порядка тысяч. Идея: индексы переписываются в смешанно-радиксном коде, тензор факторизуется по каждому разряду.

TT-РАЗЛОЖЕНИЕ: T(i1, i2, ..., in) = G1[i1] · G2[i2] · ... · Gn[in] где Gk[ik] - матрица r_{k-1} × r_k ПАРАМЕТРЫ: Оригинал: d^n TT ранга r: n · d · r² ПРИМЕР: тензор с n=10, d=100, r=10 Оригинал: 100^10 = 10^20 (невозможно хранить!) TT: 10 · 100 · 100 = 100 000 EMBEDDING-СЛОЙ через TT: 50000 × 12288 = 614 млн параметров TT (n=8, ранги r=16): ≈ 50 000 параметров Потеря качества: < 2%

**TT = MPS в физике**: Tensor Train известен в квантовой физике как Matrix Product State (MPS). Волновая функция n кубитов - тензор 2^n элементов. При ограниченной квантовой запутанности (area law) TT-ранг мал, и состояние описывается экспоненциально меньшим числом параметров. Именно это позволяет классическим компьютерам симулировать квантовые цепи из 100+ кубитов.

Сравнение методов

МетодПараметрыКогда использоватьML-применение
CP (ранг R)R·(I+J+K)Данные имеют аддитивную структуруРекомендательные системы (user×item×time)
Tucker (R1,R2,R3)R1R2R3 + IR1+JR2+KR3Разные оси имеют разную сложностьСжатие свёрточных слоёв CNN
TT/MPS (ранг r)n·d·r²Данные высокоразмерные (n>>3)Сжатие Embedding-слоёв, квантовые симуляции

tensorly: единый API для всех разложений

**tensorly** - библиотека Python для тензорных вычислений с бэкендами numpy, PyTorch, TensorFlow. Стандартный инструмент для всех трёх разложений в research и production.

**Тензорные разложения в индустрии** От теории к production - **Рекомендательные системы (CP)**: 3-way тензор user × item × context. Netflix, Amazon: CP-разложение обрабатывает временной контекст лучше матричного SVD. Улучшение точности на 5-10%. - **Сжатие CNN (Tucker)**: Low-rank аппроксимация conv-весов. MobileNet, EfficientNet используют Tucker-подобные разложения. 4x сжатие без потери точности на ImageNet. - **Сжатие Embedding (TT)**: Embedding-слой как TT-матрица. Язык. модели: Embedding 50k×768 → TT с рангами 16 → в 100x меньше параметров. Скорость инференса растёт. - **Квантовые симуляции (MPS=TT)**: Волновые функции кубитов. Google, IBM Q: симуляция 100+ кубитов на GPU через MPS. Основа современной квантовой химии.

Практика: CP-разложение тензора

Что унести из урока

  • **CP-разложение**: T ≈ Σ aᵣ⊗bᵣ⊗cᵣ - аддитивная структура, R·(I+J+K) параметров, для рекомендательных систем
  • **Tucker**: T ≈ G ×₁A ×₂B ×₃C - ядро + факторы, разные ранги по модам, для сжатия CNN (4x без потери точности)
  • **Tensor Train**: T(i1,...,in) = G1[i1]·...·Gn[in] - экспоненциальное сжатие d^n → O(ndr²), для Embedding-слоёв
  • **CP = Tucker** с диагональным ядром - частный случай
  • **Тензорный ранг NP-сложен** - в отличие от матричного, нет точного полиномиального алгоритма
  • **tensorly** - стандартный Python-инструмент с бэкендами numpy/PyTorch/TF
  • Сжатие через Tucker: разложить → заменить тремя слоями → fine-tune 5-10 эпох

Связи

Тензорные разложения строятся поверх SVD и используют рандомизированные методы для ускорения

  • SVD и сингулярные числа — Tucker = многомерное обобщение SVD; HOSVD - это SVD по каждой моде
  • Рандомизированная линейная алгебра — Рандомизированное SVD - строительный блок для быстрых Tucker и TT разложений
  • Линейная алгебра в глубоком обучении — Tucker-разложение для сжатия весов нейросетей (MobileNet, pruning)

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

  • ml-01-intro
Тензорные разложения: SVD для многомерных данных

0

1

Войти

**Почему тензорный ранг NP-сложен, а матричный - нет?** Hints: Что такое ранг матрицы через SVD?; Есть ли аналог SVD для тензоров? - Матричный ранг = число ненулевых сингулярных значений, вычисляется через SVD за O(mn²) - Для тензоров нет аналога SVD с оптимальными гарантиями - задача нахождения минимального ранга NP-сложна - Более того: множество тензоров ранга ≤ R не замкнуто (в отличие от матриц), поэтому даже существование наилучшей CP-аппроксимации не гарантировано - На практике используют ALS (Alternating Least Squares) - итеративный алгоритм без гарантий глобального минимума --- **Когда Tucker предпочтительнее CP, и наоборот?** Hints: Какие параметры есть у Tucker, которых нет у CP?; Что происходит с вычислительной сложностью? - Tucker лучше когда разные оси имеют разную структуру (например, spatial vs channel в CNN) - CP лучше когда нужна максимальная интерпретируемость: каждый компонент - отдельная тема/профиль - Tucker сложнее оптимизировать (HOOI - Higher Order Orthogonal Iteration), но HOSVD даёт хорошее начальное приближение - CP - NP-сложен точно, Tucker может быть вычислен точно через HOSVD при ортогональных факторах --- **Как Tucker-разложение применяется для сжатия нейросети без потери качества?** Hints: Что такое fine-tuning?; Какой порядок операций при сжатии? - Шаг 1: Tucker-разложение уже обученных весов conv-слоёв (offline, один раз) - Шаг 2: Tucker-слой заменяется тремя: 1x1 (rank reduction) + 3x3 (core) + 1x1 (rank restoration) - Шаг 3: fine-tuning 5-10 эпох восстанавливает точность, потерянную при аппроксимации - Результат: 4x меньше параметров и FLOPS, потеря качества < 1% на ImageNet

Почему Tensor Train позволяет хранить embedding GPT с экспоненциальным сжатием?

TT-разложение хранит тензор T shape n^d как цепочку из d матриц размера r×n×r. Параметров: O(d·n·r²) вместо O(n^d). Embedding-слой GPT (50000×12288) можно представить как TT с rank r=16, экономя 90%+ памяти. В физике TT известен как MPS (Matrix Product States).