[ML] Viterbi Algorithm (비터비 알고리즘)

Viterbi Algorithm은 특히 Markov information sources (마르코프 정보 소스) 및 Hidden Markov Model (HMM, 은닉 마르코프 모델)의 맥락에서 관찰된 사건의 연속으로 나타나는 가장 가능성이 높은 숨겨진 상태의 연속성 - Viterbi path 라고도 함 - 을 찾는 데 사용되는동적 프로그래밍 (Dynamic programming) 알고리즘이다.

 

이 알고리즘은 Andrew Vitervi가 통신에 사용되는 Convolutional Codes (컨볼루션 코드, 합성 부호) 를 디코딩하기 위한 방법으로 도입했다. 이후 sequence alignment (서열 정렬)을 위한 Bioinformatics (생물정보학), 음성 인식 등 다양한 분야에 적용됐다.

 

아래는 HMM과 관련해 Viterbi Algorithm이 어떻게 작동하는지 에 대한 기본적인 개요는 다음과 같다.

 

1. Initialization (초기화)
   : 처음 인스턴스에서 각 state s에 대해 state s에 있을 초기 확률과 state s에서 첫 번째 관찰 (observation)을 방출(emitting)할 확률의 곱을 계산한다.
   
   
2. Recursion (재귀)
   : 각 후속 시간  및 각 state s에 대해 이전 state에 대해 이전 state에서 해당 state로 도달할 최대 확률을 계산하고, 이전 state에서 현재 state로 전환(transition)할 확률과 현재 state에서 관찰된 이벤트를 내보낼 확률을 곱한다. 
   이 최대 확률로 이어진 경로를 추적한다(back-pointer를 사용해 수행 가능.)
   
   
3. Termination (종료)
   : 마지막 시간 인스턴스에서 확률이 가장 높은 state를 Viterbi path의 최종 state로 선택한다.
   
   
4. Path (State Sequence) Backtracking
   : 최종 상태에서 back-pointer를 따라 가장 확률이 높은 state의 sequence를 검색한다.

 

Viterbi algorithm의 장점은 가능한 모든 state sequence를 완전히 평가하는 대신 (긴 sequence의 경우 계산적으로 금지될 수 있음), 중간 결과를 저장하고 재사용해 가장 가능성이 높은 sequence를 효율적으로 계산한다는 것이다.

 

Viterbi algorithm을 실제로 적용하려면 다음이 필요하다.

1. 모델 내의 state 집합
2. state에 대한 초기 확률 분포
3. state간의 전환(transition) 확률
4. emission probabilities (발출 확률, 즉, state를 기반으로 한 관찰된 사건의 확률)

전반적으로 Viterbi 알고리즘은 observation을 기반으로 숨겨진 state의 가장 확률이 높은 sequence를 추론해야하는 다양한 응용 분야에서 핵심 도구로 사용된다.