はじめに
PRML解答例まとめ を参照
演習 13.1
8.2節で議論した有向分離のテクニックを使って図13.3に示す全部でN N N 個のノードをもつマルコフモデルが、n = 2 , … , N n=2, \ldots, N n = 2 , … , N について条件付き独立性
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x n ∣ x n − 1 ) (13.3)
p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right)=p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}\right) \tag{13.3}
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x n ∣ x n − 1 ) ( 13.3 )
を満たすことを示せ.同様に、図13.4のグラフで記述される全部でN N N 個のノードをもつモデルが、n = 3 , … , N n=3,\ldots,N n = 3 , … , N について以下の条件付き独立性を満たすことを示せ.
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x n ∣ x n − 1 , x n − 2 ) (13.122)
p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right)=p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}, \mathbf{x}_{n-2}\right) \tag{13.122}
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x n ∣ x n − 1 , x n − 2 ) ( 13.122 )
.
※8.2.2 有向分離の節で用いられた手法で考える。図のようにA , B , C A, B, C A , B , C の部分集合を指定する。A A A に属する任意のノードからB B B に属するノードへの可能な経路は必ずC C C を通ることになる。
今、C C C は観測されており、head-to-tailとなっているので、P.91の議論からA A A からB B B への経路はC C C で遮断されており、A ⊥ ⊥ B ∣ C A \perp \!\!\! \perp B \mid C A ⊥ ⊥ B ∣ C が成立する。これより
p ( A , B ∣ C ) = p ( A ∣ C ) p ( B ∣ C )
\begin{aligned}
p(A,B\mid C) &= p(A\mid C)p(B\mid C) \\
\end{aligned}
p ( A , B ∣ C ) = p ( A ∣ C ) p ( B ∣ C )
が成立する。両辺にp ( C ) p(C) p ( C ) をかけると
p ( A , B , C ) = p ( A , C ) p ( B ∣ C )
\begin{aligned}
p(A,B, C) &= p(A,C)p(B\mid C) \\
\end{aligned}
p ( A , B , C ) = p ( A , C ) p ( B ∣ C )
となる。
問題は今p ( x n ∣ x 1 , … , x n − 1 ) = p ( B ∣ A , C ) p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right) = p(B\mid A, C) p ( x n ∣ x 1 , … , x n − 1 ) = p ( B ∣ A , C ) なので
p ( B ∣ A , C ) = p ( A , B , C ) p ( A , C ) = p ( B ∣ C )
\begin{aligned}
p(B\mid A, C) &= \frac{p(A, B, C)}{p(A,C)} \\
&=p(B\mid C)
\end{aligned}
p ( B ∣ A , C ) = p ( A , C ) p ( A , B , C ) = p ( B ∣ C )
これを書き直すと
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x n ∣ x n − 1 ) (13.3)
p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right)=p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}\right) \tag{13.3}
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x n ∣ x n − 1 ) ( 13.3 )
が得られる。
二次マルコフ連鎖の場合、n = 3 n=3 n = 3 について( 13.122 ) (13.122) ( 13.122 ) 式は自明に成立する。
n = 4 , … , N n=4,\ldots,N n = 4 , … , N の二次マルコフ連鎖の場合は上の図のようになる。このとき、同様にA A A からB B B への経路はC C C に含まれるすべてのノードで遮断されている。つまりA ⊥ ⊥ B ∣ C A \perp \!\!\! \perp B \mid C A ⊥ ⊥ B ∣ C が成立する。これより
p ( x n ∣ x 1 , … , x n − 1 ) = p ( B ∣ A , C ) = p ( A , B , C ) p ( A , C ) = p ( B ∣ C ) = p ( x n ∣ x n − 1 , x n − 2 )
\begin{aligned}
p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right) &= p(B\mid A, C) \\
&= \frac{p(A, B, C)}{p(A,C)} \\
&=p(B\mid C) \\
&=p(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}, \mathbf{x}_{n-2})
\end{aligned}
p ( x n ∣ x 1 , … , x n − 1 ) = p ( B ∣ A , C ) = p ( A , C ) p ( A , B , C ) = p ( B ∣ C ) = p ( x n ∣ x n − 1 , x n − 2 )
よって( 13.122 ) (13.122) ( 13.122 ) 式が導かれた。
演習 13.2
図13.3の有向グラフに対応する同時確率分布
p ( x 1 , … , x N ) = p ( x 1 ) ∏ n = 2 N p ( x n ∣ x n − 1 ) (13.2)
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}\right)=p\left(\mathbf{x}_{1}\right) \prod_{n=2}^{N} p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}\right) \tag{13.2}
p ( x 1 , … , x N ) = p ( x 1 ) n = 2 ∏ N p ( x n ∣ x n − 1 ) ( 13.2 )
について考えよう。確率の加法・乗法定理を用い、この同時確率がn = 2 , … , N n=2, \ldots, N n = 2 , … , N について条件付き独立性
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x n ∣ x n − 1 ) (13.3)
p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right)=p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}\right) \tag{13.3}
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x n ∣ x n − 1 ) ( 13.3 )
を満たすことを示せ。同様に、同時分布
p ( x 1 , … , x N ) = p ( x 1 ) p ( x 2 ∣ x 1 ) ∏ n = 3 N p ( x n ∣ x n − 1 , x n − 2 ) (13.4)
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}\right)=p\left(\mathbf{x}_{1}\right) p\left(\mathbf{x}_{2} \mid \mathbf{x}_{1}\right) \prod_{n=3}^{N} p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}, \mathbf{x}_{n-2}\right) \tag{13.4}
p ( x 1 , … , x N ) = p ( x 1 ) p ( x 2 ∣ x 1 ) n = 3 ∏ N p ( x n ∣ x n − 1 , x n − 2 ) ( 13.4 )
によって記述される二次マルコフモデルが、n = 3 , … , N n=3,\ldots,N n = 3 , … , N について以下の条件付き独立性を満たすことを示せ。
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x n ∣ x n − 1 , x n − 2 ) (13.123)
p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right)=p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}, \mathbf{x}_{n-2}\right) \tag{13.123}
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x n ∣ x n − 1 , x n − 2 ) ( 13.123 )
( 13.3 ) (13.3) ( 13.3 ) の左辺を展開し、x n \mathbf{x}_{n} x n で周辺化しておく。
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x 1 , … , x n ) p ( x 1 , … , x n − 1 ) = p ( x 1 , … , x n ) ∑ x n p ( x 1 , … , x n )
\begin{aligned}
p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right) &= \frac{p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right)}{p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right)} \\
&= \frac{p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right)}{\sum_{\mathbf{x}_{n}} p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right)}
\end{aligned}
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x 1 , … , x n − 1 ) p ( x 1 , … , x n ) = ∑ x n p ( x 1 , … , x n ) p ( x 1 , … , x n )
そこで、( 13.2 ) (13.2) ( 13.2 ) 式を利用してp ( x 1 , … , x n ) p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right) p ( x 1 , … , x n ) を求める。
p ( x 1 , … , x n ) = ∑ x n + 1 ⋯ ∑ x N p ( x 1 , … , x N ) = ∑ x n + 1 ⋯ ∑ x N p ( x 1 ) ∏ m = 2 N p ( x m ∣ x m − 1 ) = p ( x 1 ) ∏ m = 2 n p ( x m ∣ x m − 1 )
\begin{aligned} p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right) &=\sum_{\mathbf{x}_{n+1}} \cdots \sum_{\mathbf{x}_{N}} p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}\right) \\ &=\sum_{\mathbf{x}_{n+1}} \cdots \sum_{\mathbf{x}_{N}} p\left(\mathbf{x}_{1}\right) \prod_{m=2}^{N} p\left(\mathbf{x}_{m} \mid \mathbf{x}_{m-1}\right) \\ &=p\left(\mathbf{x}_{1}\right) \prod_{m=2}^{n} p\left(\mathbf{x}_{m} \mid \mathbf{x}_{m-1}\right) \end{aligned}
p ( x 1 , … , x n ) = x n + 1 ∑ ⋯ x N ∑ p ( x 1 , … , x N ) = x n + 1 ∑ ⋯ x N ∑ p ( x 1 ) m = 2 ∏ N p ( x m ∣ x m − 1 ) = p ( x 1 ) m = 2 ∏ n p ( x m ∣ x m − 1 )
と書けるので、もう一度p ( x n ∣ x 1 , … , x n − 1 ) p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right) p ( x n ∣ x 1 , … , x n − 1 ) を計算すると
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x 1 , … , x n ) ∑ x n p ( x 1 , … , x n ) = p ( x 1 ) ∏ m = 2 n p ( x m ∣ x m − 1 ) ∑ x n p ( x 1 ) ∏ m = 2 n p ( x m ∣ x m − 1 ) = p ( x n ∣ x n − 1 ) ∑ x n p ( x n ∣ x n − 1 ) = p ( x n ∣ x n − 1 )
\begin{aligned}
p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right) &= \frac{p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right)}{\sum_{\mathbf{x}_{n}} p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right)} \\
&= \frac{p\left(\mathbf{x}_{1}\right) \prod_{m=2}^{n} p\left(\mathbf{x}_{m} \mid \mathbf{x}_{m-1}\right)}{\sum_{\mathbf{x}_{n}} p\left(\mathbf{x}_{1}\right) \prod_{m=2}^{n} p\left(\mathbf{x}_{m} \mid \mathbf{x}_{m-1}\right)} \\
&= \frac{p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}\right)}{\sum_{\mathbf{x}_{n}} p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}\right)} \\
&= p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}\right)
\end{aligned}
p ( x n ∣ x 1 , … , x n − 1 ) = ∑ x n p ( x 1 , … , x n ) p ( x 1 , … , x n ) = ∑ x n p ( x 1 ) ∏ m = 2 n p ( x m ∣ x m − 1 ) p ( x 1 ) ∏ m = 2 n p ( x m ∣ x m − 1 ) = ∑ x n p ( x n ∣ x n − 1 ) p ( x n ∣ x n − 1 ) = p ( x n ∣ x n − 1 )
途中でx n \mathbf{x}_{n} x n に依存する項以外が分母分子でキャンセルされることを用いた。これより、( 13.3 ) (13.3) ( 13.3 ) の右辺が得られた。
二次マルコフモデルについても同様に行うと、( 13.4 ) (13.4) ( 13.4 ) の同時分布からはじめて
p ( x 1 , … , x n ) = ∑ x n + 1 ⋯ ∑ x N p ( x 1 , … , x N ) = ∑ x n + 1 ⋯ ∑ x N p ( x 1 ) p ( x 2 ∣ x 1 ) ∏ m = 3 N p ( x m ∣ x m − 1 , x m − 2 ) = p ( x 1 ) p ( x 2 ∣ x 1 ) ∏ m = 3 n p ( x m ∣ x m − 1 , x m − 2 )
\begin{aligned} p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right) &=\sum_{\mathbf{x}_{n+1}} \cdots \sum_{\mathbf{x}_{N}} p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}\right) \\ &=\sum_{\mathbf{x}_{n+1}} \cdots \sum_{\mathbf{x}_{N}} p\left(\mathbf{x}_{1}\right) p\left(\mathbf{x}_{2} \mid \mathbf{x}_{1}\right) \prod_{m=3}^{N} p\left(\mathbf{x}_{m} \mid \mathbf{x}_{m-1}, \mathbf{x}_{m-2}\right) \\ &=p\left(\mathbf{x}_{1}\right) p\left(\mathbf{x}_{2} \mid \mathbf{x}_{1}\right) \prod_{m=3}^{n} p\left(\mathbf{x}_{m} \mid \mathbf{x}_{m-1}, \mathbf{x}_{m-2}\right) \end{aligned}
p ( x 1 , … , x n ) = x n + 1 ∑ ⋯ x N ∑ p ( x 1 , … , x N ) = x n + 1 ∑ ⋯ x N ∑ p ( x 1 ) p ( x 2 ∣ x 1 ) m = 3 ∏ N p ( x m ∣ x m − 1 , x m − 2 ) = p ( x 1 ) p ( x 2 ∣ x 1 ) m = 3 ∏ n p ( x m ∣ x m − 1 , x m − 2 )
となるので、
p ( x n ∣ x 1 , … , x n − 1 ) = p ( x 1 , … , x n ) ∑ x n p ( x 1 , … , x n ) = p ( x 1 ) p ( x 2 ∣ x 1 ) ∏ m = 3 n p ( x m ∣ x m − 1 , x m − 2 ) ∑ x n p ( x 1 ) p ( x 2 ∣ x 1 ) ∏ m = 3 n p ( x m ∣ x m − 1 , x m − 2 ) = p ( x n ∣ x n − 1 , x n − 2 ) ∑ x n p ( x n ∣ x n − 1 , x n − 2 ) = p ( x n ∣ x n − 1 , x n − 2 )
\begin{aligned} p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right) &=\frac{p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right)}{\sum_{\mathbf{x}_{n}} p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right)} \\ &=\frac{p\left(\mathbf{x}_{1}\right) p\left(\mathbf{x}_{2} \mid \mathbf{x}_{1}\right) \prod_{m=3}^{n} p\left(\mathbf{x}_{m} \mid \mathbf{x}_{m-1}, \mathbf{x}_{m-2}\right)}{\sum_{\mathbf{x}_{n}} p\left(\mathbf{x}_{1}\right) p\left(\mathbf{x}_{2} \mid \mathbf{x}_{1}\right) \prod_{m=3}^{n} p\left(\mathbf{x}_{m} \mid \mathbf{x}_{m-1}, \mathbf{x}_{m-2}\right)} \\
&= \frac{p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}, \mathbf{x}_{n-2}\right)}{\sum_{\mathbf{x}_{n}} p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}, \mathbf{x}_{n-2}\right)} \\
&= p\left(\mathbf{x}_{n} \mid \mathbf{x}_{n-1}, \mathbf{x}_{n-2}\right)
\end{aligned}
p ( x n ∣ x 1 , … , x n − 1 ) = ∑ x n p ( x 1 , … , x n ) p ( x 1 , … , x n ) = ∑ x n p ( x 1 ) p ( x 2 ∣ x 1 ) ∏ m = 3 n p ( x m ∣ x m − 1 , x m − 2 ) p ( x 1 ) p ( x 2 ∣ x 1 ) ∏ m = 3 n p ( x m ∣ x m − 1 , x m − 2 ) = ∑ x n p ( x n ∣ x n − 1 , x n − 2 ) p ( x n ∣ x n − 1 , x n − 2 ) = p ( x n ∣ x n − 1 , x n − 2 )
を得る。
演習 13.3
有向分離を用いて、図13.5の有向グラフで表現される状態空間モデルにおける観測データの分布p ( x 1 , … , x N ) p(\mathbf{x}_1,\ldots,\mathbf{x}_N ) p ( x 1 , … , x N ) が何の条件付き独立性も満足せず、したがって、どのような有限次数のマルコフ性ももたないことを示せ.
図13.5によると、任意の2つの変数x n \mathbf{x}_n x n とx m \mathbf{x}_m x m , m ≠ n m \neq n m = n について、それぞれのノード間には直接的な経路は存在せず、z \mathbf{z} z 変数に対応する1つ以上のノードを通過する経路が存在している。これらのノードはいずれも観測データの分布p ( x 1 , … , x N ) p(\mathbf{x}_1,\ldots,\mathbf{x}_N ) p ( x 1 , … , x N ) の条件集合に含まれていない。したがって、x n \mathbf{x}_n x n とx m \mathbf{x}_m x m の間には遮断されていない経路が存在し、モデルは条件付き独立性または有限次マルコフ性を満たさないことになる。
演習 13.4
線形回帰モデルやニューラルネットワークのように、出力密度がパラメトリックなモデルp ( x ∣ z , w ) p(\mathbf{x}\mid \mathbf{z},\mathbf{w}) p ( x ∣ z , w ) で表される隠れマルコフモデルを考えよう。ここで、w \mathbf{w} w は適応パラメータのベクトルである。データから最尤推定によってパラメータw \mathbf{w} w を学習する方法を述べよ.
教科書p.330に記載されている、「隠れマルコフモデルとして離散分布、ガウス分布、混合ガウス分布といった広い範囲の出力分布に加えて、ニューラルネットワークなどの識別的モデルを利用することも可能」という記述への補足のための演習問題。
教科書では、出力分布p ( x n ∣ ϕ k ) p(\mathbf{x}_n|\phi_k) p ( x n ∣ ϕ k ) としてガウス分布(p.335)や離散多項分布(p.336)の例が記載されている。このパラメータϕ \phi ϕ をw \mathbf{w} w で置き換えると、識別的モデルにおいても同様の定式化が可能。
実際の更新式の形は、回帰モデルの形や、回帰モデルがどのように使われているかに依って異なる。一例としては、図13.8(p.351)ではx \mathbf{x} x の生成密度が、隠れ変数z \mathbf{z} z だけでなく観測変数系列u \mathbf{u} u に依存する。
この場合、回帰モデルはu \mathbf{u} u からx \mathbf{x} x への写像(写像の関数形がz \mathbf{z} z に応じて異なる)とみなすことができる。
ニューラルネットワークのような非線形な関数形では、Mステップにおけるw \mathbf{w} w の最適解が解析的に解けないことが多い。
演習 13.5
隠れマルコフモデルの初期状態確率と遷移確率のパラメータについてのMステップの方程式
π k = γ ( z 1 k ) ∑ j = 1 K γ ( z 1 j ) (13.18)
\pi_{k}=\frac{\gamma\left(z_{1 k}\right)}{\sum_{j=1}^{K} \gamma\left(z_{1 j}\right)} \tag{13.18}
π k = ∑ j = 1 K γ ( z 1 j ) γ ( z 1 k ) ( 13.18 )
A j k = ∑ n = 2 N ξ ( z n − 1 , j , z n k ) ∑ l = 1 K ∑ n = 2 N ξ ( z n − 1 , j , z n l ) (13.19)
A_{j k}=\frac{\sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n k}\right)}{\sum_{l=1}^{K} \sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n l}\right)} \tag{13.19}
A jk = ∑ l = 1 K ∑ n = 2 N ξ ( z n − 1 , j , z n l ) ∑ n = 2 N ξ ( z n − 1 , j , z nk ) ( 13.19 )
を、完全データに対する対数尤度関数の期待値
Q ( θ , θ old ) = ∑ k = 1 K γ ( z 1 k ) ln π k + ∑ n = 2 N ∑ j = 1 K ∑ k = 1 K ξ ( z n − 1 , j , z n k ) ln A j k + ∑ n = 1 N ∑ k = 1 K γ ( z n k ) ln p ( x n ∣ ϕ k ) (13.17)
\begin{aligned} Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right)=& \sum_{k=1}^{K} \gamma\left(z_{1 k}\right) \ln \pi_{k}+\sum_{n=2}^{N} \sum_{j=1}^{K} \sum_{k=1}^{K} \xi\left(z_{n-1, j}, z_{n k}\right) \ln A_{j k} \\ &+\sum_{n=1}^{N} \sum_{k=1}^{K} \gamma\left(z_{n k}\right) \ln p\left(\mathbf{x}_{n} \mid \phi_{k}\right) \end{aligned} \tag{13.17}
Q ( θ , θ old ) = k = 1 ∑ K γ ( z 1 k ) ln π k + n = 2 ∑ N j = 1 ∑ K k = 1 ∑ K ξ ( z n − 1 , j , z nk ) ln A jk + n = 1 ∑ N k = 1 ∑ K γ ( z nk ) ln p ( x n ∣ ϕ k ) ( 13.17 )
を最大化することにより確かめよ。その際、適当なラグランジュ乗数を用いてπ \boldsymbol{\pi} π とA \mathbf{A} A の成分に対する和の制約を与えること.
P.334~335参照。Mステップの更新式に相当する。
∑ l = 1 K π l = 1 \displaystyle \sum_{l=1}^{K} \pi_{l}=1 l = 1 ∑ K π l = 1 の条件下でQ ( θ , θ old ) Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right) Q ( θ , θ old ) をπ l \pi_{l} π l について最大化する。
∂ ∂ π k [ Q ( θ , θ old ) − λ ( ∑ l = 1 K π l − 1 ) ] = γ ( z 1 k ) ⋅ 1 π k − λ ( = 0 )
\begin{aligned}
&\frac{\partial}{\partial \pi_{k}}\left[Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right)-\lambda\left(\sum_{l=1}^{K} \pi_{l}-1\right)\right] \\
=&\ \gamma\left(z_{1 k}\right) \cdot \frac{1}{\pi_{k}}-\lambda(=0)
\end{aligned}
= ∂ π k ∂ [ Q ( θ , θ old ) − λ ( l = 1 ∑ K π l − 1 ) ] γ ( z 1 k ) ⋅ π k 1 − λ ( = 0 )
両辺にπ k \pi_{k} π k を乗じて、k k k について和をとって整理すると、
∑ k = 1 K γ ( z 1 k ) = λ ∑ k = 1 K π k ⏟ = 1
\sum_{k=1}^{K}\gamma(z_{1k}) = \lambda \underbrace{\sum_{k=1}^{K}\pi_{k}}_{=1}
k = 1 ∑ K γ ( z 1 k ) = λ = 1 k = 1 ∑ K π k
よって、λ = ∑ k = 1 K γ ( z 1 k ) \displaystyle \lambda = \sum_{k=1}^{K}\gamma(z_{1k}) λ = k = 1 ∑ K γ ( z 1 k ) 。これを代入して
π k = 1 λ γ ( z 1 k ) = γ ( z 1 k ) ∑ j = 1 K γ ( z 1 j ) (13.18)
\pi_{k}=\frac{1}{\lambda} \gamma\left(z_{1 k}\right)=\frac{\gamma\left(z_{1 k}\right)}{\sum_{j=1}^{K} \gamma\left(z_{1 j}\right)} \tag{13.18}
π k = λ 1 γ ( z 1 k ) = ∑ j = 1 K γ ( z 1 j ) γ ( z 1 k ) ( 13.18 )
次に、∑ k = 1 K A j k = 1 \displaystyle \sum_{k=1}^{K}A_{jk} = 1 k = 1 ∑ K A jk = 1 の条件下でQ ( θ , θ old ) Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right) Q ( θ , θ old ) をA j k A_{jk} A jk について最大化する。
\begin{aligned}
&\frac{\partial}{\partial A_{j k}}\left[Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right)-\sum_{l} \mu_{l}\left(\sum_{m} A_{j m}-1\right)\right] \\
=&\ \sum_{n=2}^{N} \sum_{l} \sum_{m} \xi\left(z_{n-1, l}, z_{n m}\right) \cdot \frac{1}{A_{lm}} \cdot \delta_{j l} \delta_{k m} - \mu_{l}\delta_{jl} \\
=&\ \sum_{n=2}^{N} \xi\left(\varepsilon_{n-1, j}, z_{n k}\right) \cdot \frac{1}{A_{j k}}-\mu_{j}(=0)
\end{aligned}
両辺にA_{jk} を乗じてk について和をとって整理すると
\sum_{k=1}^{K} \sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n k}\right)=\mu_{j} \underbrace{\sum_{k}A_{jk}}_{=1}
求めた\mu_{j} を代入して
A_{j k} =\frac{1}{\mu_{j}} \sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n k}\right) = \frac{\sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n k}\right)}{\sum_{l=1}^{K} \sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n l}\right)} \tag{13.19}
を得る。
演習 13.6
もし、隠れマルコフモデルのパラメータ\boldsymbol{\pi} か\mathbf{A} のいずれかの要素が最初に0に設定された場合、それらの要素素はEMアルゴリズムのその後に続く更新において0のままであることを示せ。
まずパラメータ\mathbf{\pi} について考える.
\mathbf{\pi} の特定の要素\pi_k が0に初期化されているとする.最初のEステップでは, \alpha(z_{1k}) は (13.37)から以下のようにかける.
\mathbf{\alpha}(z_{1k})=\pi_k p(\mathbf{x}_1\mid\phi_k)\tag{13.37}
\pi_k が0に初期化されているためこの値は0であることがわかる.また(13.33)から,
\gamma(z_{1k})=\frac{\alpha(z_{1k})\beta(z_{1k})}{p(\mathbf{x})}\tag{13.33}
\gamma(z_{1k}) も0になる.また次のMステップで
\pi_{k}=\frac{\gamma\left(z_{1 k}\right)}{\sum_{j=1}^{K} \gamma\left(z_{1 j}\right)}\tag
{13.18}
により更新される\pi_k の値は再び0となることがわかる。これはその後のEM step に当てはまるので、この\pi_k の値は0のままである.
次に\mathbf{A} の要素A_{jk} が0で初期化されているとする。
\begin{aligned}
\xi &\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right)=p\left(\mathbf{z}_{n-1}, \mathbf{z}_{n} \mid \mathbf{X}\right) \\
&=\frac{\left.\alpha\left(\mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) \beta\left(\mathbf{z}_{n}\right)\right)}{p(\mathbf{X})} .
\end{aligned}
(13.43)
A_{j k}=\frac{\sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n k}\right)}{\sum_{l=1}^{K} \sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n l}\right)}
で与えられ、これも0になりことがわかる.以上により示された.
演習 13.7
ガウス出力密度をもつ隠れマルコフモデルを考える。ガウス分布の平均と共分散のパラメータについての関数Q(\boldsymbol{\theta},\boldsymbol{\theta}^{\mathrm{old}}) の最大化が、Mステップの方程式
\boldsymbol{\mu}_{k}=\frac{\sum_{n=1}^{N} \gamma\left(z_{n k}\right) \mathbf{x}_{n}}{\sum_{n=1}^{N} \gamma\left(z_{n k}\right)} \tag{13.20}
と
\mathbf{\Sigma}_{k}=\frac{\sum_{n=1}^{N} \gamma\left(z_{n k}\right)\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)^{\mathrm{T}}}{\sum_{n=1}^{N} \gamma\left(z_{n k}\right)} \tag{13.21}
を導くことを示せ。
P.335の後半を参照。Q(\boldsymbol{\theta},\boldsymbol{\theta}^{\mathrm{old}}) を\boldsymbol{\phi}_{k} に関して最大化する場合、(13.17) の最後の項だけが\boldsymbol{\phi}_{k} に依存している。パラメータ\boldsymbol{\phi}_{k} が成分ごとに独立ならば、この項はk の各々の値ごとの項の和に分解され、そのそれぞれの項は独立に最大化することができる。出力分布がガウス密度分布の場合にはp\left(\mathbf{x} \mid \boldsymbol{\phi}_{k}\right)=\mathcal{N}\left(\mathbf{x} \mid \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right) と書けて、「\boldsymbol{\phi}_{k} に関しての最大化」をガウス分布の平均\boldsymbol{\mu}_{k} と分散\mathbf{\Sigma}_{k} についての最大化に分けて考える。
\begin{aligned}
& \sum_{n=1}^{N} \sum_{k=1}^{K} \gamma\left(z_{n k}\right) \ln p\left(\mathbf{x}_{n} \mid \phi_{k}\right)=\sum_{n=1}^{N} \sum_{k=1}^{K} \gamma\left(z_{n k}\right) \ln \mathcal{N}\left(\mathbf{x}_{n} \mid \boldsymbol{\mu}_{k}, \mathbf{\Sigma}_{k}\right) \\
=& \sum_{n=1}^{N} \sum_{k=1}^{K} \gamma\left(z_{n k}\right)\left\{-\frac{D}{2} \ln (2 \pi)-\frac{1}{2} \ln \left|\mathbf{\Sigma}_{k}\right|-\frac{1}{2}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)^{\mathrm{T}} \mathbf{\Sigma}_{k}^{-1}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)\right\}
\end{aligned}
(1)
\begin{aligned}
\frac{\partial}{\partial \boldsymbol{\mu}_{k}} Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right) &=\frac{\partial}{\partial \boldsymbol{\mu}_{k}}\left\{\sum_{n=1}^{N} \sum_{k=1}^{K} \gamma\left(z_{n k}\right) \cdot\left(-\frac{1}{2}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)^{\mathrm{T}} \mathbf{\Sigma}_{k}^{-1}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)\right)\right\} \\
&=\sum_{n=1}^{N} \gamma\left(z_{n k}\right) \mathbf{\Sigma}_{k}^{-1}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)=0
\end{aligned}
\sum_{n=1}^{N} \gamma\left(z_{n k}\right) \mathbf{\Sigma}_{k}^{-1} \boldsymbol{\mu}_{k} = \sum_{n=1}^{N} \gamma\left(z_{n k}\right) \mathbf{\Sigma}_{k}^{-1} \mathbf{x}_{n}
両辺に\mathbf{\Sigma}_{k} を乗じて整理すると
\boldsymbol{\mu}_{k}=\frac{\sum_{n=1}^{N} \gamma\left(z_{n k}\right) \mathbf{x}_{n}}{\sum_{n=1}^{N} \gamma\left(z_{n k}\right)} \tag{13.20}
を得る。
(2) \mathbf{\Sigma}_{k} について最大化する。
\begin{aligned}
\frac{\partial}{\partial \mathbf{\Sigma}_{k}} Q\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right) &=\frac{\partial}{\partial \mathbf{\Sigma}_{k}} \sum_{n=1}^{N} \sum_{k=1}^{K} \gamma\left(z_{n k}\right)\left\{-\frac{1}{2} \ln \left|\mathbf{\Sigma}_{k}\right|-\frac{1}{2}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)^{\mathrm{T}} \mathbf{\Sigma}_{k}^{-1}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)\right\} \\
&=\sum_{n=1}^{N} \gamma\left(z_{n k}\right)\left\{-\frac{1}{2}\left(\mathbf{\Sigma}_{k}^{-1}\right)^{\mathrm{T}}-\frac{1}{2} \frac{\partial}{\partial \mathbf{\Sigma}_{k}} \operatorname{Tr}\left(\mathbf{\Sigma}_{k}^{-1}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)^{\mathrm{T}}\right)\right\} \\
&=-\frac{1}{2} \sum_{n=1}^{N} \gamma\left(z_{n k}\right)\left\{\mathbf{\Sigma}_{k}^{-1}-\mathbf{\Sigma}_{k}^{-1}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)^{\mathrm{T}} \mathbf{\Sigma}_{k}^{-1}\right\}=0 \end{aligned}
上式について左と右から1回ずつ\mathbf{\Sigma}_{k} を乗じて整理すると、
\sum_{n=1}^{N} \gamma\left(z_{n k}\right)\mathbf{\Sigma}_{k} = \sum_{n=1}^{N} \gamma\left(z_{n k}\right)\mathbf{\Sigma}_{k}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)^{\mathrm{T}}
\mathbf{\Sigma}_{k} = \frac{\sum_{n=1}^{N} \gamma\left(z_{n k}\right)\mathbf{\Sigma}_{k}\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)\left(\mathbf{x}_{n}-\boldsymbol{\mu}_{k}\right)^{\mathrm{T}}}{\sum_{n=1}^{N} \gamma\left(z_{n k}\right)} \tag{13.21}
を得る。
演習 13.8
多項分布に従う離散観測値をもつ隠れマルコフモデルにおいて、隠れ変数を与えたときの観測値の条件付き分布が
p(\mathbf{x} \mid \mathbf{z})=\prod_{i=1}^{D} \prod_{k=1}^{K} \mu_{i k}^{x_{i} z_{k}} \tag{13.22}
で与えられ、また対応するMステップの方程式が
\mu_{i k}=\frac{\sum_{n=1}^{N} \gamma\left(z_{n k}\right) x_{n i}}{\sum_{n=1}^{N} \gamma\left(z_{n k}\right)} \tag{13.23}
で与えられることを示せ。同様に、複数の二値の出力変数をもち、そのそれぞれがベルヌーイ条件付き分布に従う隠れマルコフモデルについて、条件付き分布についての式とMステップの方程式を書き下せ。
ヒント:必要に応じて、2.1節と2.2節における、独立同分布に従うデータに対する最尤推定の解法についての、対応する議論を参照せよ。
(13.17) の Q\left(\theta, \theta^{\text {old }}\right) のうち、\mu に依存しているのは最終項のみなので、最終項のみを考える.
\sum_{n=1}^{N} \sum_{k=1}^{K} \gamma\left(z_{n k}\right) \ln p\left(\mathbf{x}_{n} \mid \phi_{k}\right)=\sum_{n=1}^{N} \sum_{k=1}^{K} \gamma\left(z_{n k}\right) \sum_{i=1}^{D} x_{n i} \ln \mu_{k i}
ラグランジュの未定乗数法を用いると、最大化すべき関数は、
\sum_{n=1}^{N} \sum_{k=1}^{K} \gamma\left(z_{n k}\right) \sum_{i=1}^{D} x_{n i} \ln \mu_{k i}+\sum_{k=1}^{K} \lambda_{k}\left(\sum_{i=1}^{D} \mu_{k i}-1\right)
\mu に関して微分して、
0=\sum_{n=1}^{N} \gamma\left(z_{n k}\right) \frac{x_{n i}}{\mu_{k i}}+\lambda_{k}
\mu_{k i} を両辺にかけて, i で和を取って, \sum_{i} x_{n i}=1 と\sum_{i} \mu_{n i}=1 を利用して
\lambda_{k}=-\sum_{n=1}^{N} \gamma\left(z_{n k}\right)
\lambda_{k} を
0=\sum_{n=1}^{N} \gamma\left(z_{n k}\right) \frac{x_{n i}}{\mu_{k i}}+\lambda_{k}
に代入して、整理すると、
\mu_{i k}=\frac{\sum_{n=1}^{N} \gamma\left(z_{n k}\right) x_{n i}}{\sum_{n=1}^{N} \gamma\left(z_{n k}\right)} \tag{13.23}
を得る.
演習 13.9
隠れマルコフモデルの
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}, \mathbf{z}_{1}, \ldots, \mathbf{z}_{N}\right)=p\left(\mathbf{z}_{1}\right)\left[\prod_{n=2}^{N} p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right)\right] \prod_{n=1}^{N} p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) \tag{13.6}
で定義される同時分布が条件付き独立性(13.24)-(13.31)
\begin{aligned}
p\left(\mathbf{X} \mid \mathbf{z}_{n}\right) =\ &p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n} \mid \mathbf{z}_{n}\right) \times \\
&p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n}\right)
\end{aligned}
\tag{13.24}
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{x}_{n}, \mathbf{z}_{n}\right)= p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n}\right) \tag{13.25}
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n-1}, \mathbf{z}_{n}\right)= p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n-1}\right) \tag{13.26}
p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n}, \mathbf{z}_{n+1}\right)= p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n+1}\right) \tag{13.27}
p\left(\mathbf{x}_{n+2}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n+1}, \mathbf{x}_{n+1}\right)= p\left(\mathbf{x}_{n+2}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n+1}\right) \tag{13.28}
\begin{aligned}
p\left(\mathbf{X} \mid \mathbf{z}_{n-1}, \mathbf{z}_{n}\right) =\ &p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n-1}\right) \times \\
& p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n}\right)
\end{aligned}\tag{13.29}
p\left(\mathbf{x}_{N+1} \mid \mathbf{X}, \mathbf{z}_{N+1}\right)= p\left(\mathbf{x}_{N+1} \mid \mathbf{z}_{N+1}\right) \tag{13.30}
p\left(\mathbf{z}_{N+1} \mid \mathbf{z}_{N}, \mathbf{X}\right)= p\left(\mathbf{z}_{N+1} \mid \mathbf{z}_{N}\right) \tag{13.31}
を満たすことを、有向分離の規準を用いて確かめよ。
P.84, 85の条件付き独立性とP.90の有向分離の規準を復習すると、任意の重複しないノード集合A, B, C があり、A の任意のノードからB の任意のノードへのすべての経路を考えたときにC がP.90の(a), (b)の条件を満たすとき、「A はC によってB から有向分離されている」と呼び、A \perp \!\!\! \perp B \mid C で表す。このとき、
p(A\mid B, C) = p(A\mid C) \iff p(B\mid A, C) = p(B\mid C) \iff p(A,B\mid C) = p(A\mid C)p(B\mid C)
が成立する。日本語でまとめると、
A とB がC を与えたもとで条件付き独立
C が分かっている状況で新たにB が分かっても、A に関する情報は得られない
C が分かっている状況で新たにA が分かっても、B に関する情報は得られない
隠れマルコフモデルのグラフィカルモデルは
これを踏まえて(13.24)-(13.31) を1つずつ示していく。
(13.24) について、\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\} の任意のノードから\{\mathbf{x}_{n+1},\ldots,\mathbf{x}_{N}\} の任意のノードへの経路は\mathbf{z}_{n} によって遮断されている。なぜなら、\mathbf{z}_{n} でhead-to-tailまたはtail-to-tail(\mathbf{x}_{n} のみ)となっているからである。すなわち\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\} \perp \!\!\! \perp \{\mathbf{x}_{n+1},\ldots,\mathbf{x}_{N}\} \mid \mathbf{z}_{n} と書けるので、
\begin{aligned}
p\left(\mathbf{X} \mid \mathbf{z}_{n}\right) =\ &p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n} \mid \mathbf{z}_{n}\right) \times \\
&p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n}\right)
\end{aligned}
となる。
(13.25) について、\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n-1}\} の任意のノードから\mathbf{x}_{n} のノードへの経路は\mathbf{z}_{n} でhead-to-tailになっているので遮断されている。すなわち\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n-1}\} \perp \!\!\! \perp \mathbf{x}_{n} \mid \mathbf{z}_{n} と書けるので、
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{x}_{n}, \mathbf{z}_{n}\right)= p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n}\right)
となる。
(13.26) について、\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n-1}\} の任意のノードから\mathbf{z}_{n} のノードへの経路は\mathbf{z}_{n-1} でhead-to-tail(\mathbf{x}_{n-1} 以外)またはtail-to-tail(\mathbf{x}_{n-1} のみ)になっているので遮断されている。すなわち\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n-1}\} \perp \!\!\! \perp \mathbf{z}_{n} \mid \mathbf{z}_{n-1} と書けるので、
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n-1}, \mathbf{z}_{n}\right) = p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n}, \mathbf{z}_{n-1}\right)= p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n-1}\right)
となる。
(13.27) について、ノード\mathbf{z}_{n} から\{\mathbf{x}_{n+1},\ldots,\mathbf{x}_{N}\} の任意のノードへの経路は\mathbf{z}_{n+1} でhead-to-tailになっているので遮断されている。すなわち\mathbf{z}_{n} \perp \!\!\! \perp \{\mathbf{x}_{n+1},\ldots,\mathbf{x}_{N}\} \mid \mathbf{z}_{n+1} と書けるので、
p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n}, \mathbf{z}_{n+1}\right)= p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n+1}\right)
(13.28) について、ノード\mathbf{x}_{n+1} から\{\mathbf{x}_{n+2},\ldots,\mathbf{x}_{N}\} の任意のノードへの経路は\mathbf{z}_{n+1} でtail-to-tailになっているので遮断されている。すなわち\mathbf{x}_{n+1} \perp \!\!\! \perp \{\mathbf{x}_{n+2},\ldots,\mathbf{x}_{N}\} \mid \mathbf{z}_{n+1} と書けるので、
p\left(\mathbf{x}_{n+2}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n+1}, \mathbf{x}_{n+1}\right)= p\left(\mathbf{x}_{n+2}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n+1}\right)
(13.29) について、まずノード\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n-1}\} から\{\mathbf{x}_{n},\ldots,\mathbf{x}_{N}\} の任意のノードへの経路は\mathbf{z}_{n-1}, \mathbf{z}_{n} でhead-to-tailまたはtail-to-tailになっているので遮断されている。すなわち\mathbf{x}_{1}, \ldots ,\mathbf{x}_{n-1} \perp \!\!\! \perp \mathbf{x}_{n}, \ldots , \mathbf{x}_{N} \mid \mathbf{z}_{n-1}, \mathbf{z}_{n} と書けるので、
p\left(\mathbf{X} \mid \mathbf{z}_{n-1}, \mathbf{z}_{n} \right) = p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n-1},\mathbf{z}_{n} \right)p\left(\mathbf{x}_{n}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n-1},\mathbf{z}_{n} \right)
右辺第一項は\{\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\} から\mathbf{z}_{n} までの経路が\mathbf{z}_{n-1} で遮断されているので\{\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N}\} \perp \!\!\! \perp \mathbf{z}_{n} \mid \mathbf{z}_{n-1} となり
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n-1},\mathbf{z}_{n} \right) = p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n-1} \right)
右辺第二項は\mathbf{x}_{n} から\{\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N}\} までの経路が\mathbf{z}_{n} で遮断されているので
p\left(\mathbf{x}_{n}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n-1},\mathbf{z}_{n} \right) = p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n-1}, \mathbf{z}_{n} \right)p\left(\mathbf{x}_{n+1},\ldots,\mathbf{x}_{N} \mid \mathbf{z}_{n-1}, \mathbf{z}_{n} \right)
さらにこの右辺について、同様に考えると、\mathbf{z}_{n-1}\perp \!\!\! \perp \mathbf{x}_{n} \mid \mathbf{z}_{n} と\mathbf{z}_{n-1}\perp \!\!\! \perp \{\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N}\}\mid \mathbf{z}_n が成立しているので、
\begin{aligned}
p\left(\mathbf{x}_{n}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n-1},\mathbf{z}_{n} \right) &= p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n-1}, \mathbf{z}_{n} \right)p\left(\mathbf{x}_{n+1},\ldots,\mathbf{x}_{N} \mid \mathbf{z}_{n-1}, \mathbf{z}_{n} \right) \\
&= p(\mathbf{x}_{n} \mid \mathbf{z}_{n})p(\mathbf{x}_{n+1},\ldots,\mathbf{x}_{N} \mid \mathbf{z}_{n})
\end{aligned}
以上を合わせて
\begin{aligned}
p\left(\mathbf{X} \mid \mathbf{z}_{n-1}, \mathbf{z}_{n}\right) =\ &p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n-1}\right) \times \\
& p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n}\right)
\end{aligned}
(13.30) について、\mathbf{x}_{N+1} ノードから任意の\mathbf{X} ノードへは\mathbf{z}_{N+1} で遮断されている。\mathbf{X} \perp \!\!\! \perp \mathbf{x}_{N+1} \mid \mathbf{z}_{N+1} なので、
p\left(\mathbf{x}_{N+1} \mid \mathbf{X}, \mathbf{z}_{N+1}\right)= p\left(\mathbf{x}_{N+1} \mid \mathbf{z}_{N+1}\right)
(13.31) について、任意の\mathbf{X} ノードから\mathbf{z}_{N+1} ノードへは\mathbf{z}_{N} で遮断されている。\mathbf{X} \perp \!\!\! \perp \mathbf{z}_{N+1} \mid \mathbf{z}_{N} なので、
p\left(\mathbf{z}_{N+1} \mid \mathbf{z}_{N}, \mathbf{X}\right)= p\left(\mathbf{z}_{N+1} \mid \mathbf{X}, \mathbf{z}_{N}\right) = p\left(\mathbf{z}_{N+1} \mid \mathbf{z}_{N}\right)
演習 13.10
隠れマルコフモデルの
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}, \mathbf{z}_{1}, \ldots, \mathbf{z}_{N}\right)=p\left(\mathbf{z}_{1}\right)\left[\prod_{n=2}^{N} p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right)\right] \prod_{n=1}^{N} p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) \tag{13.6}
で定義される同時分布が条件付き独立性(13.24)-(13.31) を満たすことを、確率の加法乗法定理を用いて確かめよ。
(13.24) を加法・乗法定理から求める
\begin{aligned}
p\left(\mathbf{x}_{1}, \ldots \mathbf{x}_{n}, \mathbf{z}_{n}\right)&=\sum_{\mathbf{x}_{n+1}} \cdots \sum_{\mathbf{x}_{N}} p\left(\mathbf{X}, \mathbf{Z}_{n}\right)=\sum_{\mathbf{x}_{n+1}} \cdots \sum_{\mathbf{x}_{N}} \sum_{\mathbf{Z}_{/n}} p(\mathbf{X}, \mathbf{Z}) \\
&=\sum_{\mathbf{x}_{n+1}} \cdots \sum_{\mathbf{x}_{N}} \sum_{\mathbf{Z}_{/n}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \\
&=\sum_{\mathbf{Z}_{/n}} \sum_{\mathbf{x}_{n+1}} \ldots \sum_{\mathbf{x}_{N}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \\
&=\sum_{\mathbf{Z}_{/n}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{n} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \sum_{\mathbf{x}_{n+1}} \ldots \sum_{\mathbf{x}_{N}} \prod_{i= n+1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \\
&=\sum_{\mathbf{Z}_{/n}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{n} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \prod_{i=n+1}^{N} \underbrace{\sum_{\mathbf{x}_{i}} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)}_{=1} \\
&=\sum_{\mathbf{Z}_{/n}} p\left(\mathbf{z}_{i}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{n} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \\
&=\sum_{\mathbf{z}_{1}} \cdots \sum_{\mathbf{z}_{n-1}} \sum_{\mathbf{z}_{n+1}} \cdots \sum_{\mathbf{z}_{N}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{n} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \\
&=\sum_{\mathbf{z}_{1}} \ldots \sum_{\mathbf{z}_{n-1}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{n} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)\left(\sum_{\mathbf{z}_{n+1}} \cdots \sum_{\mathbf{z}_{N}}\left[\prod_{i=n+1}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right]\right) \\
&=\sum_{\mathbf{z}_{1}} \cdots \sum_{\mathbf{z}_{n-1}} p\left(\mathbf{z}_{i}\right)\left[\prod_{i=2}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{n} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)
\end{aligned}
となる。同様に
\begin{aligned}
p\left(\mathbf{x}_{n+1}, \cdots \mathbf{x}_{N}, \mathbf{z}_{n}\right)&=\sum_{\mathbf{x}_{1}} \cdots \sum_{\mathbf{x}_{n}} \sum_{\mathbf{Z}_{/n}} p(\mathbf{X}, \mathbf{Z}) \\
&=\sum_{\mathbf{x}_{1}} \ldots \sum_{\mathbf{x}_{n}} \sum_{\mathbf{Z}_{/n}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \\
&=\sum_{\mathbf{Z}_{/n}} p\left(\mathbf{z}_{i}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=n+1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \underbrace{\sum_{\mathbf{x}_{1}} \sum_{\mathbf{x}_{n}} \prod_{i=1}^{n} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)}_{1} \\
&=\sum_{\mathbf{Z}_{/n}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=n+1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \\
&=\sum_{\mathbf{z}_{n+1}} \sum_{\mathbf{z}_{N}}\left[\prod_{i=n+1}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=n+1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \sum_{\mathbf{z}_{1}} \cdots \sum_{\mathbf{z}_{n-1}} p\left(\mathbf{z}_{i}\right)\left[\prod_{1-2}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \\
&=\left(\sum_{\mathbf{z}_{n+1}} \cdots \sum_{\mathbf{z}_{N}}\left[\prod_{i=n+1}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=n+1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)\right)\left(\sum_{\mathbf{z}_{1}} \cdots \sum_{\mathbf{z}_{n-1}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right]\right)
\end{aligned}
となる。ここで
\begin{aligned}
p\left(\mathbf{z}_{n}\right)=\sum_{\mathbf{X}} \sum_{\mathbf{Z}_{/n}} p\left(\mathbf{X}, \mathbf{z}\right)&=\sum_{\mathbf{X}} \sum_{\mathbf{Z}_{/n}} p\left(\mathbf{z}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \\
&=\sum_{\mathbf{Z}_{/n}} p\left(\mathbf{z}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \underbrace{\sum_{\mathbf{x}_{i=1}}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i}\right)}_{=1} \\
&=\sum_{\mathbf{Z}_{/n}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \\
&=\sum_{\mathbf{z}_{1}} \cdots \sum_{\mathbf{z}_{n-1}} \sum_{\mathbf{z}_{n+1}} \cdots \sum_{\mathbf{z}_{N}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \\
&=\sum_{\mathbf{z}} \cdots \sum_{\mathbf{z}_{n-1}} p\left(\mathbf{z}\right)\left[\prod_{i=2}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \underbrace{\sum_{\mathbf{z}_{n+1}}\cdots\sum_{\mathbf{z}_{N}}\left[\prod_{i=n+1}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right]}_{=1}\\
&=\sum_{\mathbf{z}} \cdots \sum_{\mathbf{z}_{n-1}} p\left(\mathbf{z}\right)\left[\prod_{i=2}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right]
\end{aligned}
なので
\begin{aligned}
&p\left(\mathbf{x}_{n+1}{ }, \ldots, \mathbf{x}_{N}, \mathbf{z}_{n}\right)=\left(\sum_{\mathbf{z}_{n+1}}\cdots \sum_{\mathbf{z}_{N}}\left[\prod_{i=n+1}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=n+1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)\right) p\left(\mathbf{z}_{n}\right) \\
&\left.\therefore p\left(\mathbf{x}_{n+1}{ }, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n}\right)=\ \sum_{\mathbf{z}_{n+1}} \ldots \sum_{\mathbf{z}_{N}}\left[\prod_{i=n+1}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=n+1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)\right)
\end{aligned}
よって
\begin{aligned}
& p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}, \mathbf{z}_{n}\right) p\left(\mathbf{x}_{n+1}, \ldots,\mathbf{x}_{N} \mid \mathbf{z}_{n}\right) \\
=&\ \left(\sum_{\mathbf{z}_{1}} \ldots \sum_{\mathbf{z}_{n-1}} p\left(\mathbf{z}\right)\left[\prod_{i=2}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{n} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)\right)\left(\sum_{\mathbf{z}_{n+1}} \sum_{\mathbf{z}_{N}}\left[\prod_{i=n+1}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=n+1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)\right) \\
=&\ \sum_{\mathbf{z}_{n+1}}\cdots\sum_{\mathbf{z}_{N}}\left(\sum_{\mathbf{z}_{1}}\cdots\sum_{\mathbf{z}_{n-1}} p\left(\mathbf{z}\right)\left[\prod_{i=2}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{n} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)\right) \underbrace{\left.\prod_{i=n+1}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=n+1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)}) \\
=&\ \sum_{\mathbf{z}_{n+1}} \cdots \sum_{\mathbf{z}_{N}}\left(\sum_{\mathbf{z}_{1}} \cdots \sum_{\mathbf{z}_{n-1}} p\left(\mathbf{z}\right)\left[\prod_{i=2}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{n} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)\left[\prod_{i=n+1}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=n+1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right)\right) \\
=&\ \sum_{\mathbf{z}} \cdots \sum_{\mathbf{z}_{n-1}} \sum_{\mathbf{z}_{n+1}} \cdots \sum_{\mathbf{z}_{N}} p\left(\mathbf{z}\right)\left[\prod_{i=2}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{N} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \\
=&\ \sum_{\mathbf{Z}_{/n}} p(\mathbf{X}, \mathbf{Z}) = p\left(\mathbf{X}, \mathbf{z}_{n}\right)
\end{aligned}
を得る。両辺をp\left(\mathbf{z}_{n}\right) で割ると
\frac{p\left(\mathbf{x}_{1} \ldots \mathbf{x}_{n}, \mathbf{z}_{n}\right) p\left(\mathbf{x}_{n+1} \ldots \mathbf{x}_{N} \mid \mathbf{z}_{n}\right)}{p\left(\mathbf{z}_{n}\right)}=\frac{p\left(\mathbf{X}, \mathbf{z}_{n}\right)}{p\left(\mathbf{z}_{n}\right)}
\therefore p\left(\mathbf{x}_{1} \ldots \mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{x}_{n+1} \cdots \mathbf{x}_{N} \mid \mathbf{z}_{n}\right)=p\left(\mathbf{X} \mid \mathbf{z}_{n}\right) \tag{13.24}
演習 13.11
因子グラフにおける一つの因子における変数の周辺分布の表現
p\left(\mathbf{x}_{s}\right)=f_{s}\left(\mathbf{x}_{s}\right) \prod_{i \in \operatorname{ne}\left(f_{s}\right)} \mu_{x_{i} \rightarrow f_{s}}\left(x_{i}\right) \tag{8.72}
を出発点として、13.2.3節で得られた積和アルゴリズムにおけるメッセージの結果も用いて、隠れマルコフモデルにおける2つの連続した潜在変数上の同時事後確率分布の結果(13.43)
\begin{aligned}
\xi\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right)&=p\left(\mathbf{z}_{n-1}, \mathbf{z}_{n} \mid \mathbf{X}\right) \\
&=\frac{p\left(\mathbf{X} \mid \mathbf{z}_{n-1}, \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right)}{p(\mathbf{X})} \\
&=\frac{p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1} \mid \mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) p\left(\mathbf{z}_{n-1}\right)}{p(\mathbf{X})} \\
&=\frac{\alpha\left(\mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) \beta\left(\mathbf{z}_{n}\right)}{p(\mathbf{X})}
\end{aligned}
を導け.
考え方としては、pp.344-345がノード\mathbf{z}_{n} 1つについてHMMの積和アルゴリズムを用いて\gamma(\mathbf{z}_{n}) を求めているのを参考しながら、図13.15の因子f_{n} に結合している\mathbf{z}_{n-1}, \mathbf{z}_{n} 2つの変数ノードについて計算すれば良い。注意として、\mathbf{X} = \{\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}\} は与えられており、条件付きの形で考える必要がある。
まず定義から\xi\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right)=p\left(\mathbf{z}_{n-1}, \mathbf{z}_{n} \mid \mathbf{X}\right) である。pp.344-345の議論のように、\mathbf{X} が与えられている状態で単純化された因子グラフを書くと図13.15のようになる。
(13.50) と(13.52) で見たように、\alpha(\mathbf{z}_{n}), \beta(\mathbf{z}_{n}) は
\alpha\left(\mathbf{z}_{n}\right)=\mu_{f_{n} \rightarrow \mathbf{z}_{n}}\left(\mathbf{z}_{n}\right) \tag{13.50}
\beta\left(\mathbf{z}_{n}\right)=\mu_{f_{n+1} \rightarrow \mathbf{z}_{n}}\left(\mathbf{z}_{n}\right) \tag{13.52}
と定義できるので、これを用いて(8.72) を利用してある因子f_{n} に関連する変数ノード\mathbf{z}_{n-1}, \mathbf{z}_{n} 全体上の周辺分布を求めると、すでに\mathbf{X} = \{\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}\} で条件付けられていることに注意して
\begin{aligned}
p\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}, \mathbf{X}\right) &=f_{n}\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right) \mu_{\mathbf{z}_{n-1} \rightarrow f_{n}}\left(\mathbf{z}_{n-1}\right) \mu_{\mathbf{z}_{n} \rightarrow f_{n}}\left(\mathbf{z}_{n}\right) \\
&=p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) \mu_{f_{n-1} \rightarrow \mathbf{z}_{n-1}}\left(\mathbf{z}_{n-1}\right) \mu_{f_{n+1} \rightarrow \mathbf{z}_{n}}\left(\mathbf{z}_{n}\right) \\
&=\alpha\left(\mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) \beta\left(\mathbf{z}_{n}\right)
\end{aligned}
となる。この式変形では
\begin{aligned}
\mu_{x_{m} \rightarrow f_{s}}\left(x_{m}\right) &=\prod_{l \in \operatorname{ne}\left(x_{m}\right) \backslash f_{s}}\left[\sum_{X_{l m}} F_{l}\left(x_{m}, X_{l m}\right)\right] \\
&=\prod_{l \in \operatorname{ne}\left(x_{m}\right) \backslash f_{s}} \mu_{f_{l} \rightarrow x_{m}}\left(x_{m}\right)
\end{aligned} \tag{8.69}
も利用した。これについて両辺をp(\mathbf{X}) で割ると
\begin{aligned}
\xi\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right)&=p\left(\mathbf{z}_{n-1}, \mathbf{z}_{n} \mid \mathbf{X}\right) \\
&= \frac{\alpha\left(\mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) \beta\left(\mathbf{z}_{n}\right)}{p(\mathbf{X})}
\end{aligned}\tag{13.43}
を得る。
演習 13.12
隠れマルコフモデルをR 個の独立した観測系列から構成されるデータを用いた最尤推定で学習したいとする。ここで、これらの観測行列を\mathbf{X}^{(r)}, r=1, \ldots, R で表す。EMアルゴリズムのEステップにおいて潜在変数の事後確率を求めるためには、各々の系列に対して独立に\alpha 再帰と\beta 再帰を実行すればよいことを示せ。また、Mステップにおいては、初期確率と遷移確率のパラメータは
\pi_{k}=\frac{\gamma\left(z_{1 k}\right)}{\sum_{j=1}^{K} \gamma\left(z_{1 j}\right)} \tag{13.18}
A_{j k}=\frac{\sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n k}\right)}{\sum_{l=1}^{K} \sum_{n=2}^{N} \xi\left(z_{n-1, j}, z_{n l}\right)} \tag{13.19}
を以下のように修正した式で再推定されることを示せ.
\pi_{k}= \frac{\sum_{r=1}^{R} \gamma\left(z_{1 k}^{(r)}\right)}{\sum_{r=1}^{R} \sum_{j=1}^{K} \gamma\left(z_{1 j}^{(r)}\right)} \tag{13.124}
A_{j k}= \frac{\sum_{r=1}^{R} \sum_{n=2}^{N} \xi\left(z_{n-1, j}^{(r)}, z_{n, k}^{(r)}\right)}{\sum_{r=1}^{R} \sum_{l=1}^{K} \sum_{n=2}^{N} \xi\left(z_{n-1, j}^{(r)}, z_{n, l}^{(r)}\right)} \tag{13.125}
ここで、表記を簡単にするために、系列はすべて同じ長さをもつと仮定した(長さの異なる系列への一般化は簡単である) 。同様に、ガウス出力モデルの平均の再推定のためのMステップの方程式が以下の形で与えられることを示せ。
\boldsymbol{\mu}_{k}=\frac{\sum_{r=1}^{R} \sum_{n=1}^{N} \gamma\left(z_{n k}^{(r)}\right) \mathbf{x}_{n}^{(r)}}{\sum_{r=1}^{R} \sum_{n=1}^{N} \gamma\left(z_{n k}^{(r)}\right)}
他の出力モデルパラメータや出力分布に対するMステップの方程式も類似の形になることに注意せよ。
隠れマルコフモデルの定義から、観察値\mathbf{X}^{(r)} には対応する潜在変数\mathbf{Z}^{(r)} が存在する。よって、その同時分布は以下のように表せる
\begin{aligned}
p(\mathbf{X}, \mathbf{Z}|\boldsymbol{\theta}) = \prod_r^R p(\mathbf{X}^{(r)}, \mathbf{Z}^{(r)}|\boldsymbol{\theta})
\end{aligned}
そして、Eステップでは、事後分布を求める。
\begin{aligned}
p(\mathbf{Z}|\mathbf{X}, \boldsymbol{\theta}) &= \frac{p(\mathbf{X}, \mathbf{Z}|\boldsymbol{\theta})}{\sum_{\mathbf{Z}} p(\mathbf{X}, \mathbf{Z}|\boldsymbol{\theta})} \\
&= \frac{\prod_r p(\mathbf{X}^{(r)}, \mathbf{Z}^{(r)}|\boldsymbol{\theta})}{\sum_{\mathbf{Z}^{(1)}} \cdots \sum_{\mathbf{Z}^{(R)}}\prod_r p(\mathbf{X}^{(r)}, \mathbf{Z}^{(r)}|\boldsymbol{\theta})}\\
&= \prod_r \frac{p(\mathbf{X}^{(r)}, \mathbf{Z}^{(r)}|\boldsymbol{\theta})}{\sum_{\mathbf{Z}^{(r)}} p(\mathbf{X}^{(r)}, \mathbf{Z}^{(r)}|\boldsymbol{\theta})}\\
&= \prod_r p( \mathbf{Z}^{(r)}|\mathbf{X}^{(r)},\boldsymbol{\theta})
\end{aligned}
ここで、
\begin{aligned}
p( \mathbf{Z}^{(r)}|\mathbf{X}^{(r)}) &= p( \mathbf{z}_{N}^{(r)}| \mathbf{z}_{N-1}^{(r)}, \cdots \mathbf{z}_{1}^{(r)}, \mathbf{X}^{(r)}) p( \mathbf{z}_{N-1}^{(r)}, \cdots \mathbf{z}_{1}^{(r)}|\mathbf{X}^{(r)}) \\
&= p( \mathbf{z}_{N}^{(r)}| \mathbf{z}_{N-1}^{(r)}, \mathbf{X}^{(r)}) p( \mathbf{z}_{N-1}^{(r)}, \cdots \mathbf{z}_{1}^{(r)}|\mathbf{X}^{(r)}) \\
&= p( \mathbf{z}_{N}^{(r)}| \mathbf{z}_{N-1}^{(r)}, \mathbf{X}^{(r)}) \cdots p( \mathbf{z}_{2}^{(r)}|\mathbf{z}_{1}^{(r)}\mathbf{X}^{(r)}) p( \mathbf{z}_{1}^{(r)}|\mathbf{X}^{(r)}) \\
&= \frac{p( \mathbf{z}_{N}^{(r)}, \mathbf{z}_{N-1}^{(r)}|\mathbf{X}^{(r)})}{p( \mathbf{z}_{N-1}^{(r)}|\mathbf{X}^{(r)}) } \cdots \frac{p( \mathbf{z}_{2}^{(r)}, \mathbf{z}_{1}^{(r)}|\mathbf{X}^{(r)})}{p( \mathbf{z}_{1}^{(r)}|\mathbf{X}^{(r)}) }p( \mathbf{z}_{1}^{(r)}|\mathbf{X}^{(r)}) \\
&= \frac{\xi^{(r)}(\mathbf{z}_{N}^{(r)}, \mathbf{z}_{N-1}^{(r)})}{\gamma^{(r)}(\mathbf{z}_{N-1}^{(r)})} \cdots \frac{\xi^{(r)}(\mathbf{z}_{2}^{(r)}, \mathbf{z}_{1}^{(r)})}{\gamma^{(r)}(\mathbf{z}_{1}^{(r)})}\gamma^{(r)}(\mathbf{z}_{1}^{(r)})\\
&= \frac{\prod_{n=2}^N \xi^{(r)}(\mathbf{z}_{n}^{(r)}, \mathbf{z}_{n-1}^{(r)})}{\prod_{n=2}^{N-1} \gamma^{(r)}(\mathbf{z}_{n}^{(r)})}
\end{aligned}
である。
よって、
\begin{aligned}
p( \mathbf{Z}|\mathbf{X}, \boldsymbol{\theta}) &= \prod_r \frac{\prod_{n=2} \xi^{(r)}(\mathbf{z}_{n}^{(r)}, \mathbf{z}_{n-1}^{(r)})}{\prod_{n=2} \gamma^{(r)}(\mathbf{z}_{n}^{(r)})}
\end{aligned}
これより、Eステップで求める事後分布は\xi と\gamma により計算できる。また、\xi と\gamma はそれぞれ\alpha^{(r)}(\mathbf{z}_n) と\beta^{(r)}(\mathbf{z}_n) を再帰で求めることができる。
次にMステップを考える。Eステップで求めた事後分布と\theta_{old} を用いて、完全データ対数尤度の期待値を求める。
\begin{aligned}
Q(\boldsymbol{\theta}, \boldsymbol{\theta_{old}}) &= E_{\mathbf{Z}} [\ln p(\mathbf{X, Z}|\boldsymbol{\theta}) ] \\
&= E_{\mathbf{Z}} [\sum_r^R \ln p(\mathbf{X}^{(r)}, \mathbf{Z}^{(r)}|\boldsymbol{\theta}) ] \\
&= \sum_r^R p( \mathbf{Z}^{(r)}|\mathbf{X}^{(r)},\boldsymbol{\theta}_{old}) \ln p(\mathbf{X}, \mathbf{Z}|\boldsymbol{\theta}) \\
&= \sum_r^R \sum_k^K \gamma(z_{1k}^{(r)}) \ln \pi_k + \sum_r^R \sum_N^n \sum_j^K \sum_k^K \xi(z_{n-1, j}^{(r)}, z_{n, k}^{(r)}) \ln A_{jk}+ \sum_r^R \sum_N^n \sum_k^K \gamma(z_{nk}^{(r)}) \ln p(\mathbf{x}_n^{(r)}|\phi_k) &(EX13.12.1)
\end{aligned}
最後の形は、いつも通りラグランジュ乗数法を用いて\pi と\mathbf{A} について最大化することができる。よって(13.124)、(13.125)が導かれる。詳細は http://sioramen.sub.jp/prml_wiki/lib/exe/fetch.php/wiki/13.12.pdf
次に、出力分布をガウス分布とする。すなわち、
\begin{aligned}
p(\mathbf{x}_n^{(r)}|\phi_k) = N(\mathbf{x}_n^{(r)}|\mathbf{\mu}_k, \mathbf{\Sigma}_k)
\end{aligned}
とする。
この時、Q(\boldsymbol{\theta}, \boldsymbol{\theta_{old}}) は(EX13.12.1)を用いて、\mathbf{\mu}_k を含まない部分はC にまとめて、
\begin{aligned}
Q(\boldsymbol{\theta}, \boldsymbol{\theta_{old}}) &= C+\sum_r^R \sum_N^n \sum_k^K \gamma(z_{nk}^{(r)}) \ln p(\mathbf{x}_n^{(r)}|\phi_k) \\
&= C+\sum_r^R \sum_N^n \sum_k^K \gamma(z_{nk}^{(r)}) \ln \frac{1}{(2\pi)^{D/2}}\frac{1}{|\mathbf{\Sigma}_k|^{1/2}} \exp\{ -\frac{1}{2}(\mathbf{x}_n^{(r)}-\mathbf{\mu}_k)^T \mathbf{\Sigma}_k^{-1}(\mathbf{x}_n^{(r)}-\mathbf{\mu}_k)\} \\
&= C+\sum_r^R \sum_N^n \sum_k^K \gamma(z_{nk}^{(r)}) \{ -\frac{1}{2}(\mathbf{x}_n^{(r)}-\mathbf{\mu}_k)^T \mathbf{\Sigma}_k^{-1}(\mathbf{x}_n^{(r)}-\mathbf{\mu}_k)\}
\end{aligned}
なお、最後の式変形は、\ln の後の一部をC にまとめた。あとはいつも通り\mathbf{\mu}_k について停留条件を求めると、Mステップの方程式が得られる。
演習 13.13
因子グラフにおける因子ノードから変数ノードへ渡されるメッセージの定義
\mu_{f_{s} \rightarrow x}(x) \equiv \sum_{X_{s}} F_{s}\left(x, X_{s}\right) \tag{8.64}
と隠れマルコフモデルの同時分布の表現
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}, \mathbf{z}_{1}, \ldots, \mathbf{z}_{N}\right)=p\left(\mathbf{z}_{1}\right)\left[\prod_{n=2}^{N} p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right)\right] \prod_{n=1}^{N} p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) \tag{13.6}
を用いて、\alpha メッセージの定義
\alpha\left(\mathbf{z}_{n}\right)=\mu_{f_{n} \rightarrow \mathbf{z}_{n}}\left(\mathbf{z}_{n}\right) \tag{13.50}
が
\alpha\left(\mathbf{z}_{n}\right) \equiv p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}, \mathbf{z}_{n}\right) \tag{13.34}
の定義と同一であることを示せ。
(8.64) の定義からスタートする。
\begin{aligned}
\alpha\left(\mathbf{z}_{n}\right) &=\mu_{f_{n} \rightarrow \mathbf{z}_{n}}\left(\mathbf{z}_{n}\right) \\
&=\sum_{\mathbf{z}_{n-1}} f_{n}\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right) \mu_{\mathbf{z}_{n-1}\to f_{n}}\left(\mathbf{z}_{n-1}\right) \\
&=\sum_{\mathbf{z}_{n-1}} f_{n}\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right) \mu_{f_{n-1} \rightarrow \mathbf{z}_{n-1}}\left(\mathbf{z}_{n-1}\right)\\
&=\cdots \\
&=\sum_{\mathbf{z}_{1},\ldots,\mathbf{z}_{n-1}} h\left(\mathbf{z}_{1}\right) \prod_{i=2}^{n} f_{i}\left(\mathbf{z}_{i-1}, \mathbf{z}_{i}\right)
\end{aligned}
ここで、図13.15の因子グラフでは
h\left(\mathbf{z}_{1}\right) =p\left(\mathbf{z}_{1}\right) p\left(\mathbf{x}_{1} \mid \mathbf{z}_{1}\right) \tag{13.45}
f_{n}\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right) =p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) \tag{13.46}
が成立しているので、これを利用して更に変形すると、周辺化を利用して
\begin{aligned}
\alpha\left(\mathbf{z}_{n}\right) &=\sum_{\mathbf{z}_{1}, \cdots, \mathbf{z}_{n-1}} p\left(\mathbf{z}_{1}\right) p\left(\mathbf{x}_{1} \mid \mathbf{z}_{1}\right) \prod_{i=2}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right) p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \\
&=\sum_{\mathbf{z}_{1}, \cdots, \mathbf{z}_{n-1}} p\left(\mathbf{z}_{1}\right)\left[\prod_{i=2}^{n} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right)\right] \prod_{i=1}^{n} p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \\
&=\sum_{\mathbf{z}_{1}, \cdots, \mathbf{z}_{n-1}} p\left(\mathbf{x}_{1}, \cdots, \mathbf{x}_{n}, \mathbf{z}_{1}, \cdots, \mathbf{z}_{n}\right)\ (\because (13.6))\\
&=p\left(\mathbf{x}_{1}, \cdots, \mathbf{x}_{n}, \mathbf{z}_{n}\right)
\end{aligned}
となり、(13.34) の定義が得られる。
演習 13.14
因子グラフにおける因子ノードから変数ノードへ渡されるメッセージの定義
\mu_{f_{s} \rightarrow x}(x) \equiv \sum_{\mathbf{x}_{s}} F_{s}\left(x, \mathbf{x}_{s}\right) \tag{8.64}
と隠れマルコフモデルの同時分布の表現
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}, \mathbf{z}_{1}, \ldots, \mathbf{z}_{N}\right)=p\left(\mathbf{z}_{1}\right)\left[\prod_{n=2}^{N} p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right)\right] \prod_{n=1}^{N} p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) \tag{13.6}
を用いて、\beta メッセージの定義
\beta\left(\mathbf{z}_{n}\right)=\mu_{f_{n+1} \rightarrow \mathbf{z}_{n}}\left(\mathbf{z}_{n}\right) \tag{13.52}
が
\beta\left(\mathbf{z}_{n}\right) \equiv p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n}\right) \tag{13.35}
の定義と同一であることを示せ.
演習問題13.13と似たような問題だが、最後の式変形が少し難しくなる。同様に図13.15の因子グラフを用いて考える。
(13.52) の定義からスタートして
\begin{aligned}
\beta\left(\mathbf{z}_{n}\right) &=\mu_{f_{n+1} \rightarrow \mathbf{z}_{n}}\left(\mathbf{z}_{n}\right) \\
&=\sum_{\mathbf{z}_{n+1}} f_{n+1}\left(\mathbf{z}_{n}, \mathbf{z}_{n+1}\right) \mu_{\mathbf{z}_{n+1}\to f_{n+1}}\left(\mathbf{z}_{n+1}\right) \\
&=\sum_{\mathbf{z}_{n+1}} f_{n+1}\left(\mathbf{z}_{n}, \mathbf{z}_{n+1}\right) \mu_{f_{n+2}\to\mathbf{z}_{n+1}}\left(\mathbf{z}_{n+1}\right) \\
&=\cdots \\
&=\sum_{\mathbf{z}_{n+1}, \cdots, \mathbf{z}_{N}} \prod_{i=n+1}^{N}f_{i}\left(\mathbf{z}_{i-1}, \mathbf{z}_{i}\right) \underbrace{\mu_{\mathbf{z}_{N}\to f_{N}}\left(\mathbf{z}_{N}\right)}_{=1} \\
&=\sum_{\mathbf{z}_{n+1}, \cdots, \mathbf{z}_{N}} \prod_{i=n+1}^{N}f_{i}\left(\mathbf{z}_{i-1}, \mathbf{z}_{i}\right) \\
&=\sum_{\mathbf{z}_{n+1}, \cdots, \mathbf{z}_{N}} \prod_{i=n+1}^{N} p\left(\mathbf{z}_{i} \mid \mathbf{z}_{i-1}\right) p\left(\mathbf{x}_{i} \mid \mathbf{z}_{i}\right) \quad (\because (13.46))\\
&=\sum_{\mathbf{z}_{n+1}, \cdots, \mathbf{z}_{N}} p\left(\mathbf{z}_{n+1} \mid \mathbf{z}_{n}\right) p\left(\mathbf{x}_{n+1} \mid \mathbf{z}_{n+1}\right) \cdots p\left(\mathbf{z}_{N} \mid \mathbf{z}_{N-1}\right) p\left(\mathbf{x}_{N} \mid \mathbf{z}_{N}\right) \\
&=\sum_{\mathbf{z}_{n+1}, \cdots, \mathbf{z}_{N}} p\left(\mathbf{z}_{n+1} \mid \mathbf{z}_{n}\right) p\left(\mathbf{x}_{n+1} \mid \mathbf{z}_{n}, \mathbf{z}_{n+1}\right) p\left(\mathbf{z}_{n+2} \mid \mathbf{z}_{n+1}\right) p\left(\mathbf{x}_{n+2} \mid \mathbf{z}_{n+2}\right)\cdots p\left(\mathbf{z}_{N} \mid \mathbf{z}_{N-1}\right) p\left(\mathbf{x}_{N} \mid \mathbf{z}_{N}\right) \quad (\because (13.27)) \\
&=\sum_{\mathbf{z}_{n+1}, \cdots, \mathbf{z}_{N}} p\left(\mathbf{x}_{n+1}, \mathbf{z}_{n+1} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n+2} \mid \mathbf{x}_{n+1}, \mathbf{z}_{n+1}\right) p\left(\mathbf{x}_{n+2} \mid \mathbf{x}_{n+1}, \mathbf{z}_{n+1}, \mathbf{z}_{n+2}\right) \cdots p\left(\mathbf{x}_{N} \mid \mathbf{x}_{N-1}, \mathbf{z}_{n+1}, \cdots, \mathbf{z}_{N}\right)\quad (\because (13.28)) \\
&=\sum_{\mathbf{z}_{n+1}, \cdots, \mathbf{z}_{N}} p\left(\mathbf{x}_{n+1}, \cdots, \mathbf{x}_{N}, \mathbf{z}_{n+1}, \cdots, \mathbf{z}_{N} \mid \mathbf{z}_{n}\right) \\
&=p\left(\mathbf{x}_{n+1}, \cdots, \mathbf{x}_{N} \mid \mathbf{z}_{n}\right)
\end{aligned}
以上で(13.35) 式が示された。
演習 13.15
隠れマルコフモデルの周辺分布の表現
\gamma\left(\mathbf{z}_{n}\right)=\frac{p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}, \mathbf{z}_{n}\right) p\left(\mathbf{x}_{n+1}, \ldots, \mathbf{x}_{N} \mid \mathbf{z}_{n}\right)}{p(\mathbf{X})}=\frac{\alpha\left(\mathbf{z}_{n}\right) \beta\left(\mathbf{z}_{n}\right)}{p(\mathbf{X})} \tag{13.33}
と
\xi(\mathbf{z}_{n-1}, \mathbf{z}_{n}) = p(\mathbf{z}_{n-1}, \mathbf{z}_{n} \mid \mathbf{X}) = \frac{\alpha\left(\mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) \beta\left(\mathbf{z}_{n}\right)}{p(\mathbf{X})} \tag{13.43}
を用いて、スケーリングされた変数についての対応する結果
\gamma\left(\mathbf{z}_{n}\right) =\widehat{\alpha}\left(\mathbf{z}_{n}\right) \widehat{\beta}\left(\mathbf{z}_{n}\right) \tag{13.64}
\xi\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right) =\left(c_{n}\right)^{-1} \widehat{\alpha}\left(\mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) \widehat{\beta}\left(\mathbf{z}_{n}\right) \tag{13.65}
を導け.
\begin{aligned}
\gamma\left(\mathbf{z}_{n}\right)&=\frac{\alpha\left(\mathbf{z}_{n}\right) \beta\left(\mathbf{z}_{n}\right)}{p(\mathbf{X})} \\
&=\frac{p(\mathbf{x}_1,\cdots , \mathbf{x}_n)\widehat{\alpha}\left(\mathbf{z}_{n}\right) \cdot \left( \prod_{m=n+1}^N c_m\right) \widehat{\beta}\left(\mathbf{z}_{n}\right)}{\prod_{m=1}^N c_m } \\
&= \frac{\left(\prod_{m=1}^n c_m \right) \widehat{\alpha}\left(\mathbf{z}_{n}\right) \cdot \left( \prod_{m=n+1}^N c_m\right) \widehat{\beta}\left(\mathbf{z}_{n}\right)}{\prod_{m=1}^N c_m } \\
&=\widehat{\alpha}\left(\mathbf{z}_{n}\right) \widehat{\beta}\left(\mathbf{z}_{n}\right)
\end{aligned}
\begin{aligned}
\xi\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right) &=\frac{\alpha\left(\mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) \beta\left(\mathbf{z}_{n}\right)}{p(\mathbf{X})}\\
&=\frac{\left(\prod_{m=1}^{n-1} c_m \right) \widehat{\alpha}\left(\mathbf{z}_{n-1}\right) \cdot
p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) \cdot \left(\prod_{m=n+1}^{N} c_m \right)
\widehat{\beta}\left(\mathbf{z}_{n}\right)}{\prod_{m=1}^{N} c_m }\\
&=\left(c_{n}\right)^{-1} \widehat{\alpha}\left(\mathbf{z}_{n-1}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right) \widehat{\beta}\left(\mathbf{z}_{n}\right) \end{aligned}
演習 13.16
この演習問題では、Viterbiアルゴリズムのフォワードメッセージパッシングの式を同時分布の表現
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}, \mathbf{z}_{1}, \ldots, \mathbf{z}_{N}\right)=p\left(\mathbf{z}_{1}\right)\left[\prod_{n=2}^{N} p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right)\right] \prod_{n=1}^{N} p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) \tag{13.6}
から直接導く。これは、すべての隠れ変数\mathbf{z}_1,\ldots,\mathbf{z}_{N} についての最大化を含む。対数を取り、最大化と和の順序を交換することにより、再帰式
\omega\left(\mathbf{z}_{n+1}\right)=\ln p\left(\mathbf{x}_{n+1} \mid \mathbf{z}_{n+1}\right)+\max _{\mathbf{z}_{n}}\left\{\ln p\left(\mathbf{z}_{n+1} \mid \mathbf{z}_{n}\right)+\omega\left(\mathbf{z}_{n}\right)\right\} \tag{13.68}
を求めよ。ここで、\omega(\mathbf{z}_n) は
\omega\left(\mathbf{z}_{n}\right)=\max _{\mathbf{z}_{1}, \ldots, \mathbf{z}_{n-1}} \ln p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}, \mathbf{z}_{1}, \ldots, \mathbf{z}_{n}\right) \tag{13.70}
で定義される。この再帰式の初期条件が
\omega\left(\mathbf{z}_{1}\right)=\ln p\left(\mathbf{z}_{1}\right)+\ln p\left(\mathbf{x}_{1} \mid \mathbf{z}_{1}\right) \tag{13.69}
で与えられることを示せ。
(13.6)を書き換えて
p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N}, \mathbf{z}_{1}, \ldots, \mathbf{z}_{N}\right)=p\left(\mathbf{z}_{1}\right) p\left(\mathbf{x}_{1} \mid \mathbf{z}_{1}\right) \prod_{n=2}^{N} p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right) p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right)
を得る.この式のlogをとると
\begin{aligned}
\ln p\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{N},\right.&\left.\mathbf{z}_{1}, \ldots, \mathbf{z}_{N}\right)
=\ln p\left(\mathbf{z}_{1}\right)+\ln p\left(\mathbf{x}_{1} \mid \mathbf{z}_{1}\right)+\sum_{n=2}^{N}\left(\ln p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right)+\ln p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right)\right)
\end{aligned}
となる.ここで最初の2項は(13.69)式で書き換えられる.この式を\mathbf{z}_1,\dots,\mathbf{z}_N について最大化すると
\begin{aligned}
\max _{\mathbf{z}_{1}, \ldots, \mathbf{z}_{N}} &\left\{\omega\left(\mathbf{z}_{1}\right)+\sum_{n=2}^{N}\left[\ln p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right)+\ln p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right)\right]\right\} \\
=& \max _{\mathbf{z}_{2}, \ldots, \mathbf{z}_{N}}\left\{\ln p\left(\mathbf{x}_{2} \mid \mathbf{z}_{2}\right)+\max _{\mathbf{z}_{1}}\left\{\ln p\left(\mathbf{z}_{2} \mid \mathbf{z}_{1}\right)+\omega\left(\mathbf{z}_{1}\right)\right\}\right.
\left.+\sum_{n=3}^{N}\left[\ln p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right)+\ln p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right)\right]\right\} \\
=& \max _{\mathbf{z}_{2}, \ldots, \mathbf{z}_{N}}\left\{\omega\left(\mathbf{z}_{2}\right)+\sum_{n=3}^{N}\left[\ln p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}\right)+\ln p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}\right)\right]\right\}
\end{aligned}
ここで最大化と総和の順序を入れ替えて、n = 2 の (13.68) を得た。この式の最初の行と最後の行は添字n が一つ増えただけで同じ形であり、これによってすべての n > 2 について再帰的に(13.68)が成り立つことがわかる。
演習 13.17
図13.18のinput-output隠れマルコフモデルに対する有向グラフが図13.15に示す形の木構造因子グラフで表現されることを示せ。そして、初期因子h(\mathbf{z}_{1}) と一般的な因子f_{n}(\mathbf{z}_{n-1}, \mathbf{z}_{n}) を書き下せ。ここで、2\leqslant n \leqslant N である。
教科書の図8.42あたりの記述も参考にする。h や因子f_{n}(\mathbf{z}_{n-1}, \mathbf{z}_{n}) は出力確率\mathbf{x}_{n} や入力確率\mathbf{u}_{n} を吸収した形になる。図13.14, 13.15と同様のやり方を踏まえれば
h\left(\mathbf{z}_{1}\right)=p\left(\mathbf{z}_{1} \mid \mathbf{u}_{1}\right) p\left(\mathbf{x}_{1} \mid \mathbf{z}_{1}, \mathbf{u}_{1}\right)
f\left(\mathbf{z}_{n-1}, \mathbf{z}_{n}\right)=p\left(\mathbf{z}_{n} \mid \mathbf{z}_{n-1}, \mathbf{u}_{n}\right) p\left(\mathbf{x}_{n} \mid \mathbf{z}_{n}, \mathbf{u}_{n}\right)
とすればよい。
Discussion