[ML Study] GMM + EM Algorithm

1. Detour

convex

Image from wekipidia

f''(X) >= 0일 때, function f는 convex(아래로 볼록) 증명.

MLE에서 위로 볼록임을 증명할 때(concave) f''(x) <= 0을 사용하는 것도 같음.

 

Jensen's Inequality

2. EM algorithm as MLE

log likelihood는 datapoint x, parameter 세타에대해 다음과 같이 나타낼 수 있다.

 

즉, GMM과 같이 datapoint 1개에 대한 latent variable을 구한 후 전체 n개의 datapoint에 해대 log likelihood를 줄 것이다.

(latent variable z를 모르기에 z를 merge한 값을 바탕으로 log likelihood 구한다.)

log likelihood 직접 미분 x

latent variable에 대한 값은 모르기때문에 MLE를 직접 구할 수 없다(log likelihood를 직접 미분할 수 없다.)

그렇기에 아래 그림과 같은 순서로 E,M알고리즘을 순회하면 local maximam으로 최적화한다.

이때, 새로 만든 L(세타)는 lower bound property와 tight property가 만족되어야 한다.

그리고 최적화도 쉽다고 가정한다.

다시한번 설명하면 위의 그림과 같다.

 

Creating curve L(Theta)

최적화를 위해 L(세타)를 구하기 위해서는 Jensens’s를 위해서 구한다.

먼저, likelihood log p(x)를 optimizing을 하고, 그리고 모든 n example에 대해 구할 수 있는 방향으로 가본다. 8장에서 말한거처럼 p(x)먼저 구하는 것이다.

P(x)에 대해 하기 위해서는, 아까 말한 latent variable z에 대해 합치는 방향으로 하고, Q(Z)를 대입한다. Q(Z)는 다음과 같은 조건을 만족해야 한다.그럼 이떄 Q(z)의 합이 1이란 조건에 의해 다음과 같이 Z를 distributed like Q라고 하고, Jensen’s inequality를 바탕으로 다음과 같이 변환시킬 수 있다.

(여기서 concave이기 때문에 우리가 처음 배운것과 반대로)

 

여기서 위의 "z ∼ Q" 첨자는 기대치가 Q에서 도출된 z에 대한 것임을 나타낸다.

즉, Q를 선택함에 따라 log(p에 대한 lower bounding을 찾을 수 있고, 이는 construct the curve를 뒤에 찾는 것을 알 수 있다.

여기서는 이걸 만족하는 Q가 많다.

 

logp(x;θ)의 하한을 구할 때 (low boundry) Q를 어떻게 구해야 할까? 

특정 θ 값에 대해 하한을 엄격하게 만들려면 위의 유도에서 젠슨의 부등식을 포함하는 단계가 등식으로 유지되어야 합니다.

Q가 log(x:세타)의 하한을 준다.

앞선 이 식에서, 안에가 constant 하면 expectation은 관계가 없어진다. 즉, tight property를 위해서는 constant한 Q를 해서 maximize 해야한다.

그러면 다음과 같이 나타낼 수 있고, 그렇기에 l저기 c가되는 Q를 구해야 한다.

P(x,z;세타)는 다음과 같이 풀수있기에 Q, c는 다음과 같이 구할 수 있다.

또한, Q(Z)는 세타와 x에 의존하지 않는다. 그렇기에 모든 datapoint x에 대해 다른 Q가 생긴다.

Evidence Based Lower Bound(ELBO)

ELBO의 정의는 위의 하이라이트한 것과 같다.

이때 앞에서 log likelihood가 크거나 같은 값이 ELBO임을 알 수 있고, 이를 바탕으로 이를 만족하는 Q 분포를 찾아야 한다(lower bound). 그리고, ELBO를 maximize해서 l(세타)와 동일하게 만들어서 Tight property도 만족하도록 해야한다.

 

ELOB는 추정 확률의 log likelihood의 lower bound를 제공한다.

즉, Maximizing ELBO를 통해 posterior distribution(datapoint를 바탕으로 parameter 예측 확률)을 근사할 수 있다.

(우선, Variational Inference에서 사후 분포를 근사화하기 위해, 근사 분포를 선택한다. ELBO는 이 근사 분포를 사용하여 원래의 사후 분포를 근사화하는데 사용되는 목적함수이다.. 즉, ELBO를 최대화함으로써 우리는 원래의 사후 분포를 근사화하는데 사용되는 근사분포를 찾을 수 있다.)

 

 

ELBO는 EM 알고리즘 말고도 VAE와 같은 알고리즘에서도 사용이 가능하다.

Summary

즉, 현재 model parameter 세타를 바탕으로 각각의 data points x가 속할 cluster z의 probability 추정 후, 각각의 데이터 포인트에 대해 potential variable z probability distribution을 구한다. 다시 말하면, 우리가 가지고 있는 세타와, 데이터포인트들로 Q(i) distribution을 선택하라는 것. 앞에서 Qi를 바탕으로 lower bound를 구하고, EM alogrithm을 최적화 할 수 있다고 배웠다.

 

M step은 모델 파라미터를 1번에서 구한 Q distribution을 바탕으로 Lt(세타)를 최대화하도록 업데이트한다.

 

이를 계속 반복해서 파라미터를 최적화한다.

 

 

GMM에서 EM Alog를 쓰는 과정을 다시 보면 다음과 같다.

GMM의 log likelihood는 latent variable이 있어 미분을 못하기 때문에 Q를 만들어서 expectation step을 진행한다.

그리고, ELBO로 하한을 구하기 위해 ELBO 식을 초록색과 같이 모든 데이터포인트 1부터 n까지 진행해 식을 만든다.

이렇게 만든 식을 위로 볼록한 그냥 L(세타)이기 때문에 non latent variable인 평균, 분산, z의 확률(multinomial)을 바탕으로 저 ELBO식을 미분해 0이 나오는 값을 찾으면 된다.

평균에 대해서만 진행해보면

다음과 같이 나온다.

이미지 출처

https://angeloyeo.github.io/2021/02/08/GMM_and_EM.html

GMM과 EM 알고리즘 - 공돌이의 수학정리노트 (Angelo's Math Notes)

https://www.wikipedia.org/

Wikipedia, the free encyclopedia