Студент ПМИ нашел оптимальный алгоритм решения задачи поиска барицентра Вассерштейна
В конце августа в центре "Сириус" прошла школа "Управление, информация и оптимизация". На ней студент 4 курса ПМИ Даниил Тяпкин вывел оптимальный алгоритм решения задачи поиска барицентра Вассерштейна, которой занимался с начала 2020 года. Даниил рассказал об истории задачи и ее возможном практическом применении.
О себе и о математике
Сейчас я учусь на 4 курсе программы "Прикладная математика и информатика", специализация "Теоретическая информатика". Еще недавно я состоял в лаборатории алгебраической топологии и приложений, занимался топологическим анализом данных, но сейчас мои интересы сместились в сторону теории вероятностей. Меня интересуют случайные графы, концентрация меры и стохастическая оптимизация.
Учиться на ФКН для меня достаточно напряжно, так как я добрал дополнительные к стандартной программе ФКН курсы: в обучении мне все очень нравится кроме того, что у нас не очень много именно математических предметов по выбору. Однако на моей специализации это компенсируется возможностью добирать различные курсы, поэтому я не сильно жалуюсь.
История решения
Впервые про барицентры Вассерштейна я услышал зимой на семинаре вышкинской G2PS-group под руководством Кентана Пари. Потом мне снова встретилась эта задача во время работы над проектом по непрерывной оптимизации на курсе Александра Владимировича Гасникова. Тогда я попросил у него задание, связанное с оптимальным транспортом, и он предложил мне подумать над одной из вариаций задачи про барицентры и показал подход, который хотелось бы использовать. В мае — июне я всерьез занимался этой задачей и получил нетривиальные результаты, которые мы попытались подать на конференцию NeurIPS, но спешка на последних этапах сильно ухудшила впечатление от работы, и пройти на неё не получилось.
В следующий раз я столкнулся с этой задачей уже в "Сириусе". Я хотел выступить на постерной сессии с предыдущим результатом, но Александр Владимирович предложил попробовать его доработать. Во время лекции он рассказал про текущий подход к решению от Дарины Двинских, аспирантки института Вейерштрасса, и обратил внимание на то, что могло бы быть улучшено. Той же ночью я сделал это улучшение и оно дало искомый оптимальный алгоритм.
История самой задачи
Поиск барицентра Вассерштейна — это не самая известная задача, но у нее достаточно интересная история. В XVIII веке французский математик Гаспар Монж впервые начал решать задачу оптимальной транспортировки. Насколько я знаю, он задавался вопросом как передвинуть ядра в яму, затратив наименьшие усилия, но в том виде, в каком он сформулировал задачу, она оказалась слишком сложной. В XX веке наш соотечественник Леонид Витальевич Канторович привел эту задачу к более современному виду, после чего ее получилось решить.
С помощью теории оптимального транспорта мы можем получить, например, расстояние между картинками. Мы хотим "передвинуть" интенсивность каждого пикселя в какое-либо другое место, при этом если мы будем перемещать их слишком далеко, то будем платить бОльший штраф, чем если осуществим меньшее перемещение или оставим пиксель на месте.
Помимо расчета расстояния, мы хотим уметь считать некоторый взвешенный центр масс (барицентр) множества картинок: мы как бы находим некоторую среднюю картинку. Например, можно много раз написать на листе бумаги цифру "3", и если посчитать их среднюю картинку, то можно получить какую-то цифру "3", обобщающую все предыдущие.
Способ решения задачи появился почти сразу после формулировки Канторовича, но вопрос оптимальности решения все еще был актуален — им я и занимался. В моем конкретном случае рассматривался пример, когда мы хотим решать задачу не очень точно, но для большого количества картинок, а именно для размера 1000 на 1000; предыдущее решение этой задачи давало ответ только для десяти картинок.
А где применять?
Эту задачу можно использовать в нейроисследованиях. С помощью МРТ можно сделать запись активности головного мозга, на которой врач будет искать аномалии. Если запись длинная, то их физически сложно заметить, и тогда на помощь приходит алгоритм. Чтобы отслеживать изменения, можно сравнивать соседние кадры, но нам могут мешать шумы и то, что изменения происходят не за один кадр. Поэтому хочется как-то усреднить серию снимков, а затем сравнивать уже эти "барицентры" и их отличия между собой.
Сложно сказать, что ждет это решение дальше. Сейчас мы с Дариной Двинских работаем над препринтом статьи, а потом — посмотрим.