Expectation Maximization

이번 장에서는 EM 알고리즘에 대해서 알아본다.

objective function 이 주어졌을 때, 최적화 문제를 푸는 방법은 다양하다. EM 알고리즘의 경우는 maximum likelyhood 나 posteriori(MAP) 설정되어 있는 목적함수의 parameter를 찾는 방법이다. 매 step마다 해를 변경해가면서 최적의 parameter를 찾아간다. EM 알고리즘의 경우는 서로 다른 step을 번갈아가면서 해를 찾아간다. 그 step은 E와 M으로 나뉜다.

E는 Expectation의 E 이고, M은 Maximization의 M 이다. 기댓값을 찾는 과정과 최댓값을 찾는 과정을 반복하는 것이다. E step 은 parameter를 고정시켜 놓고 likelyhood값의 기댓값을 구한다. M step은 그렇게 계산된 기댓값을 다시 최대화하는 parameter를 추정한다.

 왜 번갈아 가면서 이 작업을 수행하느냐? 추정하고자 하는 데이터 이외에 관측되지 않은 state가 존재하기 때문이다. 이걸 모르면 정확하게 likelyhood를 구할 수 없고, 쉽게 계산이 안되는 것을 앞전에 베이지안 네트워크 부분에서 알아보았다.

 그래서 관측값에 대한 기댓값을 계산하고, 이를 고정시키고 parameter를 추정하고, 이 parameter 하에서 다시 관찰하지 못한 값에 대해서 기댓값을 계산하는 과정을 반복하다 결국 수렴을 하게 되는 방식으로 추정한다. 

 

 이번 장에서는 Gaussian Mixture 에 EM알고리즘이 어떻게 사용되는지 알아본다.

 

 직관적인 알고리즘인 K means 알고리즘을 예를 들면서 EM이 어떤식으로 돌아가는지 알아보자. K means에서 목적함수는 풀어서 설명하면 어떤 데이터가 다른 클러스터의 centroid와의 거리가 최대가 되게끔 하는 식으로 흘러간다. 이 때 생각해보면 먼저 사전에 centroid $\mu$를 구하고, 그런 다음 데이터들이 어디속할지 모르니 각 관측치별로 centroid와의 거리를 계산하고, 또 centroid $\mu$를 구하면서 수렴할 때까지 가는 과정을 떠올려볼 수 있다. 이게 위에서 얘기한 기댓값을 계산하고, 이를 고정시키고, parameter를 또 업데이트하고 다시 기댓값을 또 구하는 과정과 연결지어 볼 수 있다.

 

 Gaussian Mixture

 

 가우시안 혼합모델은 k means와는 조금 다른 방식으로 클러스터링을 진행한다. 우리가 가진 데이터가 서로 다른 정규분포에서 얻어진 것이라는 가정. 즉 정규분포의 혼합체로써 전체 데이터를 설명할 수 있다는 것으로 시작한다.

 아래의 수식을 보면 어떤 데이터에 분포를 알기 위해 K 개의 클러스터 즉, 정규분포가 있고, 각 분포들의 혼합으로 결정되어 있는 것을 볼 수 있다. 괄호 안에 평균 벡터 $\mu$와 공분산행렬인 $\Sigma$을 볼 수 있다. 그리고 $\pi$는 prior probability 사전확률이라고 하는데, 각각 클러스터들의 확률 즉, 정규분포마다의 비중을 나눠준다. 그래서 0~1 사이의 값을 가진다.

실제로는 모르지만 이럴 것이다 하고 알고자 하는 것이 $\pi, \mu, \Sigma$ 이 되고, 이를 위해 추정을 위해서는 샘플들을 활용해야한다. 이러한  샘플들이 어떻게 관찰되는지 알아보자. 확률적으로 어떻게 모델링되는지 알아보자.

 

 아래의 z는 특정 샘플이 어느 분포에서 왔는지를 나타내는 값이라고 생각하자. 우리는 현재 x 값만 관찰한 상태이다. 그렇다면 z는 k 개의 정규분포 중에서 한군데에서 뽑힌 것일 텐데 어느 정규분포에서 뽑혔는지는 알기 힘들어 latent variable이라고 부른다. 

 k개의 정규분포에서 뽑힌 z라면 그 정규분포에서 뽑힌 z 라는 것을 의미하는 joint probability 가 아래에 나와있다. 

 

 

 아래의 식같은 경우는 z의 분포를 나타내는데, $z_{i} \in (1,0)$ 이라서 포함되는 k 아니면 전부 0 이기 때문에 포함되는 k 에 대해서만 1의 값을 갖는다.

이를 일반화하면 아래와 같은 식으로 표현을 할 수 있다. 선택된 클러스터 k 의 파이값만 남는 것을 말하고, 특정 분포가 선택 되었을 때 x는 선택된 분포를 따르게 되니까 아래와 같이 죽 전개가 가능하다. 그래서 실제 marginal distribution은 joint distribution에서 모드 가능한 z에 대한 것을 구하고 더하면 계산을 할 수 있게 된다.

 

 

우리가 가정한 상황하에서 p(x)의 marginal distribution을 구하였다. 이제 관찰한 x를 가지고 $\pi_{k}, \mu_{k}, \Sigma_{k}$ 를 구해야한다. 그래서 likelyhood function을 계산해야한다. 각 샘플이 모두 독립적이다 가정을 하기 때문에 p(x)의 marginal distrubution에서 $x_{i}$값을 넣어 n 개의 샘플들에 대해서 모두 곱한 것이 곧 likelyhood function이 된다. 그래서 위의 수식에서 본 것을 합쳐주면 아래의 우항의 수식을 얻을 수 있다. 일반적으로 확률값들을 곱하는 것이다보니 log를 취하여 계산하게 된다.

 

likelyhood function

log likelyhood function

 이제 likelyhood function을 최소화하기 위해서 아래와 같이 $\mu_{k}, \Sigma_{k}$를 편미분하여 0이 되게 하는 계산을 수행한다.

  아래는 $\mu_{k}$로의 미분과정을 나타내고 있다. 일반적으로 알고 있는 $ln(x)$의 미분값을 $\frac{1}{x}$ 가 되고, $\mathit{log} \ f(x)$ 의 경우에는 미분하면 $\frac{1}{f(x)} f'(x)$ 가 된다. 아래의 수식에서 sum으로 묶인 term의 분모가 $\frac{1}{x}$와 같이 전자에 해당하고 나머지 분자부분과 곱해진 부분이 후자에 해당되게 된다. 

아래는 복잡한 전개를 $\mu_{k} \ = $ 이라는 형태로 바꾸어 주기 위한 전개이다.

마찬가지로 $\Sigma_{k}, \pi_{k}$ 에 대해서도 전개하여 준다. $\gamma(z_{ik})$ 의 경우에는 $\Sigma_{j}, \mu_{j}$에 dependent 하기 때문에 analitically 하게 최적화 문제를 풀 수 없다. 

 

 

EM알고리즘은 앞서 얘기한 것처럼 먼저 초기에 k means 클러스터링처럼 유사하다. 샘플들이 어디 클러스터에 속하는지 알면 centroid를 계산할 수 있다. centroid를 구하려면 마찬가지로 샘플들이 어디 클러스터에 속하는지를 알아야 한다. 이런 의존적인 부분이 비슷하다.

 샘플들의 클 $\gamma(z_{ik})$ 를 안다고 가정하면, $\mu_{k}, \Sigma_{k}, \pi_{k}$를 구할 수 있다. 반대로 $\mu_{k}, \Sigma_{k}, \pi_{k}$ 를 알면 $\gamma(z_{ik})$를 구할 수 있다. 그래서 여기서 이 두개를 분리해서 계산을 한다. 하나하나 값을 산정해줄 수 없는 상황이기 때문에 티키타카를 해야한다. 

 

 Gaussian Mixture 모델에서 EM알고리즘을 통해서 parameter를 추정하는 과정을 보자. 

 

1. log likelyhood 의 초깃값을 계산하기 위해 $\mu_{k}, \Sigma_{k}, \pi_{k}$ 를 initialize 한다. 초깃값을 셋팅해주어야 한다. $\pi_{k}$ 는 모두 더해 합이 1이 나오게, $\Sigma_{k}$는 공분산행렬이니 symmetric해야하고, $\mu_{k}$는 어느 값이와도 상관 없다.

 

2. 이제 Expectation 단계이다. 초기화한 값을 가지고 아래의 responsibilities 값을 계산한다. 

 -> $\pi$가 주어 졌다고 하면 결국 이 단계는 $x_{i}$에 대한 확률분포 값이다. 잠재변수의 기댓값을 찾는 과정이라 생각하면된다.

 

Expectation

3. Maximization 단계이다. 구한 responsibilities 를 가지고 k 개의 정규분포의 평균, 공분산행렬, prior probability($\pi_{k}$)를 업데이트 할 수 있게 된다.

 -> 잠재변수의 기댓값을 기준으로 parameter를 추정하는 단계라 생각하면 된다.

Maximization

특정 convergence를 만족할 때까지 2, 3 과정을 계속해서 반복해주면 된다.

 

 

위 그림은 초깃값으로 시작하여 EM step을 반복하다가 최종적으로 평균과 분산으로 분포를 추정해내는 것을 보여 준다. 아래의 위키피디아의 움짤을 보면 어떤식으로 추정이 되어가는지 쉽게 이해할 수 있다.

en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm#/media/File:EM_Clustering_of_Old_Faithful_data.gif

Expectation–maximization algorithm - Wikipedia

 

EM 알고리즘의 경우 local optimal 은 보장하지만 global하게는 보장을 못한다는 것을 염두에 두어야한다. 완벽한 global parameter를 찾는 것은 사실 불가능하다고 할 수 있다. 초깃값에 따라 local point 또한 달라진다.