[general] 일반적인 EM 알고리즘(The EM Algorithm in General)

이전 글 EM 알고리즘(Expectation and Maximization Algorithm)에서 가우시안 혼합 모델에 대한 EM 알고리즘을 다루었습니다. 예시로 가우시안 혼합 모델의 모수를 추정하였지만, 본래 EM 알고리즘은 잠재 변수가 있는 모델에 대해 모두 사용할 수 있습니다.

이번 글에서는 가우시안 혼합 모델에 국한하지 않고, 일반적으로 잠재 변수가 있는 모델에서 어떻게 모수를 추정하게 되는지 알아보겠습니다.

또한 가우시안 혼합 모델을 기반으로 많은 이야기가 전개되니 가우시안 혼합 모델도 읽고 오시는 것을 추천드립니다.

[관련 글] 가우시안 혼합 모델(Gaussian Mixture),가우시안 혼합 모델의 확장(Extention ofGaussian Mixture)

---

변수를 주변화 하는 기본적인 방법은 필요하지 않은 변수에 대해 다 더하는 것입니다.

$ln~p(\textbf {X}|\theta)=ln~\left \{ \displaystyle \sum_{\textbf {Z}}{p(\textbf {X},\textbf {Z}|\theta) }\right \} $

일반적으로 모델의 모수를 추정하는 방법은 이렇게 주변화된 변수에 로그 우도를 최대화하는 것입니다. 하지만, 위의 식에서도 알 수 있듯이, 로그 안에 합이 있기 때문에, 매우 복잡한 형태로 미분 값이 표현되게 됩니다. 이를 해결하기 위해선 로그 밖으로 합을 빼내야 할 것입니다.

따라서 EM 알고리즘에서는 로그 우도를 직접 최대화하는 대신 결합 확률의 로그에 대한 기댓값을 최대화하는 방법을 통해 이를 해결 하였습니다.

E Step

다음과 같이 잠재 변수를 샘플링하여 결합 확률에 대한 로그의 기댓값을 구할 수 있습니다.

$\mathcal {Q}(\theta,~\theta^{\textrm {old}})=\displaystyle \sum_{\mathbf {Z}}{p(\mathbf {Z}|\mathbf {X},~\theta^{\textrm {old}})~ln~p(\textbf {X},\textbf {Z}|\theta)}$

M Step

E Step에서 구해진 결합 확률의 로그에 대한 기댓값을 최대화하는 과정이 M Step에 해당하는데, 다음과 같습니다.

$\theta^{\textrm {new}}=\textrm {argmax}_\theta {\mathcal {Q}(\theta,~\theta^{\textrm {old}})}$

$\theta^{\textrm{old}}=\theta^{\textrm{new}}$

위의 과정을 앞서 설명한 가우시안 혼합 모델에서의 EM 알고리즘과 비교하여 설명하면 다음과 같습니다.

---

먼저 위의 과정에서처럼 결합 확률 분포에 대한 로그 값의 기댓값을 구해보겠습니다.

$\begin {align} \mathbb {E}_Z {\left [ ln~p(\textbf {X}, \textbf {Z}|\theta)\right ]}=& \mathbb {E}_Z {\left [ \displaystyle \sum_n ln~p(\textbf {x}_n, \textbf {z}_n|\theta)\right ]}=\displaystyle \sum_n \mathbb {E}_Z \left [ ln~p(\textbf {x}_n, \textbf {z}_n|\theta)\right ] \\ =& \displaystyle \sum_n \mathbb {E}_Z \left [ ln \left [ p(z_n) p(x_n|z_n,~\theta) \right ]\right ] \\ =& \displaystyle \sum_n \mathbb {E}_Z \left [ ln \left [ \displaystyle \prod^K_{k=1}{\left [ \pi_k N(x_n|\mu_k,~\Sigma_k) \right ]^{z_{nk}}} \right ]\right ] \\ =& \displaystyle \sum^N_{n=1} \displaystyle \sum^K_{k=1} \mathbb {E}_{Z}{(z_{nk})} \left [ ln  {\left [ \pi_k N(x_n|\mu_k,~\Sigma_k) \right ]} \right ] \\ =& \displaystyle \sum^N_{n=1} \displaystyle \sum^K_{k=1} \mathbb {E}_{Z}{[z_{nk}]}  ln  {\left [ \pi_k N(x_n|\mu_k,~\Sigma_k) \right ]}  \end {align}$

위의 결합 분포의 로그의 기댓값을 계산하기 위해선 잠재 변수의 사후 분포에서 샘플링할 수 있어야 하는데, 잠재 변수의 사후 분포는 다음과 같습니다.

$\begin {align} p(Z|X,~\mu,~\Sigma,~\pi)=&\frac {p(X|Z,~\mu,~\Sigma,~\pi) p(Z)}{p(X|\mu,~\Sigma,~\pi)} \\ =&\frac {\displaystyle \prod^N_{n=1} \displaystyle \prod^K_{k=1}{\left [ \pi_k N(x_n|\mu_k,~\Sigma_k)\right ]}^{z_{nk}}}{\displaystyle \sum^K_{k=1}{\pi_k N(x_n|\mu_k,~\Sigma_k)}} \end {align}$

우리가 관심 있는 변수 $Z_{nk}$에 대한 기댓값(E Step)은 다음과 같습니다.

$\begin {align} \mathbb {E}{\left [ z_{nk} \right ] }=& \frac {\displaystyle \sum_{z_{nk}}z_{nk} \left [ \pi_k N(x_n|\mu_k,~\Sigma_k)\right ]^{z_{nk}}}{\displaystyle \sum^K_{k=1}{\pi_k N(x_n|\mu_k,~\Sigma_k)}} \\ =& \frac {\pi_k N(x_n|\mu_k,~\Sigma_k) }{\displaystyle \sum^K_{k=1}{\pi_k N(x_n|\mu_k,~\Sigma_k)}} \\ =& \gamma({z_{nk}}) \end {align} $

따라서 결합 분포의 로그의 기댓값은 다음과 같습니다.

$\begin {align} \mathbb {E}_Z {\left [ ln~p(\textbf {X}, \textbf {Z}|\theta)\right ]} = \displaystyle \sum^N_{n=1} \displaystyle \sum^K_{k=1} \gamma{(z_{nk})}  ln  {\left [ \pi_k N(x_n|\mu_k,~\Sigma_k) \right ]}  \end {align}$

만약 responsibility의 값이 주어진다면, 위의 기댓값을 각각의 모수에 대해 미분(M Step)할 수 있으므로, 모수의 값을 갱신할 수 있습니다.