[머신 러닝] 5. EM(Expectation-Maximization) Algorithm(알고리즘)에 대해서 알아보자.

---

오늘은 최대 우도 추정량을 구하는 방법 중에 하나인 EM Algorithm(알고리즘)에 대해서 알아보려고 한다.

---

---

본 포스팅에서는 수식을 포함하고 있습니다.

티스토리 피드에서는 수식이 제대로 표시되지 않을 수 있으니

PC 웹 브라우저 또는 모바일 웹 브라우저에서 보시기 바랍니다.

---

---

   EM 알고리즘이란?

EM 알고리즘이란 무엇인가

EM(Expectation-Maximization) 알고리즘은 Latent 변수를 도입하여 최대 우도 추정량을 구하는 방법이다. 여기서 Latent 변수는 실제로 관측이 되지 않았지만 관측된 데이터에 상호 영향을 미치리라 판단되는 변수를 말한다. 예를 들면 Gaussian Mixture 모형에서 그룹을 나타내는 변수가 Latent 변수에 해당한다. 왜냐하면 그룹 변수는 실제로 관측되지 않았지만 데이터에 영향을 주어 데이터가 특정 그룹에 속했다고 생각할 수 있기 때문이다. Latent 변수를 도입하는 이유는 모형과 알고리즘에 대한 해석을 자연스럽게 해 주며 EM 알고리즘을 통하여 최대 우도 추정량을 비교적 쉽게 추정할 수 있기 때문이다.

---

이제 EM 알고리즘을 정의하기 위해 필요한 재료는 실제로 관측된 데이터 $X$, Latent 변수 데이터 $Z$ 그리고 최대 우도 추정법으로 추정해야할 파라미터 $\theta$인 것을 짐작할 수 있다. EM 알고리즘은 $\theta$를 Analytical 하게 한방에 구하는 알고리즘이 아니다. 주어진 $\theta^*$를 이용하여 업데이트 해나가야하는 Iterative 알고리즘이다. 따라서 EM 알고리즘을 정의하는데 $\theta$의 현재 추정값 $\theta^*$이 추가적으로 필요하다.

 

EM 알고리즘을 최대 우도 추정량을 구하는 방법이라고 했다. 보통 최대 우도 추정량을 구하기 위해서 다음과 같은 로그 우도 함수를 생각한다.

$$l(\theta; x) := \log f_{\theta}(x)$$

여기서 $x$는 $X$의 관측값, $f_{\theta}(x)$는 $X$의 확률 밀도 함수(이산형인 경우 확률 질량 함수)이다. 이때 로그 우도 함수를 최대화 하는 $\theta$를 찾는 것이 최대 우도 추정법이다. 그럼 끝난 거 아니냐 할지 모르지만 앞에서 'Latent 변수' $Z$를 도입한다고 하였다. 근데 $Z$는 관측 된 것이 아니므로 로그 우도 함수에 직접적으로 끼워줄 수 없다. 따라서 다음의 식을 이용한다.

$$f_{\theta}(x) = \frac{f_{\theta}(x,z)}{f_{Z|X, \theta}(z)}$$

위 식 양변에 로그를 취해주자.

$$l(\theta; x) = \log f_{\theta}(x,z) - \log f_{Z|X, \theta}(z)$$

그리고 파라미터 추정값 $\theta^*$에 의존하는$Z$의 조건부 확률 밀도 함수 $f_{Z|X, \theta^*}(z)$를 양변에 곱한 다음 $z$에 대해 적분(이산형인 경우 합)을 취해주자.

$$\begin{align}l(\theta; x) &= \int_z l(\theta; x) f_{Z|X, \theta^*}(z) dz \\ &= \int_z \left\{\log f_{\theta}(x,z)\right\}  f_{Z|X, \theta^*}(z) dz - \int_z \left\{\log f_{Z|X, \theta}(z)\right\} f_{Z|X, \theta^*}(z) dz \\ &= Q(\theta|\theta^*) + H(\theta|\theta^*)\tag{1}\end{align}$$

첫 번째 등식은 $l(\theta; x)$가 $z$와 관계없고 확률 밀도 함수의 적분값은 1이기 때문에 성립한다.

 

이제 식(1)을 통하여 $l(\theta; x)$를 최대화하는 것은 $Q(\theta|\theta^*) + H(\theta|\theta^*)$화 하는 문제와 같아진다. 이때 EM 알고리즘은 $\theta^*$가 주어진 상황에서 $Q(\theta|\theta^*)$를 최대화하는 $\theta$를 찾는다. 왜냐하면 $Q$를 최대화하는 것이 $l(\theta; x)$을 최대화하는 것보다 일반적으로 쉽기 때문이다. 그렇다면 다음과 같은 질문을 할 수 있다.

---

$Q$를 최대화하는 $\theta$는 $l(\theta; x)$을 최대화하는 $\theta$와 같은가?

---

아니다. 그렇다면 사람들이 다음과 같이 생각할 것이다.

---

오잉?? 그렇다면 왜 EM 알고리즘을 사용하는가? 지금 나랑 장난하자는 건가!

---

아니다. 왜냐하면 EM 알고리즘은 $l(\theta; x)$을 최대화하는 $\theta$를 찾는데 도움이 되기 때문이다. 그러면 어떻게 도움이 되는지 알아보자.

 

식 (1)에서 $\theta$대신 $\theta^*$를 넣으면 다음과 같이 된다.

$$l(\theta^*; x) = Q(\theta^*|\theta^*) + H(\theta^*|\theta^*)\tag{2}$$

이제 (1) 식에서 (2)식을 빼주자. 그러면 다음과 같아진다.

$$l(\theta; x) - l(\theta^*; x)= Q(\theta|\theta^*) - Q(\theta^*|\theta^*) + H(\theta|\theta^*) -H(\theta^*|\theta^*)\tag{3}$$

식 (3)에서 $H(\theta|\theta^*) -H(\theta^*|\theta^*)$을 살펴보자.

$$\begin{align}H(\theta|\theta^*) -H(\theta^*|\theta^*) &= \int_z \left\{\log f_{Z|X, \theta^*}(z)\right\} f_{Z|X, \theta^*}(z) dz -\int_z \left\{\log f_{Z|X, \theta}(z)\right\} f_{Z|X, \theta^*}(z) dz \\ &= -\int_z \left\{\log\frac{f_{Z|X, \theta}(z)}{f_{Z|X, \theta^*}(z)}\right\} f_{Z|X, \theta^*}(z) dz \\ &\geq -\log \int_z \left\{\frac{f_{Z|X, \theta}(z)}{f_{Z|X, \theta^*}(z)}\right\} f_{Z|X, \theta^*}(z) dz = 0\end{align}$$

부등식의 경우 Jensen's 부등식을 이용하였다.

---

참고)

위 부등식은 $Z$가 이산형인 경우는 상관이 없지만 연속형인 경우 각 적분값이 유한하고 다음과 같은 가정이 있어야 한다.

$$f_{Z|X, \theta}(z) > 0 \;\;\text{ almost everywhere } \;\;\forall\; \theta$$ 

이러한 가정이 있어야 위 부등식 증명에서 두 번째 등식이 성립한다.

---

위 부등식을 이용하면 다음과 같이 쓸 수 있다.

$$l(\theta; x) - l(\theta^*; x)\geq Q(\theta|\theta^*) - Q(\theta^*|\theta^*) \tag{4}$$

부등식 (4)가 EM이 최대 우도 추정량을 구하는데 왜 도움이 되는지를 알려주는지를 알려준다.

 

$\theta^{(t)}$가 주어진 상황에서 $Q(\theta|\theta^{(t)})$를 최대화하는 $\theta$를 $\theta^{(t+1)}$라고 하자. 그렇다면 부등식 (4)에 의하여 다음을 알 수 있다.

$$l(\theta^{(t+1)}; x) - l(\theta^{(t)}; x) \geq Q(\theta^{(t+1)}|\theta^{(t)}) - Q(\theta^{(t)}|\theta^{(t)}) \geq 0\tag{5}$$

부등식 (5)가 의미하는 바는 $\theta^{(t)}$가 주어진 상황에서 $Q(\theta|\theta^{(t)})$를 최대화하는 $\theta$는 우도 함수값 $l(\theta; x)$도 증가시킨다는 것이다. 즉, $\theta^{(t)}$가 주어진 상황에서 $Q(\theta|\theta^{(t)})$를 구하고 $Q(\theta|\theta^{(t)})$를 최대화하는 $\theta^{(t+1)}$를 찾는 작업을 반복한다. 이렇게 구한 최종 추정량 $\hat{\theta}$는 최대 우도 추정량이 될 가능성이 있다는 것이 EM 알고리즘의 아이디어이다. 따라서 EM 알고리즘은 최대 우도 추정량을 찾는데 도움이 되는 것이다.

반응형

---

이제 EM 알고리즘을 정의해보자.

 

알고리즘)

단계 1) 파라미터 초기값 $\theta^{(0)}$을 설정한다.

 

단계 2) $\theta^{(t)}$에 대하여 다음을 계산한다.

$$\begin{align}Q(\theta|\theta^{(t)}) &= \int_z \left\{\log f_{\theta}(x, z)\right\} f_{Z|X, \theta^{(t)}}(z) dz \\ &=E_{Z|X, \theta^{(t)}}\left\{\log f_{\theta}(X, Z) \right\} \end{align}$$

이 단계는 조건부 기대값을 구하는 과정이라 볼 수 있어서 Expectation Step이라고 한다.

 

단계 3) $Q(\theta|\theta^{(t)})$를 최대화하는 $\theta^{(t+1)}$을 찾는다. 즉, 

$$\DeclareMathOperator*{\argmaxB}{argmax} \theta^{(t+1)} = \argmaxB_{\theta} Q(\theta|\theta^{(t)})$$

이 단계는 $Q$를 최대화한다는 의미에서 Maximization Step이라고 한다. 이제 알고리즘 명칭이 왜 EM 인지 알았을 것이다.

 

단계 4) 수렴할 때까지 단계 2) ~ 단계 3)을 반복한다.

---

이때 $Q(\theta|\theta^*)$를 최대화하는 것의 의미에 대해서 조금만 더 짚고 넘어가도록 하자. 우리가 원래 최대화하려고 했던 우도 함수 $l(\theta; x)$를 변형해보자.

$$\begin{align} l(\theta; x) &= \log f_{\theta}(x) \\ &= \log \int_z f_{\theta}(x, z) dz \\ &= \log \int_z \left\{\frac{f_{\theta}(x, z)}{f_{Z|X, \theta^*}(z)}\right\}f_{Z|X, \theta^*}(z) dz \\ &\geq \int_z \log \left\{\frac{f_{\theta}(x, z)}{f_{Z|X, \theta^*}(z)}\right\}f_{Z|X, \theta^*}(z) dz \\ &= Q(\theta|\theta^*) + \text{const. not depend on }\theta \end{align}$$

즉, $Q$를 최대화하는 과정은 원래의 우도 함수의 Lower Bound를 최대화하는 과정과 같다. 그리고 $Q$는 원래의 우도 함수에서 로그와 적분의 위치를 바꾼 것이다. 이러한 점 때문에 $Q$를 최대화하는 것이 더 쉽다.

 

EM 알고리즘이란 무엇인가?

새로운 Latent 변수를 도입한 우도 함수에서 Expectation Step을 통해 다루기 쉬운 Lower Bound를 구하고 이를 최대화하는 과정(Maximization Step)을 반복하여 최대 우도 추정량을 추정해내는 알고리즘이다.

---

EM 알고리즘의 장단점

- 장점 -

EM 알고리즘은 각 스텝마다 우도 함수를 증가시키는 추정치를 계산할 수 있어 계산의 안정성이 보장된다. 그리고 원래의 우도함수를 최대화하는 문제보다 EM 알고리즘을 적용하는 것이 더 쉽다. 즉, Expectation Step과 Maximization Step이 원래의 우도함수를 최대화하는 과정보다 더 쉽다. 여기서 Maximization Step의 해는 Closed Form으로 나타나는 경우가 많아 계산이 훨씬 쉬워진다.

 

- 단점 -

모든 Iterative 방법들이 그러하듯이 EM 알고리즘도 Local Maxima에 빠질 위험이 있다. 또한 수렴 속도가 일반적으로 느리다. 

---

어디에 사용하는가?

Gaussian Mixture 모형, 결측치 추정, 인자 분석(Factor Analysis), Hidden Markov 모형에서 사용한다. EM 알고리즘을 활용하는 법은 해당 내용을 포스팅할 때 다루려고 한다.

---

참고자료

Kenneth Lange - Optimization

Trevor Hastie 외 2명 - The Elements of Statistical Learning

wiki - Expectation–maximization algorithm

---

---