[TENSORFLOW] HMM viterbi 알고리즘

2017/04/14 - [machine learning] - [TENSORFLOW] Hidden Markov Model

지난 포스팅에서 HMM과 forward 알고리즘에 대해 알아봤다면 이번에는 주어진 관측 데이터에 대해 가장 최상의 hidden state는 무엇인지를 찾아보는 viterbi 알고리즘에 대해 알아보자.

예를 들어 [Walk -> Shop -> Shop -> Clean -> Shop] 라는 관측 데이터가 주어졌을 때, 이에 대한 가장 최상의 state는 [Rainy -> Sunny -> Sunny -> Rainy -> Rainy] 라는 것을 찾아 내는 것이다.

위와 같은 HMM 모델에 대해서 [Walk->Shop->Shop->Clean->Shop] 일 때의 상태 정보를 알아볼 것인데, 원리는 해당 관측일때의 각각의 상태 확률을 곱해서 가장 높은 확률 결합을 나타내는 상태정보를 찾으면 되는 것이다. 즉, 해당 하는 관측일때의 모든 상태 리스트들에 대한 확률을 계산해서 가장 높게 나타나는 확률을 가진 상태 정보를 찾으면 된다.

이론상으로는 이렇지만 구지 모든 상태 리스트들을 다 계산하지 않아도 된다. 코드로 살펴보자.

viterbi_decode 함수를 실행하면 맨 처음으로 forward 알고리즘과 마찬가지로 초기 확률에 해당 하는 관측 확률을 곱한다. ( [0.6 * 0.1], [0.4 * 0.6]] )

초기 확률에 대한 계산이 끝났다면 ([0.06], [0.24]) 이제 decode_op와 backpt_op를 실행하자. decode_op는 이전 forward_op와 마찬가지로 각 상태에 대한 확률을 곱해주는 것이다. 차이점이 있다면, forward_op에서는 각 상태의 확률을 더했다면, decode_op에서는 각 상태의 확률 중 y축을 기준으로 max 값만을 취한다는 것이 차이점이다.

이 말인즉, 만약 현재 상태가 [[Rainy -> Rainy, Rainy -> Sunny], [Sunny->Rainy, Sunny->Sunny]] 이고, 여기서 y축 기준으로 max를 취한다는 것은, 다음 번 Rainy와 Sunny 상태 중 지금까지 확률 값이 가장 큰 값을 취한다는 뜻이 된다.

decode_op는 이런 식으로 계속 반복함으로써 결과적으로 가장 나중 상태에서 가장 큰 확률 값을 찾아낸다.

backpt_op는 이렇게 가장 큰 확률을 찾았을 때, 이 확률이 발생한 상태를 찾아가기 위해 필요한 기능을 한다. decode_op와 비슷한 로직으로 계산하는 반면 리턴을 현재 상태 중 값이 큰 상태를 1로 설정한다.

예를 들어, [[Rainy -> Rainy, Rainy -> Sunny], [Sunny->Rainy, Sunny->Sunny]] 이고 argmax를 취한 값이 [1,1]이 나왔다면, 다음 번 Rainy 상태일 때는 Sunny->Rainy가 가장 높은 확률을 가지고, Sunny 상태일 때는 Sunny->Sunny가 가장 높은 확률을 가짐을 뜻한다.

이런 식으로 각 단계에서의 높은 확률 값에 대해 1로 마크를 해준다. 그럼 각각 Rainy 상태일 때의 이전의 상태 정보들 ([-1, 0, 0, 0, 1]) 과 Sunny 상태일 때의 이전의 상태 정보들이 계산된다.

모든 계산이 끝났다면, 이제 최종 확률의 상태에서 역으로 올라가며 높은 상태의 값들을 찾아내자.

viterbi[:,-1].argmax()를 통해 최종 확률 값들 중 높은 확률의 상태 정보를 찾아서 token에 저장하자.

for문을 돌며 이전 상태에서 현재 token에서 마지막 저장된 상태가 됐을 때 가장 높은 확률을 가지는 값의 index를 token의 저장하자. 

결과 token을 print 하면 관측 값에 대한 가장 높은 확률을 가지는 상태 정보를 출력할 수가 있다.