[ML개론] (22) Marginalization & Elimination

이전 글에서 Conditional prob, likelihood, most probable assignment inference를 다뤘다. 결국 특정 확률의 inference를 위해선 full joint에서부터 시작하여 이를 계속 marginalize out하여야 함을 확인했다. 가령 P(A, B, MC)의 likelihood inference를 위해선 JC, E factor에 대해 marginalize out한 full joint prob을 구해야한다. 

 

그런데 이러한 inference algorithm을 Big-oh notation으로 평가하면 어떨까? r.v의 갯수가 늘어날수록 더 많은 multiplication으로 이어지기 때문에 연산이 늘어나게 된다. 가령 n개의 variable이 존재하고 이 중 k개가 hidden variable인 상태로 full joint를 계산해야된다면 k개 모두를 marginalize out해야하기 때문에 2^k개의 full joint prob을 계산한 뒤 모두 더해야한다. 

 

그럼 복잡한 계산을 간소화할 방법은 없을까? 위 예시를 보면 JC, E가 hidden variable로 marginalize out되어있었는데, P(MC|A)와 P(B)는 JC나 E를 variable로 갖고 있지 않기 때문에 constant의 형태로 sigma에서 꺼내줘도된다. 이렇게 되면 계산은 2^k에서 2^2로 크게 줄어든다.

 

Elimination은 이처럼 복잡한 연산을 간소화해주는 체계적인 도구다.

가령 P(E|JC,MC)를 계산한다면 이는 P(E, JC, MC)/P(JC,MC)로 표현된다. 이 때 1/P(JC, MC)의 normalizing term을 constant a의 형태로 편의상 변환시켜준다.

P(E, JC, MC, B, A) given E, JC, MC = T을 계산해야한다고 가정해보자. 그럼 우리는 a*P(E)*Σ_bP(b)*Σ_aP(a|b,E)*P(JC|A)*P(MC|A)로 표현할 수 있다. 이전에서 살핀것과 같이 sigma에 속하지 않는 term들은 밖으로 빼주는 것이다. 이러한 작업은 term들을 Bayesian Network 상의 Topological order로 정렬해줌으로서 실현가능하다. 가령 이 예시의 경우 {B, E, A, JC, MC}가 그 topological order이다. 

 

다시 정리해보자.

첫째, P(E,JC,MC=T)라는 joint prob.을 계산하기 위해선 이를 factorize하여 conditional prob.으로 나눠야한다. 

둘째, 이 때 conditional prob에 대해 모든 확률을 summation하기 힘드니까 topological order로 정렬한 뒤 summation의 대상이 되는 term을 공유하는 conditional prob.에 대해서만 summation을 진행한다. 

셋째, 위와 같이 정리된 conditional prob.들의 곱에 대해, 기존에 알려진 확률분포를 활용하여 계산을 실시한다. 

 

우선 P(E)=T는 0.002로 고정되어있다. 다음으로는 P(JC|A)와 P(MC|A)인데 이들은 r.v A에 영향을 받는 확률값이다. 우선은 A=T일때 각 0.9, 0.7, A=F일때 각 0.05, 0.01이다. 이들은 given A일때 상호독립적인 관계에 놓이기 때문에 서로 값을 곱해준다. 그럼 Σ_aP(A|B,E)(P(JC|A)*P(MC|A))가 된다. 이 때 P(JC|A)*P(MC|A)는 T일때 0.63, F일때 0.0005의 확률값을 갖는다.

 

더 이어나가면 P(A|B,E) 또한 B,E의 T/F에 따라 총 4가지의 경우의 수에 대한 확률분포가 존재한다. 그럼 A는 B,E의 T/F에 의해 결정되고, 이 A가 이전에 살핀 JC, MC의 확률값을 결정짓는다. 그럼 말단의 위치한 JC, MC는 B,E,A에 영향을 받으니 B,E,A의 T/F에 따라 총 8가지 경우의수에 관한 확률분포가 존재한다. 가령 B=F, E=T, A=F인 관측치가 있다면 P(A=F|B=F,E=T)는 0.71이고, 잇따른 P(JC=T|A=F)*P(MC=T|A=F)는 0.0005이니 이둘의 곱이 최종적인 확률값이 된다. 이 작업을 총 8번 해주면 된다. 그런데 우리는 Σ_a를 통해 A=T/F의 확률값을 더해줘야하니 8가지의 경우의수 중 A에 대해 marginalize out하여 f_AJM을 a에 대해 무관한 확률값으로 만들어준다. 

추가적으로 f_b(b)*f_AJM(b,e)를 구해야하는데 마찬가지다. f_AJM의 4가지 확률이 존재할텐데 B=T/B=F인 경우에 대해 P(B=T), P(B=F)의 확률을 각각 곱해서 marginalize out해주면 된다. 이렇게 구한 값을 최종적으로 f_E(E=T) 확률과 곱해주면 우리는 E=T/F에 따라 확률값이 결정되는 variable elimination 과정을 끝낸것이다.