9. Mixture Models and EM

이 장에서는 혼합 모델과 그를 학습하는 EM 알고리즘에 대해 다룬다.

9.1. K-means Clustering

K-평균 클러스터링은 D차원 데이터 N개를 K개의 클러스터로 나눌 때 자주 쓰이는 클러스터링이다. 이는 K개의 클러스터에 대한 평균점을 초기화시킨 뒤, 평균점들을 그 클러스터로 분류된 데이터들의 평균으로 놓고, 이를 반복한다.

9.1.1. Image segmentation and compression

K-평균 클러스터링은 이미지 세그멘테이션과 압축에 쓰인다.

9.2. Mixtures of Gaussians

p(\mathbf{x}) = \sum_{k=1}^{K} \pi_{k} \mathcal{N}(\mathbf{x} | \mathbf{\mu}_{k}, \mathbf{\Sigma}_{k})의 형태를 가진 분포를 가우시안 혼합 분포라 한다.

9.2.1. Maximum likelihood

최대가능도추정은 일반적인 방법으론 계산 가능하지 않고 EM 등의 방법을 써야 한다.

9.2.2. EM for Gaussian mixtures

가우시안 혼합의 기대값 최대화 알고리즘은 다음과 같다.

  1. \mathbf{\mu}_{k}, \mathbf{\Sigma}_{k}, \pi_{k}을 초기화하고 로그 가능도의 초기값을 구한다.
  2. E 단계. \gamma(z_{nk}) = \frac{\pi_{k} \mathcal{N}(\mathbf{x}_{n} | \mathbf{\mu}_{k}, \mathbf{\Sigma}_{k})}{\sum_{j=1}^{K}\pi_{j} \mathcal{N}(\mathbf{x}_{n} | \mathbf{\mu}_{j}, \mathbf{\Sigma}_{j})} 을 구한다.
  3. M 단계. \mathbf{\mu}_{k, new} = \frac{1}{N_{k}} \sum_{n=1}^{N} \gamma(z_{nk}) \mathbf{x}_{n}, \mathbf{\Sigma}_{k, new} = \frac{1}{N_{k}} \sum_{n=1}^{N} \gamma(z_{nk}) (\mathbf{x}_{n} - \mathbf{\mu}_{k, new})(\mathbf{x}_{n} - \mathbf{\mu}_{k, new})^{T}, \pi_{k, new} = \frac{N_{k}}{N} 으로 재추정한다. (N_{k} = \sum_{n=1}^{N} \gamma(z_{nk}))
  4. 로그 가능도 \ln p(\mathbf{X} | \mathbf{\mu}, \mathbf{\Sigma}, \mathbf{\pi}) = \sum_{n=1}^{N} \ln (\sum_{k=1}^{K} \pi_{k} \mathcal{N}(\mathbf{x}_{n} | \mathbf{\mu}_{k}, \mathbf{\Sigma}_{k}))을 구한다. 수렴하지 않았으면 2단계로 되돌아간다.

9.3. An Alternative View of EM

일반적인 EM 알고리즘은 다음과 같다.

  1. \mathbf{\theta}_{old}을 초기화한다.
  2. E 단계. p(\mathbf{Z} | \mathbf{X}, \mathbf{\theta}_{old})을 구한다.
  3. M 단계. \mathbf{\theta}_{new} = \mathrm{argmax}_{\mathbf{\theta}} \mathcal{Q}(\mathbf{\theta}, \mathbf{\theta}_{old})을 구한다. 여기서 \mathcal{Q}(\mathbf{\theta}, \mathbf{\theta}_{old}) = \sum_{\mathbf{Z}} p(\mathbf{Z} | \mathbf{X}, \mathbf{\theta}_{old}) \ln p(\mathbf{X}, \mathbf{Z} | \mathbf{\theta})이다.
  4. 로그 가능도를 구한다. 수렴하지 않았으면 2단계로 되돌아간 뒤 \mathbf{\theta}_{old} = \mathbf{\theta}_{new}로 세팅한다.

9.3.1. Gaussian mixtures revisited

위의 알고리즘을 가우시안 혼합에 적용하면 9.2.에서 다루었던 알고리즘이 나온다.

9.3.2. Relation to K-means

K-평균 알고리즘과 가우시안 혼합에 대한 기대값 최대화 알고리즘은 유사한 관계가 있다.

9.3.3. Mixtures of Bernoulli distributions

베르누이 분포의 혼합에 대해 E 단계는 다음과 같다.

\gamma(z_{nk}) = \frac{\pi_{k} p(\mathbf{x}_{n} | \mathbf{\mu}_{k})}{\sum_{j=1}^{K} \pi_{j} p(\mathbf{x}_{n} | \mathbf{\mu}_{j})}

N_{k} = \sum_{n=1}^{N} \gamma(z_{nk})

\bar{\mathbf{x}}_{k} = \frac{1}{N_{k}} \gamma(z_{nk}) \mathbf{x}_{n}

M 단계는 다음과 같다.

\mathbf{\mu}_{k} = \bar{\mathbf{x}}_{k}

\pi_{k} = \frac{N_{k}}{N}

9.3.4. EM for Bayesian linear regression

베이지안 선형 회귀에서 E 단계에서는 \mathbf{w}의 사후분포를 구한 뒤 이를 이용해서 기대 데이터 로그가능도를 구한다. M 단계는 다음과 같다. \alpha = \frac{M}{\mathbf{m}_{N}^{T} \mathbf{m}_{N} + \mathrm{tr}(\mathbf{S}_{N})} $\beta$도 비슷하게 구할 수 있다.

9.4. The EM Algorithm in General

\ln p(\mathbf{X} | \mathbf{\theta}) = \mathcal{L}(q, \mathbf{\theta}) + KL(q \lvert \lvert p)인데 EM 알고리즘의 각 단계는 KL 발산을 감소시킨다. 따라서 EM 알고리즘의 정당성이 보장된다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중