[Pose Estimation] 신뢰전파(Belief propagation) 알고리즘

 

 

 

 

OpenPose 를 프로젝트에 적용하려고 "Convolutional Pose Machines" 이라는 논문을 읽던 중 belief map 이라는 개념이 나왔다. 여기서 칭하는 belief의 뜻이란 아래와 같이 쓰여져 있었다.

 

"We use the term belief in a slightly loose sense, however the belief maps described are closely related to beliefs produced in message passing inference in graphical models. The overall architecture can be viewed as an unrolled mean-field message passing inference algorithm that is learned end-to-end using backpropagation"

 

 

 

당최 무슨소린지 모르겠어서... 모르는 단어를 체크하고 구글링을 하기 시작했다. 

 

"We use the term belief in a slightly loose sense, however the belief maps described are closely related to beliefs produced in message passing inference in graphical models. The overall architecture can be viewed as an unrolled mean-field message passing inference algorithm that is learned end-to-end using backpropagation"

 

이러니 이해가 안가기 시작했고 논문이 어렵다고 느껴졌다. 

belief map 이라는게 graphical model에서 message passing inference 할 때 나오는 belief 개념과 연관이 있다는거고, 전반적인 구조는 end-to-end 로 이루어진 역전파 알고리즘을 이용하여 학습된 unrolled mean-field message passing inference algorithm 로 볼 수 있다는 말인데... 

 

일단 graphical model 이 뭔지, 거기서 message passing inference 는 무엇인지 알아야 이해가 갈 것 같아서, 이에 대한 내용을 담고있는, 구글링 하다가 찾아낸 핵심 키워드인 "Belief propagation" 에 대해서 내용을 설명하고자 한다. 확알못 이지만... 전반적인 흐름을 이해하고자... 최대한 쉽게 풀어 써보려고 한다. 

 

 

 

 

신뢰전파 (Belief Propagation)

 

신뢰전파 알고리즘은 Sum-product 메시지 전달(message passing)이라고도 한다. 이는 베이즈 네트워크 또는 마코프 네트워크등의 그래프 모델 상에 작용하는 메세지 전달 알고리즘이다. 이 알고리즘은 이미 관측한 노드의 상태를 토대로 아직 관측하지 않은 노드의 주변분포를 각각 계산하는 알고리즘이다. 쉽게말해서 그래프 상에서 관측된 특정한 확률 변수의 분포가 주어졌을 때, 그로부터 직간접 적으로 영향을 받는 모든 관측되지 않은 확률 변수의 Belief를 추정하는 것이다. 즉, 완전히 간결하게 말하자면 Graphical Model에서 일부 노드에 대한 확률 분포 또는 값이 주어졌을 때, 그 외 다른 노드에 해당하는 확률 변수의 분포를 추정하는 문제라고 할 수 있다. 

 

 

 

신뢰전파 알고리즘의 활용도

 

이 알고리즘은 주로 인공지능이나 정보이론의 분야에서 널리 사용되고 있으며, 저밀도 패리티 검사 부호, 터보 부호, 자유에너지 근사, 충족 가능성 문제를 다룰 수 있다. 

 

 

 

신뢰전파 알고리즘

 

결합확률질량 함수 p를 갖는 확률변소의 집합이 있을 때 특정 노드의 확률을 가리키는 주변 분포 x는 단순히 p를 x 이외의 모든 노드에 대한 합을 구하는 것으로 표현 가능한데, 이는 확률 변수들이 100개의 이진변수라고 한다면 전체 수는 엄청난 수에 달하여 컴퓨터상으로 계산하는 것이 힘들어진다. 그래서 신뢰 전파를 이용함으로써 대상 확률 변수의 그래프 구조를 이용함으로써 주변 분포의 계산을 보다 효율적으로 할 수 있다. 

 

신뢰전파 알고리즘은 두 단계로 구성이 된다.

 

1. Message Passing

2. Data Fusion

 

이 단계들을 거쳐서 각 노드의 확률 분포를 추정하게 된다. 노드 간에 어떤 정보를 전달한 후, 그 정보들을 융합하여 확률 분포를 추정하는 흐름이라고 보면 된다.

 

 

 

 

신뢰전파 알고리즘 예시

 

예시 문제 : 살인 사건에 3명의 용의자가 있다. 세명 중 한명은 무조건 살인자고, 지문이 검출된 흉기가 발견되었다.

 

A : 마지막으로 흉기를 사용한 사람(살인자)를 나타내는 확률변수

B : 마지막으로 흉기를 만진 사람을 나타내는 확률변수

C : 흉기에서 검출된 지문과 일치하는 사람을 나타내는 확률변수

 

확률 변수간 Dependency를 나타내면 위와 같다.

 

 

 

 

 

 

 

 

루트 노드의 Belief 값이 아래 그래프와 같이 주어졋다고 할 때, 아무런 증거가 없을 때 1번 용의자가 0.8 로 가장 살인마일 Belief가 가장 높은 상황이다. (각 열마다 각각 1,2,3 번 용의자에 대한 믿음의 정도를 나타냄) 이 때 해당 노드의 정보가 자식 노드로 전파되어 영향을 주게 된다.

 

 

 

 

 

 

 

 

 

 

 

원래 있던 Belief 값과 A->B 로 전달된 메세지 간의 행렬 곱으로 노드 B의 값을 업데이트 한다. 즉, A노드에서 1번 용의자가 0.8로 가장 살인마일 Belief 가 높은 상황이 확률 변수 B로 전파되어, B 노드에서 마지막으로 흉기를 만진 사람도 1번 용의자일 것이라는 믿음이 0.66 으로 가장 높게 평가되는 상황이라고 할 수 있다.

 

BEL(B) = aA(B)'rr(B) = a(0.80, 0.60, 0.50)(0.66, 0.17, 0.17) = (0.738, 0.142, 0.119) 

 

 

 

 

 

 

 

 

 

 

 

위 그림은 증거(Evidence), 즉 관측결과가 도착했을 때 신뢰 전파 상황이다. 지문 감식 결과가 각각 1, 2, 3번 용의자의 지문일 가능성이 (0.8, 0.6, 0.5) 라는 결과가 증거로 주어진 상황이다. 

 

증거가 주어졌으므로 노드 C에서는 부모 노드 B로 메세지가 전파되고, B에서는 해당 메세지를 이용하여 Belief 값을 위 그림의 수식과 같이 업데이트한다. 최종적으로 확률 변수 B의 분포는 흉기에 묻은 지문이 1번 용의자의 지문일 가능성이 가장 높은 것 (0.738)으로 평가된다. 

 

 

 

 

 

 

 

 

 

 

 

확률 변수 B의 값이 업데이트 되었으므로, 노드 B에서 노드 A로 메세지가 전파된다

 

 

 

 

 

 

(노란칸 마지막 결과 0.76 -> 0.076 임)

 

 

노드 B에서 노드 A로 전파된 메세지를 이용하여 확률변수 A의 Belief 값을 업데이트하면 노드 C에 주어졌던 증거의 전파가 완료된다. 

 

BEL(A) = aA(A)Tr(A) = a(0.75, 0.61, 0.54)(0.8, 0.1,0.1) = (0.84,0.085,0.076). 

 

위 그림의 수식을 살펴보면 증거가 주어지기 전 상황에 (0.8, 0.1, 0.1)의 분포를 보였던 확률변수 A가 증거가 주어진 후에는 (0.84, 0.085, 0.076)으로 업데이트 되는 것을 알 수 있다. 

 

간단히 말하자면, 지문 감식 결과가 흉기에 남은 지문의 주인이 1번 용의자일 가능성이 높은것으로 나오자, 1번 용의자가 살인마일 가능성이 0.8에서 0.84로 증가하고, 반대로 2번 3번 용의자가 살인마일 가능성이 줄어들었다. 정도로 설명 할 수 있다. 

 

 

 

 

 

 

참고자료 1 : Wei, Shih-En, et al. "Convolutional pose machines." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016.

 

참고자료 2 : Pearl, Judea. "Fusion, propagation, and structuring in belief networks." Artificial intelligence 29.3 (1986): 241-288.

 

참고자료 3 : http://tastyprogramming.tistory.com/7

 

참고자료 4 : http://tastyprogramming.tistory.com/17

 

참고자료 5 : https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%A2%B0%EC%A0%84%ED%8C%8C