d-разделение¶

d-разделение — это критерий условной независимости множеств вершин в ориентированном ациклическом графе (DAG), используемый в теории вероятностных графических моделей, в частности в байесовских сетях. Понятие введено для определения, являются ли два набора переменных независимыми при условии третьего набора, исходя из структуры графа. d-разделение лежит в основе алгоритмов вывода и обучения в байесовских сетях, позволяя упрощать вычисления за счёт выявления условных независимостей.

¶Определение

Пусть задан ориентированный ациклический граф \( G = (V, E) \), где \( V \) — множество вершин (случайных переменных), а \( E \) — множество направленных рёбер. Для трёх непересекающихся множеств вершин \( X, Y, Z \subseteq V \) говорят, что \( X \) и \( Y \) d-разделены множеством \( Z \), если любой путь (не обязательно направленный) между любой вершиной из \( X \) и любой вершиной из \( Y \) блокируется вершинами из \( Z \). Путь считается блокированным, если хотя бы одна вершина на нём удовлетворяет одному из следующих условий:

1. Последовательное соединение (цепь): на пути есть вершина \( v \in Z \), в которую входит ребро, и из которой выходит ребро (структура \( \rightarrow v \rightarrow \) или \( \leftarrow v \leftarrow \)).
2. Расходящееся соединение (вилка): на пути есть вершина \( v \in Z \), из которой выходят два ребра (структура \( v \rightarrow ... \)).
3. Сходящееся соединение (коллайдер): на пути есть вершина \( v \notin Z \), в которую входят два ребра (структура \( \rightarrow v \leftarrow \)), и при этом ни сама \( v \), ни её потомки не входят в \( Z \).

Если все пути между \( X \) и \( Y \) блокированы \( Z \), то \( X \) и \( Y \) d-разделены при условии \( Z \). В противном случае они d-связаны.

¶Интуитивное объяснение

d-разделение моделирует потоки информации в графе. В байесовских сетях направленные рёбра интерпретируются как причинно-следственные связи. Информация (влияние) может распространяться по графу, но блокируется при определённых условиях:

• В цепи (\( A \rightarrow B \rightarrow C \)) знание \( B \) блокирует поток информации между \( A \) и \( C \). Например, если \( B \) — это «дождь», \( A \) — «облачность», \( C \) — «мокрый асфальт», то при известном факте дождя облачность и мокрый асфальт становятся независимыми.
• В вилке (\( A \leftarrow B \rightarrow C \)) общая причина \( B \) делает \( A \) и \( C \) зависимыми, но при условии \( B \) они становятся независимыми. Например, \( B \) — «возраст», \( A \) — «рост», \( C \) — «словарный запас»: при фиксированном возрасте рост и словарный запас не связаны.
• В коллайдере (\( A \rightarrow B \leftarrow C \)) две причины \( A \) и \( C \) влияют на общее следствие \( B \). В отсутствие информации о \( B \) (или его потомках) \( A \) и \( C \) независимы. Однако при условии \( B \) они становятся зависимыми. Например, \( A \) — «талант», \( C \) — «усердие», \( B \) — «успех». Без знания об успехе талант и усердие независимы, но если известно, что человек успешен, то знание о таланте делает усердие менее вероятным (и наоборот) — это явление называется объяснительным устранением (explaining away).

¶Формальное определение

Пусть \( G \) — DAG. Для пути \( \pi \) между вершинами \( x \) и \( y \) и множества \( Z \) вершина \( v \) на \( \pi \) называется блокирующей, если выполняется одно из условий:

1. \( v \in Z \) и \( v \) не является коллайдером на \( \pi \) (т.е. рёбра на \( \pi \) не сходятся в \( v \)).
2. \( v \notin Z \) и \( v \) является коллайдером на \( \pi \), и при этом ни один потомок \( v \) (включая саму \( v \)) не входит в \( Z \).

Путь \( \pi \) блокирован \( Z \), если на нём есть хотя бы одна блокирующая вершина. Множества \( X \) и \( Y \) d-разделены \( Z \) (\( X \perp_G Y \mid Z \)), если все пути между любой \( x \in X \) и любой \( y \in Y \) блокированы \( Z \).

¶Свойства

• Симметричность: d-разделение симметрично: если \( X \) d-разделено с \( Y \) при условии \( Z \), то \( Y \) d-разделено с \( X \) при условии \( Z \).
• Монотонность: если \( X \) и \( Y \) d-разделены \( Z \), то они остаются d-разделенными при добавлении вершин в \( Z \) (при условии, что \( Z \) не содержит коллайдеров, открывающих пути).
• Связь с условной независимостью: в байесовской сети, представляющей совместное распределение \( P \), d-разделение \( X \perp_G Y \mid Z \) влечёт условную независимость \( X \perp_P Y \mid Z \). Обратное, вообще говоря, неверно: могут существовать условные независимости, не отражённые в графе (например, из-за параметрических особенностей). Однако для строго положительных распределений (по теореме о факторизации) d-разделение эквивалентно условной независимости.

¶Примеры

¶Пример 1: Цепь

Граф: \( A \rightarrow B \rightarrow C \). Множество \( Z = \{B\} \). Путь \( A-B-C \) блокирован вершиной \( B \in Z \) (последовательное соединение). Следовательно, \( A \) и \( C \) d-разделены при условии \( B \). Если \( Z = \varnothing \), то \( A \) и \( C \) d-связаны (путь не блокирован).

¶Пример 2: Вилка

Граф: \( A \leftarrow B \rightarrow C \). Множество \( Z = \{B\} \). Путь \( A-B-C \) блокирован вершиной \( B \in Z \) (расходящееся соединение). \( A \) и \( C \) d-разделены при условии \( B \). Без условия (\( Z = \varnothing \)) они d-связаны.

¶Пример 3: Коллайдер

Граф: \( A \rightarrow B \leftarrow C \). Множество \( Z = \varnothing \). Путь \( A-B-C \) блокирован, так как \( B \) — коллайдер и не входит в \( Z \). \( A \) и \( C \) d-разделены. Если \( Z = \{B\} \), то \( B \in Z \) и является коллайдером — условие блокировки не выполняется (коллайдер блокирует только если не в \( Z \)), поэтому путь становится неблокированным, и \( A \) и \( C \) d-связаны при условии \( B \).

¶Пример 4: Сложный граф

Рассмотрим граф: \( A \rightarrow B \rightarrow C \leftarrow D \). Пусть \( X = \{A\}, Y = \{D\}, Z = \{C\} \). Путь \( A-B-C-D \): вершина \( C \) — коллайдер, она входит в \( Z \), поэтому условие блокировки коллайдера не выполняется (коллайдер в \( Z \) не блокирует). Других блокирующих вершин нет. Следовательно, \( A \) и \( D \) d-связаны при условии \( C \). Если \( Z = \varnothing \), то \( C \) — коллайдер, не входящий в \( Z \), путь блокирован, \( A \) и \( D \) d-разделены.

¶Применение

• Байесовские сети: d-разделение используется для проверки условных независимостей, что позволяет упростить вычисление совместных распределений и апостериорных вероятностей. Например, при построении графа сети эксперт может задать структуру, а затем проверить, какие переменные становятся независимыми при наблюдении других.
• Алгоритмы вывода: алгоритмы, такие как устранение переменных (variable elimination) и выборка по Гиббсу, используют d-разделение для определения, какие переменные можно исключить из рассмотрения при заданных наблюдениях.
• Обучение структуры: при восстановлении графа по данным критерии d-разделения помогают тестировать гипотезы о наличии или отсутствии рёбер, сравнивая условные независимости, выводимые из графа, с наблюдаемыми в данных.
• Причинный вывод: в рамках структурных причинных моделей (SCM) d-разделение используется для идентификации причинных эффектов и определения, какие переменные являются инструментальными.

¶Связь с другими понятиями

• Марковское остовное дерево: d-разделение в DAG тесно связано с понятием разделения в неориентированных графах (U-разделение). Для морального графа (moral graph) байесовской сети d-разделение эквивалентно U-разделению.
• Критерий d-отделимости: в некоторых источниках d-разделение называют d-отделимостью (d-separation).
• Минимальное разделяющее множество: множество \( Z \), которое d-разделяет \( X \) и \( Y \), называется разделяющим множеством. Минимальное по включению разделяющее множество называется минимальным разделяющим множеством.

¶Критика и ограничения

• d-разделение не учитывает параметрические особенности распределения. Возможны случаи, когда граф указывает на d-связь, но в силу конкретных значений параметров (например, нулевых коэффициентов) условная независимость всё же выполняется. Такие ситуации называются параметрическими независимостями.
• Для графов с циклами (например, в циклических причинных моделях) понятие d-разделения не определено напрямую; требуются модификации, такие как d-разделение для смешанных графов.
• Проверка d-разделения для больших графов может быть вычислительно затратной, хотя существуют алгоритмы с полиномиальной сложностью (например, на основе поиска в глубину).

¶Интересные факты

• Термин «d-разделение» был введён Джудией Перл в 1985 году в контексте байесовских сетей и причинного вывода. Буква «d» означает «directional» (направленный).
• В 2000 году Перл получил премию Тьюринга, в том числе за вклад в развитие вероятностных графических моделей и понятия d-разделения.
• d-разделение лежит в основе алгоритма PC (Peter-Clark) для восстановления структуры байесовских сетей по данным.

¶Источники

• Pearl, J. (1985). «A Constraint Propagation Approach to Probabilistic Reasoning». Proceedings of the 1st Conference on Uncertainty in Artificial Intelligence.
• Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann.
• Koller, D., Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. MIT Press.
• Spirtes, P., Glymour, C., Scheines, R. (2000). Causation, Prediction, and Search. MIT Press.