続パタの前向き・後ろ向きアルゴリズムについてのメモ

8章で解説されている前向きアルゴリズムに関するメモです． 私が勉強していてつまずいたところを，本文に即する形で補足します．

---

求めたいのは，サイコロの目の系列 が得られる確率 です．

この確率は潜在変数を用いて

と表すことができます．

\begin{align} \sum_{ \mathbf{s} } \end{align}

は一見普通の和に見えますが，実は

\begin{align} \sum_{ \mathbf{s} } = \sum_{s_1} \sum_{s_2} \sum_{s_3} \dots \sum_{s_n } \end{align}

という恐ろしい形の和です．

\begin{align} P( \mathbf{x}, \mathbf{s}) = \Pi_{ \mathbf{s} } a(s_{t-1}, s_{t}) b(s_t, x_t) \end{align}

この同時確率から $ \mathbf{x} $ のみに関する確率を得るためには，上で述べた恐ろしい $ \mathbf{s} $ に関する周辺化を行う必要があり， $ s_n $ の $ n $ が大きくなると現実的ではありません（$ O(2nc^{n}) $ になります）．

ここで，

\begin{align} P( \mathbf{x}, s_t = w_i ) \end{align}

について考えてみましょう．

\begin{align} P( \mathbf{x}, s_t = w_i ) &= P( x_1 x_2 \dots x_t, s_t = w_i ) P( x_{t+1} x_{t+2} \dots x_{n} | x_1 x_2 \dots x_t, s_t = w_i) \\ &= P(x_1 x_2 \dots x_t, s_t = w_i ) P( x_{t+1} x_{t+2} \dots x{n} | s_t = w_i ) \end{align}

最後の式で，２つ目の確率の条件の部分から $ x_1 x_2 \dots x_t $ が消えていることに気づくと思います．

この消去は条件付き独立の定義によって行われています．

問題文の条件に従ってグラフィカルモデルを書いてみると， $ x_n $ は $ x_1 \dots x_{n-1} $ の値とは独立であることがわかります．

ここで，

\begin{align} \alpha_t (i) = P(x_1 x_2 \dots x_t, s_t = w_i) \end{align}

とします．

$ \alpha_n (i) $ を $ \alpha_{n-1} (i) $を用いて表すことができないか考えてみます．

(唐突感がありますが， $ t = n-1 $とおいて考えてみたらこうなりました)

\begin{align} \alpha_n (i) = \left[ \sum_{j=1}^{c} \alpha_{n-1} (j) a(s_{n-1}, s_n) \right] b(s_{n}, x_{n}) \end{align}

ただし．$ t = 1 $のときは $ \alpha_{1} (i) = \rho_i b(w_i, x_1) $ とします．

得られた確率をよく見ると， $ \alpha_{n} (i) $ は $ P( \mathbf{x}, s_t = w_i ) $であることに気づきます．

つまり，これを $ i $ について周辺化すれば求めたい確率 $ P( \mathbf{x} ) $ を得ることができます．

よって，

\begin{align} P( \mathbf{x} ) = \sum_{i = 1}^c \alpha_{n} (i) \end{align}

となります．

おつかれさまでした．