Наукові публікації університету

Суперпозиция метода балансировки и универсального градиентного метода для поиска энтропийно-регуляризованного барицентра Вассерштейна и равновесий в многостадийных моделях транспортных потоков

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

В основном мы исходили из цикла работ M. Cuturi с соавторами. Общая идея этих работ – найти барицентр вероятностных мер согласно энтропийно-регуляризованному расстоянию Вассерштейна. Такое (регуляризованное) расстояние можно заметно эффективнее посчитать, чем исходное расстояние Вассерштейна. В одной из работ отмеченного цикла [8] содержалась идея сочетания метода Синхорна балансировки) для решения внутренней задачи (расчета соответствующих регуляризованных расстояний и их субградиентов) и быстрого градиентного метода для решения внешней задачи (поиск барицентра). К сожалению, в описанном авторами виде метод оказался не пригодным для использования на практике (не было также никаких теоретических гарантий его сходимости). В [1] показано, как можно доработать данный метод (в частности, доказана сходимость предложенной модификации). Однако мы были сконцентрированы на другом приложении (к поиску равновесий в многостадийных транспортных моделях).

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

ID: 182625
Кількість показів: 28
дата змінення: 14.11.2016 20:33:42
Ким змінено (ім'я): (cyb13) Дмитро Терлецький
Вид роботи:  Наукова публікація
Тип роботи:  Наукова стаття
Кількість сторінок:  20
Рік видання:  2016
Звітний рік:  2016
Видання:  Труды МФТИ
Том:  8
Випуск, частина:  3
Номери сторінок:  5–24
Галузь науки:  Математика
Автори,співробітники Університету:   /  /  / Стецюк Петро Іванович / 
Кафедра / Відділ:  Інформаційних систем
№ теми:  16КФ015-01
Посилання на статтю (посилання на рецензію в журналі (для монографій):  https://mipt.ru/upload/medialibrary/6f6/5_24.pdf
Ключові слова:  седловая задача, энтропия, метод балансировки, метод Синхорна, универсальный метод, неточный оракул, задача Монжа–Канторовича, рас- стояние Вассерштейна, барицентр Вассерштейна.
Опубліковано за рішенням Вченої ради:  ні
Інститут/Факультет:  Факультет комп'ютерних наук та кібернетики

Повернення до списку

Вгору