ビタビ復号

スキル上の位置モジュール 2/3 · トピック 2/4

2.2 ビタビ復号

—ラボスコア— / 100合計XP—連続日数—

最も確からしい1つの筋書き

前向きアルゴリズムは、データがどれだけ起こりやすいかを言うために、すべての隠れ経路を足し合わせます。しばしば欲しいのは別のもの、つまりデータを最も高い確率で説明する1つの最良の筋書き（状態の1本の系列）です。それを見つけるのがビタビ復号です。考え方は前向きアルゴリズムとほぼ同じで、違いは1点だけ、前の状態について和を取る代わりに最良のものを選ぶことです。スコア $\delta_t(j)$ （ $t$ 日目に状態 $j$ で終わる最良経路の確率）を持ち、それをもたらした前の状態を後ろ向きポインタとして覚えます。

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

最終日のあと、 $\delta_T$ が最大の状態を選び、ポインタ $\psi$ をたどって戻り、経路全体を読み取ります。実用上の注意が2つあります。1つ目は対数を使うこと。多くの確率の積は $0$ に近づきますが、対数にすれば和になり、対数は単調増加なので最良の経路は変わりません。2つ目は、最良の経路は、各日ごとに最も確からしい状態を別々に選ぶことと同じではないという点です。例が示すように、あとの出来事によって経路が決まることがあります。

再び小・大・大1日目：

\delta_1=(0.54,\ 0.12)

。2日目（大）：穏やかが最もよく来るのは穏やかからで

0.54\cdot0.9\cdot0.1=0.0486

。荒れは荒れから来るのが最良で

0.12\cdot0.8\cdot0.7=0.0672

（穏やかからは

0.54\cdot0.1\cdot0.7=0.0378

）。3日目：荒れは荒れから

0.0672\cdot0.8\cdot0.7=0.0376

、穏やかはわずか

0.0044

。最良の経路は「荒れ・荒れ・荒れ」で確率

0.0376

です。それでも初日だけを見れば確率

0.82

で穏やかに見えました。あとの大きな動きが筋書き全体を荒れのほうへ引っ張ります。この経路は「穏やか・荒れ・荒れ」（

0.0212

）より

1.78

倍起こりやすいです。

ビタビは前向きアルゴリズムの和を最大値に置き換え、後ろ向きポインタを保持する。
最良の経路は、各日を別々に見た最も確からしい状態とは違うことがある。
対数を使う：対数の和ならアンダーフローを避けられ、最良経路は変わらない。

ラボ：採点される内容

2日目のビタビスコア15点
最良経路の確率15点
最良経路の対数10点
別の経路との比較10点
最良経路の最初の状態15点
ビタビの手順10点
用語を結び付ける10点
なぜ対数を使うのか15点

0/ 8問回答済み

1数値で答える15点未回答

$\delta_1=(0.54,\ 0.12)$ で2日目に大きな動きがあったとき、 $\delta_2(S)=\max(0.54\cdot0.1,\ 0.12\cdot0.8)\cdot0.7$ はいくつですか。小数第4位まで答えてください。

d =

許容:± 0.0003

2数値で答える15点未回答

$\delta_2=(0.0486,\ 0.0672)$ で3日目に大きな動きがあったとき、最良経路の確率 $\delta_3(S)=\max(0.0486\cdot0.1,\ 0.0672\cdot0.8)\cdot0.7$ はいくつですか。小数第4位まで答えてください。

d =

許容:± 0.0003

3数値で答える10点未回答

最良経路の確率 $0.0376$ の自然対数はいくつですか。小数第2位まで答えてください。

l =

許容:± 0.02

4数値で答える10点未回答

最良経路（確率 $0.0376$ ）は、経路「穏やか・荒れ・荒れ」（確率 $0.0212$ ）の何倍起こりやすいですか。小数第2位まで答えてください。

r =

許容:± 0.02

5選択15点未回答

初日は小さな動きで、それだけなら穏やかの確率は82%です。「小・大・大」の最良経路の最初の状態は何ですか。

6手順を並べ替える10点未回答

ビタビ復号の手順を正しい順に並べてください。

ドラッグして並べ替えます。または項目にフォーカスし、スペースで持ち上げ、矢印キーで移動、スペースで置きます。

1最終日のあと、スコア最大の状態を選ぶ
2delta を初期確率×最初の出力で始める
3ポインタをたどって戻り経路を読む
4各日・各状態で最良の前の状態を残して記憶する

7対応づけ10点未回答

各用語をその意味に結び付けてください。

左の各項目に対応するものを選んでください。

\delta_t(j)

\psi_t(j)

前向きアルゴリズム

ビタビアルゴリズム

8言葉で説明する15点未回答

1〜2文で、ビタビ復号が通常は確率の対数で書かれる理由と、それが最良の経路を変えない理由を説明してください。

採点基準:多くの確率の積は0に近づきアンダーフローする対数は積を和にし、単調増加なので最良経路は同じ0 / 400文字

数学モードキーボードまたは LaTeX で入力問題1/8 · Ctrl ⏎ で確認

ビタビ復号

スキル上の位置モジュール 2/3 · トピック 2/4

2.2 ビタビ復号

—ラボスコア— / 100合計XP—連続日数—

最も確からしい1つの筋書き

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

再び小・大・大1日目：

\delta_1=(0.54,\ 0.12)

。2日目（大）：穏やかが最もよく来るのは穏やかからで

0.54\cdot0.9\cdot0.1=0.0486

。荒れは荒れから来るのが最良で

0.12\cdot0.8\cdot0.7=0.0672

（穏やかからは

0.54\cdot0.1\cdot0.7=0.0378

）。3日目：荒れは荒れから

0.0672\cdot0.8\cdot0.7=0.0376

、穏やかはわずか

0.0044

。最良の経路は「荒れ・荒れ・荒れ」で確率

0.0376

です。それでも初日だけを見れば確率

0.82

で穏やかに見えました。あとの大きな動きが筋書き全体を荒れのほうへ引っ張ります。この経路は「穏やか・荒れ・荒れ」（

0.0212

）より

1.78

倍起こりやすいです。

ビタビは前向きアルゴリズムの和を最大値に置き換え、後ろ向きポインタを保持する。
最良の経路は、各日を別々に見た最も確からしい状態とは違うことがある。
対数を使う：対数の和ならアンダーフローを避けられ、最良経路は変わらない。

ラボ：採点される内容

2日目のビタビスコア15点
最良経路の確率15点
最良経路の対数10点
別の経路との比較10点
最良経路の最初の状態15点
ビタビの手順10点
用語を結び付ける10点
なぜ対数を使うのか15点

0/ 8問回答済み

1数値で答える15点未回答

$\delta_1=(0.54,\ 0.12)$ で2日目に大きな動きがあったとき、 $\delta_2(S)=\max(0.54\cdot0.1,\ 0.12\cdot0.8)\cdot0.7$ はいくつですか。小数第4位まで答えてください。

d =

許容:± 0.0003

2数値で答える15点未回答

d =

許容:± 0.0003

3数値で答える10点未回答

最良経路の確率 $0.0376$ の自然対数はいくつですか。小数第2位まで答えてください。

l =

許容:± 0.02

4数値で答える10点未回答

最良経路（確率 $0.0376$ ）は、経路「穏やか・荒れ・荒れ」（確率 $0.0212$ ）の何倍起こりやすいですか。小数第2位まで答えてください。

r =

許容:± 0.02

5選択15点未回答

初日は小さな動きで、それだけなら穏やかの確率は82%です。「小・大・大」の最良経路の最初の状態は何ですか。

6手順を並べ替える10点未回答

ビタビ復号の手順を正しい順に並べてください。

ドラッグして並べ替えます。または項目にフォーカスし、スペースで持ち上げ、矢印キーで移動、スペースで置きます。

1最終日のあと、スコア最大の状態を選ぶ
2delta を初期確率×最初の出力で始める
3ポインタをたどって戻り経路を読む
4各日・各状態で最良の前の状態を残して記憶する

7対応づけ10点未回答

各用語をその意味に結び付けてください。

左の各項目に対応するものを選んでください。

\delta_t(j)

\psi_t(j)

前向きアルゴリズム

ビタビアルゴリズム

8言葉で説明する15点未回答

1〜2文で、ビタビ復号が通常は確率の対数で書かれる理由と、それが最良の経路を変えない理由を説明してください。

採点基準:多くの確率の積は0に近づきアンダーフローする対数は積を和にし、単調増加なので最良経路は同じ0 / 400文字

数学モードキーボードまたは LaTeX で入力問題1/8 · Ctrl ⏎ で確認

ビタビ復号

最も確からしい1つの筋書き

ラボ：採点される内容

コードを実行するにはログインしてください。

ビタビ復号

最も確からしい1つの筋書き

ラボ：採点される内容

コードを実行するにはログインしてください。