はじめに
PRML解答例まとめを参照
演習 13.1
8.2節で議論した有向分離のテクニックを使って図13.3に示す全部でN個のノードをもつマルコフモデルが、n=2, \ldots, Nについて条件付き独立性
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}
を満たすことを示せ．同様に、図13.4のグラフで記述される全部でN個のノードをもつモデルが、n=3,\ldots,Nについて以下の条件付き独立性を満たすことを示せ．
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}
.
※8.2.2 有向分離の節で用いられた手法で考える。図のようにA, B, Cの部分集合を指定する。Aに属する任意のノードからBに属するノードへの可能な経路は必ずCを通ることになる。
今、Cは観測されており、head-to-tailとなっているので、P.91の議論からAからBへの経路はCで遮断されており、A \perp \!\!\! \perp B \mid Cが成立する。これより
\begin{aligned}
p(A,B\mid C) &= p(A\mid C)p(B\mid C) \\
\end{aligned}
が成立する。両辺にp(C)をかけると
\begin{aligned}
p(A,B, C) &= p(A,C)p(B\mid C) \\
\end{aligned}
となる。
問題は今p\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right) = p(B\mid A, C)なので
\begin{aligned}
p(B\mid A, C) &= \frac{p(A, B, C)}{p(A,C)} \\
&=p(B\mid C)
\end{aligned}
これを書き直すと
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}
が得られる。
二次マルコフ連鎖の場合、n=3について(13.122)式は自明に成立する。
n=4,\ldots,Nの二次マルコフ連鎖の場合は上の図のようになる。このとき、同様にAからBへの経路はCに含まれるすべてのノードで遮断されている。つまりA \perp \!\!\! \perp B \mid Cが成立する。これより
\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}
よって(13.122)式が導かれた。
演習 13.2
図13.3の有向グラフに対応する同時確率分布
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}
について考えよう。確率の加法・乗法定理を用い、この同時確率がn=2, \ldots, Nについて条件付き独立性
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\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}
によって記述される二次マルコフモデルが、n=3,\ldots,Nについて以下の条件付き独立性を満たすことを示せ。
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}
(13.3)の左辺を展開し、\mathbf{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}
そこで、(13.2)式を利用してp\left(\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right)を求める。
\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\left(\mathbf{x}_{n} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{n-1}\right)を計算すると
\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}
途中で\mathbf{x}_{n}に依存する項以外が分母分子でキャンセルされることを用いた。これより、(13.3)の右辺が得られた。
二次マルコフモデルについても同様に行うと、(13.4)の同時分布からはじめて
\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}
となるので、
\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}
を得る。
演習 13.3
有向分離を用いて、図13.5の有向グラフで表現される状態空間モデルにおける観測データの分布p(\mathbf{x}_1,\ldots,\mathbf{x}_N )が何の条件付き独立性も満足せず、したがって、どのような有限次数のマルコフ性ももたないことを示せ.
図13.5によると、任意の2つの変数\mathbf{x}_nと\mathbf{x}_m, m \neq nについて、それぞれのノード間には直接的な経路は存在せず、\mathbf{z}変数に対応する1つ以上のノードを通過する経路が存在している。これらのノードはいずれも観測データの分布p(\mathbf{x}_1,\ldots,\mathbf{x}_N )の条件集合に含まれていない。したがって、\mathbf{x}_nと\mathbf{x}_mの間には遮断されていない経路が存在し、モデルは条件付き独立性または有限次マルコフ性を満たさないことになる。
演習 13.4
線形回帰モデルやニューラルネットワークのように、出力密度がパラメトリックなモデルp(\mathbf{x}\mid \mathbf{z},\mathbf{w})で表される隠れマルコフモデルを考えよう。ここで、\mathbf{w}は適応パラメータのベクトルである。データから最尤推定によってパラメータ\mathbf{w}を学習する方法を述べよ.
教科書p.330に記載されている、「隠れマルコフモデルとして離散分布、ガウス分布、混合ガウス分布といった広い範囲の出力分布に加えて、ニューラルネットワークなどの識別的モデルを利用することも可能」という記述への補足のための演習問題。
教科書では、出力分布p(\mathbf{x}_n|\phi_k)としてガウス分布（p.335）や離散多項分布（p.336）の例が記載されている。このパラメータ\phiを\mathbf{w}で置き換えると、識別的モデルにおいても同様の定式化が可能。
実際の更新式の形は、回帰モデルの形や、回帰モデルがどのように使われているかに依って異なる。一例としては、図13.8（p.351）では\mathbf{x}の生成密度が、隠れ変数\mathbf{z}だけでなく観測変数系列\mathbf{u}に依存する。
この場合、回帰モデルは\mathbf{u}から\mathbf{x}への写像（写像の関数形が\mathbf{z}に応じて異なる）とみなすことができる。
ニューラルネットワークのような非線形な関数形では、Mステップにおける\mathbf{w}の最適解が解析的に解けないことが多い。
演習 13.5
隠れマルコフモデルの初期状態確率と遷移確率のパラメータについての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}
を、完全データに対する対数尤度関数の期待値
\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}
を最大化することにより確かめよ。その際、適当なラグランジュ乗数を用いて\boldsymbol{\pi}と\mathbf{A}の成分に対する和の制約を与えること.
P.334~335参照。Mステップの更新式に相当する。
\displaystyle \sum_{l=1}^{K} \pi_{l}=1の条件下でQ\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right)を\pi_{l}について最大化する。
\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}
両辺に\pi_{k}を乗じて、kについて和をとって整理すると、
\sum_{k=1}^{K}\gamma(z_{1k}) = \lambda \underbrace{\sum_{k=1}^{K}\pi_{k}}_{=1}
よって、\displaystyle \lambda = \sum_{k=1}^{K}\gamma(z_{1k})。これを代入して
\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}
次に、\displaystyle \sum_{k=1}^{K}A_{jk} = 1の条件下でQ\left(\boldsymbol{\theta}, \boldsymbol{\theta}^{\text {old }}\right)を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