EM 알고리즘 이해1

 

 

EM 알고리즘 부분은 따로 섹션을 마련하였습니다.

 

앞에 이미 적은 것은 지우고 그 중에서 필요한 부분은 이 섹션에 다시 쓰고요.

 

여기서 기호는 a, b, c 등은 모수, 즉 우리가 데이터에서 추정해야 하는 값이고, X, Y, X, x, y, z는 변수, 그리고 필요에 따라서 V, v, H, h, 즉 관찰변수 V(visual), 은닉변수 H(Hidden)로 표시하겠습니다. 그리고 a, x 이런 표현은 1차원 변수도 될 수 있지만 일반적으로 k차원 변수, 즉 벡터라고 생각하셔도 됩니다. 통상 통계학 교과서에 우도함수라고 하는 것을 저는 가능성 함수라 이야기하겠습니다. 그리고 가능성 함수는 통상 log을 많이 취하는데 이건 그냥 계산상의 편리입니다. 개념적으로만 생각하면 log를 취할 필요가 없습니다. 그러나 실제 문제에서는 대부분 log을 취해야 합니다.

 

 

 

 

1. EM을 기계적으로 한다면

 

 

먼저 우리가 EM 알고리즘 자체를 이해하지 않고 그냥 기계적으로 적용한다면 한편으로는 EM 알고리즘은 간단하다고 할 수 있고요, 또 한편으로는 어렵다고 할 수 있습니다.

 

EM 알고리즘은 기댓값 구하는 첫 번째 부분(Expectation 부분)과 첫 번째에서 구해진 기댓값을 모수에 대해 최대값을 구하는 부분(Maximization 부분, 즉 모수에 대해 미분해 0으로 놓고 풀면 되는 것이죠) 이 두 부분이 있고, 이걸 수치해석적으로 계속 반복해서 실행하면 됩니다.

 

 

E: ELL=Eh|v,a*[logf(V, H; a)]

 

M: ELL을 maximize 하는 a를 구하자

 

 

 

M 단계에서 구한 a를 다시 E 단계에서 a*로 집어 넣고 다시 ELL을 구하고 두 번째 구한 ELL을 최대화하는 a을 구한 다음 이를 다시 E 단계에서 a*로 넣고 이런 식으로 계속해서 진행하여 안정적인 값에 갈 때까지 계속 하는 방법입니다.

 

쉽다면 측면은 이 방법을 통계학적으로 이해하지 않고 그냥 전산과의 수치해석 문제로 생각하고 풀면 된다는 것이죠. 한편 쉽지 않다는 것은 실제로 대부분 교과서에 나오는 예제는 수치해석의 문제가 아니라 손으로 수학문제를 푸는 것과 같고, 이게 쉽지가 않습니다. 특히 E 단계에서요. E 단계를 풀면 M단계는 수치해석으로 할 필요도 없이 단순하게 풀어질 수 있습니다. 즉 closed form으로 ELL을 최대화하는 모수 a의 공식을 구할 수 있습니다.

 

 

E 단계에서 가장 어려운 부분이 H|V에 관해 기댓값을 구하는 부분입니다. 이 기댓값을 구하려면 H|V의 확률분포 f(h|v), 즉 조건부 확률분포를 구해야 하는데 이게 쉽지가 않습니다. 통상 문제에서, 또 현실에서 V|H의 확률분포 f(v|h)는 알려져 있거나 현실에서 어느 정도 알 수 있다고 생각합니다. 그래서 머리 속 생각에서는

 

 

 

f(v|h)==>f(h|v)

 

 

 

구하는 것은 간단하다고 생각할 수 있지만, 왜냐하면 이건 기초통계의 간단한 확률공식이거든요, 그러나 실제로는 매우 어렵습니다.

 

 

그러나 또 한편 쉽다고 생각할 수 있는 것은 기댓값 E는

 

 

 

E[aX+bY]=aE[X]+bE[Y]

 

 

 

라는 선형 함수, 또는 linear operator는 성격 때문에 ELL이 생각보다 쉽게 풀어질 수 있습니다. 기댓값이 실제 계산에서는 적분이기 때문에 이런 성질을 가지고 있는 것이죠. 특히 확률분포가 지수계열(exponential family)이면 EM 알고리즘은 더 간단하게 표현됩니다.

 

 

그러나 현실적인 문제에서는 대부분 E 단계를 손으로 수학 문제 풀듯이 어렵게 풀어야 합니다.

 

 

 

 

2. 우리는 도대체 뭘 하는 것일까요?

 

 

대부분 사람들은 EM 알고리즘을 적용한다면 뭐 대단한 이상한 것을 한다고 생각합니다. 아닙니다. 그냥 MLE 구하는 것입니다. 단지 은닉변수 H 변수가 들어가 있는 경우 일반적인 MLE 구하는 방법을 바로 적용할 수 없습니다.

 

여기 블로그를 방문하신 분들이 MLE 구하는 방법, 가능성 함수(우도 함수)에 대해 질문들을 많이 하십니다. 이 MLE와 LF(가능성 함수)을 잘 이해 못하는 이유가 주류통계학 관점이 문제가 있기 때문입니다. 베이지안 생각을 가르치면 바로 이해가 되는 것이거든요. 하여간 주류통계학의 표현을 사용하겠습니다.

 

 

확률분포 f(x; a)는 우리가 모르는 모수가 a일 때 확률변수 X가 x라는 값을 취할 확률의 개념입니다. 그러나 구체적으로 x가 무슨 값인지 모릅니다. 모든 가능한 x에 대해서 이야기를 하는 것이죠. 연속형 변수이면 x값 근처의 구간의 확률이 되고요. 그냥 확률변수 X의 확률이라 생각하시면 됩니다. 즉 확률분포 f(X, a), 여기서 X가 구체적으로 무슨 값인지 모릅니다.

 

 

LF는 전혀 반대의 개념입니다. 우리가 설문지나 아니면 실험에서 확률변수 X의 구체적인 값 x를 관찰하였을 경우 모수 a가 나올 확률, 가능성 개념입니다. 즉 f(X=x; a)가 됩니다.

 

 

예를 들어 어떤 사람이 손에 동전을 쥐고 있습니다. 손을 폈을 때 동전 앞면이 나올 확률이 a, 뒷면이 나올 확률은 (1-a)라고 하죠. 동전을 폈을 경우 앞면이 나오면 1이라 하고, 뒷면이 나오면 0이라고 하죠.

 

그럼 확률분포는, 동전을 손에 감추고 있으면  동전이 앞이 나오는지 뒤가 나오는지 모르기 때문에 X=0일 경우, X=1일 경우 다 적어야 합니다.

 

f(X=1, a)=a, f(X=0, a)=1-a 라는 것이죠. 이걸 하나의 식으로 쓰면

 

 

 

f(x; a)=ax(1-a)1-x

 

 

즉, x와 a의 함수입니다.

 

 

그러나 LF, 가능성 함수는 다릅니다. 이건 실제 X의 값을 관찰한 경우입니다. 만약 손을 폈을 때 앞면이라면 x=1 을 위 확률분포의 식에 대입합니다. 그럼

 

 

 

LF=f(x=1,a)=a

 

 

 

즉 오로지 모수 a의 함수입니다.

 

만약 뒷면이 나왔다면 x=0 이면

 

 

 

LF=f(x=0,a)=1-a

 

 

 

 

이것 역시 오로지 모수 a의 함수입니다.

 

즉 가능성 함수는 위 두가지 경우 중 오로지 하나만 선택해서 사용해야 합니다. 왜냐하면 이미 x는 특정 어떤 값으로 관찰되었기 때문입니다.

 

 

간단히 이야기 해서 확률분포는 f(X ;a)라고 생각하고 가능성 함수는 f(X=x; a)라고 생각하면 됩니다. 이때 x는 설문지나 실험에서 실제 여러분이 관찰한 값으로 가능성 함수는  “실제로”  확률분포 수식에 이 x값을 집어 넣어 나오는 오로지 모수 a에 대해서만의 함수입니다.

 

 

그럼 은닉변수가 들어가 있는 경우 MLE를 구할 때 무슨 문제가 생길까요?

 

가능성 함수를 구하려면  f(V, H; a)에서 실제 관찰한 값 V=v, H=h 값을 집어 넣어야 하는데 H의 값이 관찰이 안된다는 것이죠.

 

즉

 

 

 

LH=f(V=v, H=? ; a)

 

 

 

 

이렇게 되어 버려 사용할 수 없습니다. 

 

그럼 우리가 오로지 관찰한 값, 우리가 가지고 있는 정보는 V=v 이기 때문에 위의 식 대신

 

 

 

LH=f(V=v; a)

 

 

을 써서 하면 안될까요? 하는 의문이 생깁니다.

 

 

네 맞습니다. LH=f(V=v; a)를 사용해서 하면 됩니다.

 

 

그런데 여기서 사람들이 많이 햇갈립니다. 통상 교과서에 나오는 f(x;a)와 EM 알고리즘에 나오는 f(x:a)는 개념이 많이 다릅니다. 예를 두 개 들어 주겠습니다.

 

 

동전을 던진다고 하죠. 앞면이 나올 확률은 a, 됫면이 나올 확률은 당연히 (1-a)가 되겠죠. 그럼 확률분포는

 

 

 

f(x; a)=ax(1-a)1-x

 

 

 

 

이게 통상 교과서에 나오는 확률분포의 모습입니다. 우리가 모르는, 그래서 관찰된 값 x를 보고 추정해야 할 모수는 a 오로지 한 개입니다.

 

 

 

그러나 사람이 가리막 뒷에서 두 개에서 동전을 가지고 있습니다. 동전 A는 앞면이 나올 확률은 a, 동전 B는 앞면이 나올 확률은 b라고 하죠. 그리고 이 두 개의 동전 중 A를 선택해서 던질 확률은 c라고 하고 B를 선택해서 던질 확률은 (1-c)라고 하죠. 동전을 관찰하는 사람은 어떤 동전을 던지는지는 전혀 모르고 오로지 동전이 앞면이 나왔는지 뒷면에 나왔는지 이것만 알 수 있다는 것이죠.

 

이 경우 확률분포는 위와 전혀 다릅니다. 이 경우

 

 

 

f(x; a)=c*ax(1-a)1-x +(1-c)*bx(1-b)1-x

 

 

 

 

이렇게 됩니다. 이 경우 우리가 모르는, 데이터를 보고 추정해야 하는 모수는 a, b, c 세 개로 늘어납니다. EM 알고리즘은 이 경우를 합니다. 똑같이 f(x)를 쓰지만 실제 구체적인 함수 모양과 모수가 다릅니다.

 

 

그럼 위의 공식은 어디서 나왔을가요. f(v;a)는 두 가지로 달리 표현됩니다. 먼저 결합밀도함수에서 주변밀도함수를 구할 경우입니다.

 

 

==> 아래 식에서 u는 h로 고쳐야 합니다.

 

 

 

 

 

 

즉 은닉변수 h에 대해 적분, 또는 summation 하면 됩니다.

 

 

이런 표현말고 대부분 베이지안 정리때 사용하는 표현이 있습니다.

 

 

 

 

 

 

 

   

 

위의 동전 A, B 중 하나를 던지는 경우 바로 위 식의 마지막 summation에 있는 공식을 사용한 것입니다.

 

 

그래서 EM에서 나오는 f(v)는 원래 결합밀도함수 f(v, h)에서 나온 주변밀도함수 f(v)니다. 여기에 관찰된 값 v를 집어 넣고 모수 a에 대한 함수로 생각해 최대화 시키는 a를 구하는 것입니다.

 

 

즉, 이런식으로 f(v;a)가 쉽게 구해지면 이걸 최대화하는 a를 구하면 됩니다. 구태여 EM 알고리즘을 사용할 필요가 없습니다. 통상 EM 설명하는 예 중에 구태여 EM 알고리즘을 사용할 필요가 없는데 EM알고리즘을 적용해 사용하는 예를 보여주는 경우가 많습니다.

 

 

 

예를 들어 결측값이 있는 경우입니다. 우리가 사람들의 키를 관찰했다고 하죠, 그 중 하나는 결측값(missin value)라고 하죠. 사람의 키는 정규분포를 한다고 가정하고, 그럼 모수 a=(평균, 분산) 두 개가 됩니다. X~Normal(x;a) 이렇게 되는 것이죠. 실제 관찰한 값이 다음과 같다고 하죠.

 

 

변수	값
V1	150
V2	170
H	?

 

 

두 개의 관찰된 키는 V1=150, V2=170, 하나는 어떤 이유로 인해 값을 모릅니다. 즉 H=?입니다. 이런 상황에서 우리가 결측값 H를 무시하고 V1과 V2만을 사용하면 평균에 대한 추정값은 표본 평균인 (150+170)/2=160이 됩니다.

 

 

그러나 은닉변수인 H까지 고려할 경우 평균은 추정값은 어떻게 달라질까요? 똑 같습니다. 즉 이 경우도 160입니다. 왜 이렇게 되는지 한번 보겠습니다. 우리가 먼저 구해야 할 확률분포는 f(V1, V2, H;a)입니다.

 

 

그럼

 

 

f(V1, V2, H;a)=Normal(v1, a)*Normal(v2, a)*Normal(h,a)

 

 

입니다. 서로 독립이기 때문에 곱해주면 됩니다.

 

 

여기서 우리가 실제로 사용해야 할 확률분포는 주변밀도 분포인 f(V1, V2;a)입니다. 즉.

 

   

 

 

즉, 관찰된 변수 V1, V2만 가지고 MLE 구하는 것이랑 결측값이 은닉변수 H가 있는 경우 MLE 구하는 것이 같습니다. 따라서 구태여 EM 알고리즘을 적용해 멍청하게 구할 필요가 없습니다. 그런데도 교과서 같은 곳에 EM 알고리즘을 적용해 설명하는 이유는 EM 알고리즘 계산 방법을 쉽게 설명하기 위해서입니다. 이게 수식이 간단하거든요.

 

 

그럼 결측값이 있는 경우는 모조건 은닉변수인 결측값을 무시해도 되는 것일까요. 위에 결측값 예에서는 관찰변수 V와 은닉변수인 결측값 H가 서로 독립적인 경우입니다. V와 H가 서로 관계가 있는 변수인 경우 은닉변수인 결측값 H도 고려해야 문제를 해결할 수 있습니다. 이런 예를 다음 글에서 적겠습니다.