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

Другая идея расстояния

KL из блока 4 сравнивает распределения поточечно: если носители не пересекаются, она бесконечна независимо от того, насколько далеко распределения друг от друга. Для генеративных моделей это плохо: две почти правильные модели, промахнувшиеся в разные стороны, неразличимы.

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

$$W_p^p(\mu,\nu) = \min_{\htmlData{k=plan}{\gamma \in \Pi(\mu,\nu)}} \int \htmlData{k=cost}{\|x - y\|^p}\, d\gamma(x,y)$$

План $\gamma$ — это совместное распределение, маргиналы которого равны $\mu$ и $\nu$: сколько массы из точки $x$ уехало в точку $y$. Задача Монжа требовала детерминированного отображения; Канторович разрешил дробить массу, и от этого задача стала линейной, а значит решаемой.

Три факта, которые стоит знать

В одномерном случае задача решается сортировкой. Оптимальный план — сопоставить $k$-ю по порядку точку одной выборки с $k$-й другой. Проверено перебором всех $720$ перестановок на двух выборках по шесть точек: сортировка даёт $21.0890802768$, полный перебор — то же число.

Между гауссианами есть замкнутая форма. В одномерном случае

$W_2^2 = (\mu_1 - \mu_2)^2 + (\sigma_1 - \sigma_2)^2$

распределения	$W_2$
$\mathcal{N}(0,1)$ и $\mathcal{N}(3,1)$	$3.000$
$\mathcal{N}(0,1)$ и $\mathcal{N}(0,4)$	$1.000$
$\mathcal{N}(1, 0.25)$ и $\mathcal{N}(-1, 2.25)$	$2.236$

Вторая строка — то, чего KL не умеет выразить так же просто: два распределения с общим средним и разной шириной отстоят на конечное расстояние, и оно равно разности стандартных отклонений.

Метрика видит расстояние, а не пересечение. Для непересекающихся носителей KL равна бесконечности, а $W_2$ — расстоянию между ними. Именно поэтому Вассерштейн появился в GAN и почему он естественен для потоков: он измеряет перемещение, а потоки перемещением и занимаются.

Формулировка Бенаму–Бренье: транспорт как поток

Вот связь, ради которой урок стоит в этой ветке. Расстояние $W_2$ имеет динамическую формулировку:

$W_2^2(\mu,\nu) = \min_{v} \int_0^1\!\!\int \|v(x,t)\|^2\, p_t(x)\, dx\, dt$

при условии, что поле $v$ переносит $\mu$ в $\nu$. То есть $W_2$ — это минимальная кинетическая энергия потока, переводящего одно распределение в другое.

Отсюда сразу два следствия:

1. Оптимальный поток движется по прямым с постоянной скоростью. Из всех способов проехать из точки в точку за единицу времени минимум $\int\|v\|^2dt$ даёт равномерное прямолинейное движение — это неравенство Коши–Буняковского (блок 1, урок 050), а не свойство транспорта.
2. Цель flow matching и цель OT — разные. Flow matching берёт случайные пары $(x_0, x_1)$; оптимальный транспорт выбирает пары так, чтобы суммарная стоимость была минимальна. Первое проще, второе даёт прямее.

Minibatch OT: как это используют

Практический приём из урока 090, теперь с объяснением. Вместо случайного сопоставления шума и данных внутри батча решают маленькую задачу транспорта: батч на батч, венгерский алгоритм или Синкхорн. Пары перестают пересекаться, усреднение искажает меньше, маргинальное поле выпрямляется.

способ пар	стоимость	прямизна
случайно	нулевая	как есть
minibatch OT	$O(B^3)$ или Синкхорн	заметно лучше
rectified flow	переобучение	лучше всего, но дороже

Оговорка, которую стоит держать: OT внутри батча — не глобальный OT. При размере батча $B$ решается задача на $B$ точках, а не на всём наборе данных, и с ростом $B$ приближение улучшается. Это компромисс, а не решение.

Посмотрите, что даёт прямизна для сэмплера: при четырёх шагах прямой путь проходится точно, а кривой — срезается.

прямые путикривые пути

шагов

4

длина пути

2.83

прямое расстояние

2.83

кривизна

×1

ошибка ломаной

1.6e-16

Путь совпадает с прямой: минимум кинетической энергии по Бенаму–Бренье достигается ровно на равномерном прямолинейном движении.

Чего оптимальный транспорт не делает

Стоит закрыть популярное ожидание. Знание $W_2$ не даёт генеративной модели: расстояние — это число, а нужна выборка. И решение задачи транспорта между шумом и данными в полной постановке столь же дорого, как сама генерация, — при $n$ точках это $O(n^3)$ и требует всех данных сразу.

Практическая роль OT в этой ветке скромнее и точнее: он объясняет, почему прямые пути хороши (минимум энергии), и даёт дешёвое приближение внутри батча. Не более того — и этого достаточно.

Итог

• $W_p$ измеряет стоимость перевозки массы и остаётся конечной при непересекающихся носителях.
• В одном измерении задача решается сортировкой; между гауссианами есть замкнутая форма.
• Бенаму–Бренье переписывает $W_2$ как минимум кинетической энергии потока — отсюда прямые пути.
• Flow matching со случайными парами не решает задачу OT; minibatch OT приближает её и выпрямляет поле.
• Само по себе расстояние генеративной модели не даёт: полезны формулировка и приближение, а не число.