記法

\(x_{i…j}\) （ただし \(i \le j\)）は \(i\) 番目から \(j\) 番目の要素からなる部分列 \(x_i\ldots x_j\)を表す．

Backward変数（Backward AlgorithmのDP変数）

Backward Algorithmは，出力列 \(x_{1…T}=x_1\ldots x_T\)が得られる確率を，Forward Algorithmとは逆向きの順序で計算する．その目的は，HMMのパラメータ学習に用いられるBaum-Welch Algorithmなど、周辺確率の計算に用いることである．
Backward変数 \(b_i(t)\) は，出力部分列 \(x_{t+1…T}\) の，時刻 \(t\) における状態が \(s_i\) である場合の条件付確率である．あらゆる状態部分列\(h_{t+1…T}=h_{t+1}\ldots h_T\)について，出力部分列と状態部分列の同時確率が合計される．
\[
b_i(t) \equiv \sum_{h_{t+1…T}} P(x_{t+1…T},h_{t+1…T}|h_t=s_i)
\]

Backward Algorithm

\[
\begin{eqnarray}
\mbox{初期化}: &(t=T)& b_i(T)=1 \mbox{ for all } i>0\\
\mbox{再帰}: &(t=1,\ldots,T)& b_i(t)=\sum_j a_{i,j}e_j(x_{t+1})b_j(t+1)\\
\mbox{終了処理}: & & P(x_{1…T})=\sum_i a_{0,j}e_j(x_1)b_j(1))
\end{eqnarray}
\]