Графические вероятностные модели

Язык, изображения, молекулы, социальные сети - всё это графы. Графические вероятностные модели - единый математический язык для рассуждений о зависимостях: от пикселей изображения до нейронов мозга.

• Коды с исправлением ошибок (LDPC): loopy BP достигает предела Шеннона в мобильных сетях 5G
• Геномика: Gaussian GGM строит сети генной экспрессии - кто регулирует кого
• Компьютерное зрение: CRF (conditional random fields) уточняет семантическую сегментацию

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

• Causal Inference

Марковские случайные сети: факторизация

В 1925 году Эрнст Изинг описал модель из 10^23 спинов, где каждый зависит только от соседей. Та же идея сегодня сегментирует изображения в DeepLab и кодирует данные в LDPC-кодах 5G: марковская случайная сеть факторизует совместное распределение по кликам графа.

**Связь с Deep Learning:** Conditional Random Fields (CRF) используются в NLP (named entity recognition) и Computer Vision (semantic segmentation). DeepLab добавляет Dense CRF поверх CNN для уточнения границ. Restricted Boltzmann Machine (RBM) - двудольный MRF, строительный блок глубоких сетей доверия (DBN). Diffusion models имеют связь с energy-based моделями через score matching.

Направленные vs ненаправленные графы

**Байесовская сеть (DAG):** P(X) = ∏ P(Xᵢ | Pa(Xᵢ)). Независимости через **d-separation**: Xᵢ ⊥ Xⱼ | Z если каждый путь между ними «заблокирован» Z. Три паттерна: chain (A→B→C: A⊥C|B), fork (A←B→C: A⊥C|B), collider (A→B←C: A⊥C, но A∦C|B!). **MRF:** независимости через глобальное марковское свойство: X_A ⊥ X_B | X_S если S разделяет A и B в графе. **Markov blanket** в DAG: родители + дети + со-родители.

**I-map и Perfect map:** граф G - I-map модели P если все независимости в G выполняются в P (граф может «игнорировать» некоторые независимости P). G - perfect map если независимости точно совпадают. Большинство реальных распределений не имеют perfect map - приходится выбирать между DAG и MRF. Алгоритмы обучения структуры (PC, FCI, GES) ищат G, который лучше всего приближает I-map для данных.

Loopy BP и Gaussian Graphical Models

**Belief Propagation (BP)** - точный вывод на деревьях через передачу сообщений: μ_{i→j}(xⱼ) = ∑_{xᵢ} ψᵢ(xᵢ) ψᵢⱼ(xᵢ,xⱼ) ∏_{k∈N(i)\j} μ_{k→i}(xᵢ). На деревьях - точен за O(n·|X|). **Loopy BP** - те же уравнения на произвольном графе. Аппроксимативен (не гарантирует сходимость), но хорошо работает на практике (коды с исправлением ошибок LDPC, турбо-коды). **Gaussian Graphical Model:** X ~ N(0,Σ), precision matrix Ω = Σ⁻¹ - нулевой элемент Ωᵢⱼ = 0 ↔ Xᵢ ⊥ Xⱼ | остальные.

**Loopy BP: когда работает/не работает?** Хорошо: разреженные графы с длинными циклами (LDPC коды дают почти Shannon-предел), слабые взаимодействия. Плохо: короткие циклы (треугольники), сильные зависимости. Альтернативы: expectation propagation (EP), variational message passing, tree-reweighted BP (TRW-BP). В Deep Learning loopy BP реализован через graph neural networks (message passing neural networks).

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

• MRF: P(X) = (1/Z) ∏_C ψ_C(X_C); вычисление Z - NP-hard для общего графа
• DAG: d-separation; collider A→B←C создаёт зависимость A∦C|B (explaining away)
• MRF: X_A ⊥ X_B | X_S при разделении S; Markov blanket = минимальный набор признаков
• Loopy BP: точен на деревьях, аппроксимативен на общем графе
• GGM: Ωᵢⱼ = 0 ↔ Xᵢ ⊥ Xⱼ | остальные; Graphical Lasso даёт sparse Ω

Графические модели и курс

Графические модели объединяют байесовскую статистику, теорию информации и алгоритмы. HMM - частный случай направленной цепи. CRF = обусловленный MRF. Вариационный вывод CAVI - применение BP-идей к VI.

• Вариационный байесовский вывод — CAVI - вариационный аналог BP; mean-field = полностью разобщённый граф
• Причинный вывод — DAG = каузальная графическая модель; d-separation определяет идентифицируемость эффектов

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

• Объясните, почему обусловливание на collider (B в A→B←C) создаёт зависимость между A и C. Приведите пример из жизни, где это ведёт к ошибочным выводам при анализе данных.
• Graphical Lasso минимизирует −log P(X|Ω) + λ‖Ω‖₁. Как выбор λ влияет на разреженность графа? Как это связано с торговлей между интерпретируемостью и точностью подгонки?
• Loopy BP используется в турбо-кодах для исправления ошибок. Почему он работает хорошо там, но ненадёжен для плотных графов с сильными взаимодействиями? Что делает цикловую структуру LDPC кодов особенной?

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

• ml-15-naive-bayes