Tree Belief Propagation과 정보 전달

메시지는 바깥 부분의 요약이다

나무에서 i→j 메시지는 j 쪽을 제외한 i의 부분나무가 j의 값에 대해 주는 가중치를 요약합니다. i의 unary와 다른 이웃에서 받은 메시지를 곱한 뒤 i를 합합니다. 수신자 j의 메시지를 다시 곱하면 같은 정보가 중복될 수 있으므로 제외합니다.

메시지에 양의 상수를 곱해도 마지막 주변 정규화에서 상쇄됩니다. 구현은 안정성을 위해 각 메시지를 두 상태의 합으로 정규화합니다.

이 실습의 시간과 공간

그래프는 A−B−C−D이고 field h는 A에만 있습니다. 초기 메시지는 두 상태 각각 .5입니다. 동기 라운드에서는 이전 라운드의 모든 메시지로 다음 메시지를 한꺼번에 계산합니다. 한 라운드에서 정보가 한 간선씩 이동하므로 A의 영향이 D까지 가려면 세 라운드가 필요합니다.

Belief와 정확한 주변 비교

각 노드 belief는 unary와 모든 수신 메시지의 곱을 정규화한 값입니다. 파랑은 현재 belief, 주황은 16개 할당을 직접 열거한 정확한 주변입니다. J=1,h=.7에서 한 라운드 후 C,D의 파랑은 아직 .5지만 정확한 값은 각각 약 .6753,.6335입니다.

세 라운드 후에는 전체 나무의 정보가 전달되어 수치 오차 수준에서 일치합니다. 일반적인 나무에서는 적절한 두 방향 스케줄로 각 방향 메시지를 한 번씩 계산할 수도 있습니다. 동기 반복 횟수와 그런 스케줄의 메시지 연산 수는 같은 단위가 아닙니다.

정확성 조건과 다른 목적

이 결과는 나무 구조와 정확한 sum-product 연산에 의존합니다. 순환 그래프에 같은 반복을 적용하면 다른 성질을 갖습니다. 또한 노드 주변들의 최빈값을 각자 선택한다고 전체 joint MAP를 얻는 것은 아닙니다. Joint MAP에는 max-product와 적절한 역추적을 구분해 사용합니다.

확인 문제와 해설

1. j로 보내는데 j에서 온 메시지를 다시 쓰나요? 아니요. 수신자는 제외합니다.
2. 한 라운드의 작은 오차가 항상 전체 정보 전달을 뜻하나요? 아니요. 멀리 있는 관측의 경로를 확인해야 합니다.
3. J=0에서는? 변수들이 독립이어서 초기 local belief만으로도 정확합니다.

추가 읽기: Stanford CS228, Probabilistic Graphical Models.