EM Algorithm

latent variable 추론

clustering과 classification의 가장 큰 차이점은 숨어있는 변수가 있느냐 없느냐이다.
clustering은 latent variable이 포함되어 있다
classification은 observed variable로 분류 한다

• $\{ X, Z\}$ : 모든 variable

• $X$ : 관측된(Observed) variable

• $Z$ : hidden(latent) Variable

• $\theta$ : 분포 parameter

latent variable을 marginal out 해주면 된다

$$P(X \mid \theta) = \sum_z P(X,Z \mid \theta)$$

로그 속에 summation이 있으면 계산이 복잡해져서 결국에는 summation의 위치를 바꿔줘야 한다(Jensens’s inequality). 그리고 $q(z)$의 임의의 pdf를 넣어준다

$$\ln P(X \mid \theta) = \ln \left\{ \sum_z P(X,Z \mid \theta)\right\}$$ $$l(\theta) = \ln P(X \mid \theta) = \ln \left\{ \sum_z q(z)\frac{P(X,Z \mid \theta)}{q(z)} \right\}$$

CF) Jensen’s inequality

• $\psi$가 convex function일때는

$$f \left( \frac{x+y}{2}\right) \leq \frac{f(x) + f(y)}{2}$$ $$\psi\left( \frac{\sum a_i x_i}{\sum a_j} \right) \leq \frac{\sum a_i \psi (x_i)}{\sum a_j}$$

• $\psi$가 concave function일때는

$$f \left( \frac{x+y}{2}\right) \geq \frac{f(x) + f(y)}{2}$$ $$\psi\left( \frac{\sum a_i x_i}{\sum a_j} \right) \geq \frac{\sum a_i \psi (x_i)}{\sum a_j}$$

로그는 Concave function이므로 jensen’s inequality에 의해 다음과 같이 로그 속의 summation을 다음과 같이 빼서 식을 정리할수 있다

$$l(\theta) = \ln \left\{ \sum_z q(z)\frac{P(X,Z \mid \theta)}{q(z)} \right\} \geq \sum_z q(z) \ln \frac{P(X,Z \mid \theta)}{q(z)}$$

오른쪽항의 식을 정리해주면

$$\sum_z \left\{q(z) \ln P(X,Z \mid \theta) - q(z)\ln q(z) \right\}$$

첫번째 항은 $q(z)$의 가중평균이고 두번째 항은 $q(z)$가 확률분포라는 가정하에 엔트로피를 나타낸다. 따라서 다음과 같이 식을 notation 해줄 수 있다

$$Q(\theta, q) = E_{q(z)} \ln P(X,Z \mid \theta) + H(q)$$

$Q(\theta, q)$은 결국 $l(\theta)$의 lower bound이다 이것을 최대화 시켜주면 $l(\theta)$값도 같이 최대화 시켜줄수 있다는 것이다
단 항상 그런것은 아니다 왜냐하면 서로 inequality하기 때문이다

Maximizing lower bound(1) $$l(\theta) \geq \sum_z q(z) \ln \frac{P(X,Z \mid \theta)}{q(z)} = \sum_z q(z) \ln \frac{P(Z \mid X, \theta)P(X \mid \theta)}{q(z)}$$

맨 오른쪽의 항을 다음과 같이 정리할수 있다

$$\sum_z \left\{q(z) \ln \frac{P(Z \mid X, \theta)}{q(z)} + q(z)\ln P(X \mid \theta) \right\}$$ $$=\sum_z \left\{q(z) \ln \frac{P(Z \mid X, \theta)}{q(z)}\right\} + \ln P(X \mid \theta)$$

다음을 최적화 시키기 위한 식으로 바꿔주기 위해 summation 속의 로그를 역수로 취해줌으로써 Kullback-Leiber divergence로 변형 시켜준다

$$L(\theta, q) = \ln P(X \mid \theta) - \sum_z \left\{ q(z) \ln \frac{q(z)}{P(Z \mid X, \theta)} \right\}$$

이 식을 보면 많은 뜻을 볼수 있다 기존의 우리가 maximize시키고 싶었던 $\ln P(X \mid \theta)$에 KL divergence term을 빼주는 식이 되었다 즉 KL divergence term을 0에 가깝게 해주면 해줄수록 우리의 objective function에 가까워 진다
KL divergence term이 0에 가까워 진다는 것은 $q(z)$ 분포 모양과 $P(Z \mid X, \theta)$의 분포 모양이 비슷해 진다는 것을 의미한다

Maximizing lower bound(2) $$Q(\theta, q) = E_{q(z)} \ln P(X,Z \mid \theta) + H(q)$$ $$L(\theta, q) = \ln P(X \mid \theta) - \sum_z \left\{ q(z) \ln \frac{q(z)}{P(Z \mid X, \theta)} \right\}$$

우리가 $L(\theta, q)$를 구한 이유는
우리가 제일 처음 구한 $Q(\theta, q)$만 가지고 optimal value를 구하는 것은 쉽지 않다. 왜냐하면 $q(z)$를 업데이트하는 방법에 대한 정확한 지식이 없기 때문이다
하지만 $L(\theta, q)$를 가지고 $q(z)$를 업데이트 하기는 쉽다 임의의 $\theta$에 대해 $q(z)$는 $P(Z \mid X, \theta)$의 분포와 비슷하게 Update해주면 된다

$$KL\left(q(Z) \lVert P(Z \mid X, \theta)\right) = 0 \to q^t(z) = P(Z \mid X, \theta^t)$$

특정한 iteration동안 $\theta^t$로 되면 $q^t(z)$로 업그레이드 된다

$$Q(\theta, q^t) = E_{q^t(z)} \ln P(X,Z \mid \theta^t) + H(q^t)$$ $$\theta^{t+1} = argmax_{\theta}Q(\theta, q^t) = argmax_{\theta}E_{q^t(z)} \ln P(X,Z \mid \theta)$$

그러면 업그레이드 된 $q^t$를 가지고 다시 $\theta$를 업그레이드 해준다

정리 $$P(X \mid \theta) = \sum_z P(X,Z \mid \theta)$$ 1. EM 알고리즘은 latent variable이 포함된 maximum likelihood를 찾는것이다
2. 처음에는 $\theta$를 랜덤으로 정해준다
3. likelihood가 converge할때 까지 iteration을 돌려준다