PRML　演習問題 1.31（標準）　解答

## はじめに
本記事は, 機械学習の教科書の決定版ともいえる, **Christopher Bishop先生**による[**『Pattern Recognition and Machine Learning （パターン認識と機械学習）』**](https://www.microsoft.com/en-us/research/people/cmbishop/prml-book/), 通称**PRML**の演習問題のうち, 私が解いた問題の解答を記したものです. これは, 私の所属する[生物測定学研究室](https://www.ut-biomet.org/)の輪読会で**PRML**を取り扱っており, その勉強の一環として演習問題を解いたときのものです. なお, 他の演習問題の解答例に関する記事については, [PRML　演習問題　解答集　まとめ](https://qiita.com/Lab_of_Biomet/items/15e38ca34fafa8176d89)をご覧ください.


## 問題
> 2つの変数 $\mathbf{ x }$, $\mathbf {y}$ を考え, 同時分布を $p ( \mathbf{ x }, \mathbf{ y }）$ とする． この変数の組の微分エントロピーが
<a id="eq:1.152"></a>
$$
\begin {align*}
\mathrm { H } [ \mathbf { x } , \mathbf { y } ] \leq \mathrm { H } [ \mathbf { x } ] + \mathrm { H } [ \mathbf { y } ] 
\tag{1.152}
\end{align*}
$$
を満たし等号は $\mathbf{ x }$ と $\mathbf{ y }$ が統計的に独立なとき, またそのときに限ることを示せ．




## 微分エントロピー
**微分エントロピー** (differential entropy) は, 離散変数のエントロピー
<a id="eq:1.98"></a>

```math
\begin {align*}
\mathrm { H } [ p ] = - \sum _ { i } p \left( x _ { i } \right) \ln p \left( x _ { i } \right)
\tag{1.98}
\end{align*}
```

を連続変数に拡張し, $\Delta \rightarrow 0$ ($\Delta$ は微小区間) の極限で発散する $\ln { \Delta }$ 分を無視したもので, 
<a id="eq:1.104"></a>

```math
\begin {align*}
\mathrm { H } [ \mathbf { x } ] = - \int p ( \mathbf { x } ) \ln p ( \mathbf { x } ) \mathrm { d } \mathbf { x }
\tag{1.104}
\end{align*}
```
のように表される値です.


## 基本的な考え方
この問題を解くにあたって, 一つの解法は $\mathrm { H } [ \mathbf { x } , \mathbf { y } ]$, $\mathrm { H } [ \mathbf { x } ]$, $\mathrm { H } [ \mathbf { y } ]$ のそれぞれを (1.104) 式に代入して, なんとかして (1.152) 式の不等式を証明する, という方法でしょう. しかし, この方法は少し面倒な上, この不等式の持つ意味も理解しにくいのが問題です.
そこで, ここではPRMLの本文にて紹介されている等式・不等式を用いてこの問題を解いていきましょう.
まず, (1.152) 式の左辺, すなわち $\mathrm { H } [ \mathbf { x } , \mathbf { y } ]$ に関しては,
<a id="eq:1.112"></a>

```math
\begin {align*}
\mathrm { H } [ \mathbf { x } , \mathbf { y } ] = \mathrm { H } [ \mathbf { y } | \mathbf { x } ] + \mathrm { H } [ \mathbf { x } ]
\tag{1.112}
\end{align*}
```

という関係が成り立つことが紹介されています （演習問題 1.37）. この式は, $\mathbf { x }$, $\mathbf { y }$ の同時確率の微分エントロピーが, $\mathbf { x }$ に関する微分エントロピーと, $\mathbf { y }$ を $\mathbf { x }$ で条件付けた時の条件付き微分エントロピーの和に等しい, ということを表しており, 直感的にも納得のいく等式ですね.
さて, (1.152) 式の右辺と (1.112) 式の右辺を見比べてみると,
<a id="eq:1.31.1"></a>

```math
\begin {align*}
\left( \mathrm { H } [ \mathbf { x } ] + \mathrm { H } [ \mathbf { y } ] \right) - \left( \mathrm { H } [ \mathbf { y } | \mathbf { x } ] + \mathrm { H } [ \mathbf { x } ] \right) = \mathrm { H } [ \mathbf { y } ] - \mathrm { H } [ \mathbf { y } | \mathbf { x } ] \geq 0
\tag{1.31.1}
\end{align*}
```

を示すことができれば,  (1.152) 式が証明できることがわかります. 
実はこの (1.31.1) 式は,

<a id="eq:1.121"></a>

```math
\begin {align*}
\mathrm { I } [ \mathbf { x } , \mathbf { y } ] = \mathrm { H } [ \mathbf { x } ] - \mathrm { H } [ \mathbf { x } | \mathbf { y } ] = \mathrm { H } [ \mathbf { y } ] - \mathrm { H } [ \mathbf { y } | \mathbf { x } ]\tag{1.121}
\end{align*}
```

にある通り （演習問題 1.41）, **相互情報量** (mutual information) とよばれる値で, この値は, 同時分布 $p ( \mathbf{ x }, \mathbf{ y }）$ と $p ( \mathbf { x } ) p ( \mathbf { y } )$ の間の**カルバック-ライブラーダイバージェンス** (Kullback-Leibler divergence) を表します. したがって, (1.121) 式は, $\mathrm { I } [ \mathbf { x } , \mathbf { y } ] \geq 0$ を満し, 等号は $\mathbf { x }$, $\mathbf { y }$ が独立であるとき, またそのときに限り成り立つことがわかります.

まとめると, 

<a id="eq:1.31.2"></a>

```math
\begin {align*}
\left ( \mathrm { H } [ \mathbf { x } ] + \mathrm { H } [ \mathbf { y } ] \right ) - \mathrm { H } [ \mathbf { x } , \mathbf { y } ] 
& = \left( \mathrm { H } [ \mathbf { x } ] + \mathrm { H } [ \mathbf { y } ] \right) - \left( \mathrm { H } [ \mathbf { y } | \mathbf { x } ] + \mathrm { H } [ \mathbf { x } ] \right) \\
& = \mathrm { H } [ \mathbf { y } ] - \mathrm { H } [ \mathbf { y } | \mathbf { x } ] \\
& = \mathrm { I } [ \mathbf { x } , \mathbf { y } ] \geq 0, \\
\tag{1.31.2}
\end{align*}
```

より, (1.152) 式を導けるというわけです. つまり, この問題から, 2つの変数があるとき, それぞれのエントロピーの和が, 同時確率のエントロピーと相互情報量の和に等しいことがわかります. 


## 補足の証明

### (1.112) 式の証明 （演習問題 1.37, 基本）
> （1.111）の定義と確率の乗法定理から, (1.112）を証明せよ．

条件付きエントロピーは, 
<a id="eq:1.111"></a>

```math
\begin {align*}
\mathrm { H } [ \mathbf { y } | \mathbf { x } ] = - \iint p ( \mathbf { y } , \mathbf { x } ) \ln p ( \mathbf { y } | \mathbf { x } ) \mathrm { d } \mathbf { y } \mathrm { d } \mathbf { x }
\tag{1.111}
\end{align*}
```

で定義されます. これを (1.112) 式の左辺に代入することで展開を進めていくと, 

<a id="eq:1.37.1"></a>

```math
\begin {align*}
\mathrm { H } [ \mathbf { y } | \mathbf { x } ] + \mathrm { H } [ \mathbf { x } ]
& = - \iint p ( \mathbf { y } , \mathbf { x } ) \ln p ( \mathbf { y } | \mathbf { x } ) \mathrm { d } \mathbf { y } \mathrm { d } \mathbf { x } - \int p ( \mathbf { x } ) \ln p ( \mathbf { x } ) \mathrm { d } \mathbf { x } \\
& = - \iint p ( \mathbf { y } , \mathbf { x } ) \ln p ( \mathbf { y } | \mathbf { x } ) \mathrm { d } \mathbf { y } \mathrm { d } \mathbf { x } - \int p ( \mathbf { x } ) \ln p ( \mathbf { x } ) \mathrm { d } \mathbf { x } \int p ( \mathbf { y } | \mathbf { x } ) \mathrm { d } \mathbf { y } \\
& = - \int \left ( \int p ( \mathbf { y } , \mathbf { x } ) \ln p ( \mathbf { y } | \mathbf { x } ) \mathrm { d } \mathbf { y } + \int p ( \mathbf { x } ) p ( \mathbf { y } | \mathbf { x } ) \ln p ( \mathbf { x } ) \mathrm { d } \mathbf { y } \right ) \mathrm { d } \mathbf { x } \\
& = - \int \left ( \int \left \{ p ( \mathbf { y } , \mathbf { x } ) \ln p ( \mathbf { y } | \mathbf { x } ) + p ( \mathbf { y } , \mathbf { x } ) \ln p ( \mathbf { x } ) \right \} \mathrm { d } \mathbf { y } \right ) \mathrm { d } \mathbf { x } \\
& = - \iint  p ( \mathbf { y } , \mathbf { x } ) \ln p ( \mathbf { y } , \mathbf { x } ) \mathrm { d } \mathbf { y } \mathrm { d } \mathbf { x } \\
& = \mathrm { H } [ \mathbf { x } , \mathbf { y } ]
\tag{1.37.1}
\end{align*}
```

と変形できるため, (1.112) 式の証明ができました. なお, 確率の乗法定理 $p ( \mathbf { y } , \mathbf { x } ) = p ( \mathbf { y } | \mathbf { x } ) p ( \mathbf { x } )$ を用いました.


### (1.121) 式の証明 （演習問題 1.41, 基本）

> 確率の加法・乗法定理を使って, 相互情報量 $\mathrm { I } [ \mathbf { x } , \mathbf { y } ]$ が（1.121）の関係を満たすことを示せ．

相互情報量 $\mathrm { I } [ \mathbf { x } , \mathbf { y } ]$ の定義は,
<a id="eq:1.120"></a>

```math
\begin {align*}
\mathrm { I } [ \mathbf { x } , \mathbf { y } ] & \equiv \mathrm { KL } ( p ( \mathbf { x } , \mathbf { y } ) \| p ( \mathbf { x } ) p ( \mathbf { y } ) ) \\ & = - \iint p ( \mathbf { x } , \mathbf { y } ) \ln \left( \frac { p ( \mathbf { x } ) p ( \mathbf { y } ) } { p ( \mathbf { x } , \mathbf { y } ) } \right) \mathrm { d } \mathbf { x } \mathrm { d } \mathbf { y }
\tag{1.120}
\end{align*}
```

でした. 今度は, (1.121) 式の一番左辺を変形していくことで, (1.120) 式に近づけていくことを考えます. すると, 

<a id="eq:1.41.1"></a>

```math
\begin {align*}
\mathrm { H } [ \mathbf { y } ] - \mathrm { H } [ \mathbf { y } | \mathbf { x } ]
& =  - \int p ( \mathbf { y } ) \ln p ( \mathbf { y } ) \mathrm { d } \mathbf { y } + \iint p ( \mathbf { y } , \mathbf { x } ) \ln p ( \mathbf { y } | \mathbf { x } ) \mathrm { d } \mathbf { y } \mathrm { d } \mathbf { x } \\
& = - \int p ( \mathbf { y } ) \ln p ( \mathbf { y } ) \mathrm { d } \mathbf { y } \int p ( \mathbf { x } | \mathbf { y } ) \mathrm { d } \mathbf { x } + \iint p ( \mathbf { y } , \mathbf { x } ) \ln p ( \mathbf { y } | \mathbf { x } ) \mathrm { d } \mathbf { y } \mathrm { d } \mathbf { x } \\
& = - \int \left ( \int p ( \mathbf { y }, \mathbf { x } ) \ln p ( \mathbf { y } ) \mathrm { d } \mathbf { y } - \int p ( \mathbf { y } , \mathbf { x } ) \ln p ( \mathbf { y } | \mathbf { x } ) \mathrm { d } \mathbf { y } \right ) \mathrm { d } \mathbf { x } \\
& = - \int \left ( \int p ( \mathbf { y }, \mathbf { x } ) \ln \left ( \frac { p ( \mathbf { y } ) } { p ( \mathbf { y } | \mathbf { x } ) } \right ) \mathrm { d } \mathbf { y } \right ) \mathrm { d } \mathbf { x } \\
& = - \iint p ( \mathbf { x } , \mathbf { y } ) \ln \left( \frac { p ( \mathbf { x } ) p ( \mathbf { y } ) } { p ( \mathbf { x } , \mathbf { y } ) } \right) \mathrm { d } \mathbf { x } \mathrm { d } \mathbf { y } \\
& = \mathrm { KL } ( p ( \mathbf { x } , \mathbf { y } ) \| p ( \mathbf { x } ) p ( \mathbf { y } ) ) = \mathrm { I } [ \mathbf { x } , \mathbf { y } ] 
\tag{1.41.1}
\end{align*}
```

と展開でき, (1.121) 式の証明を行うことができました.