Тензорное разложение

Материал из MachineLearning.

Перейти к: навигация, поиск
Статья написана с использованием LLM Claude Sonnet 5 и проверена участником Участник:Georgii Kvaratsкheliia 19 июля 2026

Промпт приводится полностью в Обсуждение: Тензорное разложение


Содержание

Тензорное разложение (англ. tensor decomposition) — семейство методов представления многомерного массива данных (тензора) в виде комбинации более простых компонентов меньшей размерности, обобщающих сингулярное разложение матриц (SVD) и метод главных компонент на случай трёх и более измерений. Тензор порядка N — это многомерный массив \mathcal{X}\in\mathbb{R}^{I_1\times I_2\times\cdots\times I_N}: скаляр — тензор нулевого порядка, вектор — первого, матрица — второго; данные с тремя и более индексами (время × пользователь × товар, канал × время × испытание в ЭЭГ, высота × ширина × кадр в видео) естественно описываются тензорами более высокого порядка.

Идея разложения тензора на сумму или произведение более простых объектов лежит в основе многих алгоритмов современного машинного обучения и искусственного интеллекта: сжатия и ускорения нейронных сетей, метода моментов для обучения скрытых переменных моделей, факторизации знаниевых графов, анализа многоканальных сигналов и многомерных изображений.

Определение

Каноническое полиадическое разложение (CP/PARAFAC)

Наиболее прямое обобщение матричной факторизации на тензоры — каноническое полиадическое разложение (CANDECOMP/PARAFAC, CP), представляющее тензор как сумму R тензоров ранга один:

\mathcal{X} \approx \sum_{r=1}^{R} \lambda_r\, a_r^{(1)} \circ a_r^{(2)} \circ \cdots \circ a_r^{(N)},

где \circ — внешнее произведение векторов, а a_r^{(n)} — столбцы «факторных матриц» A^{(n)}\in\mathbb{R}^{I_n\times R}. Для тензора третьего порядка это записывается покомпонентно как x_{ijk}\approx\sum_{r=1}^{R} a_{ir}\,b_{jr}\,c_{kr}. Наименьшее R, для которого равенство точное, называется рангом тензора.

Разложение Такера

Разложение Такера — более общая модель, представляющая тензор как произведение малого «ядерного» тензора \mathcal{G}\in\mathbb{R}^{R_1\times\cdots\times R_N} на факторные матрицы по каждой моде:

\mathcal{X} \approx \mathcal{G}\times_1 A^{(1)}\times_2 A^{(2)}\times_3\cdots\times_N A^{(N)}, \qquad x_{i_1\cdots i_N}\approx\sum_{r_1,\dots,r_N} g_{r_1\cdots r_N}\prod_{n=1}^N a^{(n)}_{i_n r_n},

где \times_n — умножение тензора по n-й моде. Разложение Такера можно рассматривать как многомерный аналог метода главных компонент: ядро \mathcal{G} играет роль «взаимодействия» компонент, тогда как в CP это взаимодействие ограничено диагональным (сверхдиагональным) ядром — CP является частным случаем разложения Такера с квадратным сверхдиагональным ядром.

Матрицизация

Ключевой технический инструмент — матрицизация (развёртка) тензора по моде n, обозначаемая \mathcal{X}_{(n)}: превращение тензора в матрицу путём выстраивания всех волокон вдоль моды n в столбцы. Через матрицизацию тензорные разложения сводятся к привычным матричным операциям, что лежит в основе большинства алгоритмов их вычисления.

Мотивация

Зачем нужна отдельная теория для многомерных массивов, если тензор можно просто «развернуть» в матрицу и применить обычный PCA или SVD?

  • Потеря многомодовой структуры. Разворачивание тензора в матрицу по одной моде уничтожает взаимосвязи между остальными модами: например, для видеоряда (кадр × высота × ширина) матрицизация по кадрам теряет пространственную структуру внутри каждого кадра, которую как раз и призвана уловить многомодовая модель.
  • Экспоненциальный рост объёма данных. Тензор порядка N с размерами моды I занимает I^N ячеек памяти. Разложение CP хранит лишь R\cdot N\cdot I параметров — линейный, а не экспоненциальный рост по числу мод; ещё более радикальную экономию даёт тензорный поезд (см. ниже).
  • Интерпретируемость и идентифицируемость. В отличие от матричной факторизации, где решение определено лишь с точностью до произвольного обратимого преобразования базиса (UV^\top=(UQ)(VQ^{-\top})^\top), CP-разложение при мягких условиях регулярности единственно с точностью до масштабирования и перестановки компонент — свойство, которого не даёт ни PCA, ни NMF в общем случае, и которое делает CP особенно ценным там, где важна содержательная интерпретация компонент (хемометрика, нейронаука, метод моментов).

История

Математическое определение разложения тензора на сумму слагаемых ранга один впервые дал Фрэнк Хичкок в 1927 году[1]. Практическое применение и алгоритмическое развитие пришло из психометрики: Такер в 1966 году предложил трёхмодовый факторный анализ[2], а Кэрролл и Чанг, а также независимо Харшман в 1970 году ввели каноническое разложение CANDECOMP/PARAFAC[3,4]. В 1977 году Крускал доказал фундаментальную теорему об условиях единственности трилинейного разложения — результат, до сих пор остающийся центральным для теории идентифицируемости CP[5]. Крунеберг и де Лью в 1980 году формализовали алгоритм чередующихся наименьших квадратов (ALS) для оценки параметров модели Такера, заложив стандартную вычислительную схему, используемую и по сей день[6].

Строгая многолинейно-алгебраическая трактовка пришла с работой Де Латхауэра, Де Мора и Вандевалле (2000), предложивших SVD высшего порядка (Higher-Order SVD, HOSVD) — обобщение матричного SVD, вычисляемое через матрицизацию и обычное SVD по каждой моде[7]. Первое заметное применение тензорных методов в компьютерном зрении дали Василеску и Терзопулос (2002) в модели «TensorFaces» для распознавания лиц с учётом освещения, ракурса и мимики как отдельных мод[9]. Обзорная статья Колды и Бейдера 2009 года стала общепринятой точкой входа в тему для специалистов по анализу данных и машинному обучению, систематизировав определения, алгоритмы и приложения[10].

2010-е годы принесли взрывной рост применений в машинном обучении: Осёледец (2011) предложил формат тензорного поезда (Tensor Train, TT), позволяющий работать с тензорами очень высокого порядка без экспоненциального роста памяти[12]; Анандкумар с соавторами (2014) формализовали метод моментов на основе тензорных разложений для гарантированного (не только локально-оптимального) обучения скрытых переменных моделей — смесей гауссиан, скрытых марковских моделей, латентного размещения Дирихле[13]; Никель, Треспе и Кригель (2011) применили трёхмодовую факторизацию к мультиреляционным (знаниевым) графам[11]; Лебедев с соавторами и Новиков с соавторами (оба 2015) показали, что CP- и TT-разложения способны на порядки сжимать и ускорять свёрточные и полносвязные слои нейронных сетей[15,16]. Современное состояние области для аудитории специалистов по обработке сигналов и машинному обучению systematized в обзорах Сидиропулоса с соавторами и Чичоцки с соавторами (оба середины 2010-х)[17,18].

Алгоритмы вычисления

ALS для CP-разложения

Стандартный алгоритм вычисления CP-разложения — метод чередующихся наименьших квадратов (Alternating Least Squares, ALS), являющийся прямым применением идеи альтернированной минимизации к тензорной задаче: при фиксированных факторных матрицах всех мод, кроме одной, задача минимизации \|\mathcal{X}-[\![A^{(1)},\dots,A^{(N)}]\!]\|_F^2 по оставшейся матрице становится обычной линейной задачей наименьших квадратов. Используя матрицизацию по моде n и произведение Хатри — Рао \odot, обновление имеет замкнутую форму

A^{(n)} \leftarrow \mathcal{X}_{(n)}\Bigl(A^{(N)}\odot\cdots\odot A^{(n+1)}\odot A^{(n-1)}\odot\cdots\odot A^{(1)}\Bigr)\Bigl(A^{(N)\top}A^{(N)}\ast\cdots\ast A^{(1)\top}A^{(1)}\Bigr)^{+},

где \ast — поэлементное (адамарово) произведение, а {}^{+} — псевдообратная матрица; шаги циклически повторяются по всем модам до сходимости. Историю сходимости алгоритма ALS для трёхмодовой модели Такера впервые изучили Крунеберг и де Лью[6], а общая теория блочного координатного спуска для мультивыпуклых задач, включающих задачи тензорной факторизации, дана Сюем и Инем[19]. Подробнее об общих свойствах и вариантах метода — в статьях «Альтернированная минимизация» и «Альтернированный градиентный спуск».

HOSVD и HOOI для разложения Такера

HOSVD вычисляет факторную матрицу каждой моды как левые сингулярные векторы соответствующей матрицизации \mathcal{X}_{(n)}, после чего ядро находится как \mathcal{G}=\mathcal{X}\times_1 A^{(1)\top}\times_2\cdots\times_N A^{(N)\top}[7]. Такое разложение, вообще говоря, не даёт наилучшего приближения заданного ранга (в отличие от матричного случая теоремы Эккарта — Янга); уточнением служит итеративная схема Higher-Order Orthogonal Iteration (HOOI), по сути также являющаяся частным случаем альтернированной минимизации.

Вычислительная сложность и NP-трудность

В отличие от матричного ранга, который вычисляется за полиномиальное время (через SVD), определение точного ранга тензора и нахождение наилучшего CP-приближения заданного ранга в общем случае NP-трудны: Хиллар и Лим (2013) строго показали NP-трудность практически всех содержательных тензорных задач, включая вычисление ранга, наилучшего ранг-1 приближения и проверку положительной полуопределённости для тензоров четвёртого порядка[14]. Это принципиальное отличие от матричного случая объясняет, почему на практике почти всегда используют эвристические итеративные методы (ALS, HOSVD/HOOI) без гарантии глобальной оптимальности.

Чем тензоры отличаются от матриц: три неожиданных факта

Для читателя, знакомого с матричным SVD, поведение тензорных разложений преподносит несколько контринтуитивных сюрпризов, важных для практики.

  • CP-разложение может быть существенно единственным — притом что матричная факторизация никогда не единственна без дополнительных ограничений (ортогональности, неотрицательности и т. п.). Достаточное условие даёт теорема Крускала: если сумма так называемых k-рангов факторных матриц k_A+k_B+k_C\ge 2R+2, то CP-разложение ранга R единственно с точностью до перестановки и масштабирования компонент[5]. Именно эта единственность делает CP незаменимым инструментом там, где компоненты должны иметь содержательную интерпретацию (например, извлечение источников сигналов, метод моментов).
  • Наилучшее низкоранговое приближение тензора может не существовать. Теорема Эккарта — Янга гарантирует, что наилучшее приближение матрицы рангом r всегда достигается (усечённым SVD); для тензоров порядка три и выше это, вообще говоря, неверно — Де Силва и Лим (2008) показали, что задача наилучшего ранг-r приближения может быть некорректно поставлена (последовательность приближающих тензоров ранга r может сходиться к тензору строго большего ранга, а инфимум ошибки не достигается ни на каком тензоре ранга r)[8].
  • Ранг тензора может превышать все его размеры моды — в отличие от матрицы, чей ранг всегда не больше меньшей из двух размерностей. Максимально возможный («типичный») ранг тензора над вещественными числами часто оказывается больше, чем над комплексными, что также не имеет аналога в матричном случае.

Другие разложения

Помимо CP и Такера, для задач очень высокого порядка (десятки и сотни мод) применяется тензорный поезд (Tensor Train, TT): тензор представляется цепочкой малых тензоров третьего порядка, «нанизанных» друг за другом, что даёт число параметров, растущее линейно, а не экспоненциально по числу мод, и при этом сохраняет устойчивость вычислений (в отличие от CP, где задача наилучшего приближения может быть некорректной)[12]. TT-формат тесно связан с представлением «матричных произведений состояний» (matrix product states) в квантовой физике многих тел. Существуют и другие модели — тензорные кольца, иерархическая Такер-декомпозиция, блочно-термовые разложения, — каждая из которых предлагает свой компромисс между компактностью представления, устойчивостью вычислений и интерпретируемостью.

Применения в машинном обучении и искусственном интеллекте

Сжатие и ускорение нейронных сетей

Полносвязные и свёрточные слои глубоких сетей часто избыточно параметризованы. Новиков с соавторами (2015) показали, что представление плотной весовой матрицы полносвязного слоя в формате тензорного поезда позволяет сократить число параметров слоя в десятки и сотни тысяч раз почти без потери качества, а всей сети — в несколько раз[16]. Лебедев с соавторами (2015) применили CP-разложение к ядрам свёрточных слоёв с последующей дообучающей настройкой, добившись значительного ускорения инференса свёрточных сетей[15].

Метод моментов и обучение скрытых переменных моделей

Для широкого класса моделей со скрытыми переменными (смеси гауссиан, скрытые марковские модели, латентное размещение Дирихле) моменты второго и третьего порядка наблюдаемых данных образуют тензор специальной (ортогонально разложимой) структуры; извлечение CP-подобного разложения этого тензора моментов даёт вычислительно и статистически эффективный способ оценки параметров модели с гарантиями, недостижимыми для локальных методов вроде EM-алгоритма[13].

Факторизация знаниевых графов и рекомендательные системы

Модель RESCAL Никеля, Треспе и Кригеля представляет знаниевый граф (тройки «сущность–отношение–сущность») как трёхмодовый тензор и применяет к нему разложение, родственное Такеру, для коллективного вывода недостающих связей[11]. В рекомендательных системах с контекстом (например, пользователь × товар × время или × устройство) тензорная факторизация естественно обобщает матричную ALS-факторизацию[20], обсуждаемую в статье «Альтернированная минимизация», на дополнительные контекстные измерения.

Компьютерное зрение

Модель TensorFaces Василеску и Терзопулоса представляет ансамбль изображений лиц как тензор (люди × ракурсы × освещение × мимика × пиксели) и с помощью разложения Такера отделяет вклад каждого из этих факторов друг от друга, превосходя классический метод собственных лиц (eigenfaces), основанный на обычном PCA после «сплющивания» всех факторов в один режим[9].

Обработка сигналов, хемометрика, нейронаука

Исторически тензорные методы возникли в хемометрике (разложение флуоресцентных спектров возбуждения-эмиссии) и психометрике; сегодня они широко применяются для анализа многоканальных сигналов ЭЭГ/фМРТ (канал × время × испытание), гиперспектральных изображений и телекоммуникационных сигналов — подробный обзор применений в обработке сигналов и машинном обучении дают Сидиропулос с соавторами и Чичоцки с соавторами[17,18].

Ограничения и практические аспекты

  • Отсутствие гарантий глобальной оптимальности. Поскольку точное вычисление тензорного ранга и наилучшего приближения NP-трудно, ALS и HOOI сходятся лишь к локальному минимуму (а иногда и вовсе не сходятся к содержательной точке, если задача некорректно поставлена, как в примере Де Силвы и Лима)[8,14].
  • Выбор ранга. В отличие от матричного случая, где ранг однозначно связан с сингулярными числами, для тензоров не существует единого практичного способа определить «истинный» ранг CP-разложения; на практике ранг подбирают по критерию качества приближения или кросс-валидацией.
  • Численная неустойчивость CP при высоком ранге. Приближающая последовательность CP-разложений может «взрываться» (компоненты стремятся к бесконечности при взаимном сокращении) именно из-за некорректности задачи наилучшего приближения — на практике это проявляется как численная неустойчивость ALS при попытке подобрать ранг, близкий к максимально возможному.
  • Компромисс между моделями. CP даёт наиболее компактное и потенциально единственное представление, но менее гибко; Такер — более гибкое (произвольное ядро), но менее компактное и не единственное; тензорный поезд — наиболее устойчиво и масштабируемо для тензоров очень высокого порядка ценой менее прозрачной интерпретации компонент. Выбор модели определяется задачей: интерпретируемость (CP), сжатие данных общего вида (Такер), сверхвысокая размерность (TT).

См. также

Примечания

  1. Hitchcock F. L. The expression of a tensor or a polyadic as a sum of products // Journal of Mathematics and Physics. — 1927. — Т. 6, № 1. — С. 164–189.
  2. Tucker L. R. Some mathematical notes on three-mode factor analysis // Psychometrika. — 1966. — Т. 31, № 3. — С. 279–311.
  3. Carroll J. D., Chang J. J. Analysis of individual differences in multidimensional scaling via an N-way generalization of "Eckart-Young" decomposition // Psychometrika. — 1970. — Т. 35, № 3. — С. 283–319.
  4. Harshman R. A. Foundations of the PARAFAC procedure: Models and conditions for an "explanatory" multi-modal factor analysis // UCLA Working Papers in Phonetics. — 1970. — Т. 16. — С. 1–84.
  5. Kruskal J. B. Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics // Linear Algebra and its Applications. — 1977. — Т. 18. — С. 95–138.
  6. Kroonenberg P. M., De Leeuw J. Principal component analysis of three-mode data by means of alternating least squares algorithms // Psychometrika. — 1980. — Т. 45. — С. 69–97.
  7. De Lathauwer L., De Moor B., Vandewalle J. A multilinear singular value decomposition // SIAM Journal on Matrix Analysis and Applications. — 2000. — Т. 21, № 4. — С. 1253–1278.
  8. De Silva V., Lim L.-H. Tensor rank and the ill-posedness of the best low-rank approximation problem // SIAM Journal on Matrix Analysis and Applications. — 2008. — Т. 30, № 3. — С. 1084–1127.
  9. Vasilescu M. A. O., Terzopoulos D. Multilinear Analysis of Image Ensembles: TensorFaces // Computer Vision — ECCV 2002. Lecture Notes in Computer Science, vol. 2350. — Springer, 2002. — С. 447–460.
  10. Kolda T. G., Bader B. W. Tensor Decompositions and Applications // SIAM Review. — 2009. — Т. 51, № 3. — С. 455–500.
  11. Nickel M., Tresp V., Kriegel H.-P. A Three-Way Model for Collective Learning on Multi-Relational Data // Proceedings of the 28th International Conference on Machine Learning (ICML). — 2011. — С. 809–816.
  12. Oseledets I. V. Tensor-Train Decomposition // SIAM Journal on Scientific Computing. — 2011. — Т. 33, № 5. — С. 2295–2317.
  13. Anandkumar A., Ge R., Hsu D., Kakade S. M., Telgarsky M. Tensor Decompositions for Learning Latent Variable Models // Journal of Machine Learning Research. — 2014. — Т. 15, № 80. — С. 2773–2832.
  14. Hillar C. J., Lim L.-H. Most tensor problems are NP-hard // Journal of the ACM. — 2013. — Т. 60, № 6. — Статья 45.
  15. Lebedev V., Ganin Y., Rakhuba M., Oseledets I., Lempitsky V. Speeding-up Convolutional Neural Networks Using Fine-tuned CP-Decomposition // International Conference on Learning Representations (ICLR). — 2015.
  16. Novikov A., Podoprikhin D., Osokin A., Vetrov D. Tensorizing Neural Networks // Advances in Neural Information Processing Systems 28 (NIPS 2015). — С. 442–450.
  17. Sidiropoulos N. D., De Lathauwer L., Fu X., Huang K., Papalexakis E. E., Faloutsos C. Tensor Decomposition for Signal Processing and Machine Learning // IEEE Transactions on Signal Processing. — 2017. — Т. 65, № 13. — С. 3551–3582.
  18. Cichocki A., Mandic D., De Lathauwer L., Zhou G., Zhao Q., Caiafa C., Phan H. A. Tensor Decompositions for Signal Processing Applications: From Two-way to Multiway Component Analysis // IEEE Signal Processing Magazine. — 2015. — Т. 32, № 2. — С. 145–163.
  19. Xu Y., Yin W. A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion // SIAM Journal on Imaging Sciences. — 2013. — Т. 6, № 3. — С. 1758–1789.
  20. Koren Y., Bell R., Volinsky C. Matrix factorization techniques for recommender systems // Computer. — 2009. — Т. 42, № 8. — С. 30–37.

Литература

  • Kolda T. G., Bader B. W. Tensor Decompositions and Applications // SIAM Review. — 2009. — Т. 51, № 3. — С. 455–500.
  • Sidiropoulos N. D., De Lathauwer L., Fu X., Huang K., Papalexakis E. E., Faloutsos C. Tensor Decomposition for Signal Processing and Machine Learning // IEEE Transactions on Signal Processing. — 2017. — Т. 65, № 13. — С. 3551–3582.
  • Cichocki A. et al. Tensor Decompositions for Signal Processing Applications // IEEE Signal Processing Magazine. — 2015. — Т. 32, № 2. — С. 145–163.
  • Oseledets I. V. Tensor-Train Decomposition // SIAM Journal on Scientific Computing. — 2011. — Т. 33, № 5. — С. 2295–2317.
  • Kruskal J. B. Three-way arrays: rank and uniqueness of trilinear decompositions // Linear Algebra and its Applications. — 1977. — Т. 18. — С. 95–138.
  • Anandkumar A., Ge R., Hsu D., Kakade S. M., Telgarsky M. Tensor Decompositions for Learning Latent Variable Models // Journal of Machine Learning Research. — 2014. — Т. 15. — С. 2773–2832.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BD%D0%B7%D0%BE%D1%80%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5»
Личные инструменты