(Deep Bayes) 05.TEST - Approximate Bayesian Inference

[Deep Bayes] TEST - Approximate Bayesian Inference

해당 내용은 https://deepbayes.ru/ (Deep Bayes 강의)를 듣고 정리한 내용이다.

Clustering Problem

문제를 풀기에 앞서서, Clustering에 대해서 알아보자. 많이들 알 고 있을 것이니 간단하게만 이야기하고 넘어갈 것이다. 우선 Clustering은 데이서셋 \(X = \{x_i\}_{i=1}^{N}\) 를 K개의 클러스터로 그룹핑하는 것을 의미한다. 대표적인 예시로 K-Means Clustering이 있다. 여기서 우리가 다루게 될 Clustering 기법은 GMM ( Gaussian Mixture Model )이다.

Gaussian Mixture Model

• K 개의 Gaussian components로 구성 ( 각각의 probability : \(\pi = (\pi_1,...\pi_K)\) )

• 각각의 Gaussian은 parameter \(\mu_k\)와 \(\lambda_k\)를 가짐

• 모든 데이터는, 각각의 K개의 클러스터에 대한 소속 정도를 의미하는 latent variable을 가짐

  \[z_i \in \{0,1\}^K,\;\;\; \sum_{k=1}^{K}z_{ik}=1\]

GMM을 식으로 확인하면 다음과 같다.

\[p(X,Z \mid \pi, \mu, \lambda ) = \prod_{i=1}^{N}p(z_i \mid \pi)p(x_i \mid z_i, \mu, \lambda) = \prod_{i=1}^{N} \prod_{k=1}^{K} [ \pi_k N(x_i \mid \mu_k, \lambda_k^{-1})]^{z_{ik}}\]

이를 통해, 우리가 알고 싶은 것은 두 개이다.

• 1 ) latent variable \(z\)에 대한 posterior distribution
• 2 ) 최적의 parameter

Inference methods

우리가 풀고자 하는 문제는 크게 세 가지로 구분해볼 수 있을 것이다.

• 1 ) Parameter만 구하고 싶은 경우
• 2 ) Latent Variable만 구하고 싶은 경우
• 3 ) Parameter와 Latent Variable을 모두 구하고 싶은 경우

1)의 경우에는, Maximum Likelihood 방법을 사용하면 된다.

2)의 경우에는, 또 다시 세 가지로 나눠 생각해볼 수 있다

• a) Conjugacy가 있는 경우 : Full Bayesian Inference
• b) Conditional Conjugacy가 있는 경우 : Mean field Variational Inference
• c) Conjugacy가 없는 경우 : Parametric Variational Inference

3)의 경우, 위의 2)의 경우에다가, 저번 포스트에서 다룬 EM Algorithm을 적용하면 된다.

Clustering 및 GMM에 대한 내용과 저번 시간의 내용에 대한 정리는 여기까지 하고, 이제 문제를 풀어볼 것이다.

문제 풀이 시 참고할 수 있는 내용

Question 1. basic GMM

(a) Check that likelihood & prior are “CONJUGATE”

• prior distribution : \(p(Z)\)
• likelihood : \(p(X \mid Z,\pi, \mu, \lambda)\)

우선, GMM의 식을 확인해보자.

\[p(X,Z \mid \pi, \mu, \lambda ) = \prod_{i=1}^{N}p(z_i \mid \pi)p(x_i \mid z_i, \mu, \lambda) = \prod_{i=1}^{N} \prod_{k=1}^{K} [ \pi_k N(x_i \mid \mu_k, \lambda_k^{-1})]^{z_{ik}}\]

위 식에서, prior와 posterior는 다음과 같다.

• prior : \(p(Z) = \prod_{i=1}^{N}\prod_{k=1}^{K} \pi_k^{z_{ik}}=\prod_{i=1}^{N}\prod_{k=1}^{K}C^{z_{ik}}\)

• posterior : \(p(Z \mid X) \propto p(X,Z) = \prod_{i=1}^{N} \prod_{k=1}^{K} [ \pi_k N(x_i \mid \mu_k, \lambda_k^{-1})]^{z_{ik}} = \prod_{i=1}^{N} \prod_{k=1}^{K} C'^{z_{ik}}\)

따라서, 우리는 likelihood과 prior가 서로 conjugate함을 알 수 있다.

(b) E-step : derive \(p(Z\mid X, \pi, \mu, \lambda)\)

( Values of \(\pi, \mu, \lambda\) are fixed on this step )

위에서 우리는 posterior과 다음에 비례함(proportional to)을 확인했다.

\[p(Z \mid X) \propto p(X,Z) = \prod_{i=1}^{N} \prod_{k=1}^{K} [ \pi_k N(x_i \mid \mu_k, \lambda_k^{-1})]^{z_{ik}}\]

정확한 값을 구하기 위해서, 우리는 이를 정규화(Normalize) 해줄 필요가 있다

( \(\sum_{k=1}^{K}p(z_{ik}=1 \mid X) = 1\)가 되도록! )

그 결과, 최종적인 posterior \(p(Z\mid X)\) 는 다음과 같이 나오게 된다.

\[p(Z \mid X) = \prod_{i=1}^{N} \prod_{k=1}^{K} [ \frac{\pi_k N(x_i \mid \mu_k, \lambda_k^{-1})}{\sum_{j=1}^{K}\pi_j N(x_i \mid \mu_j, \lambda_k^{-1})}]^{z_{ik}}\]

(c) M-step : compute optimal values of \(\pi, \mu, \lambda\) by maximizing \(E_{p(Z\mid X, \pi, \mu, \lambda)} log\;p(X,Z \mid \pi, \mu, \lambda)\)

( posterior distribution on Z are fixed on this step )

\[\begin{align*} E_{p(Z\mid X)} log\;p(X,Z)&= E_{p(Z\mid X)} log\prod_{i=1}^{N} \prod_{k=1}^{K} [ \pi_k N(x_i \mid \mu_k, \lambda_k^{-1})]^{z_{ik}} \\ &=E_{p(Z\mid X)}\sum_{i=1}^{N}\sum_{k=1}^{K}z_{ik}[log \pi_k + logN(x_i \mid \mu_k, \lambda_k^{-1})]\\ &=E_{p(Z\mid X)}\sum_{i=1}^{N}\sum_{k=1}^{K}z_{ik}[log \pi_k + \frac{1}{2}log\lambda_k - \frac{1}{2}(x_i-\mu_k)^2\lambda_k] + C\\ &= \{E_{p(Z\mid X)}z_{ik} = p(z_{ik}=1 \mid X) = \gamma_{ik}\}\\ &=\sum_{i=1}^{N}\sum_{k=1}^{K}\gamma_{ik}[log \pi_k + \frac{1}{2}log\lambda_k - \frac{1}{2}(x_i-\mu_k)^2\lambda_k] + C\\ \end{align*}\]

우리는 위 식을 \(\pi, \mu, \lambda\)에 대해서 최소화해야한다.

우선, \(\pi\)에 대해서 구해보자. 그러기 위해, 다음과 같은 변환을 해주고 라그랑즈 승수를 사용하여 문제를 푼다.

\[\eta = log \pi_k\] \[L(\eta,\psi) = \sum_{i=1}^{N}\sum_{k=1}^{K}\gamma_{ik}\eta_k - \psi(\sum_{k=1}^{K}exp\; \eta_k -1)\]

위 식을 각각 \(\eta_k\)와 \(\psi\)에 대해 미분한 뒤 0이 되게끔 만들면 다음과 같이 나오게 된다.

\(0 = \frac{\partial\;L(\eta, \psi)}{\partial\;\eta_k} = \sum_{i=1}^{N}\gamma_{ik} - \psi exp\;\eta_k\) 이므로, \(\pi_k = exp\;\eta_k = \frac{\sum_{i=1}^{N}\gamma_{ik}}{\psi}\)

\(0 = \frac{\partial\;L(\eta, \psi)}{\partial\;\psi} = -\sum_{k=1}^{K}exp\;\eta_k +1\)이므로, \(\psi = \sum_{k=1}^{K}\sum_{i=1}^{N}\gamma_{ik} = N\)

따라서, \(\pi_k = \frac{\sum_{i=1}^{N}\gamma_{ik}}{N}\)가 나오게 된다.

위과 같은 방법으로 \(\mu\)와 \(\lambda\)도 구하게 되면, 다음과 같이 나온다.

\[\mu_k = \frac{\sum_{i=1}^{N}\gamma_{ik}x_i}{\sum_{i=1}^{N}\gamma_{ik}}\] \[\lambda_k = \frac{\sum_{i=1}^{N}\gamma_{ik}}{\sum_{i=1}^{N}\gamma_{ik}(x_i-\mu_k)^2}\]

Question 2. GMM with prior on \(\pi\)

이번 문제는 위 Question1. GMM에, \(\pi\)에 대한 prior가 있는 경우의 문제이다.

\(\pi\)가 Dirichlet Distribution을 따를 때의 경우를 적용해서 문제를 풀어보자.

우선, 우리의 probabilistic model은 다음과 같이 된다.

\[p(X,Z,\pi \mid \mu, \lambda ) = p(\pi)\prod_{i=1}^{N}p(z_i \mid \pi)p(x_i \mid z_i, \mu, \lambda) = Dir(\pi \mid \alpha) \prod_{i=1}^{N} \prod_{k=1}^{K} [ \pi_k N(x_i \mid \mu_k, \lambda_k^{-1})]^{z_{ik}}\]

이번 문제가 이전 문제와 가지는 또 다른 차이점은, 더 이상 prior와 likelihood가 conjugacy를 가지지 않는 다는 점이다. 대신, conditional conjugacy를 가진다.

(a) Check that likelihood & prior are not conjugate ( + Check that there is a onditional conjugacy if we use the factorization \(q(Z,\pi) = q(Z)q(\pi)\) )

• prior distribution : \(p(Z,\pi)\)
• likelihood : \(p(X,\pi \mid Z,\mu, \lambda)\)

우선, GMM의 식을 확인해보자.

\[p(X,Z,\pi \mid \mu, \lambda ) = Dir(\pi \mid \alpha) \prod_{i=1}^{N} \prod_{k=1}^{K} [ \pi_k N(x_i \mid \mu_k, \lambda_k^{-1})]^{z_{ik}}\]

위 식에서, prior와 posterior는 다음과 같다.

• prior : \(p(Z,\pi) = Dir(\pi \mid \alpha) \prod_{i=1}^{N}\prod_{k=1}^{K} \pi_k^{z_{ik}}=C\prod_{k=1}^{K}[\pi_k^{\beta}\prod_{i=1}^{N}\pi_k^{z_{ik}}]\)

• posterior :
  \(\begin{align*} p(Z, \pi \mid X) \propto p(X,Z, \pi) &= Dir(\pi \mid \alpha) \prod_{i=1}^{N} \prod_{k=1}^{K} [ \pi_k N(x_i \mid \mu_k, \lambda_k^{-1})]^{z_{ik}} \\ &= C'\prod_{k=1}^{K}[\pi_k^{\beta'}\prod_{i=1}^{N}\pi_k^{z_{ik}}\gamma^{z_{ik}}]\\ \end{align*}\)

따라서, 우리는 likelihood과 prior가 서로 conjugate하지 않음을 알 수 있다.

하지만, 여기서 만약 우리가 \(Z\)를 고정시킨다면, 다음과 같이 서로 conjugate함을 확인할 수 있다. ( Conditional Conjugate )

• prior : \(p(Z,\pi) = C\prod_{k=1}^{K}[\pi_k^{\beta}\prod_{i=1}^{N}\pi_k^{z_{ik}}] = C \prod_{k=1}^{K}\pi_k^{\psi}\)
• posterior : \(p(Z, \pi \mid X) \propto C'\prod_{k=1}^{K}[\pi_k^{\beta'}\prod_{i=1}^{N}\pi_k^{z_{ik}}\gamma^{z_{ik}}] = C^{''}\prod_{k=1}^{K}\pi_k^{\psi'}\)

반대로, 여기서 \(\pi\)로 고정 시킬 경우, 다음과 같이 마찬가지로 서로 conjuagte함을 확인할 수 있다.

• prior : \(p(Z,\pi) = C\prod_{k=1}^{K}[\pi_k^{\beta}\prod_{i=1}^{N}\pi_k^{z_{ik}}] = C \prod_{k=1}^{K}\prod_{i=1}^{N}\xi^{z_{ik}}\)
• posterior : \(p(Z, \pi \mid X) \propto C'\prod_{k=1}^{K}[\pi_k^{\beta'}\prod_{i=1}^{N}\pi_k^{z_{ik}}\gamma^{z_{ik}}] = C^{''}\prod_{k=1}^{K}\prod_{i=1}^{N}\xi{'z_{ik}}\)

결론 : Conditional Conjugacy ( \(q(Z,\pi) = q(Z)q(\pi)\) )

(b) E-step : write down update rules for \(q(Z)\) and \(q(\pi)\)

(a)에서 구한 것 처럼, 우리는 Mean Field Approximation을 사용하여 문제를 해결할 것이다.

즉, 다음과 같이 근사하는 함수 \(q\)를 찾아낼 것이다.

Approximation : \(p(Z,\pi \mid X, \mu, \lambda) \approx q(Z,\pi) = q(Z)q(\pi)\)

그리고 Variational Inference의 Update rule을 다시 생각해보자. 그 Updating equation은 다음과 같음을 우리는 저번 포스트에서 공부했었다

\(log\;q_j(\theta_j) = E_{q_{i\neq j}}logp(X,\theta) + Const\) ( 여기서 \(\theta\) = \((Z,\pi)\) 이다)

(1) \(q(Z)\) 에 대한 updating equation

\[\begin{align*} logq(Z) &= E_{q(\pi)}logp(X,Z,\pi) + Const \\ &= E_{q(\pi)}[\sum_{i=1}^{N} \sum_{k=1}^{K}z_{ik}(log\pi_k + logN(x_i \mid \mu_k, \lambda_k^{-1}))] + Const \\ &= \sum_{i=1}^{N} \sum_{k=1}^{K}z_{ik}(E_{q(\pi)}log\pi_k + logN(x_i \mid \mu_k, \lambda_k^{-1})) + Const\\ &=\sum_{i=1}^{N} \sum_{k=1}^{K}z_{ik}log\rho_{ik} + Const \end{align*}\]

\(q(Z) = \prod_{i=1}^{N}q(z_i)\) 으로 factorize 되므로, \(q(z_i)\) 는 다음과 같이 된다.

정답 : \(q(z_i) = \frac{\prod_{k=1}^{K}\rho_{ik}^{z_{ik}}}{\sum_{k=1}^{K}\rho_{ik}}\)

(2) \(q(\pi)\) 에 대한 updating equation

\[\begin{align*} logq(\pi) &= E_{q(Z)}logp(X,Z,\pi) + Const \\ &= E_{q(Z)}[\sum_{k=1}^{K}(\alpha_k -1) log\pi_k + \sum_{i=1}^{N}\sum_{k=1}^{K}z_{ik}log\pi_k] + Const\\ &= \sum_{k=1}^{K}(\alpha_k-1)log\pi_k + \sum_{i=1}^{N}\sum_{k=1}^{K}[E_{q(Z)}z_{ik}]log\pi_k + Const\\ &=\sum_{k=1}^{K}log\pi_k(\alpha_k -1 + \sum_{i=1}^{N}E_{q(Z)}z_{ik}) + Const \end{align*}\]

따라서, \(q(\pi)\) 는 \(\alpha_k' = \alpha_k + \sum_{i=1}^{N}E_{q(Z)}z_{ik}\) 인 \(Dir(\pi \mid \alpha')\) 이다.

정답 : \(q(\pi) = Dir(\pi \mid \alpha')\)

(c) M-step : compute optimal values of \(\mu, \lambda\) by maximizing \(E_{p(Z, \pi \mid X, \mu, \lambda)} log\;p(X,Z ,\pi \mid \mu, \lambda)\)

M-step에서는 parameter \(\mu\)와 \(\lambda\)를 update한다. 따라서, \(E_{q(Z,\pi \mid X)}logp(X,Z,\pi)\) 를 \(\mu\)와 \(\lambda\)에 대한 함수로 다시 쓴다. 구체적인 내용은 생략 ( 1-(c)와 같이 유사한 방식으로 풀면 된다 )

그렇게 하면, 우리는 다음과 같은 updating parameter값을 얻게 된다.

\[\mu_k = \frac{\sum_{i=1}^{N}\gamma_{ik}x_i}{\sum_{i=1}^{N}\gamma_{ik}}\] \[\lambda_k = \frac{\sum_{i=1}^{N}\gamma_{ik}}{\sum_{i=1}^{N}\gamma_{ik}(x_i - \mu_k)^2}\]