EM 알고리즘 1

 

 

 

오늘부터 EM 알고리즘에 관해 이야기를 좀 해보죠.

 

 

 

EM 알고리즘을 소개한 Dempster 논문을 이해하기는 그리 쉽지 않습니다. 싶게 설명하려고 처음에 지수분포계열를 예를 들어 설명하는데 사실 통계전공이 아닌 사람은 지수분포계열 조차 잘 모르거든요.

 

 

 

하여간 통계학책에 나오는 EM 알고리즘 설명은 별로 직관적이지 않습니다. 제가 판단하기로는 Kullback-Leibler divergence로 설명한 것이 그래도 EM 알고리즘을 쉽게 이해하는 방법인 것 같습니다. Kullbak-Leibler divergence는 Kullbak number, Kullbak distance, Kullback-Leibler discrepancy라고 하기도 하는데 그냥 Kullback 거리라고 하죠. 표시는 D(f;g)로 하고요. 이건 좀 있다 설명하고요.

 

 

 

 

흔히 EM 알고리즘은 결측값(missing value)이 있는 경우, 또는 은닉변수(hidden variable, latent variable)이 있는 경우 쓴다고 되어 있습니다.

 

 

결측값의 예로는 최근 여론조사에서 20대 설문조사자가 응답하지 않는 경우 이런 경우 결측값이 되겠죠. 20대 설문자가 100명이 되어야 하는데 10명 밖에 응답하지 않았다면 90명의 응답값은 결측값이 되죠. 만약 10명 응답자의 A라는 사람의 지지율이 0.3이면 나머지 90명에 대해 A의 지지율을 0.3으로 처리하면 이건 결측값에다가 일종의 평균을 대체한 방법입니다. 이럴 경우 어떤 문제가 생길까요?

 

 

 

 

 

 

은닉변수는 흔히 방송에서 보는 모자이크 화면을 생각하면 됩니다. 원래 이미지 값은 은닉변수이고 우리가 보는 모자이크된 화면의 이미지 값은 관찰 변수에 해당하죠. 모자이크하는 방법은 간단합니다. 어떤 픽셀의 모자이크된 값은 그 픽셀의 주변 픽셀의 값을 평균 시키면 됩니다. 이건 주식 그래프에서 이동평균 시킨 것이랑 똑 같은 것입니다. 주식 그래프는 일차원 값이고 모자이크 화면은 2차원 값이라는 것에 차이가 있는 것에 불과합니다. 낮은 주파수는 통과시키고 높은 주파수(잡음, 또는 세밀한 표현 부분)는 걸려내는 기법이죠.

 

 

 

 

 

하여간 EM 알고리즘은 생각보다 간단합니다. h는 hidden, v는 visual 변수입니다.

 

 

 

 

 

E(expectation)단계: E[logf(h,v;u)|V]를 구한다.

 

M(maximization)단계: E 단계에서 구한 것을 u에 관한 함수로 보고 최대가 되는 u를 구한다.

 

 

 

 

 

이 두 단계를 어느 정도 수렴할 정도까지 계속 한다.

 

 

 

보기에 좀 어려워 보이죠. 그러나 쉽게 생각하면 또 쉽습니다. 일반 최대가능추정량(MLE) 구하는 것이랑 별 다른 것 없습니다. MLE를 구하려면

 

 

 

 

 

1단계: log 가능성함수(우도함수)를 구한다.

 

2단계: 위에서 구한 log 가능성 함수를 u에 대한 함수로 보고 최대가 되는 u를 구한다

 

 

 

 

 

 

그래서 문제는

 

 

 

1. 왜 log 가능성함수=log(f(v;u)를 구하지 않고 E[log f(v,h;u)|V)를 구하는가 하는 점이고. 이게 EM 알고리즘 이해의 핵심입니다.

 

 

 

 

2. 두 번째 반복하는 것은 실제로 어렵지 않습니다. 왜냐하면 2단계에서 통상 u(i+1)=G(u(i)) 형태, 즉 모수 u에 대한 다음 추측값은 M단계에서 대부분 공식으로 나옵니다. 그래서 다음 단계에서 다시 E단계를 하고 또 M 단계를 하고 계속 이런식으로 할 필요가 없다는 것이죠.

 

 

그래서 2번째 문제는 별 문제가 되지 않는데 첫 번째 문제에 대한 설명이 별로 직관적이지 않다는 것입니다.

 

여기서 쿨백넘버를 사용해 보죠. 주로 기계학습이나 인공지능쪽에 책에는 이 쿨백넘버를 사용하여 EM알고리즘을 설명하고 있는 것 같습니다. 하여간 일단 이건 이해를 했다고 해보죠.

 

 

그럼 다음 문제는 실제 현실에서 부딪치는 문제입니다.

 

 

 

E[log f(v,h;u)|V)는 log f(V, H;u)라는 확률변수를 H|V라는 조건부 확률에 대해 기댓값을 취하는 것입니다. 좀 어렵죠. H|V의 조건부 확률의 확률분포를 g(h|v)라고 하죠 그럼

 

 

 

 

 

 

 

 

 

 

 

가 됩니다. 여기서 f(h,v:u)는 은닉변수 h와 관찰된 변수 v의 결합밀도함수이고 g(h|v)는 관찰된 변수의 값을 조건으로 할 때 은닉변수의 조건부밀도함수(donditional distribution)입니다.

 

 

그래서 이 g(h|v)를 어떻게 구하고 f(h,v|u)를 어떻게 구하는가 하는 현실적인 문제가 등장합니다. 이건 통계 기본 이론도 알아야 하지만 현실에서의 문제를 모형으로 잘 구현할 줄도 알아야 합니다. 그냥 되지 않겠죠. 책에 나오는 예제나 수 많은 논문을 읽어봐야 실력이 늘겠죠.

 

 

 

하여간 이 문제는 차차 해보기로 하고 가장 큰 문제인 앞에서 이야기한 왜 f(v;u)를 사용하지 않고 E[log f(v,h;u)|V) 를 사용하냐는 것이죠. 이렇게 해도 log 우도함수가 최대화 될까요?

 

 

 

 

 

여기서 쿨백거리를 사용합니다. 간단히 이야기해서 log 가능성 함수를 최대화하는 u를 구하는 것이 아니고 log 가능성 함수의 하한(low bound)를 최대화하는 u를 구하는 것입니다. 하한을 최대화하면 log 가능성 함수도 최대화되지 않겠나 하는 생각이죠.

 

 

 

 

그럼 log 가능성 함수를 어떻게 구할까요. 여기서 쿨백거리를 사용합니다. 쿨백거리는 정의가

 

 

 

 

 

 

 

입니다. 여기서 f와 g는 확률밀도함수입니다.

 

 

 

그래서 이 쿨백거리는 통상 진짜 확률분포 f(x)와 어떤 확률분포 g(x)와의 거리로 해석을 합니다. 실제로 거리는 아닙니다. 왜냐하면 대칭이 성립이 안됩니다. 두 사람 A와 B와의 인간관계를 한번 생각해보죠. A는 B를 굉장히 친근하게 생각하는데 그래서 A가 생각하는 거리가 매우 짧은데 비해 B는 속으로는 A를 굉장히 싫어할 수 있습니다. 그러면 B가 생각하는 A와 B와의 거리는 매우 길 수 있습니다.

 

 

 

이 쿨백거리도 그런 거리 개념과 흡사합니다. 두 개의 분포 f와 g가 있을 때 f가 진짜 분포하고 하면 g라는 분포는 f에서 얼마나 diverge 되어 있나, 아니면 얼마나 discrepancy 한가 이런 것을 측정하는 거리하는 것이죠.

 

 

 

쿨백거리는 항상 다음의 성질이 있습니다.

 

 

 

 

등호는 g=f 일때 성립합니다. EM 알고리즘에서 이것 매우 중요합니다. 여기서 log f(h;u)의 하한이 나옵니다. 그럼 f(x)와 g(x)에 어떤 분포를 집어 넣어야지 log f(v:u)와 E[log f(v,h;u)|V) 등이 나올까요?

 

 

 

 

다음에 조금 더 쓰고

 

 

 

 

 

 

 

위의 쿨백거리가 0보다 크다는 것을 증명하는 것은 별로 어렵지 않는데 약간의 아이디어가 필요합니다. 간단한 아이디어를 소개하면

 

 

1) 쿨백거리 적분안에 (f/g)*f 가 들어 있습니다. 이걸 (g/f)*f로 하면 1이 되고 이걸 log 취하면 0이 됩니다.

 

 

2) -log(A/B)=log(B/A)가 됩니다.

 

 

3) -log 함수가 concave(오목함수)임을 이용하여 Jensen 부등식을 이용하거나 아니면 log(x)< (x-1)를 이용합니다. Jensen 부등식은 매우 중요합니다. 그리고 직관적으로 이해하기 매우 쉽습니다. 오목함수나 볼록함수 H의 그림을 그린 다음 H(E[X])와 E[H(X)]를 비교해 보면 됩니다.