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

Дискретный OT и приложения

Цели урока

Понять LP-структуру дискретного OT и почему оптимальный план разрежен
Применить 1D OT как алгоритм сортировки для цветопередачи и других задач
Разобраться в алгоритме MUSE: чередование OT и Procrustes

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

Задача Канторовича как LP
Алгоритм Синкхорна для регуляризованного OT
Базовые знания линейного программирования и двойственности

110 языков. 50 000 слов. 82% точности перевода - без единого параллельного предложения. MUSE (Facebook AI Research, 2018) сделал это через дискретный OT. Тот же алгоритм, что решает задачу о перевозке угля, выровнял словари русского и суахили.

MUSE (Meta): cross-lingual word embeddings для 110 языков - дискретный OT между векторными пространствами слов
Перенос стиля изображений: OT между цветовыми гистограммами - одна сортировка и ранговое сопоставление
Few-shot learning с EMD (Earth Mover's Distance) matching - W₂ между признаками query и support
Graph neural network matching: OT находит оптимальное соответствие между узлами двух молекулярных графов

От задачи назначений к MUSE

Harold Kuhn в 1955 опубликовал венгерский алгоритм - O(n³) решение задачи назначений (OT с равными весами). Morton Klein в 1967 описал сетевой симплекс для транспортных задач. Эти алгоритмы десятилетиями применялись в логистике. Прорыв в NLP: MUSE (Conneau et al., 2018) превратил словари в дискретные меры и применил Sinkhorn для их выравнивания. Дискретный OT перешёл из операционных исследований в state-of-the-art NLP за одну публикацию.

Дискретный OT: структура и алгоритмы

Facebook AI Research (FAIR) опубликовали MUSE в 2018: выравнивание словарей между 110 языками без единого параллельного примера. Математика - дискретный OT между пространствами слов. Точность перевода без параллельных данных - 82%. Транспортный план для 50 000 слов строился за 3 секунды. Это и есть дискретный OT в продакшене.

Как вычисляется оптимальный транспорт в одномерном случае?

В 1D оптимальный план - монотонное ранговое отображение. Это сводится к: отсортируй обе меры, сопоставь i-й элемент источника с i-м целевым. W_p^p = среднее p-х степеней разностей.

Цветопередача и выравнивание словарей

Два классических применения дискретного OT - полные противоположности по шкале 'эстетика vs инженерия'. Перенос цвета: один алгоритм, две строки кода, мгновенный результат. Выравнивание словарей: сложная итерационная процедура, 110 языков, state-of-the-art без параллельных данных. Одна математика.

В MUSE выравнивание словарей - итерационный процесс: 1) Строим OT-план для текущего W; 2) Обновляем W через SVD (Procrustes); 3) Повторяем до сходимости. Конвергенция обычно за 5-10 итераций для близких языков.

OT в мета-обучении

Prototypical Networks в few-shot learning классифицируют через ближайший прототип. OT-вариант (EMD Matching, Li et al. 2019): вместо евклидова расстояния до прототипа - W₂ между распределением признаков query и support. На miniImageNet: точность 5-way 5-shot растёт с 65% до 72% - за счёт более богатого сравнения распределений.

Почему алгоритм MUSE чередует OT и обновление матрицы выравнивания W?

Совместная задача по (W, P) - bilevel: нелинейная и некоммутативная. Чередующаяся оптимизация - стандарт: каждый блок решается в closed form, процедура монотонно убывает по общей цели.

OT в обучении с учителем и без учителя

Дискретный OT проник в задачи, где и не ожидали его увидеть. Сопоставление датасетов (dataset distillation), attention через transport, graph matching - везде, где нужно сопоставить два набора объектов оптимально. Каждый раз один и тот же LP под новым именем.

NetworkX и scipy.sparse.csgraph реализуют венгерский алгоритм через linear_sum_assignment. Для n < 500 - точное решение за миллисекунды. Для n > 1000 используйте Sinkhorn: регуляризованный OT с ε=0.01-0.1.

Dataset distillation с OT

Dataset Distillation (Wang et al. 2018, улучшение через OT): задача - сжать 60 000 изображений CIFAR до 10. OT между синтетическим дистиллятом и реальным датасетом - сигнал для обучения. Sinkhorm distance как differentiable loss позволяет backprop через сопоставление. Результат: 10 синтетических изображений воспроизводят 90% accuracy модели.

Чем Sinkhorn Transformer отличается от стандартного Transformer с точки зрения attention?

Softmax нормирует строки матрицы Q·Kᵀ - это одна итерация Синкхорна. Двусторонняя нормировка (строки и столбцы) - полный Синкхорн - даёт doubly stochastic матрицу и симметричное сопоставление токенов.

Куда ведёт тема

Дискретный OT - рабочая лошадка задач сопоставления. Следующий шаг: энтропийная регуляризация (ot-24) как мост между LP и мостом Шрёдингера, и барицентры Вассерштейна (ot-09) как усреднение мер через OT-планы.

Optimal Transport — Связанная тема

Итоги

Дискретный OT - LP с n² переменными; оптимальный план разрежен: не более n+m-1 ненулевых элементов
1D OT: сортировка и ранговое сопоставление - O(n log n) без LP, применяется в переносе цвета
MUSE: OT + Procrustes итерация для выравнивания словарей без параллельных данных
Sinkhorn Transformer: двойная нормировка attention матрицы = полный алгоритм Синкхорна

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

Почему оптимальный дискретный план имеет не более n+m-1 ненулевых элементов - и что это означает геометрически?
Как перенос цвета через OT отличается от простого совмещения статистик (mean/std matching)?
В каких случаях Sinkhorn attention превзойдёт стандартный softmax attention, а в каких - нет?

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

ot-02-kantorovich — LP-формулировка - основа дискретного OT
ot-12-comp-ot — вычислительные аспекты OT детально
ot-09-barycenters — барицентры Вассерштейна строятся на дискретном OT
ot-08-domain-adaptation — выравнивание доменов через дискретный транспортный план