Contents
1. EM Algorithm as Maximization-Maximization Procedure
1.1. Deriving a Lower Bound of Log-likelihood
1.2. E-step: Maximizing the Lower Bound with respect to $\tilde P$
1.3. M-step: Maximizing the Lower Bound with respect to $\theta’$
1.4. Why Does EM Algorithm Work?
2. EM Algorithm and KL Divergence

The Elements of Statistical Learning의 Chapter 8를 요약/정리한 이 포스트에서는, 관측되지 않는 잠재 변수(latent variable)가 있을 때 likelihood의 최대화를 가능하게 해주는 방법인 EM 알고리즘에 대해 소개하였다. 그 알고리즘은 다음과 같다.

• 추정하고자 하는 모수 $\theta$의 초기값을 설정한다.
• Expectation step : 모수 $\theta$를 한 값으로 고정하고, 그 때의 latent variable의 조건부분포를 이용하여 log-likelihood의 기대값을 구한다.
• Maximization step : E-step에서 구한 log-likelihood의 기대값을 이용해 모수 $\theta$의 최적값을 구하고, 이를 새로운 $\theta$의 값으로 업데이트한다.
• 이 과정을 반복할 때, $\theta$가 특정 값으로 수렴한다면, 우리는 이를 likelihood를 최대화하는 $\theta$의 추정치로 삼는다.

이 포스트에서는 어떻게 EM 알고리즘이 (log-) likelihood의 최대화를 가능케 하는지에 대한 이론적인 배경을 자세히 설명하고자 한다. 아래의 도출과정에서 사용된 notation은 The Elements of Statistical Learning, Chapter 8의 notation과 동일하다. 참고로 아래의 설명에서는 모수를 나타내는 문자 $\theta$에 prime이 붙은 $\theta’$의 형태로 모수를 나타내는데, 이는 The Elements of Statistical Learning의 표기를 따른 것일 뿐, 별다른 의미는 없다.

1. EM Algorithm as Maximization-Maximization Procedure

1.1. Deriving a Lower Bound of Log-likelihood

우리의 최종 목표는 관측된 변수의 observed data $\mathbf{Z}$에 대한 likelihood를 최대화하는 $\theta’$를 찾는 것이다. 여기서는 논의의 편의를 위해, latent 변수 $\mathbf{Z}^m$이 discrete 확률변수라고 가정하고 논의를 전개하겠다. $\mathbf{Z}$에 대한 log-likelihood는 다음과 같다.

\[\log P(\mathbf{Z};\theta')=\log \Big[ \sum_{\mathbf{Z}^m} P(\mathbf{Z},\mathbf{Z}^m;\theta') \Big]\]

관측되지 않는 latent 변수의 data($\mathbf{Z}^m$)에 대한 어떤 임의의 확률분포, $\tilde P(\mathbf{Z}^m)$를 이용하여 아래와 같이 식을 변형할 수 있다.

\[=\log \Big[ \sum_{\mathbf{Z}^m} \frac{P(\mathbf{Z},\mathbf{Z}^m;\theta')}{\tilde P(\mathbf{Z}^m)} \tilde P(\mathbf{Z}^m)\Big] =\log \mathbb{E}_\tilde P \Big[ \frac{P(\mathbf{Z},\mathbf{Z}^m;\theta')}{\tilde P(\mathbf{Z}^m)}\Big]\]

로그함수는 concave 함수이므로 Jensen 부등식에 의해, $\log \mathbb E_{\tilde P} \Big[ \frac{P(\mathbf{Z},\mathbf{Z}^m;\theta’)}{\tilde P(\mathbf{Z}^m)}\Big] \ge \mathbb E_{\tilde P} \Big[ \log \Big[ \frac{P(\mathbf{Z},\mathbf{Z}^m;\theta’)}{\tilde P(\mathbf{Z}^m)} \Big] \Big]$가 만족한다. 즉, $F(\theta’,\tilde P)$는 최대화하고자 하는 $\log P(\mathbf{Z};\theta’)$의 lower bound라는 것을 알 수 있다.

\[\log P(\mathbf{Z};\theta') \ge \mathbb{E}_\tilde P \Bigg[ \log \Big[ \frac{P(\mathbf{Z},\mathbf{Z}^m;\theta')}{\tilde P(\mathbf{Z}^m)} \Big] \Bigg]\] \[\log P(\mathbf{Z};\theta') \ge \mathbb{E}_\tilde P \Big[ \log P(\mathbf{Z},\mathbf{Z}^m;\theta') \Big] - \mathbb{E}_\tilde P \Big[ \log \tilde P(\mathbf{Z}^m) \Big]\] \[\text{Lower bound of log-likelihood }\enspace F(\theta',\tilde P)= \mathbb{E}_\tilde P \Big[ \log P(\mathbf{Z},\mathbf{Z}^m;\theta') \Big] - \mathbb{E}_\tilde P \Big[ \log \tilde P(\mathbf{Z}^m) \Big]\]

결론부터 이야기하자면, EM 알고리즘은 likelihood의 lower bound, $F(\theta’,\tilde P)$를 최대화함으로써 간접적으로 likelihood를 최대화하는 알고리즘이다. 그리고 이는 $\tilde P$와 $\theta’$를 번갈아가며 최대화하는 작업을 반복함으로써 이루어진다. Expectation step은 $\theta’$가 주어지고 $\tilde P$에 대해 $F(\theta’,\tilde P)$를 최대화하고, Maximization step은 $\tilde P$가 주어지고 $\theta’$에 대해 $F(\theta’,\tilde P)$를 최대화하는 것과 같다.

위 그림은 maximization-maximization 과정으로서의 EM 알고리즘을 쉽게 이해할 수 있도록 나타낸 그림이다. 그림 상의 등고선은 log-likelihood의 lower bound, $F(\theta’,\tilde P)$를 나타낸 것이다. $\tilde P$와 $\theta’$를 번갈아가며 최대화하는 작업을 반복하며 log-likelihood의 lower bound를 최대화하는 것이다. 앞에서 구한 lower bound, $F(\theta’,\tilde P)$를 최대화하는 것이 log-likelihood의 최대화로 이어진다는 것은 뒤의 1.4에서 다루도록 하겠다.

1.2. E-step: Maximizing the Lower Bound with respect to $\tilde P$

모수가 $\theta’$의 값이 주어져 있을 때, log-likelihood의 lower bound, $F(\theta’,\tilde P)$를 최대화하는 함수 $\tilde P$를 찾는 문제를 생각해보자. $\tilde P(\mathbf{Z}^m)$는 $\mathbf{Z}^m$에 대한 어떤 임의의 확률분포함수이므로, log-likelihood의 lower bound를 최대화하는 것은 아래와 같은 제약 하의 최대화 문제가 된다.

\[\begin{equation*} \begin{aligned} & \underset{\tilde P}{\text{maximize}} & & F(\theta',\tilde P) \\ & \text{subject to} & & \tilde P (\mathbf{Z}^m)\ge0 \text{ for all possible value of }\mathbf{Z}^m, \\ &&& \sum_{\mathbf{Z}^m} \tilde P (\mathbf{Z}^m)=1. \end{aligned} \end{equation*}\]

Lagrange multiplier, $\lambda$와 $\tau =\{ \tau_{\mathbf{z}^m} \}$를 이용하여 $F(\theta’,\tilde P)$를 최대화하는 제약 하 최적화 문제를 세우면 다음과 같다.

\[\underset{\tilde P, \lambda, \tau }{\text{maximize}} \enspace \enspace G(\tilde P, \lambda, \tau) =F(\theta',\tilde P)-\lambda \Big[ \sum_{\mathbf{Z}^m} \tilde P (\mathbf{Z}^m)-1 \Big]-\sum_{\mathbf{Z}^m} \Big[ \tau_{\mathbf{z}^m} \tilde P (\mathbf{Z}^m) \Big]\]

First-order Condition

일계 미분 조건을 이용하여, log-likelihood의 lower bound $F(\theta’,\tilde P)$를 최대화하는 함수 $\tilde P$를 찾자. 먼저 $F(\theta’,\tilde P)$를 $\tilde P (\mathbf{Z}^m)$로 미분한 결과는 다음과 같다.

\[\frac{\partial F(\theta',\tilde P)}{\partial \tilde P (\mathbf{Z}^m)}=\frac{\partial}{\partial \tilde P (\mathbf{Z}^m)} \Bigg[ \sum_{\mathbf{Z}^m} \Big( \log P(\mathbf{Z},\mathbf{Z}^m;\theta') \Big) \tilde P(\mathbf{Z}^m) -\sum_{\mathbf{Z}^m} \Big( \log \tilde P(\mathbf{Z}^m) \Big) \tilde P(\mathbf{Z}^m) \Bigg]\] \[= \log P(\mathbf{Z},\mathbf{Z}^m;\theta')-\log \tilde P(\mathbf{Z}^m)-\frac{1}{\tilde P(\mathbf{Z}^m)}\tilde P(\mathbf{Z}^m)\]

이를 이용하여 Lagrange 목적함수, $G(\tilde P, \lambda, \tau)$를 $\tilde P (\mathbf{Z}^m)$로 미분한 결과는 다음과 같다. (가능한 $\mathbf{Z}^m$의 값 중 하나의 값 $\mathbf{Z}^m=\mathbf{z}^m$일 때의 함수 $\tilde P$의 값으로 미분하는 것이라고 생각하면 된다.) 제약 하에서 $F(\theta’=\theta^{(t)},\tilde P)$를 최대화하는 함수 $\tilde P$는 다음과 같은 일계 미분 조건을 만족한다.

\[\frac{\partial G(\tilde P, \lambda, \tau)}{\partial \tilde P (\mathbf{Z}^m)}=\frac{\partial}{\partial \tilde P (\mathbf{Z}^m)} \Bigg[ F(\theta',\tilde P) -\lambda \Big[ \sum_{\mathbf{Z}^m} \tilde P (\mathbf{Z}^m)-1 \Big]-\tau_{\mathbf{z}^m} \Big[ \tilde P (\mathbf{Z}^m) \Big] \Bigg] \stackrel{\text{let}}{=}0\] \[\Rightarrow \enspace \log P(\mathbf{Z},\mathbf{Z}^m;\theta')-\log \tilde P(\mathbf{Z}^m)-1-\lambda- \tau_{\mathbf{z}^m}=0\] \[\Rightarrow \enspace \frac{P(\mathbf{Z},\mathbf{Z}^m;\theta')}{\tilde P(\mathbf{Z}^m)}=e^{1+\lambda + \tau_{\mathbf{z}^m}}=\text{constant}\] \[\Rightarrow \enspace \tilde P(\mathbf{Z}^m)= \frac{P(\mathbf{Z},\mathbf{Z}^m;\theta')}{\text{constant}} \propto P(\mathbf{Z},\mathbf{Z}^m;\theta')\]

제약 하에서 $F(\theta’=\theta^{(t)},\tilde P)$를 최대화하는 함수 $\tilde P$는 $\mathbf{Z},\mathbf{Z}^m$의 joint probability $P(\mathbf{Z},\mathbf{Z}^m;\theta’)$의 상수배임을 알 수 있다. 따라서 다음과 같이 나타낼 수 있다.

\[c \cdot \tilde P(\mathbf{Z}^m)= P(\mathbf{Z},\mathbf{Z}^m;\theta')\]

근데 여기서 $P(\mathbf{Z};\theta’)=\sum_{\mathbf{Z}^m} P(\mathbf{Z},\mathbf{Z}^m;\theta’)= c \cdot \sum_{\mathbf{Z}^m} \tilde P(\mathbf{Z}^m)= c$이므로, 이를 대입하면 제약 하에서 $F(\theta’,\tilde P)$를 최대화하는 함수 $\tilde P$를 구할 수 있다.

\[\therefore \enspace \enspace \tilde P(\mathbf{Z}^m)= \frac{P(\mathbf{Z},\mathbf{Z}^m;\theta')}{P(\mathbf{Z};\theta')}=P(\mathbf{Z}^m \mid \mathbf{Z};\theta')\]

따라서, 만약 모수가 $\theta’$의 값이 주어져 있다면, log-likelihood의 lower bound $F(\theta’,\tilde P)$를 최대화하는 함수 $\tilde P(\mathbf{Z}^m)$는 $P(\mathbf{Z}^m \mid \mathbf{Z};\theta’)$임을 알 수 있다.

Expectation Step Revisited

EM 알고리즘의 Expectation step은 아래와 같이, 관측된 변수의 sample $\mathbf{Z}=\mathbf{z}$과 모수의 특정 값 $\theta’=\theta^{(t)}$가 주어져 있을 때의 관측 불가능한 변수 $\mathbf{Z}^m$의 조건부 분포를 이용하여, log-likelihood를 기대값 취한 대리 likelihood, $Q(\theta’ \mid \theta^{(t)})$를 구한다.

\[Q(\theta' \mid \theta^{(t)})=\mathbb{E}_{\mathbf{Z}^m | \mathbf{Z}=\mathbf{z},\theta^{(t)}} \Big[ \log P(\mathbf{Z},\mathbf{Z}^m;\theta') \Big]\]

그런데 우리는 모수가 $\theta’=\theta^{(t)}$로 주어져있을 때, log-likelihood의 lower bound, $F(\theta’,\tilde P)$를 최대화하는 함수 $\tilde P^\ast$가 $P(\mathbf{Z}^m \mid \mathbf{Z};\theta’=\theta^{(t)})$임을 확인했다. 즉 log-likelihood의 lower bound의 최대화된 값은 다음과 같다. 두 번쨰 항은 $\theta’$를 포함하지 않는다는 사실을 짚고 넘어가자.

\[F(\theta',\tilde P^\ast)=\mathbb{E}_{\mathbf{Z}^m | \mathbf{Z}=\mathbf{z},\theta^{(t)}} \Big[ \log P(\mathbf{Z},\mathbf{Z}^m;\theta') \Big]-\mathbb{E}_{\tilde P^\ast} \Big[ \log {\tilde P^\ast}(\mathbf{Z}^m) \Big]\]

즉, EM 알고리즘의 Expectation step은, 현재의 모수 값 $\theta^{(t)}$에서, log-likelihood의 lower bound를 가장 크게 만드는 $\tilde P(\mathbf{Z}^m)=P(\mathbf{Z}^m \mid \mathbf{Z};\theta’)$를 찾은 것과 동일하다는 것을 알 수 있다.

1.3. M-step: Maximizing the Lower Bound with respect to $\theta’$

그럼 $\tilde P$가 주어져 있을 때, log-likelihood의 lower bound, $F(\theta’,\tilde P)$를 최대화하는 모수 값 $\theta’$를 찾는 문제를 생각해보자. 이는 위의 Expectation step과 달리 매우 간단하다. 이전 시행에서 업데이트된 $\theta$ 값이 $\theta^{(t)}$라면, $F(\theta’,\tilde P)$를 최대화하는 $\tilde P$는 $\tilde P^\ast(\mathbf{Z}^m)=P(\mathbf{Z}^m \mid \mathbf{Z};\theta’=\theta^{(t)})$일 것이다. 따라서 아래의 식을 최대화하는 모수 $\theta’$의 값을 찾아 $\theta^{(t+1)}$로 업데이트 해주면 된다.

\[\theta^{(t+1)}= \text{arg}\max_{\theta'} \enspace F(\theta',\tilde P^\ast)\] \[=\text{arg}\max_{\theta'} \enspace \mathbb{E}_{\mathbf{Z}^m | \mathbf{Z}=\mathbf{z},\theta^{(t)}} \Big[ \log P(\mathbf{Z},\mathbf{Z}^m;\theta') \Big]-\mathbb{E}_{\tilde P^\ast} \Big[ \log {\tilde P^\ast}(\mathbf{Z}^m) \Big]\] \[=\text{arg}\max_{\theta'} \enspace \mathbb{E}_{\mathbf{Z}^m | \mathbf{Z}=\mathbf{z},\theta^{(t)}} \Big[ \log P(\mathbf{Z},\mathbf{Z}^m;\theta') \Big]\]

1.4 Why Does EM Algorithm Work?

이 절에서는 이와 같은 방법으로 log-likelihood의 lower bound를 최대화하는 것이, 왜 log-likelihood의 최대화로 이어지는지 간단히 설명하겠다. 조건부 확률의 식을 이용하여, $P(\mathbf{Z}^m \mid \mathbf{Z};\theta’)$의 식은 다음과 같이 나타낼 수 있다.

\[P(\mathbf{Z}^m \mid \mathbf{Z};\theta')=\frac{P(\mathbf{Z},\mathbf{Z}^m ;\theta')}{P( \mathbf{Z};\theta')} \enspace , \enspace \enspace P( \mathbf{Z};\theta')=\frac{P(\mathbf{Z},\mathbf{Z}^m ;\theta')}{P(\mathbf{Z}^m \mid \mathbf{Z};\theta')}\] \[\log P( \mathbf{Z};\theta')=\log P(\mathbf{Z},\mathbf{Z}^m ;\theta')-\log P(\mathbf{Z}^m \mid \mathbf{Z};\theta')\]

양변에 $P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})$를 곱하고, Latent 변수 $\mathbf{Z}^m$에 대해 summation을 취한다.

\[\sum_{\mathbf{Z}^m} \Big[ \log P( \mathbf{Z};\theta') \Big] P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)}) = \sum_{\mathbf{Z}^m} \Big[ \log P(\mathbf{Z},\mathbf{Z}^m ;\theta')\Big] P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})\] \[- \sum_{\mathbf{Z}^m} \Big[ \log P(\mathbf{Z}^m \mid \mathbf{Z};\theta') \Big] P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})\]

이 때, 좌변은 $\log P( \mathbf{Z};\theta’)$가 $\mathbf{Z}^m$을 포함하고 있지 않으므로, 다음과 같다.

\[\sum_{\mathbf{Z}^m} \Big[ \log P( \mathbf{Z};\theta') \Big] P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})=\log P( \mathbf{Z};\theta')=\ell (\theta';\mathbf{Z}) \enspace \text{ : Target log-likelihood}\]

우변의 첫 번째 항을 보면, total sample( $\mathbf{T}=(\mathbf{Z},\mathbf{Z}^m)$ )의 likelihood를 $ P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})$로 조건부평균낸 surrogate likelihood, $Q(\theta’ \mid \theta^{(t)})$임을 알 수 있다.

\[Q(\theta ' \mid \theta^{(t)})=\sum_{\mathbf{Z}^m} \Big[ \log P(\mathbf{Z},\mathbf{Z}^m ;\theta')\Big] P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})\]

우변의 두 번째 항은 표기의 편의를 위해, 다음과 같이 나타내겠다.

\[R(\theta ' \mid \theta^{(t)})=\sum_{\mathbf{Z}^m} \Big[ \log P(\mathbf{Z}^m \mid \mathbf{Z};\theta') \Big] P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})\]

따라서 위 식은 아래와 같이 정리할 수 있다.

\[\ell (\theta';\mathbf{Z})=Q(\theta ' \mid \theta^{(t)})- R(\theta ' \mid \theta^{(t)}) \enspace \cdots \cdots (a)\]

이 식은 모수 공간 내의 모든 $\theta’$에 대해 성립하므로, 아래와 같이 $\theta’ =\theta^{(t)}$일 때도 성립한다.

\[\ell (\theta^{(t)};\mathbf{Z})=Q(\theta ^{(t)} \mid \theta^{(t)})- R(\theta ^{(t)} \mid \theta^{(t)})\]

위 두 식을 빼면 아래와 같은 식을 얻는다.

\[\ell (\theta';\mathbf{Z})-\ell (\theta^{(t)};\mathbf{Z})=Q(\theta ' \mid \theta^{(t)})-Q(\theta ^{(t)} \mid \theta^{(t)})- \Big[ R(\theta ' \mid \theta^{(t)})-R(\theta ^{(t)} \mid \theta^{(t)}) \Big] \enspace \cdots \cdots (b)\]

여기서 $R(\theta’ \mid \theta^{(t)})-R(\theta ^{(t)} \mid \theta^{(t)})$의 성질에 대해 알아보겠다.

\[R(\theta ' \mid \theta^{(t)})-R(\theta ^{(t)} \mid \theta^{(t)})=\sum_{\mathbf{Z}^m} \Big[ \log \frac{ P(\mathbf{Z}^m \mid \mathbf{Z};\theta')}{P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})} \Big] P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})\]

로그함수는 concave 함수이므로, Jensen 부등식을 이용하면 다음과 같다.

\[\sum_{\mathbf{Z}^m} \Big[ \log \frac{ P(\mathbf{Z}^m \mid \mathbf{Z};\theta')}{P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})} \Big] P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)}) \le \log \Bigg[ \sum_{\mathbf{Z}^m} \frac{ P(\mathbf{Z}^m \mid \mathbf{Z};\theta')}{P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})} P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)}) \Bigg]\] \[\sum_{\mathbf{Z}^m} \Big[ \log \frac{ P(\mathbf{Z}^m \mid \mathbf{Z};\theta')}{P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})} \Big] P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)}) \le \log \Bigg[ \sum_{\mathbf{Z}^m} P(\mathbf{Z}^m \mid \mathbf{Z};\theta') \Bigg] = \log 1 =0\]

이 때, $R(\theta’ \mid \theta^{(t)})-R(\theta ^{(t)} \mid \theta^{(t)})$는 다음을 만족한다.

\[R(\theta ' \mid \theta^{(t)})-R(\theta ^{(t)} \mid \theta^{(t)}) \le 0\]

이 결과를 위의 $(b)$식에 대입하면 다음과 같다.

\[\ell (\theta';\mathbf{Z})-\ell (\theta^{(t)};\mathbf{Z}) \ge Q(\theta ' \mid \theta^{(t)})-Q(\theta ^{(t)} \mid \theta^{(t)}) \enspace \cdots \cdots (c)\]

E-step에서 $Q(\theta’ \mid \theta^{(t)})$를 구하고, M-step에서 $Q(\theta’ \mid \theta^{(t)})$를 최대화하는 $\theta’ $를 구하는 작업은 log-likelihood의 lower bound, $F(\theta’,\tilde P)$를 최대화하는 것과 같다는 것을 앞의 두 절 1.2, 1.3에서 확인하였다. $Q(\theta’ \mid \theta^{(t)})$를 최대화하는 $\theta’ $를 $\theta^{(t+1)}$로 업데이트 한다면, 다음 식이 만족한다.

\[Q(\theta^{(t+1)} \mid \theta^{(t)})-Q(\theta^{(t)} \mid \theta^{(t)}) \ge 0\]

따라서 $(c)$ 식에 $\theta’=\theta^{(t+1)}$을 대입하고 위 결과를 사용하면, 최종적으로 아래와 같은 식을 얻을 수 있다.

\[\ell (\theta^{(t+1)};\mathbf{Z})-\ell (\theta^{(t)};\mathbf{Z}) \ge Q(\theta^{(t+1)} \mid \theta^{(t)})-Q(\theta ^{(t)} \mid \theta^{(t)}) \ge 0\] \[\therefore \enspace \enspace \enspace \ell (\theta^{(t+1)};\mathbf{Z}) \ge \ell (\theta^{(t)};\mathbf{Z})\] \[\Rightarrow \Big[ \text{log-likelihood when }\theta '=\theta^{(t+1)} \Big] \ge \Big[ \text{log-likelihood when }\theta '=\theta^{(t)} \Big]\]

이 식의 의미에 대해 생각해보자. $\log P( \mathbf{Z};\theta’)=\ell (\theta’;\mathbf{Z})$는 우리가 EM 알고리즘을 통해 최대화하고자 했던 log-likelihood이다. 따라서, EM 알고리즘의 $t+1$ 번째 시행에서 $Q(\theta’ \mid \theta^{(t)})$를 최대화하는 $\theta’ $로 업데이트한 모수 추정치, $\theta^{(t+1)}$은 이전 시행에서의 모수 추정치, $\theta^{(t)}$보다 log-likelihlood의 값을 항상 증가시킨다. 다시 말해서, EM 알고리즘을 반복적으로 수행할 수록, 우리의 모수 추정치는 항상 log-likelihood를 증가시키는 방향으로 최적화된다.

2. EM Algorithm and KL Divergence

Kullback-Leibler Divergence는 한 확률분포가 다른 확률분포와 서로 얼마나 다른지를 측정하는 척도이다. 두 확률분포가 완전히 같다면 KL Divergence는 $0$이 된다. 그 식은 다음과 같다.

\[D_{KL} (P \mid \mid Q)=- \sum_{x} P(x) \log ( \frac{Q(x)}{P(x)} ) =-\mathbb{E}_P \log(\frac{Q(x)}{P(x)})\]

KL Divergence의 개념을 이용하여 EM 알고리즘을 이해하기 위해, 아래와 같은 과정을 통해 식을 도출하고, 그 식의 의미를 생각해볼 것이다. 위의 1.4 절에서 사용한 $(a)$ 식을 가져오면 다음과 같다.

\[\ell (\theta';\mathbf{Z})=Q(\theta ' \mid \theta^{(t)})- R(\theta ' \mid \theta^{(t)})\]

이는 아래와 같은 식을 간단히 나타낸 것이다.

\[\log P( \mathbf{Z};\theta')=\sum_{\mathbf{Z}^m} \Big[ \log P(\mathbf{Z},\mathbf{Z}^m ;\theta')\Big] P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})- \sum_{\mathbf{Z}^m} \Big[ \log P(\mathbf{Z}^m \mid \mathbf{Z};\theta') \Big] P(\mathbf{Z}^m \mid \mathbf{Z};\theta^{(t)})\]

관측된 변수 $\mathbf{Z}$의 log-likelihood는 다음 식을 만족한다. \(\log P( \mathbf{Z};\theta')=\log P(\mathbf{Z},\mathbf{Z}^m ;\theta')-\log P(\mathbf{Z}^m \mid \mathbf{Z};\theta')\)

양변에 $\tilde P (\mathbf{Z}^m)$를 곱하고, $\mathbf{Z}^m$에 대해 summation을 취한다. 여기서 $\tilde P(\mathbf{Z}^m)$는 위에서와 동일하게 latent 변수 $\mathbf{Z}^m$에 대한 어떤 임의의 확률분포함수이다.

\[\sum_{\mathbf{Z}^m} \Big[ \log P( \mathbf{Z};\theta') \Big] \tilde P (\mathbf{Z}^m) = \sum_{\mathbf{Z}^m} \Big[ \log P(\mathbf{Z},\mathbf{Z}^m ;\theta')\Big] \tilde P (\mathbf{Z}^m) - \sum_{\mathbf{Z}^m} \Big[ \log P(\mathbf{Z}^m \mid \mathbf{Z};\theta') \Big] \tilde P (\mathbf{Z}^m)\]

좌변은 $\log P( \mathbf{Z};\theta’)$가 $\mathbf{Z}^m$을 포함하고 있지 않으므로, 다음과 같다.

\[\sum_{\mathbf{Z}^m} \Big[ \log P( \mathbf{Z};\theta') \Big] \tilde P (\mathbf{Z}^m)=\log P( \mathbf{Z};\theta')=\ell (\theta';\mathbf{Z}) \enspace \text{ : Target log-likelihood}\]

또한, 우변에 $\sum_{\mathbf{Z}^m} \tilde P (\mathbf{Z}^m)[\log \tilde P (\mathbf{Z}^m)]$를 더했다 빼는 작업을 통해, 아래와 같은 식을 얻을 수 있다.

\[\ell (\theta';\mathbf{Z})=\sum_{\mathbf{Z}^m} \Big[ \log \frac{P(\mathbf{Z},\mathbf{Z}^m ;\theta')}{ \tilde P (\mathbf{Z}^m)}\Big] \tilde P (\mathbf{Z}^m) - \sum_{\mathbf{Z}^m} \Big[ \log \frac{P(\mathbf{Z}^m \mid \mathbf{Z};\theta') }{ \tilde P (\mathbf{Z}^m)} \Big] \tilde P (\mathbf{Z}^m)\]

따라서, 우리는 최대화하고자 하는 log-likelihood를 어떤 functional $F$, 그리고 $\tilde P(\mathbf{Z}^m)$와 $P(\mathbf{Z}^m \mid \mathbf{Z};\theta’)$의 KL Divergence의 합으로 decompose할 수 있다.

\[\therefore \enspace \enspace \enspace \ell (\theta';\mathbf{Z})=F(\tilde P, \theta' ) + D_{KL} \Big( \tilde P(\mathbf{Z}^m) \mid \mid P(\mathbf{Z}^m \mid \mathbf{Z};\theta') \Big)\] \[\text{where } \enspace F(\tilde P, \theta' )=\sum_{\mathbf{Z}^m} \Big[ \log \frac{P(\mathbf{Z},\mathbf{Z}^m ;\theta')}{ \tilde P (\mathbf{Z}^m)}\Big] \tilde P (\mathbf{Z}^m)\] \[\text{ and } \enspace D_{KL} \Big( \tilde P(\mathbf{Z}^m) \mid \mid P(\mathbf{Z}^m \mid \mathbf{Z};\theta') \Big) = - \sum_{\mathbf{Z}^m} \Big[ \log \frac{P(\mathbf{Z}^m \mid \mathbf{Z};\theta') }{ \tilde P (\mathbf{Z}^m)} \Big] \tilde P (\mathbf{Z}^m)\]

Meaning of the Decomposition

\[\ell (\theta';\mathbf{Z}) \ge \mathcal{L}(\tilde P, \theta' ) \enspace \text{ and } \enspace \ell (\theta';\mathbf{Z}) - \mathcal{L}(\tilde P, \theta' )=D_{KL} \Big( \tilde P(\mathbf{Z}^m) \mid \mid P(\mathbf{Z}^m \mid \mathbf{Z};\theta') \Big)\]

두 확률분포 사이의 KL Divergence는 항상 $0$ 이상의 값을 가지며, 두 확률분포가 같을 때 $0$의 값을 가진다. 또 하나 짚고 넘어갈 점은, $F(\tilde P, \theta’ )$이 위에서 정의된 log-likelihood의 lower bound와 동일한 식이라는 것이다. 따라서, log-likelihood와 그 lower bound의 차이는 $\tilde P(\mathbf{Z}^m)$와 $P(\mathbf{Z}^m \mid \mathbf{Z};\theta’ )$의 KL Divergence이다. 따라서, 우리는 이 KL Divergence를 0으로 만들면서 lower bound를 최대화하는 방법으로, likelihood의 최대화를 간접적으로 달성할 수 있다. 다시 말해서, $\tilde P(\mathbf{Z}^m)=P(\mathbf{Z}^m \mid \mathbf{Z};\theta’ )$로 두고, lower bound를 최대화하는 $\theta’ $를 구함으로써, log-likelihood의 최대화를 간접적으로 달성한다. 이는 1. EM Algorithm as Maximization-Maximization Procedure에서 설명했던 내용과 정확히 일치한다.

Reference

Hastie, T., Tibshirani, R.,, Friedman, J. (2001). The Elements of Statistical Learning. New York, NY, USA: Springer New York Inc..
Bishop, C. M. (2016). Pattern Recognition and Machine Learning. New York, NY: Springer New York.