수리통계학 - EM 알고리즘

 

오늘은 MLE와 관련하여 작성하는 마지막 포스팅으로, EM 알고리즘에 대해 글을 써보려고 한다. EM 알고리즘을 풀어쓰면 'expectation-maximization algorithm'으로, "기대값을 최대화하는 알고리즘"으로 직역할 수 있다. 그러면 EM 알고리즘은 "어떤 기대값"을 구하고자 하는 걸까, "무엇을 최대화"하려고 하는 걸까?

EM 알고리즘이란?

 

이에 대한 해답을 얻기 위해 EM 알고리즘을 언제 사용하는지, 잠시 짚고 넘어갈 필요가 있다. EM 알고리즘은 일부 데이터의 정보가 없는 상황에서 MLE를 얻어야 할 때 자주 사용된다.

 

모수에 대한 추정치를 구해야 하는 상황에서 MLE를 구하기 위한 완전한 정보가 없다. 이 때, 모수를 초기값으로 세팅해놓고 불완전한 정보까지 포함한 likelihood의 기대값을 계산한다(E단계). 여기서 구한 기대값을 최대화 하는 모수 추정값을 다시 구한다(M단계). 거기서 구한 모수 추정값을 다시 likelihood에 대입하고 다시 기대값을 구한다(E단계).... 

 

EM 알고리즘은 다음 E단계와 M단계를 반복하며 새로운 모수 추정값과 기존의 모수 추정값의 차이가 매우 작아질 때까지 반복하는 과정이다. 다시 풀어쓰면 불완전한 정보까지 포함한 likelihood 기대값을 구하고(E단계), 그 값을 최대화하는 모수 추정값을 구하는 것을 반복하여(M단계) MLE를 찾아내는 과정이라고 볼 수 있겠다.

 

수식으로 증명하면 다음과 같다. (수식입력이 귀찮아서 손으로 써버렸다..)

 

 

 

X : 관찰한 데이터

Z : 관찰하지 않은 데이터

• X와 Z는 서로 독립이라고 가정한다.
• 관찰한 데이터는 특정 분포에서 iid(identically independent distributed)하게 추출되며, 각 변수는 독립적이므로 joint pdf는 각 pdf의 product와 같다. 이것을 observed likelihood로 부르기도 한다.
• 우리에게는 관찰하지 않은 데이터도 있다. 이것을 포함한 likelihood는 complete likelihood로 부르며,
• observed likelihood와 complete likelihood를 조합하면 conditional pdf도 구할 수 있다.

이제 우리의 목표는 complete likelihood(관찰되지 않은 데이터까지 포함한 likelihood)로 observed likelihood를 최대화하고, 그 값으로 모수를 추정하는 것이다.

 

수식으로 풀고 풀고 풀면 복잡하지만,

• 관찰된 결과값, 그리고 모수에 대한 초기값을 세팅한 상태에서 관찰되지 않은 결과값에 대한 기대값을 구하고, 
• 그 기대값을 대입하여 complete likelihood(관찰되지 않은 데이터까지 포함한 likelihood)를 최대화하는 값을 찾고
• 그 값에서 도출된 모수를 다시 대입하여 위의 과정들을 반복한다.

여기까지가 수식 증명인데...

 

사실 정리한 수식도 복잡하고 직관적이지 않아 해당 포스팅만으로는 설명이 부족할 것 같기도 하고,

EM 알고리즘에 대해 설명이 더 쉽고 자세한 포스팅들이 많아서 참고 링크로 걸어둔다.(아니 정정한다. 내 기준에서 여전히 EM 알고리즘은 어렵다.)

 

개념 및 수식 정리 링크1

개념 및 수식 정리 링크2

 

EM 알고리즘의 활용

 

그렇다면 EM 알고리즘은 언제 사용하는 것일까?

 

실제 현업에서 어떻게 쓰이는지 잘 몰라 여기저기 구글링을 해본 결과, 보통 라벨에 대한 정보가 없는 상태에서 classification을 할 때 주로 사용되는 것 같다. 

 

추천 시스템 예시

문서 유사도 측정 예시

 

이는 수리통계학적 관점(?)에서 "mixture problem"이라고 부르는 것과 대응된다고 볼 수 있다.

어떤 변수가 mixture distribution을 따르는데(a조건을 만족할 때는 분포A를, b조건을 만족할 때는 분포B를 따름)

a, b조건에 대한 지식이 없을 때에도 EM 알고리즘을 사용할 수 있는데, 대개 검색해서 얻은 활용 예시가 다 이러한 mixture distribution을 따르는 분포에 대한 것들이었다.

 

mixture problem과 관련하여 코드로 잘 구현해놓은 블로그가 있어 해당 링크도 참고로 첨부한다.

 

https://analysis-slave.tistory.com/4

[R] EM 알고리즘을 통해 혼합정규분포(Gausian mixture model) 모수 추정

 

느낀점

다 쓰고 보니, 공부하는데 도움이 되었던 링크 모음집이 된 것 같지만....

결국 이게 아직까지는 내 지식으로 체화가 안 되었기에, 이렇게밖에 못 쓴 것 같기는 하다.

 

열심히 더 공부해서, 언젠가 EM 알고리즘을 현업에 써먹어보기도 했으면 좋겠다?!