HMM계산1

 

 

1. HMM의 전제

 

지난번에 음성인식하는 방법에 대한 기본적인 개념을 살펴 보았습니다. 단순히 개념을 이해했다고 문제를 해결할 수 있는 것은 아니지요. 실제로 계산을 할 줄 알야야 합니다. 그래서 오늘은 전에 잠깐 쓰다가 만 HMM의 계산에 대해서 좀 더 자세히 알아보겠습니다.

 

계산은 수학적으로 별 어려운 것은 없습니다. 단지 좀 복잡해서 처음에 계산 과정을 쫓아 가는 것이 힘듭니다. 먼저 HMM 계산에서 확실하게 이해를 하고 넘어가야 할 부분이 있습니다. HMM 계산에서 사전에 우리가 알고 있는 정보는 딱 2개뿐입니다.

 

 

1) 은닉변수 U는 마코프체인을 한다. 모르는 값이지만 상태전이확률 p(ij)가 있다고 전제를 한다.

 

2) 특정시간 t 시점에서 관찰되는 변수 Y의 분포는 t 시점에서 은닉변수 U의 상태 j에 영향을 받고 이 조건부 확률 분포의 형태만을 우리가 알고 있다. 형태만 알고 있기 때문에 모수들은 모릅니다.

 

 

위 2가지만 우리가 알고 있는 정보라 전제하고 실제 관찰된 data y값을 보고 문제를 해결해야 합니다.

 

위 2가지 정보에서 다음을 알 수 있습니다.

 

1) 시간 t 시점에서 은닉변수 U(t)와 관찰된 변수 Y(t)만 서로 관계를 갖고 있지만 기타 변수들, 즉 관찰변수 (Yi, Yj)간, 관찰변수와 은닉변수 (Yi, Uj) 간에는 서로 독립을 가정하고 있습니다. 즉, 독립의 성격에서

 

f(yi, yj)=f(yi, yj) 또는 f(yi|yj)=f(yi)

 

f(yi, uj)=f(yi, uj) 또는 f(yi|uj)=f(yi) 또는 f(uj|yi)=f(uj)

 

예를 들어 Y(t=3)과 Y(t=5)간에는 서로 독립니다. 그래서

 

f(y(t=3),y(t=5)) = f(y(t=3))*f(y(t=5))

 

입니다.

 

 

또한 t=3에서 U(t=3)과 t=5에서 Y(t=5) 역시 독립입니다. 즉

 

f(u(t=3),y(t=5)) = f(u(t=3))*f(y(t=5))

 

달리 표현하면

 

f(u(t=3)|y(t=5)) = f(u(t=3))

입니다.

 

 

2) U는 마코브체인이기 때문에 Ui와 U(i-1)는 독립이 아닙니다. 그렇다고 해서 Ui와 U(i-2), 또는 Ui와 U(i-3) 과 독립이라는 이야기는 아닙니다. 마크프 체인은 조건부 독립을 이야기합니다. 즉,

 

f(ui, uj|u(i-1))=f(ui|u(i-1))*f(uj|u(i-1))

 

입니다.

 

 

음성인식에서 관찰된 data y1, y2, .., yT이 결합확률분포를 구하는 것이 중요합니다. 그래야 관찰된 음성 y1, y2, ..., yT가 어떤 단어에서 왔는지 판단을 할 수 있습니다. 그럼 이 경우 f(y1, y2, ..., yT)를 한번 구해볼까요.

 

앞에서 이야기했지만 전부 독립이기 때문에

 

f(y1, y2, ..., yT) = f(y1)*f(y2)*...,f(yT)

 

입니다. 간단하죠. 그러나 이걸 실제로 이용할 수 없습니다. 왜냐하면 우리가 아는 것은 f(y(t)|u(t))이지 f(y(t)가 아니거든요. 그럼 우리가 아는 f(y(t)|u(t))를 이용하려면 위의 결합확률분포 f(y(1:T))의 모양을 좀 변경을 해야 합니다. 즉

 

f(y(1:T))=f(y(1:T)|u(t))*f(u(t))

 

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

 

 

여기서 y(t)와 u(t) 빼고는 모두 독립이라는 정보를 이용했습니다. 그러나 뒤에 있는 f(u(t)) 역시 모른다는 것이죠. 그래서 우리가 아는 상태전이확률 f(u(t)|f(u(t-1))를 이용하면

 

f(y(1:T)) = f(y(t)|u(t))*f(u(t)|u(t-1))*f(u(t-1))

 

마지막에 여전히 우리가 모르는 f(u(t-1))이 있기 때문에 이런 간단한 방법이 잘 되지가 않습니다. 그래서 좀 더 골치 아픈 방법을 사용합니다.

 

 

 

2. 강도 문제

 

그래서 다시 기억을 살리기 위해 전에 이야기한 강도 사건으로 돌아가겠습니다. 2충에서 잠들고 있는데 1층에 강도가 듭니다. t 시점에서 2층에서 들을 수 있는 관찰 변수

 

V(t)=(V1(t), V2(t))=(삐끗 소리 여부 , 쿵 소리 여부)

 

즉 2차 다차원 변수입니다.

 

그리고 히든 변수는 아래 거실에서 강도의 위치입니다. 아래 거실을 격자로 나눠

 

H(t)=(Hx(t), Hy(t))=(x 축 방향에서 위치, y축 방향에서 위치)

 

입니다.

 

 

우리가 들은 삐긋소리와 쿵 소리로 알 수 없는 1층 거실에서 강도의 위치에 대한 다양한 추론하고자 하는 것입니다.

그럼 앞에서 이야기한 전제 조건이 이 강도문제에서 맞는지 한번 알아볼까요.

 

1) 현재 시간 i의 2층의 주인이 들은 관찰변수 Vi=(삐긋, 쿵) 소리는 이전 시간이나 이후 시간 Vj=(삐끗, 쿵) 소리와 독립입니다. 왜냐하면 현재 시간 i의 (삐끗, 쿵) 소리 여부는 현재 아래층의 도둑이 있는 거실 위치의 바닥상태나 지형지물(Hi)에만 영향을 받지 다른 위치의 바닥상태와 지형지물(Hj)하고는 아무런 관계가 없죠.

 

2) 현재 거실에서 도둑의 위치는 아래, 위, 왼쪽, 오른쪽 한 칸만 움직일 수 있습니다. 그래서 마코프 체인을 합니다.

지난번 그림을 다시 보죠.

 

 

 

 

수식으로 표현하면

 

fitering은 집주인의 입장에서 추측입니다. 즉 현재 5시점까지 삐끗과 쿵 소리를 들었을 때 도둑이 현재 5시점에서 바닥 어디에 있는가 하는 문제입니다.

 

smoothing은 현재 t 시점까지 다 (삐끗, 쿵) 소리를 다 들은 후 과거 이전 시전 에서 도둑이 있었을 위치를 추정하는 것입니다.

 

세번째 문제 Viterbi 문제와 조금 헷갈릴 수가 있습니다. 수사관이 10시점까지 모든 정보를 집주인에게 듣습니다. 그리고 전체적으로 도둑이 1시점부터 10시점까지 움직일 가능성이 제일 높은 경로를 판단하는 문제입니다. 지난번 음성은식에서 “I bought books"와 ”I boat books"의 예로 설명을 했습니다. filtering이나 smoothing 문제에서 "boat"가 나올 확률이 “bought"가 나올 확률보다 크게 나왔지만 전체적으로 보면 ”I bought books"를 선택한다고 했죠. 이게 히든변수의 문법구조에 맞기 때문이죠.

 

 

 

3. HMM 계산하기

 

여기서 은닉변수 U=H, 관찰변수 데이터 Y=V로 혼용해서 표시하겠습니다. Barber 책에서 내용을 뽑아야 하기 때문에 그 책의 표현도 중간에 사용하겠습니다. H=hidden, V=visual이라는 뜻입니다. 또 HMM의 많이 나오는 recursive 방식의 , 도 간단하게 a(t), b(t)로 사용하겠습니다.

 

그럼 a(t), b(t)의 정의를 한번 알아보겠습니다. Barber 머시러닝 책을 참조하세요.

 

 

 

 

V1:T=(V1, V2, ..., VT)=(V1, V2, ,,,, Vt, Vt+1, ..., VT)는 단순한 표현 방법이고요. 두 번째 식은 Pr(A, B)=Pr(A|B)*Pr(B) 공식을 사용한 것입니다.

 

 

이렇게 정의하면 관찰데이타의 확률분포 f(v1, v2, ..., vT)는 다음과 같이 a(t), b(t)로 간단하게 정의됩니다.

 

 

 

 

 

왜냐하면 f(v1:T)=Σf(ht, v1:T)이고 여기서 f(ht, v1:T)가 바로 위에 정의한 식이기 때문입니다. 이와 같이 HMM관련 문제에서 대부분 계산을 이 a(t)와 b(t)를 이용하여 풉니다.

 

 

 

그래서 계산은 사실상 a(t), b(t)를 구하기만 하면 됩니다. 그런데 a(t), b(t)를 구하는데 전산에서의 recursive 방식을 사용합니다. 구하려는 값을 result(n)이라 하면

 

result(n) = something * result(n-1)

 

이런 모양으로 구현을 해야 합니다. 예를 들어 factorial 계산에서는

 

factorial(n)=n*factorial(n-1)

 

이죠. 그래서 a(t), b(t) 계산에서도

 

a(t)=something*a(t-1)

b(t)=something*b(t+1)

 

이런 모양이 나오도록 수식을 전개해야 합니다. b(t)는 계속 과거로 까는 것이 아니고 미래로 계속 덮어가는 모습니다.

 

그럼 이 a(t), b(t)가 recursive 형태로 어떻게 표현되는지 barber 책에서 한번 보죠.

 

 

 

1) 알파 계산

 

 

 

 

 

최종식에서 보면 우리가 알 수 있는 계산만 나옵니다. p(vt|ht)와 p(ht|h(t-1))이죠. 식을 자세히 보면 a(t)는 a(t-1)의 가중평균을 구한 다음 p(vt|ht)를 곱하는 것으로 나옵니다.

 

 

 

2) 베타 계산

 

위 a(t), b(t) recursive 공식 계산에서는 다음의 정보를 이용했습니다. 앞에서 계속 강조했지만 hj와 vi간, vi와 vj간에는 서로 독립입니다.

 

X와 Y가 독립이면

 

f(x,y) = f(x)*f(y) 또는

f(x|y) = f(x)

 

이렇게 됩니다. 또 주변밀도함수 법칙

 

f(v1:T) = Σf(ht, v1:T)

 

 

b(t)도 a(t)와 마찬가지로 우리가 아는 계산만 나옵니다.

 

 

 

 

앞에서 결합확률분포 f(y1, ..., yt)를 간단하게 a(t)로 표현했듯이 다음에는 이 a(t), b(t)를 이용하여 또 다른 문제를 a(t), b(t)의 형식으로 써 보겠습니다.

 

 

 

4. recursive 방식과 iterative 방식

 

recursive 방식과 iterative 방식은 실제 프로그램에서 어떻게 다르까요. factorial 구하는 식을 S와 R에서 프로그램을 해보겠습니다.

 

 

1) recursive 방식

 

fact<-function(n){

if (n<=1) 1 else n*fact(n-1);

}

 

이걸 노트장에서 쓰고 fact.txt로 저장하고 S나 R의 명령문 창에서 source("fact.txt") 하면 됩니다. 그런 다음 명령문 창에서 fact(5)하면 5! 값이 나옵니다. 이건 Becker 책에 그대로 나오는 프로그램입니다. 실제 계산 효율은 안 좋다고 합니다. 계속 fact라는 함수를 불러와야 하죠. 실제 S나 R에서는 prod(1:n)이라는 함수를 제공하고 있습니다. factorial(n)이라는 함수도 제공하고요.

 

 

 

2) iterative 방식

 

ifact<-function(n){

init<-1;

for (i in 1:n){

init<-i*init;

}

init;

}

 

iterative 방식은 실제 프로그램에서 반복하는 과정을 구체적으로 써야 합니다.

 

 

S나 R은 벡터 컴퓨팅을 지원합니다. 예를 들어 위의 계산은 하나의 factorial 값 밖에 구할 수 없습니다. 만약에 5개의 factorial 값을 한꺼번에 구한다면 어떻게 해야 할까요. 벡터 컴퓨팅이 아니면 위의 factorial 계산을 5번 해야 합니다. 그러나 벡터 컴퓨팅을 지원하고, 그리고 슈퍼 컴퓨터 같이 프러세스가 여러개 있으면 1번 계산으로 끝납니다. 각 프러세스가 서로 병렬적, 즉 독립적으로 하나씩 맡이 계산을 따로 따로 합니다. 그래서 이런 벡터 컴퓨팅, 병렬 컴퓨팅의 계산 능력이 매우 중요합니다. factorial 계산을 병렬적으로 하려면 Becker 책을 참조하시기 바랍니다. R을 전문적으로 쓰려는 분은 꼭 이 책을 보셔야 합니다. S나 R의 고전책입니다.

 

 

볼쯔만 머신에서 각 노드에서 1과 0을 결정하는 것은 그 노드 주변의 노드에 영향을 받는다고 했습니다. 또 그 주변에 있는 노드의 0과 1을 결정하는 것은 또 그 의 주변에 있는 노드들에 의해 영향을 받는다고 했습니다. 그래서 각 노드의 값의 결정이 서로 독립적이지 않고 상호연관적입니다. 그래서 병렬 계산이 쉽지가 않습니다. 슈퍼컴퓨터 같이 프로세스가 엄청나게 많아도 별 효과가 없다는 것이죠.

 

 

이건 기상 예측에서도 비슷할 겁니다. 한 지역의 기상은 그 주변의 기상에 영향을 받고 그 주변의 기상은 또 그 주변의 기상에 영향을 받고 이런 식으로 서로 영향 관계가 되어 있다는 것이죠.

 

슈퍼컴퓨터를 도입한다고 기상 예측이 정확해지는 것은 아닙니다. 이건 하드웨어 개념이기 때문에 계산을 빨리 해준다는 것이죠. 기상 예측 프로그램이 병렬 컴퓨팅을 지원한다면요.

 

기상 예측이 좋아지려면 기상예측 프로그램, 소프트웨어가 좋아야 하는 것이죠. 슈퍼 컴퓨터를 도입했는데도 불구하고 기상 예측이 계속 안 좋으면 예측 프로그램이 자체가 안 좋거나 아니면 이 프로그램의 파라메터를 우리나라 기상 상황에 맞춰 fitting, 학습을 시켜야 하는데 이걸 제대로 못한다는 이야기입니다.

 

 

그런데 기상예측이나 지진예측에는 왜 인공지능이야기를 안 하는 걸까요?