PRML　式(13.17)の導出

この記事では統計学・機械学習の教科書である、C. M. Bishop 著「パターン認識と機械学習」（略称：PRML）の演習問題を私が解いた結果を載せています。この本は私が所属する研究室の輪読会で現在扱われていて、勉強の一環として演習問題を解いています。

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

　この記事の中では、練習問題の解答ではなく、教科書内に出てくる式の導出について記述しました。

#命題

　以下のような隠れマルコフモデルを考える。

```math
\begin{align}
p(\z_n|\z_{n-1}, \boa{A})
=&\ 
\prod_{k=1}^K \prod_{j=1}^K A_{jk}^{z_{n-1,j}\ z_{nk}}
\tag{13.7}
\\
p(\z_1|\bog{\pi})
=&\ 
\prod_{k=1}^K \pi_k^{z_{1k}}
\tag{13.8}
\\
p(\x_n|\z_n,\bog{\phi})
=&\ 
\prod_{k=1}^K p(\x_n|\bog{\phi}_k)^{z_{nk}}
\tag{13.9}
\\
p(\X,\Z|\th)
=&\ 
p(\z_1|\bog{\pi})
\left[ \prod_{n=2}^N p(\z_n|\z_{n-1}, \boa{A}) \right]
\prod_{m=1}^N p(\x_m|\z_{m}, \bog{\phi})
\tag{13.10}
\end{align}
```

　この時、パラメータをEMアルゴリズムで推定するために必要な、完全データ対数尤度関数の期待値

```math
\begin{align}
Q(\th, \tho)
=&
\mathbb{E}_{\Z | \tho} [\ln p(\X,\Z|\th)]
\\=&
\sum_\Z p(\Z|\X,\tho) \ln p(\X,\Z|\th)
\tag{13.12}
\end{align}
```

　は、以下のようになる。

```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}) \ln p(\x_n|\phi_k)
\tag{13.17}
\end{align}
```

　なお、$\gamma, \xi$ は以下のように定義される。

```math
\begin{align}
\gamma(\z_n) =&\ p(\z_n|\X,\tho) \tag{13.13}
\\
\xi(\z_{n-1},\z_n) =&\ p(\z_{n-1},\z_n|\X,\tho) \tag{13.14}
\\
\gamma(z_{nk}) =&\ \mathbb{E} [z_{nk}]
\\ =& \sum_{\z_n} \gamma(\z_n) z_{nk} \tag{13.15}
\\
\xi(z_{n-1,j},z_{nk}) =&\ \mathbb{E} [z_{n-1,\ j},z_{nk}]
\\ =& \sum_{\z_{n-1},\ \z_n} \xi(\z_{n-1},\z_n) z_{n-1,j} z_{nk} \tag{13.16}
\end{align}
```



#証明

```math
\begin{align}
Q(\th, \tho)
=&\ 
\sum_\Z p(\Z|\X,\tho) \ln p(\X,\Z|\th)
\tag{13.12}
\end{align}
```

　
　$Q(\th, \tho)$ を構成する要素のうち、同時分布 $p(\X,\Z|\th)$ の対数は、式 $(13.10)$ のように３つの項の和に分けられるので、それぞれに関して考える。

## 第１項

　第１項は $\z_1$ に注目して変形する。そのため、$\Z$ から $\z_1$ を除いたものを $\Z_{/1}$ と表記する。

```math
\begin{align}
&\ 
\sum_\Z p(\Z|\X,\tho)
\ln p(\z_1|\bog{\pi})
\\=&\ 
\sum_{\z_1} \sum_{\Z_{/1}} 
p(\z_1|\X,\tho) p(\Z_{/1}|\z_1\X,\tho)
\ln p(\z_1|\bog{\pi})
\\=&\ 
\sum_{\z_1} \left[ p(\z_1|\X,\tho) \ln p(\z_1|\bog{\pi})
\sum_{\Z_{/1}} p(\Z_{/1}|\z_1\X,\tho) \right]
\\=&\ 
\sum_{\z_1} p(\z_1|\X,\tho) \ln p(\z_1|\bog{\pi})
\\=&\ 
\sum_{k=1}^K \gamma(z_{1k}) \ln \pi_k
\tag{ex.1}
\end{align}
```

　以上より、求める式 $(13.17)$ の第１項を導出することができた。

## 第２項

　対象とする式は以下である。

```math
\begin{align}
&\ 
\sum_\Z \left[ p(\Z|\X,\tho) 
\ln \left( \prod_{n=2}^N p(\z_n|\z_{n-1}, \boa{A}) \right) \right]
\\=&\ 
\sum_\Z \left[ p(\Z|\X,\tho) 
\sum_{n=2}^N \ln p(\z_n|\z_{n-1}, \boa{A}) \right]
\tag{ex.2}
\end{align}
```

　２つ目のシグマ記号の各要因 $(n=2,...,N)$ について、更に分解して考える。$\Z$ から $\z_{n-1},\z_n$ を除いたものを $\Z_{/n-1,n}$ と表記する。


```math
\begin{align}
&\ 
\sum_\Z p(\Z|\X,\tho) \ln p(\z_n|\z_{n-1}, \boa{A})
\\=&\ 
\sum_{\z_n} \sum_{\z_{n-1}} \sum_{\Z_{/n-1,n}}
p(\z_n,\z_{n-1}|\X,\tho) p(\Z_{/n-1,n}|\z_n,\z_{n-1},\X,\tho) 
\ln p(\z_n|\z_{n-1}, \boa{A})
\\=&\ 
\sum_{\z_n} \sum_{\z_{n-1}} \left[
p(\z_n,\z_{n-1}|\X,\tho) \ln p(\z_n|\z_{n-1}, \boa{A})
\sum_{\Z_{/n-1,n}}
p(\Z_{/n-1,n}|\z_n,\z_{n-1},\X,\tho) \right]
\\=&\ 
\sum_{\z_n} \sum_{\z_{n-1}}
p(\z_n,\z_{n-1}|\X,\tho) \ln p(\z_n|\z_{n-1}, \boa{A})
\\=&\ 
\sum_{j=1}^K \sum_{k=1}^K \xi(z_{n-1,j}, z_{nk}) \ln A_{jk}
\tag{ex.3}
\end{align}
```

　これを $n=2,...,N$ において足し合わせることで、求める式 $(13.17)$ の第２項を導出することができる。

```math
\begin{align}
& \ \sum_\Z \left[ p(\Z|\X,\tho) 
\ln \left( \prod_{n=2}^N p(\z_n|\z_{n-1}, \boa{A}) \right) \right]
\\=& \  
\sum_{n=2}^N \sum_{j=1}^K \sum_{k=1}^K \xi(z_{n-1,j}, z_{nk}) \ln A_{jk}
\tag{ex.4}
\end{align}
```


## 第３項

```math
\begin{align}
&\ 
\sum_\Z p(\Z|\X,\tho) 
\ln \prod_{m=1}^N p(\x_m|\z_{m}, \bog{\phi})
\\=&\ 
\sum_\Z \left[ p(\Z|\X,\tho) 
\sum_{m=1}^N \ln p(\x_m|\z_{m}, \bog{\phi}) \right]
\tag{ex.5}
\end{align}
```

　こちらも、２つ目のシグマ記号の各要因 $(m=1,...,N)$ について、更に分解して考える。$\Z$ から $\z_m$ を除いたものを $\Z_{/m}$ と表記する。


```math
\begin{align}
&\ 
\sum_\Z p(\Z|\X,\tho) \ln p(\x_m|\z_{m}, \bog{\phi})
\\=&\ 
\sum_{\z_m} \sum_{\Z_{/m}} 
p(\z_m|\X,\tho) p(\Z_{/m}|\z_m,\X,\tho) \ln p(\x_m|\z_{m}, \bog{\phi})
\\=&\ 
\sum_{\z_m} \left[ 
p(\z_m|\X,\tho) \ln p(\x_m|\z_{m}, \bog{\phi})
\sum_{\Z_{/m}}  p(\Z_{/m}|\z_m,\X,\tho) \right]
\\=&\ 
\sum_{\z_m} p(\z_m|\X,\tho) \ln p(\x_m|\z_{m}, \bog{\phi})
\\=&\ 
\sum_{k=1}^K \gamma(z_{nk}) \ln p(\x_n|\phi_k)
\tag{ex.6}
\end{align}
```

　これを $m=1,...,N$ において足し合わせることで、求める式 $(13.17)$ の第３項を導出することができる。

```math
\begin{align}
&\ \sum_\Z p(\Z|\X,\tho) 
\ln \prod_{m=1}^N p(\x_m|\z_{m}, \bog{\phi})
\\=&\ 
\sum_{m=1}^N \sum_{k=1}^K \gamma(z_{mk}) \ln p(\x_m|\phi_k)
\tag{ex.7}
\end{align}
```

　以上より、題意

```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}) \ln p(\x_n|\phi_k)
\tag{13.17}
\end{align}
```

　は示された。