비터비 알고리즘 (Viterbi / HMM)

비터비 알고리즘 (Viterbi Algorithm)

친구가 매일 뭘 했는지(산책 · 쇼핑 · 청소)만 메신저로 알려준다. 그런데 그 동네 날씨(☀️ 맑음 / ☔ 비)는 직접 볼 수 없다. "행동 기록만 보고, 지난 며칠간 날씨가 어땠을지 가장 그럴듯한 시퀀스를 통째로 맞혀라." 이게 은닉 마르코프 모델(HMM)의 대표 문제이고, 이를 푸는 O(T·N²) 동적 계획법이 비터비 알고리즘이다.

비터비는 1967년 통신용 오류정정 부호를 디코딩하려고 나왔지만, 지금은 스마트폰 자동완성·음성 인식· GPS 경로 맵매칭·유전자 예측·통신 모뎀 어디에나 들어가 있다.

1. 은닉 마르코프 모델의 3가지 확률

HMM 은 "숨은 상태가 마르코프 사슬로 흐르고, 각 상태가 관측을 확률적으로 방출한다"는 모델이다. 필요한 건 딱 3개의 표다.

① 시작 확률 π — 첫날 날씨

맑음	비
0.6	0.4

② 전이 확률 A — 어제 날씨 → 오늘 날씨

from ＼ to	맑음	비
맑음	0.7	0.3
비	0.4	0.6

③ 방출 확률 B — 그날 날씨 → 친구의 행동

상태 ＼ 관측	🚶 산책	🛍️ 쇼핑	🧹 청소
맑음	0.6	0.3	0.1
비	0.1	0.4	0.5

각 행의 합은 1 이다. "비 오는 날엔 청소할 확률이 높다"처럼 상식이 숫자로 들어가 있다.

2. 그리디는 왜 틀리나

"매일 그 행동을 가장 잘 설명하는 날씨를 하나씩 고르면 되지 않나?" — 안 된다. 그렇게 지역적으로 고르면 날씨끼리의 연결 확률(전이 A) 을 무시하게 된다. 어제·오늘·내일을 한 덩어리로 봐야 진짜 최적 경로가 나온다. 아래 데모에서 그리디 경로와 비터비 경로가 갈라지는 걸 직접 볼 수 있다.

3. 점화식 — 최댓값을 이어 붙인다

δ_t(j) = "시각 t 에 상태 j 로 끝나는 경로 중 가장 확률 높은 경로의 확률".

δ_t(j) = max_i [ δ_t−1(i) · A_i→j ] · B_j(o_t)

시작: δ₁(j) = π_j · B_j(o₁) | 역추적: ψ_t(j) = argmax_i [ δ_t−1(i) · A_i→j ]

각 노드는 "이전 열의 어느 노드에서 왔을 때 가장 좋은가"만 기억한다(이게 백포인터 ψ). 마지막 열에서 δ 가 최대인 노드를 찾고, ψ 를 거꾸로 따라가면 전체 최적 상태열이 복원된다.

4. 트렐리스에서 직접 돌려보기

관측 시퀀스

로그 확률로 보기 (언더플로 방지)

후보 전이 (계산됨) 각 노드의 최선 백포인터 ψ 비터비 최적 경로 그리디 경로 (열별 최댓값)

※ δ 값은 확률의 곱이라 열이 늘수록 빠르게 작아진다. 실제 구현은 log 를 취해 덧셈으로 바꾼다 — 위 체크박스를 켜면 log₂ δ (음수, 클수록 좋음)로 표시된다.

5. 코드로 보기

import math

def viterbi(obs, states, start_p, trans_p, emit_p):
    # log 공간: 곱 → 합, 언더플로 방지
    L = lambda p: math.log(p) if p > 0 else -1e18

    delta = [{}]           # delta[t][state] = 최선 로그확률
    psi   = [{}]           # psi[t][state]   = 직전 상태(백포인터)
    for s in states:                                 # t = 0 초기화
        delta[0][s] = L(start_p[s]) + L(emit_p[s][obs[0]])
        psi[0][s] = None

    for t in range(1, len(obs)):
        delta.append({}); psi.append({})
        for j in states:
            best_i, best_v = None, -1e18
            for i in states:                          # 이전 열 N개 후보
                v = delta[t-1][i] + L(trans_p[i][j])
                if v > best_v:
                    best_i, best_v = i, v
            delta[t][j] = best_v + L(emit_p[j][obs[t]])
            psi[t][j]   = best_i                       # 어디서 왔는지 기록

    last = max(states, key=lambda s: delta[-1][s])   # 종료: 최댓값 상태
    path = [last]
    for t in range(len(obs)-1, 0, -1):              # 역추적
        path.append(psi[t][path[-1]])
    return path[::-1], delta[-1][last]

바깥 루프 T (관측 길이) × 안쪽 이중 루프 N² (상태 쌍) = O(T·N²) 시간, O(T·N) 공간. 모든 경우의 수 N^T 를 지수 → 선형으로 접는다.

6. 어디에 쓰이나

통신 · 저장장치: 컨볼루션 부호 / 하드디스크 PRML 채널의 최우도 디코더 (원조 용도)
음성 인식: 음소 HMM 격자에서 "가장 그럴듯한 발음열" 탐색 (딥러닝 이전 표준)
스마트폰 키보드: 오타 섞인 터치 좌표열 → 가장 그럴듯한 단어열 (자동완성·자동수정)
GPS 맵매칭: 튀는 좌표 관측 → 도로망 위 "실제로 달렸을 경로" 복원
생물정보학: DNA 염기 서열에서 유전자 / 인트론·엑손 영역 예측
자연어 처리: 품사 태깅(각 단어의 품사 = 숨은 상태)

7. 한 줄 요약

비터비는 "열마다 각 상태로 끝나는 최고의 경로 하나만 남기고, 어디서 왔는지 화살표를 남긴다"는 동적 계획법이다. 관측이 끝나면 최댓값에서 화살표를 거꾸로 따라가 전역 최적 상태열을 한 번에 얻는다 — 그리디로는 절대 못 얻는 답을, 지수 시간 대신 O(T·N²) 에.