Оптимальный транспорт
Энтропийная регуляризация
Цели урока
- Понять связь задачи Шрёдингера 1931 года с регуляризованным OT и алгоритмом Синкхорна
- Объяснить скорость сходимости и численные трудности при малом ε
- Применять epsilon-scaling и log-domain вычисления для устойчивых результатов
Предварительные знания
- Алгоритм Синкхорна и энтропийная регуляризация
- KL-дивергенция и информационная геометрия
- Численные методы: log-sum-exp
Шрёдингер в 1931 году: 'Если ансамбль броуновских частиц начинается из µ и приходит в ν - какой путь наиболее вероятен?' Вопрос физика. Ответ нашли только в 2013-м - и он оказался алгоритмом Синкхорна. Математика задаётся сама за 82 года до того, как её применят.
- Waddington OT (Science 2019): восстановление траекторий клеточной дифференциации по 65 000 single-cell профилей через мост Шрёдингера
- Stable Diffusion 3: Flow Matching с OT-coupled батчами использует энтропийный OT для прямых траекторий генерации
- ProteinMPNN: мост Шрёдингера для генерации белковых последовательностей, совместимых с заданной 3D-структурой
- Оптимальное управление диффузионными процессами: планирование траекторий молекулярной динамики через мост Шрёдингера
От квантовой механики к machine learning
Эрвин Шрёдингер сформулировал задачу о броуновском мосте в 1931 году как мысленный эксперимент о статистической механике. Ришар Форте в 1940 году решил уравнение Шрёдингера через скалярные потенциалы - те же u и v алгоритма Синкхорна. Связь с энтропийным OT формализована Leonard (2014) и Peyre et al. (2019). Сегодня мост Шрёдингера - основа нового класса генеративных моделей (Bridge Matching, I2SB), превосходящих диффузию на задачах переноса между двумя произвольными распределениями.
Задача Шрёдингера: физика за алгоритмом
1931 год, Эрвин Шрёдингер задаётся вопросом: если броуновские частицы стартуют из µ и приходят в ν - какой путь наиболее вероятен? Это не задача оптимизации в привычном смысле. Но в 2013 году выяснилось: задача Шрёдингера и регуляризованный OT - одно и то же. Алгоритм Синкхорна решает задачу 1931 года.
Мост Шрёдингера - это не просто интерполяция. Это наиболее вероятная эволюция ансамбля частиц, связывающая µ и ν. В применениях к генеративным моделям: это прямые, 'физически реалистичные' траектории от шума к данным.
Мост Шрёдингера в биологии клетки
Отслеживание клеточной дифференциации по single-cell RNA-seq данным (Waddington OT, Schiebinger et al. Science 2019): клетки измеряются в разные моменты времени, нужно восстановить траектории дифференциации. Мост Шрёдингера даёт наиболее вероятные траектории, совместимые с наблюдаемыми распределениями. 65 000 клеток, 20 000 генов.
В чём физический смысл параметра ε в задаче Шрёдингера?
В статистической физике ε ~ kT: при T→0 система принимает конфигурацию минимальной энергии (OT-план), при T→∞ - полностью случайную. В OT ε → 0 даёт детерминированный транспорт, ε → ∞ - равномерное смешивание.
Скорость сходимости и устойчивость Синкхорна
Синкхорн сходится. Но как быстро? И насколько устойчив при малых ε? Ответ: линейная сходимость с коэффициентом e^{-λ(C)/ε}, где λ(C) - зависит от матрицы стоимостей. При ε → 0 сходимость замедляется экспоненциально. Именно здесь log-domain и epsilon-scaling спасают практические вычисления.
Зачем использовать epsilon-scaling при малых ε вместо запуска Синкхорна сразу с целевым ε?
Коэффициент сходимости ρ = exp(-λ/ε) → 1 при ε→0: нужно экспоненциально много итераций. Warm start от большего ε даёт хорошее начальное приближение и резко сокращает число шагов.
Применения энтропийного OT: скейлинг до миллионов
Синкхорн работает для задач размера n=100. Но что делать с n=100 000 точек? Или с батчами изображений в обучении генеративных моделей? Два подхода: mini-batch OT (упрощение с bias) и stochastic Sinkhorn (онлайн версия). Оба жертвуют точностью ради масштаба.
В Flow Matching (Stable Diffusion 3) coupling осуществляется через mini-batch OT с батчами 512-1024 изображений. Exact OT на таком масштабе нереален, но mini-batch approximation достаточна для прямых траекторий.
Mini-batch OT смещён: E[W_ε(µ_batch, ν_batch)] ≠ W_ε(µ, ν). Для оценки качества модели используйте полный W_ε на тестовой выборке. Для обучения mini-batch достаточен - градиенты несмещены в ожидании.
Почему mini-batch Sinkhorn даёт смещённую оценку W_ε, но всё равно применяется для обучения?
В SGD нужны несмещённые оценки градиента, а не несмещённая оценка функции потерь. E[∇_θ W_ε(P_θ_batch, P_data_batch)] = ∇_θ W_ε(P_θ, P_data) - это выполнено при случайном сэмплинге.
Куда ведёт тема
Энтропийная регуляризация через мост Шрёдингера открывает путь к Bridge Matching (ot-25) и стохастическому управлению. Несбалансированный OT (ot-29) обобщает энтропийную регуляризацию на меры с разными полными массами.
- Optimal Transport — Связанная тема
Итоги
- Задача Шрёдингера = KL-проекция на пространство планов с маргиналями µ, ν = регуляризованный OT
- Сходимость Синкхорна линейная с коэффициентом exp(-λ/ε): при малом ε нужны тысячи итераций
- Log-domain Sinkhorn и epsilon-scaling - обязательные оптимизации для малого ε
- Mini-batch OT смещён как оценка W_ε, но несмещён как оценка градиента - пригоден для обучения
Вопросы для размышления
- Что физически означает мост Шрёдингера для ансамбля частиц - и почему это 'наиболее вероятная' траектория?
- При каком ε Синкхорн сойдётся за 50 итераций для типичной матрицы C из [0,1]^{n×n}?
- Как идея моста Шрёдингера используется в I2SB (Image-to-Image Schrodinger Bridge) для трансформации изображений?
Связанные уроки
- ot-21 — базовый алгоритм Синкхорна - основа этого урока
- ot-13-schrodinger — мост Шрёдингера - непрерывная версия энтропийного OT
- ot-25-flow-matching — Flow Matching использует геодезические энтропийного OT
- ot-15-unbalanced — несбалансированный OT обобщает энтропийную регуляризацию