[참고] http://www.seanborman.com/publications/EM_algorithm.pdf
보통 Maximum Likelihood estimate 방법을 사용해서 관측된 데이터에 알맞은 모델의 변수(parameter)를 추정한다. "
즉, 어떤 모델의 변수를 모르는 경우에 이를 추정하는 방법이라는 건데,
초기에 랜덤하게 혹은 어떤 다른 방법으로 모델 변수를 설정한 상태에서, 관측데이터(X)가 이 모델(ramda_0)로부터 생성되었을 확률을
계산한다.
P(X | ramda_0 )
이제 모델 내부의 변수를 아주 조금 수정한 새로운 모델을 ramda_1 이라고 하자.
그리고 나서 다시 관측데이터의 posterior 확률을 구하면
P(X | ramda_1 )
자, 이제 어떤것이 더 큰지 결정한다.
만약 P(X | ramda_1 ) 이 더 크다면, 우리는 ramda_1이 ramda_0 보다 더 관측데이터(X)가 나올법한 모델이라는 것을 알 수 있다.
그 다음에는 어떻게 하는가?
위 작업을 계속 반복하는 것이다. 이것이 iterative procedure
그러면 언제 멈추는가? 새로운 모델 ramda에 대한
P( X | ramda ) 가 기존 모델보다 부적합한 경우(likelihood가 더 작은 경우)에 멈추면 된다.
음...
좀더 진행하면 현재보다 더 좋은 모델이 나올 가능성은 있지만 말이다. 그래서 local maximum을 찾는 다고 하는 것이다.
다시 본론으로 들어가서, 그러면 E-step, M-step은 무엇인가?
확실한 예가 없어서 이해하기 힘들기는 하다.
계속 살펴보도록 하자.
ramda 대신에 theta를 쓰면,
P( X | theta ) 는 관측데이터 X가 있을 경우, theta에 대한 likelihood 이며
로그 함수를 씌우면
L(theta) = ln P( X | theta )
이것을 일반적인 log likelihood function 이라고 부른다.
"우리가 원하는 것은 L(theta)를 최대로 하는 모델 theta를 찾자는 것이다."
EM 알고리즘의 iterative procedure에서는
L(theta_current_max) > L(theta_n)
theta_current_max가 현재까지 가장 L 값이 큰 모델이라면, 위와 같은 조건이 만족되는 경우, 정지하면 된다.
음... 현재까지는 hidden variable에 대해 고려하지 않고 수식을 전개했는데, 이를 포함시켜보자.
위 (10) 번 수식은 현재까지 언급되던 theta를 hidden variable Z , known variable theta 로 분리시킨 것이다.
( 이 수식 전개는 partition theory 를 참고하면 된다. )
이를 이용하면, 위 (9) 번 수식을 아래와 같이 쓸 수 있다.
음... 대충 수식 관련 눈팅만 했다.
이제부터는 E-step, M-step에 대해서 좀더 알아보자.
[참고] http://en.wikipedia.org/wiki/Expectation-maximization_algorithm
위에서 기술한 바와 같이,
P( X | theta ) 에서 theta는 hidden variable을 포함하고 있다. 따라서, 처음 시작은
그냥 아는 변수는 그대로 하고, 모르는 변수에 대해서만 랜덤하게 값을 설정해준다.
즉, 다시 theta를 hidden variable z 와 known variable theta 로 분리하면
P( X | Z, theta )
여기서, Z에 대해서만 랜덤으로 설정해 준다는 것이다.
그리고 나면,
current parameter estimate를 알고 있으니, 이를 이용해서 hidden variable에 대한 expectation 값을 계산할 수 있다.
즉, Z에 대한 expected estimate를 계산할 수 있다.
이게 먼 말인고?
간단히 얘기하면, Z=(z1, z2, z3) theta=(t1, t2, t3, t4)
이렇게 element가 있다고 하면
우리는 theta 값을 알지만, Z 값을 모르니
t1, t2, t3, t4, 초기에 설정된 z1, z2, z3 에 대해서 평균값으로
z1, z2, z3를 다시 설정하겠다는 것이다.
그림으로 표현해보면
초기에 swallow, bug, insect 는 모르는 변수이고, 그래서 전부 0으로 설정하고
나머지에 대해서만 관측되었다고 했을 때,
Expectation 단계에서는 (아는 것 + 모르는 것) 전체에 대한 평균값을 계산해서
모르는 값에 평균값을 설정하겠다는 의미이다.
이 부분은 사실 Maximum Entropy Model과 아주 비슷하다.
오캄의 면도칼(ocam's razer)이라는 건데, 여러가지 가설중에서 가장 간단한 가설이 진리일 확률이 높다는 얘기다.
즉, 잘 모르면 그냥 평균값을 사용하라는 것.
그렇다면, Maximization 단계는 멀 하는 걸까?
여기서는 앞서 Expectation 단계에서 우리가 모르는 Z값에 대해 추정해 뒀기 때문에, ln P( X | Z, theta ) 값을 새롭게
계산할 수 있을 것이다.
이렇게 계산된 ln P( X | Z, theta ) 값이 기존 likelihood 값보다 더 크다면, 이것이 더 관측데이터에 적합한 모델이므로
해당 모델을 교체한다.
아니면 반복 과정을 정지시키던가....
혹은, likelihood 값의 변화량이 어떤 음수값보다 더 커지면 정지하는 방법도 있다.
이것은 search space를 탐색하는 이론을 참조하면 될 것이다.
다른 그림을 이용해서 살펴보면 아래와 같다.
[참고] http://www.cs.jhu.edu/~jason/465/PowerPoint/lect26-em.ppt
동전던지기에 대한 EM 예제는 다음 URL을 참고하면 된다.
[참조] http://www.nature.com/nbt/journal/v26/n8/full/nbt1406.html
위의 2번 화살표 아래쪽에 있는 값들은 아래와 같이 계산되었다.
A를 던졌을 때,
앞면이 나올 확률 0.6
뒷면이 나올 확률 0.4
P( HTTTHHTHTH )
= 0.6^5 * 0.4^5 = 0.07776 * 0.01024 = 0.0007962624
B를 던졌을 때,
앞면이 나올 확률 0.5
뒷면이 나올 확률 0.5
P( HTTTHHTHTH )
= 0.5^5 * 0.5^5 = 0.03125 * 0.03125 = 0.0009765625
0.0007962624 0.0007962624
---------------------------- = ---------------- = 0.4491489261009364207373215482251
0.0007962624 + 0.0009765625 0.0017728249
따라서,
A를 0.449회
B를 0.551회
던졌을 것이다.
A를 0.45, B를 0.55 회 던졌다고 계산되었는데, 실제 H는 5회, T는 5회 나왔다.
그렇다면, A에 대해서
0.45 * 5 H = 2.2 H
0.45 * 5 T = 2.2 T
B에 대해서
0.55 * 5 H = 2.8 H
0.55 * 5 T = 2.8 T
위 그림을 프로그램으로 구현한 결과 참조 http://blog.daum.net/comefeel/6935672
(동료분이 구현해 주셨음 ㅋㅋ)
to be continued...
[출처 : http://blog.daum.net/hazzling/17067790]