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

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

Версия от 20:14, 14 июля 2026; Kirill Savitskii (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM DeepSeek и проверена участником К.А.Савицкий 23:44, 14 июль 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://machinelearning.ru/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»

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