신뢰전파

신뢰전파(Belief Propagation) 또는 Sum-product 메시지 전달 (sum-product message passing)은 베이즈 네트워크 또는 마르코프 네트워크 등의 그래프 모델상에 작용하는 메시지 전달 알고리즘이다. 이 알고리즘은 이미 관측한 노드의 상태를 토대로 아직 관측하지 않은 노드의 주변분포를 각각 계산한다. 신뢰전파는 주로 인공지능이나 정보이론의 분야에서 널리 사용되고 있으며 저밀도 패리티 검사 부호, 터보 부호, 자유에너지 근사, 충족 가능성 문제를 포함하며 응용에 다수 성공함이 경험적으로 확인된 상태다.

이 알고리즘은 1982년 주디아 펄에 의해 제안된 것으로 당초에는 트리 구조상의 그래프 모델에서 작용되는 알고리즘을 후에 일반적인 트리 구조 모델에서도 작용할 수 있도록 확장하였다. 현재는 이 알고리즘이 일반 그래프 구조에서도 근사치를 주는 것으로 알려져있다.

한 가지 예를 들어 X=(X_v)를 결합확률질량함수p를 갖는 확률변수의 집합이라하면 특정 노드의 확률을 가리키는 주변분포 X_i는 단순히 p를X_i이외의 모든 노드에 대한 합을 구하는 것으로 표현 가능하다:

$p_{X_{i}}(x_{i})=\sum _{\mathbf {x} ':x'_{i}=x_{i}}p(\mathbf {x} ').$

그러나 이 계산방식은 만일 확률변수들이 100개의 이진변수라 한다 하여도 이 확률수 전체의 수는 2⁹⁹ ≈ 6.338 × 10²⁹라는 엄청난 수에 달하며 컴퓨터 상으로 계산하는 것은 매우 힘들어진다. 신뢰전파를 이용함으로써 대상 확률변수의 그래프 구조를 이용함으로써 주변분포의 계산을 보다 효율적으로 실행할 수 있다.

Sum-product알고리즘의 개요

신뢰전파는 인자그래프 상에서 실행되는 알고리즘이다. 여기서 인자그래프란 변수 $V$와 인자 $U$에 의해 구성되어있는 이분 그래프이며 변수와 인자는 변으로 연결되어있다. 이 그래프를 이용함으로써 결합확률질량함수를 아래와 같이 표현할 수 있다.

$p(\mathbf {x} )=\prod _{u\in U}f_{u}(\mathbf {x} _{u})$

여기서 x_u는 인자 노드 u에 연접해있는 변수를 뜻하는 벡터이다. 모든 베이즈 네트워크와 마르코프 네트워크는 인자그래프 형식으로 표현이 가능하다.

이 알고리즘은 ”메시지”로 불리는 변수 x_v를 인수로 취하는 함수를 노드간의 엣지를 따라 전파된다. 이들의 메시지는 특정 변수가 타 변수에 주는 영향 또는 "상호작용"을 내포하고 있다. 메시지에는 두가지 종류가 있다:

• 변수 노드 v에서 인자노드 u로 건네는 메시지. 메시지의 계산은 인접해있는 모든 인자 그래프의 곱을 취하는 것으로 표현할 수 있다 (그러나 대상 인자노드에서 온 메시지는 제외된다. 이것은 대상 인자노드에서는 메시지로 1을 보냈다고 간주하여도 무난하다):

$\mu _{v\to u}(x_{v})=\prod _{u^{*}\in N(v)\setminus \{u\}}\mu _{u^{*}\to v}(x_{v}).$

여기서 N(v)은 변수노드v에 연접한 모든 인자노드의 집합이된다. $N(v)\setminus \{u\}$가 공집합일 경우에는 $\mu _{v\to u}(x_{v})$는 균등분포가 된다.

• 인자노드u에서 변수노드v에 건네는 메시지. 메시지의 계산은 연접해있는 타 노드에서의 메시지의 곱을 취해 x_v이외의 모든 변수에 대한 주변화를 실행하는 것으로 표현된다:

$\mu _{u\to v}(x_{v})=\sum _{\mathbf {x} '_{u}:x'_{v}=x_{v}}f_{u}(\mathbf {x} '_{u})\prod _{v^{*}\in N(u)\setminus \{v\}}\mu _{v^{*}\to u}(x'_{v^{*}}).$

여기서 N(u)은 인자 노드 u에 연접해있는 모든 변수노드의 집합이 된다. $N(u)\setminus \{v\}$가 공집합일 경우에는 $\mu _{u\to v}(x_{v})=f_{u}(x_{v})$가 된다.

보는바와같이 "신뢰전파"의 이름의 유래는 위의 공식에서 오는 것임을 알 수 있다. 이 알고리즘에 의해서는 결합확률분포에 대한 주변분포를 계산하는 어려움이나 문제가 단순한 메시지의 곱과 합으로 감소된다.

트리 구조 경우의 엄밀해

신뢰전파의 가장 간단한 형태는 대상 인자그래프가 트리 구조인 경우이다. 이때, 신뢰전파는 주변분포의 엄밀해가 계산가능하며 이하 두 단계 스텝후에 종료된다. 이 알고리즘을 시작하기 전에 대상 그래프 안에 하나의 루트 노드를 정한다. 여기서 루트 노드가 아니며 엣지가 하나인 노드는 리프라 불린다.

첫 번째 단계에서는 리프 노드에서 메시지를 계산하기 시작한다. 각각의 노드는 엣지를 통하여 받은 메시지를 루트노드를 향해 전파한다. 그래프가 트리 구조이므로 대상 노드에게 메시지를 건네기 전에 모든 타 근접 노드로부터 메시지를 받을 수 있음이 보증된다. 이 전파법칙은 루트노드가 모든 근접 노드로부터 메시지를 받을때까지 반복된다.

두 번째 단계에서는 루트 노드로부터 리프노드를 향하여 메시지를 보낸다. 이 경우, 메시지는 역방향으로전파된다. 모든 리프노드가 메시지를 받음으로 이 알고리즘은 종료한다. 계산이 종료된 후, 각 노드의 주변분포는 인접해있는 인자 노드로부터의 메시지의 곱에 비례한다.

$p_{X_{v}}(x_{v})\propto \prod _{u\in N(v)}\mu _{u\to v}(x_{v}).$

동일하게 어느 특정인자에 속해있는 변수집합의 주변분포는 변수에서의 메시지와 그 인자의 곱에 비례한다:

$p_{X_{u}}(\mathbf {x} _{u})\propto f_{u}(\mathbf {x} _{u})\prod _{v\in N(u)}\mu _{v\to u}(x_{u}).$

이들의 계산은 수학적 귀납법에 의해 증명이 가능하다.

일반적인 그래프상의 근사 알고리즘

기묘하게도 일반적인 그래프상에서도 트리 구조와 동일한 알고리즘을 사용할 수 있다. 이 알고리즘은 대상 그래프가 일반적으로 루프를 포함하고 있기 때문에 "loopy" belief propagation 알고리즘이라 불린다. 대상 그래프가 리프를 포함하지 않기 때문에 이 알고리즘은 신뢰전파의 전파규칙을 살짝 수정할 필요가 있다. 우선 모든 변수의 초기 메시지는 1로 초기화 한다. 다음, 각 반복회수에서 위의 정의에 따라서 메시지를 갱신한다. 이때 리프나 트리 구조의 부분그래프에서 기지의 메시지가 전달될때까지 (즉, 메시지가 수렴할 때까지) 모든 메시지를 갱신한다. 대상 그래프가 트리 구조인 경우 loopy belief propagation 알고리즘은 대상 그래프의 직경과 동등한 반복수내에 원래 알고리즘에 의한 신뢰전파로 얻을 수 있는 메시지로 수렴한다.

Loopy belief propagation 알고리즘의 정확한 수렴조건은 아직 분명하지 않지만 통상 단일 루프 그래프에서는 수렴하는 것으로 알려져 있다. 또한 그 외에도 loopy belief propagation이 유일 고정점으로 수렴하기 위한 충분조건(필요조건 없음)이 몇 가지 존재한다. 한편 메시지가 발산하거나 각 반복 횟수에서 값이 진동하는 그래프도 존재한다. 이때에는 EXIT 차트 수법을 통하여서 신뢰전파의 경과나 수렴상황을 통해 근사적으로 가시화하여 조사하는 것또한 가능하다.

주변화를 위한 근사법으로는 그 밖에도 변분법이나 몬테칼로법을 포함한 몇가지 수법이 제안되어있다.

일반적인 그래프상에서 엄밀한 주변분포값을 구하기 위해선 정션트리 알고리즘을 꼽을 수 있다. 이 알고리즘은 대상그래프를 트리 구조로 수정하여 그 후 신뢰전파를 적용한다. 정션트리에서는 루프를 포함한 클러스터를 한개의 노드로 묶어 루프를 제거하여 신뢰전파의 수렴성을 보존한다.

유사 알고리즘과 복잡성

유사 알고리즘으로는 일반적으로 비터비 알고리즘을 꼽을 수 있다. 비터비 알고리즘은 max-product 또는 min-sum 알고리즘으로도 알려져 있으며 관련된 모델의 최대화문제를 푸는데 쓰인다. 구체적으로 설명하자면 이 알고리즘은 주변분포를 구하는 것이 아니라 대역 함수를 최대화하는 값$\mathbf {x}$을 구한다. 이것은 확률적으로 가장 일어나기 쉬운 값을 선택하는 것과 같으며 arg max기호를 써서 정의할 수 있다:

$\arg \max _{\mathbf {x} }g(\mathbf {x} ).$

이 문제의 풀이방법은 신뢰전파와 거의 같으며 합연산을 최대치연산으로 직변하는 것으로 족하다.

그래프 모델상에서의 주변화나 최대화와 같은 추정문제는 엄밀해나 상대오차이하의 근사값을 얻기위한 경우에는 NP-난해 문제이다. 정확하게는 위에서 정의된 주변하 문제는 #P완성 문제이며, 최대화 문제는 NP-완성이다.