Задача Монжа: как перенести гору с минимальной работой

1781 год: французский математик Гаспар Монж ставит задачу - как переместить землю при строительстве укреплений с минимальной работой? 200 лет задача оставалась без общего решения. Канторович решил её в 1942 и получил Нобелевку. Сегодня то же уравнение - основа Wasserstein GAN и Stable Diffusion 3.

• WGAN (2017) - первый стабильно обучаемый GAN благодаря замене KL на Wasserstein
• Flow Matching - основа Stable Diffusion 3, Meta MovieGen: в 5-10 раз быстрее диффузии
• Domain adaptation: OT-DA переносит медицинские модели между госпиталями без разметки
• Sinkhorn в CLIP, DINOv2: soft-assignment между image и text embeddings

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

• Функции нескольких переменных

Задача Монжа: транспортный план T и суммарная стоимость

**1781 год, мемуар «Sur la théorie des déblais et des remblais».** Военный инженер Гаспар Монж решает прикладную задачу: армия строит укрепления, землю берут из карьеров (déblais) и укладывают в насыпи (remblais). Объёмы совпадают. Вопрос: какой план переноса минимизирует суммарную работу? Монж формулирует это как поиск отображения T: карьеры → насыпи, минимизирующего интеграл стоимости. Через 240 лет это уравнение запускают на GPU-кластерах, чтобы превращать фото в картины Ван Гога.

Задача Монжа в одной строке: дано два распределения масс μ (источник) и ν (цель) одинаковой суммарной массы. Найти отображение T: X → Y, переводящее μ в ν, такое что суммарная стоимость **∫ c(x, T(x)) dμ(x)** минимальна. Формально: inf_T ∫ c(x, T(x)) dμ при условии T#μ = ν.

Три ключевых слова задачи. **Распределения**, не точки: речь идёт о массе, а не о координатах. **Отображение T**, а не корреляция: каждой точке источника назначается ровно одна точка цели - масса не делится. **Стоимость c(x, y)**: цена переноса единицы массы из x в y, обычно ||x - y||² или ||x - y||. Условие T#μ = ν называется pushforward - требование сохранения массы.

Релаксация Канторовича: от отображения T к плану π

Задача Монжа в чистом виде иногда не имеет решения. Простейший контрпример: μ - точечная масса в точке 0, ν - две точечных массы по 1/2 в точках -1 и +1. Любое отображение T обязано отправить точку 0 куда-то одно - либо в -1, либо в +1. Но тогда pushforward даёт точечную массу, а не распределение по двум точкам. Решения нет. Причина: отображение T - жёсткая структура, масса не делится.

**Релаксация Канторовича (1942)**: вместо отображения T искать совместное распределение π на X × Y с маргиналами μ и ν. Задача: min_π ∫∫ c(x,y) dπ(x,y) при условии, что маргиналы π по x равны μ, по y равны ν. Это уже **линейная программа** - всегда разрешимая. Отображение T соответствует π, сосредоточенному на графике T. Канторович разрешает массе «размазываться».

Для гладких распределений и квадратичной стоимости **теорема Бренье** гарантирует: оптимальный план Канторовича сосредоточен на графике некоторого отображения T. Монж и Канторович дают одинаковый ответ - но Канторович всегда определён. Именно поэтому весь современный вычислительный OT строится на постановке Канторовича.

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

Минимальная стоимость транспорта из задачи Канторовича при стоимости c(x,y) = ||x-y||^p даёт **расстояние Васерштейна** (Wasserstein distance): W_p(μ, ν) = (inf_π ∫∫ ||x-y||^p dπ(x,y))^(1/p). Это настоящая метрика на пространстве вероятностных мер: симметрична, удовлетворяет неравенству треугольника, равна нулю тогда и только тогда, когда μ = ν.

**Почему Wasserstein лучше KL для ML**: KL(μ || ν) = +∞, если support μ не содержится в support ν. На ранних этапах обучения GAN распределение генератора и реальное почти не пересекаются - KL даёт бесконечность или NaN, градиент пропадает. Wasserstein определён всегда и даёт гладкий ненулевой градиент даже для непересекающихся распределений. Это и был ключевой прорыв WGAN (Arjovsky 2017).

**OT в продакшн ML**: WGAN (Arjovsky 2017) - стабильный loss для генеративных моделей через Wasserstein-1. Flow Matching (Lipman 2022) - основа Stable Diffusion 3, Meta MovieGen, обучается в 5-10 раз быстрее классической диффузии. Domain adaptation через OT-DA (Courty-Flamary) - перенос модели между госпиталями, сенсорами, производственными линиями. Везде, где есть два распределения и нужно их сравнить или совместить - первый вопрос: а не Wasserstein ли нужен?

Итог

• Задача Монжа: inf_T ∫ c(x, T(x)) dμ при T#μ = ν - минимизация стоимости переноса μ в ν через отображение T
• T#μ = ν (pushforward): если X ~ μ, то T(X) ~ ν. Это условие «правильности» генератора в WGAN
• Монж ломается: дискретные распределения, где масса не делится. Точечная масса не отображается в сумму двух дельт
• Релаксация Канторовича: план π вместо отображения T. Линейная программа - всегда разрешима
• Wasserstein W_p: метрика на пространстве мер. Определена даже для непересекающихся носителей - в отличие от KL
• Стоимость c(x,y) - часть постановки: квадратичная → карта Бренье, евклидова → Wasserstein-1, perceptual → OT в feature space

Куда дальше

Монж задал вопрос. Дальше - инструменты решения и приложения.

• Релаксация Канторовича — LP-задача, всегда разрешимая. База для всех вычислительных алгоритмов OT
• Алгоритм Sinkhorn — Энтропийная регуляризация: OT за O(n²) итераций, дифференцируемый end-to-end
• Теорема Бренье — Для квадратичной стоимости оптимальная T существует, единственна и есть градиент выпуклой функции

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

• В каких задачах команды сравниваются два распределения? Какая дивергенция используется и не нужен ли там Wasserstein?
• Если бы выбор loss в генеративной модели делался через «какую стоимость c я хочу минимизировать», что изменилось бы в архитектуре?
• Какие задачи в продакшне (drift detection, fairness, A/B) формально - это вопрос «насколько μ далеко от ν»?

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

• calc-26-divergence-theorem