안녕하세요, 조교입니다.

오늘은 EM Algorithm에 대해 조금 더 살펴보도록 하겠습니다.

먼저, 거의 대부분의 머신러닝 문제는 결국 model distribution  $\log p(x;\theta )$ 를 maximize하는 Maximum Likelihood Estimation (MLE)를 통해 해결합니다.

왜 MLE가 그렇게 중요할까요? 이 MLE는 결국  \int p_{r}(x)\log{p(x;\theta)}dx=-\int p_{r}(x)\log{\frac{p_{r}(x)}{p(x;\theta)}}dx+\int p_{r}(x)\log{p_{r}(x)}dx=-D_{KL}(p_{r}(x)\Vert p(x;\theta))-H(p_{r}(x))  ∫p​r​​(x)logp(x;θ)dx=−∫p​r​​(x)log​p(x;θ)​ ​p​r​​(x)​​dx+∫p​r​​(x)logp​r​​(x)dx=−D​KL​​(p​r​​(x)∥p(x;θ))−H(p​r​​(x)) 인데요, 여기서  D_{KL}(p_{r}(x)\Vert p(x;\theta))  D​KL​​(p​r​​(x)∥p(x;θ)) 는 data distribution  p_{r}(x)  p​r​​(x) 과 model distribution  $p(x;\theta )$ 가 얼마나 다른지 측정하는 measure입니다. 또한,  H(p_{r}(x))  H(p​r​​(x)) 은 data distribution의 entropy로, optimization target인  $p(x;\theta )$ 와는 무관한 항이기 때문에 MLE는 결국  D_{KL}(p_{r}(x)\Vert p(x;\theta))  D​KL​​(p​r​​(x)∥p(x;θ))  minimization 문제가 됩니다. 즉, MLE는 KL divergence minimization으로 생각할 수 있어서 중요한 것이 됩니다.

그렇다면 latent variable model에서도 MLE를 할 수 있을까요? 거의 대부분의 경우 이는 불가능합니다. 왜냐하면  $\log p(x;\theta )=\log \int p(x,z;\theta )dz$ 에서 우리는 integration을 tractable하게 계산할 수 없기 때문입니다. 이러한 intractable likelihood를 maximize하기 위한 두가지 방법론이 EM Algorithm과 Variational Inference이고, 우리는 오늘 EM Algorithm에 대한 소개를 드리도록 하겠습니다.

EM Algorithm의 Expectation step에서는  Q(\theta\vert\theta_{old})=\int p(z\vert x;\theta_{old})\log{p(x,z;\theta)}dz  Q(θ∣θ​old​​)=∫p(z∣x;θ​old​​)logp(x,z;θ)dz 로 정의합니다. 이 식은 어떤 것과 같냐면, \int p(z\vert x;\theta_{old})\log{p(x,z;\theta)}dz=\int p(z\vert x;\theta_{old})\log{\frac{p(z\vert x;\theta)p(x;\theta)}{p(z\vert x;\theta_{old})}}+\int p(z\vert x;\theta_{old})\log{p(z\vert x;\theta_{old})}dz  ∫p(z∣x;θ​old​​)logp(x,z;θ)dz=∫p(z∣x;θ​old​​)log​p(z∣x;θ​old​​)​ ​p(z∣x;θ)p(x;θ)​​+∫p(z∣x;θ​old​​)logp(z∣x;θ​old​​)dz  가 됩니다. 조금 더 풀어쓰면 결국 이는 \log{p(x;\theta)}-D_{KL}(p(z\vert x;\theta_{old})\Vert p(z\vert x;\theta))-H(p(z\vert x;\theta_{old}))  logp(x;θ)−D​KL​​(p(z∣x;θ​old​​)∥p(z∣x;θ))−H(p(z∣x;θ​old​​))가 되는데요, 여기서  H(p(z\vert x;\theta_{old}))  H(p(z∣x;θ​old​​)) 는 고정한  \theta_{old}  θ​old​​ 로 생성한 posterior  p(z\vert x;\theta_{old})  p(z∣x;θ​old​​) 의 entropy이기 때문에 constant가 되겠습니다. Maximization step에서는  \theta^{*}=argmax_{\theta}Q(\theta;\theta_{old})  θ​∗​​=argmax​θ​​Q(θ;θ​old​​) 를 수행하기 때문에 결국 우리가 optimize하게 되는 대상은 log-likelihood가 아니라  \log{p(x;\theta})-D_{KL}(p(z\vert x;\theta_{old})\Vert p(z\vert x;\theta))  logp(x;θ)−D​KL​​(p(z∣x;θ​old​​)∥p(z∣x;θ)) 가 되는 것입니다.

자연스럽게 떠오르는 질문은 다음과 같습니다: EM style로 optimize하면, 즉 log-likelihood - KL을 optimize하면, log-likelihood를 optimize한 것에 비해 얼마만큼의 손실이 있을까? 먼저, 이를 조금 더 잘 이해하려면 loss surface를 생각해야 합니다. 우리가 원래 optimize하고자 했던 log-likelihood의 loss surface와 우리가 실제로 optimize하는  Q(\theta;\theta_{old})  Q(θ;θ​old​​) 의 loss surface가 다르기 때문에 iterative EM의 convergence point가 log-likelihood loss surface의 global (혹은 local) maxima로 converge하지 않을 수 있습니다.

특수한 경우에는 iterative EM의 convergence point가 global maximum을 guarantee하는 상황이 존재하지만 일반적으로는 local maximum으로도 converge하지 않을 수 있습니다. 그렇기 때문에 Variational Inference 알고리즘에 비해 EM Algorithm은 최근들어 많이 사용되지 않고 있습니다. Variational Inference는  \log{p(x;\theta)}-D_{KL}(q(z\vert x;\phi)\Vert p(z\vert x;\theta))  logp(x;θ)−D​KL​​(q(z∣x;ϕ)∥p(z∣x;θ)) 를  $(\varphi ,\theta )$ 두 parameter에 대해 동시에 optimize하는 문제로,  p(z\vert x;\theta_{old})  p(z∣x;θ​old​​) 가 free distribution  $q(z|x;\varphi )$ 로 바뀌게 되어 EM보다 조금 더 유연하게 optimize를 하게 되고, 결국 Variational Inference의 loss의 global maximum은 log-likelihood의 global maximum과 정확히 일치합니다.