1 분 소요

중간고사 성적은 40점 만점에 36점이 나왔다. 1등은 37점인데 어디셔널 포인트를 안 했다고.. 난 다 받았으니 종합 39점으로 공동 1등? 평균 28점에 중앙값 29점.

화요일(10/29)은 문제 복기랑 풀이만 해주시고 30분도 안 되어서 수업 종료! 그래서 목요일치만 기록한다.

Oct 31 (Thu)

Inference by Enumeration은 오래 걸려

지난 Bayes Net 2장에서는 열거(enumeration)를 통한 조건부 확률 분포 추정법을 배웠다. 각 evidence가 추가될 때마다 추정되는 조건부 확률이 바뀌니까, 모든 hidden variables들까지 포함한 결합 분포를 구해서, sum out하고 normalize하는 방식이었다. 즉 local conditional distributions의 곱으로 베이지안 네트워크를 표현하는 방식

그런데 이 방식은 너무 느리다. 모든 hidden variables를 추가했다가(=inflating=joining), 다 summing out해야 하므로(=deflating=marginalizing) 너무 시간이 오래 걸린다. 해결책이 없을까

Inference by Variable Elimination

해결 방법은 interleave(=intersperse: 번갈아 포개다/사이사이에 배치하다)하게 joining하고 marginalizing하는 것이다! 무슨 말이냐, 각 sub-joint 분포에 대해 하나씩 부분적으로 sum out하는 것이다. 인플레이션과 디플레이션을 hidden 변수들을 하나씩 추가하며 계속 수행하는 방식이다.

수식으로 보면 더 간단할 것이다.

\[P(B|j,m)=\alpha \sum_{e,a}P(B)P(e)P(a|B,e)P(j|a)P(m|a)\]

보다는

\[P(B|j,m)=\alpha P(B)\sum_eP(e)\sum_aP(a|B,e)P(j|a)P(m|a)\]

와 같이 안쪽으로부터 점차 시그마를 쓰는 것이, 전체 계산의 복잡도를 줄일 수 있다는 것이다. 시그마는 최대한 식의 안쪽으로 집어넣고, 시그마와 무관한 분포들은 최대한 바깥쪽으로 빼내어 계산을 줄인다. 이를 Inference by Variable Elimination라고 한다.

이때 변수는 각각의 차원을 의미하는데, 이는 곧 각 변수는 테이블(표)를 갖게 된다는 것이다. 강의 노트의 Factor Type을 살펴보자. 고정된 변수는 차원을 잃어 버린다. 이처럼 각 확률 변수들이 가질 수 있는 모든 값들을 저장하는 다차원 배열을 Factor라고 한다.

기존의 열거(enumeration) 방식은 pointwise products, 즉 점별로 곱하여 맨 마지막에 합쳤기에 계산량이 많았지만, 변수 제거(variable elimination) 방식은 각 변수별로 joint와 summing을 한 단계씩 하기에 전체 계산량이 줄어든다.

항상 Local CPTs로부터 출발을 하자. 이제 hidden variabels들을 하나씩 꺼내오는데, 이 변수 H를 언급(mention)하는 모든 분포들을 다 꺼내와야 정확히 계산이 된다.

Order Matters

이때 계산을 위한 팁이 있다. 부모부터 나열해야 계산량이 줄어든다. 부모 확률 변수 Z가 자식 확률 변수 A~D에 영향을 주는 베이지안 네트워크를 생각해보자. D의 확률을 계산한다면

\[\begin{align} P(D)&=\alpha \sum_{z,a,b,c}P(z)P(a|z)P(b|z)P(c|z)P(D|z)\\&=\alpha \sum_zP(z)\sum_aP(a|z)\sum_bP(b|z)\sum_cP(c|z)P(D|z)\end{align}\]

가

\[\begin{align} P(D)&=\alpha \sum_{a,b,c,z}P(a|z)P(b|z)P(c|z)P(D|z)P(z)\\&=\alpha \sum_a\sum_b\sum_c\sum_zP(a|z)P(b|z)P(c|z)P(D|z)P(z)\end{align}\]

보다 계산이 더 빨라 보인다. 그러니 순서가 중요하다는 것을 알겠지? 34페이지의 예제로는 제거 방식이 약 1000배 더 빠르다고 하니, 앞으로는 enumeration보단 elimination으로 계산하자.

출처: 인공지능(COSE361) ㅇㅅㅅ 교수님

참고