記法

$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}$$