EM Algorithms

참고 블로그 

- http://sanghyukchun.github.io/70/

Machine learning 스터디 (14) EM algorithm - README

 

EM Algorithms

 

E : Expectation

M: Maximization

으로 기대치를 최대화 하는 알고리즘인데

 

EM알고리즘은 MLE, MAP와 달리

latent variable이 존재하는 probabilistic model에 대한 

문제를 해결하기 위해 사용되는 알고리즘이다.

 

즉 MLE, MAP와 달리 Unsupervised Learning에서 사용되는 

알고리즘으로 K-means, HMM, GMM 등에 많이 사용된다.

 

 

여기서 EM 무엇을 기대치 하는 알고리즘인지

영화추천 시스템을 예시로 한번 들여다 보자.

 

영화 추천 시스템은 기존 고객들이 사용한 정보를

토대로 새로운 영화나 기존 영화들을 추천하는 시스템이다.

 

이 과정을 자세히 들여다보면

기존 정보를 토대로 새로운 영화를 추천하는 것을

Expectation 단계라 볼수 있고

그 이후 추천한 영화에 대한 만족도를 기반으로

다시 정보를 업데이트 시키느 과정이

Maximization 단계라고 볼 수 있다.

 

즉 위와 같은 과정을 반복해서 수행하다 보면

점점 고객에게 딱 맞는 영화를 추천해줄 수 있는

확률이 높아지게 되면서 "converge" 상태에 다다르게 되는 것이다.

 

즉 EM알고리즘의 목표는 반복적인 학습을 통해 

정답이 없는 데이터에 대해 분류(예측)을 하는 작업이라고 볼 수 있다,

 

 

What's the different with MLE, MAP?

 

 

위에 EM 알고리즘과 MLE, MAP와 유사해 보이지만

다른 알고리즘이라고 언급을 했는데

어떤 차이점이 있는지 자세히 알아보자.

 

 

1) Iterative한 방식

 

EM알고리즘은 MLE, MAP와 같이

직접 최적 파라미터를 구하는 방식이 아닌

E-step, M-step을 반복하는 

Iterative한 방식으로 파라미터를 점차적으로

최적화 시키는 모습을 가진다.

+ 미분이 복잡한 모델에 대한 MLE,MAP의 한계점을 극복

 

2) Random variable 정의

 

MLE에 경우 observation에 의존해 

파라미터를 구한다면 EM은 구하고자한 

파라미터의 함수에 대해 Random variable을 정의해 

이에 대해 최적화를 수행한다.

 

 

MLE, EM에 대한 심화 질문 

-> MLE 로 구한 파라미터 결과값과 EM으로 구한 파라미터의 결과 값은 다를까?

(HINT : Global optima, Local optima)

 

결론부터 말하자면 다르다

EM 알고리즘은 초기값을 스스로 정한 상태에서 

Random variable도 고려 하는 과정이기 때문에

초기값에 따라 최종 결과가 달라지기 때문에 

Local Optim이다.

 

반변에 MLE는 Observation에 의존해 

파라미터를 구하기 때문에 

Global Optima을 찾을 수 있다.

 

 

 

 

Latent variable이 존재하는 EM Algorithms

 

EM 알고리즘에 대해 다루기 전에 먼저 latent variable을 가지고 있는

probabilistic model에 대해 설명하도록 하겠다.

 

Latent variable은 우리가 본래 가지고 있는 random variable이 아닌,

우리가 임의로 설정한 hidden variable을 의미한다.

 

예를 들어, 아래 그림과 같은 Grapical model을 고려해보자.

이때 우리가 관측할 수 있는 random variable은

paramter θ로 parameterized 되어있는 X 하나이고, 

Z은 우리가 관측할 수 없는 hidden variable이라고 해보자.

 

 

 

source - https://blog.evjang.com/2016/08/

 

X의 maximum likelihood를 계산하고 싶다면 어떻게 해야할까?

먼저 X의 maximum likelihood는 다음과 같이 표현된다.

 

위의 식에서 Z는 discrete variable이라고 정의

(계산의 용이성을 위해)

이 문제에서 가정할 것이 하나있다.

바로 marginal distribution p(X|θ)p(X|θ)를

직접 계산하는 것이 매우 까다롭다는 것이다.

이때, Z는 임의로 정할 수 있는 latent variable이기 때문에,

joint distribution p(X,Z|θ)p(X,Z|θ)가 marginal distribution보다

쉬운 Z를 잡는 것이 가능하다.

 

 

이 과정은 Jensen's inequality라는 정의를 참고 바란다.

- https://ko.wikipedia.org/wiki/%EC%98%8C%EC%84%BC_%EB%B6%80%EB%93%B1%EC%8B%9D

옌센 부등식 - 위키백과, 우리 모두의 백과사전

만약 우리가 latent variable Z의 marginal distribution을 

q(Z)라고 정의한다면, 앞에서 설명한 log-likelihood를

위 식의 결과값인 다음과 같이 Decompose 할 수 있다.

 

위의 식에서 L(q,θ)는 hidden variable Z의

marginal distribution q(Z)의 functional이다.

 

그리고 KL(q∥p)는 q,p의 KL divergence를 의미하게되고

위와 같이 log-likelihood를 decompose하게 되면,

한 쪽에는 random variable X,Z의 joint distribution,

그리고 또 한 쪽은 conditional distribution으로 표현이 된다는 것을 알 수 있다.

 

https://icim.nims.re.kr/post/easyMath/550

Entropy, Cross-entropy, KL Divergence | 알기 쉬운 산업수학 | 산업수학혁신센터

 

또한 KL divergence의 특성에서부터 재미있는 사실을 하나 더 유추할 수 있는데,

바로 KL divergence가 반드시 0보다 크거나 같기 때문에 

L(q,θ)이 곧 log-likelihood의 lower bound가 된다는 사실이다.

이를 그림으로 나타내면 아래 그림의 오른쪽 그림과 같다.

 

 

 

 

EM Algorithms

 

lower bound가 maximum이 되도록하는 θ와 q(Z)의 값을 찾고,

그에 해당하는 log-likelihood의 값을 찾는 알고리즘을 설계하는 것이 가능할 것이다.

 

만약 θ와 q(Z)를 jointly optimize하는 문제가 어려운 문제라면

이 문제를 해결하는 가장 간단한 방법은 둘 중

한 variable을 고정해두고 나머지를 update한 다음,

나머지 variable을 같은 방식으로 update하는 alternating method일 것이다.

EM 알고리즘은 이런 아이디어에서부터 시작하게 된다.

EM 알고리즘은 E-step과 M-step 두 가지 단계로 구성된다.

각각의 step에서는 앞서 설명한 방법처럼 θ와 q(Z)를 번갈아가면서

한 쪽은 고정한채 나머지를 update한다.

 

이런 alternating update method는 한 번에 수렴하지 않기 때문에,

EM 알고리즘은 E-step과 M-step을 알고리즘이

수렴할 때 까지 반복하는 iterative 알고리즘이 된다.

 

 

 

그리고 위 그림처럼 

Log-likelihood를 decompose한 식인

L, KL은 상보적이라는 결과를 활용해 

EM Algorithms에 E-step, M-step을

들여다 보자.

 

E-step

 

E-step은 먼저 θold 값을 고정해두고 

L(q,θ)의 값을 최대로 만드는q(Z)의 값을 찾는 과정이다.

 

이 과정은 매우 간단하게 계산 수 있는데,

그 이유는 log-likelihood ln⁡p(X|θold)의 값이 q(Z) 값과 전혀 관계가 없기 때문에,

항상 L(q,θ)를 최대로 만드는 조건은 KL divergence가 0이 되는 상황이기 때문이다.

 

KL divergence는 q(Z)=p(Z|X,θold) 인 상황에서 0이 되기 때문에, 

q(Z)에 posterior distribution p(Z|X,θold)을 대입하는 것으로 해결할 수 있다.

따라서 E-step은 언제나 KL-divergence를 0으로 만들고,

lower bound와 likelihood의 값을 일치시키는 과정이 된다.

 

즉 정리해보면 미리 정해둔 θold을 기반으로

Z에 대한 분포를 계산하는 과정이다.(or sampling)

 

 

M-step

E-step에서 θold을 고정하고 q(Z)에 대한 optimization 문제를 풀었으므로

M-step에서는 그 반대로, q(Z)를 고정하고

log-likelihood를 가장 크게 만드는 새 parameter θnew을

찾는 optimization 문제를 푸는 단계가 된다.

 

E-step에서는 update하는 variable과 log-likelihood가

서로 무관했기 때문에 log-likelihood가 증가하지 않았지만,

M-step에서는 θ가 log-likelihood에 직접 영향을 미치기 때문에

log-likelihood 자체가 증가하게 된다.

 

 

즉 구한 Z을 기반으로 다시 반복해서 데이터와 

비교하는 과정이기 때문에  θ가 업데이트가 되면서

Log-likelihood 자체가 증가하기 되는 것이다.

 

 

E-step, M-step

 

 

E-step을 의미하는 위에 그림에서 KL divergence는 0이 되고,

lower bound인 functional과 log-likelihood의 값이 같아진다.

 

M-step을 표현하고 있으며, θ가 update되면서

log-likelihood의 값이 증가하게 되지만,

더 이상 KL divergence의 값이 0이 아니게 된다.

 

이 과정을 더 이상 값이 변화하지 않을 때(const가 생성되지 않을때)까지

충분히 많이 돌리게 되면 이 값은 log-likelihood의 어떤 값으로 수렴하게 될 것이다.

그리고 매 step마다 항상 optimal한 값으로 진행하기 때문에

이 값은 log-likelihood의 local optimum으로 수렴하게 된다는 사실을 알 수 있다.

(Global optimum x)

source - http://sanghyukchun.github.io/70/

 

E-step, M-step 의 요약

 

 

 Iterative 하게 MLE 수행  파라메터 초기값 θold

 

1) E-step
 θold 에서 log-likelihood와 최대한 근사한 L (파란색) 얻음

 

2) M-step
 L을 최대화하는 θnew 얻음

 

3)  E-step
 θnew 로부터 L (초록색) 을 새로 얻음

 

4) …위의 E-M 스텝 반복을 수렴할 때까지 반복

 

+ M-step에서 θold가 θnew로 바뀌었기 때문에 E-step에서 구했던 

p(Z)로는 더 이상 KL-divergence가 0이 되지 않고 

M-step을 통해 θnew가 되면서 Log-likelihood 자체가 커지게 되고

(이때는 KL-divergence != 0)

따라서 다시 E-step을 진행시켜 KL-divergence를 0으로 만들고,

log-likelihood의 값을 M-step을 통해 키우는 과정을 계속 반복 해야만 한다.