Машинное обучение, как и некоторые другие типы статистических задач, страдает от проблемы, называемой проклятием размерности. Он возникает, когда количество особенностей модели становится слишком большим. Объем данных растет в геометрической прогрессии, что не только увеличивает трудоемкость вычислений и требования к хранению данных, но и ставит под угрозу успех обучения.
Тензорные поезда
Одним из способов обойти эту проблему является алгоритм, основанный на разложении многомерного тензора (многомерного массива комплексных чисел) в тензорный поезд (ТТ). Впервые его предложил Иван Оселедец, ныне сотрудник Сколковского института науки и технологий и AIRI. В этом методе многомерный тензор можно выразить через произведение нескольких низкоразмерных тензоров (ТТ-ядер). В ряде важных случаев такой подход позволяет существенно сократить количество ячеек памяти, необходимых для обработки данных.
Существующие методы, такие как метод TT-кросс-аппроксимации или метод попеременных наименьших квадратов, рассматривают значения тензора как черный ящик. Другими словами, эти методы не учитывают аналитическую зависимость, если таковая имеется, значения тензора от его индексов. Из-за этого существующие методы могут долго строить TT-разложение и иметь плохую сходимость, даже если исходный тензор имеет точное TT-разложение.
Аналитическая зависимость от индексов
Чтобы воспользоваться этим ресурсом, Иван Оселедец в сотрудничестве с научным сотрудником Сколтеха Глебом Рыжаковым недавно представили быстрый метод прямого построения ядер TT-разложения тензора, для которого известна аналитическая зависимость значения тензора от значений его индексов. . Технически новый метод работает с функциями, каждая из которых зависит от индекса тензора и последовательно применяется к значениям предыдущих функций. Авторы назвали их производными функциями.
К сожалению, не существует единого алгоритмического подхода к построению последовательности производных функций на основе заданной аналитической зависимости значения тензора от его индексов. Более того, такое представление не уникально и разные представления могут привести к разным рангам результирующего тензора. Команда привела несколько примеров разных наборов производных функций для одного и того же тензора. Однако оказывается, что для производных функций существуют довольно общие закономерности. Авторы надеются, что на основе приведенных ими примеров из различных приложений метода нетрудно по аналогии построить искомую последовательность производных функций для конкретной прикладной задачи.
Оказалось, что новый подход лучше всего работает в тех случаях, когда производные функции вместе с самим тензором имеют небольшое число возможных значений. При этом ТТ-ядер, полученных новым методом, очень мало, что дает дополнительный выигрыш в производительности.
Практическое применение
Команда доказала это, применив алгоритм к ряду задач, включая кооперативные игры, задачу о рюкзаке, задачу n-ферзя, вычисление матричных перманентов и многое другое. В кооперативных играх они сравнивают его с существующими методами и показывают наше превосходство как по времени выполнения, так и по точности. Для задачи вычисления перманента матрицы новый метод дает оценочное количество операций лишь в два раза больше, чем оптимизированный ad hoc метод вычисления перманента с помощью гамильтоновых блужданий. Важно, что предложенный подход не только позволяет преодолеть проклятие размерности, но и реализует алгебру для TT-тензоров.
Ученые заметили, что ограничением их метода является быстрый рост рангов в случае, когда производные функции имеют большой размер своего множества изображений. Хотя у них есть процедура ограничения ранга для этого случая, авторы планируют указать расширение алгоритма для точного построения TT-разложения и для таких случаев, если известно, что оно имеет низкий ранг.
Подробнее можно прочитать в статье, опубликованной в Трудах конференции ICLR 2023.
