믿음 전파

1. 개요[편집]

믿음 전파(belief propagation, BP), 다른 이름으로 합-곱 알고리즘(sum-product algorithm)은 확률분포의 인자분해 구조를 그래프로 그린 뒤 이웃 노드끼리 메시지라는 국소 함수를 주고받게 하여 각 변수의 주변확률 $p(x_i)$ 를 계산하는 추론 알고리즘이다. 변수 $n$ 개짜리 결합분포를 정직하게 주변화하면 상태공간 크기가 $q^n$ 으로 폭발하지만, 분포가

$$p(x) = \frac{1}{Z} \prod_{a} f_a(x_a)$$

처럼 작은 인자들의 곱으로 쪼개진다면 합과 곱의 순서를 바꿔치기해서 국소 계산만으로 답을 낼 수 있다. BP는 그 순서 바꾸기를 “메시지 주고받기”라는 분산 규칙으로 재포장한 것이다. 펄(Pearl)이 1982년 베이지안 망 추론용으로 제안했고, 통신·통계물리·컴퓨터 비전에서 서로 독립적으로 재발명되다가 1990년대 후반에야 전부 같은 알고리즘이라는 것이 정리됐다.¹

2. 인자 그래프와 메시지 규칙[편집]

무대는 인자 그래프(factor graph)다. 변수 노드 $i$ 와 인자 노드 $a$ 를 두고, 인자 $f_a$ 가 변수 $x_i$ 를 인수로 쓰면 둘을 간선으로 잇는 이분 그래프다. 메시지는 간선마다 양방향으로 하나씩, 총 $2|E|$ 개가 흐른다.

$$\mu_{i \to a}(x_i) = \prod_{b \in N(i) \setminus a} \mu_{b \to i}(x_i)$$ $$\mu_{a \to i}(x_i) = \sum_{x_a \setminus x_i} f_a(x_a) \prod_{j \in N(a) \setminus i} \mu_{j \to a}(x_j)$$

변수 노드는 들어온 메시지를 곱해서 내보내고, 인자 노드는 자기 인자를 곱한 뒤 나머지 변수를 합으로 지워서 내보낸다. 규칙은 이게 전부다. 두 식 모두 “받은 쪽으로는 되돌려 보내지 않는다”($\setminus a$, $\setminus i$)는 점이 핵심인데, 이걸 빼먹으면 자기가 보낸 정보를 자기가 다시 증거로 세는 자기확신 루프가 된다.

수렴한 뒤 각 변수의 믿음(belief)은 들어온 메시지의 곱이다.

$$b_i(x_i) \propto \prod_{a \in N(i)} \mu_{a \to i}(x_i), \qquad b_a(x_a) \propto f_a(x_a) \prod_{i \in N(a)} \mu_{i \to a}(x_i)$$

마르코프 확률장처럼 인자가 전부 쌍별이면 식이 더 익숙한 꼴로 줄어든다. $m_{i \to j}(x_j) \propto \sum_{x_i} \psi_{ij}(x_i, x_j)\, \phi_i(x_i) \prod_{k \in N(i) \setminus j} m_{k \to i}(x_i)$. 상태 수가 $q$ 일 때 메시지 하나가 $O(q^2)$, 전체 한 바퀴가 $O(|E| q^2)$ 다. 인자의 차수 $d$ 가 크면 $q^d$ 로 뛰지만, 인자에 구조가 있으면(패리티 검사, 덧셈, min/max) 그 합을 $O(d)$ 나 $O(q \log q)$ 로 접을 수 있다.

구현에서 반드시 하는 두 가지가 있다. 매 갱신마다 메시지를 정규화할 것, 그리고 가능하면 로그 영역에서 계산할 것. 곱이 수십 번 겹치면 부동소수점 연산의 하한을 뚫고 0이 되며, 이건 은닉 마르코프 모형의 전방 변수가 언더플로하는 것과 완전히 같은 병이다. 주변확률만 필요하다면 정규화 상수를 버려도 되므로 매번 합을 1로 맞춰주면 그만이다.

3. 트리에서는 정확하고, 유한 번에 끝난다[편집]

그래프에 순환이 없으면 BP는 근사가 아니라 정확한 알고리즘이다. 이유는 단순하다. 트리에서 간선 하나를 자르면 그래프가 두 조각으로 갈라지고, 메시지 $\mu_{a \to i}$ 는 정확히 ”$i$ 쪽에서 떼어낸 반대편 부분트리를 전부 주변화한 결과”라는 확률적 의미를 갖는다. 각 변수의 믿음은 서로 겹치지 않는 조각들의 곱이므로 정확한 주변확률이 된다.

계산도 유한 번에 끝난다. 잎에서 뿌리로 한 번(상향 패스), 뿌리에서 잎으로 한 번(하향 패스) 쓸면 모든 메시지가 딱 한 번씩 계산되고 그걸로 끝이다. 총 메시지 계산 횟수는 $2|E|$ 회. 반복이나 수렴 판정이 아예 필요 없다. 사슬 그래프에 이걸 적용하면 상향/하향 패스가 각각 HMM의 전방/후방 재귀와 문자 그대로 같은 식이 되고, 잠재변수가 선형-가우시안이면 칼만 필터와 RTS 평활자가 나온다. 다시 말해 전방-후방, 칼만 평활, BP는 서로 다른 그래프 위의 같은 알고리즘이다.

4. 루피 BP와 베테 자유에너지[편집]

문제는 실전의 그래프가 대개 순환투성이라는 것이다. 격자 마르코프 확률장, LDPC의 태너 그래프, 대부분의 인자 그래프가 그렇다. 그래도 사람들은 그냥 돌렸다. 메시지를 전부 1로 초기화하고 수렴할 때까지 반복하는 루피 BP(loopy BP)다. 원리적 정당성이 전혀 없는데도 결과가 좋아서, 한동안은 “왜 되는지 모르겠지만 된다”가 공식 입장이었다.

정당성을 준 것이 예디디아·프리먼·와이스(2000)의 결과다. 루피 BP의 고정점은 정확히 베테 자유에너지의 정류점이다. 여기서 베테 자유에너지는 믿음 $\{b_a, b_i\}$ 의 범함수

$$F_{\text{Bethe}} = \sum_a \sum_{x_a} b_a(x_a) \ln \frac{b_a(x_a)}{f_a(x_a)} - \sum_i (d_i - 1) \sum_{x_i} b_i(x_i) \ln b_i(x_i)$$

이고, $d_i$ 는 변수 노드 $i$ 의 차수다. 제약은 정규화와 국소 일치($\sum_{x_a \setminus x_i} b_a = b_i$)뿐이며, 이 라그랑주 함수의 정류 조건을 풀면 앞의 메시지 갱신식이 그대로 튀어나온다. 즉 루피 BP는 떠도는 휴리스틱이 아니라 특정 변분 목적함수를 (비볼록하게) 푸는 알고리즘이고, $-\ln Z$ 의 베테 근사가 덤으로 나온다. 트리에서는 베테 엔트로피가 정확한 엔트로피와 일치하므로 근사가 아니게 되고, 위 절의 결과가 특수한 경우로 회수된다.²

이 관점은 곧장 확장을 낳았다. 인자 하나가 아니라 겹치는 영역(region)을 단위로 엔트로피를 근사하는 키쿠치 근사 → 일반화 BP(GBP)로 가면 정확도가 올라가고 대신 영역이 커진 만큼 비용이 오른다. 통계물리 쪽 언어로는 BP가 스핀글라스 이론의 캐비티 방법·TAP 방정식과 같은 물건이며, 무작위 $k$-SAT 문턱 근처를 공략한 서베이 전파는 여기에 “얼어붙은 변수”라는 상태를 하나 더 넣은 변형이다.

5. 수렴 조건과 감쇠[편집]

정류점이라는 사실이 수렴을 보장하지는 않는다. 루피 BP는 진동하거나 발산할 수 있고, 고정점이 여럿일 수도 있다. 알려진 충분조건들은 대체로 “결합이 약하면 된다”는 한 문장의 변주다.

• 계산 트리 관점(Tatikonda–Jordan) — 노드를 무한히 펼친 계산 트리 위 깁스 측도가 유일하면 BP가 수렴한다. 도브루신 조건 같은 유일성 판정을 그대로 빌려 쓴다.
• 수축 사상 관점(Ihler 등, Mooij–Kappen) — 메시지 갱신 사상이 적당한 거리에서 수축이면 유일 고정점으로 수렴한다. 판정식은 쌍별 퍼텐셜의 “세기”(동적 범위)로 만든 행렬의 스펙트럼 반지름이 1보다 작다는 형태다.
• 가우시안 BP — 결합분포가 가우시안이면 특히 깔끔하다. 수렴하기만 하면 평균은 정확하고, 분산은 일반적으로 틀린다(대개 과소추정). 정밀도 행렬이 워크-합산 가능(대각지배면 충분)하면 수렴이 보장된다.

강한 결합 영역, 즉 이징 모형식으로 말하면 저온에서 BP가 흔들리는 것은 물리적으로도 자연스럽다. 여러 상이 공존하는 영역이라 고정점도 여럿이기 때문이다. 실무 처방은 세 가지다. 첫째 감쇠(damping) — 로그 영역에서 $\log \mu^{t+1} = (1-\alpha)\log \mathcal{F}(\mu^t) + \alpha \log \mu^t$ 로 이전 메시지를 섞는다. $\alpha \approx 0.5$ 면 진동하던 것이 웬만하면 잡힌다.³ 둘째 비동기 스케줄 — 전부 동시에 갱신하는 대신 순서대로 갱신하거나, 잔차가 큰 메시지부터 갱신하는 잔차 BP를 쓴다. 셋째 볼록화 — 트리 재가중 BP(TRW)는 베테 엔트로피를 트리들의 볼록결합으로 바꿔 $\ln Z$ 의 상계를 주고, 목적함수가 볼록이라 고정점이 유일하다. 정확도를 조금 내주고 보장을 사는 거래다.

6. max-product와 MAP[편집]

주변확률이 아니라 최빈 상태 $\arg\max_x p(x)$ 가 필요하면 메시지 규칙에서 합을 최대로 바꾸기만 하면 된다.

$$\mu_{a \to i}(x_i) = \max_{x_a \setminus x_i} f_a(x_a) \prod_{j \in N(a) \setminus i} \mu_{j \to a}(x_j)$$

이것이 max-product이고, 로그를 씌우면 곱이 합이 되어 max-sum(max-plus) 재귀가 된다. 합-곱과 max-곱은 각각 $(+, \times)$ 반환과 $(\max, +)$ 반환 위에서 돌아가는 같은 알고리즘이라, 코드에서는 보통 연산자만 갈아 끼운다.

그래프가 사슬이면 max-sum은 정확히 비터비 알고리즘이다. 트리에서는 최대해가 유일한 한 max-product가 정확한 MAP를 준다. 순환이 있으면 보장이 약해지지만 완전히 없지는 않다 — 와이스와 프리먼의 결과에 따르면 max-product 고정점은 트리와 단일 루프로 이루어진 부분그래프 위에서는 최적이라는 국소 최적성을 갖는다. 또 max-product는 국소 주변 다면체 위 선형계획 완화의 쌍대와 밀접해서, TRW-S나 MPLP처럼 쌍대 목적을 단조 개선하도록 고친 변형들이 그래프 컷이 다루지 못하는 다중 라벨 문제의 표준 도구가 됐다.⁴

7. 응용[편집]

• LDPC 복호. BP의 최대 흥행작. 패리티 검사 행렬을 그대로 인자 그래프(태너 그래프)로 읽고, 채널에서 받은 로그우도비를 초기 메시지로 넣어 몇십 번 반복한다. 차수 $d$ 짜리 검사 노드의 합은 $\tanh\!\big(L_{a\to i}/2\big) = \prod_{j \neq i} \tanh\!\big(L_{j \to a}/2\big)$ 라는 항등식으로 $O(d)$ 에 접히고, 하드웨어에서는 이걸 다시 min-sum으로 근사하고 보정계수를 곱한다. 갤러거가 1962년에 제안했다가 잊혔고 매케이 등이 1990년대에 재발견했는데, 부호 길이를 키우면 샤논 한계에 수렴하는 성능을 낸다. 지금 DVB-S2·Wi-Fi·5G NR 데이터 채널이 전부 이걸 쓴다. 터보 부호의 반복 복호도 순환 있는 그래프 위 BP의 한 사례로 재해석됐다.
• 스테레오 비전과 저수준 비전. 시차(disparity)를 라벨로 둔 격자 MRF에서 루피 BP를 돌려 조밀 시차맵을 얻는다. 라벨 수 $L$ 이 100 근처라 $O(L^2)$ 메시지가 부담인데, 평활항이 절단 선형/이차이면 거리 변환으로 $O(L)$ 에 계산할 수 있고 거기에 거친-정밀 다중해상도와 체스판 스케줄을 얹으면 실시간에 근접한다. 한때 그래프 컷과 스테레오 벤치마크 상위권을 다퉜다.
• 일반 MRF 추론. 분할·잡음제거·인페인팅처럼 $Z$ 를 못 구해서 마르코프 연쇄 몬테카를로나 변분 추론으로 가야 하는 문제에서, BP는 평균장보다 정확하고 MCMC보다 빠른 중간 지대를 차지한다. 평균장이 상관을 통째로 버리는 데 비해 BP는 쌍별 상관을 살려두기 때문이다.
• 그 밖에. 저밀도 압축센싱의 근사 메시지 전달(AMP), 유사도 기반 군집화의 친화도 전파, 무작위 제약충족 문제의 서베이 전파, 그리고 그래프 신경망의 메시지 전달 층 — 마지막 것은 메시지 함수 자체를 학습으로 대체한 물건이라 계보상 BP의 직계 후손이다.

8. 관련 문서[편집]

• 마르코프 확률장 · 그래프 컷
• 은닉 마르코프 모형 · 비터비 알고리즘
• 칼만 필터 · 입자 필터
• 변분 추론 · 마르코프 연쇄 몬테카를로
• 동적 계획법 · 이징 모형 · 스핀글라스
• 그래프 신경망 · 심층 학습
• LDPC 부호 · 인자 그래프
• 부동소수점 연산 · 통계

9. Footnotes[편집]

1. 펄의 베이지안 망 신뢰 전파, 갤러거의 LDPC 반복 복호, 통계물리의 베테-파이얼스 근사와 캐비티 방법, 그리고 HMM의 전방-후방이 전부 같은 알고리즘이라는 것이 밝혀졌을 때 각 분야 사람들의 표정이 볼 만했을 것이다. 서로 30년씩 모르고 지냈다. ↩

2. “왜 되는지 모르겠지만 잘 된다”에서 “특정 자유에너지의 정류점이다”로 승격되는 데 근 20년이 걸렸다. 반대로 말하면, 그동안 논문 심사에서 “이론적 보장이 없다”는 지적을 받아온 사람들이 아주 많았다는 뜻이기도 하다. ↩

3. 감쇠 계수를 0.5로 놓고도 안 잡히면 결합이 진짜로 센 것이므로, 계수를 0.9까지 올리며 버티는 대신 모형이 상전이 영역에 들어가 있는 게 아닌지 먼저 의심하는 편이 빠르다. 수렴 안 하는 BP는 대개 알고리즘이 아니라 모형이 하는 말이다. ↩

4. 실무 감각으로 정리하면 이렇다. 이진 라벨에 부분모듈 에너지면 그래프 컷이 정확해를 주니 그쪽이 정답이고, 라벨이 많고 평활항이 절단형이면 BP 계열이나 TRW-S가 편하다. “일단 BP 돌려”는 라벨 구조를 안 따져도 되는 게 장점이지 정확도가 장점인 게 아니다. ↩