EM 알고리즘

기댓값 최대화 알고리즘(expectation-maximization algorithm, 약자 EM 알고리즘)은 관측되지 않는 잠재변수에 의존하는 확률 모델에서 

최대가능도(maximum likelihood)나 최대사후확률(maximum a posteriori, 약자 MAP)을 갖는 매개변수를 찾는 반복적인 알고리즘이다. 

EM 알고리즘은 매개변수에 관한 추정값으로 로그가능도(log likelihood)의 기댓값을 계산하는 기댓값 (E) 단계와 

이 기댓값을 최대화하는 변수값을 구하는 최대화 (M) 단계를 번갈아가면서 적용한다. 

최대화 단계에서 계산한 변수값은 다음 기댓값 단계의 추정값으로 쓰인다.

최대가능도는 관측되지 않은 모든 변수 각각에 대하여 로그가능도를 미분한 식을 풀어서 구할 수 있다. 

하지만 잠재변수를 포함하는 통계 모델의 수식들은 매우 복잡하여 이와 같은 방법으로는 풀 수 없다. 각각의 변수에 관해 미분한 식은 서로 얽혀있어 한 수식의 해를 구하기 위해서는 다른 식의 해를 구해야 하는데, 이 수식의 해 또한 이전 식의 변수를 포함하기 때문이다. 따라서 이 경우 정확한 해를 계산하는 것은 불가능하다.

하지만 EM알고리즘을 이용하면 이 문제의 해를 수치적으로 계산할 수 있다. 우선 서로 얽혀있는 두 식과 각각의 변수들을 가정해보자. 두 식은 얽혀있기 때문에 한 식의 변수는 다른 식의 변수일 수 있다. 첫번째 식의 변수값을 임의로 잡은 후 이 변수값으로 두번째 식의 변수값을 추정한다. 그렇게 구한 변수값으로 다시 첫번째 식의 변수값을 추정하고 이를 반복한다. 특정한 상황에서 충분히 많은 반복을 거치면 각각의 변수들이 일정한 값으로 수렴한다는 것을 보일 수 있다. 

관측할 수 있는 확률변수 ${\displaystyle \mathbf {X} }$와 관측할 수 없는 확률변수 ${\displaystyle \mathbf {Z} }$, 그리고 매개변수 ${\displaystyle {\boldsymbol {\theta }}}$가 있을 때, ${\displaystyle (\mathbf {X} ,\mathbf {Z} )}$에 대한 확률분포는 ${\displaystyle L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )=p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})}$로 주어져 있다. 이 때 최대가능도를 계산하고 싶은 경우, 최대화하려는 가능도 함수는 ${\displaystyle L({\boldsymbol {\theta }};\mathbf {X} )=p(\mathbf {X} |{\boldsymbol {\theta }})=\sum _{\mathbf {Z} }p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})}$로 정의할 수 있다.

이 수식의 계산비용은 잠재변수 ${\displaystyle \mathbf {Z} }$가 취할 수 있는 값의 수에 비례하고, ${\displaystyle \mathbf {Z} }$의 차원이 증가할수록 취할 수 있는 값의 수는 지수적으로 증가하기 때문에 이 수식을 계산하기는 매우 어렵다.

EM알고리즘은 다음 두 단계를 반복하여 가능도 함수 ${\displaystyle L({\boldsymbol {\theta }};\mathbf {X} )}$의 최대가능도를 구한다.

기댓값 (E) 단계에서는 ${\displaystyle {\boldsymbol {\theta }}^{(t)}}$가 주어지고 새로운 ${\displaystyle {\boldsymbol {\theta }}}$를 사용할 때 가능도의 기댓값 ${\displaystyle Q}$를 정의한다. 이 때 기댓값을 취하는 확률분포는 ${\displaystyle \mathbf {X} }$, ${\displaystyle {\boldsymbol {\theta }}^{(t)}}$가 주어졌을 때 ${\displaystyle \mathbf {Z} }$의 조건부 분포이다.

${\displaystyle Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})=\operatorname {E} _{\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)}}\left[\log L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )\right]=\sum _{\mathbf {Z} }p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )}$

최대화 (M) 단계에서는 ${\displaystyle Q}$를 최대화하는 새로운 매개변수 ${\displaystyle {\boldsymbol {\theta }}^{(t+1)}}$를 계산한다.

${\displaystyle {\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\ Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})\,}$

매개변수 ${\displaystyle {\boldsymbol {\theta }}}$가 주어졌을 때, 잠재변수 ${\displaystyle \mathbf {Z} }$에 관한 가능도 함수를 최대화함으로써 ${\displaystyle \mathbf {Z} }$의 값을 어렵지 않게 추정할 수 있고, 반대로 잠재변수 ${\displaystyle \mathbf {Z} }$의 값이 주어졌을 때, 매개변수에 관한 가능도 함수를 최대화함으로써 매개변수 ${\displaystyle {\boldsymbol {\theta }}}$의 값을 추정할 수 있다. 매개변수와 잠재변수 중 하나의 값을 알면 다른 값도 쉽게 알 수 있다는 것이 EM 알고리즘의 핵심이다. 

다음은 EM알고리즘을 간략히 요약한 것이다.

1. 매개변수 ${\displaystyle {\boldsymbol {\theta }}}$를 임의의 값으로 설정한다.
2. 주어진 매개변수 값에 관한 잠재변수 ${\displaystyle \mathbf {Z} }$값을 추정한다.
3. 2단계에서 얻은 잠재변수 값을 이용해 매개변수 ${\displaystyle {\boldsymbol {\theta }}}$값을 다시 추정한다.
4. 매개변수 ${\displaystyle {\boldsymbol {\theta }}}$값과 잠재변수 ${\displaystyle \mathbf {Z} }$값이 수렴할 때까지 2, 3단계를 반복한다.