Week 8.9 Derivation of EM Algorithm

앞에 생성된 ln𝑃(𝑋|𝜃)와 밑에 정의된 , L(𝜃, q) 와의 관계를 보면 

위의 식을 빼주는것의 관계이다. 이 식은 inequality 를 만들게되는 근원이었다. 근원(factor 로 작용)을 없애 버리면 lower bounnd 가 타이트하게 붙어지면서 equility 되 버린다.

그러면 이 근원을 어떻게 없앨수 있을까?

이 근원은 KL divergence 와 매우 유사한 형태이다. 두확률분포의 유사도를 측정하는 것이다.

q(z) ,P(Z|X,𝜃) 2개 모두 확률분포이다. 2개의 확률분포가 동일해질때 위의 근원이 사라지게된다.

Non - symmetric 하다는 의미는 P관점에서 Q를 보았을때 얼마나 다르냐와 Q관점에서 P를 보았을때 얼마나 다르냐가 다를수 있다는 의미이다.

 

KL Divergence 는 확률분포간에 얼마나 차이가 나는지 측정하기위해서 만든 measure 이다. KL 이 크면 두확률간의 차이가 크다는 것이다.

 

그러면 KL divergence를 0으로 만들면 위의  근원이 사라질수 있다. 2개의 q(z) ,P(Z|X,𝜃) distribution 이 동일해지면 Lower bound 가 optimize 될수 있다. 즉 핵심은 KL divergence를 0으로 만드는 확률 분포를 q라고 생각하는것이다.

 

 

그러면 q를 어떻게 알아내야 할까?

q(z)를 P(Z|X,𝜃) 로 구성하면 된다.

z라는 것의 assignment 를 특정시간대의 특정 iteration 의 𝜃값과 , X를 받아들여 계산되는 Z의 값을 qt(Z) 라 하면 KL divergence 가 0 이 되면서 근원 부분이 사라지게 되면서 Lower bound 가 optimize 된다.

 

 

optimizing 𝜃 는 qt(Z) 를 assignment probability 처럼 받아들이겠다는 것이다.  즉 현재의 데이터 포인더(X)와 파라미터(𝜃t)를 활용해서 나온 확률값 qt(Z)  가 KL divergence=0 을 만들기위해 받아들이겠다는 내용이다.

그럼 다음 time 에서 𝜃t+1로 업데이트 해야한다. 이것은 Q를 이용해서 업데이트 하면 된다. Q를 이용해 optimize 하여  𝜃를 𝜃t+1 로 업데이트 한다.

그리고  업데이트 된 𝜃t+1 를 이용해 𝑃(𝑍|𝑋,𝜃𝑡)에 𝜃t 를 𝜃t+1로 업데이트하여 bound를 optimize하면된다.

이것을 반복하는것을 EM algorithm 이다.

 

 

KL divergence를 이용해 latent variable의 probable distribution을 알아내는것이 하나가 있고, (𝑃(𝑍|𝑋,𝜃𝑡))

𝜃t를 업데이트 하기위한 q값이 latent variable에 대한 정보가 들어오기 때문에 𝜃t를 다시 업데이트 할 수 있다.

𝜃t 업데이트하면 예전에 만족하던 KL divergence가 만족하지 않기 때문에 이걸 다시 업데이트한다.

이 과정을 반복하는것이 EM 이다.

 

EM의 큰 문제점은 local optimize에 빠질수 있기 때문에 주의해야한다. 하지만 Latent variable이 있는 경우에는 많이 사용한다.