Expectation Maximization Algorithm

Expectation Maximization Algorithm

EM 알고리즘은 불완전 정보 (missing data) 에 대한 Posterior 분포의 해석적 표현을 얻을 수 있으며, 완전 정보 (complete data) 의 최대우도 추정 (Maximum Likelihood Estimation) 의 해석적 표현이 가능할 때는 언제나 강력한 계산도구로 사용할 수 있으며, 추정치 (estimate) 가 안정적이다.

Wikipedia : Expectation-maximization algorithm : 통계 (Statistics) 에서 EM 알고리즘은 보이지 않는 잠재 변수 (latent variable) 에 의존하는 확률모델에서 모수 (parameter) 들의 최대우도 추정치 (maximum likelihood estimates of parameters) 를 찾고자하는 알고리즘이다. 즉 expectation (E) 단계에서는 잠재 변수의 기대치를 계산하고, maximization (M) 단계에서는 주어진 데이터와 기대치가 부여된 잠재 변수를 이용하여 모수들의 최대우도 추정치를 계산한다.

관측된 (observed) 변수를 y, 잠재 변수를 z 라고 하자. y 와 z 는 같이 완전정보 (complete data) 를 형성한다. 모수 θ를 가진 완전정보의 joint model 을 p 라고 가정한다. EM 알고리즘이 반복되면 최초 추정치 θ₀값이 증진되어 새로운 추정치 θ₁부터 θ_N 까지 만든다. θ_N 부터 θ_N+1 를 유도하는 각각의 재 추정 단계는 다음의 형태를 취한다 (여기서는 이산값 (discrete case) 의 경우이다 ; 연속값의 경우 (continuous case) 는 유사하다) :

$\theta_{n+1} = \arg\max_{\theta} \sum_z p(z \,|\, y, \theta_n) \times \log p(y, z \,|\, \theta)$

달리말하면, θ_N+1 는 complete data log-likelihood 의 기대치 (E) 를 최대화 시키는 값이다 (이전 모수값 하에서 잠재변수의 조건분포와 비교해서). 이 기대치는 보통 Q(θ) 라고 표기한다 :

$Q(\theta) = \sum_z p(z \,|\, y, \theta_n) \times \log p(y, z \,|\, \theta)$

expectation (E) 단계에 대해 말하자면 조금 잘못된 명칭 (misnomer) 이다. expectation (E) 단계에서 계산되는 것은 함수 Q 의 고정된 (fixed), 데이터 의존 (data-dependent) 모수들이다. 일단 Q 의 모수들이 알려지면, 그것은 완전히 결정되고 maximization (M) 단계에서 최대값으로 된다.

EM iteration 이 계속되면서 observed data likelihood function 이 감소되지 않는 것으로 보일 수 있다. 반복을 멈추게 하는 유일한 정지점 (stationary points) 는 observed data likelihood function 의 정지점이다. 실제로 이것은 EM 알고리즘이 observed data likelihood function 의 local maximum 에 수렴하는 것을 의미한다.

EM 은 완전정보 모델의 최대우도 추정이 쉬울 때 특히 유용하다. 만일 closed-form estimators 가 존재하면 M 단계는 뻔한 것이다 (trivial). 전형적인 예는, mixing 분포가 알려져 있다면 각 구성요소가 뻔하게 추정될 수 있는 finite mixture of Gaussians 의 최대우도 추정이다.

"Expectation-maximization" 은 특별한 알고리즘이 아니라 관련된 알고리즘의 종류에서 따온 이름이다 ; EM 은 특별한 알고리즘을 발명하기위해 사용되는 하나의 수단 (recipe) 또는 메타알고리즘 (meta-algorithm) 이다. Baum-Welch algorithm 은 hidden Markov models 에 응용된 EM 알고리즘의 한 예이다. 또다른 예는 mixture density model를 fitting 하기위한 EM 알고리즘이다.

EM algorithm 은 M 단계에서 maximum likelihood 보다는 maximum a posteriori (MAP) estimates를 찾을 수도 있다.

maximum likelihood estimates를 찾는 다른 방법들이 있는데, Gradient Descent, conjugate gradient 또는 Gauss-Newton method 의 변형이 그것이다.

참고 :

Arthur Dempster, Nan Laird, and Donald Rubin. "Maximum likelihood from incomplete data via the EM algorithm". Journal of the Royal Statistical Society, Series B, 39(1):1–38, 1977.

Radford Neal, Geoffrey Hinton. "A view of the EM algorithm that justifies incremental, sparse, and other variants". In Michael I. Jordan (editor), Learning in Graphical Models pp 355-368. Cambridge, MA: MIT Press, 1999.

EM Algorithm 과 통계적 추정 : 조세현, 충북개발연구원, 1995

A Density-based Clustering Method : 안성만. 백성욱, 한국통계학회, 2002

불완전한 사용현장 보증 데이터를 이용한 제품 신뢰도 추정 (Estimation of Product Reliability with Incomplete Field Warranty Data) : 임태진, 대한산업공학회, 2002

EM 알고리즘에 대한 간단한 개괄 : 축산기술 연구소

ExpectationMaximization : NoSmoke : Expectation maximization algorithm 은 'missing data' 가 있을 때의 maximum likelihood estimation 방법이다.