Оптимальный транспорт
Gromov-Wasserstein: OT между разными пространствами
Как выровнять word2vec пространства русского и английского языков без словаря переводов? Facebook MUSE (2018) сделал это через OT + GW: Wasserstein выровнял структуры, Procrustes нашёл отображение. Это позволило создать русско-английский словарь с нуля через геометрию языковых пространств. GW - инструмент для задач, где нет общей метрики.
- **Facebook MUSE:** cross-lingual alignment 30+ языков через GW/OT без билингвальных корпусов. Открытый код, 4000+ звёзд на GitHub.
- **Word Mover Distance:** semantic search в Elasticsearch, document similarity в production. Медленнее tf-idf, но значительно точнее для семантического поиска.
- **Grakel/PyTorch Geometric:** GW для graph kernels, молекулярного fingerprinting, protein structure alignment в drug discovery.
Gromov-Wasserstein: сопоставить структуры, не точки
MUSE (Facebook AI, 2018) выровнял embeddings 30 языков без параллельных корпусов, используя Gromov-Wasserstein расстояние. Вектор 'dog' (en) сопоставляется с 'собака' (ru) без общего пространства - выравниваются структуры попарных расстояний. Та же идея применяется в AlphaFold для сравнения 3D-структур белков.
Классический OT: сопоставить точки из X и Y через cost C(x,y). Требует: X и Y в одном пространстве или явный cross-space cost. GW: сопоставить структуры через **внутрипространственные** расстояния. Стоимость: насколько расстояния искажаются при отображении.
**Gromov-Wasserstein расстояние:** GW(μ,ν) = min_{P∈Π(μ,ν)} Σᵢⱼₖₗ L(dₓ(xᵢ,xₖ), d_Y(yⱼ,yₗ))·Pᵢⱼ·Pₖₗ где L(a,b) = (a-b)² (стандартный выбор) dₓ - метрика в пространстве X, d_Y - в Y **Смысл:** P «хорошее», если при отображении i→j и k→l сохраняется: dₓ(xᵢ,xₖ) ≈ d_Y(yⱼ,yₗ) **Нелинейная задача:** в отличие от классического OT, это квадратичная задача по P. Нет гарантии глобального минимума. **Fused GW (FGW):** λ·GW + (1-λ)·OT - комбинирует структурное и содержательное сравнение.
Почему Gromov-Wasserstein задача нелинейна, хотя классический OT линеен по P?
В классическом OT целевая функция ∑_{ij} C_{ij}P_{ij} линейна по P. В GW появляется P_{ij}P_{kl} - произведение двух элементов плана, что даёт квадратичную задачу. Frank-Wolfe линеаризует её итерационно.
Word Mover Distance и выравнивание языковых пространств
**Word Mover Distance (Kusner 2015):** расстояние между документами как OT между распределениями слов с cost = L2 в word2vec/GloVe пространстве. Превзошёл tf-idf и LDA в задачах text classification без обучения. Используется в semantic search и document retrieval.
**Выравнивание языковых пространств (MUSE, Facebook 2018):** Дано: word embeddings X (английский, n×d) и Y (русский, m×d), обученные раздельно. Цель: найти ортогональное отображение W: W·X ≈ Y для переводных пар. Алгоритм MUSE: 1. OT находит soft alignment между наиболее частыми словами 2. Прокрустово решение: W = argmin_{W^T W=I} ||WX_aligned - Y_aligned||² W = U·Vᵀ через SVD(Y_aligned·X_aligned^T) = U·S·Vᵀ 3. Итерировать: OT → Procrustes → OT → ... Результат: русско-английский словарь без билингвальных данных через GW/OT alignment.
Почему инициализация P₀ критически важна для сходимости MUSE (OT + Procrustes)?
OT+Procrustes - нелинейная чередующаяся оптимизация. При случайной P₀ можно сойтись к ложному выравниванию языковых пространств (напр., перепутать семантические кластеры).
Fused GW: граф matching и молекулярное сравнение
**Fused Gromov-Wasserstein (FGW)** объединяет структурное (GW) и содержательное (классический OT) сравнение. Формула: FGW = α·GW + (1-α)·OT. Для графов: структура через adjacency matrix расстояния, атрибуты вершин через признаки. Применение: молекулярный fingerprint, граф классификация, knowledge graph alignment.
POT (Python Optimal Transport) library содержит ot.gromov.gromov_wasserstein и ot.gromov.fused_gromov_wasserstein с эффективными реализациями. Используется в PyTorch Geometric для graph-level OT pooling и в chemoinformatics для molecular similarity.
В FGW = α·GW + (1-α)·OT, что происходит при α=0 и α=1?
α=0: FGW = OT - сравниваем только узловые признаки, граф-структура игнорируется. α=1: FGW = GW - сравниваем только расстояния внутри графов. Промежуточный α балансирует оба критерия.
Ключевые идеи
- **GW расстояние:** min_P Σᵢⱼₖₗ (d_X(i,k) - d_Y(j,l))²·Pᵢⱼ·Pₖₗ. Сохраняет внутренние расстояния при отображении. Квадратичная задача по P.
- **Алгоритм:** Frank-Wolfe / projected gradient. Каждый шаг линеаризуем GW -> linear OT -> Sinkhorn. Нет гарантии глобального минимума.
- **Word Mover Distance:** OT между bag-of-words с cost = L2 word2vec. Semantic distance без обучения.
- **MUSE alignment:** OT → Procrustes → OT → ... Выравнивание языковых embedding spaces без словаря.
- **Fused GW:** α·GW + (1-α)·OT для графов с атрибутами. Молекулы, knowledge graphs, social networks.
Связанные темы
Gromov-Wasserstein в контексте OT теории:
- Несбалансированный OT — Предыдущий урок: OT когда масса не совпадает
- OT в NLP и генерации — Следующий урок: применения в language models и generative AI
Связанные уроки
- ot-03-wasserstein — GW обобщает Wasserstein на разные metric spaces
- ot-10-gromov — Углублённый анализ и применения
- ot-15-unbalanced — Оба снимают ограничения классического OT