[Data Mining] EM algorithm

EM algorithm을 공부해보자. 이건 사실 내가 생각보다 어렵다고 생각하여 계속 미루고 미뤄왔던 내용이었다. 그런데 용기를 내서? 공부를 해보니 생각보다 어려운 내용은 아니더라.

EM algorithm은 Expectation Maximization Algorithm이다. 왜 Expectation Maximization이라고 하는지 그리고 이게 뭐하는 것인지에 대하여 이번 포스팅에서 알아보려고 한다. 

우선, 이게 뭐하는 것인지 알아보자. 아주 간단한 개념이다. 아래와 같이 두 개의 Gaussian distribution이 있다고 해보자.(Normal Distribution = Gaussian Distribution)

파란 점섬으로 된 거는 무시하고, 두 개의 normal distribution만 봐보자. 노란색 그래프 중간에 있는 저 빨간색 점. 저 data가 주어졌을 때, 저 data가 노란 그래프에 속할지 파란 그래프에 속할지 알 수 없다. 상식적으로 노란 그래프에 속할 확률이 크고 파란 그래프에 속할 확률은 작다. 이걸 알아내기 위해서 EM을 쓰는 것이다. 

이번 포스팅은 수학 말고 편하게 예를 통해서 알아보자. 우리가 동전이 두개가 있다. 하나는 약간 구부러진 동전(A)이고, 또 하나는 그냥 일반 동전이다(B). 그리고 나는 아래와 같은 data를 받았다.

각 round마다 10번씩 동전을 던지고 앞면(H)가 나온 경우와 뒷면(T)가 나온 경우를 기록한 data이다. 각 round마다 어떤 동전을 사용했는지는 모른다.(이것이 포인트다.) 이 상황에서 각 round가 어떤 동전을 통해서 수행된 것인지 알아보자. 우선 우리는 동전 A에서 head가 나올 확률(pA)을 0.6, 동전 B에서 head가 나올 확률(pB)를 0.5라고 initialize해주자.

pA = 0.6

pB = 0.5

이 상황에서 산수같은 수학을 한번 해보자. 각 round에 대하여 선택된 동전이 A라고 가정할 때, 그리고 B라고 가정할 때의 확률을 구해보자.

round2을 예시로 설명을 해보면, A를 선택했을 때를 가정하면(choiceA), pA = 0.6이고 round2에서 head = 9, tail = 1이었으므로

이렇게 된다. 그러면 이 말은 무엇인가? 0.00403 : 0.00098은 403:98 즉, H가 9가 나오고 T이 1개 나왔을 경우는 동전 A를 사용했을 확률(0.00403)이 동전 B를 사용했을 확률(0.00098)보다 4배정도 높다는 것이다.(참고로 이런 것을 normalization해준다고 한다.) 이 계산을 모든 round에 대해서 해주면 아래와 같다. (여기까지의 작업을 expectation step이라고 한다.)

그러면 이제 normalized pA, normalized pB 확률을 각 round의 H, T count에 곱해주자. 이렇게 하면 동전 A B에 대하여 expected count를 구할 수 있다.

자 이제 우리가 할 일은 마지막에 있는 sum값을 가지고 새로운 확률을 구해보는 것이다.

위의 결과를 보면, A를 던져서 head가 나올 확률이 0.6에서 0.71로 증가했다. B도 이번에 증가했네? 여기까지의 작업을 maximization step이라고 한다.

이제 다음에 해야할 일은, 이 새로운 확률을 가지고 똑같은 일을 똑같이 해주는 것이다. 최초에 pA = 0.6, pB = 0.5를 가지고 했었던 그 일을 계속 반복해준다. 이 작업을 반복해주면 pA와 pB 값이 특정 값에 fix된다고 한다. 그 때까지 반복해주면 된다.

아주 쉬운 포스팅이다. 그런데 이 쉬운 개념이 내가 얼마전에 어려워서 그냥 넘어갔던 forward-backward algorithm의 기본 개념이라고 한다. 다음 포스팅은 이 forward-backward algorithm이다.