각잡고 PRML을 열심히 읽어보니까, 예전보다 훨씬 잘 이해가 되는 것 같다. 내 수학 실력이 는걸까, 아니면 그냥 집중을 조금 더 잘 하게 된 걸까… ‘ㅅ’… 어쨌건 이해가 잘 가니 기분이 좋다.
데이터셋에서 관측되지 않았지만, 이러한 확률 변수가 존재한다고 가정하면 문제를 더 쉽게 모델링할 수 있는 경우가 자주 존재한다. 기계학습에서는 이러한 방법을 자주 이용한다.(K-means, Mixture of Gaussian, Hidden Markov Model 등…) 관측되지 않은 확률변수를 Latent variable, 혹은 Hidden variable이라고 부른다. 다만, 문제를 모델링하는 것은 쉬워졌지만, MLE를 바로 적용하기가 힘들어진다. 이럴 때 EM 알고리즘을 사용한다.
EM 알고리즘은 관측하지 않은 데이터가 있는 데이터셋에 대한 MLE를 계산하는 방법이다. 관측하지 못한 데이터가 모델에 필요한 경우 이런 방법을 사용한다.
알고리즘의 과정은 다음과 같다.
마침 EM 알고리즘을 설명하기에 짱짱킹 예시를 찾았으므로 이를 기반으로 설명을 하면 좋을 것 같다.
| 키 | 몸무게 |
|---|---|
| 172 | 62 |
| 170 | 61 |
| 152 | 44 |
| 168 | a |
| 165 | b |
| c | 70 |
이러한 데이터가, $\text{Normal}(\mu, \Sigma)$(다변수 정규분포)를 따른다고 가정하고, 이에 대한 MLE를 구한다고 생각해보자. 우리가 추정해야 하는 parameter는 $\mu$와, $\Sigma$이다. 처음부터 그리 정확한 $\mu, \Sigma$를 알 필요는 없으므로(점점 좋게 만들면 된다) missing value가 있는 row는 내버려두고,
우리가 추정해야 할 parameter는 \(\mu\)와, \(\Sigma\)이다. 일단 missing value가 있는 row는 내버려두고, 값이 완전히 차 있는 세 row에 대해서만 mu와 sigma를 추정하면 다음과 같다. (그냥 세 변수의 평균과 Covariance를 구하면 된다)
\(\mu = [164.66,55.66]\) \(\Sigma = \begin{bmatrix}121.3 & 111.3 \\ 111.3 & 102.3 \end{bmatrix}\) \(= \begin{bmatrix}\sigma_1^2 & \rho\sigma_1\sigma_1 \\ \rho\sigma_1\sigma_1 & \sigma^2 \end{bmatrix}\)
변수가 2개인 정규분포의 pdf는 다음과 같다. \(f(x) = \frac{1}{2\pi \mid \Sigma \mid }(- \frac{1}{2}exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))\)
4번째 row $[168,a]$을 보자. EM 알고리즘의 key point는 다음과 같다.
즉, 우리는 $E[a \mid 168]$를 계산할 수 있다. dimension이 2인 Gaussian distribution에서, $\text{E}[X_2 \mid x_1]$은 다음과 같다. \(E[X_2 \mid x_1] = \mu_2 + \frac{\Sigma_{1,2}}{\Sigma_{2,2}}(x_1 - \mu_1)\)으로 나타낼 수 있다. 이 식을 이용해, $E[a \mid x_1 = 68]$을 구해보자. \(\hat a = E[a \mid x_1 = 168] = 55.66 + \frac{111.3}{102.3}(168-164.66) = 59.29\)
비슷한 방법으로, $\hat b$와 $\hat c$도 계산할 수 있다.
\(\hat b = E[b \mid x_1 = 165] = 55.66 + \frac{111.3}{102.3}(165-164.66) = 56.02\) \(\hat c = E[c \mid x_2 = 70] = 164.66 + \frac{111.3}{121.3}(70 - 55.66) = 177.82\)
새롭게 구한 근사치로, 키-몸무게 테이블을 채우면 다음과 같다. | 키 | 몸무게 | |–|–| | 172 | 62 | | 170 | 61 | | 152 | 44 | | 168 | 59.29 | | 165 | 56.02 | | 177.82 | 70 |
이렇게 구한 $a,b,c$가 그다지 정확한 값이 아닐 수도 있지만, 어쨌건 나름대로 합리적이게 missing data를 채웠다. 이렇게 채운 전체 데이터를 이용해 $\mu$와 $\Sigma$를 다시 갱신하는 것이 M step이다. \(\mu = [167.47, 58.71]\) \(\Sigma = \begin{bmatrix}75.94 & 74.41 \\ 74.41 & 73.49 \end{bmatrix}\) 이런 방법을 계속 반복하는 것이 EM algorithm이다.
data $x$가 $K$개의 Normal distribution중 하나를 따르는데, 그 중 어떤 Normal distribution을 따르는지는 확률적으로만 알고, $x$가 $k$번째 Normal distribution을 따를 확률을 $\pi_k$라 하면, $x$에 대한 확률분포는 다음과 같이 정의할 수 있다.
\[p(x) = \sum_k \pi_k N(x| \mu _k, \Sigma_K)\]이를 다른 방법으로 모델링하기 위해, 새로운 확률 변수 $z$를 도입해보자. $z$는 size가 $K$인 one-hot vector이며, $x$가 $k$번째 가우시안에 속할 경우, $z_k=1$이며 나머지는 다 0이다.
그렇다면, $p(z_k=1) = pi_k$이며, $p(z) = \prod {\pi_k}^{z_k}$이다.
\(\)
p(x) = p(x \vert z) p(z) =
\sum_z[\prod_k (\pi_k \Nu(X|u_k, \Sigma_k))^{z_k} =
\sum_z(1 \times (\pi_k \Nu(X|u_k, \Sigma_k)) \times 1 \text{ … } )=
\sum_z\pi_k \Nu(X|u_k, \Sigma_k)
$$
위에서 정의한 $p(x)$의 log likelihood를 계산해보면 다음과 같다.
\(\log p(X| \pi, \mu, \Sigma) = \sum_n\log\{\sum_k\pi_k \Nu(x_n| \mu_k, \Sigma_k) \}\) where $\mu = {\mu_1, \mu_2, …, }$, $\Sigma = {\Sigma_1, \Sigma_2, … }$이며, 가우시안들의 패러미터의 집합을 의미한다. 또한 $\pi = { \pi_1, \pi_2, …}$는 Latent variable $z$의 parameter이다.
저 log likelihood를 단순히 미분하는 것으로는 쉽게 문제를 해결할 수 없다. 예를 들어, log likelihood를 $u_k$에 대해 미분해보자.
\(\frac{\partial }{ \partial u_k}\log p = \sum_n \frac{ \pi_k \Nu (x_n|\mu_k, \Sigma_k)}{\sum_i\pi_i \Nu (x_n|\mu_i, \Sigma_i)} \Sigma_k^{-1}(x_n - u_k)\) 이다. 그리고 이 식은 쉽게 closed form으로 변환되지 않는다.
EM 알고리즘의 목적은 latent variables $Z$가 포함된 Maximum Likelihood Estimation을 푸는 것이다. 암튼, 이런 경우 log likelihood는 다음과 같이 표현된다. \(\log p( X \vert \theta) = \log(\sum_Z p(X, Z \mid \theta))\) 방금 본 Mixture of Gaussian에서의 log likelihood의 미분과 같이, 일반적으로 이런 식은 미분해서 MLE를 구하기가 어렵다.
식이 이렇게 불편해진 가장 큰 이유는 우리가 $Z$를 관측하지 못했다는 점이다. 만약 $Z$가 관측되었다면, $X’ ={X, Z}$으로 정의한 뒤, $\log p( X’ \vert \theta) = \log(p(X’ \mid \theta)$으로 쉽게 계산할 수 있다.
근데, $Z$에 대한 지식이 완전히 없지는 않다. $p(Z|X, \theta)$에 대해서도, 우리는 어느 정도 알고 있다. 그럼… 그럼… $Z$에 대해 완전히 모르는 것은 아니니, $\log p( X’ \vert \theta)$의 기대값을 계산하고, 이를 최대화하는 솔루션을 찾는 것은 어떨까, 하는 아이디어를 EM 알고리즘에서는 이용하고 있다. \(Q(\theta_t, \theta_{t-1}) = \Epsilon_{Z}[\log(X'|\theta) \mid X, \theta_{t-1}] \\ = \sum_Z p(Z \mid X, \theta_{t-1})\log(X' \mid \theta)\) where $X’ = {X, Z}$
$X$와 $\theta_{t-1}$은 상수이며, $Z$는 확률변수이지만 expectation을 취함으로서 나타나지 않는다. 따라서, $Q$는 $\theta$에 대한 함수가 된다.
EM algorithm은 Expectation step과 Maximization step으로 나눠져 있다. 각 step도 역시 이름 그대로다.
기대값 $Q(\theta_t, \theta_{t-1}) = \sum_Z p(Z \mid X, \theta_{t-1})\log(X’ \mid \theta)$을 계산한다.
기대값 $Q(\theta_t, \theta_{t-1})$를 최대화하는 $\theta_t$를 계산한다.
Expectation과 Maximization Step을 log likelihood가 converge할때까지 반복하는 것이 EM 알고리즘이다.
| $$P(Z \vert X) \propto \prod_n \prod_k (\pi_k \Nu(x | u_k, \Sigma_k))^{z_k} $$이고, $z_{nk}$의 평균을 구하면 | |
| $$ \frac{\pi_k \Nu(x | u_k, \Sigma_k)}{\sum (\pi_i \Nu(x | u_i, \Sigma_i))} $$의 형태가 된다. |
then, estimated data $z$를 이용해 complete log likelihood
아무튼 일반적으로 EM algorithm의 intuition은 여기까지만 알아도 충분한 것 같다. 여기까지만 공부하면 어디서 EM 알고리즘 얘기 나왔을 때 엣헴엣헴 할 수 있지 않을까 하는 생각이 드니 여기까지만 봐도 될 것 같다. 사실 다음 유도는 조금 괜히 어렵다.