8.52 HMM의 전향-후향 알고리즘

1. 전향-후향 알고리즘의 목적

전향-후향 알고리즘(Forward-Backward Algorithm)은 은닉 마르코프 모델(HMM)에서 관측 시퀀스가 주어졌을 때 각 시각의 상태 사후 확률을 효율적으로 계산하는 동적 계획법이다. HMM의 평가 문제와 학습 문제(바움-웰치 알고리즘)의 핵심 구성 요소이다.

2. 전방 변수(Forward Variable)

시각 $t$ 까지의 관측 시퀀스 $\mathbf{o}_{1:t}$ 가 관측되고 현재 상태가 $s_i$ 일 결합 확률을 전방 변수로 정의한다.

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

2.1 재귀 공식

초기화:

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

재귀: 시각 $t$ 에서 $t+1$ 로:

$\alpha_{t+1}(j) = \left[\sum_{i=1}^{N}\alpha_t(i)A_{ij}\right]b_j(\mathbf{o}_{t+1}), \quad 1 \leq j \leq N$

종료: 관측 시퀀스의 가능도:

$P(\mathbf{o}_{1:T} \vert \lambda) = \sum_{i=1}^{N}\alpha_T(i)$

2.2 직관적 해석

$\alpha_t(i)$ 는 “시각 $t$ 까지의 관측을 설명하면서 현재 상태 $s_i$ 에 있을 확률“이다. 재귀식은 “다음 상태 $s_j$ 로 전이할 수 있는 모든 이전 상태 $s_i$ 의 $\alpha$ 값과 전이/관측 확률의 곱의 합“을 나타낸다.

3. 후방 변수(Backward Variable)

시각 $t$ 에 상태 $s_i$ 에 있을 때, 시각 $t+1$ 부터 $T$ 까지의 미래 관측 시퀀스가 발생할 조건부 확률을 후방 변수로 정의한다.

$\beta_t(i) = P(\mathbf{o}_{t+1:T} \vert q_t = s_i, \lambda)$

3.1 재귀 공식

초기화:

$\beta_T(i) = 1, \quad 1 \leq i \leq N$

재귀: 시각 $t+1$ 에서 $t$ 로(시간 역방향):

$\beta_t(i) = \sum_{j=1}^{N}A_{ij}b_j(\mathbf{o}_{t+1})\beta_{t+1}(j), \quad 1 \leq i \leq N$

4. 상태 사후 확률(Posterior Probability)

전방 변수와 후방 변수를 결합하면 각 시각의 상태 사후 확률이 얻어진다.

$\gamma_t(i) = P(q_t = s_i \vert \mathbf{o}_{1:T}, \lambda) = \frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^{N}\alpha_t(j)\beta_t(j)} = \frac{\alpha_t(i)\beta_t(i)}{P(\mathbf{o}_{1:T} \vert \lambda)}$

이는 전체 관측 시퀀스가 주어졌을 때 시각 $t$ 의 상태가 $s_i$ 일 확률이다. 필터링 $P(q_t \vert \mathbf{o}_{1:t})$ 이 현재까지의 관측만을 사용하는 반면, 평활화(smoothing) $P(q_t \vert \mathbf{o}_{1:T})$ 는 미래 관측까지 활용하여 더 정확한 추정을 제공한다.

5. 쌍 확률(Pair Posterior)

시각 $t$ 와 $t+1$ 의 상태 쌍에 대한 사후 확률:

$\xi_t(i, j) = P(q_t = s_i, q_{t+1} = s_j \vert \mathbf{o}_{1:T}, \lambda)$

$\xi_t(i, j) = \frac{\alpha_t(i)A_{ij}b_j(\mathbf{o}_{t+1})\beta_{t+1}(j)}{\sum_{k=1}^{N}\sum_{l=1}^{N}\alpha_t(k)A_{kl}b_l(\mathbf{o}_{t+1})\beta_{t+1}(l)}$

$\xi_t(i, j)$ 는 바움-웰치 알고리즘에서 전이 확률 갱신에 사용된다.

6. 계산 복잡도

전방 변수와 후방 변수의 재귀적 계산은 각각 $O(N^2T)$ 의 계산 복잡도를 갖는다. 단순 무차별 대입(모든 상태 시퀀스 열거)의 $O(N^T)$ 와 비교하면 현저한 효율성 향상이다.

7. 수치적 안정성 고려

전방/후방 변수는 시간에 따라 확률의 곱이 누적되어 매우 작은 값이 되므로 수치적 언더플로(underflow)가 발생한다. 이를 해결하기 위한 방법:

7.1 스케일링(Scaling)

매 시각마다 전방/후방 변수를 정규화한다.

$\tilde{\alpha}_t(i) = \frac{\alpha_t(i)}{c_t}, \quad c_t = \sum_{j=1}^{N}\alpha_t(j)$

로그 가능도는 스케일링 상수로부터 복원된다.

$\ln P(\mathbf{o}_{1:T} \vert \lambda) = \sum_{t=1}^{T}\ln c_t$

7.2 로그 도메인 계산

모든 확률을 로그 도메인에서 계산하며, 합은 log-sum-exp 기법으로 수행한다.

$\ln(a + b) = \ln a + \ln(1 + e^{\ln b - \ln a})$

8. 바움-웰치 알고리즘에서의 활용

전방-후방 알고리즘이 제공하는 $\gamma_t(i)$ 와 $\xi_t(i, j)$ 는 바움-웰치의 M 단계에서 HMM 매개변수 갱신에 직접 사용된다.

$\hat{A}_{ij} = \frac{\sum_{t=1}^{T-1}\xi_t(i, j)}{\sum_{t=1}^{T-1}\gamma_t(i)}, \quad \hat{\pi}_i = \gamma_1(i)$

관측 확률 갱신은 관측 기호의 분포에 따라 계산된다(이산 또는 연속).

9. 로봇 공학에서의 응용

상태 평활화: 오프라인 분석에서 전방-후방 알고리즘에 의한 평활화는 필터링보다 정확한 상태 추정을 제공한다. 사후 경로 분석, 오류 진단 등에 활용된다.

학습 기반 인식기: 활동 인식, 제스처 분류, 음성 인식 등의 HMM 기반 분류기 학습에 바움-웰치 알고리즘이 사용되며, 그 핵심이 전방-후방 알고리즘이다.

10. 참고 문헌

Rabiner, L. R. (1989). “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.” Proceedings of the IEEE, 77(2), 257–286.
Baum, L. E., Petrie, T., Soules, G., & Weiss, N. (1970). “A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains.” The Annals of Mathematical Statistics, 41(1), 164–171.
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.

version: 1.0