ビタビアルゴリズム
具体例

遠く離れた地に友人がいて、毎日その友人と電話をして彼がその日何をしたかを聞くものとする。その友人は、公園を散歩すること、買い物をすること、部屋を掃除することという3つのことにしか興味が無い。ある日にどれをするかは、その日の天気だけに依存する。その友人が住んでいる地の天気に関する具体的情報は、別経路では全く得られないが、一般的傾向はわかっている。彼が電話で話した毎日の行動に基づいて、その場所の天気を推測してみよう。
天気の変動は離散マルコフ連鎖になっているものとする。状態としては「雨; Rainy」と「晴れ; Sunny」の2つだけだが、直接観測することはできないので、我々にとってはそれが「隠された」状態である。毎日、友人は「散歩; walk」、「買い物; shop」、「掃除; clean」のいずれかを行う可能性がある。彼は何をしたかを電話連絡してくるので、それが「観測された」状態となる。システム全体としては、隠れマルコフモデル (HMM) となる。
その地域の天気の傾向はわかっていて、平均的にその友人が何をする傾向があるかもわかっている。言い換えれば、HMM のパラメータは既知である。これを Python で書くと次のようになる。
states = ('Rainy', 'Sunny')
 
observations = ('walk', 'shop', 'clean')
 
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
 
transition_probability = {
    'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
    'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
    }
 
emission_probability = {
    'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
    'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
    }
このコードにおいて、start_probability は最初に友人が電話してきたときに HMM がどの状態にあるかを表している（つまり、雨の可能性がやや高いということしか知らない）。ここで使われている確率分布は定常時のものではない（定常時の確率分布はだいたい {'Rainy': 0.571, 'Sunny': 0.429} である）。transition_probability は、このマルコフ連鎖での天気の変化を表している。この例では、今日が雨だった場合に翌日が晴れとなる可能性は 30% しかない。emission_probability は、友人がある活動を行う確率を示している。雨だった場合、50% の確率で部屋を掃除する。晴れだった場合、60% の確率で外を散歩する。
友人と三日間続けて話をしたところ、初日は散歩、二日目は買い物、三日目は掃除をしたという。ここで2つの疑問が生じる。この観測されたシーケンスの全体としての確率はどうなるか? そして、この観測結果を説明する最も尤もらしい天気のシーケンスはどうなるか? 第一の疑問には前向きアルゴリズムで答えられる。第二の疑問にはビタビアルゴリズムで答えられる。これら2つのアルゴリズムは構造的に非常に近いので（実際、これらは同じ抽象アルゴリズムのインスタンスである）、1つの関数として次のように実装できる。
def forward_viterbi(y, X, sp, tp, ep):
    T = {}
    for state in X:
        ##          prob.      V. path  V. prob.
        T[state] = (sp[state], [state], sp[state])
    for output in y:
        U = {}
        for next_state in X:
            total = 0
            argmax = None
            valmax = 0
            for source_state in X:
                (prob, v_path, v_prob) = T[source_state]
                p = ep[source_state][output] * tp[source_state][next_state]
                prob *= p
                v_prob *= p
                total += prob
                if v_prob > valmax:
                    argmax = v_path + [next_state]
                    valmax = v_prob
            U[next_state] = (total, argmax, valmax)
        T = U
    ## apply sum/max to the final states:
    total = 0
    argmax = None
    valmax = 0
    for state in X:
        (prob, v_path, v_prob) = T[state]
        total += prob
        if v_prob > valmax:
            argmax = v_path
            valmax = v_prob
    return (total, argmax, valmax)
関数 forward_viterbi は、次のような引数をとる。y は観測シーケンスであり、例では ('walk', 'shop', 'clean') となる。X は隠された状態の集合である（例では states）。sp は初期の確率である（例では start_probability）。tp は遷移確率である（例では transition_probability）。ep は隠された状態から観測された状態への対応確率である（例では emission_probability）。
このアルゴリズムは、T と U というマッピングを使う。これらは、状態から3つ組 (prob, v_path, v_prob) へのマッピングであり、prob は初期状態から現在状態までの全経路の確率、v_path は現在状態までのビタビ経路、v_prob は現在状態までのビタビ経路の確率である。マッピング T は与えられた時点  t についてのこの情報を保持し、メインループで構築する U は  t+1 の時点についての同様の情報を保持する。マルコフ性があるため、 t 以前の時点に関する情報は不要である。
このアルゴリズムでは、まず  T を初期の確率で初期化する。ある状態の全体確率は単にその状態の初期の確率となる。初期状態へのビタビ経路は、その状態のみを含むシングルトン経路である。ビタビ経路の確率は、初期の確率と等しい。
メインループでは、y から順に観測結果を取り出す。T はそこまでの時点での正しい情報を含むが、現在の観測時点に関する情報は含まない。このアルゴリズムでは次に、考えられる次の状態についての3つ組 (prob, v_path, v_prob) を計算する。与えられた次の状態の全体確率 total は、その状態に到達する全経路の確率の総和によって得られる。より正確に言えば、このアルゴリズムは考えられる全ての元の状態について繰り返している。それぞれの元の状態について T は、その状態に到達する全経路の全体確率を保持している。この確率に、その状態で現在の観測値が得られる確率と次の状態に遷移する確率をかける。それによって得られる確率 prob を total に加算する。ビタビ経路の確率も同様に求められるが、その場合は全経路の総和を計算するのではなく、最大値を持つ経路を選択する。初期状態では、最大値 valmax はゼロに設定されている。元の状態について、その状態までのビタビ経路の確率は既知である。この場合も同様に、その状態で現在の観測値が得られる確率と次の状態に遷移する確率をその時点までのビタビ経路の確率にかけ、それが valmax の現在値よりも大きい場合は valmax を置き換える。ビタビ経路そのものは、最大値に対応した状態系列を argmax として保持する。このように計算された3つ組 (prob, v_path, v_prob) が U に格納され、全ての可能な次の状態について U の計算が完了した時点で、それを T に代入する。
最後に総和と最大をとる（最後の実際の観測結果を処理した後に仮想的な観測結果を処理するようにすれば、メインループ内でもできる）。
当初の例にこのアルゴリズムを適用する場合、次のようになる。
def example():
    return forward_viterbi(observations,
                           states,
                           start_probability,
                           transition_probability,
                           emission_probability)
print example()
これにより、['walk', 'shop', 'clean'] という並びの全体確率は 0.033612、ビタビ経路は ['Sunny', 'Rainy', 'Rainy', 'Rainy'] となる。3つ目の観測結果から3つ目の状態と4つ目の状態への遷移が求められるので、ビタビ経路には4つ目の状態も含まれている。つまり、与えられた観測結果から、友人が散歩に出た初日は晴れだったが、その後雨が降り続いている可能性が最も高いと言える。
このアルゴリズムを実装する際、多くの言語では浮動小数点数を使うと思われるが、p が小さいと結果としてアンダーフローを生じる危険性がある。これを防ぐ技法として、確率の対数をとり、計算を全てその対数値で行う方法がある。最終的な値が対数で得られたら、それに適切な指数関数を適用すれば、真の値が求められる。