Viterbi 알고리즘(최적 경로 해법, 오프라인 버전)

안녕하세요
숨겨진 Markov 체인 모델 (HMM)의 최소 비용 계열 해석 (최적 경로)을 찾는 Viterbi 알고리즘
상태수 계열 1 2 4 4 2 1 를 주어 내부의 transition, emission 에는 난수를 사용하고 있습니다. 이번 해는 minimum_cost_path = [0, 1, 3, 3, 1, 0] 를 얻었습니다 1 . 2 로 나타내면 아래 그림이 됩니다.

트렐리스 다이어그램

보충

이번 최적 경로 예에서는 최종 상태가 하나이므로 해는 확정합니다. 그러나 최종 상태가 둘 이상인 경우에는 확정하지 않습니다 경로의 끝은이 새로운 관측치에 대한 의존성을 갖습니다).

실행 예 · 소스

$ ./viterbi.py 1 2 4 4 2 1
0. transition: [0]
1. transition: [0, 0]
2. transition: [1, 1, 1, 1]
3. transition: [3, 3, 2, 3]
4. transition: [1, 3]
5. transition: [1]
minimum_cost_path = [0, 1, 3, 3, 1, 0]

viterbi.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import random

nstates = [int(n) for n in sys.argv[1::]]
COST, STATE = range(2)
INITIAL = (0, 0)  # (cost, state)

def transition(m, n):
    return [[random.random() for _ in range(m)] for _ in range(n)]

def emission(n):
    return [random.random() for _ in range(n)]

def update(cost, trans, emiss):
    costs = [c[COST]+t for c, t in zip(cost, trans)]
    min_cost = min(costs)
    return min_cost + emiss, costs.index(min_cost)

def decodePath(trellis, lastState):
    state = lastState
    path_reversed = [state]
    for rtr in reversed(trellis):
        state = rtr[state][STATE]
        path_reversed.append(state)
    return list(reversed(path_reversed))

### main ###
n_prev = 1
trellis = []
cost = [INITIAL]
for i, n in enumerate(nstates):
    e = emission(n)
    m = transition(n_prev, n)
    n_prev = n
    cost = [update(cost, t, f) for t, f in zip(m, e)]
    trellis.append(cost)
    print(f'{i}. transition:', [c[STATE] for c in cost])

if nstates[-1] == 1:
    state_last = 0
else:
    cost_last = [w[COST] for w in trellis[-1]]
    state_last = cost_last.index(min(cost_last))
    print("last costs =", [round(c,2) for c in cost_last])
path = decodePath(trellis, state_last)
print(f'minimum_cost_path = {path[1:]}')
exit(0)

이번과 같이 해의 일의화(지기)를 마지막으로 정리해(오프라인적으로) 실시하는 것이 아니라, 순차적으로 가지지면 온라인 동작화할 수 있습니다( 「3 」). Viterbi 알고리즘(온라인 버전)

이번 예와 같은 상태수 계열 [1,2,4,4,2,1] 에 의한 그림이, "↩"그림 8 또는 "The Viterbi algorithm"이라는 기사의 그림 4, 5에서도 볼 수 있습니다. The Viterbi Algorithm

참조 : 「↩ (정보 통신 이론)」의 후반의 그림 예. 비터비 알고리즘