Viterbi アルゴリズム（最適経路解法、オフライン版）

こんにちは
隠れMarkov連鎖モデル (HMM) の最小コスト系列解（最適経路）を求める Viterbi アルゴリズムを Python で書きました（今回はオフライン版¹）。
状態数系列 1 2 4 4 2 1 を与え、内部の transition, emission には乱数値を使っています。今回の解は minimum_cost_path = [0, 1, 3, 3, 1, 0] が得られました²。トレリス図で示すと下図となります。

補足

今回の最適経路例では最終状態が一つなので解は確定します。

しかし、もしも最終状態が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)

1. 今回のように解の一意化（枝刈り）を最後にまとめて（オフライン的に）行うのではなく、逐次的に枝刈りするとオンライン動作化できます（「Viterbi アルゴリズム（オンライン版）」）。 ↩

2. 今回例と同じ状態数系列 [1,2,4,4,2,1] による図が、"The Viterbi algorithm", G. David Forney, Jr., Proc. of the IEEE Vol. 61, No. 3, pp. 268-278. March, 1973 の Fig. 8 、もしくは "The Viterbi Algorithm" という記事内の Fig. 4, 5 でも見られます。 ↩

3. 参照：「ビタビ・アルゴリズム（情報通信理論）」の中の後半の図例。 ↩