EM 알고리즘과 가우스 혼합(The EM algorithm and Gaussian mixtures)

측정값 200개의 히스토그램⁠(histogram)⁠에 봉우리가 둘 있습니다. 두 무리가 섞였다고 짐작되지만, 어느 값이 어느 무리에서 왔는지는 적혀 있지 않습니다. 무리마다 정규분포를 따른다고 하면, 값 하나가 나올 확률밀도⁠(probability density)⁠는 두 정규분포를 비율 $\pi_1, \pi_2$(합이 1)로 섞은 것입니다.

$$p(x) = \pi_1\,\mathcal N(x \mid \mu_1, \sigma_1^2) + \pi_2\,\mathcal N(x \mid \mu_2, \sigma_2^2)$$

모수 여섯 개(비율은 합이 1이니 사실 다섯 개)를 최대가능도로 정하고 싶은데, 로그 가능도⁠(log-likelihood)⁠ $\sum_i \log p(x_i)$는 로그 안에 합이 있어서 미분⁠(differentiation)⁠해 0으로 놓아도 공식으로 풀리지 않습니다. 그런데 두 가지 반쪽 문제는 쉽습니다. 이름표를 안다면 무리마다 평균⁠(mean)⁠, 표준편차⁠(standard deviation)⁠, 비율을 구하면 그것이 최대가능도의 답입니다. 모수를 안다면 베이즈 정리⁠(Bayes' theorem)⁠로 점마다 어느 무리에서 왔을 확률을 계산할 수 있습니다. EM 알고리즘⁠(algorithm)⁠은 이 둘을 번갈아 합니다.

E 단계. 지금의 모수로 점 i가 무리 k에서 왔을 사후 확률⁠(posterior probability)⁠, 곧 책임도⁠(responsibility)⁠를 구합니다.

$$r_{ik} = \frac{\pi_k\,\mathcal N(x_i \mid \mu_k, \sigma_k^2)}{\sum_j \pi_j\,\mathcal N(x_i \mid \mu_j, \sigma_j^2)}$$

M 단계. 책임도를 가중치로 삼아 평균, 분산⁠(variance)⁠, 비율을 다시 구합니다. 이름표를 알 때의 공식에서 '센다'를 '책임도만큼 센다'로 바꾼 것입니다.

$$\pi_k = \frac1n\sum_i r_{ik}, \qquad \mu_k = \frac{\sum_i r_{ik}\,x_i}{\sum_i r_{ik}}, \qquad \sigma_k^2 = \frac{\sum_i r_{ik}\,(x_i - \mu_k)^2}{\sum_i r_{ik}}$$

아래에서 한 단계씩 넘겨 보세요. 축 위의 두 점은 두 성분의 평균이고, 끌어서 출발점을 바꿀 수 있습니다. 히스토그램 아래 줄의 점들은 책임도에 따라 파랑에서 노랑까지 칠해집니다. 나누는 방식: · 나쁜 시작 처음 시작

지금 로그 가능도는 입니다. 부드럽게 나누는 EM에서는 이 값이 단계마다 결코 줄지 않습니다. 까닭은 한 줄의 항등식에 있습니다. 숨은 이름표 z에 대한 아무 분포 q에 대해

$$\log p(x \mid \theta) = \underbrace{\mathbb E_{q}\!\left[\log\frac{p(x, z \mid \theta)}{q(z)}\right]}_{\text{하한 } B(q,\,\theta)} + D_{\mathrm{KL}}\bigl(q(z)\,\|\,p(z \mid x, \theta)\bigr)$$

가 성립합니다. $p(x, z)/p(z \mid x) = p(x)$이기 때문입니다. 쿨백–라이블러 발산⁠(Kullback–Leibler divergence)⁠은 0 이상이므로 B는 로그 가능도의 하한(증거 하한⁠, evidence lower bound⁠)입니다. E 단계는 q를 사후 분포⁠(posterior distribution)⁠ $p(z \mid x, \theta)$로 정해 KL 발산⁠(KL divergence)⁠을 0으로 만듭니다. 하한⁠(lower bound)⁠이 지금 자리에서 로그 가능도에 딱 닿게 하는 것입니다. M 단계는 q를 고정한 채 B를 θ에 대해 가장 크게 만듭니다. B는 책임도를 가중치로 삼은 완전한 자료의 로그 가능도에 q의 엔트로피⁠(entropy)⁠를 더한 것입니다. 엔트로피 항은 θ와 무관하므로, 위의 가중 평균 공식이 바로 B의 최댓값을 주는 θ입니다. 그러니 $\log p(x \mid \theta_{\text{새}}) \ge B(q, \theta_{\text{새}}) \ge B(q, \theta_{\text{옛}}) = \log p(x \mid \theta_{\text{옛}})$입니다.

줄지 않는다는 것이 가장 높은 곳에 간다는 뜻은 아닙니다. EM은 대개 기울기⁠(slope)⁠가 0인 곳(국소 최대점⁠(local maximum)⁠, 드물게는 안장점⁠(saddle point)⁠)에 멈추고, 어디에 멈출지는 출발점에 달렸습니다. '나쁜 시작'을 누르고 끝까지 돌려 처음 시작과 비교해 보세요. 이름을 붙이고 일반적인 틀로 정리한 1977년 뎀프스터, 레어드, 루빈의 논문에도 수렴⁠(convergence)⁠ 증명에 빈틈이 있었고, 1983년 제프 우가 이를 바로잡았습니다. 더 근본적인 함정도 있습니다. 한 성분의 평균을 점 하나에 두고 표준편차를 0으로 보내면 그 점의 밀도가 한없이 커져 가능도가 무한대로 갑니다. 곧 분산을 자유롭게 둔 가우스 혼합⁠(Gaussian mixture)⁠에는 가능도의 최댓값이 없고, 우리가 찾는 것은 좋은 국소 최대점입니다. 실제로는 분산에 아래 한계를 두거나 사전 분포⁠(prior distribution)⁠를 더해 이를 막습니다. 성분들이 많이 겹치면 수렴이 매우 느려지는 것도 알려진 약점입니다.

나누는 방식을 '딱 잘라 나누기'로 바꿔 보세요. 책임도를 0과 1로 반올림해, 점마다 사후 확률이 더 큰 성분에 통째로 넣습니다. 그림의 이 방식은 표준편차와 비율도 다시 구합니다(분류 EM). 여기서 더 나아가 두 표준편차를 같은 값으로, 비율을 1/2로 고정하면 '더 가능성 높은 성분'은 '평균이 더 가까운 성분'이 되고, 알고리즘은 정확히 k-평균 군집⁠(k-means clustering)⁠의 로이드 알고리즘⁠(Lloyd's algorithm)⁠이 됩니다. 공통 표준편차를 고정하고 0으로 보낼 때 부드러운 책임도가 0과 1로 굳어지는 극한⁠(limit)⁠이기도 합니다. k-평균이 무리의 경계를 늘 곧게(보로노이 칸의 경계로) 긋는 것과 달리, 가우스 혼합은 퍼짐이 다른 무리도 나누고, 여러 차원에서는 무리마다의 공분산⁠(covariance)⁠으로 마할라노비스 거리⁠(Mahalanobis distance)⁠를 씁니다. 딱 잘라 나누면 혼합 모형⁠(mixture model)⁠의 로그 가능도가 줄지 않는다는 보장은 사라집니다. 그 방식이 늘리는 것은 이름표까지 모수로 본 다른 가능도이기 때문입니다.

EM은 가우스 혼합만의 방법이 아닙니다. 값이 빠진 자료, 문서마다 섞인 주제를 찾는 토픽 모형⁠(topic model)⁠, 날씨 같은 숨은 상태가 이어지는 은닉 마르코프 모델⁠(hidden Markov model)⁠의 바움–웰치 알고리즘⁠(Baum–Welch algorithm)⁠이 모두 같은 틀입니다. 사후 분포를 정확히 계산할 수 없을 때 q를 계산하기 쉬운 분포로 제한하고 하한 B를 키우면 변분 추론⁠(variational inference)⁠이 되고, 이 하한이 변분 오토인코더⁠(variational autoencoder)⁠의 학습 목적 함수⁠(function)⁠이고, 확산 모델⁠(diffusion model)⁠의 학습 목적 함수도 이 하한에서 출발해 유도됩니다. 혼합 분포를 자료에 맞춘 이른 예로 널리 알려진 것은 1894년 칼 피어슨의 작업입니다. 그는 월터 웰던이 잰 나폴리 게의 몸 치수 비율에서 두 정규분포의 혼합을 찾았는데, 평균과 분산 같은 적률⁠(moment)⁠을 자료와 맞추는 적률법⁠(method of moments)⁠을 쓰느라 9차 방정식을 풀어야 했습니다.

이어지는 곳. k-평균 군집은 EM의 딱 잘라 나누는 극한이라, 그 페이지의 '거리 제곱합이 줄지 않는다'는 논증과 여기의 '가능도가 줄지 않는다'는 논증은 같은 모양입니다. 책임도는 베이즈 정리의 사후 확률이고, M 단계의 가중 평균과 가중 분산은 기댓값⁠(expected value)⁠과 분산을 책임도로 센 것입니다. 하한과 KL 발산으로 나누는 항등식은 교차 엔트로피⁠(cross-entropy)⁠가 엔트로피와 KL 발산으로 나뉘는 것과 같은 계산입니다. 1991년 제이컵스, 조던, 놀런, 힌턴이 내놓은 전문가 혼합⁠(mixture of experts)⁠은 섞는 비율 자체가 입력에 따라 소프트맥스⁠(softmax)⁠로 바뀌는 혼합 모형이고, 1994년 조던과 제이컵스는 그 계층판을 EM으로 학습시켰습니다. 성분 수를 몇으로 할지는 가능도만으로 정할 수 없어서(성분을 늘리면 자료에 더 바짝 맞출 수 있어 가능도가 커지기만 하므로) 교차 검증⁠(cross-validation)⁠이나 베이즈 정보 기준(BIC)처럼 복잡도에 벌점을 주는 기준으로 고릅니다.