합/곱 알고리즘 (sum - product Algorithm)

인자 그래프 (tistory.com)

인자 그래프

 

 

위의 글에서 소개한 인자 그래프를 바탕으로 트리 구조 그래프에 적용할 수 있는 강력한 추론 알고리즘인 합/곱 알고리즘(sum-product algorithm)에 대해 알아보자. 

 

합/곱 알고리즘

 

먼저 특정 변수 노드 x의 주변값 p(x)를 구하는 문제를 고려해 보자. 지금은 모든 변수들이 은닉 변수 즉, 관측되지 않았다고 가정하자. x를 제외한 모든 변수에 대한 결합 분포를 합산하여 주변 분포를 구할 수 있다.

식1

여기서 x\x는 x를 제외한 x의 변수들을 일컫는다. 합/곱 알고리즘의 기본적인 아이디어는 인자 그래프로 p(x)를 변경하고 그 후 덧셈과 곱셈들의 순서를 교환하여 알고리즘을 구하는 것이다. 다음의 그래프를 보자.

x를 중심으로 나타낸 인자 그래프

위의 그래프는 x를 중심으로 축약하여 나타낸 p(x)의 인자 그래프이다. x는 여러 인자들을 통해 다른 노드들과 연결되어 있다 그 중 하나의 인자인 fs를 고려하여 보자. fs는 x 뿐만 아니라 다른 여러 노드와 연결되어 있을 것이다. Xs는 fs를 통해 x와 연결되어 있는 모든 노드들을 지칭하며, Fs(x, Xs)는 fs와 연관된 그룹의 모든 인자들의 곱을 나타낸다. 이는 다음 식으로도 나타낼 수 있다.

식2

ne(x)는 x의 이웃인 인자 노드들의 집합을 지칭한다. 즉 x를 중심으로 x와 이웃인 모든 인자 노드들을 고려하여(ne(x)) 그들과 연결된 변수 노드들의 곱을 전부 계산하는 것으로 p(x)를 나타낸 것이다.

 

위의 식1에 식 2를 대입하고, 덧셈과 곱셈의 순서를 교환하면 다음과 같이 쓸 수 있다.

여기서 µfs→x(x)는 다음과 같이 정의된다. 

식3

위의 식을 fs로부터 x로 전달되는 메시지로 해석할 수 있다. 즉, p(x)는 x의 주변인자로부터 받은 모든 메시지의 곱으로 해석할 수 있다.

 

이제 이 메시지들을 계산해보자. 그런데 계산하려고 보니 fs와 연관된 각각의 변수 노드는 또 다른 인자 노드와 연결되어 있을 것이다. 다음 그래프를 보면 조금 더 쉽게 이해할 수 있을 것이다.

fs인자 노드와 연결된 변수노드에 연결된 또다른 인자 노드들Gm을 나타낸다.

위의 그래프를 보자. fs와 연결된 변수 노드 xm을 계산하려고 보니 여기에 연결된 또다른 인자 노드들이 있고 이를 고려해야 한다. xm과 연결된 모든 인자 노드들의 곱은 Gm으로 표현하였다. 이는 식으로 다음과 같이 나타낼 수 있다.

식4. Fs를 구하기 위해 G1~GM을 구해야 한다는 것을 나타낸다.

식4를 식3에 넣고 정리하면 다음을 얻을 수 있다.

인자 노드 fs로부터 x로 들어오는 메시지는 다시 변수 노드 xm들로부터 fs로 들어오는 메시지들의 곱으로 나타낼 수 있다.

인자 노드 fs로부터 x로 들어오는 메시지를 fs와 연관된 변수 노드들 xm으로부터 fs로 들어오는 메시지들의 곱으로 나타낼 수 있다는 것을 확인하였다. 여기서 µxm→fs (xm)는 다음과 같이 나타낼 수 있다.

여기까지 두 가지의 다른 메시지를 살펴보았다. 하나는 인자 노드로부터 변수 노드로 전달되는 메시지, 하나는 변수 노드로 로부터 인자 노드로 전달되는 메시지이다. p(x)를 구하는 과정은 x와 연결된 인자 노드로부터 x변수 노드로 들어오는 메시지를 계산하는 것을 시작으로 이를 계산하기 위해 필요한 변수노드로부터 인자노드로 전달되는 메시지를 계산하고 또 이를 계산하기 위해 필요한 메시지를 계산함으로써 전체 그래프에 대한 계산으로 뻗어 나간다. 즉 아래와 같은 순서로 반복적으로 계산하게 되는 것이다.

잎 노드(인자or변수) ...-> 인자 -> 변수 -> 인자 -> x변수

위의 과정을 보면, 결국 그래프는 트리 구조이기 때문에 마지막 노드에 도달하게 될 것이다. 이를 잎 노드(leaf-node)라고 지칭한다. 잎 노드는 인자 노드일수도 있으며 변수 노드일수도 있다. 만약 잎 노드가 변수 노드라면 여기서 들어오는 메시지는 다음과 같이 정의된다.

잎노드가 변수노드

만약 잎 노드가 인자 노드라면 다음과 같이 정의된다.

이는 그래프로 다음과 같이 표현할 수 있다.

반복적으로 메시지를 거슬러 올라가다보면 위와 같은 잎노드를 만나게 되고 잎 노드가 정의되었으므로 거슬러 올라가며 중단했던 모든 계산들을 실행할 수 있게 된다. 이를 통해 p(x)를 구하는 과정이 완료되게 된다.

 

그렇다면 x이외에도 모든 노드의 주변분포를 구하기 위해서는 어떻게 할 수 있을까? 각각의 변수 노드를 한 번씩 루트 노드로 삼고 위의 과정을 반복한다면 어마어마하게 비효율적일 것이다. 각각을 반복하며 중복되는 계산이 매우 많을 것이기 때문이다. 이를 해결하기 위해 이전 글(그래프 모델에서의 추론 - 사슬 (tistory.com))에서 사용한 아이디어를 똑같이 사용할 수 있다. 하나의 노드를 루트 노드로 정의하고 양방향으로 메시지를 전달하는 것이다. 이 때 중간 과정을 모두 저장한다면 모든 노드 와 인자 사이의 메시지들의 값을 알 수 있게 된다. 이를 통해 원하는 변수 노드의 주변분포를 보다 적은 계산으로(하나의 주변분포를 구할때 보다 2배 많은 계산량) 구할 수 있게 된다(위의 링크에서 소개한것과 마찬가지의 결과이다).

좀 더 자세한 방법은 밑의 예시를 통해 알아보자.

 

합/곱 알고리즘 예시

 

위에서 설명한 합/곱 알고리즘 이론을 바탕으로 구체적인 예시를 들어 이해해보자.

 

다음과 같은 4개의 노드를 가진 인자 그래프를 고려해보자.

이는 인자 그래프 정의를 이용해 다음 식으로 나타낼 수 있다.

이 그래프에 합/곱 알고리즘을 적용하기 위해 x3을 루트 노드로 정하자. 그러면 이 그래프에는 x1, x4 두 개의 잎 노드가 존재하게 된다. 잎 노드로부터 시작해서 모든 메시지를 구하면 다음과 같다.

이제 반대로 루트 노드에서 잎 노드로 메시지를 전달하자.

이 과정을 설명한 그래프가 다음과 같다.

(a)는 잎 노드로부터 루트 노드까지, (b)는 루트 노드로부터 잎 노드까지 메시지를 구한 것이다.

 

이제 모든 링크들에 대해 양 방향으로 메시지가 지나갔다. 이를 바탕으로 주변 분포들을 모두 계산할 수 있다. 간단한 체크를 통해 주변 분포 p(x2)가 올바른 식으로 주어지는지 확인해 보자.

결과가 정확히 나타나는 것을 알 수 있다.