EM 알고리즘 예시로 쉽게 이해하기 (Expectation maximization, EM algorithm)

 기댓값 최대화 알고리즘(expectation-maximization algorithm, EM algorithm)은 모수에 관한 추정 값으로 로그 가능도(log likelihood)의 기댓값을 계산하는 기댓값 (E) 단계와 이 기댓값을 최대화하는 모수 추정값들을 구하는 최대화 (M) 단계를 번갈아가면서 적용한다. 이 두 단계(2-step)를 번갈아 가며 최적화 값을 찾아가는 알고리즘으로 이해하면 된다.

 

 

참고로, 가능도 함수(Likelihood function) 는 다음 포스팅에서 언급되어 있으니 확인이 가능하다.

로지스틱 회귀 분석 예시로 쉽게 이해하기

 

 EM알고리즘을 쉽게 이해하기 위해 다음 예시를 살펴보자.

 

 

상태를 아는 경우 (State Known)

 동전 A와 동전 B가 주어진다. 다만, 각 동전의 앞/뒷면이 나올 확률을 모르고 이를 구하고자 한다. 이때 어떤 랜덤 한 확률로 동전을 한 개 선택한다. 동전 B가 처음 선택되었다면 이 동전을 10번 던져 앞면(H) 혹은 뒷면(T)이 나온 결과를 차례로 적는다. 이렇게 동전을 선택하고 10번 던지는 과정을 5 차수 반복한다.

 

 

 여기서 우리는 각 차수 마다 어떤 동전을 선택했는지 알고 있다(State Known). 이때 동전 A와 동전 B 각각의 앞/뒷면이 나올 확률을 구하고 싶다. 이를 구하기 위해서는 maximum likelihood(최대 가능도)를 사용한다. 다음과 같이 동전 A를 선택하였을 때 앞면이 나온 총 횟수 24와 뒷면이 나온 총 횟수 6을 사용하여 앞면이 나올 최대 가능도는 $\frac{24}{24+6} = 0.8$을 구할 수 있다.

 

 

 마찬가지로 동전 B의 앞면이 나올 확률 0.45를 구할 수 있다. 각 차수마다 어떤 동전을 선택했는지 아는 상태이기에, 한 차수에는 한 동전에 대한 가능성만을 계산한다.

 

 

상태를 모르는 경우 (State Unknown)

 위 예시와 동일하지만 한가지 정보가 빠진 상태로 동전 A와 동전 B 각각의 앞/뒷면이 나올 확률을 구하고자 한다. 이 때는 동전을 선택할 때 어떤 동전이 선택되었는지를 모른 상태로 앞/뒷면이 나온 결과가 10번 5차례 주어진다. 즉 각 차수가 어떤 동전이 선택되었는지를 추가로 추측해야 하며, 위 예시와 동일하게 각 동전의 앞/뒷면이 나올 확률을 구해야 한다.

 

 

 이를 해결하기 위해 EM Algorithm을 사용한다. 사용된 총 동전 개수를 의미하는 변수를 Hidden variable 또는 latent variable이라고 한다.

 

 

EM 알고리즘 (Expectation maximization)

초기값

 처음에는 모수 추정값인 동전 A의 앞면이 나올 확률 $\hat{\theta}_A^{(0)}$과 동전 B의 앞면이 나올 확률 $\hat{\theta}_B^{(0)}$ 에 랜덤으로 확률 값을 넣어준다.

 

• $\hat{\theta}_A^{(0)} = 0.6$
• $\hat{\theta}_B^{(0)} = 0.5$

E-Step

 Hidden variable의 responsibility를 계산하는 단계이다.

 주어진 추정값(처음은 랜덤 한 값)을 사용하여 각 차수의 각 동전에 대해 앞/뒷면이 나올 확률을 구해본다. 1번 차수에서는 HTTTHHTHTH로 된 sequence (H=앞면, T=뒷면)가 데이터로 주어져 있으며 각 동전의 추정 값을 사용하여 이 sequence가 나올 확률을 구해본다.

• 동전 A를 사용한 경우 $a = 0.6^5*0.4^5 = 7.96e-05$
• 동전 B를 사용한 경우 $b = 0.5^5*0.5^5 = 9.76e-05$
• 1차수에서 동전 A를 사용했을 비율(responsibility): $a/(a+b) = 0.45$
• 1차수에서 동전 B를 사용했을 비율(responsibility): $b/(a+b) = 0.55$

 계산을 하다 보면 추정 값이 A는 0.6으로 B의 0.5보다 더 높기 때문에, H가 많이 나온 sequence에서는 A동전의 responsibility가 더 높게 나온 다는 것을 볼 수 있다.

 이러한 과정을 각 차수에 대해 모두 시행한다.

 

 

M-Step

 추정값 $\theta$를 update 하는 단계이다.

 상태를 아는 경우 (State Known) 예시에서는 각 차수에서 어떤 동전이 선택되었는지 알았기 때문에 각 동전에 대해 responsibility를 1 또는 0으로 확실하게 줄 수 있었다. 때문에 총 H와 T의 개수로 최대 가능도를 구할 때 각 차수마다 특정 동전만 사용하여 계산을 하였다.

 반면 상태를 모르는 경우 (State Unknown) 확신할 수 없기에 E-step에서 계산한 responsibility를 사용하여 확률을 계산해준다.

• 1차수 sequence : HTTTHHTHTH (H: 5번 T: 5번)
• 동전 A인 경우 1차수 H개수: 0.45*5 = 2.2
• 동전 A인 경우 1차수 T개수: 0.45*5 = 2.2
• 동전 B인 경우 1차수 H개수: 0.55*5 = 2.8
• 동전 B인 경우 1차수 T개수: 0.55*5 = 2.8
• …
• 동전 A인 경우 전체 H : 21.3
• 동전 A인 경우 전체 T : 8.6
• 동전 B인 경우 전체 H : 11.7
• 동전 B인 경우 전체 T : 8.4

 

추정값 update

• $\hat{\theta}_A^{(1)} \approx \frac{21.3}{21.3+8.6} \approx 0.71$
• $\hat{\theta}_B^{(1)} \approx \frac{11.7}{11.7+8.4} \approx 0.58$

이후 E-step, M-step을 차례로 반복하면 local maximum으로 답을 찾을 수 있다.

 

---

 예시에서는 Hidden variable을 2개로 가정하였지만 실제 variable은 3개 또는 5개 등 다른 개수였을 수도 있다. 결국 variable에 대한 가정이 잘 맞아야 결과도 좋게 나올 수 있다.

 EM 알고리즘은 정답 label없이 전혀 알지 못하는 hidden variable에 대한 값을 풀 수 있다는 특징이 있다. 가정을 잘 세웠다면 EM 알고리즘을 적절히 사용하여 원하는 결과를 얻을 수 있다.

 

Chain Model에 관심이 있다면 다음 글도 확인해보면 도움이 된다.

은닉 마르코프 모델 예시로 쉽게 이해, HMM(Hidden Markov Model)

 

 

 

참고자료:

What is the expectation maximization algorithm? - Chuong B Do & Serafim Batzoglou

personal.utdallas.edu/~prr105020/biol6385/2018/lecture/lecture_4_em_paper.pdf