読者です 読者をやめる 読者になる 読者になる

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

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


求めたいのは,サイコロの目の系列 $ \mathbf{x} = x_1x_2 \dots x_n $ が得られる確率 $ P( \mathbf{x} ) $ です.

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

\begin{align} P( \mathbf{x} ) = \sum_{ \mathbf{s} } P(\mathbf{x}, \mathbf{s}) \end{align}

と表すことができます.

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

最後の式で,2つ目の確率の条件の部分から $ 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}

となります.

おつかれさまでした.