비터비 알고리즘
예제

모든 마을 주민이 건강(Healthy)하거나 열(Fever)이 나는 두 가지 상태만 있는 마을이 있다고 가정하자. 이 마을에서 오직 마을 의사 만이 각자가 열이 나는지 아닌지 판단할 수 있다. 의사는 환자들에게 몸 상태가 어떤지 질문하여 열의 유무를 진단한다. 마을 사람들은 멀쩡하다(normal), 춥다(cold), 어지럽다(dizzy) 중에서 하나의 답변 만을 할 수 있다.
의사는 환자들의 건강 상태가 이산적인 마르코프 연쇄를 따른다고 생각한다. "건강함", "열이 남"의 두 가지 상태가 존재하지만 의사는 이를 직접적으로 관찰할 수 없고 숨겨져 있다. 하루에 한번 환자는 의사에게 자신의 건강 상태에 따라 "멀쩡함", "추움", "어지러움" 중 한 가지를 얘기할 수 있다.
관측값(멀쩡함, 추움, 어지러움)은 은닉 상태(건강함, 열이 남)와 함께 은닉 마르코프 모형(HMM)을 구성하며, 파이썬으로 나타내면 다음과 같다.
obs = ('normal', 'cold', 'dizzy')
states = ('Healthy', 'Fever')
start_p = {'Healthy': 0.6, 'Fever': 0.4}
trans_p = {
 'Healthy': {'Healthy': 0.7, 'Fever': 0.3},
 'Fever': {'Healthy': 0.4, 'Fever': 0.6}
}
emit_p = {
 'Healthy': {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
 'Fever': {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6}
}
이 코드에서, start_p는 환자의 첫 방문시 HMM이 어느 상태에 있는가에 대한 의사의 생각을 반영한다. (물론 의사는 대부분의 환자가 건강할 것이란 것을 알고 있다) 주어진 전이 확률에 따르면 여기서는 평형 상태가 아닌 특정한 확률 분포 {'Healthy': 0.6, 'Fever': 0.4}를 사용하였다. trans_p는 기저의 마르코프 연쇄에 따른 건강 상태의 변화를 나타낸다. 이 예제에서 오늘 건강한 주민이 다음 날 열이 날 확률은 30% 뿐이다. emit_p는 매 하루마다 환자가 자신의 몸 상태를 어떻게 느끼는지를 나타낸다. 그가 건강하다면 50%의 확률로 자신이 "멀쩡하다"고 느낀다. 만약 열이 난다면 60%의 확률로 "어지럽다"고 느끼게 된다.
환자는 3일간 연속으로 의사를 방문하였고, 의사는 첫날 환자가 "멀쩡하다"고 느꼈고, 이튿날 "춥다"고 느꼈으며, 셋째 날에는 "어지럽다"고 느꼈다는 것을 알게 되었다. 의사에게 질문이 하나 생겼다. 환자가 설명한 관측값에 맞는 가장 가능성 높은 건강 상태의 순서는 무엇인가? 이 질문은 비터비 알고리즘으로 답할 수 있다.
def viterbi(obs, states, start_p, trans_p, emit_p):
 V = [{}]
 for st in states:
 V[0][st] = {"prob": start_p[st] * emit_p[st][obs[0]], "prev": None}
 # Run Viterbi when t > 0
 for t in range(1, len(obs)):
 V.append({})
 for st in states:
 max_tr_prob = max(V[t-1][prev_st]["prob"]*trans_p[prev_st][st] for prev_st in states)
 for prev_st in states:
 if V[t-1][prev_st]["prob"] * trans_p[prev_st][st] == max_tr_prob:
 max_prob = max_tr_prob * emit_p[st][obs[t]]
 V[t][st] = {"prob": max_prob, "prev": prev_st}
 break
 for line in dptable(V):
 print(line)
 opt = []
 # The highest probability
 max_prob = max(value["prob"] for value in V[-1].values())
 previous = None
 # Get most probable state and its backtrack
 for st, data in V[-1].items():
 if data["prob"] == max_prob:
 opt.append(st)
 previous = st
 break
 # Follow the backtrack till the first observation
 for t in range(len(V) - 2, -1, -1):
 opt.insert(0, V[t + 1][previous]["prev"])
 previous = V[t + 1][previous]["prev"]

 print('The steps of states are ' + ' '.join(opt) + ' with highest probability of %s' % max_prob)

def dptable(V):
 # Print a table of steps from dictionary
 yield " ".join(("%12d" % i) for i in range(len(V)))
 for state in V[0]:
 yield "%.7s: " % state + " ".join("%.7s" % ("%f" % v[state]["prob"]) for v in V)
함수 viterbi는 다음과 같은 인수를 갖는다. obs는 ['normal', 'cold', 'dizzy']와 같은 관측값들의 순서이다. states는 숨겨진 상태들의 집합이다. start_p는 초기 확률, trans_p는 전이 확률, emit_p는 출력 확률이다. 코드를 단순하게 하기 위해 관측값들의 순서 obs는 비어있는 경우가 없으며, trans_p[i][j], emit_p[i][j]는 모든 상태 i, j에 대하여 정의되어 있다고 가정한다.
실제 예제에서 전향/비터비 알고리즘은 다음과 같이 사용한다:
viterbi(obs,
 states,
 start_p,
 trans_p,
 emit_p)
스크립트의 실행 결과는 다음과 같다:
$ python viterbi_example.py
 0 1 2
Healthy: 0.30000 0.08400 0.00588
Fever: 0.04000 0.02700 0.01512
The steps of states are Healthy Healthy Fever with highest probability of 0.01512
이에 따르면 ['normal', 'cold', 'dizzy']는 상태 ['Healthy', 'Healthy', 'Fever']에 의해 생성될 가능성이 가장 높다는 것을 알 수 있다. 다시 말하면, 주어진 관측값 하에서 환자는 첫 이틀 동안은 건강했지만 첫날은 '멀쩡함', 둘째 날은 '추위'를 느꼈고, 셋째 날엔 열이 나게 되었다는 것이다.
비터비 알고리즘의 과정은 트렐리스 다이어그램에 의해 도식화 될 수 있다. 비터비 경로는 트렐리스 다이어그램에서의 최단 경로와 같다. 이 병원 예제는 아래와 같이 나타난다. 비터비 경로는 진하게 표시하고 있다: