[Optimization] EM(Expectation-Maximization algorithm) (기댓값 최대화 알고리즘)

ti_esti·2025년 3월 30일

algorithm bayesian optimization

Differential Equation/Optimization

목록 보기

3/4

1. 개요

Expectation-Maximization (기댓값 최대화) 알고리즘은 관측되지 않은 변수, 즉 잠재 변수(latent variable)를 포함한 확률 모델의 파라미터를 최적화하기 위한 반복 알고리즘이다.

직접적으로는 최적화하기 어려운 불완전 로그 우도(incomplete log-likelihood) 대신, 관측되지 않은 데이터의 분포에 대한 기댓값을 취한 로그 우도를 반복적으로 최대화한다.

2. 역사와 배경

EM 알고리즘은 1977년 Dempster, Laird, Rubin의 논문에서 일반적인 형태로 정립되었다. 하지만 그 이전에도 유사한 알고리즘은 통계학과 정보이론 분야에서 간헐적으로 사용되었다. 가장 널리 알려진 응용 사례는 가우시안 혼합 모델(GMM)과 히든 마르코프 모델(HMM)에서의 파라미터 추정이다.

3. 문제 설정

관측된 데이터: $X = \{x_1, \dots, x_n\}$
숨겨진(잠재) 변수: $Z = \{z_1, \dots, z_n\}$
파라미터: $\theta$

관측 불가능한 전체 데이터는 $Y = (X, Z)$ 이고, 우리가 최적화하고 싶은 것은 다음과 같은 로그 가능도이다.

\log p(X \mid \theta) = \log \sum_Z p(X, Z \mid \theta)

하지만 $\log$ 안에 합(sum)이 있어서 직접 최적화하기 어렵다.

4. 핵심 아이디어

직접적으로 최적화할 수 없는 $\log p(X \mid \theta)$ 대신, 현재 파라미터 $\theta^{(t)}$ 하에서 숨겨진 변수 $Z$ 의 분포를 고려해, 기댓값 형태의 우도 함수를 최적화한다.

이 과정은 다음 두 단계로 이루어진다.

E-step: 숨겨진 변수의 분포에 대한 기대값 계산
M-step: 기대값을 고정한 상태에서 파라미터 최적화

5. 알고리즘 절차

Step 0: 초기화

파라미터 $\theta^{(0)}$ 를 초기화한다.

Step 1: E-step (Expectation step)

현재 파라미터 $\theta^{(t)}$ 에서 완전 로그우도의 기댓값을 계산한다.

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

이 기대값은 현재 조건부 분포 $p(Z \mid X, \theta^{(t)})$ 를 기반으로 계산된다.

Step 2: M-step (Maximization step)

E-step에서 계산한 기대값 $Q$ 를 파라미터 $\theta$ 에 대해 최대화한다.

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

Step 3: 수렴 여부 확인

다음 중 하나의 조건이 충족될 때까지 1~2단계를 반복한다:

$\lvert \theta^{(t+1)} - \theta^{(t)} \rvert < \varepsilon$
반복 횟수가 최대치를 초과하거나, 로그 가능도의 증가량이 매우 작을 때.

6. 수학적 유도 (Jensen 부등식 기반)

불완전 로그우도 $\log p(X \mid \theta)$ 는 다음과 같이 변형 가능하다:

\log p(X \mid \theta) = \log \sum_Z q(Z) \cdot \frac{p(X, Z \mid \theta)}{q(Z)} \geq \sum_Z q(Z) \log \frac{p(X, Z \mid \theta)}{q(Z)}

이 하한을 최대화하는 것이 EM 알고리즘의 핵심이다. 이 식의 등호는 $q(Z) = p(Z \mid X, \theta)$ 일 때 성립한다.

7. 예제: 가우시안 혼합 모델 (GMM)

각 데이터 $x_i$ 는 $K$ 개의 가우시안 분포 중 하나에서 생성됨
잠재 변수 $z_i$ 는 $x_i$ 가 어떤 가우시안에서 왔는지를 나타냄

E-step: 책임도 계산

\gamma_{ik} = p(z_i = k \mid x_i, \theta^{(t)}) = \frac{\pi_k^{(t)} \cdot \mathcal{N}(x_i \mid \mu_k^{(t)}, \Sigma_k^{(t)})}{\sum_{j=1}^K \pi_j^{(t)} \cdot \mathcal{N}(x_i \mid \mu_j^{(t)}, \Sigma_j^{(t)})}

M-step: 파라미터 갱신

N_k = \sum_{i=1}^n \gamma_{ik}

\mu_k^{(t+1)} = \frac{1}{N_k} \sum_{i=1}^n \gamma_{ik} x_i

\Sigma_k^{(t+1)} = \frac{1}{N_k} \sum_{i=1}^n \gamma_{ik} (x_i - \mu_k^{(t+1)})(x_i - \mu_k^{(t+1)})^T

\pi_k^{(t+1)} = \frac{N_k}{n}

8. 수렴성 및 성질

EM 알고리즘은 반복할수록 $\log p(X \mid \theta)$ 를 증가시킨다.
일반적으로 국소 최댓값(local maximum)으로 수렴한다.
전역 최적 해를 보장하지는 않는다.
수렴 속도가 느린 경우도 많다.

9. 요약 테이블

단계	내용
E-step	조건부 기대값 $Q(\theta \mid \theta^{(t)})$ 계산
M-step	기대값을 최대화하여 $\theta^{(t+1)}$ 갱신
반복 조건	로그 가능도의 증가 또는 파라미터 차이 기준으로 수렴 여부 결정

10. MLE와의 관계

MLE와 다른 것이 아니다. 이는 최적화의 목표이고, MLE를 수행하기 위한 서로 다른 전략이 존재한다고 볼 수 있따. EM은 "잠재 변수 포함된 경우의 MLE"라고 볼 수 있따.

ti_esti

KAIST Computational Neuroscience

이전 포스트

[Optimization] Lagrange Multiplier Method (라그랑주 승수법)

다음 포스트