Expectation Maximization

부분적으로 관측된 데이터만을 가지고 있을 경우 효과적으로 모델링하기 위한 알고리즘이다.

주어진 통계적인 모델에서 D 가 관측이 된 데이터셋트이고, U는 관측이 안된 데이터 셋트라고 하자.
파라미터 T는 이 두 데이터셋트를 아우르는 모델을 기술한다고 할때 EM 알고리즘은 P(D|T)=sum_{U} P(D,U|T)를 최대값을 갖도록 하는 T를 예측한다.

알고리즘은 초기 추정치  T를 이용하여서, 아래의 두 단계를 거쳐서 다음 단계의 파라미터값은 예측한다.

1. E-step:: 이 단계에서는 주어진 파라미터셋트와 관측데이터를 이용하여서 관측이 안된 데이터에 대한 posterior probability 분포 P(U|D,T)를 예측한다.

2. M-step:: 이 단계에서는 E-step에서 얻어진 U에 대한 posterior 분포를 이용하여 전체데이터셋트(관측된 그리고 안된)에 대한 log-likelihood를 최대화시키는 모델파라미터 T'를 얻는다.

Q(T'| D,T) = sum_{U} P(U|D,T) * log( P(D,U|T) );

종종 E-step은 전체데이터를 아우를수 있는 통계적인 파라미터(평균,분산..)을 계산하는 과정으로 단순화 된다. 즉, 미리 전제된 통계모델을 기술하는 파라미터를 관측이 된 데이터에 기반하여서 예측한다.

K-Means 알고리즘은 가우시안 분포를 모델로 한 EM알고리즘으로 볼수 있다. 주어진 데이터가 여러개의 가우시안 분포의 혼합으로 여기고 각각의 가우시안 분포를 기술하는 파라미터를 구하는 작업이 된다. 아래의 그림은 주어진 평면상의 점분포를 두개의 가우시안 분포의 혼합으로 모델링하여 그 파라미터를 추정한 것이다.