d-분리

1. 개요

d-분리 d-separation
대상	방향 비순환 그래프(DAG) 위의 노드 집합 X, Y, Z
판정	Z 가 주어졌을 때 X–Y 사이 모든 경로가 막혔는가
건전성	d-분리 ⇒ 그 DAG 를 따르는 모든 분포에서 조건부 독립
완전성	d-연결 ⇒ 종속인 분포가 존재 (가이거·베르마·펄 1990)
계산량	$O(V+E)$ — 도달 가능성 탐색 한 번
제안	주데아 펄 (1980년대 중반)

그래프만 보고 조건부 독립을 읽는 기술. 확률표는 한 칸도 안 본다.

d-분리(d-separation, “d”는 directional)는 방향 비순환 그래프(DAG)에서 노드 집합 $Z$ 를 관측했을 때 집합 $X$ 와 $Y$ 사이의 모든 경로가 “막혀” 있는지를 그래프 구조만으로 판정하는 규칙이다. 막혀 있으면 그 그래프를 따라 인수분해되는 모든 확률분포에서 $X\perp Y\mid Z$ 가 성립한다. 1980년대 중반 주데아 펄이 베이지안 네트워크의 독립 구조를 읽는 도구로 정리했고, 지금은 인과 추론의 백도어 기준, 인과 발견의 PC 알고리즘, 공변량 선택까지 이 규칙 위에 서 있다.

사슬·분기·충돌이라는 세 기본 패턴과 그 직관은 베이지안 네트워크 문서의 「화살표 읽는 법」 절에 있다. 이 문서는 그 다음 이야기다. 규칙의 정확한 문장, 후손 조항이 왜 필요한지의 수치 확인, 기계가 판정하는 두 가지 알고리즘, 그리고 “그래프가 독립이라 했는데 데이터는 아니라고 한다”(또는 그 반대)가 언제 일어나는지.

2. 정의 — 경로가 언제 막히나

DAG $G$ 에서 두 노드 사이의 경로는 화살표 방향을 무시하고 이은 노드 열이다. 경로 위의 가운데 노드 $m$ 은 양옆 화살표 모양에 따라 셋 중 하나다.

• 사슬 $\cdot\to m\to\cdot$ 또는 분기 $\cdot\leftarrow m\to\cdot$ : $m\in Z$ 이면 막힌다.
• 충돌자 $\cdot\to m\leftarrow\cdot$ : $m$ 과 그 모든 후손이 $Z$ 밖에 있으면 막힌다.

경로 위에 막힌 노드가 하나라도 있으면 그 경로는 막혔다. 막히지 않은 경로를 활성 경로라 한다. $X$ 의 어느 노드와 $Y$ 의 어느 노드 사이에도 활성 경로가 없을 때 ”$Z$ 가 $X$ 와 $Y$ 를 d-분리한다”고 쓰고 $X\perp_G Y\mid Z$ 로 적는다.

두 가지 정리가 이 정의의 값어치를 만든다.

1. 건전성. $X\perp_G Y\mid Z$ 이면, $G$ 를 따라 $p(v)=\prod_i p(v_i\mid \mathrm{pa}_i)$ 로 인수분해되는 모든 분포에서 $X\perp Y\mid Z$ 이다(펄·베르마).
2. 완전성. 역으로 d-분리되지 않았으면, $G$ 를 따르면서 $X$ 와 $Y$ 가 $Z$ 조건부로 종속인 분포가 적어도 하나 존재한다(가이거·베르마·펄 1990). 즉 그래프만으로 얻을 수 있는 독립 정보는 d-분리가 전부다. 미크(1995)는 더 나아가 이산·가우스 모형에서 d-분리에 없는 독립을 갖는 매개변수가 측도 0 이라는 것을 보였다.

3. 후손 조항을 숫자로 확인

충돌자 자체가 아니라 그 후손만 관측해도 경로가 열린다는 조항이 가장 많이 틀리는 곳이다. 작은 예를 직접 계산했다.

$A, B$ 는 독립인 공정한 동전, $C=A\lor B$ (둘 중 하나라도 앞이면 1), $D$ 는 $C$ 를 확률 0.1로 뒤집어 읽은 센서값이다. 그래프는 $A\to C\leftarrow B$, $C\to D$.

조건	$P(A=1\mid\cdot)$
없음	0.500
$B=1$	0.500
$D=1$	0.643
$D=1,\ B=1$	0.500
$D=1,\ B=0$	0.900

$D$ 를 안 볼 때 $B$ 는 $A$ 에 대해 아무것도 알려 주지 않는다(첫 두 줄). 그런데 $D=1$ 을 보고 나면 $B$ 의 값에 따라 $A$ 의 확률이 0.5와 0.9 사이를 오간다. $C$ 는 한 번도 직접 관측하지 않았는데도 그 후손 $D$ 가 충돌자를 “반쯤 관측”한 효과를 내서 경로 $A\to C\leftarrow B$ 를 연 것이다. 이른바 해명 효과(explaining away)다. $B=1$ 이 이미 $D=1$ 을 설명하니 $A$ 는 사전확률로 돌아가고, $B=0$ 이면 $A$ 가 유일한 설명이라 0.9까지 오른다.

4. 손으로 판정해 보기

시뮬레이션 V&V 장면을 DAG로 그려 보자. 메시 품질 $M$ 과 시간 간격 $\Delta$ 가 수렴 여부 $C$ 를 함께 정하고($M\to C\leftarrow\Delta$), $C$ 가 결과 오차 $E$ 를 정하며($C\to E$), $M$ 은 계산 시간 $T$ 에도 영향을 준다($M\to T$).

질의	판정	이유
$M\perp\Delta$	독립	유일한 경로의 충돌자 $C$ 와 후손 $E$ 모두 미관측
$M\perp\Delta\mid E$	종속	충돌자 $C$ 의 후손 $E$ 관측 → 경로 열림
$T\perp\Delta$	독립	$T\leftarrow M\to C\leftarrow\Delta$ 가 $C$ 에서 막힘
$T\perp\Delta\mid C$	종속	$C$ 관측으로 충돌자 열림, 분기 $M$ 은 미관측이라 통과
$T\perp E$	종속	$T\leftarrow M\to C\to E$ 가 전부 열림
$T\perp E\mid M$	독립	분기 $M$ 관측으로 막힘

넷째 줄이 실무 함정이다. “수렴한 런만 골라서” 분석하면($C$ 로 조건화) 원래 무관하던 계산 시간과 시간 간격 사이에 가짜 상관이 생긴다. 통계학에서 말하는 선택 편향(collider bias)의 정체가 이것이다.¹

5. 기계가 판정하는 법

경로를 하나하나 열거하면 경로 수가 지수적으로 늘어난다. 실제 구현은 두 가지 선형 시간 방법 중 하나를 쓴다.

도달 가능성 탐색(베이즈 볼). 셰처터(1998)의 “베이즈 볼”이 가장 유명한 형태다. 공을 $X$ 에서 굴려 $Y$ 에 닿는지 본다. 상태는 (노드, 들어온 방향)의 쌍이다.

1. 먼저 $Z$ 와 $Z$ 의 조상 전부를 표시한다. 충돌자가 열리는 조건 “본인 또는 후손이 $Z$ 에 있다”는 “본인이 $Z$ 의 조상(자기 자신 포함)이다”와 같기 때문이다.
2. 자식 쪽에서 올라온 공은 $m\notin Z$ 이면 부모·자식 모두로 퍼진다(사슬·분기 통과).
3. 부모 쪽에서 내려온 공은 $m\notin Z$ 이면 자식으로만 계속 가고, $m$ 이 1단계에서 표시된 노드면 부모 쪽으로도 튕긴다(충돌자 열림).

각 (노드, 방향) 쌍을 한 번씩만 방문하므로 $O(V+E)$ 이다. 공이 닿은 노드 집합이 곧 ”$Z$ 조건부로 $X$ 와 d-연결된 노드 전부”이니, 질의 하나가 아니라 한 번에 모든 $Y$ 를 답한다.

도덕화 조상 그래프. 로리첸 등(1990)의 동치 판정이다. (1) $X\cup Y\cup Z$ 와 그 조상만 남기고 나머지를 지운다. (2) 같은 자식을 둔 부모끼리 선을 잇는다(도덕화, moralization). (3) 화살표를 지워 무방향 그래프로 만든다. (4) 그 그래프에서 $Z$ 를 지웠을 때 $X$ 와 $Y$ 가 끊기면 d-분리다. 마르코프 확률장의 분리 판정으로 문제를 넘기는 셈이고, 접합 트리 알고리즘이 첫 단계에서 도덕화를 하는 것도 같은 이유다. 1단계에서 조상만 남기는 게 핵심이다. 그래프 전체를 도덕화하면 관측 안 된 충돌자의 부모끼리도 이어져 버려 독립을 놓친다.

6. 그래프와 데이터가 어긋날 때

충실성 위반. 건전성 덕에 “그래프가 독립이라면 데이터도 독립”은 늘 맞지만, 역은 아니다. $A, B$ 를 공정한 동전, $C=A\oplus B$ (배타적 논리합)로 두면 그래프 $A\to C\leftarrow B$ 에서 $A$ 와 $C$ 는 화살표로 바로 이어져 있는데도 $P(C=1\mid A)=1/2$ 로 주변 독립이다. 이처럼 매개변수가 정확히 상쇄돼 그래프에 없는 독립이 생기는 분포를 비충실(unfaithful)하다고 한다. 미크의 결과대로 일반적인 매개변수에서는 측도 0 이지만, 대칭성이 있는 공학 시스템(완벽하게 균형 잡힌 피드백, 설계상 상쇄)에서는 측도 0 이 실제로 나온다. 데이터에서 독립성 검정으로 그래프를 복원하는 인과 발견 알고리즘은 충실성을 전제로 하므로 이런 곳에서 틀린다.²

마르코프 동치. 서로 다른 DAG가 정확히 같은 d-분리 집합을 줄 수 있다. 베르마·펄(1990)에 따르면 두 DAG는 골격(방향 뺀 연결)이 같고 v-구조(인접하지 않은 두 부모를 가진 충돌자)가 같을 때 그리고 그때만 동치다. $A\to B\to C$, $A\leftarrow B\leftarrow C$, $A\leftarrow B\to C$ 셋은 모두 $A\perp C\mid B$ 하나만 말하므로 관측 데이터로는 구별이 안 된다. $A\to B\leftarrow C$ 만 다르다. 데이터만으로 화살표 방향을 정할 수 있는 건 v-구조 근처뿐이라는 뜻이다.

가우스 모형에서의 의미. 선형 가우스 구조 방정식에서는 조건부 독립이 편상관 0 과 같다. d-분리는 정밀도 행렬(공분산의 역)의 해당 블록을 적절히 주변화했을 때 0 이 되는 패턴을 미리 알려 준다. 반대로 정밀도 행렬의 0 패턴만 보고 DAG를 그리면 위의 도덕화 간선 때문에 원래 없던 연결이 보인다.

7. 어디에 쓰나

• 백도어 기준. $X\to Y$ 의 인과 효과를 관측 데이터로 추정할 때, 공변량 집합 $Z$ 가 ”$X$ 로 들어오는 화살표로 시작하는 모든 경로”를 d-분리하고 $X$ 의 후손을 포함하지 않으면 $Z$ 로 보정하면 된다. 충돌자를 보정 변수에 넣으면 오히려 편향을 만든다는 경고도 d-분리에서 바로 나온다.
• 추론 국소화. 한 노드의 마르코프 담요가 나머지와 d-분리를 이루므로 깁스 표본추출·믿음 전파의 갱신이 국소 계산으로 끝난다.
• 모델 검증. 시뮬레이션 대리 모델이나 고장 진단 네트워크를 만든 뒤, 그래프가 함의하는 독립성 목록을 뽑아 실험·시뮬레이션 데이터로 하나씩 검정하는 것은 저렴하고 강력한 반증 테스트다. 하나라도 크게 깨지면 그래프에 빠진 간선이 있다.³

8. 관련 문서

• 베이지안 네트워크 · 마르코프 확률장 · 접합 트리 알고리즘 · 믿음 전파
• 인과 추론 · 인과 발견 · 그레인저 인과성 · 조건부 독립
• 깁스 표본추출 · 마르코프 연쇄 몬테카를로 · 은닉 마르코프 모형

9. Footnotes

1. 고전 예시가 “유명 배우는 연기력과 외모가 반비례한다”는 속설이다. 둘 중 하나는 있어야 유명해지니, 유명인만 모아 놓으면($C$ 로 조건화) 독립이던 두 특성 사이에 음의 상관이 생긴다. 논문 리뷰에서 “수렴한 케이스만 그렸습니다”가 나오면 이 각주를 떠올리자. ↩

2. 충실성 위반의 공학판 예가 완벽한 피드포워드 보상이다. 외란이 출력에 주는 직접 효과를 보상기가 정확히 상쇄하면, 외란과 출력은 화살표로 이어져 있는데도 데이터상으로는 무상관이다. 제어 엔지니어가 잘하면 잘할수록 인과 발견 알고리즘은 헷갈린다. ↩

3. R 의 dagitty 패키지가 그래프에서 함의 독립 목록을 뽑고 데이터로 검정하는 기능을 제공한다. 그래프를 그리는 순간 반증 가능한 예측 목록이 생긴다는 점이 이 방법의 매력이다 — 수렴은 신에게 맡겨도 독립성은 검정할 수 있다. ↩