가우시안 혼합모형 (Gaussian Mixture Model, GMM)과 EM 알고리즘

가우시안 혼합 모형 (Gaussian Mixture Model, GMM)과 EM 알고리즘

1. GMM 시작하기: 데이터에 숨겨진 그룹 찾기

어떤 데이터가 주어졌을 때, 이 데이터가 하나의 정규분포(가우시안분포)만으로는 잘 설명되지 않는 경우가 많습니다. 예를 들어, 남학생과 여학생의 키 데이터를 합쳐놓으면, 평균이 다른 두 개의 정규분포가 섞인 듯한 봉우리가 두 개인 분포가 나타날 것입니다.
가우시안 혼합 모형 (GMM)은 이처럼 전체 데이터가 여러 개의 가우시안 분포가 혼합되어 생성되었다고 가정하는 강력한 확률 모델입니다. 각 데이터 포인트가 어떤 숨겨진(latent) 그룹(가우시안)에서 왔는지를 확률적으로 추정하여 데이터를 부드럽게 클러스터링(soft clustering)할 수 있습니다.

GMM의 구성 요소

• 관측 데이터 (Observed Data): $X = \{x_1, \dots, x_n\}$, 우리 눈에 보이는 데이터 포인트들입니다. ($x_i \in \mathbb{R}^d$)
• 잠재 변수 (Latent Variable): $Z = \{z_1, \dots, z_n\}$, 각 데이터 $x_i$가 $K$개의 가우시안 중 어느 것에서 왔는지를 나타내는 숨겨진 정보입니다. $z_i=k$는 $x_i$가 $k$번째 가우시안에서 왔음을 의미합니다.
• 모델 파라미터 $\theta$: 우리가 찾아야 할 GMM의 명세서입니다.
  • 혼합 가중치 (Mixture Weight) $\pi_k$: 전체 데이터 중 $k$번째 가우시안이 차지하는 비율(사전 확률). $\sum_{k=1}^K \pi_k = 1$ 입니다.
  • 평균 (Mean) $\mu_k$: $k$번째 가우시안 분포의 중심 위치.
  • 공분산 (Covariance) $\Sigma_k$: $k$번째 가우시안 분포의 모양과 퍼짐 정도.

이 파라미터 $\theta = \{\pi_k, \mu_k, \Sigma_k\}_{k=1}^K$가 주어졌을 때, 하나의 데이터 $x$가 나타날 확률(가능도)은 다음과 같이 각 가우시안의 확률밀도함수에 가중치를 두어 더한 값이 됩니다.
$$ p(x \mid \theta) = \sum_{k=1}^K \pi_k \mathcal{N}(x \mid \mu_k, \Sigma_k) $$

---

2. 왜 직접 최적화가 어려운가?: 로그 안의 덧셈 문제

머신러닝의 기본 원리는 모델이 데이터를 가장 잘 설명하도록 파라미터 $\theta$를 찾는 것입니다. 이는 보통 전체 데이터에 대한 로그 가능도(log-likelihood)를 최대화하는 문제로 귀결됩니다. GMM의 경우, 관측 데이터에 대한 로그 가능도는 다음과 같습니다.
$$ \mathcal{L}(\theta) = \log p(X \mid \theta) = \sum_{i=1}^n \log p(x_i \mid \theta) = \sum_{i=1}^n \log \left( \sum_{k=1}^K \pi_k \mathcal{N}(x_i \mid \mu_k, \Sigma_k) \right) $$
이 식을 $\mu_k$나 $\Sigma_k$에 대해 미분해서 0으로 만드는 파라미터를 찾으려고 하면, 로그 함수 안에 덧셈($\sum$)이 있는 구조 때문에 수식이 매우 복잡해지고 깔끔한 해(closed-form solution)가 나오지 않습니다. 이것이 GMM을 직접 최적화하기 어려운 근본적인 이유입니다.

---

3. EM 알고리즘: '상상'으로 문제를 푸는 두 단계 전략

이 어려운 문제를 풀기 위해 기대값-최대화 (Expectation-Maximization, EM) 알고리즘이 등장합니다. EM 알고리즘은 잠재 변수 $z_i$를 우리가 '알고 있다'고 가정하면 문제가 매우 쉬워진다는 사실에 착안합니다.
만약 $z_i$를 안다면, 즉 각 데이터가 어느 그룹에 속하는지 안다면, 로그 가능도는 다음과 같이 간단한 '덧셈의 로그' 형태로 바뀝니다. 이를 완전 데이터 로그 가능도(complete-data log-likelihood)라고 합니다.
$$ \log p(X, Z \mid \theta) = \sum_{i=1}^n \sum_{k=1}^K z_{ik} \left( \log \pi_k + \log \mathcal{N}(x_i \mid \mu_k, \Sigma_k) \right) $$
($z_{ik}$는 $x_i$가 $k$번째 그룹에 속하면 1, 아니면 0인 원-핫 인코딩 벡터입니다.)
하지만 우리는 $Z$를 모르죠. 그래서 EM 알고리즘은 다음과 같은 두 단계를 반복합니다.

1. Expectation (E) 단계: 현재 파라미터 $\theta$를 기반으로, 각 데이터 $x_i$가 각 그룹 $k$에 속할 '책임(responsibility)' 또는 확률을 '추측'합니다.
2. Maximization (M) 단계: E-단계에서 추측한 '책임'을 가중치 삼아, 완전 데이터 로그 가능도의 기댓값을 최대화하는 새로운 파라미터 $\theta$를 '계산'합니다.

이 과정을 반복하면 신기하게도 관측 데이터 로그 가능도가 항상 증가하거나 유지됨이 보장됩니다.

3-1. E-Step: 책임감 분배하기

E-단계에서는 현재 파라미터 $\theta^{\text{old}}$가 주어졌을 때, 데이터 $x_i$가 $k$번째 가우시안에서 생성되었을 사후 확률을 계산합니다. 이를 '책임(responsibility)' $\gamma_{ik}$라고 부릅니다.
$$ \gamma_{ik} := p(z_{ik}=1 \mid x_i, \theta^{\text{old}}) = \frac{p(x_i \mid z_{ik}=1, \theta^{\text{old}}) p(z_{ik}=1 \mid \theta^{\text{old}})}{p(x_i \mid \theta^{\text{old}})} $$ $$ = \frac{\pi_k^{\text{old}} \mathcal{N}(x_i \mid \mu_k^{\text{old}}, \Sigma_k^{\text{old}})}{\sum_{j=1}^K \pi_j^{\text{old}} \mathcal{N}(x_i \mid \mu_j^{\text{old}}, \Sigma_j^{\text{old}})} $$
$\gamma_{ik}$는 $x_i$라는 결과에 대해 $k$번째 가우시안이 얼마나 '책임'이 있는지를 나타내는 0과 1 사이의 값입니다.

3-2. M-Step: 책임에 기반하여 파라미터 업데이트

M-단계에서는 E-단계에서 계산한 책임 $\gamma_{ik}$를 사용하여, 완전 데이터 로그 가능도의 기댓값 $Q(\theta, \theta^{\text{old}}) = \mathbb{E}_{Z \sim p(Z|X,\theta^{\text{old}})}[\log p(X, Z \mid \theta)]$를 최대화하는 새로운 파라미터 $\theta^{\text{new}}$를 찾습니다.
다행히도 이는 각 데이터 포인트를 $\gamma_{ik}$만큼의 가중치를 주어 해당 그룹의 통계량을 다시 계산하는 직관적인 형태로 나타납니다.
먼저, 각 클러스터에 할당된 데이터의 유효 개수 $N_k$를 계산합니다. $$ N_k = \sum_{i=1}^n \gamma_{ik} $$
업데이트 규칙:

• 혼합 가중치 $\pi_k$: 전체 데이터 중 $k$번째 클러스터가 차지하는 비율. $$ \pi_k^{\text{new}} = \frac{N_k}{n} $$
• 평균 $\mu_k$: $k$번째 클러스터에 속한 데이터들의 가중 평균. $$ \mu_k^{\text{new}} = \frac{1}{N_k} \sum_{i=1}^n \gamma_{ik} x_i $$
• 공분산 $\Sigma_k$: $k$번째 클러스터에 속한 데이터들의 가중 공분산. $$ \Sigma_k^{\text{new}} = \frac{1}{N_k} \sum_{i=1}^n \gamma_{ik} (x_i - \mu_k^{\text{new}})(x_i - \mu_k^{\text{new}})^\top $$

---

4. 왜 EM은 항상 통하는가?: ELBO와 단조 증가 원리

EM 알고리즘이 반복될수록 왜 로그 가능도 $\mathcal{L}(\theta)$가 항상 좋아지는지(감소하지 않는지)를 이해하는 것은 매우 중요합니다. 이는 증거 하한(Evidence Lower Bound, ELBO)이라는 개념과 젠슨 부등식(Jensen's Inequality)으로 증명할 수 있습니다.

KL-발산으로 ELBO 이해하기

임의의 근사 분포 $q(Z)$에 대해, 관측 데이터 로그 가능도는 다음과 같이 분해할 수 있습니다.
$$ \log p(X \mid \theta) = \mathcal{F}(q, \theta) + \mathrm{KL}(q(Z) \,\|\, p(Z \mid X, \theta)) $$
여기서 $\mathcal{F}(q, \theta) = \mathbb{E}_{q}[\log p(X, Z \mid \theta)] - \mathbb{E}_{q}[\log q(Z)]$가 ELBO입니다. KL-발산은 항상 0 이상이므로($\mathrm{KL}(\cdot\|\cdot) \ge 0$), $\log p(X \mid \theta) \ge \mathcal{F}(q, \theta)$가 항상 성립합니다. 즉, ELBO는 로그 가능도의 '하한선(lower bound)'입니다.

EM 알고리즘과 ELBO의 춤

EM 알고리즘은 이 ELBO를 이용하여 로그 가능도를 영리하게 끌어올리는 과정으로 볼 수 있습니다.

1. E-Step: 하한선을 로그 가능도에 붙이기
   $t$번째 반복에서 얻은 파라미터를 $\theta^{(t)}$라고 합시다. E-단계에서는 근사 분포 $q(Z)$를 실제 사후분포 $p(Z \mid X, \theta^{(t)})$와 똑같이 설정합니다. $$ q^{(t+1)}(Z) = p(Z \mid X, \theta^{(t)}) $$ 이렇게 하면 두 분포가 같아지므로 $\mathrm{KL}(q^{(t+1)} \,\|\, p(Z \mid X, \theta^{(t)})) = 0$이 됩니다. 따라서, $$ \log p(X \mid \theta^{(t)}) = \mathcal{F}(q^{(t+1)}, \theta^{(t)}) $$ 이 단계에서 ELBO는 현재 로그 가능도 값에 정확히 '접하게' 됩니다.
2. M-Step: 하한선 자체를 끌어올리기
   M-단계에서는 $q^{(t+1)}$는 고정한 채로, ELBO $\mathcal{F}(q^{(t+1)}, \theta)$를 최대화하는 새로운 파라미터 $\theta^{(t+1)}$를 찾습니다. $$ \theta^{(t+1)} = \arg\max_{\theta} \mathcal{F}(q^{(t+1)}, \theta) $$ 따라서 정의에 의해 $\mathcal{F}(q^{(t+1)}, \theta^{(t+1)}) \ge \mathcal{F}(q^{(t+1)}, \theta^{(t)})$ 입니다.

증명의 완성: 이제 모든 조각을 맞춰봅시다.
$$ \begin{aligned} \log p(X \mid \theta^{(t+1)}) & = \mathcal{F}(q^{(t+1)}, \theta^{(t+1)}) + \mathrm{KL}(q^{(t+1)} \,\|\, p(Z \mid X, \theta^{(t+1)})) \\ & \ge \mathcal{F}(q^{(t+1)}, \theta^{(t+1)}) & (\text{KL} \ge 0 \text{ 이므로}) \\ & \ge \mathcal{F}(q^{(t+1)}, \theta^{(t)}) & (\text{M-step의 정의에 의해}) \\ & = \log p(X \mid \theta^{(t)}) & (\text{E-step에서 KL=0 이었으므로}) \end{aligned} $$
결론적으로 $\log p(X \mid \theta^{(t+1)}) \ge \log p(X \mid \theta^{(t)})$가 되어, EM 알고리즘은 매 반복마다 로그 가능도를 절대 감소시키지 않음을 수학적으로 보장합니다.