정의
HMM의 세 가지 근본 문제 중 Likelihood 문제를 풀기 위한 동적 프로그래밍 알고리즘. 관측 시퀀스 O와 HMM λ=(A,B)가 주어졌을 때 P(O|λ)를 효율적으로 계산한다.
문제 설정
- 입력: HMM λ=(A,B,π), 관측 시퀀스 O = o₁o₂…o_T
- 출력: 해당 관측 시퀀스의 우도 P(O|λ)
- 왜 어려운가: hidden state 시퀀스를 모르기 때문에 직접 계산 불가능
순진한 접근법의 한계
모든 가능한 hidden state 시퀀스 Q에 대해 합산:
N개 상태, T 길이의 시퀀스에서 가능한 Q의 수 = N^T → 지수 폭발. T=10, N=5이면 이미 5¹⁰ = 약 천만 개.
Forward Variable (전진 변수)
핵심 아이디어: 부분 결과를 메모이제이션해서 중복 계산 제거.
→ “시간 t까지의 관측 o₁…o_t를 보면서 상태 j에 있을 결합 확률”
알고리즘 (3단계)
1. 초기화 (t=1)
초기 상태 j에서 시작할 확률(πⱼ) × 첫 관측 o₁을 j가 emit할 확률(bⱼ(o₁)).
2. 재귀 (t=2…T)
이전 시간의 모든 상태 i에서 j로 전이할 확률 합산 × o_t를 j가 emit할 확률.
3. 종료
마지막 시점 T에서 모든 상태의 전진 확률 합산 = 전체 우도.
복잡도
| 방법 | 시간 복잡도 |
|---|---|
| 순진한 합산 | O(N^T · T) |
| Forward algorithm | O(N² · T) |
동적 프로그래밍으로 지수 → 다항식으로 단축.
아이스크림 예시 (Eisner Task)
HMM: 상태 {HOT, COLD}, 관측 {1, 2, 3} (아이스크림 개수)
관측 시퀀스 3 1 3에 대해:
- α₁(HOT) = π(HOT) · P(3|HOT) = 0.2 × 0.4 = 0.08
- α₁(COLD) = π(COLD) · P(3|COLD) = 0.8 × 0.1 = 0.08
- α₂(HOT) = [α₁(HOT)·a(H→H) + α₁(COLD)·a(C→H)] · P(1|HOT)
- … (격자 전체에 걸쳐 반복)
Forward 격자를 채우면 α_T의 열 합산이 P(O|λ).
다른 알고리즘과의 관계
- Viterbi: Forward와 구조 동일, 합산(Σ) 대신 최댓값(max) 사용 → Decoding 문제
- Forward-Backward: Forward + Backward pass 조합 → Learning 문제 (EM)
관계
- 20260515-hidden-markov-model — 상위: Forward algorithm이 푸는 문제의 모델
- 20260515-markov-chain — 기반 구조
- 20260515-viterbi-algorithm — 자매: 같은 격자, 다른 연산 (max vs sum)
인용
The key insight is that all the forward paths that contribute to a given cell in the trellis pass through the same state at the same time. We can compute the probability of reaching each cell by summing over all the ways of reaching that cell.
출처
클리핑 · Jurafsky & Martin, SLP3 Appendix A · stanford.edu