Оптимальный транспорт
Несбалансированный оптимальный транспорт
Цели урока
- Понять, как KL-штраф в UOT заменяет жёсткие маргинальные ограничения
- Объяснить робастность UOT к выбросам и применение для частичного транспорта
- Применять мягкий алгоритм Синкхорна для UOT с параметром τ
Предварительные знания
- Алгоритм Синкхорна для регуляризованного OT
- KL-дивергенция и её свойства
- Основы single-cell геномики (для биологических применений)
139 000 клеток мышиного эмбриона. 15 временных точек. Число клеток в каждой точке разное: одни делятся, другие умирают. Как сравнить временные точки через OT? Классический OT молчит. UOT: штрафуй за несоответствие маргиналей вместо жёсткого ограничения. Moscot восстановил полную карту клеточных судеб.
- Moscot (Nature Methods 2024): OT и UOT для траекторий клеточного развития - 139 000 клеток мышиного эмбриона
- Scanpy/POT: несбалансированный OT для сравнения scRNA-seq образцов разного размера
- Слабо надзорное domain adaptation: UOT для partial matching признаков при смещении домена
- Распределённые вычисления: UOT для балансировки рабочей нагрузки при 'потерянных' задачах
От сохранения массы к её релаксации
Классический OT предполагает сохранение массы - физически мотивированное, но ограничивающее. Первые работы по partial transport: Caffarelli и McCann (2010) для TV-регуляризованного случая. Чизат, Пейре и соавторы в 2018 году (SIAM J. Math. Analysis) предложили унифицированный фреймворк UOT с произвольными Φ-дивергенциями и доказали Gamma-сходимость. Scaling алгоритм для KL-случая: прямое обобщение Синкхорна с экспонентой τ/(τ+ε). Применение к scRNA-seq (Schiebinger et al. Cell 2019) дало новое дыхание теории.
UOT: когда маргинали не совпадают
Классический OT: масса сохраняется - всё что взяли из µ, доставили в ν. Но что если одна клетка делится на две? Или опухоль растёт? Или часть сигнала теряется при передаче? Несбалансированный OT разрешает 'создание' и 'уничтожение' массы, штрафуя отклонение маргиналей через KL-дивергенцию.
Что происходит с UOT при τ → ∞?
При τ→∞ бесконечный штраф за отклонение маргиналей → оптимальный план имеет точные маргинали. Это Gamma-сходимость UOT к OT.
Робастность UOT к выбросам и частичному транспорту
Один выброс в целевом распределении (точка далеко от остальных) заставляет OT 'тянуть' всю массу к нему - огромная транспортная стоимость. UOT игнорирует выбросы: их транспортировка дорогостоящая, алгоритм предпочитает заплатить штраф KL и оставить их непокрытыми. Это и есть partial transport.
Для сравнения single-cell датасетов разного размера используйте UOT с τ ≈ 1.0 и ε ≈ 0.01. Scanpy/POT: ot.unbalanced.sinkhorn_knopp_unbalanced(a, b, C, reg=0.01, reg_m=1.0). При τ < 0.1 результат нестабилен.
Почему UOT более робастен к выбросам чем сбалансированный OT?
OT: маргинальные ограничения жёсткие, выброс неизбежно получает транспортируемую к нему массу. UOT: маргинали мягкие, выброс 'игнорируется' за цену τ·KL(δ_outlier|ν).
UOT для single-cell биологии: анализ клеточных популяций
Single-cell RNA-seq (scRNA-seq) измеряет экспрессию генов в отдельных клетках. Сравнить два образца с разным числом клеток? Классический OT требует равных весов - нереально. UOT решает это напрямую: разные полные массы, частичный транспорт для клеток без аналогов. Scanpy реализует это через POT для 100 000+ клеток.
Moscot: OT для траекторий развития
Moscot (Lübeck et al. Nature Methods 2024): фреймворк для анализа клеточных судеб через OT и UOT. Датасеты: мышиный эмбриогенез (139 000 клеток), 15 временных точек, 100+ типов клеток. UOT обрабатывает 1) разные числа клеток в точках, 2) пролиферацию (масса увеличивается), 3) апоптоз (масса уменьшается). Результат: полная карта клеточных судеб за время развития эмбриона.
Почему UOT необходим для анализа scRNA-seq временных рядов, а не классический OT?
В эмбриогенезе T=0: 100 клеток → T=24h: 10 000 клеток. Классический OT несовместим с разными полными массами (µ ≠ ν по размеру). UOT разрешает это через KL-штрафы.
Куда ведёт тема
UOT замыкает серию обобщений OT в этом курсе. Практическое резюме: OT = основа, Sinkhorn = вычислимость, WGAN = deep learning, Flow Matching = генерация, MOT = k маргиналей, Martingale OT = финансы, Causal OT = временные процессы, UOT = разные массы.
- Optimal Transport — Связанная тема
Итоги
- UOT: маргинальные ограничения заменены штрафами τ·KL(π_1|µ) + τ·KL(π_2|ν); τ→∞ = OT
- Мягкие итерации Синкхорна: u = (a/(Kv))^α, α = τ/(τ+ε) < 1
- Робастность к выбросам: выброс не транспортируется, платим KL-штраф
- Применения: scRNA-seq (разные числа клеток), partial matching, выбросоустойчивые меры расстояния
Вопросы для размышления
- Как выбрать τ для конкретной задачи - и что означает 'слишком большой' и 'слишком маленький' τ?
- Почему TV-штраф (вместо KL) в UOT даёт точный partial transport с порогом - а KL нет?
- Как UOT обрабатывает пролиферацию клеток (масса растёт) vs апоптоз (масса уменьшается) - что происходит с τ·KL(π_1|µ)?
Связанные уроки
- ot-15-unbalanced — детальное рассмотрение UOT с разными расходящимися штрафами
- ot-21 — алгоритм Синкхорна - основа масштабирующего алгоритма UOT
- ot-24-entropic-reg — энтропийная регуляризация входит в UOT как двойной штраф