[Density Estimation]GMM(Gaussian Mixture Model)과 EM 알고리즘

• Parametic Methods(단순한 분포를 가정하고 유한한 파라미터를 구하자)
  • ML(Maximum Likelihood) Estimation
  • MAP(Maximum A Posteriori) Estimation
• Non-Parametic Methods(복잡한 분포를 가정하자)
  • 파젠창(Parzen Window)
  • K-Nearest Neighbor Estimation
• (Parametric Methods + Non Parametic Methods)단순한 분포를 여러개 사용하자!

 

 

---

 

Mixture Models

 

 

두 개 이상의 서로 다른 확률 분포의 혼합으로 데이터의 확률 분포를 모델링하자.

 

 

(b)와 같이 하나의 단순 분포로 나타내기에는 아무래도 무리가 있다.

그래서 (c)와 같이 두 개의 단순 분포를 혼합해서 사용하는 것이다.

이처럼 Unsupervised learning(clustering)에 많이 활용된다.

 

 

GMM(Gaussian Mixture Model)

 

 

 

단순 분포로서 가우시안을 택한다면 이는 Gaussian Mixture Model이 된다.

데이턱 K개의 가우시안분포로부터 생성되었다고 보는 모델이다.

여러 가우시안의 선형결합형태는 복잡한 밀도까지 표현할 수 있다.

 

 

아래의 모양은 다음과 같이 가우시안 세 개를 사용했으므로 표현할 수 있겠다. 

 

$$P(x) = \pi_1N(x|\mu_1,\Sigma_1) + \pi_2N(x|\mu_2,\Sigma_2) + \pi_3N(x|\mu_3,\Sigma_3)$$

 

$x_4$가 발생할 확률은 다음과 같이 계산된다.

$$P(x_4) = \pi_1N(x_4|\mu_1,\Sigma_1) + \pi_2N(x_4|\mu_2,\Sigma_2) + \pi_3N(x_4|\mu_3,\Sigma_3)$$

 

 

위에서 보았듯, 매 분포마다 가중치 $\pi$가 곱해져 있다.

가중치는 분포마다의 샘플 발생 빈도에 따라서 정해진다.

 

일반화하여 K개 가우시안들의 선형 결합으로 확률 분포를 표현하자면

$$P(x) = \sum\limits_{k=1}^K\pi_kN(x|\mu_k,\Sigma_k)$$

 

 

그러므로 추정할 파라미터는 가우시안 한 세트당 {$\pi, \mu, \Sigma$}이다.

 

 

 

우선 어떠한 데이터 분포가 하나의 가우시안을 따른다고 가정하고 시작했을 때에는

MLE 또는 MAP를 cost를 미분하여 구할 수 있었다.

 

그렇게 구한 최적의 파라미터는 다음과 같다.

 

$$\hat{\mu} = \frac{1}{n}\sum_{i=1}^{n}x_i$$

 

$$\hat{\sigma}^2 = \frac{1}{n}\sum_{i=1}^{n}\left(x_i-\mu\right)^2$$

 

 

 

 

만일 라벨이 주어진 경우를 생각해보자.

라벨도 알고 있겠다, 각각에 대해서 Maximum Likelihood로 analytic하게 계산하면

likelihood가 최대로 되는 $\mu$와 $\sigma$를 추정할 수 있다.

 

 

다음과 같이 데이터에 라벨이 주어지지 않은 데이터가 있다.

 

라벨을 부여하기 위해서는 확률 분포가 필요하고,

확률 분포를 얻기 위해서는 파라미터를 알아야 하고,

파라미터를 알기 위해서는 다시 각 데이터의 라벨이 필요하다.

 

 

어디에 속하는지 라벨을 얻기 위해서는 분포가 필요하고,

분포를 얻기 위해서는 다시 라벨이 필요하다.

 

 

 

즉 어떠한 데이터 분포가 Gaussian Mixture을 따른다고 가정하고 시작했을 때

 

1) 가우시안 분포는 몇 개 쓸지(몇 개의 k label이 있을 것이라 가정할지)

2) 가우시안 모양(파라미터)은 어떻게 세팅할 것인지

3) 샘플이 어떤 가우시안에 속하는지

멤버십 결정(소속정보)과 매개변수 추정(분포)을 번갈아 반복해보자(EM 알고리즘)

 

 

 

EM Algorithm의 순서도

 

1) K개의 분포에 대해서 난수로 파라미터 설정

2) [E단계]각 샘플이 어떤 분포에 속하는지 소속정보 Z 추정

3) [M단계]각 분포에 소속된 샘플들을 이용하여 확률분포 $\theta$ 갱신(MLE 사용)

2) 3)을 iterative하게 반복한다.

 

 

이러한 과정을 통해서 가우시안 분포가 자리를 찾아간다.

 

 

 

구체적으로 위 예제와 함께 Expectation 단계와 Maximization 단계를 살펴보자.

 

 

E단계 : 소속정보 Z 추정

 

 

현재는 class 수 K = 2으로 잡았고, 샘플 수 N = 10이다.

 

샘플과 각각의 가우시안과의 관계를 행렬로 나타내니

행렬 요소 값은 특정 k번째 가우시안에서 $x_i$가 발생하는 확률이겠다.

앞으로 이에 대해서 $P(z_{ki}=1|x_i) = r^{(k)}_i$라고 칭하겠다.

 

 

샘플 $x_i$가 $k^{th}$ 가우시안 분포에서 발생했을 (사후)확률은,

$P(z_{ki}=1|x_{i}) = \dfrac{P(x_i|z_{ki}=1)P(z_{ki}=1)}{P(x_i)}$

$= \dfrac{\pi_k N(x_i|\mu_k, \Sigma_k)}{\sum_{j=1}^{K}\pi_j N(x_i|\mu_j, \Sigma_j)}$

 

• 조건부확률 $\dfrac{P(x_i|z_{ki}=1)P(z_{ki}=1)}{P(x_i)}$ : k번째 가우시안에 소속했다고 할 때 x가 얼마나 발생할 지
• 사전확률 $P(z_{ki}=1) = \pi_k$
• likelihood $P(x_i|z_{ki}=1) = N(x_i|\mu_j, \Sigma_k)$

 

 

 

 

 

 

$z_{ki}$는 샘플 $x_i$가 $k^{th}$ 가우시안에서 발생하는 확률

 

 

 

 

이렇게 E단계로 각 분포에 대해 샘플의 소속 정보를 나타낸 뒤

M단계를 거치면서 소속정보를 가장 잘 나타내도록(maximize) 하는 파라미터 업데이트를 한다.

 

 

 

그렇다면 파라미터를 바꾸어보자!

 

 

 

M단계 : 확률분포 $\theta$ 추정

 

 

Maximum Likelihood Estimation을 다시 상기시켜보면
<샘플 likelihood의 곱>을 최대화하는 것이고,
0에 수렴하는 값이 될 우려를 피하기 위해 log를 취하여 곱을 덧셈으로 만듦으로써
<log(샘플 likelihood)의 덧셈>을 최대화한다.

 

 

앞에서도 이야기했듯, 가우시안 분포 당 $\pi, \mu, \sigma$를 추정해야한다.

 

$$P(x) = \sum\limits_{k=1}^K\pi_kN(x|\mu_k,\Sigma_k)$$

 

 

 

 

 

 

위의 과정을 거쳐 constraint optimization 문제로 본다면,

 

$\textrm{maximize } L(\theta) = \sum_{i=1}^N log (\sum_{k=1}^K\pi_kN(x|\mu_k, \Sigma_k))$
$\textrm{subject to } \sum_{k=1}^K\pi_k=1$

 

$L(\theta, \lambda) = L(\theta) + \lambda(\sum_{k=1}^K\pi_k-1) = 0$

 

$\dfrac{\partial L(\theta, \lambda)}{\partial \mu_k} = 0, \dfrac{\partial L(\theta, \lambda)}{\partial \Sigma_k} =0, \dfrac{\partial L(\theta, \lambda)}{\partial \pi_k} =0$

 

 

 

$\pi_k$를 업데이트 시킨 뒤 $\mu_k, \Sigma_k$에 MLE를 하는 문제로 볼 수도 있다.

 

소속정보 $r_i^{(k)}$를 통해서 파라미터 업데이트 하는 것이 MLE가 직접적이기에 이로 풀이를 해보겠다.

 

 

 

0) $r^{(k)}$ 정의

$r^{(k)}$ = k번째 분포에 속한 샘플의 확률적 개수

$$r^{(k)} = \sum_{i=1}^NP(z_{ki}=1|x_i) = \sum_{i=1}^Nr^{(k)_i}$$

 

 

 

1) $\pi_k$ 업데이트

 

만일 3개의 가우시안, 모든 샘플 10개 중에서 1번째 가우시안에 5개의 샘플이 포함되어있다면

100퍼센트의 확률로 속하니, $\dfrac{5 \times 1}{10}$로 가중치 $\pi_1$를 주겠다.

 

현재 우리가 구해야 할 $\pi_k$는 소속확률이 1이 아닌 것 빼고 똑같다.

 

k번째 분포가 선택되는 (확률적) 빈도 = k번째 가우시안에 속한 샘플의 <확률적> 개수 / 전체 sample의 개수

$$\pi_k = \dfrac{r^{(k)}}{N}$$

 

 

2) $\mu_k$ 업데이트

 

원래 평균을 구할 때 다음으로 구했다.

$\mu = \dfrac{1}{N}\sum_{i=1}^{N}x_i$

샘플 N개의 100% 발생이 아니므로 $N$을 $r^{(k)}$로 치환한다.

또한 $x_i$ 샘플 하나의 발생 확률이라는 것이 있으니 $x_ir^{(k)}$으로 치환한다.

 

$$\mu_k = \dfrac{1}{r^{(k)}}\sum_\limits{i=1}^Nx_ir^{(k)}_i$$

 

이는 k class에 대한 class mean으로 칭하기도 한다.

 

 

 

3) $\Sigma_k$ 업데이트

 

분산은 편차 제곱의 평균으로 계산했다.

$\sigma^2 = \frac{1}{N}\sum_{i=1}^{N}\left(x_i-\mu\right)^2$

 

이로부터 확률적인 발생을 반영하여 N과 $x_i$을 바꾸어주면,

$$\Sigma_k=\dfrac{1}{r^{(k)}}\sum_\limits{i=1}^nr^{(k)}_i(x_i-\mu_k)(x_i-\mu_k)^T$$

 

 

 

 

이렇게 M단계를 거쳐 분포가 조정되고 이로부터 E단계를 거쳐 소속정보를 업데이트한다....

iteratively하게 E, M단계를 계속 거치면서 다음처럼 더 좋은 clustering을 하게 된다.