HMM

 

 

1. Mixture, PET, HMM 비교

 

오늘은 EM이 나오는 또 하나의 경우인 HMM에 대해서 설명하겠습니다. 이게 음성을 문자로 전환하고 또 전환된 결과를 다른 언어로 번역하거나 응답하는 경우에 자주 쓰이는 모형인 것 같습니다. 그러나 아직 좀 간단하면서도 구체적인 예를 보지 못해서 이건 나중에 찾으면 소개하겠습니다.

 

우선 관련된 논문을 첨부하겠습니다.

 

 

tutorial on hmm and applications.pdf

 

 

첨부한 논문이 유명한 논문인 모양입니다. 그냥 구글에 검색해서 읽어 봤는데요. 하여간 이 논문에 나온 내용을 한국 박사가 국내에 와서 강의를 한 모양입니다. 제 블로그에 방문한 분이 있는데 이 분이 이 강의를 듣고 한글 파일로 정리한 게 있습니다. 그것도 첨부하겠습니다. 공개된 블로그에서 가져 왔기 때문에 별 문제가 없을 것 같습니다.

 

 

히든마코브.hwp

 

같이 보시면 이해하는데 도움이 될거라 봅니다.

 

 

그럼 우선 앞에 소개한 Mixture 모형(혼합모형)과 PET(뇌촬영)과 HMM(은닉 마코프 모델)을 간단히 비교 소개하겠습니다. HMM의 경우 예를 들어 그날 날씨에 따라 교통사고의 건수가 달라질 수 있습니다. 그럼 우리가 관찰된 교통사고의 건수 데이터를 있을 경우 관측되지 않는 그날의 날씨를 알 수 있겠는가 하는 문제입니다. 이 문제의 가정으로 날씨는 마코프 체인을 한다고 가정합니다. 간단하게 날씨를 맑은 날, 흐린 날, 비나 눈이 오는 경우 세 가지를 나누고 현재 날씨는 오로지 이전 날씨에만 영향을 봤지 그 전의 날씨나 오늘 이후 날씨에는 영향을 안 받는다는 가정입니다.

 

 

아래 그림을 한번 보죠.

 

 

 

 

 

 

 

HMM은 혼합모형과 비교하면 은닉변수가 시간에 따라 변하는데 이때 마코브 체인을 한다는 것이고요. 뇌촬영과 비교하면 뇌촬영에서는 은닉변수에서 디텍터로 갈 확률 Pij가 기하학적인 성질에 의해 사전에 이미 알려져 있다고 가정하는 반면 HMM에서 전날 날씨에서 오늘 날씨로 갈 상태전이 확률 Pij는 관찰된 변수에서 추정을 해야 하는 모수로 가정을 합니다.

 

 

음식인식이 경우 관찰된 변수 Y는 벡터 모향을 뜁니다. 예를 들어 “Love"라고 누가 이야기를 하면 Y1는 ”L"에 해당하는 음파로 받아 U1는 “L"이라 문자로 인식하고 Y2는 ”o"에 해당하는 음파를 받아 U2는 “o"라는 문자로 인식합니다. 따라서 음파로 데이터로 해야 하기 때문에 Y1, Y2, ..., YT 각 변수들 각각 하나의 실수 값이 아니고 벡터 값 모양의 데이터 받아야 합니다.

 

실제로는 다르게 할 수 있습니다. 영어 알파벳 문자 26개인가요? 각 알파벳 문자의 주파수에 대해 표준적인 codebook를 만들고 이 codebook에 index를 줘 이 index를 데이터 값으로 할 수 있습니다.

하여간 전반적인 과정은 첨부한 논문 216페이지 오른쪽에 있으니까 참조하시기 바랍니다.

 

 

한글이 디지털 시대에 잘 맞는다고 하는데 이런 인공지능에 나오는 문자나 음성 인식 문제에서는 별로 좋지 않습니다. 영어나 일어는 철자 하나 하나 분리가 되는데 우리는 초성, 중성, 종성이 결합되어 수 많은 형태가 있습니다. 이걸 데이터를 통해 분류를 해야 하거든요. 아마 획기적인 아이디어가 필요할 지 모르겠습니다.

 

 

우리는 예로서 특정 날씨별로 그날 교통사고를 관찰변수 Y로 하였는데, 이 경우 f(y|특정날씨)는 포아송 분포를 가정하고, 또 관찰변수를 그날 회사에 도착할 때까지 걸리는 시간으로 하면 f(y|그날 날씨)는 지수분포를 한다고 가정하면 됩니다. 그러나 대부분의 책의 예제는 Y는 범주형 변수, 즉 특정 값 몇 개만 취하는 다항분포를 가정하고 많이들 설명합니다.

 

 

 

2. Dynamic Programming

 

책에 설명에 많이 나오는 것이 Dynamic Programming입니다. 흔히 전산 프로그램에서 반복작업을 많이 하는데 여기에는 두 가지 개념이 있습니다. 일반적으로 iteration한다고 하는데 좀 특수한 형태를 recursive 방식으로 한다고 합니다. 통상 iteration 방식은 대등하게 반복작업을 하는 경우를 말합니다.

 

EM 알고리즘 자체가 iteration 방식이고요. 예를 들어 숫자 n 개 값을 더한다 하면 S1=a1, S2=S1+a2, S3=S2+a3 이런 식으로 계속 반복해서 더하면 됩니다. 만약 n개 숫자가 1부터 n까지라고 하면 이건 다음과 같이 쓸 수가 있습니다.

  

S(n)=1+2+3,...,+n=S(n-1)+n=S(n-2)+(n-1)+n=...

 

이런식으로 표현이 됩니다. 양파 까듯이 계속 파고 드는데 계속 같은 모습 S(k)라는 형식이 나온다는 것이죠. 가장 대표적인 것이 factorial 계산입니다.

   

n!=(n-1)!*n=(n-2)!*(n-1)*n=...

 

이런 모양이 나올 때 recursive 방식이라 이야기 합니다. 사실 이 성질을 일반적으로 이야기하면 프랙탈의 자기 유사성 성질입니다. 즉 scale(규모)에 관계없이 어떤 시스템에서 똑같은 성질을 가지고 있는 것을 말합니다. 그 대표적인 예가 관료주의이겠죠, 가장 큰 국가 조직에서 시작해서 각 부서, 또는 지방 정부, 또 지방 정부의 각 부서 이렇게 밑으로 작은 조직으로 계속 까 내려 갈 때 관료주의, 또는 위계문화, 억압문화 등이 계속 보이면 이걸 프랙탈 성질이라 합니다.

 

 

이건 확률분포에서도 볼 수 있습니다. 이 블로그의 지난번 글에서 모든 확률분포는 조건부 확률분포를 표현할 수 있다고 했습니다. 즉.

 

f(u(1), u(2), u(3),..., u(n))

=f(u(n)|u(1),u(2), u(3),..., u(n-1)) * f(u(1), u(2),..., u(n-1))

=f(u(n)|u(2),u(3),...,u(n-1)) * f(u(n-1)|u(1),u(2),..., u(n-2)) * f(u(1),u(2)..., u(n-2))

=...

 

이렇게 계속 똑같은 모양으로 새끼를 쳐 갈 수 있다는 것이죠. 만약 위의 U가 마코프 체인이면 위 식은

 

f(u(1), u(2), u(3),..., u(n))

=f(u(n)|u(n-1)) * f(u(1), u(2),..., u(n-1))

=f(u(n)|u(n-1)) * f(u(n-1)|u(n-2)) * f(u(1),u(2)..., u(n-2))

=f(u(n)|u(n-1)) * f(u(n-1)|u(n-2)) * f(u(n-2)|u(n-3)) * f(u(1),u(2)..., u(n-3))

=...

 

이렇게 더 간단하게 표현이 됩니다.

 

 

 

3. f(y,u), f(y) 구하기

 

EM을 적용하려면 관찰변수 Y와 은닉변수 U의 결합확률분포 f(y,u)를 구해야 합니다. 물론 기댓값을 취하기 위해 f(u|y)도 구해야 하죠. 먼저 f(y, u)부터 볼까요. 확률공식에 의해

 

f(y,u)=f(y|u)*f(u)

 

입니다.

 

 

그럼 먼저 f(u)부터 알아보죠. 앞에서 U는 마코프체인이라 해서 이것의 확률분포는 간단히 표현된다고 했죠. 이게 중요한 첫 번째 전제이고요.

 

그럼

 

f(u)=f(u(n)|u(n-1)) * f(u(n-1)|u(n-2)) * f(u(n-2)|u(n-3)) * f(u(1),u(2)..., u(n-3))

 

즉 상태 전이 확룰 Pij로 표현이 됩니다.

 

즉

 

f(u)=P(1)*Pij(1->2)*Pij(2->3)*Pij(3->4),...,*Pij((T-1)->T)

 

P(1)는 시점 1인 초기 U의 상태에 대한 확률입니다. 1->2는 시점 1에서 시점 2로 가는 것을 말합니다. 예를 들어 시점 1에서 U=맑음, 시점 2에서 U=비눈이 되면 Pij(1->2)는 P13이 되는 것이죠. 시점 1에서 U=흐림, 시점 2에서 U가 맑음이 되면 Pij(1->2)는 P21이 되고요. 우리 U가 1은 맑음, U가 2면 흐림, U가 3이면 비눈이라 정의했다고 가정한 것입니다. 즉 f(u)는 첫 번째 초기 확률에다 각 시간 변화에 따른 상태 전이 확률을 계속적으로 곱한 형태가 됩니다.

 

그 다음 f(y|u)를 알아보죠. f(y|u)는 앞의 사고건수인 경우는 포아송 분포를 쓰면 되고, 직장까지 도착하는데 걸리는 시간이면 f(y|u)는 지수분포가 됩니다. 그러나 통상 HMM에서는 범주형, 즉 다항분포를 가정하는데 여기서 이 분포식이 쓰기도 힘들고 계산도 복잡해집니다. 연속형이 분포 식이 어려워서 힘들 것 같은데 실제는 그 반대입니다.

 

하여간 f(y|u)는 우리의 경우 연속형은 세 가지가 나옵니다. f(y|맑음), f(y|흐림), f(y|비눈) 이겠죠. 또 다항분포인 경우 만약 y가 m개의 값을 취한다고 하면 m*3개의 표현이 들어가야 합니다. Y=m, U=k라는 값을 취하면 이때 확률의 값을 B(m,k)라고 표현하겠습니다.

 

여기서 중요한 두 번째 가정이 있습니다. 특정 t 시점에서 관찰된 Y(t)는 그 시점에서 은닉변수 U(t)에만 영향을 받지 이전이나 이후의 Y값, 또는 U값에는 아무런 영향을 안 받는다는 것이죠. 즉,

 

 

f(y|u)=f(y1, y2, ..., yT|u)=f(y1|u)*f(y2|u)*,...,*f(yT|u)

=f(y1|u1)*f(y2|u2)*,...*f(yT|uT)

 

즉 u의 상태에 따라 포아송인 경우 포아송 분포, f(y|맑음), f(y|흐림), f(y|비눈) 이런 식으로 계속 곱하고 지수 분포인 경우 U의 상태에 따라 지수분포를 계속 곱하고, 다항분포인 경우 B(m,맑음), B(m,흐림), B(m, 비눈)의 확률값이 된다는 것이죠.

 

그럼 복잡하지만 f(y|u)문제도 해결되었고, f(u) 문제도 해결되었고, 그래서 f(y,u)는 이 구한 두 개를 곱하면 됩니다.

 

그럼 f(y)는 어떻게 구할까요. 정의에 의해

 

f(y) = Σf(y,u)

 

입니다. 여기서 summation은 당연히 U가 취할 수 있는 모든 경우에 대해서 summation 한다는 이야기죠. u가 맑음, 흐림, 비눈 이 세 가지 밖에 없어 간단할 것 같지만 그렇지 않습니다. U가 시간 1에서 T까지 있는 변수, 즉 U=(U1, U2, U3,...,UT)이기 때문에 T*3의 개수 만큼 경우의 수가 존재합니다.

 

그래서 실제로 구하기가 힘든데 여기에 또 dynamic programing 아이디어가 작용합니다. 이걸 사용하는 방법을 HMM에서는 forward-backward 방식이라 이야기합니다. 즉 프랙탈같이 계속 앞이나 뒤로 까 나가면 계속 같은 모양, 같은 유형이 나온다는 이야기입니다.

 

이건 다음에 더 이야기 하고 앞에서 이야기한 블로그 한글파일에 있는 그림을 먼저 보여 드리겠습니다.

 

  

 

히든마코브.hwp

1.49MB

tutorial on hmm and applications.pdf

2.21MB