마르코프 무작위장 - 방향성 그래프와의 연관성

비방향성 그래프, 방향성 그래프 변환

 

지금까지 확률 분포를 표현하기 위해 방향성 그래프와 비방향성 그래프에 대해 알아 보았다. 이제 두 그래프의 연관성에 대해 알아보자. 일단 첫 번째로 방향성 그래프를 이용해 명시된 모델을 비방향성 그래프로 변환하자. 첫 번째 예시로 다음을 고려해보자.

사슬 구조 방향성 그래프의 결합 분포

이를 그래프로 표현하면 다음과 같다.

(a)는 방향성 그래프로 표현한 것, (b)는 비방향성 그래프로 표현한 것이다.(b의 xN 다음 xN-1은 오타이며 xN-1 다음 xN이 맞다)

이 비방향성 그래프에서 최대 클리크는 단순히 인접한 노드들의 쌍에 해당하기 때문에 위와 같이 비방향성 그래프가 표현되었다. 이를 결합분포로 다음과 같이 확인할 수 있다.

여기서 각각의 포텐셜함수는 다음과 같이 정의된다.

이렇게, 방향성 그래프의 조건부 확률을 비방향성 그래프의 클리크 활성화 함수로 매칭할 수 있으면 변환이 가능하다. 역도 마찬가지이다. 이를 만족시키기 위해서는 각 조건부 분포에서 보여지는 변수 집합이 비방향성 그래프의 클리크들 중 최소 하나에 속해있어야 한다. 이는 방향성 그래프 상에서 하나의 부모를 가지고 있을 경우(머리 대 꼬리 혹은 꼬리 대 꼬리) 단순히 방향성 링크를 비방향성으로 바꾸면 된다. 그러나 머리 대 머리 경로를 가지는 노드의 경우 그렇지 않다. 다음 결합 분포를 살펴보자.

위의 결합 분포를 방향성 그래프와 비방향성 그래프로 나타내보자.

(a)는 방향성, (b)는 비방향성 그래프이다.

위의 조건부 분포가 클리크 포텐셜 함수에 흡수되기 위해서는 네 개의 변수가 모두 하나의 클리크에 포함되어야 한다. 따라서 x4의 모든 부모들을 링크로 연결시켜야 한다. 이러한 과정을 도덕화(moralization)라고 부르며, 그 결과에 해당하는 비방향성 그래프를 도덕적 그래프(moral graph)라고 부른다.

 

이렇게 부모 노드를 비방향성 링크로 연결해야 하는 이유를 조건부 독립 성질을 통해서도 이해할 수 있다.위의 방향성 그래프 (a)는 머리 대 머리 노드이다. 만약 x4가 관측된다면, x1, x2, x3는 서로 조건부 독립 성질을 만족하지 못한다는 것을 알고 있다(조건부 독립(conditional independence) (tistory.com)). 이제 (b)를 보자. 만약 방향성 그래프에서 비방향성 그래프로 변환하는 과정에서 부모 노드들을 링크로 연결하지 않았다고 가정해보자. 그렇다면 x4가 관측되었을 때 x1, x2, x3은 서로 x4를 통하지 않고서는 연결되지 않는다. 이는 비방향성 그래프에서의 조건부 독립 조건에 해당한다(마르코프 무작위장(Markov random field) (tistory.com)). 즉, 이 경우 방향성 그래프일 때는 조건부 독립 성질을 띄지 않는데 비방향성 그래프로 변환 결과 조건부 독립 성질을 띄게 되는 모순이 생긴다. 이는 같은 확률 분포를 나타내지 않는다는 뜻이 된다. 따라서 변환 시 부모 노드들을 비방향성 링크로 연결하여 x4가 관측되어도 x1, x2, x3가 서로 x4를 지나지 않고도 연결되도록 해야 하는 것이다. 

 

따라서 결론은 방향성 그래프를 비방향성 그래프로 변환하기 위해 첫째로 각 노드에 대해 그 부모 노드들의 모든 쌍 사이에 비방향성 링크를 추가하고, 그 후 모든 링크의 방향 표시를 제거하여 도덕적 그래프를 만들어야 한다. 그 다음 방향성 그래프의 조건부 분포를 하나씩 취하여 클리크 포텐셜 중 하나에 곱하면 변환이 완료된다.

 

이렇게 방향성 그래프를 비방향성 그래프로 변환하는 과정은 접합 트리 알고리즘과 같은 추론 테크닉에서 중요한 역할을 한다.

 

방향성 그래프와 비방향성 그래프의 차이점

 

방향성 그래프와 비방향성 그래프가 조건부 독립 성질을 나타내는 방법이 다르다는 것을 이전 글들을 통해 알아보았다. 그런데, 각각의 그래프가 모든 조건부 독립성을 표현할 수는 없는데 이는 그래프 표현 방식의 한계 때문이다. 두 그래프가 각각 표현할 수 없는 조건부 독립성이 다른데 이에 대해 알아보자.

 

이에 앞서 먼저 D사상, I사상, 완벽 사상에 대해 알아보자. 

 

• D사상은 어떤 분포의 조건부 독립성이 그래프에 모두 반영되어 있는 경우이다. 예를 들어, 링크가 하나도 없는(완전히 연결이 끊어진) 그래프는 모든 노드가 조건부 독립이기 때문에 D사상에 해당한다.
• I사상은 그래프가 나타내는 모든 조건부 독립성이 해당 분포의 조건부 독립성에 포함되는 경우이다. 예를 들어, 완전히 연결된 그래프는 조건부 독립성을 가지지 않기 때문에 I사상에 해당한다.
• 완벽사상은 D사상이면서 I사상인 그래프이다. 즉, 어떤 분포의 조건부 독립성이 그래프에 모두 반영이 되어있으면서, 그래프가 나타내는 조건부 독립성이 해당 분포의 조건부 독립성에 포함되는 경우이다.  

이를 조금 더 쉽게 설명하기 위해 어떤 분포와 그 분포를 그래프로 나타낸 것을 생각해보자. 그리고 각각이 가지고 있는 조건부 독립 성질을 생각해보자.

 

D사상은 다음과 같다.

분포    ----조건부 독립---->    그래프

즉, 분포가 가진 모든 조건부 독립 성질이 그래프에 반영되어있는 상태이다. 

 

I사상은 다음과 같다.

분포    <----조건부 독립----    그래프

즉, 그래프가 가진 모든 조건부 독립 성질이 분포에 반영되어있는 상태이다. 

 

완벽 사상은 다음과 같다.

분포    <----조건부 독립---->    그래프

분포가 가진 조건부 독립 성질과 그래프가 가진 조건부 독립 성질이 완전히 일치하는 것이다.

 

이러한 개념을 바탕으로 우리의 논제를 "방향성/비방향성 그래프가 완벽 사상을 제공하는 분포는 어떻게 다른지"로 정의하자. 이는 밴다이어그램으로 나타낼 수 있다.

P는 주어진 변수들에 대한 모든 분포들, D는 방향성그래프를 이용해 완벽 사상 할 수 있는 분포들, U는 비방향성그래프를 이용해서 완벽 사상 할 수 있는 그래프이다.

위의 밴다이어그램과 같이 방향성 그래프는 완벽 사상이 가능하지만 비방향성 그래프는 완벽 사상이 불가능한 경우(교집합을 제외한 D)가 존재하며, 이와 반대되는 경우(교집합을 제외한 U)도 존재한다. 또한 두 그래프 모두 완벽 사상이 가능할 수도 있으며(교집합), 두 그래프 모두 완벽 사상이 불가능(D와U의 합집합의 여집합)할 수도 있다. 이에 대한 예시를 몇가지 살펴보자. 

 

다음 그래프를 고려해 보자.

비방향성 그래프로는 이 그래프의 조건부 독립 성질을 모두 표현할 수 없다.

위의 방향성 그래프는 다음을 내포하고 있다.

동일한 세 개의 변수에 대해 완벽 사상하는 비방향성 그래프는 존재하지 않는다.

 

이번엔 다른 그래프를 고려해 보자.

방향성 그래프로는 이 그래프의 조건부 독립 성질을 모두 표현할 수 없다.

위의 비방향성 그래프는 다음을 내포하고 있다.

동일한 네 개의 변수에 대해 완벽 사상하는 방향성 그래프는 존재하지 않는다.