Как стать автором
Обновить
55.79

Прибытие тензорного поезда. Как достижения мультилинейной алгебры помогают преодолеть проклятие размерности

Уровень сложностиСложный
Время на прочтение6 мин
Количество просмотров8.4K
Коллаж AIRI. Источник: iclcollective.com
Коллаж AIRI. Источник: iclcollective.com

Привет! Меня зовут Глеб Рыжаков, я научный сотрудник Сколтеха. Я занимаюсь математикой, а точнее, линейной алгеброй, и её приложениями к практическим задачам. Сегодня я расскажу вам о нашем исследовании, которое может помочь справиться с проблемой проклятия размерности, которая возникает во множестве статистических задач, включая машинное обучение.

Понятие «проклятие размерности» появилось в середине прошлого века в пионерской работе Ричарда Беллмана, посвященной методам решения сложных задач путём разбиения их на более простые подзадачи. Сегодня оно понимается в более общем смысле, а именно как экспоненциальный — O(nd) — рост количества необходимых данных и, как следствие, количества памяти, необходимой для их хранения, с ростом размерности пространства d. Когда задачу можно свести к работе с многомерными массивами в общем случае комплексных чисел, удобно говорить о d-мерных тензорах и использовать достижения мультилинейной алгебры. Хорошая новость заключается в том, что там существует такая процедура, как тензорное разложение, которое в ряде случаев может помочь преодолеть проклятие размерности.

Разложение матриц

Прежде, чем говорить о разложении тензоров, взглянем на то, как это делается с матрицами — просто двумерными таблицами. Под разложением матрицы понимается её представление в виде произведения других матриц, обладающих более простыми или симметричными свойствами. Такую задачу, например, непрерывно решают процессоры в наших мобильных телефонах.

Среди прочего важно уметь производить ранговую факторизацию матриц. Представьте, что у вас есть матрица m×n ранга r (назовем ее A). Тогда ранговой факторизацией будет называться нахождение матриц U и V размерами m×r и r×n, произведение которых даст A. В реальности ранги матриц r могут не обязательно быть малыми. В этом случае может помочь малоранговая аппроксимация, которая заключается в ранговой факторизации в некотором приближении. С такой задачей лучше всего справляется сингулярное разложение, для которого есть множество эффективных численных реализаций. В индексном виде его результат можно записать как

A_{i,j}≈∑_{α,\beta=1}^r U_{iα} \Sigma_{α\beta} V_{\beta j},

где матрица Σ является диагональной, т.е. вне основной диагонали у неё находятся нули. Объединяя матрицу Σ с одной из матриц U или V, получаем малоранговое разложение. В идеальном случае ранг r много меньше, чем m и n.

Но что будет, если вместо Ai,j мы будем иметь дело с Ai,j,k или большим числом индексов, словом, с тензорами? Здесь уже требуются методы тензорного разложения, которые исследованы не так хорошо, как в случае матриц.

Методы тензорного разложения

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

A(i_1,…,i_d)≈∑_{α=1}^rU_1 (i_1,α)…U_d (i_d,α)

Несмотря на свою распространённость в том или ином виде, каноническое разложение сталкивается с трудностями при больших рангах. Задача сама по себе NP-сложная, и для неё нет быстрых и универсальных алгоритмов.

Этих проблем нет в разложении Таккера. В нём у матриц индексы суммирования не общие, а связанные некоторым склеивающим множителем. Разложение Таккера всегда устойчиво, но для его исполнения требуется много места для многомерного множителя, что делает обход проклятия размерности с его помощью практически бесполезным. Вот так оно выглядит:

A(i_1,…,i_d)≈∑_{α_1,…,α_d}G(α_1,…,α_d)U_1 (i_1,α_1 )…U_d (i_d,α_d ).

Еще один способ — лепить большие двумерные матрицы из наших тензоров. Для этого одну часть индексов объявляем строчными, а другу — столбцовыми индексами нашей мегаматрицы. В результате сингулярное разложение обеспечивает нас меньшими матрицами, приобретающими дополнительный индекс, к которым можно снова применить эту процедуру:

A→A_{I_1,I_2},

где

A_{I_1,I_2}≈∑_αU_{I_1,α} V_{I_2,α}.

Этот рекурсивный подход давал некоторое преимущество в скорости, но его довольно сложно программировать и он требователен к вычислительным ресурсам.

Тензорный поезд

Вместо этого Иван Оселедец, работающий ныне в Сколтехе и AIRI, более десяти лет назад предложил самый простой вид этой структуры, который получил название тензорного поезда (tensor train, TT). В этом разложении суммирование ведется по попарно общим индексам соседних трехмерных тензоров, стоящих в произведении (TT-ядер). Лучше слов эту идею проиллюстрирует формула для некоторого тензора K

\begin{array}[b]{r}    K(i_1,…,i_d )≈∑_{α_0=1}^1∑_{α_1=1}^{r_1} … ∑_{α_d=1}^1G_1 (α_0,i_1,α_1 ) G_2 (α_1,i_2,α_2 ) …\\       …G_d (α_{d-1},i_d,α_d )      \end{array}

Оказалось, что такой подход позволяет добиться O(ndr2), где r — это средний ранг ядер, что для целого ряда задач позволяет преодолеть проклятие размерности. Потом, как это часто бывает, выяснилось, что он не первый, кто придумал подобное. В квантовой физике подобные конструкции носят название состояния матричного произведения (matrix product states) и используются для описания квантовых тензорных сетей. Но хорошую вещь надо открыть как минимум дважды — иначе не очень понятно, хорошая ли она.

TT-разложение оказалось очень плодотворной идеей, особенно в машинном обучении. Например, вот в этой работе тензорные поезда используются для решения многомерных параболических уравнений в частных производных с d порядка сотни. Это побудило нас и наших коллег искать оптимальные способы вычисления ядер. Было сделано несколько таких попыток, среди которых крестовая TT-аппроксимация, чередующийся метод наименьших квадратов или чередующиеся линейные схемы. Все эти подходы объединяет одна деталь: они игнорируют возможную аналитическую связь между компонентами тензора и их индексами. Из-за этого существующие методы имеют большое время работы и плохую сходимость, даже если точное решение известно.

Учёт аналитических зависимостей

Чтобы задействовать этот ресурс мы с Иваном Оселедцем в своей недавней статье предложили новый метод построения ядер ТТ-разложения, который учитывает аналитическую зависимость компонент тензора от индексов (под аналитической зависимостью мы понимаем известную символьную формулу значения тензора, а не определение термина в рамках комплексного анализа). Технически это реализовано через цепочку функций, которые получили название производящих. Каждая из них зависит от индекса тензора, а также от результата применения другой функции на предыдущем шаге.

В общем случае процесс построения ТТ-разложения можно представить как последовательное преобразование (линейное) вектора в каждом «вагоне», начиная с конца поезда. Функции же могут не обязательно быть линейными. Решение этой проблемы оказалось довольно простым: мы присваиваем каждому возможному входному и выходному значению производящей функции различные базисные векторы, благодаря чему нужное нам преобразование может быть представлено как умножение матрицы на вектор.

Схема TT-разложения
Схема TT-разложения

На рисунке выше схематически изображен процесс ТТ-разложения некоторого тензора K, каждый элемент которого вычисляется с помощью движения по поезду с двух сторон: слева и справа. Ядра разложения обозначаются чёрными кружочками, входные индексы тензоров — синими линиями. Чёрные линии, соединяющие ядра, снабжены числом, равным размерности суммирования. Наконец, красными стрелками показано соответствие между выходным вектором, полученным последовательным перемножением ядер (слева и справа) и значениями производящих функций.

К сожалению, не существует единого алгоритмического подхода для построения последовательности производящих функций по заданной аналитической зависимости значения тензора от его индексов. Более того, такое представление не единственно, и разные представления могут привести к разным рангам результирующего тензора. Однако оказывается, что существуют достаточно общие закономерности для производящих функций, и мы надеемся, что на основе приводимых нами примеров будет несложно строить нужные последовательности по аналогии.

Проверка на практике

Предложенный нами подход работает лучше всего в тех случаях, когда производящие функции вместе с самим тензором имеют небольшое количество возможных значений. При этом ТТ-ядра, полученные новым методом, сильно разрежены, т.е. в них много нулевых элементов, что дает дополнительный выигрыш в производительности.

Мы убедились в этом, применив алгоритм к ряду задач, включающему в себя кооперативные игры, задачу о рюкзаке, задачу о расстановке n ферзей, вычисления перманента матрицы и многое другое. Так, в кооперативных играх новый подход показал превосходство, как по времени выполнения, так и по точности по сравнению с существующими методами. В случае же с вычислением перманента оценочное число операций оказалось всего в два раза больше, чем в оптимизированном ad hoc методе на основе гамильтоновых блужданий. Важно, что предложенный подход не только решает проблему проклятия размерности, но и реализует алгебру для TT-тензоров.

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

Конечно, метод не лишен недостатков: если размер множества образов, которым обладают производящие функции, слишком велик, ранг ядер растёт довольно быстро. Вообще-то, эту проблему можно решить с помощью специальной процедуры ограничения рангов, и мы планируем расширить свой алгоритм и на такой случай.

Теги:
Хабы:
Всего голосов 24: ↑24 и ↓0+24
Комментарии41

Публикации

Информация

Сайт
airi.net
Дата регистрации
Численность
101–200 человек