この記事では統計学・機械学習の教科書である、C. M. Bishop 著「パターン認識と機械学習」（略称：PRML）の演習問題を私が解いた結果を載せています。この本は私が所属する研究室の輪読会で現在扱われていて、勉強の一環として演習問題を解いています。
\newcommand{\boa}[1]{\mathbf{#1}}
\newcommand{\bog}[1]{\boldsymbol{#1}}
\newcommand{\z}{\mathbf{z}}
\newcommand{\Z}{\mathbf{Z}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\X}{\mathbf{X}}
\newcommand{\th}{\boldsymbol{\theta}}
\newcommand{\tho}{\th^{\rm old}}
#問題
多項分布に従う離散観測値をもつ隠れマルコフモデルにおいて、隠れ変数を与えたときの観測値の条件付き分布が $(13.22)$ で与えられ、また対応するMステップの方程式が $(13.23)$ で与えられることを示せ。同様に、複数の二値の出力変数をもち、そのそれぞれがベルヌーイ条件付き分布に従う隠れマルコフモデルについて、条件付き分布についての式とMステップの方程式を書き下せ。
ヒント：必要に応じて、2.1節と2.2節における、独立同分布に従うデータに対する最尤推定の解法についての、対応する議論を参照せよ。
#方針
この問題では、観測値が離散となる以下の２つのケースについて考える。
ケースA. 観測値 $\x$ が多項分布に従う場合
ケースB. 観測値 $\x$ が複数あり、それぞれがベルヌーイ分布に従う場合
そして、それぞれの場合おいて、以下の二つの式を導出する。
式1. 隠れ変数を与えたときの観測値の条件付き分布 $p(\x|\ z)$
式2. Mステップの方程式、すなわち $Q(\th, \tho)$ を最大化する $\th$ の導出式
#解答
##命題A-1
観測値 $x$ が多項分布に従う場合、隠れ変数を与えたときの観測値の条件付き分布 $p(\x|\z)$ は以下のようになる。
\begin{align}
p(\x | \z)
\prod_{i=1}^D \prod_{k=1}^K \mu_{ik}^{x_i z_k}
\tag{13.22}
\end{align}
**証明** まず、問題設定を確認する。いま、潜在変数 $\z$ は離散変数であり、1-of-K符号化によって表されている長さ $K$ のベクトルである。
観測変数 $\x$ も離散変数である。多項分布に従うということであるから、こちらも1-of-K符号化によって表すことができる。長さ（多項分布の'項'数）は $D$ とする。
いま求めたいのは、条件付き分布 $p(\x|\z)$ である。これを定義するには、潜在変数の $K$ 個の状態と、観測変数の $D$ 個の状態を結び付ける出力確率を設定すればよい。出力確率は $KD$ 個のパラメータで設定され、それらは
```math
p(x_i = 1|z_k = 1) = \mu_{ik} \ \ (i = 1,...,D,\ k = 1,...,K) \tag{ex1.1}
と定義される。なお、以下の制約条件があることに注意する。
\sum_{i=1}^D \mu_{ik} = 1 \ \ (k = 1,...,K) \tag{ex1.2}
ゆえに、$\x$ の $D$ 個の要素の同時分布は
p(\x|z_k = 1) = \prod_{i=1}^D \mu_{ik}^{x_i} \ \ (k = 1,...,K) \tag{ex1.3}
となり、更に $\z$ に関して式を統合することで式 $(13.22)$ が得られる。（証明終）
##命題A-2
観測値 $x$ が多項分布に従う場合、Mステップの方程式、すなわち $Q(\th, \tho)$ を最大化する $\th$ の導出式は以下のようになる。
\begin{align}
\mu_{ik}
\frac
{\sum_{n=1}^N \gamma(z_{nk}) x_{ni}}
{\sum_{n=1}^N \gamma(z_{nk})}
\tag{13.23}
\end{align}
**証明** 本文では観測値 $\x$ が正規分布に従う場合の導出を行っており、完全データ対数尤度関数の期待値 $Q(\th, \tho)$ を以下のように書き下していた。
```math
\begin{align}
Q(\th, \tho)
=&\
\sum_\Z p(\Z|\X,\tho) \ln p(\X,\Z|\th)
\tag{13.12}
\\=&\
\sum_{k=1}^K \gamma(z_{1k}) \ln \pi_k
+ \sum_{n=2}^N \sum_{j=1}^K \sum_{k=1}^K \xi(z_{n-1,j}, z_{nk}) \ln A_{jk}
\\
&+ \sum_{n=1}^N \sum_{k=1}^K \gamma(z_{nk}) \ln p(\x_n|\phi_k)
\tag{13.17}
\end{align}
このうち、観測変数 $\X$ に関わるのは第３項のみであり、$p(\x_n|z_{nk})$ を命題A-1で導いた式 $(\rm ex1.3)$ で置き換えることで、この場合の $Q(\th, \tho)$ が得られる。
\begin{align}
Q(\th, \tho)
=&\
\sum_{k=1}^K \gamma(z_{1k}) \ln \pi_k
+ \sum_{n=2}^N \sum_{j=1}^K \sum_{k=1}^K \xi(z_{n-1,j}, z_{nk}) \ln A_{jk}
\\
&+ \sum_{n=1}^N \sum_{k=1}^K \gamma(z_{nk}) \sum_{i=1}^D x_{ni} \ln \mu_{ik}
\tag{ex2.1}
\end{align}
求めたいMステップの方程式、すなわち $Q(\th, \tho)$ を最大化する $\mu_{ik}$ の導出式は、$(\rm ex2.1)$ を微分することで得られる。$\mu_{ik}$ に関わるのは第３項のみなので、それ以外の項は無視してよい。ただし、$\mu_{ik}$ にまつわる制約条件である式 $(\rm ex1.2)$ を考慮するために、ラグランジュの未定乗数法を用いる。すなわち、以下の式
\sum_{n=1}^N \sum_{k=1}^K \gamma(z_{nk}) \sum_{i=1}^D x_{ni} \ln \mu_{ik}
+ \sum_{k=1}^K \lambda_k \left( \sum_{i=1}^D \mu_{ik} - 1 \right)
\tag{ex2.2}
の最大値を求めればよい。これを $\mu_{ik}$ で微分して０と置くと、以下のようになる。
\begin{align}
0 &= \sum_{n=1}^N \frac{\gamma(z_{nk}) x_{ni}}{\mu_{ik}} + \lambda_k
\\
0 &= \sum_{n=1}^N \gamma(z_{nk}) x_{ni} + \lambda_k \mu_{ik}
\tag{ex2.3}
\end{align}
この方程式は $i=1,..,D,\ k=1,...,K$ に対応する数だけ存在する。このうち、$i$ に関して和を取ると以下のようになる。
\begin{align}
\\
0 &= \sum_{i=1}^D \sum_{n=1}^N \gamma(z_{nk}) x_{ni} + \sum_{i=1}^D \lambda_k \mu_{ik}
\\
0 &= \sum_{n=1}^N \left( \gamma(z_{nk}) \sum_{i=1}^D x_{ni} \right)
+ \lambda_k \sum_{i=1}^D \mu_{ik}
\\
0 &= \sum_{n=1}^N \gamma(z_{nk}) + \lambda_k
\\
\lambda_k &= -\sum_{n=1}^N \gamma(z_{nk})
\tag{ex2.4}
\end{align}
式 $(\rm 2.4)$ を式 $(\rm 2.3)$ に代入することで、題意の式
\begin{align}
\mu_{ik}
=
\frac
{\sum_{n=1}^N \gamma(z_{nk}) x_{ni}}
{\sum_{n=1}^N \gamma(z_{nk})}
\tag{13.23}
\end{align}
を得る。（証明終）
##命題B-1
観測値 $x$ が複数あり、それぞれがベルヌーイ分布に従う場合、隠れ変数を与えたときの観測値の条件付き分布 $p(\x|\z)$ は以下のようになる。
p(\x|\z) = \prod_{i=1}^D \prod_{k=1}^K \mu_{ik}^{x_i z_k} (1-\mu_{ik})^{(1-x_i)z_k}
\ \ (k = 1,...,K) \tag{ex3.1}
**証明** まず、問題設定を確認する。いま、潜在変数 $\z$ は離散変数であり、1-of-K符号化によって表されている長さ $K$ のベクトルである。一方、観測変数 $\x$ は複数の二値変数(0/1)で構成される。観測変数の数を $D$ とする。
いま求めたいのは、条件付き分布 $p(\x|\z)$ である。これを定義するには、潜在変数の $K$ 個の状態と、$D$ 個の観測変数を結び付ける出力確率を設定すればよい。出力確率は $KD$ 個のパラメータで設定され、それらは
```math
p(x_i|z_k = 1) = \mu_{ik}^{x_i} (1-\mu_{ik})^{1-x_i}
\ \ (i = 1,...,D,\ k = 1,...,K) \tag{ex3.2}
と定義される。ゆえに、$\x = (x_1, ..., x_D)$ の同時分布は
p(\x|z_k = 1) = \prod_{i=1}^D \mu_{ik}^{x_i} (1-\mu_{ik})^{1-x_i}
\ \ (k = 1,...,K) \tag{ex3.3}
となり、更に $\z$ に関して式を統合することで式 $(\rm ex3.1)$ が得られる。（証明終）
##命題B-2
観測値 $x$ が複数あり、それぞれがベルヌーイ分布に従う場合、Mステップの方程式、すなわち $Q(\boldsymbol{\theta}, \boldsymbol{\theta}^{\rm old})$ を最大化する $\boldsymbol{\theta}$ の導出式は以下のようになる。
\mu_{ik} = \frac{\sum_{n=1}^N \gamma(z_{nk}) x_{ni}}{\sum_{n=1}^N \gamma(z_{nk})}
\tag{ex4.1}
**証明** 本文では完全データ対数尤度関数の期待値 $Q(\th, \tho)$ を式 $(13.17)$ のように書き下していた。このうち、観測変数 $\X$ に関わるのは第３項のみであり、$p(\x|z_{nk})$ を命題B-1で導いた式 $(\rm ex3.2)$ で置き換えることで、この場合の $Q(\th, \tho)$ が得られる。
```math
\begin{align}
Q(\th, \tho)
=&\
\sum_{k=1}^K \gamma(z_{1k}) \ln \pi_k
+ \sum_{n=2}^N \sum_{j=1}^K \sum_{k=1}^K \xi(z_{n-1,j}, z_{nk}) \ln A_{jk}
\\
&+ \sum_{n=1}^N \sum_{k=1}^K \gamma(z_{nk})
\sum_{i=1}^D \{ x_{ni} \ln \mu_{ik} + (1-x_{ni}) \ln (1-\mu_{ik}) \}
\tag{ex4.2}
\end{align}
求めたいMステップの方程式、すなわち $Q(\th, \tho)$ を最大化する $\mu_{ik}$ の導出式は、$(\rm ex4.2)$ を微分することで得られる。$\mu_{ik}$ に関わるのは第３項のみなので、それ以外の項は無視してよい。計算すると以下のようになる。
\begin{align}
0 &= \sum_{n=1}^N \gamma(z_{nk})
\left( \frac{x_{ni}}{\mu_{ik}} - \frac{1-x_{ni}}{1-\mu_{ik}} \right)
\\
0 &= \sum_{n=1}^N \gamma(z_{nk})
\frac{x_{ni}(1-\mu_{ik}) - (1-x_{ni})\mu_{ik}}{\mu_{ik}(1-\mu_{ik})}
\\
0 &= \sum_{n=1}^N \gamma(z_{nk}) (x_{ni}-\mu_{ik})
\\
\mu_{ik} &= \frac{\sum_{n=1}^N \gamma(z_{nk}) x_{ni}}{\sum_{n=1}^N \gamma(z_{nk})}
\tag{ex4.3}
\end{align}
よって、題意は示された。（証明終）