비터비 알고리즘

비터비 알고리즘은 은닉 마르코프 모형 등에서 관측된 사건들의 순서를 야기한 가장 가능성 높은 은닉 상태들의 순서(비터비 경로, 영어: Viterbi path)를 찾기 위한 동적 계획법 알고리즘을 말한다.

일반적으로 CDMA, GSM 모두를 포함한 셀룰러 이동통신, 다이얼업 모뎀, 위성 통신, 심우주 통신, 802.11 무선랜에서 사용하는 길쌈 부호를 해독하는데 사용하였으나 지금은 음성 인식, 음성 합성, 화자 구분, 키워드 검출, 전산언어학, 생물정보학 분야에서도 널리 활용되고 있다. 예를 들어 음성 인식(Speech to Text)에서는 음향 신호를 관측된 사건들의 순서라고 하면, 문자열은 이러한 음향 신호를 야기한 "숨겨진 원인(hidden cause)"으로 간주된다. 이 때 비터비 알고리즘은 주어진 음향 신호에 대한 가장 가능성 높은 문자열을 찾아내는데 사용된다.

역사

비터비 알고리즘은 1967년 잡음 있는 통신 링크 상에서 길쌈 부호의 해독 알고리즘으로 이를 제안한 앤드류 비터비의 이름에서 유래하였다. 그러나 비터비 자신은 물론 니들만-분쉬, 바그너-피셔 등 최소 7번 이상의 독립적인 발견에 의한 복수 발명의 대상으로 본다.

"비터비 경로"와 "비터비 알고리즘"은 확률과 관련된 극대화 문제의 동적 계획법 알고리즘의 표준 용어가 되었다. 예를 들어 통계적 파싱 분야에서 문맥으로부터 자유로운, 가장 가능성 높은 단일 유도체 문자열을 찾아내는데 사용되는 동적 계획법 알고리즘은 "비터비 파스(Viterbi Parse)"라고 부른다.

예제

모든 마을 주민이 건강(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%의 확률로 "어지럽다"고 느끼게 된다.

본 예제의 HMM에 대한 그래픽적 표현

환자는 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']에 의해 생성될 가능성이 가장 높다는 것을 알 수 있다. 다시 말하면, 주어진 관측값 하에서 환자는 첫 이틀 동안은 건강했지만 첫날은 '멀쩡함', 둘째 날은 '추위'를 느꼈고, 셋째 날엔 열이 나게 되었다는 것이다.

비터비 알고리즘의 과정은 트렐리스 다이어그램에 의해 도식화 될 수 있다. 비터비 경로는 트렐리스 다이어그램에서의 최단 경로와 같다. 이 병원 예제는 아래와 같이 나타난다. 비터비 경로는 진하게 표시하고 있다:

비터비 알고리즘을 나타낸 트렐리스 다이어그램. 셋째 날 이후 가장 가능성 높은 상태 순서는 ['Healthy', 'Healthy', 'Fever']이다.