Тензорный поезд (Tensor Train): преодоление проклятия размерности

От матриц к матричным произведениям состояний (MPS)

Идея, лежащая в основе формата Тензорного поезда, впервые возникла в квантовой физике под названием Matrix Product States (MPS) в алгоритме DMRG, созданном Стивеном Уайтом для анализа одномерных квантовых спиновых цепочек. В алгебраическом формате TT исходный гигантский тензор разбивается на цепочку (поезд) из d трехмерных тензоров-ядер гораздо меньшего размера. Каждый элемент исходного многомерного массива вычисляется не путем прямого обращения к памяти, а как результат последовательного перемножения ряда матриц, полученных из этих ядер. Формат «цепочки» означает, что i-е ядро связано только с (i-1)-м и (i+1)-м ядрами через так называемые индексы TT-рангов. Если TT-ранги невелики, весь тензор сжимается до невероятно малых размеров.

Алгоритм TT-SVD: конструктивное разложение

В отличие от канонического CP-разложения тензоров, где задача нахождения оптимального приближения является NP-трудной и опирается на неустойчивые итерационные методы, формат Тензорного поезда обладает идеальными алгоритмическими свойствами. Формирование ядер TT-разложения выполняется с помощью абсолютно надежного, неитеративного алгоритма TT-SVD. Алгоритм берет исходный тензор, разворачивает (сплющивает) его в гигантскую двумерную матрицу и применяет усеченное сингулярное разложение (SVD). Затем левые сингулярные векторы образуют первое ядро, а правые векторы переформатируются в новый тензор меньшей размерности, к которому процедура SVD применяется рекурсивно. Этот детерминированный процесс математически гарантирует нахождение аппроксимации с заданным порогом ошибки.

TT-арифметика: вычисления в сжатом виде

Гениальность формата Tensor Train заключается в том, что он позволяет выполнять математические операции непосредственно над сжатыми ядрами, вообще не восстанавливая гигантский исходный тензор. Сложение двух TT-тензоров сводится к простому блочному объединению их ядер, а умножение на скаляр или скалярное произведение двух тензоров выполняется за время, линейное по размерности d (вместо экспоненциального). Даже решение огромных систем линейных уравнений, где матрица оператора и вектор правой части представлены в формате TT, осуществляется с помощью специализированной версии метода AMEn (Alternating Minimal Energy), который оптимизирует ядра тензора поочередно, оставаясь в компактном сжатом пространстве на протяжении всего процесса решения.

Округление и управление TT-рангами

При выполнении математических операций над тензорами в формате TT (например, при сложении) их внутренние TT-ранги увеличиваются. Чтобы избежать раздувания памяти, применяется критически важная процедура TT-округления (TT-Rounding). Алгоритм проходит по всей цепочке ядер слева направо, выполняя ортогонализацию (через QR-разложение), а затем возвращается справа налево, выполняя сжатие через SVD и отсекая малые сингулярные числа. Эта процедура восстанавливает минимально возможные TT-ранги, сохраняя общую точность тензора. TT-формат сегодня встроен в библиотеки машинного обучения (TensorFlow, PyTorch) для компрессии весовых матриц глубоких нейросетей, позволяя запускать гигантские модели, такие как трансформеры, на мобильных устройствах с ограниченной памятью.