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

Мульти-маргинальный OT

Цели урока

  • Понять задачу MOT и почему вычислительная сложность растёт как n^k
  • Связать SCI-предел DFT с N-маргинальным OT и кулоновской стоимостью
  • Увидеть барицентр Вассерштейна как частный случай MOT

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

  • Классический двух-маргинальный OT
  • Алгоритм Синкхорна и его чередующиеся нормировки
  • Основы квантовой химии: DFT, электронная плотность
  • Канторович и LP-формулировка
  • Барицентры Вассерштейна

AlphaFold 3 (2024) предсказывает структуры белков с точностью 0.8 ангстрем. Часть секрета - MOT: взаимодействие N атомов нельзя описать парными потенциалами, нужен N-маргинальный транспорт. Задача оптимального транспорта нашла применение в квантовой химии.

  • AlphaFold 3: DFT-ограничения через MOT для предсказания 3D структур белков и малых молекул с атомарной точностью
  • Model merging: Wasserstein barycenter для слияния LoRA адаптеров без потери специализации
  • Waddington OT (Science 2019): MOT для траекторий клеточной дифференциации по k временным точкам
  • Crowd simulation: MOT для координации движения толпы с k участниками без столкновений

От квантовой механики к DFT и обратно

DFT (теория функционала плотности) существует с 1964 года (Kohn-Sham). Обменно-корреляционный функционал E_xc - ключевая и нерешённая часть. В 2013 году Cotaр, Friesecke и Klueppelberg показали: SCI-предел E_xc = N-маргинальный OT. Это открыло новое направление: применение вычислительных методов OT к квантовой химии. Параллельно: Gangbo и Swiech (1998) исследовали MOT с кулоновской стоимостью теоретически. К 2024 году нейросетевые функционалы с MOT-ограничениями превзошли классические DFT приближения.

Мульти-маргинальный OT: постановка и сложность

Классический OT: два облака точек, найти оптимальное соответствие. MOT: k облаков одновременно. Кажется, небольшое обобщение. Но k маргиналей означают k-мерный тензор - вычислительная сложность растёт экспоненциально. Зачем нужна такая монструозность? DFT для N-электронных систем, барицентры Вассерштейна, временные ряды - задачи, где два маргинала принципиально недостаточны.

Почему MOT с k>2 маргиналями экспоненциально сложнее двух-маргинального OT?

Двух-маргинальный план - матрица n×n (n² элементов). k-маргинальный план - тензор n^k элементов. Для k=3 и n=100: 10^6 vs 10^4. Для k=20 и n=100: 10^40. Декомпозиция стоимости обходит это.

DFT как N-маргинальный OT: квантовая химия

Теория функционала плотности (DFT) - основа квантово-химических расчётов. Проблема: обменно-корреляционный функционал E_xc[ρ] неизвестен точно. Cotaр и Friesecke в 2013 году показали: E_xc в пределе сильной связи = N-маргинальный OT с кулоновской стоимостью. AlphaFold 3 использовал это в 2024 году.

AlphaFold 3 (DeepMind, 2024) использует нейросетевую аппроксимацию DFT функционалов, включая SCI-предел через MOT. Точность предсказания 3D структур: 0.8 ангстрем для белков, 0.4 для нуклеиновых кислот.

Neural network DFT с MOT

DeepMind MNDO (2023): нейросеть аппроксимирует E_xc[ρ] через лёгкое включение MOT-ограничений в loss function. Молекулы до 100 атомов: точность сравнима с DFT B3LYP, скорость - в 1000x быстрее. Ключ: SCI-предел как регуляризатор для нейросетевого функционала.

Почему N-маргинальный MOT используется для E_xc[ρ], если кулоновское взаимодействие попарное?

Хотя стоимость суммируется по парам, N-электронная волновая функция - функция на R^{3N}. Редукция к парным маргиналям теряет многочастичные корреляции. Именно их и описывает MOT с полным тензором γ.

Барицентры Вассерштейна как MOT

Как усреднить два распределения? Не покомпонентно (получится что-то непохожее на оба). Барицентр Вассерштейна - усреднение через оптимальный транспорт. И это частный случай MOT: k источников, один общий 'центр'. Применения: стиль-трансфер изображений, усреднение языковых моделей.

Усреднение языковых моделей через OT

Model merging (слияние нейросетей): FusionBench и аналоги усредняют параметры нейросетей. Проблема: наивное усреднение весов LoRA адаптеров теряет специализацию. OT-баricenter: выравниваем нейроны перед усреднением через Wasserstein barycenter. Эффект: merged model сохраняет 85% performance обоих источников против 70% при наивном усреднении.

Почему барицентр Вассерштейна лучше покомпонентного усреднения мер?

Пример: два кластера на R. (µ_1 + µ_2)/2 - усредняет плотности, размывая разрывы. W-барицентр интерполирует позиции атомов через транспорт - кластеры остаются кластерами, только сдвигаются.

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

MOT - обобщение OT на k маргиналей. Специальные случаи: мартингальный OT (ot-27) с финансовыми ограничениями, причинный OT (ot-28) с каузальными ограничениями, несбалансированный OT (ot-29) с разными полными массами.

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

Итоги

  • MOT: минимизируем k-частичную стоимость по тензорам γ на X^k с k маргиналями
  • Сложность O(n^k): при декомпозиции стоимости по парам снижается до O(k²n²)
  • DFT в SCI-пределе = N-маргинальный OT с кулоновской стоимостью sum_{i<j} 1/|x_i - x_j|
  • Барицентр Вассерштейна = MOT с k+1 маргиналями и свободным носителем центра

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

  • Почему N-частичные корреляции электронов нельзя восстановить из парных маргинальных планов?
  • Как epsilon-scaling ускоряет Sinkhorn для MOT - и есть ли дополнительные сложности по сравнению с двух-маргинальным случаем?
  • В чём практическое преимущество Wasserstein barycenter перед наивным усреднением для задачи merging языковых моделей?

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

  • ot-09-barycenters — барицентры Вассерштейна - частный случай MOT
  • ot-27 — мартингальный OT - MOT с финансовыми ограничениями
  • ot-02-kantorovich — классический двух-маргинальный OT - базовый случай MOT
Мульти-маргинальный OT

0

1

Войти