Объяснение одного из самых новых методов машинного обучения прямо сейчас

Вы бы поверили мне, если бы я сказал, что существует единое решение таких разных проблем, как декодирование мозга в нейробиологии, реконструкция формы в компьютерной графике, передача цвета в компьютерном зрении и автоматический перевод в обработке нейронного языка? А если бы я добавил к этому списку трансферное обучение, регистрацию изображений и спектральное разделение музыкальных данных и тот факт, что решение, о котором я говорю, не имеет ничего общего с глубоким обучением? Что ж, если вы не смогли угадать правильный ответ, продолжайте читать, поскольку эта статья посвящена оптимальному переносу (ОТ): математической теории, восходящей к концу 18 века, которая недавно процветала как в чистой математике (2 медали Филдса в последние 12 лет!) и машинное обучение стали одной из самых актуальных тем для изучения прямо сейчас. Присоединяйтесь ко мне в этом путешествии по прекрасной истории ОТ, охватывающей последние три столетия, и узнайте, почему она стала такой важной частью сегодняшнего машинного обучения.

Начало

Как и многие другие хорошие вещи, все началось во Франции в конце 18 века при Людовике XVI, примерно за десять лет до Французской революции 1789 года. В тот солнечный день Людовик XVI выглядел обеспокоенным, беседуя с одним из самых выдающихся ученых. его страны, Гаспара Монжа, вопрос первостепенной важности.

«Видишь ли, Гаспар, - сказал Людовик XVI, - у нас есть три вида сертификации сыра во Франции: сыр ферме, полностью приготовленный, не покидая фермы, кустарный сыр, изготовленный из молока с близлежащих ферм ремесленниками, и сыр с молоком, сделанный из молока с фермы. тот же регион на заводах. Проблема в том, что ремесленники, производящие кустарный сыр, обычно тратят слишком много времени на поездку и сбор молока на фермах, которые находятся слишком далеко. Я хотел бы, чтобы вы, Гаспар, помогли нам разобраться с этой проблемой, выяснив, какая ферма отдает все свое молоко какому ремесленнику, чтобы сыра было в изобилии, а жизнь была красивой.

"Ой!" воскликнул Гаспар несколько взволнованно, "это как проблема с рудой и шахтами, над которой я недавно работал с моими коллегами-металлургами".

«Как бы то ни было, Гаспар», - ответил его величество. «Пока сыр на столе и люди счастливы».

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

Несмотря на ее упрощенный вид, математикам потребовалось почти двести лет, чтобы полностью охарактеризовать эту проблему (примерно на 140 лет меньше, чем знаменитая Великая теорема Ферма), пока Ян Бренье в 1991 году не показал, что она допускает решение в общем (непрерывном) случае для некоторых общие расстояния, используемые в науке. Но перед этим произошло следующее важное событие.

Неожиданные преимущества коммунизма

Бухгалтер Нина, чья работа в конце 1930-х годов была для нас тем же, чем поиск Google сегодня, смотрела на полки Ленинградской государственной библиотеки, пытаясь найти книгу Шарля Бодлера «Les Fleurs du mal». Последнего попросил Леонид, любитель поэзии лет двадцати с небольшим, теперь нетерпеливо ожидающий у стойки.

«У нас нет Шарля Бодлера, товарищ Канторович», - сказала она, возвращаясь на работу. «Но вот хорошая статья о металлургии, которая может вас заинтересовать, как изобретателя линейного программирования и почетного советского гражданина».

Она упомянула прекрасную статью Гаспара Монжа «Mémoire sur la théorie des déblais et des remblais», которую Леонид Канторович воспринял несколько неутешительно и, читая ее дома, придумал, как ее можно улучшить.

«Проблема с проблемой Монжа в том, что эти монархисты не делятся вещами, а мы, советские люди, делимся всем друг с другом», - сказал себе Леонид. «Возьмем, к примеру, молоко. Почему мы должны заботиться о том, чтобы не позволять фермам делить производство между всеми заводами? »

Это привело его к идее, которая позже будет названа проблемой Монжа-Канторовича, где, в отличие от поиска функции T, присваивающей каждую ферму одному ремесленнику, мы теперь хотим найти (вероятностная) функция Г, позволяющая разделить производство ферм между всеми ремесленниками.

Эту проблему, в отличие от проблемы Монжа, можно показать, чтобы: 1) всегда находить решение при некоторых мягких предположениях относительно используемого расстояния и 2) зарабатывать Нобелевскую премию, медали Филдса и другие выдающиеся награды для десятка различных исследователей, работающих над ней в последние 60 лет. Наконец, это намекает на то, почему у всех сыров в постсоветских странах одинаковый вкус, несмотря на то, что они продаются под разными названиями, и это, мой друг, является большой современной загадкой, чтобы пролить свет на это (поверьте мне, я родился в Украине).

Низкоуровневый просмотр

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

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

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

Возвращаясь к моему примеру с фермами и ремесленниками, теперь я могу определить два дискретных распределения по ним с вероятностями, заданными производительностью каждой фермы (3 коровы из 7 дают мне вероятность 3/7) и спросом каждого ремесленника. Затем я получу две гистограммы, и рассмотренные ранее расстояния станут затратами на преобразование точек из моего первого распределения в точки из второго.

«Но почему это так важно?» вы можете спросить.

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

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

«Но мы обычно используем расстояния для сравнения объектов!» вы можете с полным правом заметить.

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

Более того, поскольку задача OT находит наиболее эффективный способ преобразования одного распределения в другое, вы можете использовать его решение для плавной интерполяции между ними и получения промежуточных преобразований на этом пути. Чтобы проиллюстрировать это, давайте возьмем образ Гаспара Монжа и Леонида Канторовича и решим проблему ОТ между ними. Результат на рисунке выше показывает геодезический путь между двумя изображениями, заданный наиболее эффективным способом (кратчайшим путем) постепенного преобразования одного изображения в другое с геометрией (или попарными расстояниями между пикселями в нашем случае), заданными как функция стоимости, которую вы используете. Довольно круто, а ?! Давайте, наконец, вернемся в современность и посмотрим, что именно это означает для машинного обучения.

Трейлер приложений

Ниже я представлю только некоторые приложения ОТ в компьютерном зрении и обработке нейронных языков с кодом, используемым для получения результатов, подробно описанных в Практическом руководстве по инструментарию Python Optimal Transport: Часть 2 ». Также ознакомьтесь с введением в набор инструментов Python Optimal Transport в статье Практическое руководство по инструментарию Python Optimal Transport: Часть 1 ».

Цветопередача. В этом приложении у нас есть два изображения: одно с голубым небом над океаном и одно с закатом. Наша цель - перенести цветовую гамму первого изображения на второе так, чтобы цвета изображения заката были идентичны цветам дневного изображения. Как и раньше, мы рассматриваем оба изображения как распределения вероятностей по пикселям, заданным трехмерными векторами в кубе RGB. Мы выбираем 1000 пикселей из каждого изображения и выравниваем их с помощью OT. Окончательный результат представлен на среднем изображении слева и показывает очень реалистичное изображение заката с дневными цветами.

Редактирование изображений. Цель этой задачи - отредактировать изображение, заменив его часть фрагментом другого изображения. Например, на изображении слева вы можете увидеть мое лицо, лицо Моны Лизы и результат бесшовной копии моего лица на ее лице. Оптимальный перенос здесь применяется к цветовым градиентам двух изображений, а затем решается уравнение Пуассона для расчета отредактированного изображения. Более интересные примеры этого можно найти в этой статье.

Автоматический перевод. Давайте теперь обратим наше внимание на что-то еще, кроме изображений, и рассмотрим корпуса текста. Наша цель - найти соответствие слов и фраз на двух разных языках. В качестве примера возьмем следующую пару: учитывая английское предложение «кот сидит на циновке» и его французский перевод «le chat est assis sur le tapis» ', мы хотели бы найти соответствие, которое обеспечивает соответствия «кот» - «чат», «сидит» - «assis »и« mat »-« tapis ». Вы видите, куда я направляюсь с этим, не так ли ?! Я буду определять распределение по каждому предложению и рассматривать каждое слово как одну точку. Затем я буду использовать расстояния между их вложениями, чтобы сопоставить два распределения с OT. Результат этого сопоставления можно увидеть слева.

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

Afternote

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