Регуляризованный OT: алгоритм Синкхорна

Цели урока

• Понять, как энтропийный штраф превращает LP в строго выпуклую задачу с аналитической формой решения
• Реализовать алгоритм Синкхорна и разбираться в его сходимости при разных ε
• Использовать двойственные потенциалы для численно устойчивых вычислений

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

• Задача оптимального транспорта Канторовича (LP-формулировка)
• Двойственность в линейном программировании
• Условия оптимальности KKT

• Канторович и LP-формулировка OT
• Алгоритм Синкхорна: базовый вариант

2013 год. NeurIPS. Один постер с формулой e^{-C/ε} запустил цепную реакцию: Sinkhorn появился в диффузионных моделях, WGAN, flow matching, sequence alignment. Трюк, который в статистической физике знали 70 лет, оказался ключом к масштабируемому OT.

• Stable Diffusion 3 использует Flow Matching с Sinkhorn-coupled батчами: 512 изображений за проход, геодезические траектории вместо случайных
• Google Brain: выравнивание эмбеддингов при дистилляции моделей - Sinkhorn находит оптимальные пары учитель/ученик
• Scanpy (single-cell RNA): оптимальный транспорт между временными точками клеточной дифференциации - 50 000 клеток за секунды
• WGAN-GP в синтезе медицинских изображений: Sinkhorn как differentiable Wasserstein loss для обучения диагностических GANs

От телефонных сетей к диффузионным моделям

Ричард Синкхорн и Пол Кнопп в 1967 году доказали сходимость чередующихся нормировок матриц - без всякой связи с транспортом, просто как результат по стохастическим матрицам. Задача Шрёдингера 1931 года ставилась физиком для описания диффузии частиц - никакой оптимизации. Марко Кутюри в 2013 году соединил их в одном NeurIPS paper. Вычислительная сложность упала с O(n³) до O(n²/ε²). За 10 лет метод проник в каждую значимую архитектуру генеративных моделей.

Энтропийная регуляризация: от O(n³) к O(n²)

2013 год, лаборатория ENSAE. Марко Кутюри опубликовал статью в NeurIPS - и оптимальный транспорт перестал быть вычислительно недосягаемым для ML. До этого: решить задачу OT для 10 000 точек - это часы на сервере. После: секунды на GPU. Один трюк с энтропией изменил всё.

Матрица K = exp(-C/ε) - ключевой объект. При ε→0 она концентрируется у оптимальных пар (i,j), при ε→∞ - равномерна. Параметр ε регулирует баланс между точностью и сглаженностью плана.

Структура P* = diag(u)·K·diag(v) - не случайность. Это точно форма матрицы Гиббса из статистической физики. Задача Синкхорна - нормировка матрицы Гиббса до заданных маргиналей. Физика и транспорт оказались одним и тем же.

Алгоритм Синкхорна: чередующиеся нормировки

Решение нелинейной системы u ⊙ (Kv) = a, v ⊙ (K⊤u) = b выглядит пугающе. Но если зафиксировать v и решить для u - это просто деление. Потом зафиксировать u и решить для v. И так чередовать. Это весь алгоритм Синкхорна.

Log-domain Sinkhorn: при малом ε матрица K имеет численные нули (underflow). Решение - работать в log-domain: log(u), log(v), log(K). Тогда умножения становятся сложениями, а exp/log применяются только к небольшим числам.

Двойственность и потенциалы Синкхорна

У каждой задачи оптимизации есть двойственная. У регуляризованного OT - тоже. Двойственные переменные f, g называются потенциалами Синкхорна. Связь с прямым алгоритмом: u = exp(f/ε), v = exp(g/ε). Это не просто замена - потенциалы имеют физический смысл цен.

При ε < 0.01 и больших C_{ij} матрица K = exp(-C/ε) может содержать нули из-за underflow float64. Всегда проверяйте min(K) и переходите на log-domain Sinkhorn при подозрительных результатах.

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

Энтропийная регуляризация - фундамент для масштабируемого OT. Без неё невозможны WGAN, flow matching и дистилляция на больших датасетах. Следующий шаг: мост Шрёдингера (ot-13) как непрерывная версия, и flow matching (ot-25) как применение к генеративным моделям.

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

Итоги

• Энтропийный штраф -εH(P) превращает LP в строго выпуклую задачу с единственным решением вида P* = diag(u)·K·diag(v)
• Алгоритм Синкхорна: чередование u = a/(Kv) и v = b/(K⊤u) - каждая итерация O(n²), сходимость линейная
• Параметр ε регулирует точность: при ε→0 - точный OT, при ε→∞ - независимое произведение мер a⊗b
• Log-domain вычисления обязательны при малом ε для численной устойчивости

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

• Почему log-domain Sinkhorn численно устойчивее прямого при ε < 0.01?
• Как выбрать ε на практике: какие факторы влияют на баланс точности и скорости сходимости?
• Каким образом Sinkhorn-дивергенция W_ε(μ,ν) - 0.5·W_ε(μ,μ) - 0.5·W_ε(ν,ν) устраняет смещение регуляризации?

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

• ot-04-sinkhorn — базовый алгоритм Синкхорна - фундамент текущего урока
• ot-13-schrodinger — задача Шрёдингера - другая интерпретация того же алгоритма
• ot-24-entropic-reg — углублённая энтропийная регуляризация и мост Шрёдингера
• ot-25-flow-matching — Flow Matching строится на регуляризованном OT