Week 8.8 Fundamentals of the EM Algorithm

EM 이 어떻게 돌아가는지 알아보자.

Latent variable 의 유무가 classification 과 clustering 의 차이를 나타낸다.

classification 은 Z라는것이 없고 X, Θ 와의 관계만 있고, X는 아는것이고 Θ는 모르는것이었기 때문에, X를 이용해 Θ를 구하면 된다. [Θ= X를이용한어떠한수식]을 만들어 주면 충분히 문제가 풀렸다.

 

Clustering은 Z 라는 hidden variable 이 들어왔다. [Θ = X,Z 를 이용한 어떠한 수식] 을 만들어 진다해도 모르는 Z가 들어왔다. 그러면 Z를 어떻게 하면 좋을까라는 고민을 하는것이 Unspervised leraning ( Clustering )에서는 필요하다.

 

classification 에서는 Z 가 없기 때문에 , Z에 대한 marginalization 할 필요가 없었다.

예) lnP(X|Θ) => summation 도 필요없다.

하지만 clustering 에서는 ln{ΣzP(X,Z|Θ)} 의 꼴에 marginalization , summation 이 들어오게 된다. 여기서 문제는 z에 대해 summation 할때 log 밖에 있는것은 좋은것인데, log 안에서 summation 을 해야하기 때문에 계산이 복잡하다.

 

그래서 EM을 통해 optimize를 하게되고 , X,Z term 들끼리 optimize 하는 과정에서 interaction 이 존재하게 된다.

 

Jensen's Inequality

 

로그함수는 concave 하다.

 

위의 lnP(X|Θ) 를 Jensen's inequality를 이용하기 위해 q(Z) 라는 term 을 곱하고 나누었다.

여기서 Jensen's inequality 의 공식을 이용하면 q(Z)는 a이고 P(X,Z|Θ)/q(Z)는x의 부분이다.

그래서 결국 

위의 형태의 식이 된다. 그리고 뒤쪽의 빼기 항 부분은 엔트로피와 유사한 형태이다. 하지만 엔트로피이기 위해서는 q가 확률밀도 함수 이어야하는 제약조건이 있다. 

 

위의 식은 최종적으로 Expectation 과 엔트로피의 합의 꼴로 나타낼수 있다. 

그리고 Jensen's inequality를 이용하였기 때문에 Maximize 하는것이 (Lower bound를 올려주는것) 원래의 lnP(X|Θ) 가 optimize 하는데 도움이 된다는 내용이다.  즉 뒤의 q함수를 optimize 하게 되는 내용이다.