비터비(Viterbi) 알고리즘

프로그램 레포트가 나와서 한번 정리 해본다.

관측열과 모델이 주어져 있을때 최적의 상태열(State Sequance)를 찾아내는 알고리즘 이다.

물론 모델이라함은 HMM(Hidden Markov Models)을 칭하는것이다.
모델의 가정은 “시간 t에서의 상태에 영향을 미치는것은 t-1에서의 상태다”이다.
물론 t-1,t-2가 된다면 2차 HMM모델이 된다.
식의 유도는 복잡해서 생략하지만 간단하게 언급만 하자면 베이즈 룰을 이용해서 Prior Probability부분을 알아내기 위한거라는 것 정도만 알고있으면 된다. 그 부분에 영향을 주는걸 t-1 스테이트로 줌으로써 식을 간단하게 풀수있게 했다.

아래와 같은 모델이 주어져 있다고 가정하자. 아래에서 Transition Probability는 화살표이고 내부의 확률은 Output Probability이다. 두개의 결합확률(Joint Probability)를 이용해 해당 스테이트의 확률을 구할수 있다.

개별 값들은 주사위의 눈을 지칭하는 것들이다.

두개중에 어떤 주사위를 던지는지는 모른다(모든 눈이 공평하게 나오는 주사위와 그렇지 않은 주사위 두개가 있다). 그리고 눈이 어떤눈이 나왔는지만 나는 알고 있다.

아래와 같은 관측열이 나왔다고 하자면

315116246446644245311321631164152133625144543631656626566666
651166453132651245636664631636663162326455236266666625151631
222555441666566563564324364131513465146353411126414626253356
366163666466232534413661661163252562462255265252266435353336
233121625364414432335163243633665562466662632666612355245242

과연 어느 주사위에서 나온 값들인지 추정하는게 비터비 알고리즘의 목적이다. (Load 주사위 일까 Fair 주사위일까?)

위와같이 300개정도의 관측열이 나왔을 경우는 확률값이 상당히 작아지는 경향이 있기때문에 계산 Base 자료형의 세심한 관리가 필요할것이다. 아마 float같은 형으로 계산을 했을땐 t가 증가할수록 0에 완전히 수렴해버릴것이다.

뭐 여기에 수식까지 넣기는 힘들어서 수업자료 캡쳐만 떠왔다.

B라는 변수는 시간 t에서 L 이든 F이든 어느 주사위의 이전 주사위 state를 저장하면 된다.
그렇게 함으로써 back-tracking이 가능하게 된다.
뭐 프로그램으로 구현하자면 b[t][2] 와 같은 int 나 char 형 배열로 정의하면 딱 적당하다.

V 값은 가용한 모든 이전 스테이트의 V값과 이전스테이트에서 현재 스테이트로 이동하는 trainsition 값을 곱한 값인데 그 중에서 가장 큰 값을 골라, 현재 state의 주어진 주사위 확률값과 곱을 해주면 된다.
위에서 가장 큰 값이라고 했는데 그 값을 가지는 이전 state를 B값이 저장하면 된다.

그러니까 간단하게 현재 스테이트에서 가장 큰 Probability를 구하고 그 Probability 이전 state값을 B값에 저장해놓는다. 그리고 마지막에 그런 확률값들의 누적치중 최고값을 가지는 state에서 백트랙킹을 시작해 최적의 상태열을 추출해 내는 알고리즘이다.

뭐 이번에는 C로 한번 구현해보려한다.
알고리즘은 다 이해가 되는데 일단 구현은 그보다 더 많은 고민을 요구하는게 사실이니….