КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер проекта 18-71-10108
НазваниеОптимальный транспорт: численные методы и приложения к анализу данных
Руководитель Двуреченский Павел Евгеньевич, Кандидат физико-математических наук
Организация финансирования, регион Федеральное государственное бюджетное учреждение науки Институт проблем передачи информации им. А.А. Харкевича Российской академии наук , г Москва
Конкурс №30 - Конкурс 2018 года по мероприятию «Проведение исследований научными группами под руководством молодых ученых» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-203 - Теория оптимизации и исследование операций
Ключевые слова Оптимальный транспорт, выпуклая оптимизация, ускоренный градиентный спуск, прямо-двойственный метод, распределенные алгоритмы, центральная предельная теорема, вероятностная мера, расстояние Монжа-Канторовича-Васерштейна, пространство Васерштейна, барицентр Васерштейна, несбалансированный оптимальный транспорт, метод балансировки
Код ГРНТИ27.47.19
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
В последние годы наблюдается увеличение роли концепции оптимального транспорта в машинном обучении (в том числе глубинном обучении), анализе изображений, компьютерной графике и других высокотехнологичных методах анализа данных. На основе оптимизационной задачи поиска оптимального транспорта, впервые рассмотренной Г. Монжем и обобщенной Л.В. Канторовичем, вводится понятие транспортного расстояния между вероятностными мерами, называемое расстоянием Монжа-Канторовича-Васерштейна (МКВ-расстояние). Это расстояние оказалось естественным для сложных объектов, рассматриваемых в анализе данных.
Последнее основано на том, что это расстояние позволяет на основе расстояния в некотором базовом метрическом пространстве, определить расстояние между вероятностными мерами, определенными на этом базовом пространстве. Это позволяет анализировать сложные объекты, которые могут быть смоделированы как вероятностные меры, например, изображения или поток видео, который является последовательностью изображений. Одной из задач, в которых этот подход хорошо себя зарекомендовал, является задача поиска изображений, похожих на заданное пользователем изображение (image retrieval). Известно, что можно так определить расстояние в цветовом пространстве, что это расстояние будет соответствовать восприятию близости цветов человеком. На основе этого расстояния можно определить МКВ-расстояние в пространстве цветовых гистограмм изображений. Такая гистограмма задается набором интервалов цветов и представляет собой для каждого цветового интервала долю пикселей изображения, цвет которых принадлежит этому интервалу. Причем эти гистограммы являются вероятностными мерами над цветовым пространством и расстояние между двумя изображениями вычисляется как МКВ-расстояние между их цветовыми гистограммами. Другими примерами задач, в которых подход на основе оптимального транспорта дает хорошие результаты, являются классификация изображений с помощью МКВ-расстояния, определенного на основе евклидова расстояния между пикселями изображений; анализ текстов с помощью МКВ-расстояния между текстами, определенного на основе расстояния между словами; и многие другие.
Тем не менее, успех концепции оптимального транспорта в приложениях носит по большей части эвристический и инженерный характер. Отсутствие строгого математико-статистического обоснования и понимания статистических свойств пространств мер ограничивают расширение области применимости этого подхода в приложениях. Так, стандартный подход в машинном обучении рассматривает данные как случайные реализации из некоторого вероятностного распределения. Если анализируются сложные данные, такие как изображения, то каждый элемент данных сам по себе является вероятностной мерой. Следовательно, важно понять, как работать со случайными вероятностными мерами, распространить на этот случай центральную предельную теорему и другие классические результаты. Отсутствие полностью теоретически обоснованных численных методов ограничивает применимость этого подхода как к новым прикладным задачам, так и к известным прикладным задачам с большим объемом данных или с большей размерностью анализируемых объектов. Эра больших данных предъявляет серьезные требования к вычислительной эффективности предлагаемых процедур и алгоритмов. Несмотря на свою эффективность, современные численные методы не позволяют за разумное время вычислить МКВ-расстояние между двумя трехмерными изображениями мозга с высоким разрешением. В то же время, недостаточно просто предложить эвристический метод для вычисления транспортного расстояния между объектами высокой размерности. Чтобы иметь гарантии адекватности времени работы алгоритма, необходимо получить теоретические оценки его сложности.
Как итог, основная проблема, рассматриваемая в проекте, состоит в отсутствии в достаточной степени теоретически обоснованных численных методов для вычисления транспортного расстояния между объектами высокой размерности и недостаточная теоретическая обоснованность статистических приложений концепции оптимального транспорта. Решение этих проблем позволит разработать практические, эффективные и понятные алгоритмы для более широкого диапазона приложений и масштабов задач.
Задача предлагаемого проекта состоит в продвижении в решении описанной выше проблемы, а именно в разработке новых численных методов и оценке их сложности, а также в получении новых теоретических результатов о применимости концепции оптимального транспорта и применении этих результатов в конкретных приложениях. В соответствии с этой большой задачей, мы делим проект на два подпроекта с конкретными наборами задач. Первый проект направлен на разработку численных методов и их теоретическое обоснование, второй проект направлен на разработку статистических инструментов для работы с данными, являющимися элементами пространства Васерштейна вероятностных мер, то есть пространства мер, наделенного МКВ-расстоянием. Концепция оптимального транспорта в применении к задачам машинного обучения является хорошим примером синергетического эффекта от взаимодействия математической статистики и оптимизации. Поэтому соединение оптимизационного и статистического проекта в один видится сильной стороной предлагаемого проекта. Часть коллектива, имеющая опыт в оптимизации будет влиять на другую часть, специализирующуюся в статистике, и наоборот.
Подпроект 1. Численные методы для транспортных расстояний между объектами высокой размерности.
В некоторых приложениях, таких как классификация изображений рукописных цифр, анализируемые объекты моделируются как вероятностные меры. МКВ-расстояние между двумя вероятностными мерами определяется как минимальное значение целевой функции в специальной задаче оптимизации, которая является задачей линейного программирования. Если объекты имеют большую размерность (например, размерность изображения - это число пикселей в нем), то стандартные методы, например, симплекс метод или методы внутренней точки, не могут быть применены для решения этой задачи. Причина в том, что сложность этих алгоритмов O(n^3), где n - размерность пространства объектов. Самый эффективный на сегодняшний день подход в этом случае состоит в энтропийной регуляризации задачи линейного программирования и применении метода Синхорна (в русскоязычной литературе известен как метод балансировки Брегмана-Шацкого-Шелейховского) для решения этой задачи. Недавно было показано, что сложность этого алгоритма n^2/e^3, где e - желаемая точность аппроксимации расстояния. Обратная кубическая зависимость от точности не позволяет гарантированно получить хорошую точность за разумное время. В связи с этим обстоятельством в проекте планируется а) улучшить оценку сложности метода Синхорна и б) разработать альтернативный подход на основе ускоренного градиентного метода.
На практике часто возникает необходимости сравнения двух мер разной суммарной массы. Например, эти меры могут быть изображениями разной яркости или одна из этих мер является изображением мозга с опухолью, а вторая изображением мозга без опухоли. Возникает необходимость определения расстояния между радоновскими мерами, а не вероятностными мерами. В таких ситуациях транспортное расстояние определяется на основе задачи поиска несбалансированного оптимального транспорта, которая является выпуклой задачей нелинейного программирования. Энтропийная регуляризация и обобщения метода Синхорна также могут быть применены для решения этой задачи, но почти ничего не известно об оценках сложности этих алгоритмов для этой задачи. Поэтому в проекте планируется обобщить оценки метода Синхорна и подход на основе ускоренного градиентного метода и получить новые алгоритмы и оценки сложности для задачи поиска несбалансированного оптимального транспорта и транспортного расстояния на ее основе.
При работе с набором случайных объектов естественным является определение его типичного представителя или “среднего” объекта. Если эти объекты являются нетривиальными, например изображениями, то определение понятия среднего тоже становится нетривиальным. Один из подходов, зарекомендовавший себя в машинном обучении, состоит в рассмотрении этих объектов как мер и определении на основе транспортного расстояния среднего объекта как такого объекта, сумма транспортных расстояний от которого до всех объектов из набора минимальна. Этот объект называется барицентром, порожденным транспортным расстоянием. В частном случае МКВ-расстояния его называют барицентром Васерштейна. Вычисление барицентра является более сложной задачей, чем вычисление транспортного расстояния, так как включает в себя многократное вычисление транспортного расстояния. В этой ситуации энтропийная регуляризация также используется на практике, но вопрос о теоретических оценках сложности остается открытым. Кроме того, число объектов в наборе может быть настолько большим, что они не могут быть обработаны в оперативной памяти одного компьютера и хранятся в распределенной среде. Поэтому необходима разработка распределенных алгоритмов поиска барицентра. На основе вышесказанного в проекте планируется а) обобщить развиваемые алгоритмы и их оценки сложности на задачу вычисления барицентра, порожденного общим транспортным расстоянием и б) предложить распределенный алгоритм поиска барицентра Васерштейна и оценку сложности этого алгоритма.
Подпроект 2. Статистические инструменты для работы с данными из пространств Васерштейна.
Эффективное использование и распространение существующих методов статистического анализа на пространства с нетривиальной геометрией требуют дополнительного исследования свойств последних. Например, выбор расстояния определяет такие кумулятивные характеристики случайного множества, принадлежащих многообразию, как среднее, вариабельность и т.д. Особый интерес представляют пространства Васерштейна, которые в некотором смысле учитывают внутреннюю геометрию наблюдаемых данных. В особенности следует отметить не регуляризованное и регуляризованное 2-расстояния Васерштейна, последнее, в частности, сравнительно легко вычисляется, что с практической точки зрения является неоспоримым плюсом. Помимо выбора расстояния, среди ключевых аспектов в ратификации методов анализа данных, использующих оптимальный транспорт, следует выделить понимание статистических свойств таких кумулятивных характеристик, как барицентр Васерштейна, оптимальные транспортные планы или расстояние Монжа-Канторовича, как функционал случайной меры. Эта задача возникает при разработке методов анализа случайных множеств мер. Рассмотрим меры, как независимые одинаково распределенные случайные величины. Первый вопрос касается сходимости эмпирического распределения мер к своему не случайному аналогу, например в смысле расстояния Монжа-Канторовича над мерами, определенными над пространством мер. Еще один важный вопрос - состоятельность эмпирического барицентра (регуляризованного или не регуляризованного), т.е. его сходимость к популяционному аналогу и скорость это сходимости. На вышеперечисленных свойствах также базируются многие другие статистические конструкции, например доверительные множества вокруг барицентров или методология непараметрического тестирования для двух выборок.
Помимо понимания статистических свойств, приведенных выше, новые методы анализа данных, использующие оптимальный транспорт, требуют разработки специальных инструментов. Мы рассматриваем два направления исследований. Первое связано с задачей определения гауссовских процессов над пространствами Монжа-Канторовича. Методология распространяет классические ядерные методы на множества мер. Вторая задача, возникшая в контексте semi-supervised learning, в англоязычной литературе называется domain adaptation problem. Она формулируется следующим образом. Дан набор случайных размеченных выборок, сгенерированных согласно некоторым распределениям; также имеется неразмеченная выборка, сгенерированная согласно (искаженному) деформированному распределению; соответственно, требуется присвоить метки классов (тех же, что и в размеченных выборках) элементам искаженной выборки с минимальной погрешностью. Задача особенно актуальна в свете того, что на сегодняшний день продуцируется большое количество не размеченных данных, в то время как построение разметки на них является дорогостоящей процедурой. Планируется предложить новую модель для этой задачи, которая будет основана на идеях оптимального транспорта, а также численные методы ее решения.
ОТЧЁТНЫЕ МАТЕРИАЛЫ