Тензорные методы в задачах машинного обучения тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Новиков Александр Витальевич

• Новиков Александр Витальевич
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Новиков Александр Витальевич

Введение

Глава 1. Основные понятия

1.1 Тензорные методы

1.2 Обозначения

1.3 Разложение в тензорный поезд

1.3.1 TT-SVD

1.3.2 Другие операции над ТТ-тензорами

1.3.3 Матричный ТТ-формат

1.4 Методы римановой оптимизации

1.5 Машинное обучение (распознавание образов)

1.6 Автоматическое дифференцирование и обратное распространение ошибки

1.7 Выводы

Глава 2. Тензорный алгоритм вывода в марковских случайных полях

2.1 Марковски случайные поля

2.2 Существующие подходы к задаче вывода

2.3 Тензорный алгоритм вывода

2.3.1 Тензоры марковского случайного поля

2.3.2 Вычисление нормировочной константы Z

2.3.3 Доказательство следствия

2.4 Выводы

Глава 3. Тензорные разложения для сжатия и ускорения нейронных

сетей

3.1 Обзор существующих подходов к сжатию нейронных сетей

3.2 Тензорный алгоритм сжатия

3.3 Модель учитывающая взаимодействия признаков высоких

порядков

3.3.1 Предлагаемая модель

Стр.

3.3.2 Быстрый метод вывода

3.3.3 Методы обучения

3.3.4 Степенная регуляризация

3.3.5 Обобщение модели

3.3.6 Связь с рекуррентными нейросетями

3.4 Риманово автоматическое дифференцирование

3.4.1 Риманов градиент для матриц фиксированного ранга

3.4.2 Автоматическое вычисление риманова градиента на многообразии тензоров фиксированного ТТ-ранга

3.4.3 Произведение линеаризованного риманова гессиана на заданный вектор

3.5 Выводы

Глава 4. Комплексы программ и результаты численных экспериментов

4.1 Комплекс программ для тензорных вычислений t3f

4.1.1 Интерфейс программного кода

4.1.2 Список поддерживаемых операций

4.1.3 Быстродействие пакета

4.1.4 Реализация новых операций и их асимптотическая сложность

4.1.5 Риманово автоматическое дифференцирование

4.1.6 Использование комплекса программ T3F в научных проектах

4.2 Реализация алгоритма вывода в МСП

4.2.1 Модель Изинга

4.2.2 ^-ранги энергии и вероятности

4.2.3 Нормировочная константа

4.2.4 Унарные маргинальные распределения

4.3 Реализация алгоритма сжатия нейросетей

4.3.1 Свойства ТТ-слоя

4.3.2 CIFAR-10

4.3.3 ImageNet

4.4 Реализация тензорных полиномиальных моделей

4.4.1 Наборы данных

Стр.

4.4.2 Сравнение методов оптимизации и инициализации

4.4.3 Степенная регуляризация

4.4.4 Сравнение предложенного метода с альтернативами

4.4.5 Зависимость от TT-ранга

4.5 Выводы

Заключение

Список сокращений и условных обозначений

Словарь терминов

Список литературы

Введение диссертации (часть автореферата) на тему «Тензорные методы в задачах машинного обучения»

Введение

Актуальность темы исследования. Машинное обучение переживает период бурного развития, и за последние годы совершен существенный прогресс во многих важных на практике задачах, таких как распознавание объектов, изображенных на фотографиях, сегментация фотографий, машинный перевод, распознавание и синтез речи, и др. Тем не менее, алгоритмы, показывающие наилучшее качество во многих задачах (такие, как нейронные сети и марковские случайные поля) вычислительно затратны как во время обучения, так и во время использования моделей. Так, языковая модель1 может требовать вычислительного кластера с петабайтами оперативной памяти и мощностью до сотен петафлопс для обучения [7]. Несмотря на то, что многие корпорации могут себе позволить обучение таких (или несколько менее затратных) моделей, столь высокая вычислительная сложность замедляет прогресс в области машинного обучения и останавливает исследователей, не обладающих достаточными вычислительными ресурсами, от работы над передовыми моделями.

Другой важный барьер на пути распространения машинного обучения, это ресурсозатратность применения уже обученных моделей к новым объектам. Особенно актуальна эта проблема в контексте использования моделей машинного обучения в мобильных и встроенных устройствах (таких, как смартфоны и компьютеры на борту беспилотных автомобилей), на которых доступны существенно меньшие вычислительные мощности для применения модели по сравнению с традиционными компьютерами. Например, современная модель машинного перевода может требовать сравнительно небольших ресурсов для перевода одного предложения на другой язык: сотен мегабайт оперативной памяти и десятков терафлоп [8]. Однако, такая сложность оказывается недопустимой для использования на мобильных устройствах, как по части быстродействия и требования к памяти, так и по части использования ресурса аккумулятора. В частности, размер требуемой памяти является одним из ограничивающих факторов к снижению энергопотребления моделей. Так, при использовании 45 нм техпроцесса по техно-

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

логии КМОП2, требуется 0.9 пДж энергии, чтобы сложить два 32-битных числа с плавающей точкой; доступ к одному 32-битному числу в кэше SRAM требует 5 пДж энергии; и доступ к 32-битному числу в оперативной памяти требует 640 пДж энергии, что на три порядка больше по сравнению с операцией сложения. Большие искусственные нейронные сети не помещаются в кэш процессора и, таким образом, требуют ресурсоемкого доступа к оперативной памяти.

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

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

Научная новизна. Предложен новый метод оценки нормировочной константы и маргинальных распределений марковского случайного поля (статистики, использующиеся как для обучения марковских случайных полей, так и для их применения к новым объектам), существенно превосходящий аналоги по скорости работы. Получены теоретические результаты по оценке точности работы предложенных методов.

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

2Комплементарная структура металл-оксид-полупроводник; англ. CMOS, complementary metal-oxide-semiconductor.

к параметрам. Разработанный метод римановой оптимизации использует структуру модели и оптимизируемой функции, чтобы достичь высокой скорости работы.

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

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

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

1. Разработан комплекс программ для работы с разложением в тензорный поезд на языке Python с поддержкой графических ускорителей;

2. Предложен вычислительный метод оценки нормировочной константы и маргинальных распределений марковского случайного поля, и получена теоретическая оценка точности его работы;

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

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

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

1. Международная конференция по искусственному интеллекту и статистике (AISTATS), 2018, Тенерифе, Испания

2. Научный семинар компании Яндекс, 2018, Москва, Россия

3. Фестиваль данных (Data Fest), 2018, Москва, Россия

4. Спецсеминар ИВМ РАН, 2018, Москва, Россия

5. Научный семинар компании Uber AI, 2017, Сан Франциско, США

6. Научный семинар компании OpenAI, 2017, Сан Франциско, США

7. 60-я Научная конференция МФТИ, 2017, Москва, Россия

8. Спецсеминар ИВМ РАН, 2017, Москва, Россия

9. Коллоквиум факультета комьютерных наук ВШЭ, 2017, Москва, Россия

10. Семинар лаборатории научных вычислений Сколтеха, 2017, Москва, Россия

11. Воркшоп международной конференции по обучению представлений (ICLR), 2017, Тулон, Франция

12. Спецсеминар ИППИ РАН, 2016, Москва, Россия

13. Семинар лаборатории научных вычислений Сколтеха, 2016, Москва, Россия

14. Воркшоп NeurIPS по обучению с использований тензоров, 2016, Барселона, Испания

15. Спецсеминар ИВМ РАН, 2016, Москва, Россия

16. Нейросетевые системы обработки информации (NeurIPS), 2015, Торрон-то, Канада

17. Воркшоп ICML по машинному обучению с использований тензоров, 2015, Нью Йорк, США

18. Семинар лаборатории научных вычислений Сколтеха, 2015, Москва, Россия

19. Спецсеминар «Байесовские методы машинного обучения», 2015, Москва, Россия

20. Международная конференция матричных методов в математики и приложениях, 2015, Москва, Россия

21. Научный семинар компании Google, 2014, Маунтин-Вью, США

22. Конференция SIAM по науке работе с изображениями (SIAM IS), 2014, Гонконг

23. Международная конференция по машинному обучению (ICML), 2014, Пекин, Китай

24. Семинар лаборатории научных вычислений Сколтеха, 2014, Москва, Россия

25. Спецсеминар «Байесовские методы машинного обучения», 2014, Москва, Россия

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

Публикации повышенного уровня

[1] Новиков А. В., Измаилов П. А., Хрульков В. А., Фигурнов М. В., Оселедец И. В. ТТ разложение на ТензорФлоу (T3F) // Журнал исследований машинного обучения (JMLR), секция Программное обеспечение для машинного обучения с открытым исходным кодом. - 2020. - № 21. - с. 1-7. Q2 Web of Science.

[2] Рахуба М. В., Новиков А. В., Оселедец И. В. Низкоранговый метод поиска собственных значений для многомерных гамильтонианов // Журнал вычислительной физики. - 2019. - № 396. - С. 718-737. В данной работе вклад автора выносящийся на защиту состоит в написании кода с использованием разработанного программного комплекса и проведении экспериментов. Q1 Web of Science.

[3] Новиков А. В., Подоприхин Д. А., Осокин А. А., Ветров Д. П. Тензориза-ция нейронных сетей // Нейросетевые системы обработки информации (NeurIPS). - 2015. - № 28. - С. 442-450. A* по рейтингу CORE.

[4] Новиков А. В., Родоманов А. О., Осокин А. А., Ветров Д. П. Тензорный поезд в марковском случайном поле / / Международная конференция по машинному обучению (ICML). - 2014. A* по рейтингу CORE.

Публикации стандартного уровня

[5] Новиков А. В., Трофимов М. И., Оселедец И. В. Экспоненциальные машины. // Вестник Польской Академии технических наук, специальный выпуск по

глубокому обучению: теория и практика. - 2018. - № 6. - С. 789-797. Q3 Web of Science.

Прочие публикации

[6] Новиков А. В., Родоманов А. О., Осокин А. А., Ветров Д. П., Тензорный поезд в марковском случайном поле, журнал «Интеллектуальные системы. Теория и приложения», стр. 293-318, 2014.

Личный вклад автора. Данная работа является самостоятельным трудом автора. Лично автором был реализован комплекс программ T3F [1], предложен и реализован метод автоматического риманова дифференцирования, предложена и реализована модель учитывающая взаимодействия признаков высоких порядков [5], реализована и протестирована в численных экспериментах модель искусственной нейронной сети [3], использующая тензорное разложение для сжатия весов сети. Идея метода оценки нормировочной константы марковского случайного поля [4; 6] была разработан совместно с И. В. Оселедцем и Д.П. Ветровым, а лично автором данной работы был реализован разработанный метод и произведен его теоретический анализ. Постановка задачи в работах [3; 4; 6] была выполнена Д. П. Ветровым. Постановка задачи в работе [2] и в предложенном методе по автоматическому риманову дифференцированию была выполнена И. В. Оселедцем. Так же автором реализован метод поиска собственных значений матриц в ТТ-формате в приложении к поиску вибрационного спектра молекул [2].

Структура работы. Полный объём диссертации составляет 126 страниц, вклю-чая15 рисунков и 8 таблиц. Список литературы содержит 77 наименований.

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

Именно благодаря Дмитрию Петровичу Ветрову на первом курсе университета я вдохновился заняться наукой. Он всегда подпитывал мой интерес и любо-

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

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

Конечно, я не могу перечислить в нескольких параграфах весь тот неоценимый вклад, который И. В. Оселедец и Д. П. Ветров внесли в мое становление как ученого в ходе многочасовых научных совещаний, совместного программирования, написания текстов, и прочего. Но я хочу сказать им большое спасибо за их труд и терпение.

Также, я хотел бы выразить благодарность Антонону Осокину и Максиму Рахубе, от которых я перенял очень много опыта в проведении научных исследований, и сотрудничество с которыми (которое, надеюсь, продолжится и в будущем) я всегда буду вспоминать как очень продуктивный и приятный период моей жизни.

И наконец, я бы хотел выразить благодарность всем своим учителям в МГУ им. М. В. Ломоносова и ИВМ РАН им Г. И. Марчука, чьи знания, профессионализм и усилия позволили мне овладеть всеми необходимыми знаниями для того, чтобы заниматься научными исследованиями.

Глава 1. Основные понятия

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

1.1 Тензорные методы

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

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

Также интерпретация задачи как многомерной дает возможность по-новому взглянуть на проблему и применить арсенал тензорных методов. Так, благодаря интерпретации рекуррентных нейронных сетей как тензорного скалярного произведения тензора параметров с данными, для обучения таких сетей удается применить методы римановой оптимизации (раздел 3.3.3).

Интерпретация вероятностного распределения, порожденного марковским случайным полем, как тензорного разложения и учет структуры факторов данного разложения позволяет получить эффективный алгоритм аппроксимации статистик данного распределения, опережающий аналоги по точности работы (Глава 2).

1.2 Обозначения

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

В данной работе вектора обозначаются жирными буквами нижнего регистра (например а), а матрицы - жирными буквами верхнего регистра (например A).

Под d-мерным тензором A Е Rnix---xnd понимается многомерный массив чисел индексируемый вектор-индексом (¿1,..., id), ik Е {1,..., nk}, k = 1,...,d. Длина d вектор-индекса называется размерностью тензора. Тензоры будут обозначаться жирными готическими буквами верхнего регистра (например A).

При индексации массивов, жирный шрифт будет опускаться, и будут равнозначно использоваться следующие обозначения (в зависимости от контекста): ai = a(i) для обозначения ¿-ого элемента вектора а, Ai;j = A(i,j) для индексации матриц, и Ai1,...,id = A(i1, ...,id) для индексации тензоров.

1.3 Разложение в тензорный поезд

А данном разделе вводится одно из обобщений матричного низкорангового формата на тензорный случай - разложение в тензорный поезд или ТТ-разложение [9], которое используется на протяжении данной диссертации. ТТ-разложение также известно под названием Matrix Product State (MPS) [10; 11].

Определение 1. [9, Формула 1.2] Будем говорить, что d-мерный тензор A Е Rnix -xnd представлен в TT-формате, если для всех k = 1,... ,d и всех значений

О)

О2

Оз

О 4

ЛоА23 —

I , I , I

X

¿1 — 2

|. 1. 1

1, 11, 11

X

I . I . 1

I, I, I

X

¿2 — 4 ¿3 — 2 ¿4 — 3

Рисунок 1.1 — Иллюстрация разложения в тензорный поезд для тензора А размера 3 х 4 х 4 х 3, все ТТ-ранги которого равны 3.

индексов гк — 1,...,пк (п — тахк=1,...^ пк) существуют матрицы ], такие, что каждый элемент тензора А представим в виде произведения этих матриц (см. Рис. 1.1):

Агъ...м — •••оАи (1.1)

При этом все матрицы относящиеся к одному и тому же индексу к должны иметь одинаковые размеры гк-1(А) х гк (А). Чтобы результат матричного произведения (1.1) был равен числу (соответствующему элементу тензора А), положим го (А) — г ¿(А) — 1.

Упорядоченное множество {гк(А)Ук=0 будем называть рангами тензора А, а максимальный элемент данного множества - максимальным рангом тензора А: г(А) — тахк=0)...^гк(А). Отображение СА : {1,...,пк} ^ ^Гк-1(А)хГк(А), соответствующее одному измерению, называется ядром тензора А. Представление тензора в ТТ-формате будем называть ^-разложением или представлением.

Для любого ¿-мерного тензора А существует ТТ-представление с максимальным ТТ-рангом г(А) ^ п2 (см. теорему 2.1 из [9]). Отметим, что ТТ-пред-ставление тензора не единственно, т.е. один и тот же тензор можно представить разными способами (и с разными ТТ-рангами) в формате (1.1). Например, тензор равный нулю во всех элементах можно представить взяв ТТ-представление любого другого тензора (с произвольными ТТ-рангами) и заменив элементы всех ТТ-ядер на нули.

Для обозначения (ак-1, ак)-ого элемента матрицы 0А\гк] будет использоваться символ ОА[гк](ак-1, ак). При этом при реализации ТТ-разложения на ЭВМ, ядра СА будут храниться как трехмерные массивы, индексируемые в порядке ак-1, ¿к, ак, так как такой порядок индексов допускает более эффективную

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

Агъ...м = С^Коо, а:) ...С^И^-ь ап). (1.2)

Для краткости, в случае когда это не вызывает разночтений, тензор, ТТ-разложение которого сейчас рассматривается, может опускаться в обозначениях: Ок вместо ОА, гк-1 вместо гк-1(А), и т.п.

Для хранения всех элементов тензора А требуется Пк=1 пк ячеек памяти, тогда как хранение А в ТТ-формате требует ^пк гк-1(А) гк(А). Таким образом, ТТ-представление тензора с низкими ТТ-рангами существенно компактнее перечисления его элементов.

Существуют две различные постановки задачи перевода тензора в ТТ-фор-мат: точное ТТ-представление (алгоритм TT-SVD [9], применимый для небольших тензоров), и построение приближенного ТТ-представления по небольшому подмножеству элементов тензора. Наилучшим из алгоритмов второго класса в настоящее время является метод AMEn-cшss [12].

1.3.1 TT-SVD

Обсудим более подробно алгоритм ТТ-SVD для перевода тензора в ТТ-формат с заданной точностью [9, раздел 2].

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

Определение 2. Пусть задан тензор A Е Rnix - xnd. Обозначим за vec(A) Е Rnfc=i nk операцию вытягивания тензора в вектор содержащий все элементы тензора A в лексикографическом порядке.

Определение 3. Пусть задан тензор A Е Rnix - xnd. Обозначим за reshape(A,m1,...,mq) тензор B Е Rmix-xm? такой, что vec(A) = vec(B). Например, reshape(A, Пf=1 nk) = vec(A)

Определение 4. [9, Формула 2.1] К-ой матрицей развертки тензора А Е ^п1х -хп^ (к = 1,...,^ — 1) называется матрица reshape(A, п1 ••• пк,пк+1 •• • п^) = А(к) Е

К(пг-пй )х(пй+г"п^)

Для индексирования матриц развертки мы будем пользоваться двумя вектор-индексами, отделенными точкой с запятой

; 4+1,...,^) = А(«1,...,г^) (1.3)

Рассмотрим теперь матрицу развертки А(1). Пусть её ранг равен г1. Воспользуемся SVD разложением, т.е. найдем унитарные матрицы и Е К"4ХГ1, V Е Кп2ХГ1 и диагональную матрицу $ Е КГ1ХГ1 такие, что

а(1) =

О1 Wт

или, в поэлементной форме

Г1

; ¿2,...,г^) = и(¿1, (а1; ¿2,..

а1=1

Матрица W может быть представлена в виде

W = (А(1)) т и,

или, в поэлементной форме

п1

Ж(а1; ¿2, ...,¿<0 = ^ А(1)(¿1; ¿2,.. (¿1, а1).

«1=1

Теперь, матрица W может быть интерпретирована как (^ — 1)-мерный тензор ^, в котором (а1г2) интерпретируются как один длинный индекс

^ (а^2, ¿3,..., ¿¿) = Ж (аь ¿2,..., ¿¿) Повторим процесс аналогичный описанному выше, чтобы получить

Г2

W (^¿2, ¿3,...^)=Е и 7(а1, ¿2; а2) ^ 5^2, а2)У/(а2; ¿3, ¿4,..., ¿<*)

а-2=1 ^ , . а2

^2(а1,«2 ;а2) _

^ '(а2,гз;«4,...,г^)

Повторяя данный процесс снова и снова, получим упорядоченное множество ТТ-ядер О1,..., О^.

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

Теорема 1. [9, Теорема 2.2.] Пусть все матрицы развертки тензора A удовлетворяют A^ = Rk + Ek, где матричный ранг rankRk = rk, ||Ek||F = £k, k = — 1. Тогда алгоритм ТТ-SVD при использовании сокращенных SVD

разложений рангов r\,..., rd — 1 на каждом шаге найдет тензор B в ТТ-формате с ТТ-рангами {rkтакой, что

A-B\\f ^

\

d—1

£2

£

k=i

1.3.2 Другие операции над ТТ-тензорами

Одним из основных достоинств ТТ-формата является возможность эффективно применять различные операции к тензорам в ТТ-формате с вычислительной сложностью меньшей чем размеры данных тензоров: умножение тензора на константу, добавление константы к тензору, поточечное сложение и умножение тензоров (результат этих операций — это тензор в ТТ-формате с возросшими ТТ-рангами); подсчет глобальных характеристик тензора, таких как сумма всех элементов или норма Фробениуса. Обзор часто употребимых операций над ТТ-тензорами приведен в таблице 1 (детальный обзор см в работе [9]).

Рассмотрим для примера реализацию алгоритма сложения ТТ-тензоров (раздел 4.1 [9]). Пусть даны два тензора в ТТ-формате

А(ц,...,¿<0 — сАМ• • • сАы, ад,...,¿0 — оВ[¿1]• • • оВ[¿¿]

ТТ-ядра тензора-суммы С = А + В могут быть представлены в следующем

виде

где под 0 понимается матрица соответствующего размера равная нулю во всех элементах.

Действительно, умножая блочные ТТ-ядра получим

оС [¿1]оС [¿2] •• • оС и = оАмоАы •• • оАы + о? [¿1]оВ [¿2] •• • о? и

Обратите внимание, что ТТ-ранг полученного ТТ-представления тензора С равен сумме ТТ-рангов тензоров А и В.

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

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

Чтобы контролировать такой излишний рост ТТ-рангов, существует операция ТТ-округления. По ТТ-представлению тензора А и относительной точности £ ^ 0 операция ТТ-округления round(A,£) найдет тензор А в ТТ-формате, который, во-первых, достаточно близок к тензору А: || А — А.||Р ^ £|| А||Р и, во-вторых, обладает минимальными ТТ-рангами среди всех тензоров В : 11А — ^ Тс£—1ЦАЦ-Р. Наличие операции ТТ-округления позволяет применять последовательность операций к тензорам (например, округляя результат после применения каждой операции), контролируя рост ТТ-рангов.

и

оС [¿1] = (оАы о?и), оС и

(оАы) [о1? му

Таблица 1 — Операции, которые можно эффективно выполнять над тензорами в TT-формате. Для каждой операции указана её вычислительная сложность и TT-ранг результата для ситуаций, когда результат является тензором в TT-формате.

Операция Ранг результата Вычислительная сложность

C = A ■ const r(C) = r( A) O(n r( A))

C = A + const r(C )= r(A) + 1 O(nd r2(A))

C = A + B r(C) ^ r(A)+r(B) O(nd (r(A) + r(B))2)

Список литературы диссертационного исследования кандидат наук Новиков Александр Витальевич, 2021 год

Список литературы

1. Tensor Train Decomposition on TensorFlow (T3F) / A. Novikov [и др.] // Journal of Machine Learning Research, Machine Learning Open Source Software (JMLR MLOSS). — 2020. — Т. 21, № 30. — С. 1—7.

2. Rakhuba M. Low-rank Riemannian eigensolver for high-dimensional Hamiltonians / M. Rakhuba, A. Novikov, I. Oseledets // Journal of Computational Physics. — 2019. — Т. 396. — С. 718—737.

3. Tensorizing neural networks / A. Novikov [и др.] // Advances in Neural Information Processing Systems. — 2015. — С. 442—450.

4. Putting MRFs on a Tensor Train / A. Novikov [и др.] // International Conference on Machine Learning (ICML). — 2014. — С. 811—819.

5. Novikov A. Exponential machines / A. Novikov, M. Trofimov, I. Oseledets // Bulletin of the Polish Academy of Sciences: Technical Sciences. — 2018. — Т. 6.

6. Тензорный поезд в марковском случайном поле / А. Новиков [и др.] //. — 2014.— С. 293—318.

7. Language models are few-shot learners / T. B. Brown [и др.] // Advances in Neural Information Processing Systems 33 (NeurIPS). — 2020.

8. The Best of Both Worlds: Combining Recent Advances in Neural Machine Translation / M. X. Chen [и др.] // arXiv preprint arXiv:1804.09849. — 2018.

9. Oseledets I. V. Tensor-Train Decomposition /1. V. Oseledets // SIAM J. Scientific Computing. — 2011. — Т. 33, № 5. — С. 2295—2317.

10. Fannes M. Nachtergaele B. W. R. Finitely correlated states on quantum spin chains / W. R. Fannes M. Nachtergaele B. // Comm. Math. Phys. — 1992. — Т. 144, № 3. — С. 443—490.

11. Klumper A. Schadschneider A. Z. /.Matrix Product Ground States for One-Dimensional Spin-1 Quantum Antiferromagnets / Z. J. Klumper A. Schadschneider A. / Europhys. Lett. — 1993. — Т. 24, № 4. — С. 293—297.

12. Dolgov S. V. Alternating minimal energy methods for linear systems in higher dimensions. Part II: Faster algorithm and application to nonsymmetric systems : arXiv preprint / S. V. Dolgov, D. V. Savostyanov. — 2013. — № 1304.1222.

13. Holtz S. On manifolds of tensors of fixed TT-rank / S. Holtz, T. Rohwedder, R. Schneider // Numerische Mathematik. — 2012. — C. 701—731.

14. Robbin J. W Introduction to Differential Geometry / J. W. Robbin, D. A. Salamon // ETH, Lecture Notes. — September, 2013. — URL: https : //people.math.ethz.ch/~salamon/PREPRINTS/diffgeo.pdf..

15. Absil P.-A. An extrinsic look at the Riemannian Hessian / P.-A. Absil, R. Mahony, J. Trumpf // International Conference on Geometric Science of Information. — Springer. 2013. — C. 361—368.

16. Rakhuba M. Jacobi-Davidson Method on Low-Rank Matrix Manifolds / M. Rakhuba, I. V. Oseledets // SIAM Journal on Scientific Computing. — 2018. — T. 40, № 2. — A1149—A1170.

17. Kressner D. Preconditioned low-rank Riemannian optimization for linear systems with tensor product structure / D. Kressner, M. Steinlechner, B. Vandereycken // SIAM Journal on Scientific Computing. — 2016. — T. 38, № 4. — A2018— A2044.

18. Steinlechner M. M. Riemannian Optimization for Solving High-Dimensional Problems with Low-Rank Tensor Structure / M. M. Steinlechner // PhD Thesis. — 2016. — T. 6958. — URL: https://infoscience.epfl.ch/record/217938/files/ EPFL%7B%5C_%7DTH6958.pdf.

19. Absil P.-A. Projection-like retractions on matrix manifolds / P.-A. Absil, J. Malick // SIAM Journal on Optimization. — 2012. — T. 22, № 1. — C. 135— 158.

20. Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer / N. Shazeer [h gp.] // International Conference on Learning Representations (ICLR). — 2017.

21. Automatic differentiation in machine learning: a survey / A. G. Baydin [h gp.]. — 2018.

22. Learning representations by back-propagating errors / D. E. Rumelhart, G. E. Hinton, R. J. Williams [h gp.] // Cognitive modeling. — 1988. — T. 5, №3. —C. 1.

23. Gander W. Scientific computing-An introduction using Maple and MATLAB. T. 11 / W. Gander, M. J. Gander, F. Kwok. — Springer Science & Business, 2014.

24. Margossian C. C. A Review of automatic differentiation and its efficient implementation / C. C. Margossian // Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. — 2019. — T. 9, № 4. — e1305.

25. Boykov Y. Markov random fields with efficient approximations / Y. Boykov, O. Veksler, R. Zabih // Computer vision and pattern recognition, 1998. Proceedings. 1998 IEEE computer society conference on. — IEEE. 1998. — C. 648—655.

26. Valiant L. G. The complexity of computing the permanent / L. G. Valiant // Theoretical computer science. — 1979. — T. 8, № 2. — C. 189—201.

27. A Comparative Study of Modern Inference Techniques for Discrete Energy Minimization Problems / J. Kappes [et al.] // IEEE Conference on Computer Vision and Pattern Recognition (CVPR). — 2013.

28. Neal R. Annealed importance sampling / R. Neal // Statistics and Computing. — 2001. —T. 11. —C. 125—139.

29. Grosse R. Annealing between Distributions by Averaging Moments / R. Grosse, C. Maddison, R. Salakhutdinov // Neural Information Processing Systems (NIPS).— 2013.

30. Kschischang F. R. Factor Graphs and the Sum-Product Algorithm / F. R. Kschischang, B. J. Frey, H.-A. Loeliger // IEEE Transactions on Information Theory. — 2001. — T. 47, № 2. — C. 498—519.

31. Wainwright M. ./.Graphical models, exponential families, and variational inference / M. J. Wainwright, M. I. Jordan // Foundations and Trends in Machine Learning. — 2008. — T. 1, № 1/2. — C. 1—305.

32. Minka T. Tree-structured Approximations by Expectation Propagation / T. Minka, Y. Qi // Neural Information Processing Systems (NIPS). — 2004.

33. Wainwright M. /. A new class of upper bounds on the log partition function / M. J. Wainwright, T. Jaakkola, A. S. Willsky // IEEE Transactions on Information Theory. — 2005. — T. 51, № 7. — C. 2313—2335.

34. Hazan T. On sampling from the Gibbs distribution with random maximum a posteriori perturbations / T. Hazan, S. Maji, T. Jaakkola // Neural Information Processing Systems (NIPS). — 2013.

35. Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization / S. Ermon [h gp.] // International Conference on Machine Learning (ICML). — 2013.

36. Xue J. Restructuring of deep neural network acoustic models with singular value decomposition / J. Xue, J. Li, Y. Gong // Interspeech. — 2013. — C. 2365—2369.

37. Predicting Parameters in Deep Learning / M. Denil [h gp.] // Advances in Neural Information Processing Systems 26 (NIPS). — 2013. — C. 2148—2156.

38. Compressing Neural Networks with the Hashing Trick / W. Chen [h gp.] // International Conference on Machine Learning (ICML). — 2015. — C. 2285— 2294.

39. Compressing Deep Convolutional Networks using Vector Quantization / Y. Gong [h gp.] // arXiv preprint. — 2014. — № 1412.6115.

40. Deep Learning with Limited Numerical Precision/ S. Gupta [ugp.] //International Conference on Machine Learning (ICML). — 2015. — C. 1737—1746.

41. On multiplicative integration with recurrent neural networks / Y. Wu [h gp.] // Advances in Neural Information Processing Systems. —2016. — C. 2856—2864.

42. Vandereycken B. Low-rank matrix completion by Riemannian optimization /

B. Vandereycken // SIAM Journal on Optimization. — 2013. — T. 23, № 2. —

C. 1214—1236.

43. Steinlechner M. Riemannian Optimization for Solving High-Dimensional Problems with Low-Rank Tensor Structure / M. Steinlechner. — 2016.

44. Izmailov P. Scalable Gaussian Processes with Billions of Inducing Inputs via Tensor Train Decomposition / P. Izmailov, A. Novikov, D. Kropotov // The 21st International Conference on Artificial Intelligence and Statistics (AISTATS 2018).— 2018.

45. Rasmussen C. E. Gaussian processes in machine learning / C. E. Rasmussen // Advanced lectures on machine learning. — Springer, 2004. — C. 63—71.

46. ImageNet Large Scale Visual Recognition Challenge / O. Russakovsky [h gp.] // International Journal of Computer Vision (IJCV). — 2015.

47. Quiñonero-Candela J. A unifying view of sparse approximate Gaussian process regression / J. Quiñonero-Candela, C. E. Rasmussen // Journal of Machine Learning Research. — 2005. — T. 6, Dec. — C. 1939—1959.

48. Wilson A. G. Kernel interpolation for scalable structured Gaussian processes (KISS-GP) / A. G. Wilson, H. Nickisch // International Conference on Machine Learning. — 2015. — C. 1775—1784.

49. Arbenz P. Lecture notes on solving large scale eigenvalue problems / P. Arbenz, D. Kressner, D. Zürich // D-MATH, EHT Zurich. — 2012. — T. 2.

50. Thomas P. S. Using Nested Contractions and a Hierarchical Tensor Format to Compute Vibrational Spectra of Molecules with Seven Atoms / P. S. Thomas, T. Carrington Jr // J. Phys. Chem. A. — 2015. — C. 13074—13091.

51. Rakhuba M. Calculating vibrational spectra of molecules using tensor train decomposition / M. Rakhuba, I. Oseledets // The Journal of chemical physics. — 2016.

52. Khrulkov V. Expressive power of recurrent neural networks / V. Khrulkov, A. Novikov, I. Oseledets // 6th International Conference on Learning Representations, ICLR. — 2018.

53. Cohen N. On the expressive power of deep learning: A tensor analysis / N. Cohen, O. Sharir, A. Shashua // Conference on Learning Theory. — 2016. — C. 698— 728.

54. Harshman R. A. Foundations of the parafac procedure: models and conditions for an "explanatory"multimodal factor analysis / R. A. Harshman. — 1970.

55. Carroll J. D. Analysis of individual differences in multidimensional scaling via an N-way generalization of "Eckart-Young" decomposition / J. D. Carroll, J.-J. Chang // Psychometrika. — 1970. — T. 35, № 3. — C. 283—319.

56. Mooij J. M. libDAI: A Free and Open Source C++ Library for Discrete Approximate Inference in Graphical Models / J. M. Mooij // Journal of Machine Learning Research. — 2010. — Abe — T. 11. — C. 2169—2173.

57. LeCun Y. The MNIST database of handwritten digits / Y. LeCun, C. Cortes, C. J. C. Burges. — 1998.

58. Krizhevsky A. Imagenet classification with deep convolutional neural networks / A. Krizhevsky, I. Sutskever, G. E. Hinton // Advances in neural information processing systems. — 2012. — C. 1097—1105.

59. Improving neural networks by preventing co-adaptation of feature detectors / G. E. Hinton [h gp.] // arXiv preprint arXiv:1207.0580. — 2012.

60. Krizhevsky A. Learning multiple layers of features from tiny images : guc. ... Mar. / Krizhevsky A. — Computer Science Department, University of Toronto, 2009.

61. Maxout networks / I.J. Goodfellow [u gp.] // International Conference on Machine Learning (ICML). — 2013. — C. 1319—1327.

62. Snoek ./.Practical Bayesian optimization of machine learning algorithms / J. Snoek, H. Larochelle, R. P. Adams // Advances in Neural Information Processing Systems 25 (NIPS). — 2012. — C. 2951—2959.

63. Cybenko G. Approximation by superpositions of a sigmoidal function / G. Cybenko // Mathematics of control, signals and systems. — 1989. — C. 303— 314.

64. Simonyan K. Very Deep Convolutional Networks for Large-Scale Image Recognition / K. Simonyan, A. Zisserman // International Conference on Learning Representations (ICLR). — 2015.

65. Ba /. Do Deep Nets Really Need to be Deep? / J. Ba, R. Caruana // Advances in Neural Information Processing Systems 27 (NIPS). — 2014. — C. 2654—2662.

66. Deep Fried Convnets / Z. Yang [ngp.] // arXiv preprint. — 2014. —№ 1412.7149.

67. Krizhevsky A. ImageNet Classification with Deep Convolutional Neural Networks / A. Krizhevsky, I. Sutskever, G. E. Hinton // Advances in Neural Information Processing Systems 25 (NIPS). — 2012. — C. 1097—1105.

68. Qian N. On the momentum term in gradient descent learning algorithms / N. Qian // Neural networks. — 1999. — T. 12, № 1. — C. 145—151.

69. Dheeru D. UCI Machine Learning Repository / D. Dheeru, E. K. Taniskidou. — 2017. —URL: http://archive.ics.uci.edu/ml.

70. Harper F. M. The movielens datasets: History and context / F. M. Harper, A. J. Konstan // ACM Transactions on Interactive Intelligent Systems (TiiS). — 2015.

71. Higher-Order Factorization Machines / M. Blondel [u gp.] // Advances in Neural Information Processing Systems 29 (NIPS). — 2016.

72. Kingma D. Adam: A method for stochastic optimization / D. Kingma, J. Ba // International Conference on Learning Representations (ICLR). — 2015.

73. Friedman J. H. Greedy function approximation: a gradient boosting machine / J. H. Friedman // Annals of statistics. — 2001. — C. 1189—1232.

74. Scikit-learn: Machine Learning in Python / F. Pedregosa [h gp.] // Journal of Machine Learning Research. — 2011. — T. 12. — C. 2825—2830.

75. Bayer I. fastFM: A Library for Factorization Machines /1. Bayer // Journal of Machine Learning Research. — 2016.

76. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems / Martin Abadi [h gp.]. —2015. —URL: https://www.tensorflow.org/; Software available from tensorflow.org.

77. Khoromskij B. N. DMRG+QTT approach to computation of the ground state for the molecular Schrodinger operator: Preprint / B. N. Khoromskij, I. V. Oseledets ; MPI MIS. — Leipzig, 2010. — № 69.