Optimal Transport

1942: Ленинград в блокаде, советская армия решает задачу логистики - как доставить грузы из заводов на фронт с минимальными затратами при ограниченных ресурсах. Леонид Канторович, 30-летний математик, формулирует задачу как линейную программу. За это - Нобелевская премия по экономике 1975. Семьдесят лет спустя, в 2013 году, его формула становится основой для обучения генеративных нейронных сетей.

• **WGAN (2017):** замена нестабильной JS-дивергенции на W_1 решила проблему mode collapse в генеративных моделях - сейчас это стандарт обучения GAN
• **Стилевой перенос изображений:** OT между гистограммами цветов в feature space позволяет переносить стиль Ван Гога на фотографию с математически точным совпадением распределения яркостей и цветов
• **Domain adaptation в медицине:** выравнивание распределений данных из разных клиник через OT-план - основа адаптации медицинских AI-моделей к новым больницам без переобучения

Предварительные знания

• Линейное программирование: прямая и двойственная задача, сильная двойственность
• Теория вероятностей: вероятностные меры, маргинальные распределения, матожидание
• Interior Point методы (урок cvx-11): метод барьеров и центральный путь

• Interior Point Methods

Расстояние Вассерштейна как линейная программа

Дано два распределения вероятностей mu и nu на метрическом пространстве. Расстояние Вассерштейна-1 (W_1) - это минимальная стоимость «перевозки» массы из формы mu в форму nu. Формально: W_1(mu, nu) = min_{gamma in Pi(mu, nu)} integral c(x,y) d gamma(x,y), где Pi(mu, nu) - множество всех совместных распределений (coupling) с маргиналями mu и nu.

**Почему это линейная программа?** Объективная функция integral c(x,y) d gamma линейна по gamma. Ограничения: маргинали gamma должны совпадать с mu и nu - это линейные ограничения. gamma >= 0 - ограничение неотрицательности. В дискретном случае с n точками носителя: - Переменная: матрица gamma in R^{n x n} (n^2 переменных) - Ограничения: суммы по строкам = a_i, суммы по столбцам = b_j (2n ограничений) - Это классическая задача транспортировки - частный случай LP.

W_1 обладает свойствами, которых нет у других расстояний между распределениями: он конечен даже когда носители mu и nu не пересекаются (где KL-дивергенция была бы бесконечной), и чувствителен к геометрии метрического пространства. Именно поэтому W_1 стал основой для WGAN.

Не путайте W_1 и W_2. Wasserstein-2: W_2^2 = min integral ||x-y||^2 d gamma. Он чаще используется в теории, W_1 - в практических ML-приложениях (WGAN). Оба - линейные программы по gamma, но с разной матрицей стоимости C.

Алгоритм Синхорна: энтропийная регуляризация

Точное решение транспортного LP стоит O(n^3 log n) через метод симплекса или O(n^3) через Hungarian algorithm - слишком медленно для n > 1000. В 2013 году Марко Кутури (NeurIPS 2013, «Sinkhorn Distances») предложил добавить энтропийную регуляризацию, превратив OT в задачу с гладким решением.

**Энтропийно-регуляризованный OT (Cuturi, 2013):** min_{gamma >= 0} <C, gamma> - epsilon * H(gamma) s.t. gamma * 1 = a, gamma^T * 1 = b где H(gamma) = -sum_{ij} gamma_ij * log(gamma_ij) - энтропия coupling. **Аналитическое решение:** gamma* = diag(u) * K * diag(v) где K_ij = exp(-C_ij / epsilon) - матрица ядра Гиббса. Векторы u и v находятся итерационно - это и есть алгоритм Синхорна.

Каждая итерация Синхорна: u = a / (K v), v = b / (K^T u) - это просто нормировка строк и столбцов матрицы K, чтобы маргинали совпадали с a и b. Сложность: O(n^2) per iteration против O(n^3 log n) для точного LP. Для GPU - матричные умножения параллелизуются идеально.

**Компромисс epsilon:** - epsilon -> 0: gamma* приближает истинный Wasserstein, но алгоритм медленнее и численно нестабильнее - epsilon большой: быстрая сходимость, но сильное размытие (coupling менее «острый») - Типичные значения: epsilon = 0.01..0.1 * median(C) - Log-domain Sinkhorn (stabilized) решает проблему underflow при малом epsilon

Формулировка Канторовича и двойственность

Задача оптимальной транспортировки имеет двухсотлетнюю историю. В 1781 году Гаспар Монж поставил вопрос: как переместить объём земли с одного места на другое с минимальными затратами? Монж требовал детерминированного отображения T: каждая частица из x идёт строго в T(x). Такая задача оказалась математически жёсткой и трудно решаемой.

**Релаксация Канторовича (1942):** Вместо детерминированного map T, разрешить вероятностные coupling: min_{gamma >= 0} sum_{i,j} C_ij * gamma_ij s.t. sum_j gamma_ij = a_i (маргиналь по строке = источник) sum_i gamma_ij = b_j (маргиналь по столбцу = цель) Здесь gamma_ij - сколько массы везём из точки i в точку j. Это LP с n^2 переменными и 2n ограничениями. Леонид Канторович получил Нобелевскую премию по экономике 1975 года за разработку LP и его применения - транспортная задача стала одним из ключевых примеров.

Двойственность даёт практически важный результат: вместо оптимизации по n^2-мерному gamma можно оптимизировать по 2n-мерному (f, g). Для непрерывных распределений это позволяет параметризовать двойственные потенциалы нейронной сетью - основа метода WGAN-GP (Gulrajani et al., 2017).

Связь формулировок Монжа и Канторовича: при выпуклом c(x,y) = ||x-y||^2 оптимальный coupling Канторовича является детерминированным (теорема Брения). То есть gamma* = (id, T*)_# mu для некоторого map T* - градиент выпуклой функции (теорема Брения-Полара). В общем случае coupling может быть недетерминированным.

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

Математика Канторовича 1942 года нашла неожиданное применение в глубоком обучении через задачу обучения генеративных моделей. Задача GAN (Goodfellow, 2014) - найти генератор G, чтобы распределение G(z) совпало с целевым p_data. Но как измерить расстояние между распределениями, когда их носители не пересекаются?

**WGAN (Arjovsky, Chintala, Bottou, 2017):** Заменяют JS-дивергенцию в GAN на W_1: min_G max_{||f||_Lip <= 1} E_{x~p_data}[f(x)] - E_{z~p_z}[f(G(z))] Дискриминатор теперь апроксимирует двойственный потенциал f (1-Липшиц). Градиент W_1 по параметрам G всегда существует - нет проблемы исчезающих градиентов. **Word Mover's Distance (Kusner et al., 2015):** OT между двумя документами в пространстве word2vec эмбеддингов. Расстояние между документами = стоимость перевозки слов одного документа в слова другого.

Барицентры по Вассерштейну (Agueh & Carlier, 2011) решают задачу «среднего» в пространстве мер: дано k распределений, найти меру mu, минимизирующую взвешенную сумму W_2^2(mu, mu_k). В эвклидовом пространстве это обычное взвешенное среднее, в пространстве мер - выпуклая задача со специфической геометрией Вассерштейна (метрика, чувствительная к носителям, а не к плотностям). Практическое применение: усреднение облаков точек, форм, гистограмм.

Ключевые идеи

• **OT = LP:** расстояние Вассерштейна - это линейная программа над coupling gamma; Канторович (1942) релаксировал задачу Монжа от детерминированных map к вероятностным coupling, сделав её решаемой
• **Sinkhorn = OT за O(n^2):** энтропийная регуляризация (Cuturi, NeurIPS 2013) даёт аналитическую форму решения gamma* = diag(u) K diag(v) и итерационный алгоритм нормировок, ускоряя OT с O(n^3 log n) до O(n^2) per iteration
• **Двойственность Канторовича-Рубинштейна:** W_1 = max по 1-Lipschitz функциям f разности E_mu[f] - E_nu[f]; эта формулировка лежит в основе WGAN и позволяет параметризовать OT через нейронные сети

Связанные темы

Optimal Transport объединяет выпуклую оптимизацию с теорией вероятностей и находит применения в нескольких разделах ML:

• Interior Point Methods — Точный solver для транспортного LP использует primal-dual IPM; Sinkhorn - более быстрая альтернатива за счёт регуляризации
• Двойственность в LP — Двойственность Канторовича (f_i + g_j <= C_ij) - прямое следствие LP-двойственности; strong duality гарантирует совпадение primal и dual оптимумов

Вопросы для размышления

• При обучении WGAN выбор epsilon в алгоритме Синхорна влияет на точность аппроксимации W_1. Как выбирать epsilon на практике: что происходит с градиентами генератора при epsilon -> 0 и при epsilon -> infinity?
• Word Mover's Distance между двумя документами вычисляется через OT в пространстве word2vec эмбеддингов. Почему такое расстояние лучше отражает семантическую близость, чем косинусная мера между усреднёнными эмбеддингами?
• Барицентр Вассерштейна нескольких изображений отличается от поточечного усреднения пикселей. В каких задачах компьютерного зрения барицентр Вассерштейна дал бы более осмысленный результат, чем арифметическое среднее?

Связанные уроки

• prob-10-continuous