期待値伝播法

# 記事の概要
[『ベイズ深層学習』勉強会資料　4章の2.1~2.4](https://qiita.com/Kosuke_Matsui/items/96909df659428c17a2c9)において期待値伝播法の理解が不十分だったので、PRMLの10.7を学習した。

# モーメント一致法
KLダイバージェンスの最小化を行う手法の１つがモーメント一致法である。

固定された確率分布$p(\mathbf{z})$に対する$KL(p||q)$を$q(\mathbf{z})$について最小化する。

$q(\mathbf{z})$を指数型分布族とすると以下の形で表現できる

```math
\begin{eqnarray}
q(\mathbf{z})
&=&
h(\mathbf{z})g(\mathbf{\eta}) \exp \{  \eta^T \mathbf{u}(\mathbf{z}) \}
\end{eqnarray}
```

これをKLダイバージェンスの定義に代入することで、以下のKLダイバージェンスを得る。

```math
\begin{eqnarray}
KL(p||q)
&=&
- \sum_{\mathbf{z}} p(\mathbf{z}) \ln \biggl\{   \frac{q(\mathbf{z}|\mathbf{X}, \theta)}{p(\mathbf{z})}  \biggl\} \\
&=&
- \sum_{\mathbf{z}} p(\mathbf{z}) \ln q(\mathbf{z}|\mathbf{X}, \theta) 
+ \sum_{\mathbf{z}} p(\mathbf{z}) \ln p(\mathbf{z}) \\
&=&
- \sum_{\mathbf{z}} p(\mathbf{z}) \ln ( h(\mathbf{z})g(\mathbf{\eta}) \exp \{  \eta^T \mathbf{u}(\mathbf{z}) \} ) 
+ const \\
&=&
- \sum_{\mathbf{z}} p(\mathbf{z}) \ln h(\mathbf{z}) 
- \sum_{\mathbf{z}} p(\mathbf{z}) \ln g(\mathbf{\eta})  
- \sum_{\mathbf{z}} p(\mathbf{z}) \eta^T \mathbf{u}(\mathbf{z}) 
+ const \\
&=&
const 
- \ln g(\mathbf{\eta})  
- \eta^T \mathbb{E}_{p(\mathbf{z})} [ \mathbf{u}(\mathbf{z}) ]
+ const \\
\end{eqnarray}
```

ここで$\sum_{\mathbf{z}} p(\mathbf{z}) = 1$を用いた。また$\mathbf{\eta}$を含まない項は定数項とした。

KLダイバージェンスを$\mathbf{\eta}$について変分を取り0とすれば

```math
\begin{eqnarray}
- \nabla_{\mathbf{\eta}} \ln g(\mathbf{\eta}) = \mathbb{E}_{p(\mathbf{z})} [ \mathbf{u}(\mathbf{z}) ]
\end{eqnarray}
```

を得る。ここで

```math
\begin{eqnarray}
\int q(\mathbf{z}) d \mathbf{z}
&=&
\int h(\mathbf{z})g(\mathbf{\eta}) \exp \{  \eta^T \mathbf{u}(\mathbf{z}) \} d \mathbf{z} \\
&=&
1
\end{eqnarray}
```

を$\mathbf{\eta}$について変分すると

```math
\begin{eqnarray}
&& \nabla_{\mathbf{\eta}} g(\mathbf{\eta}) \int h(\mathbf{z}) \exp \{  \eta^T \mathbf{u}(\mathbf{z}) \} d \mathbf{z} 
+ g(\mathbf{\eta}) \int h(\mathbf{z}) \exp \{  \eta^T \mathbf{u}(\mathbf{z}) \} \mathbf{u}(\mathbf{z}) d \mathbf{z} \\
&=&
\frac{1}{g(\mathbf{\eta}) } \nabla_{\mathbf{\eta}} g(\mathbf{\eta})  
+ \mathbb{E}_{q(\mathbf{z})} [\mathbf{u}(\mathbf{z})] \\
&=&
0
\end{eqnarray}
```

となるので

```math
\begin{eqnarray}
- \frac{1}{g(\mathbf{\eta}) } \nabla_{\mathbf{\eta}} g(\mathbf{\eta})  = \mathbb{E}_{q(\mathbf{z})} [\mathbf{u}(\mathbf{z})] 
\end{eqnarray}
```

$\partial \ln f(x) / \partial x = (1/f(x))*(\partial f(x) / \partial x)$より、先の最小化条件に代入して

```math
\begin{eqnarray}
\mathbb{E}_{p(\mathbf{z})} [ \mathbf{u}(\mathbf{z}) ]  = \mathbb{E}_{q(\mathbf{z})} [\mathbf{u}(\mathbf{z})] 
\end{eqnarray}
```

を得る。

# 近似推論

データ$D$と隠れ変数$\mathbf{\theta}$の同時分布を考える。各分布は独立であるとする。

```math
\begin{eqnarray}
p(D, \theta) = \prod_i f_i(\theta)
\end{eqnarray}
```

これを用いると事後分布$p(\theta|D)$は

```math
\begin{eqnarray}
p(\theta|D) 
&=& 
\frac{p(D, \theta)}{p(D)} \\
&=&
\frac{1}{p(D)} \prod_i f_i(\theta)
\end{eqnarray}
```

となる。ここで$p(D)$は

```math
\begin{eqnarray}
p(D)
&=&
\int \prod_i f_i(\theta) d \theta
\end{eqnarray}
```

である。
この$\theta$に対する周辺化が解析的に計算不可能である場合の近似法の１つが期待値伝播法である。

まず、事後分布として以下の近似を与える。

```math
\begin{eqnarray}
q(\theta) = \frac{1}{Z} \prod_i \widetilde{f_i}(\theta)
\end{eqnarray}
```

ここで$\widetilde{f_i}(\theta)$は$f_i(\theta)$のどれかである。$Z$は積分を1にするための正規化項とする。

この近似を用いた以下のKLダイバージェンスを最小化したいが、計算は不可能である。

```math
\begin{eqnarray}
KL(p||q)
&=& KL \Biggl( \frac{1}{p(D)} \prod_i f_i(\theta) \Biggl| \Biggl|  \frac{1}{Z} \prod_i \widetilde{f_i}(\theta) \Biggl)
\end{eqnarray}
```

そこで期待値伝播法を用いる。
まず、１つの因子$\widetilde{f_j}(\theta)$の近似を修正する。（最終的には全ての因子の近似を１つずつ同様の方法で修正する）
この$j$とそれ以外の因子の積を分けて

```math
\begin{eqnarray}
q^{new} (\theta) &\propto& \widetilde{f_j}(\theta)　\prod_{i \neq j} \widetilde{f_i}(\theta)
\end{eqnarray}
```

とする。ここでなるべく上式が、$j$因子について近似していない

```math
\begin{eqnarray}
f_j(\theta)　\prod_{i \neq j} \widetilde{f_i}(\theta)
\end{eqnarray}
```

に近い値になるように近似してやる。

因子$j$について扱うので、近似事後分布から$\widetilde{f_j}(\theta)$を取り除きたい。手っ取り早く取り除くには$\widetilde{f_j}(\theta)$で除算してやる。これは$\prod_{i \neq j} \widetilde{f_i}(\theta)$に相当する。

```math
\begin{eqnarray}
q^{/j}(\theta)
&\equiv&
\frac{q(\theta)}{\widetilde{f_j}(\theta)}
\end{eqnarray}
```

よって近似事後分布の近似は以下になる

```math
\begin{eqnarray}
\frac{1}{Z_j} f_j(\theta) q^{/j}(\theta)
\end{eqnarray}
```

ここで$Z_j$は以下の正規化定数である。

```math
\begin{eqnarray}
Z_j &=& \int f_j(\theta) q^{/j}(\theta) d \theta
\end{eqnarray}
```

$\widetilde{f_j}(\theta)$は以下のKLダイバージェンスを最小化することで求まる。

```math
\begin{eqnarray}
KL(p||q)
&=& KL \Biggl( \frac{1}{Z_j} f_j(\theta) q^{/j}(\theta) \Biggl| \Biggl|  q^{new} (\theta) \Biggl)
\end{eqnarray}
```
もしくは$q^{new} (\theta)$の定義より$\widetilde{f_j}(\theta)$を以下のように求める。

```math
\begin{eqnarray}
\widetilde{f_j}(\theta)
&=& K \frac{q^{new} (\theta)}{\prod_{i \neq j} \widetilde{f_i}(\theta)} \\
&=& K \frac{q^{new} (\theta)}{q^{/j}(\theta)} 
\end{eqnarray}
```

$K$は上式の両辺に$q^{/j}(\theta)$を掛けて積分することで求まる。

```math
\begin{eqnarray}
\int \widetilde{f_j}(\theta) q^{/j}(\theta) d \theta
&=& K \int q^{new} (\theta) d \theta \\
&=& K
\end{eqnarray}
```

ここで

```math
\begin{eqnarray}
\int \widetilde{f_j}(\theta) q^{/j}(\theta) d \theta
&=& \int f_j(\theta) q^{/j}(\theta) d \theta
\end{eqnarray}
```

となるようにすれば、$K=Z_j$となり$Z_j$を計算することで$K$が求まる。


## 関連記事
[『ベイズ深層学習』勉強会資料　4章の1](https://qiita.com/Kosuke_Matsui/items/5d90af26b14a51accece)
[『ベイズ深層学習』勉強会資料　4章の2.1~2.4](https://qiita.com/Kosuke_Matsui/items/96909df659428c17a2c9)
[『ベイズ深層学習』勉強会資料　5章の1](https://qiita.com/Kosuke_Matsui/items/304890f71d0828cb9e45)