비터비 알고리즘

1. 개요[편집]

비터비 알고리즘 Viterbi Algorithm
제안	Andrew J. Viterbi (1967)
분류	동적 계획법 (max-plus 재귀)
푸는 문제	은닉 마르코프 모형의 최대 사후확률 상태열
복잡도	시간 O(T·N²) / 메모리 O(T·N)
대표 응용	합성곱 부호 복호, 음성인식, 유전자 예측

매 순간 제일 그럴듯한 상태를 이어 붙이면 되지 않냐고? 그렇게 만든 경로가 애초에 존재하지 않는 경로일 수 있다.

비터비 알고리즘(Viterbi algorithm)은 은닉 마르코프 모형(HMM)처럼 관측열 뒤에 숨은 상태열이 있는 모형에서, 관측 전체를 조건으로 하는 사후확률이 최대인 단일 상태열(MAP 상태열)을 동적 계획법으로 정확히 찾아내는 알고리즘이다. 1967년 앤드루 비터비가 합성곱 부호의 복호법으로 발표했는데, 정작 그 자신은 “이건 교육용 설명 도구였지 실용 알고리즘으로 낼 생각은 아니었다”는 취지의 회고를 남겼다.¹ 지금은 통신 칩, 음성 인식기, 유전체 주석 파이프라인 어디에나 들어가 있다.

핵심은 무식한 탐색과 DP의 격차다. 상태 $N$개, 시각 $T$개면 가능한 상태열은 $N^T$개다. $N=64$, $T=1000$이면 우주가 끝나도 못 센다. 그런데 마르코프 성질 덕분에 “시각 $t$에 상태 $j$로 끝나는 최적 경로”만 각 $(t, j)$마다 하나씩 들고 있으면 충분해서, 비용이 $O(T \cdot N^2)$로 주저앉는다. 동적 계획법 문서가 다루는 최적 부분구조의 가장 실전적인 성공 사례이며, 이 문서는 그중 HMM 복호라는 한 갈래에만 집중한다.

2. 트렐리스 위의 max-plus 재귀[편집]

HMM은 초기 분포 $\pi_i$, 전이확률 $a_{ij} = P(q_t = j \mid q_{t-1} = i)$, 방출확률 $b_j(o) = P(o \mid q_t = j)$로 정의된다. 시간축을 가로로, 상태를 세로로 펼쳐 각 시각의 상태를 다음 시각의 상태와 전부 잇는 층상 그래프를 트렐리스(trellis)라고 부른다. 비터비는 이 트렐리스 위의 최장경로 문제다.

로그를 취해 곱을 합으로 바꾼 형태가 표준 구현이다. $\delta_t(j)$를 “시각 $t$에 상태 $j$로 끝나면서 $o_{1:t}$를 낸 경로 중 최대 로그 결합확률”로 두면,

$$\delta_t(j) = \max_{i} \big[\, \delta_{t-1}(i) + \log a_{ij} \,\big] + \log b_j(o_t)$$

이고 초기값은 $\delta_1(j) = \log \pi_j + \log b_j(o_1)$이다. 동시에 그 최댓값을 준 $i$를 역추적 포인터 $\psi_t(j)$에 적어 둔다. 마지막에 $\hat q_T = \arg\max_j \delta_T(j)$를 잡고 $\hat q_{t-1} = \psi_t(\hat q_t)$로 되짚어 올라가면 상태열이 복원된다.

덧셈과 최댓값만 쓰는 이 구조를 대수학 쪽에서는 max-plus 반환(tropical semiring)이라고 부른다. 곱셈을 덧셈으로, 덧셈을 최댓값으로 갈아끼운 것뿐인데, 확률의 합-곱 알고리즘과 코드 뼈대가 거의 같아진다는 점이 재미있다. 실제로 두 알고리즘의 구현은 보통 연산자 하나만 바꿔 공유한다.

비용을 정리하면 이렇다. 시각마다 $N$개 목적지에 대해 $N$개 출발점을 훑으므로 시간 $O(T \cdot N^2)$, 역추적 포인터를 전부 들고 있어야 하므로 **메모리 $O(T \cdot N)$**이다. $\delta$ 자체는 직전 열 하나만 있으면 되니 $O(N)$이면 충분하지만, 역추적 표는 그렇지 않다는 점이 임베디드 구현에서 늘 병목이 된다.² 전이 행렬이 성겨서 상태당 갈 수 있는 곳이 $d$개뿐이면 시간이 $O(T \cdot N \cdot d)$로 떨어지고, 실제 통신 복호기의 트렐리스가 정확히 이 경우다(합성곱 부호는 상태당 후속이 2개뿐이다).

3. 로그 영역이 선택이 아닌 이유[편집]

$T = 10^4$인 문제에서 확률을 곧이곧대로 곱하면 어떻게 되는지 계산해 보자. 스텝마다 확률이 대략 $10^{-1}$씩 곱해지면 $10^{-10000}$이다. IEEE 754 배정밀도의 하한은 $\approx 10^{-308}$(비정규수까지 써도 $10^{-324}$)이므로, 300스텝쯤에서 전부 0이 되어 모든 경로가 동점이 된다. 부동소수점 연산의 언더플로가 알고리즘을 통째로 망가뜨리는 교과서적 사례다.

그래서 실무 구현은 예외 없이 로그 영역에서 돈다. 비터비는 여기서 유난히 운이 좋은데, 최댓값 연산은 로그를 그대로 통과하기 때문이다($\log \max = \max \log$). 반면 뒤에 나올 순방향 알고리즘은 합을 다뤄야 해서 log-sum-exp 트릭이나 스케일링 계수를 매 시각 따로 관리해야 한다. 확률 0인 전이는 $-\infty$로 두면 자연스럽게 배제되므로, 트렐리스가 성긴(sparse) 모형에서는 그 가지를 아예 건너뛰어 $O(T \cdot N^2)$의 상수를 크게 줄일 수 있다.

4. 순방향 알고리즘과의 결정적 차이[편집]

같은 트렐리스 위에서 최댓값 대신 합을 쓰면 순방향(forward) 알고리즘이 된다.

$$\alpha_t(j) = \Big[\, \sum_{i} \alpha_{t-1}(i)\, a_{ij} \Big]\, b_j(o_t)$$

이 둘이 답하는 질문이 다르다는 것이 핵심이다.

• 순방향-역방향(합-곱) — 각 시각의 주변 사후확률 $P(q_t = j \mid o_{1:T})$를 준다. 시각별로 가장 확률 높은 상태를 뽑는 것을 사후 복호(posterior decoding)라 하는데, 시각별 정확도(기대 오류 개수)를 최소화한다.
• 비터비(최대-곱) — 경로 전체의 확률 $P(q_{1:T} \mid o_{1:T})$를 최대화한다. 시각별로는 최선이 아닐 수 있지만, 반환된 경로는 반드시 모형이 허용하는 경로다.

이 차이는 말장난이 아니다. 사후 복호로 이어 붙인 상태열은 $a_{ij} = 0$인 전이를 포함할 수 있고, 그러면 사후확률이 정확히 0인 상태열이 답으로 나온다. 문법이 있는 문제(음성인식의 발음 사전, 유전자의 엑손-인트론 문법)에서는 이런 답이 아예 무의미하므로, 비터비 쪽이 기본값이다.³ 반대로 각 위치의 신뢰도(confidence)를 함께 보고해야 하면 순방향-역방향이 필요하다. 통신 쪽에서 연판정 출력을 내는 BCJR/MAP 복호기가 정확히 그 자리에 있다.

5. 어디에 쓰이나[편집]

• 합성곱 부호 복호. NASA 심우주 표준이던 구속장 $K=7$, 부호율 1/2 부호는 상태가 $2^{6} = 64$개다. 비터비 복호기는 이 64상태 트렐리스를 실시간으로 돌린다. GSM, CDMA, 위성 통신, 그리고 터보 부호의 구성 요소로도 들어갔다. 하드웨어 구현의 표준 관용구인 add-compare-select(ACS) 유닛이 바로 위 재귀식 한 줄이다.
• 채널 등화(MLSE). 심볼 간 간섭이 있는 채널을 유한 상태 기계로 보면, 최대우도 수열 추정이 그대로 비터비가 된다. 자기 기록의 PRML 검출기도 같은 골격이다.
• 음성 인식. HMM 기반 시대의 디코더는 전부 비터비였고, 어휘가 커지면서 트렐리스가 폭발하자 토큰 패싱 + 빔 가지치기로 진화했다. 심층 학습 시대의 CTC/RNN-T 디코딩도 결국은 정렬 격자 위의 빔 서치라 뼈대가 같다.
• 생물정보학. 유전자 예측기(GENSCAN 계열)와 서열 정렬 프로파일 HMM에서, 엑손·인트론·유전자간 영역 같은 은닉 상태를 서열에 붙이는 주석 작업이 비터비 복호다.
• 품사 태깅·철자 교정 등 자연어 처리의 고전 파이프라인.

6. 근사, 확장, 그리고 사촌들[편집]

$N$이 커지면 $O(N^2)$가 부담스러워진다. 그래서 각 시각에서 상위 $B$개 경로만 남기는 빔 서치(beam search)를 쓴다. 최적성 보장은 사라지지만 비용이 $O(T \cdot B \cdot N)$ 수준으로 내려가고, 실무에서는 빔 폭 몇십이면 최적해를 거의 놓치지 않는다. 최적해 하나가 아니라 상위 $k$개 경로가 필요하면 리스트 비터비를, 각 비트의 신뢰도가 필요하면 SOVA나 BCJR을 쓴다.

모형 파라미터 $(\pi, a, b)$ 자체를 데이터에서 학습해야 할 때도 비터비가 등장한다. 정석은 순방향-역방향으로 얻은 주변 확률을 써서 EM을 도는 바움-웰치 알고리즘이지만, 그 대신 매 반복마다 비터비로 뽑은 최적 경로 하나에 모든 책임을 몰아주고 그 경로 기준으로 빈도를 세는 방식도 널리 쓰인다(비터비 학습, 하드 EM). 훨씬 빠르고 구현이 단순한 대신 우도의 단조 증가 보장을 잃는다. 소프트 할당 대 하드 할당의 트레이드오프는 EM과 k-평균의 관계와 정확히 같은 구도다.

상태 공간이 이산이 아니라 연속이면 이야기가 달라진다. 선형-가우시안 모형에서 비터비에 대응하는 것이 평활화다. 가우시안에서는 최빈값과 평균이 같으므로, 전체 궤적의 MAP 추정은 칼만 필터를 정방향으로 돌린 뒤 RTS 평활기로 역방향을 한 번 더 훑은 결과와 일치한다.⁴ 즉 비터비의 역추적 단계가 하는 일을, 연속 세계에서는 역방향 평활 재귀가 한다. 모형이 비선형·비가우시안이면 입자 필터 계열로 넘어가지만, 그쪽은 최적 경로가 아니라 분포 자체를 표본으로 들고 다닌다는 점에서 목적이 다르다.

트렐리스 대신 게임 트리 위에서 최댓값을 접어 오면 미니맥스 알고리즘, 상태공간 위에서 접어 오면 마르코프 결정 과정의 가치 반복이다. 비터비는 그 셋 중 시간축 버전이라고 보면 계보가 깔끔하게 정리된다.

7. 관련 문서[편집]

• 동적 계획법 — 이 알고리즘이 속한 큰 틀
• 은닉 마르코프 모형
• 칼만 필터 · 입자 필터 — 연속 상태의 사촌들
• 부분관측 마르코프 결정 과정 — 관측이 가려진 세계에서 행동까지 고를 때
• 마르코프 결정 과정 · 미니맥스 알고리즘
• 부동소수점 연산 — 언더플로가 왜 치명적인가
• 통계 · 몬테카를로 방법
• 심층 학습 · 빔 서치

8. Footnotes[편집]

1. 비터비 본인은 이 알고리즘에 특허를 내지 않았다. 대신 나중에 퀄컴을 공동창업해서 CDMA로 훨씬 크게 회수했으니, 결과적으로는 인류에게도 본인에게도 남는 장사였다. ↩

2. 역추적 포인터 $\psi$를 저장하는 $O(T \cdot N)$ 메모리가 임베디드 복호기에서는 종종 병목이다. 그래서 실제 칩은 트레이스백 깊이를 구속장의 5~6배쯤으로 잘라 슬라이딩 윈도로 돌린다. 이론적으로는 근사지만, 그 깊이면 경로들이 이미 하나로 합쳐져 있어서 성능 손실이 사실상 0이다. ↩

3. “제일 그럴듯한 상태열”과 “각 시각에서 제일 그럴듯한 상태”가 다르다는 것은, 시험 문제로 내면 절반이 틀리고 실무에서 내면 리뷰에서 잡히는 국룰 함정이다. 확률이 0인 답을 자신 있게 출력하는 파이프라인은 대체로 여기서 태어난다. ↩

4. 선형-가우시안이라 사후분포가 가우시안이고, 가우시안은 최빈값 = 평균이라서 성립하는 특혜다. 모형이 조금이라도 다봉성을 띠면 이 등식은 즉시 깨진다. 이 시점부터 최적 경로와 평균 궤적은 서로 남남이 된다. ↩