d-separation

정의

d-separation(directional separation)은 DAG에서 두 변수 집합이 세 번째 집합으로 조건부 독립인지를 그래프 구조만으로 판정하는 기준(graphical criterion)이다.

형식적 정의:

DAG $G$ 에서 $Z$ 가 $X$ 와 $Y$ 를 d-separate 한다는 것은, $X$ 와 $Y$ 사이의 모든 경로(path)가 $Z$ 로 차단(blocked)된다는 뜻이며 다음과 같이 표기한다.

$X \perp_G Y \mid Z$

경로 차단 규칙

세 가지 기본 구조

Structure	Name	Blocked by $Z$ ?
$A \rightarrow B \rightarrow C$	Chain	$B \in Z$ 이면 blocked
$A \leftarrow B \rightarrow C$	Fork	$B \in Z$ 이면 blocked
$A \rightarrow B \leftarrow C$	Collider	$B \notin Z$ and $De(B) \cap Z = \emptyset$ 이면 blocked

차단 규칙 요약

경로 $\pi$ 가 $Z$ 로 차단되려면 다음 두 조건을 만족해야 한다.

비충돌자(non-collider, chain 또는 fork)의 중간 노드가 $Z$ 에 포함된다.
충돌자(collider)의 중간 노드와 그 후손(descendant)이 $Z$ 에 포함되지 않는다.

직관적 이해

d-separation은 “정보 흐름의 차단”으로 읽으면 직관이 선다.

Fork (Common Cause):
    A ← B → C

    - B가 주어지면: A, C 독립 (confounding 제거)
    - B가 주어지지 않으면: A, C 연관 (via B)

Chain (Mediation):
    A → B → C

    - B가 주어지면: A, C 독립 (mediator blocked)
    - B가 주어지지 않으면: A, C 연관 (causal path)

Collider (Common Effect):
    A → B ← C

    - B가 주어지지 않으면: A, C 독립 (default blocked)
    - B가 주어지면: A, C 연관! (collider bias)

d-separation 알고리즘

입력

DAG $G$
집합 $X$ , $Y$ , $Z$

절차

For each path π between X and Y:
    blocked = False
    For each node B on path π (excluding endpoints):
        If B is a non-collider on π:
            If B ∈ Z:
                blocked = True
                break
        Else (B is a collider on π):
            If B ∉ Z and De(B) ∩ Z = ∅:
                blocked = True
                break

    If not blocked:
        return "X and Y are NOT d-separated by Z"

return "X and Y are d-separated by Z"

충실성 가정

마르코프 성질(Markov property)

분포 $P$ 가 DAG $G$ 에 대해 마르코프(Markov)라면, 그래프의 d-separation이 확률적 독립을 함의한다. $X \perp_G Y \mid Z \implies X \perp_P Y \mid Z$

충실성(faithfulness)

분포 $P$ 가 DAG $G$ 에 충실(faithful)하다면, 확률적 독립이 그래프의 d-separation을 함의한다. $X \perp_P Y \mid Z \implies X \perp_G Y \mid Z$

둘이 결합하면(perfect map) 그래프 구조와 확률적 독립이 정확히 대응한다. $X \perp_P Y \mid Z \iff X \perp_G Y \mid Z$

예시

예시 1: 단순 chain

X → Y → Z

$X \perp_G Z \mid Y$ ? Yes (Y blocks the chain)
$X \perp_G Z$ ? No (path open)

예시 2: Fork (교란)

    C
   ↙ ↘
  X   Y

$X \perp_G Y \mid C$ ? Yes (C blocks the fork)
$X \perp_G Y$ ? No (confounding path open)

예시 3: Collider

X → C ← Y

$X \perp_G Y$ ? Yes (collider blocks by default)
$X \perp_G Y \mid C$ ? No (conditioning opens collider)

예시 4: 복잡한 그래프

    A
   ↙ ↘
  B   C
   ↘ ↗
    D

$A \perp_G D$ ? Check all paths:
- $A \rightarrow B \rightarrow D$ : Open
- Not d-separated
$A \perp_G D \mid B$ ?
- $A \rightarrow B \rightarrow D$ : Blocked (B ∈ Z)
- $A \rightarrow C \rightarrow D$ : Open
- Not d-separated
$A \perp_G D \mid \{B, C\}$ ?
- $A \rightarrow B \rightarrow D$ : Blocked
- $A \rightarrow C \rightarrow D$ : Blocked
- d-separated!

MAG (Maximal Ancestral Graph)
PAG (Partial Ancestral Graph)

σ-separation (순환 그래프)

순환 그래프(cyclic graph)를 위한 확장이다.

강연결 성분(Strongly Connected Components, SCC)을 고려한다.
d-separation으로 축약(reduce)할 수 있다.

참고 문헌

Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems
Pearl, J. (2009). Causality
yaoSurveyCausalInference2021 - 인과 발견(causal discovery)에서의 d-separation

정의