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

Несбалансированный OT и биология

Stable Diffusion генерирует изображения через flow matching - это optimal transport в непрерывном времени. Waddington OT восстановил полное «генеалогическое дерево» репрограммирования клеток из 65000 одиночных измерений. Несбалансированный OT - инструмент, где классика не работает: когда масса не сохраняется, когда клетки делятся и умирают, когда предложения разной длины.

**Waddington OT (Cell 2019):** 65000 клеток, 40 временных точек, восстановление траекторий iPSC репрограммирования. Наибольшее OT исследование в биологии.
**MOSCOT (2023):** Theislab Helmholtz Munich - multi-omics alignment через OT. Сопоставление RNA+protein+ATAC measurements из разных клеток.
**PyTorch Geometric + POT:** Sinkhorn Divergence как differentiable loss для 3D point clouds - standard в shape analysis, molecule generation.

Когда массы не совпадают: клетки умирают и делятся

Stable Diffusion генерирует 10M+ изображений в день через flow matching - это OT в непрерывном времени. Классический OT требует равной суммарной массы. Несбалансированный OT снимает ограничение через KL soft marginal constraints: клетки делятся и умирают, предложения разной длины - всё это несбалансированный перенос.

Классический OT: min_{P≥0} ⟨C,P⟩ при P·1 = μ, Pᵀ·1 = ν (жёсткие граничные условия). Несбалансированный OT: min_{P≥0} ⟨C,P⟩ + τ·KL(P·1|μ) + τ·KL(Pᵀ·1|ν). Параметр τ > 0 контролирует «жёсткость»: при τ→∞ возвращается к классическому OT.

**Несбалансированный OT:** UOT(μ,ν) = min_{P≥0} [Σᵢⱼ Cᵢⱼ·Pᵢⱼ + τ·KL(Pᵢ₊|μᵢ) + τ·KL(P₊ⱼ|νⱼ)] где KL(a|b) = Σᵢ aᵢ·log(aᵢ/bᵢ) - aᵢ + bᵢ **Сдвоенная (Sinkhorn) версия с регуляризацией ε:** P = diag(u)·exp(-C/ε)·diag(v) Обновления (обобщённый Sinkhorn): uᵢ ← (μᵢ/aᵢ)^(τ/(τ+ε)) где aᵢ = Σⱼ Kᵢⱼ·vⱼ vⱼ ← (νⱼ/bⱼ)^(τ/(τ+ε)) где bⱼ = Σᵢ Kᵢⱼ·uᵢ При τ→∞: (·)^(τ/(τ+ε)) → (·)^1 - обычный Sinkhorn. При τ=ε: (·)^0.5 - мягкое ограничение.

В single-cell RNA sequencing клетки в начале эксперимента (t=0) и в конце (t=T) - разные клетки. Невозможно отследить конкретную клетку. Несбалансированный OT восстанавливает **вероятностные траектории**: с какой вероятностью клетка типа A в t=0 стала типом B в t=T? Учёт пролиферации (деления) и апоптоза (гибели) через несбалансированность.

Параметр τ в несбалансированном OT: при τ→0 и τ→∞ что происходит с планом транспорта?

τ штрафует отклонение от marginals через KL-дивергенцию с весом 1/τ. При τ→0 штраф → ∞, constraints становятся жёсткими (классический OT). При τ→∞ штраф → 0, масса свободно создаётся/уничтожается.

Sinkhorn Divergence: честная метрика без bias

Regularized OT с параметром ε имеет известный недостаток: W_ε(μ,μ) > 0. Распределение не имеет нулевого расстояния до самого себя! Это **entropic bias** и это ломает использование как loss функции в ML. **Sinkhorn Divergence** исправляет это.

**Sinkhorn Divergence:** S_ε(μ,ν) = OT_ε(μ,ν) - (1/2)·OT_ε(μ,μ) - (1/2)·OT_ε(ν,ν) Свойства: - S_ε(μ,μ) = 0 (нет bias) - S_ε(μ,ν) ≥ 0 (неотрицательна) - S_ε(μ,ν) = 0 ⟺ μ = ν - Дифференцируема по μ - можно backprop! Между W₁ (Wasserstein без регуляризации) и MMD (Maximum Mean Discrepancy). При ε→0: S_ε → W (классический Wasserstein) При ε→∞: S_ε → MMD с kernel k(x,y) = -C(x,y) Применение: geom_loss в Python, loss для точечных облаков в 3D, GAN training.

Почему OT_ε(μ,μ) > 0 является проблемой, и как Sinkhorn Divergence исправляет это?

Регуляризация ε·H(P) минимизирует энтропийный член даже при μ=ν. Sinkhorn Divergence вычитает self-terms и получает симметричную функцию, равную нулю на диагонали.

scRNA-seq: optimal transport для клеточных траекторий

**Waddington OT (Schiebinger et al., Cell 2019):** репрограммирование клеток отслеживается через OT. 65000 одиночных клеток на 40 временных точках. Несбалансированный OT восстановил полное клеточное «генеалогическое дерево» репрограммирования фибробластов в iPSC. Это принципиально новый метод в биологии развития.

**Применения OT в биологии и chemistry:** - Waddington OT: клеточные траектории в single-cell data (Schiebinger 2019) - MOSCOT: multi-omics single-cell OT, Theislab (Helmholtz Munich, 2023) - FoldingDiff: генерация структур белков через OT flow matching - Drug discovery: OT для alignment молекулярных fingerprints

Почему для клеточных траекторий в scRNA-seq используется несбалансированный OT?

Классический OT требует сохранения массы: каждая клетка t₀ должна отображаться в клетку t₁. Но клетки делятся (1→2), дифференцируются или апоптозируют - несбалансированный OT моделирует это через penalties.

Ключевые идеи

**Несбалансированный OT:** min_P [⟨C,P⟩ + τ·KL(row marginals | μ) + τ·KL(col marginals | ν)]. Параметр τ: мягкость ограничений.
**Обобщённый Sinkhorn:** u ← (μ/Kv)^ρ, v ← (ν/Kᵀu)^ρ, где ρ = τ/(τ+ε). При τ→∞: ρ→1, классический Sinkhorn.
**Sinkhorn Divergence:** S_ε = OT_ε(μ,ν) - OT_ε(μ,μ)/2 - OT_ε(ν,ν)/2. Убирает entropic bias, S_ε(μ,μ)=0. Дифференцируема.
**scRNA-seq:** несбалансированный OT восстанавливает клеточные траектории с учётом пролиферации/апоптоза.
**τ→0:** только транспорт без уважения к marginals; **τ→∞:** строгие marginals, классический OT.

Связанные темы

Несбалансированный OT в контексте теории:

Sinkhorn алгоритм — Несбалансированный Sinkhorn - прямое обобщение классического
Gromov-Wasserstein — Следующий урок: OT между пространствами разной природы

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

ot-04-sinkhorn — Sinkhorn алгоритм обобщается на несбалансированный случай
ot-13-schrodinger — Оба используют KL regularization, разные смыслы
ot-14-gradient-flows — Unbalanced OT = gradient flow по обобщённой метрике

Когда массы не совпадают: клетки умирают и делятся

Параметр τ в несбалансированном OT: при τ→0 и τ→∞ что происходит с планом транспорта?

Sinkhorn Divergence: честная метрика без bias

Почему OT_ε(μ,μ) > 0 является проблемой, и как Sinkhorn Divergence исправляет это?

scRNA-seq: optimal transport для клеточных траекторий

Почему для клеточных траекторий в scRNA-seq используется несбалансированный OT?

Ключевые идеи

**Несбалансированный OT:** min_P [⟨C,P⟩ + τ·KL(row marginals | μ) + τ·KL(col marginals | ν)]. Параметр τ: мягкость ограничений.

**Обобщённый Sinkhorn:** u ← (μ/Kv)^ρ, v ← (ν/Kᵀu)^ρ, где ρ = τ/(τ+ε). При τ→∞: ρ→1, классический Sinkhorn.

**Sinkhorn Divergence:** S_ε = OT_ε(μ,ν) - OT_ε(μ,μ)/2 - OT_ε(ν,ν)/2. Убирает entropic bias, S_ε(μ,μ)=0. Дифференцируема.

**scRNA-seq:** несбалансированный OT восстанавливает клеточные траектории с учётом пролиферации/апоптоза.

**τ→0:** только транспорт без уважения к marginals; **τ→∞:** строгие marginals, классический OT.

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

ot-04-sinkhorn — Sinkhorn алгоритм обобщается на несбалансированный случай

ot-13-schrodinger — Оба используют KL regularization, разные смыслы

ot-14-gradient-flows — Unbalanced OT = gradient flow по обобщённой метрике