GMM (Gaussian Mixture Model)

mixture model

비지도 학습에는 label k가 없기에 latent z를 사용한다.

\(p(x)=\sum_zp(x,z)=\sum_zp(x|z)p(z)\)

 

대표적인 mixture model인 GMM을 알아보자.

GMM은 더 일반화된 분포를 다룰수 있다.

\(p(x)=\sum_{k=1}^K\pi_kN(x|\mu_k,\sum_k),\pi_k\) : mixing coefficients

\(\sum_{k=1}^K\pi_k=1,\pi_k\geq0, \forall k\)

 

GMM은 밀도추정을 하고 universarial approximator 이다. 심지어 diagonal GMM 또한 universarial approximator이다.

MLE \(lnp(X|\pi,\mu,\sum)=\sum_{n=1}^Nln(\sum_{k=1}^K\pi_kN(x^{(n)}|mu_k,\sum_k)) w.r.t \Theta=\{\pi_k,\mu_k,\sum_k\}\)

 

GMM Cons

• Sigularities : 이상치에 민감하게 반응
• Identifiablity : Solution is invariant to permutations, \(\pi_k\)는 class각각을 의미해야 하나 GMM에서는 permutation이 일어나도 같은 값으로 인식한다는 문제 [link]
• Non-convex : convex이면 loacl minumum or maximum 이 global minumum, maximum이 될 수 있기 때문

 

Latent Variable

Unsupervised learning에서는 label이 없기 때문에 input data의 보이지 않는 latent variable z를 잘 추출해 이를 통해 군집화나 분류 등등 task를 수행한다. GMM hidden latent variable z는 observation x를 잘 표현하고 Categorical 확률로 나타난다.

 

Let z ~ Categorical(\(\pi\)) ( where \(\pi_k \geq 0, \sum_k \pi_k=1\))

Then \(p(x) = \sum_{k=1}^Kp(x,z=k)=\sum_{k=1}^Kp(z=k)p(x|z=k)=\sum_{k=1}^K\pi_kN(x|\mu_k,\sum_k)\)

 

주요 포인트는 복잡한 분포를 간단한 분포의 합으로 보는 것이다. 비슷한 개념으로는 푸리에 변환, 컴퓨터알고리즘은 분할정복(divide-and-conquer)이 있다.

 

이제 p(x)를 latent z기준으로 나누어 보자.

joint distribution : \(p(x,z)=p(z)p(x|z)\)

log-likelihood : \(l(\pi,\mu,\sum)=lnp(X|\pi,\mu,\sum)=\sum_{n=1}^Nlnp(x^{(n)}|\pi,\mu,\sum)\)

\(=\sum_{n=1}^nln\sum_{z^{(n)}=1}^Kp(x^{(n)}|z^{(n)};\mu,\sum)p(z^{(n)}|\pi)\)

 

\(z^{(n)}\) is a hidden variable for every observation

General problem : sum inside the log

Categorical probability K의 값에 따라 복잡도가 증가하는데 Gaussian bayes classifiers 과 유사한 방식으로 최적화 해보자.

복잡한 분포를 여러 간단한 분포의 합으로 표현할 수는 있으나 분포들의 각 확률을 반영한 합이 아닌 K개의 분포중 한곳에만 속한다고 가정하는 것이다.

 

MLE로 문제를 푸는 과정에서 K>1 일때, \(\pi\)를 알 수 없기에 미분을 통해 closed form을 구할 수 없다. 만약 모든 K=1인 경우는 GDA와 다를게 없는 식이 된다.

\(lnp(x^{(n)},z^{(n)}|\pi,\mu,\sum)=lnp(x^{(n)}|z^{(n)};\pi,\mu,\sum)p(z^{(n)}|\pi,\mu,\sum)=lnp(x^{(n)}|z^{(n)};\mu,\sum)p(z^{(n)}|\pi)\)

\(=\sum_{n=1}^N ln \sum_{z^{(n)}=1}^K p(x^{(n)}|z^{(n)};\mu,\sum)p(z^{(n)}|\pi)\)

 

category k에 대한 최적의 평균,분산, 그리고 전체 분포에 영향을 미치는 parameter \(\pi\)에 대한 값을 위 식을 미분하여 구해보자.

계산 과정에서 Gaussian bayes classifiers와 같은 optimizing기법을 사용할 수 있다. (선택사항)

 

\(\mu_k=\frac{\sum_{n=1}^N1_{[z^{(n)}=k]}x^{(n)}}{\sum_{n=1}^N1_{[z^{(n)}=k]}}\)

\(\sum_k=\frac{\sum_{n=1}^N1_{[z^{(n)}=k]}(x^{(n)}-\mu_k)(x^{(n)}-\mu_k)^T}{\sum_{n=1}^N1_{[z^{(n)}=k]}}\)

\(\pi_k=\frac{1}{N}\sum_{n=1}^N1_{[z^{(n)}=k]}\)

 

K=1이라면 closed form으로 답을 구할수 있지만(GDA) K>1인 경우 \(\pi\)는 각 모든 data point가 각 K개의 cluster에 속하는 비율로 생각할 수 있지만 label이 없는 unsupervised learning 관점에서 Ground truth을 알 수 없기 때문에 closed form으로 해결할 수 없다.

그럼 최적화와 학습을 어떻게 진행할까?

Use the Expectation Maximization algorithm (EM)

1. E-step : compute the posterior probability over z
2. M-step : change the parameters of each Guassian to maximize the probability with current responsibilities.

so we will simply guess the values of the GMM and iteratively refine our guess by alternating between probabilistic inference (updating our cluster assignment inferences) and statistical inference (updating our parameter estimates).

K-Means algorithms과 비슷한 방식을 따르기도 한다.

1. Assignment step : assign each data point to the closest cluster
2. Refitting step : Move each cluster center to the center of gravity of the data assigned to it

이때 각 포인트가 K개의 cluster중 무조건 한곳에서만 나온다고 가정할 시에는 hard clustering K개의 cluster 각각에 대해 확률을 모두 고려할 시에는 soft clustering이 된다.

 

Steps of GMM optimization

1. E-step
   inference problem : which Gaussian generated each datapoint?
   Conditional probability (using Bayes rule) of z given x \(\rightarrow\) responsibility of cluster k towards x
   \(\gamma_k^{(n)}=p(z^{(n)}=k|x^{(n)};\pi,\mu,\sum)\)
   \(=\frac{p(z=k)p(x|z=k)}{p(x)}\)
   \(=\frac{p(z=k)p(x|z=k)}{\sum_{j=1}^Kp(z=j)p(x|z=j)}\)
   \(=\frac{\pi_kN(x|\mu_k,\sum_k)}{\sum_{j=1}^K\pi_jN(x|\mu_j,\sum_j)}\)
   
   \(E_{P(z^{(i)}|x^{(i)})}[\sum_ilog(P(X^{(i)},z^{(i)}|\Theta))]\)
   \(=\sum_i\sum_k\gamma^{(i)}_k(log(P(z^i=k|\Theta))+log(P(x^{(i)}|z^{(i)}=k,\Theta)))\)
   \(=\sum_i\sum_k\gamma^{(i)}_k(log(\pi_k)+log(N(x^{(i)};\mu_k,\sum_k)))\)
   
   
2. M-step
   \(Optimize : \sum_k\sum_i\gamma^{(i)}_klog(\pi_k)+\sum_k\sum_i\gamma^{(i)}_klog(N(x^{(i)};\mu_k,\sum_k))\)
   • each Gaussian gets a certain amount of posterior porbability for each datapoint.
   • fit each Gaussian to the weighted datapoints
   • derive closed form updates for all parameters
     
     \(\mu_k=\frac{1}{N_k}\sum_{n=1}^N\gamma^{(n)}_kx^{(n)}\)
     \(\sum_k=\frac{1}{N_k}\sum_{n=1}^N\gamma^{(n)}_k(x^{(n)}-\mu_k)(x^{(n)}-\mu_k)^T\)
     \(\pi_k=\frac{N_k}{N}withN_k=\sum_{n=1}^N\gamma^{(n)}\)

Evaluate log likelihood and check for convergence

\(lnp(X|\pi,\mu,\sum)=\sum_{n=1}^Nln(\sum_{k=1}^K\pi_kN(x^{(n)}|\mu_k,\sum_k))\)

 

Mixture of Guassians vs K-means

• GMM with EM is just like a soft version of K-means, with fixed priors and covariance.
• We saw soft assignments based on the softmax of the squared Mahalanobis distance from each data to each cluster rather than hard assignments.
• In K-means, weights are 0 or 1.
• General approach, Guassian can be replaced to other distributions.
• Mixture model is universal approximator
• Optomization is done using the EM alogorithm.

[참고자료]

https://web.stanford.edu/~lmackey/stats306b/doc/stats306b-spring14-lecture2_scribed.pdf