마르코프 무작위장(Markov random field)

마르코프 무작위장(Markov random field)은 노드와 링크로 구성되어 있다는 점에서 베이지안 네트워크와 비슷하나, 이와는 달리 방향성이 없는 링크를 가지고 있어 비방향성 그래프 모델(undirected graphical model)이라고도 불린다. 마르코프 무작위장을 이해하기 위해 먼저 조건부 독립 성질부터 알아보자.

 

조건부 독립 성질

 

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

조건부 독립(conditional independence)

위의 글을 통해서 조건부 독립에 대해 알아보았다. 조건부 독립을 정의하기 위해 'd 분리'라는 개념을 이용하였는데 방향성 그래프에서 조건부 독립 성질을 표현하는 것에는 애매함이 있었다. 왜냐하면 머리 대 머리, 꼬리 대 꼬리, 머리 대 꼬리 각각에 따라 조건부 독립의 성질이 달랐기 때문이다. 따라서 그래프를 보고 한 눈에 조건부 독립 성질을 파악할 수 없었다. 이러한 애매함이 생기지 않도록 그래프로 나타낸 것이 바로 비방향성 그래프 모델이다.

 

A, B, C 세 개의 노드 집합을 확인하였다고 하자. 그리고 이들에 대해 다음 조건부 독립성을 고려해보자.

비방향성 그래프에서는 해당 성질을 만족하기 위해 A에서 B를 연결하는 모든 경로를 고려해야 한다. 모든 경로가 집합 C상의 하나 이상의 노드를 경유한다면 막힌것이며, 조건부 독립성을 만족한다. 하나라도 막히지 않는 경로가 있다면 조건부 독립이 반드시 유효하지 않는다. 정확히 말하자면, 그래프에 해당하는 분포들 중에 조건부 독립을 만족하지 않는 분포가 최소 1개는 존재한다는 것이다. 

비방향성 그래프

위의 그래프를 보면 A에서 B로 가는 경로는 모두 하나 이상의 C를 거쳐야하므로 위의 조건부 독립 성질을 만족한다. 방향성 그래프보다 조건부 독립 성질을 한눈에 파악하기 쉽다는 장점을 볼 수 있다.

 

마르코프 블랭킷

 

d 분리(D-separation) (tistory.com) 에서 방향성 그래프의 마르코프 블랭킷에 대해 살펴보았다. 비방향성 그래프에서 마르코프 블랭킷은 어떻게 나타날까?

비방향성 그래프의 마르코프 블랭킷

1번 노드를 기준으로 생각하자. 1번 노드의 모든 이웃 노드들이 관측되었다면(음영) 이웃 노드와 연결된 다른 노드들(위의 그래프에는 나타나지 않은)로 가기 위해 이웃 노드를 반드시 거쳐야 하므로 조건부 독립을 만족한다. 따라서 1번 노드를 전체 그래프로부터 분리시키기 위한 최소한의 노드는 해당 노드의 이웃 노드에 해당한다.

 

인수분해 성질

 

비방향성 그래프의 인수분해 법칙에 대해 알아보자. 이는 결합 분포 p(x)를 그래프에 대해 변수 집합들에 대한 함수들의 곱으로 표현하는 것이다.

 

링크로 연결되지 않은 두 노드 xi, xj를 고려해보자. 이 경우 두 노드를 제외한 그래프 상의 모든 변수가 관측되었을 경우 xi, xj는 조건부 독립이어야 한다. 두 노드가 직접적으로 연결되어 있지 않기 때문에 관측된 노드를 경유해야 하기 때문이다. 이는 다음과 같이 표현 가능하다.

여기서 x\{i,j}는 xi와 xj를 제외한 모든 변수 x의 집합을 지칭하는 것이다. 조건부 독립성질 p(a,b|c) = p(a|c)p(b|c)를 이용해 위와 같이 나타낼 수 있다.

여기서 클리크(clique)의 개념이 발생한다. 클리크는 그래프의 부분집합으로 그 부분집합에 속하는 모든 노드간에 링크가 존재하는 경우를 의미한다. 다시말해, 클리크에 속하는 노드들은 완전연결 되어있다. 최대 클리크(maximal clique)는 다른 어떤 노드를 추가하더라도 클리크 성질이 더 이상 만족되지 않는 최대 크기의 클리크를 일컫는다.

클리크와 최대 클리크

위의 그림에서 녹색 경계는 클리크, 파란색 경계는 최대 클리크이다. x1과 x4사이에 링크가 없기 때문에 x1을 포함시키면 클리크가 아니게 되므로 파란 경계가 최대 클리크가 되는 것이다.

 

그렇다면 비방향성 함수를 어떻게 식으로 적어낼 수 있을까? 이는 포텐셜함수의 곱으로 적을 수 있다.

클리크를 C, 그 클리크에 포함되는 변수 집합을 xC라고 하자. 이 경우 다음과 같이 나타낼 수 있다.

분할 함수라고 불리기도 하는 Z는 다음처럼 주어지는 정규화 상수다.

Z는 분포 p(x)가 정규화되도록 한다. 방향성 그래프에서는 링크가 조건부분포를 나타내었지만, 비방향성 그래프에서는 링크가 어떤 특정한 확률적인 해석을 가지도록 제한되어 있지 않다.

 

정규화 상수 Z가 존재한다는 것은 비방향성 그래프의 가장 큰 한계점 중 하나다. 만약 각각이 K개의 상태를 가지는 M개의 이산 변수를 이용해서 모델을 만든다면, 정규화 상수를 계산하는 과정은 K^M개의 상탯값들에 대한 합산 과정을 필요로 한다. 따라서 이 과정에서 드는 계산 비용이 모델의 크기에 대해 기하급수적으로 증가한다.