| [ KAIST ] in KIDS 글 쓴 이(By): comofcom (OSS) 날 짜 (Date): 2002년 9월 28일 토요일 오후 03시 49분 51초 제 목(Title): Re: EM algorithm 성질 이미 질문하신 분께서는 답을 얻으신것 같지만, 사족을 잠깐... ^^ global optimization 은 어떤 알고리즘도 보장못한다는 지적이 있네요. 동의. 전에 지도교수에게 이것에 대해 얘기 한 적이 있는데 그가 이것을 재밌게 표현하더군요. Local optimization is human, but global optimization is divine. ^^ sequential EM의 응용 예로 영상의 픽셀값들이 추정해야 하는 unknown인 경우를 생각해 보죠. 이 경우 expectation step의 결과로 도출되는 함수 (보통 "Q-function") 역시 unknown의 갯수가 너무 많게 되지요. 그래서, 계산량을 줄이기 위해서, Q-function을 픽셀 하나에 대해서만 만들어서 1차원 최적화 문제로 만들어 푸는 과정을 각각의 픽셀 모두에 대해서 순서대로 적용합니다. EM의 Gauss-Seidel 버젼이라고 할 수 있을라나요? ^^ 이 알고리즘도 (심지어는 각 픽셀이 0 이상이어야 한다는 등의 제약조건이 주어지더라도) 어떤 적절한 조건하에서는 원래의 목적함수가 단조증가하여 local maxima로 수렴함이 증명되어 있습니다. 만일 픽셀을 업데이트하는 순서가 random하게 결정된다면 EM의 결과는 약간씩 달라질 수 있구요. 일반적인 Gauss-Seidel에서는 수렴이 약간 개선된다고 하던데 sequential EM의 경우는 잘 모르겠습니다. Gibbs sampling이나 MCMC와는 직접적 관련은 없습니다. EM이 속도가 늦다는게 흠이긴 한데, 어찌보면 최적화의 관점에서는 어느정도 예측할 수 있는 결과지요. EM은 계산이 어려운 최적화 문제를 약간 더 쉬운 형태의 함수(Q-function)의 최적화로 대체해서 푸는 것이라고 해석할수 있는데요, 대부분의 다른 유사한 최적화 방법에서처럼, 이 대체함수의 증가가 원래 함수의 증가를 보장하기 위해서는 대체함수에 의한 update가 좀 더 conservative 할 수 밖에 없지요. EM을 최적화 관점에서 생각해 본다면 EM의 원리, 장단점이 좀 더 잘 파악되지 않을까 싶습니다. 저도 EM이 전공은 아니어서 책한권 읽어본적 없고 한번도 실제로 구현해 본적은 없습니다만.... |