Расстояние Вассерштейна

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

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

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

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

Расстояние Вассерштейна (также расстояние Канторовича–Рубинштейна, Earth Mover’s Distance) — семейство метрик на пространстве вероятностных мер, определяемое через решение оптимальной транспортной задачи. Названо в честь Л. Н. Вассерштейна, описавшего его как частный случай метрики Канторовича–Рубинштейна, однако сам термин «расстояние Вассерштейна» был введён Р. Л. Добрушиным в 1970 году. В компьютерных науках и машинном обучении широко известен как Earth Mover’s Distance (EMD) — «расстояние перемещения земли».

Интуитивное понимание

Представим две кучи земли, соответствующие двум вероятностным распределениям. Расстояние Вассерштейна измеряет минимальные «затраты» на превращение одной кучи в другую: землю нужно перевезти так, чтобы минимизировать суммарное произведение массы на пройденный путь. Если земля перемещается на малое расстояние, распределения похожи; если требуется переносить массы далеко, они сильно различаются. В отличие от расстояния Кульбака–Лейблера или полного отклонения, которые не учитывают геометрию носителя, расстояние Вассерштейна отражает «пространственную» структуру данных.

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

Задача оптимальной транспортировки была поставлена Гаспаром Монжем в 1781 году. В 1942 году Л. В. Канторович предложил релаксацию, заменив детерминированную транспортировку на вероятностную, и доказал существование двойственной задачи. В 1958 году Г. Ш. Рубинштейн ввёл норму Канторовича–Рубинштейна, эквивалентную $W_1$ . Л. Н. Вассерштейн в 1969 году использовал метрику $W_1$ для описания марковских процессов, а в 1970 году Р. Л. Добрушин показал, что все $W_p$ метризуют слабую сходимость плюс сходимость моментов, и предложил термин «расстояние Вассерштейна». В 1990–2000-е годы оно получило развитие в работах С. Виллани, Ф. Сантамброджио и других. В 2017 году М. Аржовский и соавторы использовали $W_1$ в генеративно-состязательных сетях (WGAN), вызвав бум приложений в машинном обучении.

Математические основы

Постановка Монжа

Пусть $(M, d)$ — метрическое пространство, а $\mu, \nu \in \mathcal{P}(M)$ — вероятностные меры. Задача Монжа ищет измеримое отображение $T: M \to M$ с условием сохранения меры $T_\# \mu = \nu$ , минимизирующее стоимость $\int_M d(x, T(x))^p \, d\mu(x).$ Такое отображение существует далеко не всегда.

Постановка Канторовича

Релаксация Канторовича рассматривает множество транспортных планов $\Gamma(\mu, \nu)$ — совместных распределений на $M \times M$ с маргиналами $\mu$ и $\nu$ . p-расстояние Вассерштейна для $p \ge 1$ определяется как $W_p(\mu,\nu) = \left( \inf_{\gamma \in \Gamma(\mu,\nu)} \int_{M \times M} d(x,y)^p \, d\gamma(x,y) \right)^{1/p}.$ При $p = 1$ получаем расстояние Канторовича–Рубинштейна.

Двойственная формулировка

Для $W_1$ справедлива двойственная формула Канторовича–Рубинштейна: $W_1(\mu,\nu) = \sup_{\|f\|_{\mathrm{Lip}} \le 1} \left( \int_M f \, d\mu - \int_M f \, d\nu \right),$ где супремум берётся по 1-липшицевым функциям $f: M \to \mathbb{R}$ . Эта форма легла в основу Wasserstein GAN.

Частные случаи

Одномерный случай: для мер на $\mathbb{R}$ с функциями распределения $F_\mu, F_\nu$ и их обратными (квантильными) функциями $F^{-1}_\mu, F^{-1}_\nu$ :

$W_p(\mu,\nu) = \left( \int_0^1 |F^{-1}_\mu(t) - F^{-1}_\nu(t)|^p \, dt \right)^{1/p}.$

Дискретный случай: если $\mu = \sum_i a_i \delta_{x_i}, \nu = \sum_j b_j \delta_{y_j}$ , где $a_i, b_j$ — веса, задача сводится к линейному программированию:

$\min_{\Gamma \ge 0} \sum_{i,j} \Gamma_{ij} d(x_i, y_j)^p \quad \text{при} \quad \sum_j \Gamma_{ij} = a_i,\; \sum_i \Gamma_{ij} = b_j.$

Вычисление

Дискретные меры

Транспортная задача решается симплекс-методом или специализированными алгоритмами (венгерский, network simplex). Сложность $O(n^3 \log n)$ для двух множеств размера $n$ , что ограничивает масштабируемость.

Энтропийная регуляризация и Sinkhorn distance

Для ускорения М. Кутюри (2013) предложил добавить энтропийный штраф: $\min_{\Gamma} \sum_{i,j} \Gamma_{ij} C_{ij} - \varepsilon H(\Gamma),$ где $H(\Gamma) = -\sum \Gamma_{ij}(\log \Gamma_{ij} - 1)$ . Решение принимает вид $\Gamma_{ij} = u_i K_{ij} v_j$ с $K_{ij} = e^{-C_{ij}/\varepsilon}$ , что позволяет применить быстрый алгоритм Синкхорна с линейной сходимостью. Это даёт дифференцируемую аппроксимацию, широко используемую в глубоком обучении.

Непрерывный случай

В размерности больше единицы прямое вычисление нетривиально. На практике применяют:

Параметризацию транспортного плана нейросетями (Wasserstein GAN использует дуальную форму);
Стохастическую оптимизацию (минимизация по мини-батчам);
Сплайновые и вариационные методы для малых размерностей.

Программные библиотеки

Основные open-source реализации: POT (Python Optimal Transport), GeomLoss для PyTorch/TensorFlow, JAX-OT.

import numpy as np
import ot  # Python Optimal Transport (POT)

# Задаём носители двух дискретных распределений
x = np.array([1.0, 2.0, 3.0])  # позиции "ям"
y = np.array([2.5, 3.5, 4.5])  # позиции "холмов"

# Веса (вероятностные меры)
a = np.array([0.2, 0.5, 0.3])  # mu
b = np.array([0.4, 0.4, 0.2])  # nu

# Матрица стоимостей (здесь квадрат евклидова расстояния для W_2)
M = ot.dist(x.reshape(-1, 1), y.reshape(-1, 1), metric='sqeuclidean')

# Точное вычисление W_2^2 через решение транспортной задачи
W2_sq = ot.emd2(a, b, M)
W2 = np.sqrt(W2_sq)

print(f"W_2 расстояние: {W2:.4f}")

Свойства

Метрика: $W_p$ задаёт метрику на пространстве мер с конечным $p$ -м моментом.
Топология: сходимость в $W_p$ эквивалентна слабой сходимости плюс сходимость $p$ -х моментов.
Изометрии: пространство мер с метрикой Вассерштейна наследует геометрию исходного пространства; барицентры (средние Фреше) дают интерполяции (барицентр Вассерштейна).
Устойчивость: если носители мер ограничены, $W_p$ непрерывно относительно слабой сходимости.
Связь с другими метриками: $W_1$ совпадает с нормой Канторовича–Рубинштейна; на прямой $W_p$ связано с $L^p$ -расстоянием между квантилями.

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

Учёт геометрии — основное отличие от поточечных дивергенций (KL, JS). Даже если носители не пересекаются, $W_p$ даёт разумную оценку близости, в то время как KL/JS бесконечны или постоянны.
Интерпретируемость — минимальная стоимость транспортировки часто семантически осмыслена.
Дифференцируемость — при энтропийной регуляризации или в дуальной форме градиент может быть передан через генеративные модели, что привело к созданию WGAN.
Метрическая структура — позволяет определять средние, геодезические и барицентры, открывая путь к геометрии пространства распределений.

Ограничения

Вычислительная сложность: точное решение для дискретных мер требует кубического времени, что не подходит для больших выборок.
Проклятие размерности: скорость сходимости выборочных оценок $W_p$ экспоненциально падает с ростом размерности. Для $d$ -мерного пространства ошибка $O(n^{-1/d})$ .
Чувствительность к выбросам: $W_p$ при $p \ge 1$ чувствителен к аномальным наблюдениям, особенно при больших $p$ .
Требование конечных моментов: распределения должны обладать конечным $p$ -м моментом, что исключает тяжёлые хвосты без обрезания.

Применения в машинном обучении

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

Wasserstein GAN (WGAN, 2017): замена кросс-энтропийного дискриминатора на оценку $W_1$ через дуальную форму. Обеспечила более стабильное обучение и осмысленные метрики качества.
Wasserstein Autoencoder (WAE, 2018): использует $W_c$ в латентном пространстве для регуляризации автокодировщика.
Sinkhorn GAN и Salimans et al. (2018) — применение энтропийной регуляризации для масштабируемых генеративных сетей.

Обучение представлений и перенос стиля

Расстояние Вассерштейна применяется для доменной адаптации: оптимальный транспорт выравнивает распределения признаков источника и цели (Courty et al., 2017). В нейронном переносе стиля EMD между гистограммами признаков используется для согласования цветовых распределений.

Анализ данных и биология

В одноклеточных омиксных данных W-distance выравнивает распределения экспрессии по разным условиям (Schiebinger et al., 2019). В компьютерном зрении EMD сравнивает гистограммы изображений и формы (shape matching). В статистике — для проверки гипотез о равенстве многомерных распределений.

Экономика и логистика

Исходная задача Монжа–Канторовича широко применяется в моделировании транспортных потоков и равновесных распределений ресурсов.

См. также

Примечания

Литература

Канторович Л. В. О перемещении масс // Доклады АН СССР. — 1942. — Т. 37. — № 7–8. — С. 227–230.
Вассерштейн Л. Н. Марковские процессы над счётными произведениями пространств, описывающие большие системы автоматов // Проблемы передачи информации. — 1969. — Т. 5. — № 3. — С. 64–72.
Добрушин Р. Л. Задание системы случайных величин при помощи условных распределений // Теория вероятностей и её применения. — 1970. — Т. 15. — № 3. — С. 469–497.
Villani C. Optimal Transport: Old and New. — Springer, 2008. — ISBN 978-3-540-71049-3
Peyré G., Cuturi M. Computational Optimal Transport. — Now Publishers, 2019. — ISBN 978-1-68083-550-2
Arjovsky M., Chintala S., Bottou L. Wasserstein GAN // Proceedings of the 34th International Conference on Machine Learning. — 2017. — С. 214–223.
Cuturi M. Sinkhorn distances: Lightspeed computation of optimal transport // Advances in Neural Information Processing Systems. — 2013. — Т. 26. — С. 2292–2300.
Rubner Y., Tomasi C., Guibas L. J. The Earth Mover’s Distance as a metric for image retrieval // International Journal of Computer Vision. — 2000. — Т. 40. — № 2. — С. 99–121.
Genevay A., Peyré G., Cuturi M. Learning Generative Models with Sinkhorn Divergences // Proceedings of the 21st International Conference on Artificial Intelligence and Statistics. — 2018. — С. 1608–1617.

Источник — «http://recognition.su/wiki/index.php?title=%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%92%D0%B0%D1%81%D1%81%D0%B5%D1%80%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0»

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