기댓값 최대화 알고리즘

통계 수치해석 소프트웨어 마지막 수정: 2026-07-29 04:31:19

1. 개요[편집]

모르는 걸 아는 척 채워 넣고(E), 그 상태에서 최적화하고(M), 다시 채워 넣는다. 그런데 이게 수렴한다.

기댓값 최대화 알고리즘(Expectation–Maximization, EM)은 관측되지 않는 잠재변수 $Z$ 가 섞여 있는 확률모형에서 최대가능도 추정치를 반복적으로 찾는 알고리즘이다. 뎀스터·레어드·루빈(1977)이 흩어져 있던 여러 특수 사례를 하나의 틀로 묶으면서 이름이 붙었다.¹

문제 설정은 이렇다. 관측 데이터 $X$ , 잠재변수 $Z$ , 파라미터 $\theta$ 에 대해 우리가 최대화하고 싶은 것은 불완전 데이터 로그가능도

\ell(\theta) = \ln p(X\mid\theta) = \ln \sum_{Z} p(X, Z \mid \theta)

인데, 로그 안에 합(또는 적분)이 들어가는 순간 미분식이 닫힌 형태로 풀리지 않는다. 반면 완전 데이터 로그가능도 $\ln p(X,Z\mid\theta)$ 는 지수족이라면 대개 손으로 풀린다. EM은 이 간극을 “ $Z$ 의 사후분포로 기댓값을 취해 로그 밖으로 꺼내는” 방식으로 메운다.

2. 두 단계[편집]

$t$ 번째 반복의 추정치를 $\theta^{(t)}$ 라 하자.

E-단계(기댓값). 현재 파라미터로 잠재변수의 사후분포를 구하고, 그것으로 완전 데이터 로그가능도의 기댓값을 만든다.

Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}\big[\ln p(X, Z \mid \theta)\big]

여기서 기댓값을 취하는 분포의 파라미터는 $\theta^{(t)}$ 로 고정이고, 최적화 변수는 첫 번째 인자인 $\theta$ 다. 이 구분을 놓치면 EM은 그냥 이해되지 않는 알고리즘이 된다.

M-단계(최대화). 그 $Q$ 를 최대화한다.

\theta^{(t+1)} = \arg\max_{\theta}\, Q(\theta \mid \theta^{(t)})

실제 계산에서 E-단계가 “사후분포 전체를 구하는 것”인 경우는 드물다. 완전 데이터 로그가능도가 충분통계량 $T(X,Z)$ 에 선형이면 $Q$ 는 $\mathbb{E}[T(X,Z)\mid X,\theta^{(t)}]$ 에만 의존하므로, 필요한 것은 충분통계량의 조건부 기댓값 몇 개뿐이다. 혼합모형이면 성분별 사후확률, 은닉 마르코프 모형이면 상태 점유확률과 전이 횟수의 기댓값이 그것이다. 이 사실을 알면 구현이 갑자기 간단해진다.

지수족 모형에서는 이 최대화가 닫힌 형태로 떨어진다. 사실상 “충분통계량 자리에 그 기댓값을 대입한 완전 데이터 MLE”와 같기 때문이다. 가우시안 혼합 모형의 평균·공분산 갱신식이 표본평균·표본공분산에 책임도 가중치만 붙은 꼴인 이유가 바로 이것이다.

3. 하한 관점 — 왜 절대 나빠지지 않는가[편집]

EM의 진가는 ELBO(증거 하한) 로 보면 드러난다. 임의의 분포 $q(Z)$ 에 대해 항등식

\ln p(X\mid\theta) = \mathcal{L}(q,\theta) + \mathrm{KL}\big(q(Z)\,\|\,p(Z\mid X,\theta)\big), \qquad \mathcal{L}(q,\theta) = \sum_Z q(Z)\ln\frac{p(X,Z\mid\theta)}{q(Z)}

가 성립한다. KL 발산이 항상 0 이상이므로 $\ln p(X\mid\theta) \ge \mathcal{L}(q,\theta)$ , 즉 $\mathcal{L}$ 은 로그가능도의 하한이다(젠센 부등식으로도 같은 결론을 얻는다 — 젠센 부등식 참고).

이 틀에서 EM의 두 단계는 같은 하한을 두 방향으로 밀어 올리는 좌표상승법이다.

E-단계는 $\theta^{(t)}$ 를 고정한 채 $q$ 에 대해 $\mathcal{L}$ 을 최대화한다. 최적해는 $q = p(Z\mid X,\theta^{(t)})$ 이고, 이때 KL이 정확히 0이 되므로 하한이 현재 점에서 로그가능도에 접한다.
M-단계는 그 $q$ 를 고정한 채 $\theta$ 에 대해 $\mathcal{L}$ 을 최대화한다. $\mathcal{L}(q,\theta) = Q(\theta\mid\theta^{(t)}) + \mathrm{const}$ 이므로 $Q$ 최대화와 동치다.

여기서 단조성이 곧바로 나온다.

\ell(\theta^{(t+1)}) \;\ge\; \mathcal{L}(q^{(t)}, \theta^{(t+1)}) \;\ge\; \mathcal{L}(q^{(t)}, \theta^{(t)}) \;=\; \ell(\theta^{(t)})

첫 부등호는 하한의 정의, 두 번째는 M-단계가 최대화이기 때문, 마지막 등호는 E-단계에서 하한이 접했기 때문이다. 즉 로그가능도는 매 반복에서 절대 감소하지 않는다. 학습률도, 라인서치도, 스텝 크기 조정도 없이 이 성질이 보장된다는 것이 EM이 40년 넘게 살아남은 이유다.²

2차원 가우시안 혼합에 EM을 실제로 돌린다. E-단계의 책임도는 log-sum-exp로 안정화해 계산하고, M-단계는 닫힌 형태 갱신식을 그대로 쓴다. 점 색은 책임도 γ의 가중 혼합이라 성분 경계에서 색이 섞이는데, 이게 소프트 배정이다. 타원은 2×2 공분산의 고유분해로 그린 1σ·2σ 등고선이고, 아래 곡선은 반복 대비 로그가능도다. 위 단조성이 실제로 지켜지는지 감소 횟수 카운터로 함께 띄운다 — 정상 구현이면 0에서 움직이지 않는다. 참 성분은 3개이므로 K 슬라이더를 2나 5로 옮기면 과소·과대적합이 보이고, ↺는 데이터를 그대로 둔 채 초기화만 바꿔 지역 최적해가 갈리는 것을 보여준다.

주의할 것은 이것이 전역 최적해 수렴 보장이 아니라는 점이다. 단조 증가 + 유계이면 가능도 값 자체는 수렴하지만, 도달점은 지역 최댓값이거나 안장점일 수 있다.

4. 수렴 속도와 함정[편집]

EM은 선형 수렴한다. 오차가 반복마다 상수 비율로 줄되, 그 비율이 문제 의존적이다. 뎀스터 등의 고전적 결과에 따르면 수렴률은 이른바 결측 정보 비율(fraction of missing information), 즉 결측 정보 행렬과 완전 데이터 정보 행렬의 비의 최대 고윳값으로 주어진다.

\theta^{(t+1)} - \theta^\ast \approx J\,(\theta^{(t)} - \theta^\ast), \qquad J = I_{\text{missing}} I_{\text{complete}}^{-1}

직관은 명쾌하다. 잠재변수가 관측에서 거의 확정되면( $Z$ 에 대한 사후가 뾰족하면) 결측 정보가 적고 EM은 몇 번 만에 끝난다. 반대로 혼합 성분들이 심하게 겹쳐 있으면 결측 정보가 커서 수백~수천 반복을 기어간다. 뉴턴류 방법이 근처에서 이차 수렴하는 것과 대비되는 지점이며, 그래서 실무에서는 EM으로 안전하게 접근한 뒤 막판만 뉴턴-랩슨법이나 준-뉴턴법으로 마무리하는 하이브리드를 쓰기도 한다.

그 밖의 실전 주의사항:

지역 최적해는 기본값이다. 서로 다른 무작위 초기값으로 여러 번 돌린 뒤 최종 가능도가 가장 큰 해를 채택하는 다중 시작(multi-start)이 사실상 표준 절차다. 지역 최적해 문서의 논의가 그대로 적용된다.
정지 판정을 가능도로 하지 마라. 로그가능도 변화량이 작아도 파라미터는 아직 크게 움직이는 중일 수 있다. 선형 수렴 구간에서는 가능도 곡선이 먼저 평평해지기 때문이다.³ 파라미터 변화량도 함께 본다.
표준오차가 공짜로 안 나온다. 뉴턴법과 달리 헤세 행렬을 계산하지 않으므로, 관측 정보 행렬은 SEM 알고리즘이나 부트스트랩으로 따로 얻어야 한다.
가능도가 위로 유계가 아닌 모형(대표적으로 비제약 공분산 혼합모형)에서는 단조 증가가 오히려 특이점으로 기어 들어가는 경로가 된다. 정칙화가 필요하다.

5. 최적화 관점에서의 위치[편집]

EM은 사실 MM 알고리즘(Minorize–Maximize)의 대표적 사례다. 최대화하기 어려운 목적함수 $\ell(\theta)$ 를, 현재 점에서 접하면서 그보다 항상 작은 대리함수(surrogate)로 갈아 끼우고 그 대리함수를 최대화하는 절차 — 그게 MM이고, EM에서 그 대리함수가 바로 ELBO $\mathcal{L}(q^{(t)},\theta)$ 다. 같은 발상은 담금질 모사와 무관하게 볼록 최적화·통계 전반에서 반복적 재가중 최소제곱(IRLS) 같은 형태로 계속 등장한다.

동시에 EM은 $(q,\theta)$ 두 블록에 대한 좌표상승법이기도 하다. 이 시각의 실용적 함의는 두 가지다. 첫째, 좌표상승이 그렇듯 블록 하나를 완전히 최적화할 필요는 없다 — 여기서 GEM이 나온다. 둘째, 좌표축에 정렬된 방향으로만 움직이므로 파라미터가 강하게 상관되어 있으면 지그재그로 기어간다. 결측 정보 비율이 클 때 수렴이 느려지는 현상의 기하학적 해석이 정확히 이것이다.

6. 변형과 확장[편집]

변형	바꾼 것
GEM	M-단계에서 최대화 대신 $Q$ 를 증가만 시킴. 단조성은 그대로 유지된다
ECM / ECME	M-단계를 여러 조건부 최대화로 쪼개 각각을 닫힌 형태로 만듦
MCEM	E-단계 기댓값을 몬테카를로 방법으로 근사
확률적 EM	미니배치로 충분통계량을 온라인 갱신. 대규모 데이터용
변분 EM	사후분포가 다루기 어려울 때 $q$ 를 특정 족으로 제한

특히 변분 EM은 E-단계에서 KL을 0으로 만들 수 없는 경우다. $q$ 를 인수분해 가능한 족으로 제한하면 하한이 로그가능도에 접하지 못하고 틈이 남는다. 그래도 $\mathcal{L}$ 자체는 여전히 단조 증가하므로 알고리즘은 정상 작동하며, 이것이 변분 추론과 현대 변분 오토인코더 계열의 출발점이다. 반대로 정확한 E-단계가 가능한 경우가 오히려 특수한 축복인 셈.

7. 응용[편집]

가우시안 혼합 모형 — EM의 대표 사례. 잠재변수는 “이 표본이 어느 성분에서 왔는가”이고, E-단계의 사후확률이 곧 책임도다.
은닉 마르코프 모형의 바움-웰치 알고리즘 — 잠재변수가 상태 열이고, E-단계의 사후 주변확률을 전방-후방 알고리즘이 동적계획법으로 계산한다. EM의 시계열판.
결측 데이터 처리 — 원래 EM이 태어난 문제. 결측값 자체를 잠재변수로 두면 무응답이 섞인 자료의 MLE가 그대로 굴러간다.
인자분석·확률적 주성분 분석 — 잠재 인자를 $Z$ 로 두면 EM으로 적합할 수 있고, 결측이 있는 자료에도 확장된다.
영상 재구성·역문제 — 양전자 방출 단층촬영(PET)의 고전적 재구성 알고리즘이 EM 기반이다. 역문제 계열과도 접점이 있다.

8. 관련 문서[편집]

1977년 논문 이전에도 유전학·결측 데이터·혼합모형 각 분야에 사실상 EM인 절차들이 따로 굴러다니고 있었다. 그것들이 전부 같은 알고리즘이었다는 걸 보여준 게 그 논문의 진짜 기여다. 통합 이론의 힘. ↩
하이퍼파라미터가 없다시피 하다는 건 실무에서 엄청난 미덕이다. 경사하강법 계열이 학습률 하나 때문에 밤을 새우는 동안 EM은 초기값만 주면 알아서 올라간다. 물론 어디로 올라갈지는 초기값이 정한다. ↩
그래서 “10번 반복 만에 수렴했습니다”라는 보고를 받으면 임계값을 먼저 물어봐야 한다. 상대 변화 $10^{-4}$ 로 끊으면 어지간한 문제는 다 10번 만에 “수렴”한다. 진짜인지 아닌지는 여러 초기값의 최종 가능도가 일치하는지로 판정하는 게 빠르다. ↩