믿음 전파

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않기 때문에 대체로 검증되지 않은 상태로 남아 있다. 보다 정확한 인용문을 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2009년 4월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

총제품 메시지 전달이라고도 하는 믿음 전파는 베이시안 네트워크와 마르코프 무작위 필드 등 그래픽 모델에 대한 추론을 수행하기 위한 메시지 전달 알고리즘이다. 관측된 노드(또는 변수)를 조건으로 각 관측되지 않은 노드(또는 변수)에 대한 한계 분포를 계산한다. 믿음 전파는 인공지능과 정보 이론에서 일반적으로 사용되며, 저밀도 패리티 체크 코드, 터보 코드, 자유 에너지 근사치 및 만족도 등 수많은 응용 분야에서 경험적 성공을 입증했다.^[1]

이 알고리즘은 1982년 유대 펄에 의해 처음 제안되었는데,^[2] 그는 그것을 나무에 대한 정확한 추론 알고리즘으로 공식화하였고, 이후 폴리트로 확장되었다.^[3] 일반 그래프에서는 정확하지 않지만 유용한 근사 알고리즘으로 나타났다.^[4]

X={X_i}가 공동 질량 함수 p를 가진 이산 랜덤 변수 집합인 경우, 단일_i X의 한계 분포는 단순히 다른 모든 변수에 대한 p의 합계일 뿐이다.

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

그러나, 이것은 계산적으로 금방 금지된다: 100개의 이진수가 있다면, 2 ³⁹⁹ 6.338 × 10개의²⁹ 가능한 값을 합해야 한다. 폴리트리 구조를 이용함으로써, 믿음 전파는 여백을 훨씬 더 효율적으로 계산할 수 있게 한다.

총액 알고리즘 설명

믿음 전파 알고리즘의 변형은 여러 종류의 그래픽 모델(특히 Bayesian 네트워크와 Markov 무작위^[5] 필드)에 존재한다. 여기서는 인자 그래프에서 작동하는 변형을 설명한다. 인자 그래프는 변수 V와 인자 F에 해당하는 노드를 포함하는 초당적 그래프로서 변수와 변수들이 나타나는 인자 사이에 가장자리가 있다. 공동 질량 함수를 작성할 수 있다.

${\displaystyle p(\mathbf {x} )=\prod _{a}f_{a}(\mathbf {x} _{a})}$

여기서 x는_a 요인 노드 a에 대한 인접 변수 노드의 벡터다. 모든 베이시안 네트워크 또는 마르코프 무작위 필드는 부모 노드가 있는 각 노드에 대한 인자 또는 이웃이 있는 각 노드에 대한 인자를 각각 사용하여 인자 그래프로 나타낼 수 있다.^[6]

알고리즘은 숨겨진 노드들 사이의 가장자리와 함께 메시지라고 불리는 실제 가치 있는 기능들을 전달함으로써 작동한다. More precisely, if v is a variable node and a is a factor node connected to v in the factor graph, the messages from v to a, (denoted by ${\displaystyle \mu _{v\to a}}$) and from a to v (${\displaystyle \mu _{a\to v}}$), are real-valued functions whose domain is Dom(v), the set of values that can be taken by the v와 관련된 임의 변수 이 메시지들은 한 변수가 다른 변수에게 행사하는 "영향력"을 포함하고 있다. 메시지를 수신하는 노드가 변수 노드인지 요인 노드인지에 따라 메시지가 다르게 계산된다. 동일한 표기법 유지:

• 변수 노드 v에서 요인 노드 a로 전달되는 메시지는 인접한 다른 모든 요인 노드(수신자는 제외), 또는 수신인이 "1"과 동일한 상수 함수를 메시지로서 보낸다고 말할 수 있다.

${\displaystyle \forall x_{v}\in Dom(v),\\\mu _{v}=\prod _{a^{*}\in N(v)\setminus \{a\}}\mu _{a^{*}\}\mu(x_{v})}}$

여기서 N(v)은 v에 대한 인접(요인) 노드의 집합이다. ${\displaystyle N(v}$ ${\displaystyle )}$ ${\displaystyle \setminus \{\}}$ ${\displaystyle N(v)\setminus \{a\}}}$이(가) 비어 있는 $경우{\displaystyle {}_{}}$ ${\displaystyle {\mu v}_{}}$ ${\displaystyle {\to }_{}}$ $(x$) ${\style \mu _{v}}$이 균일한 분포로 설정된다$$.

• 요인 노드 a에서 변수 노드 v로 전달되는 메시지는 다른 모든 노드의 메시지가 포함된 인자의 산물이며, v와 관련된 변수를 제외한 모든 변수에서 소외된다.

${\displaystyle \forall x_{v}\in Dom(v),\;\mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}f_{a}(\mathbf {x} '_{a})\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}}).}$

여기서 N(a)는 인접(변수) 노드의 a 집합이다. If ${\displaystyle N(a)\setminus \{v\}}$ is empty then ${\displaystyle \mu _{a\to v}(x_{v})=f_{a}(x_{v})}$, since in this case ${\displaystyle x_{v}=x_{a}}$.

앞의 공식에서 알 수 있듯이 완전한 한계화는 완전한 공동 분포에 나타나는 것보다 단순한 용어의 생산물의 합으로 축소된다. 이를 sum-product 알고리즘이라고 하는 이유다.

일반적으로 각 메시지는 인접 메시지의 이전 값에서 반복적으로 업데이트된다. 메시지 업데이트에는 다른 일정을 사용할 수 있다. 그래픽 모델이 트리인 경우 최적의 스케줄링을 통해 각 메시지를 한 번만 계산한 후 수렴에 도달할 수 있다(다음 하위 섹션 참조). 인자 그래프에 주기가 있으면, 그러한 최적의 스케줄링은 존재하지 않으며, 일반적인 선택은 각 반복마다 모든 메시지를 동시에 업데이트하는 것이다.

수렴(융합이 발생한 경우) 시, 각 노드의 추정 한계 분포는 인접한 요소(정상화 상수 누락)에서 오는 모든 메시지의 곱에 비례한다.

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

마찬가지로, 한 인자에 속하는 변수 집합의 추정된 공동 한계 분포는 인자의 곱과 변수로부터의 메시지에 비례한다.

${\displaystyle p_{X_{a}(\mathbf {x} _{a})\propto f_{a}(\mathbf {x} _{a}\prod _{v\in N(a)\mu _{v}.}$

요인 그래프가 반복적인 경우(예: 나무 또는 숲) 이러한 추정 한계치는 실제로 유한한 반복 횟수의 실제 여백에 수렴된다. 이것은 수학적 유도를 통해 알 수 있다.

트리에 대한 정확한 알고리즘

인자 그래프가 나무인 경우, 믿음 전파 알고리즘은 정확한 여백을 계산한다. 또한, 메시지 업데이트의 적절한 스케줄링으로, 2단계 후에 종료된다. 이러한 최적의 스케줄링은 다음과 같이 설명할 수 있다.

시작하기 전에 그래프는 한 노드를 루트로 지정하여 방향을 잡는다. 다른 노드 하나에만 연결된 모든 비루트 노드를 리프라고 한다.

첫 번째 단계에서 메시지는 안쪽으로 전달된다. 잎에서 시작하여 각 노드는 루트 노드를 향해 (유일한) 가장자리를 따라 메시지를 전달한다. 트리 구조는 메시지를 전달하기 전에 인접한 다른 모든 노드에서 메시지를 얻을 수 있음을 보장한다. 이는 루트가 인접한 모든 노드로부터 메시지를 얻을 때까지 계속된다.

두 번째 단계는 메시지를 다시 전달하는 것이다: 근본부터 시작해서 메시지는 역방향으로 전달된다. 알고리즘은 모든 잎이 메시지를 받으면 완성된다.

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

원래는 반복^{[disambiguation needed]} 그래픽 모델을 위해 설계되었지만, 믿음 전파 알고리즘은 일반 그래프에서 사용될 수 있다. 그래프는 일반적으로 주기 또는 루프를 포함하기 때문에 알고리즘을 루피 믿음 전파라고 부르기도 한다. 그래프에 리프가 없을 수 있기 때문에 메시지 업데이트의 초기화 및 스케줄링은 (앞서 설명한 반복 그래프 스케줄과 비교하여) 약간 조정되어야 한다. 대신, 모든 가변 메시지를 1로 초기화하고 위의 동일한 메시지 정의를 사용하여 반복할 때마다 모든 메시지를 업데이트한다(알려진 나뭇잎이나 트리 구조 서브그래프에서 오는 메시지는 충분한 반복 후에 더 이상 업데이트할 필요가 없을 수도 있다). 트리에서 이 수정된 절차의 메시지 정의가 트리 직경과 동일한 반복 횟수 내에서 위에 주어진 메시지 정의 집합으로 수렴된다는 것을 쉽게 알 수 있다.

루프가 융합되는 정확한 조건은 여전히 잘 알려져 있지 않다. 단일 루프를 포함하는 그래프에서는 대부분의 경우 수렴되지만 얻은 확률은 부정확할 수 있다.^[7] 고유한 고정점에 대한 루피적인 믿음 전파의 수렴을 위한 몇 가지 충분한(그러나 필요하지 않은) 조건이 존재한다.^[8] 수렴에 실패하거나 여러 상태 사이에서 반복적으로 진동하는 그래프가 존재한다. EX와 같은 기술IT 관리도는 신념 전파의 진행 상황을 대략적으로 시각화하고 수렴을 위한 대략적인 테스트를 제공할 수 있다.

변이법, 몬테카를로법 등 다른 근사치적 한계화 방법이 있다.

일반 그래프에서 정확한 한계화의 한 가지 방법을 접속 트리 알고리즘이라고 하는데, 이는 단순히 트리가 될 것을 보장한 수정된 그래프에서 전파되는 믿음일 뿐이다. 사이클을 단일 노드로 클러스터링해 사이클을 없애는 것이 기본 전제다.

관련 알고리즘 및 복잡성 문제

유사한 알고리즘을 일반적으로 Viterbi 알고리즘이라고 하지만, 최대화 또는 가장 개연성 있는 설명의 관련 문제를 해결하는 max-product 또는 min-sum 알고리즘의 특수한 사례로도 알려져 있다. 한계치를 해결하려고 시도하는 대신, 여기서 목표는 글로벌 함수를 최대화하는$$ $값{\displaystyle \mathbf{}}$ x ${\$를) 찾는 것이며, arg max를 사용하여 정의할 수 있다.

${\displaystyle \chostname {*} {\arg \max }_{\mathbf {x} }g(\mathbf {x} )}$

이 문제를 해결하는 알고리즘은 신념 전파와 거의 동일하며, 정의에서 합계는 maxima로 대체된다.^[9]

한계화와 최대화와 같은 추론 문제는 그래픽 모델에서 정확하고 대략적으로(적어도 상대적 오류의 경우) 해결하기 어려운 NP라는 점에 주목할 필요가 있다. 보다 정확히 말하면 위에서 정의한 한계화 문제는 #P-완전, 최대화는 NP-완전이다.

믿음 전파의 기억력 사용은 아일랜드 알고리즘의 사용을 통해 감소시킬 수 있다(시간 복잡성의 작은 비용으로).

자유 에너지와의 관계

총생산 알고리즘은 열역학에서 자유 에너지의 계산과 관련이 있다. Z를 파티션 함수가 되게 하라. 확률 분포

${\displaystyle P(\mathbf {X} )={\frac {1}{Z}\prod _{f_}{j}{j}(x_{j})}}$

(인자 그래프 표현에 따라) 는 다음과 같이 계산된 시스템에 존재하는 내부 에너지의 척도로 볼 수 있다.

${\displaystyle E(\mathbf {X} )=-\log \prod _{f_}{j}{j}(x_{j}).}$

그때 시스템의 자유 에너지는

${\displaystyle F=U-H=\sum _{\mathbf {X}}}E(\mathbf {X})++\sum _\mathbf {X}{\mathbf {X}}\log P(\mathbf {X}).}$

그런 다음, 그러한 시스템의 자유 에너지가 최소화된 지점을 나타내는 총량-제품 알고리즘의 수렴 지점을 나타낼 수 있다. 마찬가지로 사이클이 있는 그래프에서 반복적 믿음 전파 알고리즘의 고정 지점이 자유 에너지 근사치의 정지 지점임을 알 수 있다.^[10]

일반화된 신앙 전파(GBP)

믿음 전파 알고리즘은 보통 인자 그래프에 메시지 업데이트 방정식으로 표시되며, 변수 노드와 인접 인자 노드 사이의 메시지를 포함하며, 그 반대의 경우도 마찬가지다. 그래프에서 영역 간 메시지를 고려하는 것은 믿음 전파 알고리즘을 일반화하는 한 방법이다.^[10] 메시지를 교환할 수 있는 그래프에서 영역 집합을 정의하는 방법에는 여러 가지가 있다. 한 가지 방법은 물리학 문헌에서 기쿠치가 도입한 사상을 사용하며,^[11][12][13] 기쿠치의 군집 변동법으로 알려져 있다.^[14]

신념 전파 알고리즘의 성능 향상은 필드(메시지)의 분포에서 복제본 대칭성을 파괴함으로써 달성할 수 있다. 이러한 일반화는 측량 전파(SP)라는 새로운 종류의 알고리즘으로 이어지며, 이는 만족도^[1], 그래프 컬러링과 같은 NP 완전 문제에서 매우 효율적인 것으로 입증되었다.

클러스터 변동 방법과 조사 전파 알고리즘은 믿음 전파의 두 가지 다른 개선이다. 일반화된 측량 전파(GSP)라는 명칭이 두 일반화를 병합하는 알고리즘에 할당되기를 기다리고 있다.

가우스 신앙 전파(GaBP)

가우스 신앙 전파는 기본 분포가 가우스 분포일 때 신념 전파 알고리즘의 변형이다. 이 특별한 모델을 분석한 첫 번째 작품은 와이스와 프리만의 정석적인 작품이었다.^[15]

GaBP 알고리즘은 다음과 같은 한계화 문제를 해결한다.

${\displaystyle P(x_{i}}={\frac {1}{Z}\int _{j\neq i}\ex(-1/2x^{T}Ax+b^{T}x)\,dx_{j}}$

여기서 Z는 정규화 상수, A는 대칭 양정확정 행렬(역 공분산 행렬 a.k.a. 정도 행렬)이고 b는 시프트 벡터다.

동등하게 가우스 모델을 사용하여 한계화 문제의 해결은 MAP 할당 문제와 동일하다는 것을 알 수 있다.

${\displaystyle {\underset {x}{\operatorname {argmax}}}}{\frac {1}{1}{Z}}\exp(-1/2x^{T}Ax+b^{T}x)).}$

이 문제는 또한 다음과 같은 2차 형태의 최소화 문제와도 같다.

${\displaystyle {\underset {x}{\operatorname {min}}}}}}}}}\ 1/2x^{T}Ax-b^{T}x.}$

또한 방정식의 선형 시스템과 동일하다.

$Ax=b 디스플레이 스타일 Ax=b).}$

GaBP 알고리즘의 수렴은 (일반 BP 사례에 비해) 분석이 더 쉬우며 충분한 수렴 조건이 두 가지 알려져 있다. 첫 번째 것은 정보 매트릭스 A가 대각선으로 우세한 2000년에 와이스 외 연구진에 의해 공식화되었다. 두 번째 수렴 조건은 2006년 존슨 외 매트릭스의 스펙트럼 반경이 공식화되었다.^[16]

${\displaystyle \rho(I- D^{-1/2}AD^{-1/2} )<1\,}$

여기서 D = diag(A) 이후, Su와 Wu는 동기식 GaBP와 감쇠된 GaBP에 필요한 충분한 수렴 조건과 비동기식 GaBP에 대한 또 하나의 충분한 수렴 조건을 확립하였다. 각각의 경우에 대해 수렴 조건은 1) 집합(A로 결정)이 비어 있지 않은지 확인하는 것, 2) 특정 매트릭스의 스펙트럼 반경이 1보다 작다는 것, 3) 특이성 문제(BP 메시지를 믿음으로 변환할 때)가 발생하지 않는 것을 포함한다.^[17]

GaBP 알고리즘은 선형 대수 영역과 연계되어 있으며,^[18] A는 정보 매트릭스, b는 시프트 벡터인 등식 Ax = b의 선형 시스템을 해결하기 위한 반복 알고리즘으로 GaBP 알고리즘을 볼 수 있는 것으로 나타났다. 경험적으로 GaBP 알고리즘은 자코비법, 가우스-세이델법, 연속적인 과잉완화법 등과 같은 고전적 반복법보다 더 빠르게 수렴되는 것으로 나타난다.^[19] 또한, GaBP 알고리즘은 전제 조건의 결합 그라데이션 방법의^[20] 수치적 문제에 면역이 되는 것으로 나타난다.

신드롬 기반 BP 디코딩

BP알고리즘의 이전 설명. P(es){P(es)\displaystyle}, s{\displa을 계산한 등가 form,[21] 있지만 X{X\displaystyle} 받은 시설을 대강의 한계 확률 P()X){P()X)\displaystyle}을 산정하는codeword-based 해독, 호출됩니다.ysty$le$ s$}$은(는) 수신된 $코드워드{\displaystyle }$ X ${\displaystyle$ X}의$$증후군이며 e$$ ${\displaystyle$ e$}$은 $디코딩된$ 오류다. 디코딩된 입력 벡터는 $x{\displaystyle }$= ${\displaystyle X}$+ ${\displaystyle e}$ ${\displaystyle x=X+e}$ 입니다$.$ 이 변동은 질량 함수 $f{\displaystyle {}_{}}$ ${\displaystyle a_{}}$ (${\displaystyle {}_{}{X}_{}}$ a${\displaystyle {}_{}}$) ${\displaystyle f_{a}(X_{a})$의 해석만 변경한다$.$ 명시적으로 메시지는

${\displaystyle \forall x_{v}\in Dom(v),\\\mu_{v}=P(X_{v})\prod _{a^{*}\in N(v)\setminus \a\}\mu _{a^{*}\}{v}.}$

where ${\displaystyle P(X_{v})}$ is the prior error probability on variable ${\displaystyle v}$${\displaysty$$le \forall x_{v}\in Dom(v),\;\mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}\delta ({\text{syndrome}}({\mathbf {x} }'_{v})={\mathbf {s} })\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}}).$$}$

이 신드롬 기반 디코더는 수신된 비트에 대한 정보를 필요로 하지 않기 때문에 양자 코드에 적응할 수 있는데, 여기서 유일한 정보는 측정 증후군이다.

바이너리 ${\displaystyle \mathrm{케이스}}$인 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}${ 0${\displaystyle }$, ${\displaystyle 1}$ ${\displaystyle \}}$ ${\displaystyle x_{i}\in \{0,1\}}$의 경우$,$ 이러한 메시지는 단순화하여 $복잡도$에서^[22][23] 2${\displaystyle {}^{}}${ ${\displaystyle v^{}}$ ${\displaystyle {\}}^{}}$+ ${\displaystyle {N(v}^{}}$) $displaystyle 2^{v\}$+ N$(v) }$의 지수적인 감소를 유발할 수 있다.

Define log-likelihood ratio ${\displaystyle l_{v}=\log {\frac {u_{v\to a}(x_{v}=0)}{u_{v\to a}(x_{v}=1)}}}$ , ${\displaystyle L_{a}=\log {\frac {u_{a\to v}(x_{v}=0)}{u_{a\to v}(x_$${v}=1$ 그러면

${\displaystyle v\to a:l_{v}=l_{v}^{(0)+\sum _{a^{*}\in N(v)\setminus \{a\}}}}(L_{a^{*})}}}}$

$a\to v:L_{a}=(-1)^{s_{a2}}\tanh ^{-1}\prod_{v^{*}\in N(a)\setminus \{v\}}\tanh(l_{v^{*/2)}$

여기서 $l{\displaystyle {}_{}^{}}$ (${\displaystyle {}_0^{}}$)${\displaystyle {}_{}^{}}$= ${\displaystyle \mathrm{로그}}$⁡${\displaystyle }$(${\displaystyle \mathrm{P}}$( ${\displaystyle x_{}}$ v${\displaystyle {}_{}}$= 0${\displaystyle }$)${\displaystyle }$/ ${\displaystyle P}$( ${\displaystyle \mathrm{x}}$ ${\displaystyle v_{}}$= 1${\displaystyle }$)${\displaystyle }$= ${\displaystyle \text{constance}}$ ${\$$x_{v}=1$)$={\text{const}}}$

후방 로그 우도비는 $l{\displaystyle {}_{}}$ ${\displaystyle v_{}}$= l ${\displaystyle v_{}^{}}$( ${\displaystyle 0_{}^{}}$)${\displaystyle {}_{}^{}}$+${\displaystyle \underset{}{}}$∑${\displaystyle \underset{}{N}}$( v${\displaystyle \underset{}{}}$)${\displaystyle \underset{}{}}$( ${\displaystyle L_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle l_{v}=l_{v}^{0)+\sum _{a\in N(v)}(L_{a$})}({a$})$로 추정할 수 있다.

참조

추가 읽기

• 빅슨, 대니 (2009). 가우스 믿음 전파 자원 페이지 —Matlab 소스 코드뿐만 아니라 최근 출판물을 포함하는 웹 페이지.
• Bishop, Christopher M. (2006). "Chapter 8: Graphical models" (PDF). Pattern Recognition and Machine Learning. Springer. pp. 359–418. ISBN 978-0-387-31073-2. Retrieved 20 March 2014.
• 코클란, 제임스 (2009). 믿음 전파에 대한 자습서 소개.
• Löliger, Hans-Andrea (2004). "An Introduction to Factor Graphs". IEEE Signal Processing Magazine. 21 (1): 28–41. Bibcode:2004ISPM...21...28L. doi:10.1109/MSP.2004.1267047.
• 매켄지, 다나(2005년). 2005년 7월 9일, 새로운 과학자인 "통신 속도는 터미널 속도에 가깝다. 이슈 2507 (등록 필요)
• Wymeersch, Henk (2007). Iterative Receiver Design. Cambridge University Press. ISBN 978-0-521-87315-4.
• Yedidia, J.S.; Freeman, W.T.; Weiss, Y. (January 2003). "Understanding Belief Propagation and Its Generalizations". In Lakemeyer, Gerhard; Nebel, Bernhard (eds.). Exploring Artificial Intelligence in the New Millennium. Morgan Kaufmann. pp. 239–269. ISBN 978-1-55860-811-5. Retrieved 30 March 2009.
• Yedidia, J.S.; Freeman, W.T.; Weiss, Y. (July 2005). "Constructing free-energy approximations and generalized belief propagation algorithms". IEEE Transactions on Information Theory. 51 (7): 2282–2312. CiteSeerX 10.1.1.3.5650. doi:10.1109/TIT.2005.850085.