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

はじめに

本記事は, 機械学習の教科書の決定版ともいえる, Christopher Bishop先生による『Pattern Recognition and Machine Learning （パターン認識と機械学習）』, 通称PRMLの演習問題のうち, 私が解いた問題の解答を記したものです. これは, 私の所属する生物測定学研究室の輪読会でPRMLを取り扱っており, その勉強の一環として演習問題を解いたときのものです. なお, 他の演習問題の解答例に関する記事については, PRML　演習問題　解答集　まとめをご覧ください.

問題

2つの変数 $\mathbf{ x }$, $\mathbf {y}$ を考え, 同時分布を $p ( \mathbf{ x }, \mathbf{ y }）$ とする． この変数の組の微分エントロピーが

$$
\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) は, 離散変数のエントロピー

\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 }$ 分を無視したもので,

\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 } ]$ に関しては,

\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) 式の右辺を見比べてみると,

\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) 式は,

\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 }$ が独立であるとき, またそのときに限り成り立つことがわかります.

まとめると,

\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）を証明せよ．

条件付きエントロピーは,

\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) 式の左辺に代入することで展開を進めていくと,

\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 } ]$ の定義は,

\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) 式に近づけていくことを考えます. すると,

\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) 式の証明を行うことができました.