A Conformal Prediction Approach to Explore Functional Data 구현 (1)- EM 알고리즘

 

GMM을 구현하기에 앞서 EM 알고리즘에 대해 이해할 필요가 있다. EM 알고리즘을 GMM의 parameter 추정에 사용하는 이유는 각 데이터가 어떤 Gaussian component로부터 생성되었는지를 알 수 없기 때문이다. 즉, 데이터에 대한 component label이 관측되지 않는 latent variable 형태로 존재한다.

GMM에서는 각 Gaussian component의 평균과 공분산인 $\mu_k, \Sigma_k,\pi_k$를 추정해야 하며, 각 데이터가 특정 Gaussian component에 속할 확률인 responsibility 또한 함께 계산해야 한다. 그러나 관측된 데이터만으로는 각 sample이 어느 Gaussian component에 속하는지 직접 알 수 없기 때문에 바로 likelihood를 최대화하는 것이 어렵다.

EM 알고리즘은 이러한 문제를 해결하기 위해 반복적으로 다음 과정을 수행한다. 먼저 E-step에서는 현재 parameter를 이용하여 각 데이터가 특정 Gaussian component에 속할 posterior probability, 즉 responsibility를 계산한다. 이후 M-step에서는 계산된 responsibility를 기반으로 $\mu_k,\Sigma_k,\pi_k$를 다시 업데이트한다. 이를 반복함으로써 GMM의 parameter를 점진적으로 추정할 수 있다.

EM Algorithm: E-step

Given Data:
\[
\{ X_i, z_i \} \quad \text{(latent variable \( z_i \) not observed)}
\]
\[
X_i | z_i = k \sim \mathcal{N}(\mu_k, \Sigma_k), \quad k = 1, 2, 3
\]
\[
z_i: \text{group membership (weight)}
\]

Log-likelihood:

\[
lc(\theta) = \sum_{i=1}^{n} \sum_{k=1}^{K} I(z_i = k) \left( \log \pi_k - \frac{1}{2} \log |\Sigma_k| - \frac{1}{2} (X_i - \mu_k)^T \Sigma_k^{-1} (X_i - \mu_k) \right)
\]
\[
\log \text{likelihood} = \sum_{i=1}^{n} \log \sum_{k=1}^{K} \pi_k \mathcal{N}(X_i | \mu_k, \Sigma_k)
\]

 

EM Algorithm: E-step
Objective: We don't observe $z_i$, so we compute the expected log-likelihood based on $z_i$:

\[
Q(\theta | \theta^{(t)}) = \mathbb{E}[lc(\theta) | X_i; \theta^{(t)}]
\]
\[
P(z_i = k | X_i, \theta^{(t)}) = \frac{\pi_k^{(t)} \mathcal{N}(X_i | \mu_k^{(t)}, \Sigma_k^{(t)})}{\sum_{j=1}^{K} \pi_j^{(t)} \mathcal{N}(X_i | \mu_j^{(t)}, \Sigma_j^{(t)})}
\]

Responsibility: The above probability is known as the responsibility $\tilde{w}_{ik}^{(t)}$:
\[
\tilde{w}_{ik}^{(t)} = P(z_i = k | X_i, \theta^{(t)})
\]

 

EM Algorithm: M-step with Normalized Weights

 

Update parameters:

1.  $\pi_k^{(t+1)}$:
\[
\hat{\pi}_k^{(t+1)} =  \frac{1}{n} \sum_{i=1}^{n} \tilde{w}_{ik}^{(t)}
\]

\[
\tilde{w}_{ik}^{(t)} = \frac{w_{ik}^{(t)}}{\sum_{k=1}^{K} w_{ik}^{(t)}}
\]

2.  $\mu_k^{(t+1)}$:
\[
\hat{\mu}_k^{(t+1)} =   \frac{1}{n} \sum_{i=1}^{n} \tilde{w}_{ik}^{(t)} X_i \quad \left( \sum_{i=1}^{n} \tilde{w}_{ik}^{(t)} = 1 \right)
\]

3. $\Sigma_k^{(t+1)}$:
\[
\hat{\Sigma}_k^{(t+1)} == {\sum_{i=1}^{n} \tilde{w}_{ik}^{(t)} (X_i - \hat{\mu}_k^{(t+1)})(X_i - \hat{\mu}_k^{(t+1)})^T} 
\]

Maximization step:
\[
\theta^{(t+1)} = \arg \max_{\theta} Q(\theta | \theta^{(t)})
\]
위 step으로 인해 iteration이 진행될수록 likelihood가 감소하지 않는다. 즉, EM 알고리즘은 매 iteration마다 likelihood를 증가(또는 유지)시키는 방향으로 parameter를 업데이트한다.

Proof of $\mu_k$ and $\Sigma_k$ Update

1. Proof of $\mu_k$
\[
\frac{\partial}{\partial \mu_k} \sum_{i=1}^{n} \tilde{w}_{ik}^{(t)} \left( - \frac{1}{2} (X_i - \mu_k)^T \Sigma_k^{-1} (X_i - \mu_k) \right) = 0
\]

\[
\sum_{i=1}^{n}  \tilde{w}_{ik}^{(t)} \Sigma_k^{-1} (X_i - \mu_k) = 0
\]

\[
\hat{\mu}_k^{(t+1)} = {\sum_{i=1}^{n} \tilde{w}_{ik}^{(t)} X_i} \quad \left( \sum_{i=1}^{n} \tilde{w}_{ik}^{(t)} = 1 \right)
\]

2. Proof of $\Sigma_k$:

\[
\frac{\partial}{\partial \Sigma_k} \sum_{i=1}^{n}  \tilde{w}_{ik}^{(t)} \left( - \frac{1}{2} \log |\Sigma_k| - \frac{1}{2} (X_i - \mu_k)^T \Sigma_k^{-1} (X_i - \mu_k) \right) = 0
\]

\[
\hat{\Sigma}_k^{(t+1)} ={\sum_{i=1}^{n} \tilde{w}_{ik}^{(t)} (X_i - \hat{\mu}_k^{(t+1)})(X_i - \hat{\mu}_k^{(t+1)})^T}
\]

 

위 방법들 처럼 likelihood를 업데이트 하려는 변수로 편미분하면 아래 $\pi_k$같은 경우 해가 나오지 않는다. 그 이유는 $\sum_{k=1}^{K}\pi_k=1$이라는 제약 조건이 있기 때문이다. 이런 경우 Lagrange Multiplier를 사용해 $\pi_k$를 구한다.

Lagrange Multiplier Method:

\[
\mathcal{L}(x, \lambda) = f(x) + \lambda g(x)
\]

- $f(x)$: 최적화하려는 목적 함수.
- $g(x) = 0$: 제약 조건.
- $\lambda$: 라그랑주 승수(Lagrange multiplier).

\[
\nabla f(x) + \lambda \nabla g(x) = 0
\]
\[
g(x) = 0
\]


Proof of $\pi_k$ Update using Lagrange Multiplier


3. Proof of $\pi_k$:

\[
\mathcal{L}(\pi_k, \lambda) = \sum_{i=1}^{n} \sum_{k=1}^{K}  \tilde{w}_{ik}^{(t)} \log \pi_k + \lambda \left( 1 - \sum_{k=1}^{K} \pi_k \right)
\]

\[
\frac{\partial}{\partial \pi_k} \mathcal{L}(\pi_k, \lambda) = \sum_{i=1}^{n}  \tilde{w}_{ik}^{(t)} \frac{1}{\pi_k} - \lambda = 0
\]

 

\[
\hat{\pi}_k^{(t+1)}  = \frac{1}{n} \sum_{i=1}^{n} \tilde{w}_{ik}^{(t)}
\]