비터비 알고리즘(Viterbi algorithm)은 주어진 관측 이벤트 시퀀스를 생성했을 가능성이 가장 높은 은닉 상태 시퀀스를 식별하는 동적 프로그래밍 알고리즘이다. 결과로 얻어지는 시퀀스는 종종 비터비 경로(Viterbi path)라고 불린다. 이 알고리즘은 기본 상태가 직접 관측 가능하지 않지만 관측에 영향을 미치는 은닉 마르코프 모델(HMM)에 가장 흔히 적용된다. 예를 들어, 며칠에 걸쳐 환자의 증상을 관찰하는 의사는 이 알고리즘을 사용하여 해당 증상을 유발한 가장 가능성 높은 기저 건강 상태의 시퀀스를 추론할 수 있다.
이 알고리즘은 CDMA 및 GSM 디지털 셀룰러 네트워크, 전화 접속 모뎀, 위성 및 심우주 통신, 802.11 무선 LAN에 사용되는 길쌈 부호 디코딩에 보편적으로 적용되어 왔다. 또한 음성 인식, 음성 합성, 화자 분리, 키워드 검출, 전산 언어학 및 생물정보학에서도 널리 사용된다. 음성-텍스트 시스템에서 음향 신호는 관측 시퀀스 역할을 하고 텍스트 문자열은 은닉 원인 역할을 하며, 비터비 알고리즘은 음향 신호가 주어졌을 때 가장 가능성 높은 텍스트를 찾는다.
역사
비터비 알고리즘은 1967년 잡음이 있는 디지털 통신 링크에서 길쌈 부호를 위한 디코딩 알고리즘으로 이를 제안한 앤드루 비터비(Andrew Viterbi)의 이름을 따서 명명되었다. 이 알고리즘은 여러 번의 독립적 발견의 역사를 가지고 있으며, 비터비, 니들먼과 분쉬, 바그너와 피셔를 포함한 최소 7번의 독립적 발견이 있었다. 1987년에는 품사 태깅을 위한 방법으로 자연어 처리에 도입되었다.
"비터비 경로"와 "비터비 알고리즘"이라는 용어는 확률을 포함한 최대화 문제에 대한 동적 프로그래밍 접근 방식의 표준이 되었다. 통계적 구문 분석에서 동적 프로그래밍 알고리즘은 문자열의 가장 가능성 높은 단일 문맥 자유 유도(파싱)를 발견할 수 있으며, 이를 일반적으로 "비터비 파싱"이라고 한다. 또 다른 응용 분야는 표적 추적으로, 알고리즘은 관측 시퀀스에 최대 우도를 할당하는 추적 경로를 계산한다.
알고리즘 개요
은닉 상태 집합 S, 가능한 방출(관측) 집합 M, 그리고 T개의 관측 시퀀스 o0, o1, ..., oT-1을 가진 은닉 마르코프 모델이 주어졌을 때, 비터비 알고리즘은 해당 관측을 생성했을 가능성이 가장 높은 은닉 상태 시퀀스를 찾는다. 각 시간 단계 t에서 알고리즘은 ot까지의 관측만 고려하는 부분 문제를 해결한다.
크기가 T × |S|인 두 개의 행렬이 구성된다. 행렬 Pt,s는 관측 t에서 상태 s에 도달하는 최대 확률을 포함하며, 이는 그 상태로 이어지는 모든 가능한 상태 시퀀스 중에서의 값이다. 행렬 Qt,s는 이 최대 확률 상태 시퀀스에서 s 이전에 사용된 이전 상태를 추적한다.
πs와 ar,s를 각각 초기 확률과 전이 확률이라고 하고, bs,o를 상태 s에서 o를 관측할 확률이라고 하자. 그러면 P의 값은 점화 관계로 주어진다. 시간 t = 0에서 Pt,s는 πs에 bs,o0을 곱한 값과 같다. t > 0의 경우, Pt,s는 모든 이전 상태 r에 대한 (Pt-1,r × ar,s × bs,ot)의 최대값과 같다. 행렬을 채운 후, 알고리즘은 Q 행렬을 사용하여 마지막 시간 단계에서 가장 높은 확률을 가진 상태에서 역추적하여 가장 가능성 높은 상태 시퀀스를 재구성한다.
통신 분야 응용
이 알고리즘은 현대 디지털 통신의 초석이다. 이는 많은 무선 및 유선 시스템에서 사용되는 오류 정정 부호인 길쌈 부호를 디코딩한다. CDMA 및 GSM 셀룰러 네트워크에서 비터비 알고리즘은 잡음과 간섭에도 불구하고 전송된 데이터를 복구하는 데 도움을 준다. 전화 접속 모뎀, 위성 링크 및 심우주 통신 시스템도 이에 의존한다. 802.11 무선 LAN 표준은 안정적인 데이터 전송을 위해 비터비 디코딩을 통합한다.
알고리즘의 효율성은 동적 프로그래밍 특성에서 비롯된다. 이는 가능한 모든 상태 시퀀스를 철저히 열거하는 대신 중간 확률을 저장하고 최적성 원리를 사용한다.这使得即使在资源受限的设备上，也能实时解码长序列。
음성 및 언어 분야 응용
음성 인식에서 비터비 알고리즘은 음향 특징을 음소 또는 단어 모델과 정렬한다. 음향 신호는 관측 시퀀스이고 텍스트 문자열은 은닉 원인이다. 알고리즘은 음향 신호가 주어졌을 때 가장 가능성 높은 텍스트 문자열을 찾아 정확한 전사를 가능하게 한다. 또한 음성 합성에서 가장 자연스러운 음성 단위 시퀀스를 선택하고, 화자 분리에서 누가 언제 말했는지 결정하는 데 사용된다.
전산 언어학에서 이 알고리즘은 품사 태깅에 적용되며, 여기서 은닉 상태는 문법 범주이고 관측은 단어이다. 또한 통계적 구문 분석을 지원하여 문장에 대한 가장 가능성 높은 파싱 트리를 찾는다. 생물정보학에서는 DNA 또는 단백질 서열을 관측으로, 기능적 요소를 은닉 상태로 취급하여 생물학적 서열 정렬과 유전자 구조 예측을 돕는다.
관련 기법
비터비 알고리즘은 가능한 모든 상태 시퀀스에 대한 확률을 계산하는 전방-후방 알고리즘과 같은 다른 동적 프로그래밍 방법과 밀접하게 관련되어 있다. 또한 시퀀스 생성에 사용되는 휴리스틱 검색 기법인 빔 검색과 개념적 기반을 공유한다. 현대의 기계 학습 및 인공 지능 시스템, 특히 시퀀스-투-시퀀스 모델과 대규모 언어 모델을 포함하는 시스템에서는 상태 공간이 크기 때문에 정확한 비터비 디코딩보다 빔 검색이 선호되는 경우가 많다.
신경망 접근 방식의 부상에도 불구하고 비터비 알고리즘은 하이브리드 시스템에서 여전히 관련성을 유지한다. 예를 들어, 음성 인식에서 신경망 음향 모델의 출력을 디코딩하거나 자연어 처리 작업에서 구조적 제약을 강제하는 데 사용될 수 있다. 수학적 명확성과 효율성 덕분에 고전적 및 현대적 응용 분야 모두에서 계속 사용되고 있다.