Viterbi アルゴリズム（オンライン版）

こんにちは
「Viterbi アルゴリズム（最適経路解法）」（オフライン版）を少し修正し、1ステップ毎（観測値が入力される毎）にオンライン的に最適経路解 path を求めました¹。

逐次的に（枝刈りが行われ）、解の確定部の長さも次第に伸びていきます。前提などの説明は元記事の方にあります（今回実行例の状態数系列も同じく 1 2 4 4 2 1 を与えています）。

$ ./viterbi.py 1 2 4 4 2 1
0. transition: [0]
 path = [0]
1. transition: [0, 0]
 path = [0]
2. transition: [1, 1, 1, 1]
 path = [0, 1]
3. transition: [1, 1, 2, 1]
 path = [0, 1]
4. transition: [0, 3]
 path = [0, 1, 1]
5. transition: [1]
 path = [0, 1, 1, 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 single_element(states):
    return list(states) if len(states) == 1 else []

def decodePath(trellis, lastState=None):
    if lastState is not None:
        states = set([lastState])
    else:
        if trellis == []:
            return []
        states = set(range(len(trellis[-1])))
    path_reversed = single_element(states)
    for rtr in reversed(trellis):
        states = {rtr[i][STATE] for i in states}
        path_reversed += single_element(states)
    return list(reversed(path_reversed))

### main ###
n_prev = 1
path = []
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)
    path += decodePath(trellis[len(path)::])
    print(f'{i}. transition:', [c[STATE] for c in cost])
    print(f' path = {path[1:]}')

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

exit(0)

1. Rastislav Srámek, The On-line Viterbi algorithm (2007) にも、同様のオンライン版 Viterbi アルゴリズムが議論されていました。 ↩