8.3 마르코프 무작위장 (Markov network)

지금까지 PRML 8장에서 베이지안 네트워크와 조건부 독립에 대해 다루었는데

이에 관한 모든 기반은 그래프의 성질이 방향성을 띄고 있다는 것이었다.

 

반면에 이번 포스팅에서 다룰 마르코프 네트워크, 비방향성 그래프 모델이라 알려진

마르코프 무작위장(Markov Random Field)에 대해 다루어 보고자 한다.

 

PRML 8.3 Markov Random Field

위의 그래프를 본다면, 화살표가 존재하지 않고 링크로만 이어져 있다.

A와 B 사이에 모든 경로가 차단되어 있을 경우, 즉 C가 방향을 전부 차단할 경우 이는 조건부 독립이다.

또한 C와 연결되어 있는 모든 노드들을 삭제하고 A와 B 사이의 링크가 없다면 조건부 독립 성질을 만족한다.

 

베이지안 네트워크(방향성 그래프)와 비교했을 때, d-구분을 사용하지 않아도 간단하게 조건부 독립 성질을

구할 수 있다는 것이 마르코프 무작위장(비방향성 그래프)의 장점이다.

 

 

x의 i와 j 번째 노드가 서로 조건부 독립인지 확인해보자.

여기서 x\{i,j}는 i와 j를 제외한 나머지의 노드들이다.

조건부 독립 성질을 만족하게 된다면 우변과 같이 i와 j에 대해 각각 나누어서 계산 될 수 있다.

즉 이를 마르코프 무작위장에서의 인수분해라 한다.

 

PRML 8.3 Markov Random Field

 

클리크(clique)라는 개념이 등장하게 된다.

클리크는 그래프의 부분집합으로 부분집합 안에 속한 노드들끼리 모두 연결되어 있는(fully connected) 것을

의미한다. 또한 최대 클리크(maximal clique)는 클리크에서 다른 노드를 추가하지 못하는 상태를 의미한다.

 

위의 그래프에서 클리크는 {x1 x2}, {x2 x3}, {x3 x4}, {x2 x4},{x1 x3}와, 최대 클리크인 {x1 x2 x3}, {x2 x3 x4}

를 가지고 있다.

 

위의 최대 클리크를 이용하여 마르코프 랜덤필드의 결합  분포를 구할 수 있게 된다.

 

 

 

 

 

C는 최대 클리크를 의미하며 Xc는 최대 클리크의 변수 집합이며

는 포텐셜 함수(potential function)

를 의미한다. 따라서 이 경우 포텐셜 함수의 곱으로 결합분포 p(x)를 구할 수 있으며 

Z라는 정규화 상수(분할 함수 - partition function)로 올바르게 p(x)를 정규화 하게 한다.

 

여기서 왜 정규화라는 과정이 필요한가? 라는 질문이 생길 수 있다.

이전에 베이지안 네트워크에서는 이러한 정규화 과정이 없었기 때문이다.

그 이유는 포텐셜 함수는 확률 함수가 아니며 일반 함수이기 때문이다.

즉, 다른 확률함수들은 모든 확률을 더했을때 1이 되는 정규화가 되어 있는데 

마르코프 네트워크는 그렇지 않다는 것이다. 따라서 이러한 정규화 과정이 필요하다.

 

또한 이러한 포텐셜 함수는 factor라는 개념을 알면 더 정확히 이해할 수 있는데

다음 장인 8.4장 그래프 모델의 추론에서 포스팅 할 것이다.

 

결론적으로 이러한 Z, 정규화 상수의 존재는 마르코프 네트워크의 큰 한계점 중 하나인데, 

각각 K개의 상태를 가지는 M개의 이산 변수들을 이용해 모델을 제작한다면

Z를 구하는 수식을 보았을 때 K^M의 계산 비용이 필요하기 때문에 오래 걸리게 된다.

 

하지만 지역적 조건부 분포를 구하기 위해서라면 조건부는 두 주변부의 비율에 해당하며

따라서 계산 과정에서 분할 함수 Z가 분모 분자 사이에 상쇄되기에 필요하지 않게 된다.

 

---

또한 사슬 그래프(chain graphs)라는 것이 존재하는데 기존의 두 가지 그래프 모델을 확장하여

방향성 링크와 비방향성 링크를 둘 다 포함하는 그래프 모델을 만들 수 있다.

이러한 그래프가 왜 나왔을까? 

 

PRML - 8.3 Markov Random Field

위 밴다이어그램과 사슬 그래프를 추가적으로 설명하기 위해서는 완벽 사상(perfect map)에 대해 알고 있어야 한다.

조건부 독립성을 찾아내는 방법이 앞서 설명한 방향성과 비방향성이 다르며 따라서 두 종류의 그래프는

서로 다른 조건부 독립성을 표현할 수 있음을 알 수 있다. 이를 필터라는 관점으로 한번 바라보자.

 

어떤 분포의 모든 조건부 독립성이 그래프에 반영되어 있을 경우에 이를 D사상(종속성 사상)이라 하며

그래프에 암시된 모든 조건부 독립성이 해당 분포에 만족될 경우, 그 그래프를 해당 분포의

I사상(독립 맵)이라 한다. 따라서 완벽 사상은 I와 D를 포함하는 것이라 볼 수 있다.

 

다시 위의 밴다이어그램을 보면, P는 주어진 변수들의 분포, D는 방향성 그래프를 사용한 완벽 사상

U는 비방향성 그래프를 사용한 완벽사상을 나타낼 수 있는 범위를 나타낸다.

 

결론적으로 둘이 다른 부분의 완벽 사상을 가지고 있기에 사용하는 모델에 따라 다르게 사용한다는 것!

그리고 더 포괄적으로 모델을 짜기 위해 사슬 그래프를 사용한다는 것!

여기서 이것들을 기억하면 8.1장부터 3장까지는 거의 이해했다고 볼 수 있다.

물론 공부는 많이 해야겠지만...