Оптимальный транспорт: дешевле всего перевезти одну кучу в другую

Есть склады с песком и стройки, которым он нужен. Сколько песка с какого склада на какую стройку везти, чтобы суммарный путь был минимален? Этот наивный вопрос оказался одной из глубочайших задач математики — и метрикой, которой современный ИИ измеряет расстояние между распределениями.

Задача и её цена

Пусть у источников лежит масса a_i, а стокам нужна масса b_j, и перевозка единицы из i в j стоит C_{ij} (например, квадрат расстояния). План перевозки — матрица P_{ij}: сколько массы едет из i в j. Нужно минимизировать суммарную стоимость \min_P \sum_{ij} P_{ij} C_{ij}, \qquad \sum_j P_{ij}=a_i,\quad \sum_i P_{ij}=b_j,\quad P_{ij}\ge 0. Это линейная программа: целевая функция и ограничения линейны. Её минимум — расстояние Вассерштейна между двумя распределениями массы.

Синкхорн вместо симплекса

Решать ЛП симплексом дорого. Если добавить к задаче чуть энтропии (-\varepsilon H(P)), решение становится гладким и считается удивительно просто — алгоритмом Синкхорна: берём матрицу K_{ij}=e^{-C_{ij}/\varepsilon} и поочерёдно нормируем её строки и столбцы, пока суммы не сойдутся к нужным a и b. Десяток матричных умножений — и план готов.

Параметр \varepsilon управляет резкостью. При \varepsilon\to 0 план стремится к жёсткому ЛП-оптимуму: каждый источник почти целиком обслуживает один сток. При больших \varepsilon масса размазывается по многим стокам, а стоимость растёт.

Тяни точки и крути \varepsilon: видно, как план перестраивается, а толщина линий показывает, сколько массы едет по каждому маршруту.

Зачем это ИИ

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

  • Wasserstein GAN — обучает генератор, минимизируя W_1 между настоящим и сгенерированным распределениями; градиент ведёт себя гораздо лучше, чем у обычного GAN.
  • Сравнение и выравнивание — гистограмм цветов, эмбеддингов слов между языками, одноклеточных данных в биологии.
  • Диффузия и flow matching — в некоторых постановках flow matching использует траектории, связанные с оптимальным транспортом, чтобы переносить шум в данные. Диффузионные модели тоже преобразуют шум в данные, но их стандартное описание идёт через обратный процесс зашумления и score, а не обязательно через оптимальные транспортные траектории.

Связи

  • Шум превращает оптимизацию в генерацию (§ Ланжевен): другой взгляд на генерацию — через сэмплирование, а не через транспорт.
  • k-средних (§ k-средних): присвоение точек центроидам — частный жёсткий случай транспортной задачи.
  • Метод наименьших квадратов (§ МНК): пример того, как поэлементная метрика теряет геометрию, которую сохраняет Вассерштейн.
Наверх