| [ KAIST ] in KIDS 글 쓴 이(By): comofcom (OSS) 날 짜 (Date): 2002년 9월 27일 금요일 오후 03시 09분 30초 제 목(Title): Re: EM algorithm 성질 여기 사람은 아니지만 주워들은 풍월이 있어서요... Expectation-Maximization(EM)은 원래 incomplete data로부터 Maximum Likelihood(ML) estimate를 찾기 위한 통계학적인 방법입니다. 따라서, EM을 likelihood라는 목적함수를 최대화하는 값을 찾는 최적화 기법이라고 볼수도 있지요. 일반적으로 최적화 프로그램을 돌렸을때의 결과는 목적함수, 최적화 기법, 초기값 이렇게 세가지 요인에 의해 결정됩니다. simulated anealing과 같은 stochastic relaxation 등은 예외로 한다면, 즉 deterministic한 최적화기법을 쓰셨다면, 위 세가지 요인이 같다면 결과는 동일하게 나와야 하겠지요. 입력데이타와 코드가 같다고 하셨으니 목적함수와 최적화 기법은 같다고 볼 수 있을 것 같구요, 초기값이 같은지는 설명을 안 해주셨군요. 만일 초기값이 적절히 주어지지 않는다면 local optima에 빠질수도 있지요. 원래 EM은 local optima로 수렴하는 것이 증명되어 있지만 global optima로 수렴하는 것은 보장하지 못합니다. 최적화 기법의 바람직한 성질 중 하나는 목적함수를 단조증가하도록 보장하는 건데, 그렇다면 local maxima에 도달하면 당연히 거기에서 계속 머무르겠죠. 따라서, 제가 알기로는 deterministic optimization이 global optima로 수렴하는 것을 보장하기는 극히 어려운 것으로 알고 있구요. iteration을 아무리 많이 하더라도 소용이 없지요. 그래서 stochasitic relaxation 같은 것들이 엄청난 계산량에도 불구하고 이용되기도 하지요. 일반적으로 EM는 deterministic하게 구현되어 있어서 위 세가지 요인이 같다면 결과가 같아야 하지요. 하지만, 최근에 각 패러미터들을 차례차례 업데이트하는 sequential EM을 개발하였는데요, 만일 이 업데이트 순서를 랜덤하게 한다면 deterministic한 구현이 아니기 때문에 결과가 조금씩은 다를수 있습니다. 따라서 지금 사용하시는 프로그램의 내부가 어떻게 구현되어 있는가를 아셔야 확실한 답이 나오겠지요. estimation 이나 statistical signal processing 책들에서는 많이들 소개가 되어 있습니다. 쉽게 쓰여진 글로는 Todd Moon이 1996년엔가 IEEE Signal Processing Magazine 에 쓴 튜토리얼 수준의 글이 있습니다. EE의 신호처리 관점에서 쓰여졌지만 비교적 쉽게 쓰여진 글입니다. 항상 느끼는 거지만, 여기가 여전히 과학/공학 Q/A게시판 맞나보군요. 요샌 좀 덜한 편이긴 하지만요. ^^ |