EM algorithm(PRML/cs229)

Pattern Recognition and Machine Learning 책과 웹의 여러 소스에서 EM 부분을 정리.

그리고 앤드류응 교수님이 cs229에서 설명해주신 친절한 직관도 같이 정리했다.

이 직관적 설명이 참 좋다. E step이 constructing lower bound / M step이 optimizing lower bound라는 것.

내 직관을 좀 더해보자면, stochastic gradient descent와 비교해서 바라보자면, constructing lower bound부분이 어떤 지점에서의 방향을 설정하고(SGD에서 미분값), optimizing을 통해 조금 나아가는 정도? 멋져멋져

PRML책에서의 해당 부분을 정리해보았다. 여기에 모두 기록하진 않았지만 카이스트 강의자료가 PRML을 토대로 많이 작성된 느낌이다.

200613

each x에 대한 z를 모르기 때문에 p(x, z)를 구할 수 없다는 접근 캬하.

E step : evaluating p(z|x, theta)

M step : evaluating theta

캬하.

또 다른 어프로치.

200633

Likelihood가 Lower bound와 KL-divergence의 합으로 넘어가는 부분의 derivation을 이 노트에는 정리하지 않았다. (사실 이전 GMM노트와 VI 노트에서 정리를 했다.)

잠깐 체크하고 넘어가고 싶은 부분은 ln(p|theta)의 inequality 전개해서 두가지 꼴을 만들어 볼 수 있고 각각의 직관도 재미있다는 점이다.

  1. ln P(x|theta) >= E[ ln P(x, z|theat) ] + H[Q] 꼴
  2. ln P(x|theta) >= ln P(x|theta) + KL-divergence(Q||P) 꼴

여기서는 이 중 2번 꼴을 사용하는 것으로 정리된 것이다.

이젠 조금 다른 시각의 다음 노트를 보자. 앤드류 교수님이 cs229에서 EM의 개념을 rough하게 그래프로 그려주셨다.

모델을 maximum(물론 local일 수도 있지만..)으로 보내기 위해 매 iteration마다  한땀 한땀 lower bound 최적화를 통해 열심히 가는 것이다.

lower bound를 정의한다는 것은 z 혼자에 대한 확률함수 Q를 정의한 후 이것을 이용해서 joint p(x, z)에 대한 lower bound를 정의한다는 것이다.

매력덩어리인 요 some Q를 사용한다는 것 – 좀 다르지만 sampling-based inference에서도 비슷한 개념이 주구장창 사용된다. 머신러닝 넘나 잼나는거.

여기선 Q를 사용하면서 Expectation 꼴을 도출할 수 있고 Jensen’s inequality도 사용하게 됨과 동시에 라그랑쥬로 lower bound를 정의할 수 있는 신의 한수인 셈이다.

200641.JPG

200650

이제 P(x(i), z(i) ; theata) / Qi(z(i))라는 녀석으로 정리가 되었다.

(-> 요녀석의 Q에 대한 expectation이 위 카이스트 강의에서의 L(Q, theta) 부분이다. 우리가 Q를 넣는 신의 한수로 도출한 derivation의 핵심. 이걸 maximize하는 것이 )

(물론 샘플이 많아야 저 부분이 expectation이 된다. 언제나 law of large number 같은 애들은 기본옵션으로 가정한다. Capture 근데 아니었다! 여기서는 모든 z에 대해 sum하기 때문에 그냥 expectation으로 치환될 수 있다. 물론 잠깐 expectation으로 들어갔다가 lower bound만 만들고 바로 나오긴 한다.)

요기서 가장 중요한 포인트.

P(x(i), z(i); theata) / Qi(z(i)) 가 some constant value (for all z(i)’s)가 되는 true distribution Qi(z(i))을 찾는 것이 우리가 원하는 것이라는 부분. Jensen’s inequality에서 equality가 되는 경우 중 하나를 대입한 것이다. (함수 안의 random variable이 degenerate되어 constant가 되는 경우)

j1

(https://en.wikipedia.org/wiki/Jensen%27s_inequality)

그래서 어떤 z(i)가 들어오건 상관없이 constant한 값을 내어주는 P(x(i), z(i); theata) / Qi(z(i))가 우리가 원하는 아이인 것이다. 즉, P(x(i), z(i); theata) / Qi(z(i)) 일정한 ratio인 경우인 셈.

그래서 분모 분자가 비례하도록 설정하는 단계로 넘어가는 것이고, 이를 통해 theta를 구하는 것이 바로 M step.

또한 E step 은 애초에 Q(i)(z(i))가 z(i)에 대한 확률 분포이기 때문에 저렇게 정의될 수 있었고, 두가지 스텝을 번갈아 하는 그림이 그려진 것이다.

당신은 EM을 깨우쳤다!

Jensen’s inequality를 본 김에 information theory에 적용하는 부분도 살짝 보고 넘어가도 좋다. RBM, VI 등 에서 어짜피 볼 거기 때문에 아하하..

Info theory의 핵심 역할을 하는 KL divergence를 Jensen’s inequality를 사용해서 도출한다. (KL이 0이 되는 것이 p와 q가 같아지는 지점인 것.)

j2

(https://en.wikipedia.org/wiki/Jensen%27s_inequality)

자, GMM으로 넘어가자.

Constructing lower bound 부분이 GMM에서 말하자면 현재 파라메타에 대해 latent z들의 maximum likely한 assigning이 되는 것.

200659200708

아래 강의 자료와 강의 영상을 보면 더욱 쉽게 이해할 수 있다. (강의 54분 정도부터)

시간이 나믄 cs229 한번 쭈루루룩 다시 여행을 떠나고 싶다. 응교수님 사랑해요!

http://cs229.stanford.edu/notes/cs229-notes8.pdf

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s