d 분리(D-separation)

조건부 독립(conditional independence) (tistory.com)

조건부 독립(conditional independence)

위 글에서 살펴본 방향성 그래프에서 조건부 독립 성질을 확장시켜 d 분리에 대해 알아보자.

 

일반적인 방향성 그래프를 가정해 보자. 이때 A, B, C는 서로 겹치지 않는 임의의 노드 집합이다. 주어진 방향성 비순환 그래프로부터 다음이 유추될 수 있는 지 알고싶다고 하자.

식1

이를 위해 A의 아무 노드로부터 B의 아무 노드로 향하는 모든 가능한 경로를 고려할 것이다. 이 때 만약 어떤 경로가 다음에 해당하는 노드를 포함하면 그 경로는 폐쇄(blocked)되었다고 표현한다.

1. 경로상의 모든 화살표가 어떤 노드에 대해 머리 대 꼬리 또는 꼬리 대 꼬리에 해당하며 해당 노드가 C집합에 속한다.
2. 경로상의 모든 화살표가 어떤 노드에 대해 머리 대 머리에 해당하며, 해당 노드와 그 노드의 자손들이 전부 C집합에 속하지 않는다.

위의 조건들은 뒤의 내용을 이해하는데 중요하니 확실히 이해하고 넘어가자.

 

만약 모든 경로들이 막혀 있으면 "A는 C에 의해 B로부터 d 분리 되어있다"고 한다. 그리고 그래프의 모든 변수에 대한 결합 분포는 식1을 만족한다.

 

이를 조금 더 쉽게 이해하기 위해 다음 그래프를 고려해 보자.

(a)그래프를 먼저 고려해보자. a부터 b로의 경로가 f에 의해서 막혀있지 않다. f는 꼬리 대 꼬리 노드에 해당하며 관측되지 않았기 때문이다(C집합에 속하지 않음, 조건 1번). 또한 e에 의해서도 막혀있지 않다. e는 머리 대 머리 노드에 해당하며 e의 자손이 집합 C에 속하기 때문이다(관측됨, 조건 2번). 따라서 이 그래프상에서 조건부 독립성은 성립하지 않는다.

 

(b)그래프를 고려해보자. a부터 b로의 경로가 f에 막혀이싿. f는 꼬리 대 꼬리 노드에 해당하며 해당 노드가 관측되었기 때문이다(조건 1번). 이는 e에 의해서도 막혀있다. e는 머리 대 머리 노드에 해당하며 해당 노드와 자손 노드가 관측되지 않았기 때문이다.

 

d 분리의 측면에서 작은 채워진 원으로 표시되어 있는 α 나 σ^2와 같은 결정적 매개변수들은 관측된 노드와 동일하게 작동한다. 하지만 이러한 노드들은 d 분리와 관련하여 아무런 역할도 하지 못하는 게, 이들과 연관된 주변 분포는 존재하지 않아 스스로 부모 노드를 가지지 못하며, 따라서 언제나 꼬리 대 꼬리 노드에 해당할 것이기 때문이다. d 분리의 조건은 a로부터 b로 가는 모든 경로가 막혀있어야 하는 것이므로 이러한 결정적 매개 변수들은 항상 막혀있기 때문에 고려하지 않아도 된다는 것이다.

 

d분리의 다른 예시에 대해 살펴보자. 단변량 가우시안 분포의 평균에 대한 사후 분포를 찾는 문제를 생각해 보자. 이를 그래프로 표현하면 다음과 같다.

D = {x1, ... , xN}라고 하면 D집합의 원소는 관측된 µ에 대해 꼬리대 꼬리 노드이기 때문에 각각의 xi와 xj사이에 독립이라는 것을 알 수 있다. 따라서 독립의 성질을 이용하여 다음과 같이 적을 수 있다.

그러나 여기서 만약 µ에 대해 적분한다면 관측값들은 더 이상 독립적이지 않게 된다.

 

따라서 집합 D에 속한 원소들 간의 독립성은 관측된µ에 의한 조건부 독립으로 정의된다.

 

방향성 인수분해(DF)

 

방향성 그래프는 결합 확률 분포를 조건부 확률들의 곱으로 분해한다는 것을 이전 글에서 설명하였다.

베이지안 네트워크 (tistory.com)

베이지안 네트워크

또한 방향성 그래프는 d 분리 기준을 통해 구해진 조건부 독립성들을 표현하기도 한다. 

d 분리는 이 두 성질이 동등함을 나타낸다. 이를 명확히 하기 위해 방향성 그래프를 필터로 생각하자. 확률 분포 p(x)는 인수분해 형태로 표현 가능할 때만 필터를 통과할 수 있을 것이다. 또한, 역으로 필터를 통과하는 분포만이 해당 인수분해 형태로 표현될 수 있을 것이다. 이렇게 얻게 된 집합을 방향성 인수분해(directed factorization, DF) 집합이라고 하자. 

그래프 모델을 필터로 바라보는 관점. 확률 분포 p(x)를 해당 필터에 통과시키면 방향성 인수분해를 만족시키는 분포들 DF만 남게 된다. 또한 d 분리 정리에 의해 조건부 독립성을 띄는 분포만 필터를 통과한다면 똑같이 DF만 남게 된다.

필터를 '인수분해 형태로 표현가능한 분포만 통과'와, 'd 분리 기준을 적용하여 조건부 독립 성질을 만족하는 분포만 통과' 둘 중 어느것을 사용해도 결과로 나타나는 집합은 방향성 인수분해 DF집합이다. 따라서 둘의 성질이 동일하다는 것이 증명되었다.

 

마르코프 블랭킷

 

결합 분포 p(x1, ... , xD)를 고려해보자. 여기서 특정 노드 xi의 조건부 분포를 고려한다고 하자. 이는 인수분해 성질을 이용하여 다음과 같이 적을 수 있다.

전체 결합 분포에서 xi만 적분한 결합분포를 나누어 xi의 조건부 분포를 구하는 식으로 유도하였다. 위의 식의 우변을 보자. xi와 관련이 없는 조건부 분포는 적분 밖으로 나올 수 있고 이는 분자의 동일한 것과 상쇄될 것이다 .결국 남는 것은 다음과 같다.

• p(xi|xj,...)와 같이 xi가 자손 노드가 되는 조건부 분포
• p(xj|xi,...)와 같이 xi가 부모 노드가 되는 조건부 분포

여기서 직관적으로 xi의 부모 노드와 자손 노드가 xi의 조건부 분포를 고려할 때 필수적으로 고려해야 한다는 것을 알 수 있다. xi와 직접적으로 연관된 노드이다. 그러나 여기서 중요한 것은 xi의 자손 노드의 부모 노드 즉, 공동 부모(co-parents) 노드까지 고려해야한다는 것이다.

xi의 마르코프 블랭킷

위의 그림은 xi의 마르코프 블랭킷을 나타낸다. 마르코프 블랭킷은 xi를 나머지 그래프로부터 분리시키는 최소한의 노드 집합을 일컫는다. 위의 그래프를 보면 xi의 부모, 자손 노드와 더불어 자손의 또다른 부모들까지 포함해야 하는 것을 알 수 있다. 그렇다면 왜 이들까지 포함해야 할까?

 

첫 번째로 위의 두 가지 리스트 중 두 번째 것을 보자. p(xj|xi,...)와 같이 xi가 부모 노드가 되는 조건부 분포가 마르코프 블랭킷에 포함된다. 여기서 xj에 대해 고려할 때, xj의 부모가 xi이외에도 xk, xl 두 개가 더 있다고 가정하자. 이 때 xj의 조건부 확률 분포는 p(xj|xi, xk, xl)이라고 적어야 한다. 만약 p(xj|xi)로 두 개의노드를 생략할 경우 이는 잘못된 정의라는 것을 위에 첨부한 베이지안 네트워크 글에서 설명하였다. 따라서 xi의 자손 노드를 나타내기 위해 반드시 자손 노드의 모든 부모가 고려되어야 하고 그래서 공동 부모도 xi의 마르코프 블랭킷에 포함된다.

 

두 번째로 이번엔 조건부 독립의 측면에서 이해해보자. xi와 부모 노드들을 기준으로 먼저 생각해보자. 부모 노드(1번 노드)와 연결된 또다른 노드(위의 그림에는 표현되지 않은)와 xi사이는 꼬리 대 꼬리 혹은 머리 대 꼬리로 제한된다. 따라서 xi의 부모 노드인 1번 노드가 관측되었을 경우 그 노드와 연결된 다른 노드와 xi는 조건부 독립임을 알 수 있다. 

이번엔 자손노드와 연결된 노드를 고려해보자. xi의 자손 노드(2번 노드)와 연결된 또다른 노드와의 조건부 독립 관계를 생각해 보자. 2번 노드의 자손 노드의 경우 xi와 머리 대 꼬리 노드가 된다. 따라서 2번 노드가 관측되었을 때 2번 노드의 자손 노드와는 조건부 독립이다. 2번 노드의 부모 노드(3번 노드)를 고려해보자. 3번 노드와 xi는 머리 대 머리 노드이다. 따라서 2번 노드가 관측되었을 때 3번 노드와 xi는 조건부 독립 성질을 띄지 않는다(조건부 독립(conditional independence) (tistory.com) 참조). 이와 같이 3번 노드에 해당하는 공동 부모는 조건부 독립 성질을 띄지 않기 때문에 마르코프 블랭킷에 포함되고, 그래프를 완전히 분리시키기 위해 고려야되야 할 노드에 포함되는 것이다.