Оптимальный транспорт

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Статья написана с использованием LLM DeepSeek и проверена участником К.А.Савицкий 19:51, 29 июль 2026 (UTC)

Оптимальный транспорт (ОТ; optimal transport) — математическая дисциплина, изучающая способы перемещения вероятностных масс между распределениями с наименьшими затратами. Возникнув из задачи о перемещении грунта, сформулированной Гаспаром Монжем в 1781 году, теория получила строгое обоснование в работах Леонида Канторовича и сегодня стала ключевым инструментом в машинном обучении, позволяя сравнивать и преобразовывать распределения данных с учётом геометрии исходного пространства.

Содержание

1 Введение
2 История развития
3 Постановки задач
4 Вычислительные методы
5 Связь с машинным обучением
6 Преимущества и ограничения
- 6.1 Преимущества
- 6.2 Ограничения
7 Современные применения в науке и индустрии
8 См. также
9 Примечания

Введение

Интуитивно оптимальный транспорт можно представить как задачу о перемещении кучи песка в яму с минимальными усилиями. Пусть даны две «кучи» - вероятностные меры $\mu$ и $\nu$ , определённые на метрических пространствах $\mathcal{X}$ и $\mathcal{Y}$ . Задана функция затрат $c(x,y)$ , оценивающая стоимость переноса единицы массы из точки $x \in \mathcal{X}$ в точку $y \in \mathcal{Y}$ ; обычно $c(x,y) = \|x - y\|^p$ для некоторого $p \ge 1$ . Требуется найти транспортный план, доставляющий минимум полной стоимости. В отличие от поточечных расхождений (например, дивергенции Кульбака-Лейблера), ОТ учитывает расстояние между точками исходного пространства, что делает его особенно полезным для данных, лежащих в геометрически структурированных пространствах признаков - изображений, текстов, графов.

История развития

1781 г. - Гаспар Монж формулирует задачу о де- и ремблировании (перемещении земли) и предлагает геометрическое решение для одномерного случая^[1].
1942 г. - Леонид Канторович ослабляет постановку Монжа, вводя понятие транспортного плана как совместного распределения, и сводит задачу к линейному программированию^[1]. Эта работа легла в основу транспортной задачи и принесла учёному Нобелевскую премию по экономике в 1975 году.
1980–2000-е гг. - Глубокие математические результаты: связь с уравнением Монжа-Ампера (Бренье, 1991), метрическая структура пространства Вассерштейна (Отто, 2001), исчерпывающая монография Седрика Виллани^[1].
2013 г. - Марко Кутури предлагает энтропийную регуляризацию и алгоритм Синкхорна, делая вычисление ОТ практически масштабируемым для глубокого обучения^[1].
2017 г. - Аржовский и др. вводят Wasserstein GAN (WGAN), напрямую использующий метрику Вассерштейна-1 как функцию потерь, что значительно повышает стабильность обучения генеративно-состязательных сетей^[1].

Постановки задач

Задача Монжа

Для вероятностных мер $\mu$ на $\mathcal{X}$ и $\nu$ на $\mathcal{Y}$ задача Монжа состоит в поиске измеримого отображения $T: \mathcal{X} \to \mathcal{Y}$ , минимизирующего $\int_{\mathcal{X}} c(x, T(x)) \, d\mu(x)$ при условии, что мера $\mu$ , перенесённая отображением $T$ , совпадает с $\nu$ (сохранение массы): $T_\#\mu = \nu$ , т.е. $\nu(B) = \mu(T^{-1}(B))$ для любого измеримого множества $B \subset \mathcal{Y}$ . Основные ограничения: решение не всегда существует (особенно если $\mu$ имеет атомы, а $\nu$ - нет), а оптимизация по нелинейному отображению крайне сложна.

Задача Канторовича

Канторович предложил релаксацию: вместо детерминированного переноса рассматривается транспортный план $\pi$ - вероятностная мера на произведении $\mathcal{X} \times \mathcal{Y}$ , маргиналы которой равны $\mu$ и $\nu$ . Множество таких планов обозначается $\Pi(\mu, \nu)$ . Задача Канторовича записывается как $\inf_{\pi \in \Pi(\mu, \nu)} \int_{\mathcal{X}\times\mathcal{Y}} c(x,y) \, d\pi(x,y).$ Это линейная задача с выпуклым множеством ограничений, всегда имеющая решение при слабых условиях на $c$ . Оптимальный план $\pi^*$ описывает вероятностное перемещение масс: доля массы из окрестности $x$ , направляемая в окрестность $y$ .

Двойственная задача

Двойственная формулировка Канторовича играет ключевую роль в приложениях: $\sup_{\varphi \in L^1(\mu), \psi \in L^1(\nu)} \left\{ \int \varphi \, d\mu + \int \psi \, d\nu \;:\; \varphi(x) + \psi(y) \le c(x,y) \right\}.$ Функции $\varphi$ и $\psi$ называются потенциалами Канторовича. Для стоимости $c(x,y)=\|x-y\|$ двойственная задача сводится к супремуму по 1-липшицевым функциям: $W_1(\mu, \nu) = \sup_{f:\ \|f\|_{\text{Lip}} \le 1} \left( \int f \, d\mu - \int f \, d\nu \right),$ известному как формула Канторовича-Рубинштейна, и используется в WGAN.

Метрика Вассерштейна

Для $p \ge 1$ расстояние Вассерштейна порядка $p$ между мерами $\mu$ и $\nu$ определяется как $W_p(\mu, \nu) = \left( \inf_{\pi \in \Pi(\mu, \nu)} \int \|x-y\|^p \, d\pi(x,y) \right)^{1/p}.$ При $p=1$ оно известно как расстояние землекопа. $W_p$ является метрикой на пространстве мер с конечным $p$ -м моментом, метризует слабую сходимость и учитывает геометрию пространства: расстояние между двумя дельта-мерами равно обычному расстоянию между их носителями. Это выгодно отличает его от KL- или TV-расхождений.

Вычислительные методы

Дискретный случай и линейное программирование

На практике распределения заданы эмпирическими выборками: $\hat{\mu} = \sum_{i=1}^n a_i \delta_{x_i}$ , $\hat{\nu} = \sum_{j=1}^m b_j \delta_{y_j}$ , где $a \in \mathbb{R}_{+}^n, b \in \mathbb{R}_{+}^m$ - векторы весов, $\sum_i a_i = \sum_j b_j = 1$ . Транспортный план сводится к матрице $P \in \mathbb{R}_{+}^{n \times m}$ , а ограничения - к $P \mathbf{1}_m = a,\ P^\top \mathbf{1}_n = b$ . Задача Канторовича принимает вид линейной программы: $\min_{P \in U(a,b)} \langle C, P \rangle,$ где $C_{ij} = c(x_i, y_j)$ . При $n = m$ точное решение с помощью симплекс-метода или венгерского алгоритма требует $O(n^3 \log n)$ операций, что неприемлемо для больших выборок.

Энтропийная регуляризация и алгоритм Синкхорна

Прорывом стала энтропийная регуляризация (Кутури, 2013)^[1]. К целевой функции добавляют энтропию плана со знаком минус: $\min_{P \in U(a,b)} \langle C, P \rangle - \varepsilon H(P), \quad H(P) = -\sum_{i,j} P_{ij} (\log P_{ij} - 1),$ где $\varepsilon > 0$ - параметр регуляризации. Регуляризованная задача строго выпукла и имеет единственное решение вида $P_{ij} = u_i K_{ij} v_j$ , где $K_{ij} = \exp(-C_{ij}/\varepsilon)$ . Множители $u, v$ находятся с помощью алгоритма Синкхорна - попеременного масштабирования строк и столбцов, сходящегося со скоростью, зависящей от $\varepsilon$ . Каждая итерация стоит $O(nm)$ , что делает метод применимым к задачам умеренной размерности. На больших $\varepsilon$ результат сглаживается; на малых - приближается к точному ОТ. Часто используют Sinkhorn divergence - регуляризованную версию $W_p$ с поправкой на смещение.

Масштабируемые приближения

Для повышения масштабируемости применяются стохастические методы (усреднение по мини-батчам, стохастический градиентный спуск по потенциалам), иерархический ОТ (рекурсивное разбиение пространства) и низкоранговые аппроксимации матрицы $C$ . Библиотеки Python Optimal Transport (POT) и OTT-JAX предоставляют высокопроизводительные реализации на GPU.

Нейросетевые методы

Для непрерывных распределений транспортное отображение $T$ или потенциалы Канторовича параметризуются нейронными сетями. Отображение Монжа часто ищется в классе выпуклых градиентов, а для вычисления $W_2$ используют входо-выпуклые нейронные сети (ICNN)^[1]. Двойственная задача также решается путём состязательной оптимизации (adversarial training), аналогично WGAN.

Связь с машинным обучением

Генеративное моделирование: WGAN

Классические GAN используют дивергенцию Йенсена-Шеннона, которая может быть разрывной и приводить к исчезновению градиентов, когда носители распределений не пересекаются. Wasserstein GAN заменяет её на $W_1$ (Earth mover's distance), которая непрерывна и почти всюду дифференцируема^[1]. Критик (дискриминатор) при этом является 1-липшицевой функцией, максимизирующей разность средних на реальной и сгенерированной выборках; липшицевость обеспечивается градиентным штрафом (WGAN-GP). Это дало значительный скачок в стабильности обучения и качестве генерации. Впоследствии появились Sinkhorn GAN, использующие энтропийно-регуляризованные расстояния.

Доменная адаптация и перенос обучения

В задаче адаптации домена необходимо выровнять распределения признаков в исходном и целевом доменах. ОТ позволяет найти транспортный план, учитывающий не только маргинальные распределения, но и совместное распределение признаков и меток (JDOT — Joint Distribution Optimal Transport)^[1]. План переноса затем используется для преобразования образцов или для адаптации классификатора.

Анализ омиксных данных

В single-cell RNA-seq данных ОТ восстанавливает траектории развития клеток. Например, метод Waddington-OT (Schiebinger et al., 2019) строит транспортный план между распределениями клеток в последовательные моменты времени, интерпретируемый как вероятности дифференцировки^[1]. Это позволяет детально описывать клеточные переходы и предсказывать судьбу клеток.

Другие применения

Выравнивание межъязыковых векторных представлений слов: ОТ находит соответствие между эмбеддингами на разных языках, превосходя по точности линейные отображения^[1].
Сравнение графов и молекул: расстояние Громова-Вассерштейна позволяет сопоставлять структуры без явного вложения в общее пространство^[1].
Цветокоррекция и перенос стиля: транспортный план между гистограммами цветов двух изображений реализует высококачественное преобразование палитры.
Обучение представлений: Wasserstein Autoencoder (WAE) использует ОТ-регуляризацию для выравнивания латентного распределения, а барицентры Вассерштейна усредняют распределения в задачах федеративного обучения.

Преимущества и ограничения

Преимущества

Геометрическая чувствительность. ОТ учитывает метрику исходного пространства, а не только значения плотностей.
Слабая метрика. В отличие от KL-дивергенции, $W_p$ непрерывна относительно слабой сходимости и не обращается в бесконечность при несовпадающих носителях, обеспечивая полезные градиенты.
Интерпретируемость. Транспортный план даёт структурное соответствие между элементами двух распределений, что ценно в биологии и текст-анализе.
Гладкие барицентры. Линейная интерполяция в пространстве Вассерштейна порождает плавные морфинги распределений.

Ограничения

Вычислительная сложность. Точный дискретный ОТ требует $O(n^3 \log n)$ операций; энтропийный Sinkhorn снижает до $O(n^2)$ на итерацию, но всё ещё тяжёл для миллионов точек.
Проклятие размерности. Оценка $W_p$ по эмпирическим выборкам сходится со скоростью $O(n^{-1/d})$ , что делает ОТ ненадёжным в высокоразмерных пространствах без дополнительных предположений.
Смещение регуляризации. Энтропийный ОТ не является истинной метрикой и вносит смещение, пропорциональное $\varepsilon$ .
Чувствительность к выбросам. Транспортные планы могут сильно искажаться отдельными удалёнными точками.
Сложность отображения. Восстановление детерминированного отображения Монжа в непрерывном случае остаётся вычислительно нетривиальной задачей.

Современные применения в науке и индустрии

Помимо машинного обучения, оптимальный транспорт применяется в экономике (логистика, сопоставление спроса и предложения), гидродинамике (уравнения Эйлера и Навье–Стокса как градиентные потоки в пространстве Вассерштейна), метеорологии (интерполяция полей осадков), компьютерном зрении (регистрация изображений, восстановление глубины), нейронауке (сравнение карт активности мозга) и астрофизике (реконструкция ранней Вселенной).

См. также

Примечания

Источник — «http://recognition.su/wiki/index.php?title=%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D1%82%D1%80%D0%B0%D0%BD%D1%81%D0%BF%D0%BE%D1%80%D1%82»

Категории: Теория вероятностей | Машинное обучение | Оптимальный транспорт | Вычислительная математика | Метрики и расстояния

@@ Строка 1: / Строка 1: @@
 {{well|Статья написана с использованием LLM '''DeepSeek''' и проверена участником [[Участник:Kirill_Savitskii|К.А.Савицкий]] {{CURRENTTIME}}, {{CURRENTDAY}} {{CURRENTMONTHNAME}} {{CURRENTYEAR}} (UTC)}}
-'''Оптимальный транспорт''' (ОТ; optimal transport) — математическая дисциплина, изучающая способы перемещения [[вероятностная мера|вероятностных масс]] между распределениями с наименьшими затратами. Возникнув из задачи о перемещении грунта, сформулированной [[Монж, Гаспар|Гаспаром Монжем]] в 1781 году, теория получила строгое обоснование в работах [[Канторович, Леонид Витальевич|Леонида Канторовича]] и сегодня стала ключевым инструментом в [[машинное обучение|машинном обучении]], позволяя сравнивать и преобразовывать [[распределение вероятностей|распределения данных]] с учётом геометрии исходного пространства.
+'''Оптимальный транспорт''' (ОТ; optimal transport) — математическая дисциплина, изучающая способы перемещения [[вероятностная мера|вероятностных масс]] между распределениями с наименьшими затратами. Возникнув из задачи о перемещении грунта, сформулированной Гаспаром Монжем в 1781 году, теория получила строгое обоснование в работах Леонида Канторовича и сегодня стала ключевым инструментом в [[машинное обучение|машинном обучении]], позволяя сравнивать и преобразовывать [[распределение вероятностей|распределения данных]] с учётом геометрии исходного пространства.
 == Введение ==
-Интуитивно оптимальный транспорт можно представить как задачу о перемещении кучи песка в яму с минимальными усилиями. Пусть даны две «кучи» — [[вероятностная мера|вероятностные меры]] <tex>\mu</tex> и <tex>\nu</tex>, определённые на [[метрическое пространство|метрических пространствах]] <tex>\mathcal{X}</tex> и <tex>\mathcal{Y}</tex>. Задана функция затрат <tex>c(x,y)</tex>, оценивающая стоимость переноса единицы массы из точки <tex>x \in \mathcal{X}</tex> в точку <tex>y \in \mathcal{Y}</tex>; обычно <tex>c(x,y) = \|x - y\|^p</tex> для некоторого <tex>p \ge 1</tex>. Требуется найти транспортный план, доставляющий минимум полной стоимости. В отличие от поточечных расхождений (например, [[Расстояние Кульбака — Лейблера|дивергенции Кульбака–Лейблера]]), ОТ учитывает расстояние между точками исходного пространства, что делает его особенно полезным для данных, лежащих в геометрически структурированных [[пространство признаков|пространствах признаков]] — изображений, текстов, графов.
+Интуитивно оптимальный транспорт можно представить как задачу о перемещении кучи песка в яму с минимальными усилиями. Пусть даны две «кучи» - [[вероятностная мера|вероятностные меры]] <tex>\mu</tex> и <tex>\nu</tex>, определённые на [[метрическое пространство|метрических пространствах]] <tex>\mathcal{X}</tex> и <tex>\mathcal{Y}</tex>. Задана функция затрат <tex>c(x,y)</tex>, оценивающая стоимость переноса единицы массы из точки <tex>x \in \mathcal{X}</tex> в точку <tex>y \in \mathcal{Y}</tex>; обычно <tex>c(x,y) = \|x - y\|^p</tex> для некоторого <tex>p \ge 1</tex>. Требуется найти транспортный план, доставляющий минимум полной стоимости. В отличие от поточечных расхождений (например, [[Дивергенция Кульбака - Лейблера|дивергенции Кульбака-Лейблера]]), ОТ учитывает расстояние между точками исходного пространства, что делает его особенно полезным для данных, лежащих в геометрически структурированных [[пространство признаков|пространствах признаков]] - изображений, текстов, графов.
 == История развития ==
-* '''1781 г.''' — [[Монж, Гаспар|Гаспар Монж]] формулирует задачу о ''де- и ремблировании'' (перемещении земли) и предлагает геометрическое решение для одномерного случая<ref>{{статья |автор=Монж Г. |заглавие=Mémoire sur la théorie des déblais et des remblais |издание=Histoire de l’Académie Royale des Sciences de Paris |год=1781 |страницы=666–704}}</ref>.
+* '''1781 г.''' - Гаспар Монж формулирует задачу о ''де- и ремблировании'' (перемещении земли) и предлагает геометрическое решение для одномерного случая<ref>{{статья |автор=Монж Г. |заглавие=Mémoire sur la théorie des déblais et des remblais |издание=Histoire de l’Académie Royale des Sciences de Paris |год=1781 |страницы=666-704}}</ref>.
-* '''1942 г.''' — [[Канторович, Леонид Витальевич|Леонид Канторович]] ослабляет постановку Монжа, вводя понятие транспортного плана как [[совместное распределение|совместного распределения]], и сводит задачу к [[линейное программирование|линейному программированию]]<ref>{{статья |автор=Канторович Л. В. |заглавие=О перемещении масс |издание=[[Доклады Академии наук|Доклады Академии наук СССР]] |год=1942 |том=37 |номер=7—8 |страницы=227—229}}</ref>. Эта работа легла в основу [[транспортная задача|транспортной задачи]] и принесла учёному [[Нобелевская премия по экономике|Нобелевскую премию по экономике]] в 1975 году.
+* '''1942 г.''' - Леонид Канторович ослабляет постановку Монжа, вводя понятие транспортного плана как [[совместное распределение|совместного распределения]], и сводит задачу к [[линейное программирование|линейному программированию]]<ref>{{статья |автор=Канторович Л. В. |заглавие=О перемещении масс |издание=[[Доклады Академии наук|Доклады Академии наук СССР]] |год=1942 |том=37 |номер=7-8 |страницы=227-229}}</ref>. Эта работа легла в основу [[транспортная задача|транспортной задачи]] и принесла учёному Нобелевскую премию по экономике в 1975 году.
-* '''1980–2000-е гг.''' — Глубокие математические результаты: связь с [[уравнение Монжа — Ампера|уравнением Монжа–Ампера]] (Бренье, 1991), метрическая структура [[метрика Вассерштейна|пространства Вассерштейна]] (Отто, 2001), исчерпывающая монография [[Виллани, Седрик|Седрика Виллани]]<ref>{{книга |автор=Виллани С. |заглавие=Optimal Transport: Old and New |издательство=[[Springer Science+Business Media|Springer]] |год=2009 |серия=Grundlehren der mathematischen Wissenschaften |isbn=978-3-540-71049-3}}</ref>.
+* '''1980–2000-е гг.''' - Глубокие математические результаты: связь с [[уравнение Монжа - Ампера|уравнением Монжа-Ампера]] (Бренье, 1991), метрическая структура [[метрика Вассерштейна|пространства Вассерштейна]] (Отто, 2001), исчерпывающая монография Седрика Виллани<ref>{{книга |автор=Виллани С. |заглавие=Optimal Transport: Old and New |издательство=[[Springer Science+Business Media|Springer]] |год=2009 |серия=Grundlehren der mathematischen Wissenschaften |isbn=978-3-540-71049-3}}</ref>.
-* '''2013 г.''' — Марко Кутури предлагает энтропийную регуляризацию и алгоритм Синкхорна, делая вычисление ОТ практически масштабируемым для [[глубокое обучение|глубокого обучения]]<ref name="cuturi2013">{{статья |автор=Cuturi M. |заглавие=Sinkhorn Distances: Lightspeed Computation of Optimal Transport |издание=Advances in Neural Information Processing Systems |год=2013 |том=26}}</ref>.
+* '''2013 г.''' - Марко Кутури предлагает энтропийную регуляризацию и алгоритм Синкхорна, делая вычисление ОТ практически масштабируемым для [[глубокое обучение|глубокого обучения]]<ref name="cuturi2013">{{статья |автор=Cuturi M. |заглавие=Sinkhorn Distances: Lightspeed Computation of Optimal Transport |издание=Advances in Neural Information Processing Systems |год=2013 |том=26}}</ref>.
-* '''2017 г.''' — Аржовский и др. вводят [[Wasserstein GAN|Wasserstein GAN]] (WGAN), напрямую использующий [[Расстояние Вассерштейна |метрику Вассерштейна-1]] как функцию потерь, что значительно повышает стабильность обучения [[генеративно-состязательная сеть|генеративно-состязательных сетей]]<ref name="wgan">{{статья |автор=Arjovsky M., Chintala S., Bottou L. |заглавие=Wasserstein GAN |издание=arXiv:1701.07875 |год=2017}}</ref>.
+* '''2017 г.''' - Аржовский и др. вводят [[Wasserstein GAN|Wasserstein GAN]] (WGAN), напрямую использующий [[Расстояние Вассерштейна |метрику Вассерштейна-1]] как функцию потерь, что значительно повышает стабильность обучения [[генеративная состязательная сеть|генеративно-состязательных сетей]]<ref name="wgan">{{статья |автор=Arjovsky M., Chintala S., Bottou L. |заглавие=Wasserstein GAN |издание=arXiv:1701.07875 |год=2017}}</ref>.
 == Постановки задач ==
@@ Строка 18: / Строка 18: @@
 <tex>\int_{\mathcal{X}} c(x, T(x)) \, d\mu(x)</tex>
 при условии, что мера <tex>\mu</tex>, перенесённая отображением <tex>T</tex>, совпадает с <tex>\nu</tex> (сохранение массы): <tex>T_\#\mu = \nu</tex>, т.е. <tex>\nu(B) = \mu(T^{-1}(B))</tex> для любого измеримого множества <tex>B \subset \mathcal{Y}</tex>.
-Основные ограничения: решение не всегда существует (особенно если <tex>\mu</tex> имеет атомы, а <tex>\nu</tex> — нет), а оптимизация по нелинейному отображению крайне сложна.
+Основные ограничения: решение не всегда существует (особенно если <tex>\mu</tex> имеет атомы, а <tex>\nu</tex> - нет), а оптимизация по нелинейному отображению крайне сложна.
 === Задача Канторовича ===
-Канторович предложил релаксацию: вместо детерминированного переноса рассматривается транспортный план <tex>\pi</tex> — [[вероятностная мера]] на произведении <tex>\mathcal{X} \times \mathcal{Y}</tex>, [[маргинальное распределение|маргиналы]] которой равны <tex>\mu</tex> и <tex>\nu</tex>. Множество таких планов обозначается <tex>\Pi(\mu, \nu)</tex>. Задача Канторовича записывается как
+Канторович предложил релаксацию: вместо детерминированного переноса рассматривается транспортный план <tex>\pi</tex> - вероятностная мера на произведении <tex>\mathcal{X} \times \mathcal{Y}</tex>, [[маргинальное распределение|маргиналы]] которой равны <tex>\mu</tex> и <tex>\nu</tex>. Множество таких планов обозначается <tex>\Pi(\mu, \nu)</tex>. Задача Канторовича записывается как
 <tex>\inf_{\pi \in \Pi(\mu, \nu)} \int_{\mathcal{X}\times\mathcal{Y}} c(x,y) \, d\pi(x,y).</tex>
 Это линейная задача с выпуклым множеством ограничений, всегда имеющая решение при слабых условиях на <tex>c</tex>. Оптимальный план <tex>\pi^*</tex> описывает вероятностное перемещение масс: доля массы из окрестности <tex>x</tex>, направляемая в окрестность <tex>y</tex>.
@@ Строка 30: / Строка 30: @@
 Функции <tex>\varphi</tex> и <tex>\psi</tex> называются потенциалами Канторовича. Для стоимости <tex>c(x,y)=\|x-y\|</tex> двойственная задача сводится к супремуму по 1-[[Липшицева функция|липшицевым]] функциям:
 <tex>W_1(\mu, \nu) = \sup_{f:\ \|f\|_{\text{Lip}} \le 1} \left( \int f \, d\mu - \int f \, d\nu \right),</tex>
-известному как формула Канторовича–Рубинштейна, и используется в WGAN.
+известному как формула Канторовича-Рубинштейна, и используется в WGAN.
 === Метрика Вассерштейна ===
-Для <tex>p \ge 1</tex> [[расстояние Вассерштейна]] порядка <tex>p</tex> между мерами <tex>\mu</tex> и <tex>\nu</tex> определяется как
+Для <tex>p \ge 1</tex> расстояние Вассерштейна порядка <tex>p</tex> между мерами <tex>\mu</tex> и <tex>\nu</tex> определяется как
 <tex>W_p(\mu, \nu) = \left( \inf_{\pi \in \Pi(\mu, \nu)} \int \|x-y\|^p \, d\pi(x,y) \right)^{1/p}.</tex>
-При <tex>p=1</tex> оно известно как расстояние землекопа. <tex>W_p</tex> является метрикой на пространстве мер с конечным <tex>p</tex>-м моментом, метризует [[слабая сходимость|слабую сходимость]] и учитывает геометрию пространства: расстояние между двумя [[дельта-мера]]ми равно обычному расстоянию между их носителями. Это выгодно отличает его от [[Расстояние Кульбака — Лейблера|KL-]] или [[Полная вариация|TV-расхождений]].
+При <tex>p=1</tex> оно известно как расстояние землекопа. <tex>W_p</tex> является метрикой на пространстве мер с конечным <tex>p</tex>-м моментом, метризует [[слабая сходимость|слабую сходимость]] и учитывает геометрию пространства: расстояние между двумя [[дельта-мера| дельта-мерами]] равно обычному расстоянию между их носителями. Это выгодно отличает его от [[Дивергенция Кульбака - Лейблера|KL-]] или [[Полная вариация|TV-расхождений]].
 == Вычислительные методы ==
 === Дискретный случай и линейное программирование ===
-На практике распределения заданы эмпирическими выборками: <tex>\hat{\mu} = \sum_{i=1}^n a_i \delta_{x_i}</tex>, <tex>\hat{\nu} = \sum_{j=1}^m b_j \delta_{y_j}</tex>, где <tex>a \in \mathbb{R}_{+}^n, b \in \mathbb{R}_{+}^m</tex> — векторы весов, <tex>\sum_i a_i = \sum_j b_j = 1</tex>. Транспортный план сводится к матрице <tex>P \in \mathbb{R}_{+}^{n \times m}</tex>, а ограничения — к <tex>P \mathbf{1}_m = a,\ P^\top \mathbf{1}_n = b</tex>. Задача Канторовича принимает вид [[линейное программирование|линейной программы]]:
+На практике распределения заданы эмпирическими выборками: <tex>\hat{\mu} = \sum_{i=1}^n a_i \delta_{x_i}</tex>, <tex>\hat{\nu} = \sum_{j=1}^m b_j \delta_{y_j}</tex>, где <tex>a \in \mathbb{R}_{+}^n, b \in \mathbb{R}_{+}^m</tex> - векторы весов, <tex>\sum_i a_i = \sum_j b_j = 1</tex>. Транспортный план сводится к матрице <tex>P \in \mathbb{R}_{+}^{n \times m}</tex>, а ограничения - к <tex>P \mathbf{1}_m = a,\ P^\top \mathbf{1}_n = b</tex>. Задача Канторовича принимает вид [[линейное программирование|линейной программы]]:
 <tex>\min_{P \in U(a,b)} \langle C, P \rangle,</tex>
 где <tex>C_{ij} = c(x_i, y_j)</tex>. При <tex>n = m</tex> точное решение с помощью [[симплекс-метод]]а или венгерского алгоритма требует <tex>O(n^3 \log n)</tex> операций, что неприемлемо для больших выборок.
@@ Строка 46: / Строка 46: @@
 Прорывом стала энтропийная регуляризация (Кутури, 2013)<ref name="cuturi2013"/>. К целевой функции добавляют [[энтропия|энтропию]] плана со знаком минус:
 <tex>\min_{P \in U(a,b)} \langle C, P \rangle - \varepsilon H(P), \quad H(P) = -\sum_{i,j} P_{ij} (\log P_{ij} - 1),</tex>
-где <tex>\varepsilon > 0</tex> — параметр регуляризации. Регуляризованная задача строго выпукла и имеет единственное решение вида <tex>P_{ij} = u_i K_{ij} v_j</tex>, где <tex>K_{ij} = \exp(-C_{ij}/\varepsilon)</tex>. Множители <tex>u, v</tex> находятся с помощью [[алгоритм Синкхорна|алгоритма Синкхорна]] — попеременного масштабирования строк и столбцов, сходящегося со скоростью, зависящей от <tex>\varepsilon</tex>. Каждая итерация стоит <tex>O(nm)</tex>, что делает метод применимым к задачам умеренной размерности. На больших <tex>\varepsilon</tex> результат сглаживается; на малых — приближается к точному ОТ. Часто используют Sinkhorn divergence — регуляризованную версию <tex>W_p</tex> с поправкой на смещение.
+где <tex>\varepsilon > 0</tex> - параметр регуляризации. Регуляризованная задача строго выпукла и имеет единственное решение вида <tex>P_{ij} = u_i K_{ij} v_j</tex>, где <tex>K_{ij} = \exp(-C_{ij}/\varepsilon)</tex>. Множители <tex>u, v</tex> находятся с помощью [[алгоритм Синкхорна|алгоритма Синкхорна]] - попеременного масштабирования строк и столбцов, сходящегося со скоростью, зависящей от <tex>\varepsilon</tex>. Каждая итерация стоит <tex>O(nm)</tex>, что делает метод применимым к задачам умеренной размерности. На больших <tex>\varepsilon</tex> результат сглаживается; на малых - приближается к точному ОТ. Часто используют Sinkhorn divergence - регуляризованную версию <tex>W_p</tex> с поправкой на смещение.
 === Масштабируемые приближения ===
-Для повышения масштабируемости применяются [[стохастический оптимальный транспорт|стохастические методы]] (усреднение по мини-батчам, стохастический градиентный спуск по потенциалам), [[иерархический ОТ]] (рекурсивное разбиение пространства) и низкоранговые аппроксимации матрицы <tex>C</tex>. Библиотеки [[Python Optimal Transport]] (POT) и [[OTT-JAX]] предоставляют высокопроизводительные реализации на [[GPU]].
+Для повышения масштабируемости применяются [[стохастический оптимальный транспорт|стохастические методы]] (усреднение по мини-батчам, стохастический градиентный спуск по потенциалам), [[иерархический ОТ]] (рекурсивное разбиение пространства) и низкоранговые аппроксимации матрицы <tex>C</tex>. Библиотеки Python Optimal Transport (POT) и OTT-JAX предоставляют высокопроизводительные реализации на GPU.
 === Нейросетевые методы ===
@@ Строка 56: / Строка 56: @@
 == Связь с машинным обучением ==
 === Генеративное моделирование: WGAN ===
-Классические [[генеративно-состязательная сеть|GAN]] используют [[Расстояние Кульбака — Лейблера|дивергенцию Йенсена–Шеннона]], которая может быть разрывной и приводить к исчезновению градиентов, когда носители распределений не пересекаются. [[Wasserstein GAN]] заменяет её на <tex>W_1</tex> (Earth mover's distance), которая непрерывна и почти всюду дифференцируема<ref name="wgan"/>. Критик (дискриминатор) при этом является 1-липшицевой функцией, максимизирующей разность средних на реальной и сгенерированной выборках; липшицевость обеспечивается [[градиентный штраф|градиентным штрафом]] (WGAN-GP). Это дало значительный скачок в стабильности обучения и качестве генерации. Впоследствии появились Sinkhorn GAN, использующие энтропийно-регуляризованные расстояния.
+Классические [[генеративная состязательная сеть|GAN]] используют [[Дивергенция Кульбака-Лейблера|дивергенцию Йенсена-Шеннона]], которая может быть разрывной и приводить к исчезновению градиентов, когда носители распределений не пересекаются. [[Wasserstein GAN]] заменяет её на <tex>W_1</tex> (Earth mover's distance), которая непрерывна и почти всюду дифференцируема<ref name="wgan"/>. Критик (дискриминатор) при этом является 1-липшицевой функцией, максимизирующей разность средних на реальной и сгенерированной выборках; липшицевость обеспечивается градиентным штрафом (WGAN-GP). Это дало значительный скачок в стабильности обучения и качестве генерации. Впоследствии появились Sinkhorn GAN, использующие энтропийно-регуляризованные расстояния.
 === Доменная адаптация и перенос обучения ===
@@ Строка 62: / Строка 62: @@
 === Анализ омиксных данных ===
-В [[single-cell RNA-seq]] данных ОТ восстанавливает траектории развития клеток. Например, метод Waddington-OT (Schiebinger et al., 2019) строит транспортный план между распределениями клеток в последовательные моменты времени, интерпретируемый как вероятности дифференцировки<ref>{{статья |автор=Schiebinger G. et al. |заглавие=Optimal-Transport Analysis of Single-Cell Gene Expression Identifies Developmental Trajectories in Reprogramming |издание=Cell |год=2019 |том=176 |номер=4 |страницы=928–943}}</ref>. Это позволяет детально описывать клеточные переходы и предсказывать судьбу клеток.
+В [[single-cell RNA-seq]] данных ОТ восстанавливает траектории развития клеток. Например, метод Waddington-OT (Schiebinger et al., 2019) строит транспортный план между распределениями клеток в последовательные моменты времени, интерпретируемый как вероятности дифференцировки<ref>{{статья |автор=Schiebinger G. et al. |заглавие=Optimal-Transport Analysis of Single-Cell Gene Expression Identifies Developmental Trajectories in Reprogramming |издание=Cell |год=2019 |том=176 |номер=4 |страницы=928-943}}</ref>. Это позволяет детально описывать клеточные переходы и предсказывать судьбу клеток.
 === Другие применения ===
-* '''Выравнивание межъязыковых векторных представлений слов:''' ОТ находит соответствие между [[word embedding|эмбеддингами]] на разных языках, превосходя по точности линейные отображения<ref>{{статья |автор=Grave E., Joulin A., Berthet Q. |заглавие=Unsupervised Alignment of Embeddings with Wasserstein Procrustes |издание=Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics |год=2019}}</ref>.
+* '''Выравнивание межъязыковых векторных представлений слов:''' ОТ находит соответствие между эмбеддингами на разных языках, превосходя по точности линейные отображения<ref>{{статья |автор=Grave E., Joulin A., Berthet Q. |заглавие=Unsupervised Alignment of Embeddings with Wasserstein Procrustes |издание=Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics |год=2019}}</ref>.
-* '''Сравнение графов и молекул:''' расстояние Громова–Вассерштейна позволяет сопоставлять структуры без явного вложения в общее пространство<ref>{{статья |автор=Titouan V., Courty N., Tavenard R., Laetitia C., Flamary R. |заглавие=Optimal Transport for structured data: a survey |издание=arXiv:1905.10088 |год=2019}}</ref>.
+* '''Сравнение графов и молекул:''' расстояние Громова-Вассерштейна позволяет сопоставлять структуры без явного вложения в общее пространство<ref>{{статья |автор=Titouan V., Courty N., Tavenard R., Laetitia C., Flamary R. |заглавие=Optimal Transport for structured data: a survey |издание=arXiv:1905.10088 |год=2019}}</ref>.
 * '''Цветокоррекция и перенос стиля:''' транспортный план между гистограммами цветов двух изображений реализует высококачественное преобразование палитры.
 * '''Обучение представлений:''' Wasserstein Autoencoder (WAE) использует ОТ-регуляризацию для выравнивания латентного распределения, а барицентры Вассерштейна усредняют распределения в задачах федеративного обучения.
@@ Строка 85: / Строка 85: @@
 == Современные применения в науке и индустрии ==
-Помимо машинного обучения, оптимальный транспорт применяется в экономике (логистика, сопоставление спроса и предложения), [[гидродинамика|гидродинамике]] (уравнения Эйлера и Навье–Стокса как градиентные потоки в пространстве Вассерштейна), [[метеорология|метеорологии]] (интерполяция полей осадков), [[компьютерное зрение|компьютерном зрении]] (регистрация изображений, восстановление глубины), [[нейронаука|нейронауке]] (сравнение карт активности мозга) и [[астрофизика|астрофизике]] (реконструкция ранней Вселенной).
+Помимо машинного обучения, оптимальный транспорт применяется в экономике (логистика, сопоставление спроса и предложения), гидродинамике (уравнения Эйлера и Навье–Стокса как градиентные потоки в пространстве Вассерштейна), метеорологии (интерполяция полей осадков), [[компьютерное зрение|компьютерном зрении]] (регистрация изображений, восстановление глубины), нейронауке (сравнение карт активности мозга) и астрофизике (реконструкция ранней Вселенной).
 == См. также ==
 * [[Транспортная задача]]
-* [[Метрика Вассерштейна]]
+* [[Дивергенция Кульбака-Лейблера]]
-* [[Расстояние Кульбака — Лейблера]]
+* [[Генеративная состязательная сеть]]
-* [[Генеративно-состязательная сеть]]
+* [[Алгоритм Синкхорна]]
-* [[Sinkhorn algorithm|Алгоритм Синкхорна]]
-* [[Громов — Вассерштейн расстояние]]
 * [[Расстояние Вассерштейна]]