인자 그래프

그래프 모델의 추론 알고리즘을 알아보기 전에 이를 이해하는 데 필요한 새로운 형태의 그래프인 인자 그래프(factor graph)에 대해 알아보자. 

 

인자 그래프는 각각의 인자를 기준으로 그래프를 나타낸 것이다. 예시는 다음과 같다.

인자 그래프 예시

위의 그래프는 인자 그래프로 얼핏 보면 비방향성 그래프와 비슷하지만 이와는 달리 작은 사각형이 포함되어 있다. 이 사각형이 '인자'이며, 인자는 변수들의 관계로 인해 생성된다. 위의 그래프를 결합 분포로 적으면 다음과 같다.

위의 식에서 fa는 x1, x2사이의 관계에 대해 나타내는 인자이며, fb도 마찬가지이다. fc는 x2와 x3의 관계, fd는 x3에 대한 함수이다. 만약 위의식을 비방향성 그래프로 나타냈다면, fa와 fb는 합쳐져 x1, x2의 포텐셜 함수로, fc,와 fd가 합쳐져 x2와 x3의 포텐셜 함수로 표현되었을 것이다. 즉, 인자로 그래프를 나타낸다면, 비방향성 그래프에서 표현할 수 없는 세부적인 변수 사이의 함수를 인자 그래프로는 표현할 수 있다.

 

위의 설명을 바탕으로 하나의 방향성/비방향성 그래프는 여러 형태의 인자 그래프로 표현될 수 있다.

비방향성 그래프와 인자 그래프. 모두 같은 관계를 나타낸다.

왼쪽의 비방향성 그래프는 '세 변수 x1, x2, x3가 서로 종속적이다'라는 성질만을 암시하고 있다. 이는 가운데의 인자그래프로 나타낼 수 있다. 그런데 여기서, 인자그래프는 만약 x1, x2, x3에 종속적인 함수 fa이외에도 x2, x3끼리만 종속적인 함수 fb가 있다면 이를 나타낼 수 있다. 가운데와 오른쪽 인자그래프는 둘의 형태는 다르지만 비방향성 그래프로 변환하면 세부적인 정보를 잃고 왼쪽의 비방향성 그래프가 된다.

 

이번엔 방향성 그래프의 예시를 보자.

방향성 그래프와 인자 그래프

이전 글에서도 계속 설명했듯이, 방향성 그래프와 비방향성 그래프는 머리 대 머리 노드일 경우를 제외하고는 크게 다르지 않다. 따라서 여기서도 머리 대 머리 노드인 경우만 생각해보자. (a)와 같이 머리 대 머리 노드의 경우 x1은 직접 연결된 x3이외에도 공동 부모인 x2와도 종속적이다. 따라서 인자 그래프로 나타낼 경우 (b)와 같이 나타내야 한다. 여기에 추가적으로 부모 노드 x1, x2는 결합 분포로 나타낼 댸 각각의 확률 변수 p(x1)과 p(x2)로 나타나는데, 이를 인자 그래프에 각각 fa와 fb로 표현하여 나타낼 수 있다. 이 경우 (c)와 같이 적을 수 있다.

 

그래프에서의 추론 문제를 해결하는 데 있어 '트리 구조'는 문제를 훨씬 간단하게 만들어주기 때문에 매우 중요하다. 따라서 이번엔 방향성/비방향성 그래프와 인자 그래프의 트리 구조 관계를 알아보자.

다중 트리

여기서도 위와 같은 이유로 머리 대 머리 노드를 가진 트리를 살펴보자. 방향성 트리 (a)를 비방향성 그래프로 변경하면 (b)와 같다는 것을 알 수 있다. 이 때 (b)는 순환 구조를 가지게 되므로 트리가 아니게 되는 문제가 발생한다. 그러나 이를 다시 적절한 인자 함수를 정의하여 인자 그래프로 변환하면 (c)와 같아지며 다시 트리 구조를 가지게 된다. 이처럼 방향성/비방향성 그래프를 인자그래프로 변환하면 순환 구조를 없애고 트리 구조로 정의될 수 있다는 추론 문제에서의 이점을 가지게 된다.

 

다음과 같은 지역적 순환 구조를 가지는 방향성 그래프도 고려해 볼 수 있다.

이러한 그래프도 적절한 인자 함수를 정의한다면 순환 구조를 제거하여 트리 구조로 만들 수 있다.

 

위의 예시처럼 x1, x2, x3의 관계로 나타낸 f(x1, x2, x3)를 사용하면 트리 구조로 만들 수 있지만 다음과 같이 표현할 수도 있다.

같은 비방향성 그래프에 대한 다른 인자 그래프

(b)는 x1, x2, x3사이의 관계를 한번에 나타낸 반면 (c)의 경우 더 구체적으로 인수분해하여 fa, fb, fc로 나타냈다. 이 경우 인자 그래프도 순환 구조를 가지게 된다. 많은 상황에서, 우리는 트리 구조를 원할 것이기 때문에 이러한 방식의 인수분해는 적절하지 않을 수 있다. 따라서 적절한 인자함수를 사용하여 순환 구조를 트리 구조로 변경하는 것이 그래프 추론 문제에서 중요하다.