비터비(Viterbi) 알고리즘은 기하급수적으로 늘어나는 경우의 수 속에서 어떻게 효율적으로 정답을 찾을 수 있는지 보여주는 동적 계획법(Dynamic Programming)의 정수다. 라는 거대한 우주를 뒤지는 대신, 각 단계에서 ‘지금 여기까지 오는 데 최선이었던 길’만을 기억함으로써 복잡도를 선형적으로 떨어뜨린다. 이는 미래의 결정이 과거의 모든 세부 사항이 아닌, 현재의 상태에만 의존한다는 마르코프 가정이 주는 축복이다.
근거
전체 경로를 다 계산하는 방식은 불가능에 가깝지만, 비터비는 각 셀 에 해당 시점까지의 최대 확률을 저장하고 백포인터(Backpointer)를 남긴다.
“For an HMM with N hidden states and an observation sequence of T observations, there are possible hidden sequences… Instead of using such an extremely exponential algorithm, we use an efficient algorithm called the forward algorithm [and Viterbi].”
이 알고리즘의 승리는 ‘부분 최적해가 전체 최적해의 일부가 된다’는 구조적 통찰에 기반한다. 인생의 모든 경우의 수를 계산할 수 없듯, 알고리즘 역시 효율적인 포기(Max 연산)를 통해 실시간성을 확보한다.
연결된 생각
- 20260605-hidden-markov-models-concept — 비터비 알고리즘이 적용되는 HMM 구조
- 20260605-human-perception-as-hmm-decoding — 인간의 뇌가 무의식적으로 ‘가장 그럴듯한 해석’을 실시간으로 내놓는 기제