8.53 비터비 알고리즘과 최적 상태 추정

1. 비터비 알고리즘의 목적

비터비(Viterbi) 알고리즘은 주어진 관측 시퀀스 $\mathbf{o}_{1:T}$ 에 대해, 은닉 마르코프 모델(HMM)에서 가장 가능성이 높은 상태 시퀀스를 찾는 동적 계획법이다. 비터비(A. J. Viterbi)가 1967년에 통신 오류 정정을 위해 제안한 이 알고리즘은 HMM의 디코딩 문제에 대한 최적 해를 제공한다.

2. 최대 사후 경로(MAP Sequence)

비터비 알고리즘은 관측 시퀀스 $\mathbf{o}_{1:T}$ 에 대한 최대 사후(MAP) 상태 시퀀스를 구한다.

$\hat{\mathbf{q}}_{1:T} = \arg\max_{\mathbf{q}_{1:T}}P(\mathbf{q}_{1:T} \vert \mathbf{o}_{1:T}, \lambda) = \arg\max_{\mathbf{q}_{1:T}}P(\mathbf{q}_{1:T}, \mathbf{o}_{1:T} \vert \lambda)$

분모 $P(\mathbf{o}_{1:T} \vert \lambda)$ 이 $\mathbf{q}$ 에 무관하므로 결합 확률의 최대화와 동치이다.

3. 전방-후방과 비터비의 차이

전방-후방 알고리즘: 각 시각에서 가장 가능성이 높은 상태를 독립적으로 선택한다. 이는 시각별 가장 가능성이 높은 상태를 제공하지만, 전체 상태 시퀀스의 일관성을 보장하지 않는다(비허용 전이를 포함할 수 있음).

비터비 알고리즘: 전체 시퀀스로서 가장 가능성이 높은 단일 경로를 제공한다. 상태 전이의 일관성이 보장된다.

4. 비터비 변수와 재귀

비터비 변수 $\delta_t(i)$ 는 시각 $t$ 까지의 모든 가능한 경로 중, 시각 $t$ 에 상태 $s_i$ 에 있으면서 관측 $\mathbf{o}_{1:t}$ 를 생성하는 최대 확률이다.

$\delta_t(i) = \max_{\mathbf{q}_{1:t-1}}P(\mathbf{q}_{1:t-1}, q_t = s_i, \mathbf{o}_{1:t} \vert \lambda)$

4.1 재귀 공식

초기화:

$\delta_1(i) = \pi_i b_i(\mathbf{o}_1), \quad 1 \leq i \leq N$

재귀:

$\delta_{t+1}(j) = \left[\max_{1 \leq i \leq N}\delta_t(i)A_{ij}\right]b_j(\mathbf{o}_{t+1})$

전방 알고리즘과의 차이는 $\sum$ 대신 $\max$ 를 사용한다는 점이다.

역추적 변수:

$\psi_{t+1}(j) = \arg\max_{1 \leq i \leq N}\delta_t(i)A_{ij}$

$\psi_{t+1}(j)$ 는 시각 $t+1$ 의 상태 $s_j$ 로의 최적 경로가 시각 $t$ 에서 출발한 상태의 인덱스를 기록한다.

4.2 종료 및 역추적

종료:

$P^* = \max_{1 \leq i \leq N}\delta_T(i), \quad \hat{q}_T = \arg\max_{1 \leq i \leq N}\delta_T(i)$

역추적: 시각 $t = T - 1, T - 2, \ldots, 1$ 에 대해:

$\hat{q}_t = \psi_{t+1}(\hat{q}_{t+1})$

이렇게 역방향으로 추적하여 전체 최적 경로 $\hat{\mathbf{q}}_{1:T}$ 를 복원한다.

5. 계산 복잡도

비터비 알고리즘의 계산 복잡도는 $O(N^2T)$ 이다. 무차별 대입의 $O(N^T)$ 와 비교하여 현저히 효율적이다.

6. 로그 도메인 구현

확률의 곱에 의한 언더플로를 방지하기 위해 로그 도메인에서 계산하는 것이 표준이다.

$\ln\delta_{t+1}(j) = \max_i[\ln\delta_t(i) + \ln A_{ij}] + \ln b_j(\mathbf{o}_{t+1})$

로그 변환에 의해 곱이 합으로 변환되며, 수치적 안정성이 확보된다.

7. 로봇 공학에서의 비터비 알고리즘

7.1 활동 시퀀스 디코딩

연속 관측 데이터로부터 로봇이나 인간의 활동 시퀀스를 디코딩한다. HMM이 활동 전이 모델을 제공하고, 비터비 알고리즘이 최적 활동 시퀀스를 산출한다.

7.2 지도 매칭(Map Matching)

GPS 궤적이 도로 네트워크의 어느 세그먼트를 따랐는지를 결정하는 문제에서, 도로 세그먼트가 은닉 상태이고 GPS 관측이 방출이다. 비터비 알고리즘이 가장 가능성이 높은 도로 시퀀스를 결정한다.

7.3 고장 상태 시퀀스 추론

다단계 고장 발전 과정(정상 → 초기 고장 → 중간 고장 → 심각 고장)의 최적 시퀀스를 센서 데이터로부터 추론한다.

7.4 행동 분할(Action Segmentation)

로봇의 시범 동작을 원시 행동(primitive)의 시퀀스로 분할하는 데 비터비 디코딩이 사용된다. 각 원시 행동이 HMM 상태이고, 모션 데이터가 관측이다.

8. 빔 탐색(Beam Search)

비터비의 완전한 $O(N^2T)$ 계산이 부담이 될 때, 각 시각에서 상위 $k$ 개의 가장 유망한 상태만 유지하는 빔 탐색이 근사적 해를 제공한다. 큰 상태 공간을 다루는 음성 인식 등에서 널리 사용된다.

9. 참고 문헌

Viterbi, A. J. (1967). “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm.” IEEE Transactions on Information Theory, 13(2), 260–269.
Forney, G. D. (1973). “The Viterbi Algorithm.” Proceedings of the IEEE, 61(3), 268–278.
Rabiner, L. R. (1989). “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.” Proceedings of the IEEE, 77(2), 257–286.
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.

version: 1.0