Expectation Maximization (EM) Algorithm

Expectation Maximization(EM) Algorithm은 Latent Variable이 있는 상황에서 MLE (Maximum Likelihood Estimation)을 하기 위한 Algorithm이다.

MLE가 관측된 데이터가 어떤 모델(Function)로부터 나왔는지를 계산하기 위해 "Max"인 Likelihood(가능도)를 계산하는 모델이라고 할 때 여기서 Latent Variable은 쉽게 생각하면 관측이 되지 못한 변수를 의미한다.

우리가 평소 공부할 때는 이상적인 상황을 가정한다. 즉 필요한 데이터에 대해서는 모두 완벽히 갖추고 있다고 생각하는 경우가 많다. 하지만 현실은 그렇지 않다. 훈련데이터의 일부 Feature들이 비어있어서 Unknown Value인 경우들이 상당히 많다.

이런 경우 Imputation을 하곤 하는데 EM Algorithm은 Imputation을 위한 방법 중 하나이다.  우리가 가지고 있는 관측 데이터 집합을 $X$이라고 하고, $Z$를 Latent Variable라고 하자. 그리고 우리가 알고 싶은 Model의 Parameter를 $\theta$라고 하자. 우리가 궁극적으로 구하고 싶은 Log Likelihood의 식은 다음과 같다.

$$LL(\theta | X,Z) = lnP(X,Z | \theta)$$

여기서 문제는 "Z"가 Incomplete Data이기 때문에 Z를 구할 수 없다는 것이다. 그래서 Z를 Expectation, 즉 기대값, 다른 말로 평균이라는 값으로 퉁치는게 EM에서 "E"의 Step이다.  적당히 Parameter 값을 넣고, $P(Z|X,\theta^{0}$을 추론한다음에 Z에 대한 LIkelihood의 기댓값을 계산한다. 기댓값은 $\sum\limits_{i=1}^{n} p_i x_i$로 계산한다.

$$ Q(\theta | \theta^{0}) = E_{Z|X, \theta^{0} } LL(\theta|X,Z) $$

다음에는 Maximization Step이다. 여기서는 MLE를 통해서 Parameter를 찾는다. 그게 $\theta^1$이다.

$$\theta^1 = \argmax_{\theta} Q(\theta | \theta^{1}$$

EM Step을 반복하다 보면 어느 시점에 가서 값이 수렴(Converge)한다.

EM 외에 Gradient Descent를 통해서도 문제를 구할 수 있다. 하지만 Latent Variable 변수의 갯수에 따라 Computational Cost Issue가 발생할 수 있다. EM은 Computational Cost Issue에 대해서는 상대적으로는 자유로운 편이다.