기대-최대화(EM) 알고리즘은 관측되지 않은 잠재 변수에 의존하는 통계 모델에서 매개변수의 국소 최대 우도 또는 최대 사후 확률(MAP) 추정치를 찾기 위해 통계학에서 사용되는 반복적 방법이다. 이 알고리즘은 현재 매개변수 추정치가 주어졌을 때 기대 로그 우도를 계산하는 기대(E) 단계와 그 기대 로그 우도를 최대화하도록 매개변수를 갱신하는 최대화(M) 단계를 번갈아 수행한다. 갱신된 매개변수는 다음 E 단계에 사용되며, 이 과정은 수렴할 때까지 반복된다. EM은 Machine learning과 같은 분야에서 혼합 모델 추정, 결측 데이터 처리, 은닉 마르코프 모델 훈련 등의 작업에 널리 적용된다.
EM이 다루는 핵심 문제는 우도 함수가 관측 데이터와 관측되지 않은 잠재 변수를 모두 포함할 때 발생한다. 모든 미지수에 대한 도함수를 취해 우도를 직접 최대화하면 일반적으로 해석적으로 풀 수 없는 상호 연결된 방정식이 생성된다. EM은 한쪽 변수 집합을 고정한 채 다른 쪽을 반복적으로 풀고, 둘 모두 고정점으로 수렴할 때까지 번갈아 수행함으로써 이 문제를 우회한다. 이 접근 방식은 각 반복에서 우도를 증가시키는 것이 보장되지만, 전역 최적점 대신 국소 최대값이나 안장점으로 수렴할 수 있다.
역사
EM 알고리즘은 1977년 Arthur Dempster, Nan Laird, Donald Rubin의 고전적인 논문에서 공식적으로 명명되고 설명되었다. 그러나 이 방법은 이전 연구자들에 의해 특수한 경우에 제안된 바 있다. Cedric Smith는 대립 유전자 빈도 추정을 위한 유전자 계수 방법을 도입했고, H.O. Hartley는 1958년에 관련 접근 방식을 제안했으며, Hartley와 Hocking이 1977년에 추가로 발전시켰다. Rolf Sundberg는 지수족에 대한 상세한 처리를 자신의 논문과 후속 논문에서 제공했으며, Per Martin-Löf 및 Anders Martin-Löf와의 협력을 바탕으로 했다. 1977년 Dempster-Laird-Rubin 논문은 이러한 아이디어를 일반화하고 수렴 분석을 개략적으로 제시하여 EM을 주요 통계 도구로 확립했다. 이후 C. F. Jeff Wu가 1983년에 원래 분석의 결함을 해결하고 지수족을 넘어 수렴 보장을 확장한 올바른 수렴 증명을 발표했다.
알고리즘 설명
관측 데이터 X, 잠재 데이터 Z, 알 수 없는 매개변수 θ가 주어졌을 때, 목표는 주변 우도 L(θ; X) = ∫ p(X, Z | θ) dZ를 최대화하는 것이다. EM 반복은 두 단계로 구성된다:
- E 단계: 현재 매개변수 추정치 θ^(t)와 X가 주어졌을 때 Z의 조건부 분포에 대해 로그 우도 함수의 기대값 Q(θ | θ^(t))를 계산한다.
- M 단계: Q(θ | θ^(t))를 최대화하는 매개변수 θ^(t+1)을 찾는다.
갱신된 매개변수는 다음 E 단계에 사용되며, 매개변수 또는 우도의 변화가 임계값 아래로 떨어질 때까지 프로세스가 반복된다. 이 절차는 우도를 단조롭게 증가시켜 정지점으로의 수렴을 보장한다.
응용 분야
EM은 각 관측 데이터 포인트가 여러 하위 구성 요소 중 하나에서 비롯된 것으로 가정되는 가우시안 혼합과 같은 혼합 모델의 매개변수를 추정하는 데 일반적으로 사용된다. 또한 일부 관측이 불완전한 결측 데이터 문제를 처리한다. Artificial intelligence에서 EM은 음성 인식 및 생물정보학에 사용되는 은닉 마르코프 모델의 훈련 알고리즘을 뒷받침한다. 또한 EM은 잠재 변수가 있는 다중 선형 회귀 문제를 해결할 수 있으며 요인 분석 및 군집화에 적용된다.
속성 및 한계
EM은 많은 모델에 대해 계산적으로 효율적이고 구현이 쉽지만 한계가 있다. 국소 최대값으로 수렴할 수 있으며 최종 해는 초기화에 의존한다. 혼합 모델에서 EM은 한 구성 요소의 분산이 0인 특이 해를 찾을 수 있으며, 이는 무의미한 최대값이다. 또한 알고리즘은 종종 알려지지 않은 잠재 구성 요소 또는 상태의 수를 지정해야 한다. 일반화 EM 알고리즘 및 확률적 EM과 같은 변형은 이러한 문제 중 일부를 해결하지만, 기본 방법은 여전히 통계 컴퓨팅의 기초 도구로 남아 있다.
관련 개념
EM 알고리즘은 Machine learning의 Stochastic Gradient Descent Variants 및 Adam (Optimizer)와 같은 기울기 기반 방법을 포함한 다른 반복 최적화 기술과 밀접하게 관련되어 있다. 또한 Deep learning의 변분 추론과 연결되며, 여기서 근사 사후 분포가 최적화된다. Generative AI에서는 EM 스타일 접근 방식이 잠재 변수 모델 훈련에 나타나며, 그 원리는 Reinforcement Learning from AI Feedback (RLAIF) 및 Curriculum Learning과 같은 더 고급 알고리즘을 이해하는 데 기초가 된다.
관련 개념
EM 알고리즘은 Machine learning의 Stochastic Gradient Descent Variants 및 Adam (Optimizer)와 같은 경사 기반 방법을 포함한 다른 반복 최적화 기법과 밀접한 관련이 있다. 또한 Deep learning의 변분 추론과 연결되며, 여기서 근사 사후 분포가 최적화된다. Generative AI에서 EM 스타일 접근 방식은 잠재 변수 모델 훈련에 나타나며, 그 원리는 Reinforcement Learning from AI Feedback (RLAIF) 및 Curriculum Learning과 같은 더 고급 알고리즘을 이해하는 기초가 된다.