Expectation Maximization

EM 알고리즘은 확률 모델에서 MLE parameters를 찾기위해 사용한다.


EM 알고리즘은 두단계를 거치는데

첫번째 단계는

               E단계( Expectation step )

두번째 단계는

              M단계( Maximization step )이다.

 running 과정에서는 이 두 단계가 계속 반복된다.

 간단한 예를 살펴보면

1. 초기값 설정

2. 반복 과정

               2.1 E-STEP : 주어진 현재 파라미터 추정치로 unknown 변수가 특정 class에 속하는지에 대한 기대값을 추정한다.

               2.2 M-STEP : unknown 변수의 기대 추정치를 가지고 데이터의 최대 확률값(MLE)을 재 추정한다.

EXAMPLE >>
[STEP1] 4,10 , ? , ?

                                Initial mean value : 0

[STEP2] 4, 10, 0 , 0

                                New Mean : 3.5{ ( 4 + 10 + 0 + 0 ) /4 }

[STEP3] 4, 10, 3.5, 3.5

                                New Mean : 5.5

[STEP4] 4, 10, 5.25, 5.25

                                New Mean : 6.125

[STEP5] 4, 10, 6.125, 6.125

                                New Mean : 6.5625

[STEP6] 4, 10, 6.5626, 6.5625

                                New Mean : 6.7825

[STEP7] 4, 10, 6.7825, 6.7825

이 과정을 반복하다 보면 Mean이 7에 가까워지는것을 볼 수 있다.

 

 파라미터를 추정하는 방법론이기 때문에 수렴 속도가 빨라지거나 하지는 않는다

LINK : http://en.wikipedia.org/wiki/Expectation-maximization_algorithm

LINK : Foundations of Statistical Natural Language Processing

LINK : http://nlp.korea.ac.kr/new/seminar/2000spring/fsnlp/Chap14_Clustering.ppt

-----------------------------------------------------------------------------------------------------