정확·근사 추론과 수렴의 조건

같은 메시지 식이라도 구조가 다르다

나무에서 정확한 sum-product를 triangle에 반복하면 loopy belief propagation이 됩니다. 이 방법은 유용할 수 있지만 나무의 정확성 논증을 그대로 가져올 수 없습니다. 수렴, 빠른 계산, 주변의 정확성, 결합의 정확성은 서로 다른 성질입니다.

작은 정확한 Oracle 만들기

이 모형은 세 이진 변수라 8개 상태를 직접 열거해 정확한 주변을 구할 수 있습니다. 파랑은 반복별 최대 주변 오차입니다. 실제 큰 그래프에서는 이 정확 기준을 계산할 수 없어서 근사법을 쓰는 경우가 많으므로 같은 오차창이 항상 제공되지는 않습니다.

메시지 변화는 정답 오차가 아니다

주황 잔차는 연속 두 메시지 사이의 최대 변화입니다. 작아지면 반복이 고정점 근처임을 뜻하지만 그 고정점이 정확 사후라는 뜻은 아닙니다. 기본 양의 J와 A의 field에서는 수렴하는 듯 보여도 원래 정확 주변보다 확신이 과한 belief가 나타납니다.

감쇠는 mnew=(1−η)mold+η mproposal로 업데이트합니다. 양의 정규화 메시지의 볼록 결합이므로 정규화는 유지하지만, 모든 순환 모형에서 수렴이나 정확성을 보장하지 않습니다. 첫 0회는 이전 업데이트가 없어 잔차를 —로 표시합니다.

주변이 맞아도 결합이 다를 수 있다

h=0이면 반전 대칭으로 모든 노드 주변이 .5입니다. BP도 같은 주변을 줄 수 있어 파랑 오차가 수치 0에 가깝습니다. 그러나 정확한 이웃 부호 상관은 양수일 수 있고, 주변 부호 평균의 곱은 0입니다. 주변들의 곱을 정확한 joint로 대신하면 의존을 지웁니다. 이 곱은 BP의 pair belief라고 주장하는 값도 아닙니다.

어떤 조건을 확인해야 할까

유한 상태 전체 열거는 정확하지만 지수 비용이 들고, VE·junction tree는 중간 scope가 작을 때 효율적입니다. Tree BP는 적절한 완료 스케줄에서 정확합니다. Loopy BP는 특정 모형·수축 조건 등에서 안정성을 분석해야 합니다. Monte Carlo의 수렴과 오차는 또 다른 표집·혼합 가정에 의존합니다. 알고리즘 이름만으로 보장 수준을 결정하지 마세요.

확인 문제와 해설

1. 작은 잔차는 정확한 사후의 증명인가요? 아니요. 반복 안정성의 진단입니다.
2. 감쇠를 쓰면 항상 정확해지나요? 아니요. 안정화와 정확성을 구분합니다.
3. 노드 주변이 모두 맞으면 joint도 독립인가요? 아니요. 상관 구조가 남을 수 있습니다.

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