Теория вероятностей
Байесовские сети
Диагностическая система ICU в больнице предсказывает сепсис по 80 переменным. Хранить полное совместное распределение требует $2^{80}$ чисел. Байесовская сеть со структурой причинно-следственных связей хранит те же 80 условных вероятностей $P(X_i | \text{родители})$ - экспоненциальное сжатие при сохранении полной вероятностной семантики.
- Наивный байес для спам-фильтрации: предполагает условную независимость слов при данном ярлыке. Несмотря на наивность предположения, показывает конкурентоспособную точность и остаётся стандартом в Gmail.
- Вариационный вывод (VI) в VAE и тематическом моделировании (LDA): минимизация KL между вариационным и истинным апостериорным - байесовская сеть определяет структуру зависимостей.
- Причинный вывод (Pearl's do-calculus): интервенционное распределение $P(Y | do(X=x))$ вычисляется через байесовскую сеть как структурную причинную модель. Используется в медицине и экономике для оценки причинных эффектов.
Цели урока
- Читать байесовскую сеть и записывать факторизацию совместного распределения через условные вероятности
- Применять критерий d-разделения для проверки условной независимости
- Выполнять точный вывод алгоритмом belief propagation на деревьях
Предварительные знания
- Условная вероятность и теорема Байеса
- Совместные распределения и маргинализация
- Теория графов: ориентированные ациклические графы (DAG)
Факторизация и d-разделение
Байесовская сеть - DAG, где узлы - случайные величины, рёбра - причинные связи. Совместное распределение: $P(X_1, \ldots, X_n) = \prod_{i=1}^n P(X_i | \text{Pa}(X_i))$, где $\text{Pa}(X_i)$ - родители $X_i$ в DAG. Это представление корректно (нормировано) благодаря структуре DAG. D-разделение: $X \perp Y | Z$ в распределении, если $Z$ d-разделяет $X$ и $Y$ в графе. Критерий d-разделения проверяет блокировку всех путей между $X$ и $Y$ при условии $Z$.
Belief propagation на дереве: точный алгоритм инференса за $O(n \cdot \max_i |\text{dom}(X_i)|^2)$. Сообщение $\mu_{X_i \to X_j}(x_j)$ передаётся от листьев к корню и обратно. Маргинальное $P(X_i) \propto \prod_{j \in N(i)} \mu_{X_j \to X_i}(x_i)$. На графах с циклами используют loopy BP - не гарантирует сходимость, но работает на практике (TrueSkill, LDPC-коды).
Структурное обучение байесовской сети (поиск DAG по данным) NP-трудно в общем случае. Эвристики: PC-алгоритм использует условные тесты независимости, жадные алгоритмы минимизируют BIC/AIC. Важно: оценённая структура - не обязательно истинная причинная структура - лишь статистическая зависимость.
Джудеа Перл разработал байесовские сети в 1985-1988 годах, публикуя ключевые рез
Джудеа Перл разработал байесовские сети в 1985-1988 годах, публикуя ключевые результаты в книге «Probabilistic Reasoning in Intelligent Systems» (1988). В 2011 году он получил Тьюринговскую премию «за революционный вклад в теорию причинности и вероятностного рассуждения». Do-calculus (1995) сделал причинный вывод операциональным - алгоритмом, а не философским понятием.
Структура байесовской сети
В 1988 году Джудеа Перл показал, что DAG из 100 переменных может задать совместное распределение 2^100 размерности через всего ~10^4 параметров. Так байесовская сеть стала языком вероятностного вывода в медицинской диагностике, генетике и Bayesian deep learning.
В сети A → B → C переменные A и C независимы безусловно?
D-разделение
D-разделение читает условную независимость прямо из графа. Три базовых паттерна: цепь A → B → C блокируется кондиционированием на B; вилка A ← B → C тоже; коллайдер A → B ← C, наоборот, открывается при кондиционировании на B или его потомке.
В DAG A → B ← C утверждение «A и C независимы при условии B» - верно ли?
Belief propagation и обучение структуры
На дереве BP вычисляет все маргиналы за один прямой и один обратный проход - линейная сложность. Обучение параметров CPT при известной структуре сводится к подсчёту: P(Xi=k | Pa=j) = N(i,j,k)/N(i,j). Обучение структуры - NP-трудно; используют PC, GES или константные приоры BIC.
Параметры байесовской сети обучают по выборке. Что такое лапласово сглаживание?
Три паттерна d-разделения
Цепь $X \to Z \to Y$: при условии $Z$ переменные $X$ и $Y$ независимы - информация заблокирована. Вилка $X \leftarrow Z \to Y$: при условии $Z$ переменные $X$ и $Y$ независимы - общая причина устранена. Коллайдер $X \to Z \leftarrow Y$: без условия $Z$ переменные $X$ и $Y$ независимы; при условии $Z$ - зависимы (explaining away). Коллайдеры - источник контринтуитивных зависимостей в причинном выводе.
Итоги
- Байесовская сеть - DAG с факторизацией $P = \prod P(X_i|\text{Pa}(X_i))$, экспоненциально сжимающей совместное распределение.
- D-разделение проверяет условную независимость графово.
- Belief propagation на дереве - точный, на общих графах - приближённый.
- Наивный байес - вырожденный случай без рёбер между признаками.
Связь с другими темами
Скрытые марковские модели (HMM) - байесовская сеть с цепной структурой. Марковские цепи (prob-19) - специальный случай без скрытых переменных. VAE использует латентную байесовскую сеть $z \to x$ с непрерывными переменными и вариационным выводом вместо точного BP.
- Prob 19 — связан
Вопросы для размышления
- В коллайдере $X \to Z \leftarrow Y$: $X$ и $Y$ независимы без наблюдения $Z$, но зависимы при условии $Z$. Конкретный пример: $X$ = пожар, $Y$ = ограбление, $Z$ = сработала сигнализация. Почему знание, что сигнализация сработала, делает пожар и ограбление зависимыми?