용어 목록 > 신뢰 전파 (belief propagation)

신뢰 전파 (belief propagation)

쉽게 풀면

여러 사람이 소문을 주고받아 전체 상황을 파악하는 장면을 떠올리면 됩니다. 각 노드는 자기가 아는 정보와 이웃에게 받은 메시지를 합쳐 새 메시지를 만들어 다른 이웃에게 넘깁니다. 이 주고받기를 반복하면, 전체 확률분포를 한 번에 계산하지 않고도 각 변수의 확률을 알아낼 수 있습니다.

왜 중요한가

변수 수에 지수적으로 늘어나는 추론 비용을 그래프 구조를 이용해 크게 줄여 주는 대표적 방법입니다. 확률 그래프 모형에서 실제 계산을 가능하게 만드는 엔진 역할을 하며, 통신 분야의 오류 정정 부호 복호에도 그대로 쓰여 실용적 파급력이 큽니다. 여러 근사 추론 기법이 이 알고리즘의 변형으로 설명됩니다.

논문에서는 이렇게 쓰입니다

고리가 있는 그래프에서도 이 알고리즘을 근사적으로 돌려 값이 안정될 때까지 반복했다는 뜻입니다.

조금 더 깊게 보면

트리처럼 고리가 없는 그래프에서는 메시지 갱신이 유한 번에 끝나고 정확한 주변확률을 줍니다. 최대 확률을 갖는 배치를 찾을 때는 합 대신 최대를 쓰는 최대-곱 형태를 사용합니다. 고리가 있는 일반 그래프에 그대로 적용하는 반복적 신뢰 전파는 수렴이 보장되지 않지만 실제로는 잘 작동하는 경우가 많으며, 이는 베테 자유에너지의 정류점을 찾는 과정으로 해석됩니다.

주의할 점

결과가 항상 정확한 확률이 아니라, 고리가 있는 그래프에서는 근사값이며 수렴하지 않을 수도 있습니다. 역전파도 그래프 위에서 값을 거꾸로 전달하지만 그것은 손실에 대한 기울기를 구하는 미분 과정이므로, 이름이 비슷해도 목적이 전혀 다릅니다.

관련 용어