КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ

---

Номер 18-71-10108

НазваниеОптимальный транспорт: численные методы и приложения к анализу данных

РуководительДвуреченский Павел Евгеньевич, Кандидат физико-математических наук

Организация финансирования, регион Федеральное государственное бюджетное учреждение науки Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, г Москва

Период выполнения при поддержке РНФ

07.2018 - 06.2021

, продлен на 07.2021 - 06.2023. Карточка проекта продления (ссылка)

Конкурс№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. Она формулируется следующим образом. Дан набор случайных размеченных выборок, сгенерированных согласно некоторым распределениям; также имеется неразмеченная выборка, сгенерированная согласно (искаженному) деформированному распределению; соответственно, требуется присвоить метки классов (тех же, что и в размеченных выборках) элементам искаженной выборки с минимальной погрешностью. Задача особенно актуальна в свете того, что на сегодняшний день продуцируется большое количество не размеченных данных, в то время как построение разметки на них является дорогостоящей процедурой. Планируется предложить новую модель для этой задачи, которая будет основана на идеях оптимального транспорта, а также численные методы ее решения.

Ожидаемые результаты
Мы приводим ожидаемые результаты проекта в соответствии с содержанием подпроектов. 1. Численные методы для транспортных расстояний между объектами высокой размерности Для метода Синхорна планируется получить оценки сложности вычисления МКВ-расстояния лучше, чем имеющиеся в литературе. Планируется усилить этот результат об оценках сложности с помощью разрабатываемого в проекте альтернативного подхода для вычисления МКВ-расстояния на основе ускоренного градиентного метода. Это позволит применять концепцию оптимального транспорта в прикладных задачах анализа данных большего объема и размерности, чем сейчас. К тому же, подход на основе ускоренного градиентного метода будет более гибким и позволит применять к задаче поиска оптимального транспорта другие регуляризации, например, регуляризацию квадратом евклидовой нормы. Такая регуляризация является предпочтительной, так как порождает разреженную аппроксимацию транспортного плана, в отличие от энтропийной регуляризации. Разреженная аппроксимация транспортного плана важна в таких приложениях как изменение цветовой гаммы изображения (image color transfer), в котором требуется изменить цветовую гамму изображения на основе цветовой гаммы другого изображения, или обобщение алгоритма машинного обучения на новую выборку (domain adaptation), в котором целью является получение модели для новых данных на основе имеющейся модели похожих данных, но сгенерированных из другого распределения. Также на основе ускоренного градиентного метода с полной релаксацией на каждой итерации планируется разработать алгоритм для вычисления МКВ-расстояния, который будет иметь те же оценки скорости сходимости, но будет быстрее работать на практике. Планируется обобщить перечисленные алгоритмы и их оценки сложности на задачи вычисления транспортных расстояний, основанных на задаче поиска несбалансированного оптимального транспорта. Для таких задач оценки сложности для существующих алгоритмов на основе метода Синхорна не известны. Такие методы создадут теоретически обоснованную вычислительную базу для сравнения сложных объектов с разной массой, например, изображений мозга с опухолью и без нее. Кроме того, предлагаемые в проекте алгоритмы и их оценки сложности планируется обобщить на задачи вычисления барицентра, порожденного общим транспортным расстоянием. Это создаст теоретически обоснованную вычислительную базу для центральной предельной теоремы в пространстве Васерштейна и для определения понятия среднего по выборке среди объектов сложной природы, таких как изображения. Планируется также разработать распределенный алгоритм для вычисления барицентра Васерштейна и оценить сложность этого алгоритма. Это позволит вычислять “средний” объект в случае когда объем данных настолько велик, что данные приходится распределять по нескольким компьютерам. В целом результатами этого подпроекта будут новые теоретически обоснованные методы для вычисления более широкого класса транспортных расстояний и барицентров. Также отметим, что задача оценки матрицы корреспонденций трафика, возникающая в транспортном моделировании, является энтропийно-регуляризованной задачей поиска оптимального транспорта. Поэтому предлагаемые в проекте алгоритмы и их оценки сложности могут быть применены в транспортном моделировании при создании систем интеллектуального управления транспортной сетью города и систем городского транспортного планирования. 2. Статистические инструменты для работы с данными из пространств Васерштейна Во второй части проекта планируется исследовать пространство мер, снабженное регуляризованным МКВ-расстоянием, а именно: получить критерии сходимости для регуляризованного транспортного расстояния, изучить квази-метрические и топологические свойства данного пространства. Также будут изучены свойства (регуляризованных) барицентров, такие как единственность и устойчивость относительно малых вариаций параметра регуляризации и распределения. Кроме того, мы исследуем свойства барицентров и их репрезентативность, т.е. в какой степени они отражают свойства рассматриваемых мер, например, выпуклость носителя или лог-вогнутость плотности распределения. Далее, будут получены результаты о концентрации эмпирических барицентров Васерштейна, в частности, центральная предельная теорема (в касательном пространстве к пространству Васерштейна либо в пространстве параметров для конечномерных параметрических семейств). Теория оптимального транспорта является мощным инструментом для развития статистического анализа сложных данных, которые могут быть представлены в виде случайных мер. В данном проекте мы сконцентрируемся на построении доверительных множеств для барицентров Васерштейна и обобщении непараметрических статистических критериев, основанных на линейной упорядоченности данных (например, ранговые критерии), на многомерный случай. Разработанные методы планируется применить к задаче обнаружения структурных изменений в данных. Другое направление исследований, представленное в проекте, касается построения гауссовских процессов, индексированных мерами из пространства Васерштейна. Потребность в таких объектах возникает, например, в численных экспериментах, когда априорная информация о процессе допускает множество возможных значений и выражается с помощью априорного распределения. В этом случае, наблюдая случайные реализации для такого распределения в некоторых точках, мы хотим предсказывать значение процесса в других точках. Комбинация теории оптимального транспорта и методологии обучения с частичным привлечением учителя (semi-supervised learning) ведет к развитию новых методов классификации. Мы планируем предложить новый подход к решению задачи, называемой в англоязычной литературе domain adaptation problem. Задача заключается в следующем: имея размеченную тренировочную выборку, требуется разметить новую выборку, которая сгенерирована из распределения, близкого к распределению исходной выборки. Планируется также получить теоретические гарантии качества для данного метода при определенных условиях на модель генерации случайных выборок.

---

 

ОТЧЁТНЫЕ МАТЕРИАЛЫ

---