[Clustering] Model-based Methods, Expectation Maximization (EM)

Model-Based Clustering

주어진 데이터를 만족하는 수학적 모델링을 최적화하는 방법.

기본 가정: 데이터는 여러 확률 분포의 혼합이다. (mixture of underlying probability distribution)

 

Clustering에서는 Expectation Maximization(EM, 기댓값 최대화)가 대표적인 model-based clustering이다.

Expectation Maximization (1977)

Overview

$N$개의 $\mathbb{R}^2$ 데이터 $\mathbf{X}$가 주어졌을 때, $K$개의 Gaussian 분포의 파라미터 $\mathbf{\Theta}$를 구한다.

\[ \mathbf{X} = (x_1, x_2, \dots, x_N), \quad \mathbf{\Theta} = (\theta_1, \theta_2, \dots, \theta_K) \]

EM은 mixture of Gaussians을 수학적 모델로 가정하고 있다.

반응형

Algorithm

$n$번째 point가 $k$번째 mixture에서 생성되었을(comes from, belongs to) 가능도

\[ r_{n, k} = \cfrac{p(x_n | \theta_k)}{\sum_{i=1}^{k} p(x_n | \theta_i)} \]

 

따라서 각 데이터 포인트마다 $r$을 구할 수 있다.

\[ (r_{n, 1}, r_{n,2}, \dots, r_{n,k}) \]

그리고 $r$을 이용하여 각 가우시안 모델의 weighted mean, weighted variance를 구하여 $\theta$를 구한다.

 

Expectation Step (E-Step)

collection of parameter $\Theta = (\alpha_1, \dots, \alpha_k, \theta_1, \dots, \theta_k)$

• $\alpha_j$: $j$번째 가우시안 모델의 가중치. $\sum_j \alpha_j = 1$이다.
• $\theta_j = (\mu_j, \Sigma_j)$: $\mu_j$와 $\Sigma_j$는 각각 $j$번째 가우시안의 평균과 공분산행렬.

 

따라서 $j$번째 가우시안 모델은 아래와 같다.

\[ f_j(x|\theta_j) = \cfrac{1}{(2\pi)^{d/2} |\Sigma_j|^{1/2} } \text{exp}\left[ -\cfrac{1}{2}(x-\mu_j)^\top \Sigma_j^{-1}(x - \mu_j) \right] \]

 

E-step에서는 어떤 가우시안 모델의 log-likelihood가 높은지 계산한다.

\[ p(j | x_i, \Theta) = \cfrac{\alpha_j f_j(x_i | \theta_j)}{\sum_{k=1}^{K}\alpha_k f_k(x_i | \theta_k)} \]

 

Maximization Step (M-Step)

M-step에서는 E-Step에서 구한 likelihood를 이용하여 parameter를 update한다.

\begin{align*} \mu_j^{new} &= \cfrac{\sum_{i=1}^{N} x_i p(j|x_i, \Theta^{old}) }{\sum_{i=1}^{N}p(j|x_i, \Theta^{old})} \\ \Sigma_j^{new} &= \cfrac{\sum_{i=1}^{N}p(j|x_i, \Theta^{old}) (x_i - \mu_j^{new}) (x_i - \mu_j^{new})^\top }{\sum_{i=1}^{N}p(j|x_i, \Theta^{old})} \\ \alpha_j^{new} &= \cfrac{1}{N}\sum_{i=1}^{N}p(j|x_i, \Theta^{old}) \end{align*}

 

Example

Execution of EM

EM vs K-Means

K-Mean은 단순히 mean value로 center를 계산하는 방식이지만 EM은 확률분포(주로 가우시안 분포) 기반으로 cluster center를 계산하므로 그 차이가 있다.

• Representation: K-mean은 단순히 point이지만, EM은 distribution paramter(예. 가우시안의 경우 평균과 공분산 행렬)로 표현한다.
• Membership:K-mean은 하나의 point는 하나의 클러스터에 매핑되지만 EM은 모든 클러스터에 대하여 확률로 나타낼 수 있다. ($x_1 \to c_1:80\%, c_2:10\%, c_3=10\%$)