今回も引き続き情報量(エントロピー)関係の記事です。直近、エントロピーに関する記事を複数書いていますが、その中でいくつか証明をしていない性質があります。シャノンの補助定理という面白い定理を使うとそれらが証明できるので見ていきます。
情報量の話なのでこの記事では底を省略して書いた対数関数の底は$2$とします。$\log=log_2$です。一方で、自然対数も使うのでそれは$\ln=\log_e$と書きます。
早速、シャノンの補助定理を見ていきます。
定理
二つの確率事象系$A = \{a_k | k=1,\dots, n \}$と$B = \{b_k | k=1,\dots, n\}$の確率をそれぞれ$p_k$, $q_k$とします。つまり、
$\sum_{k=1}^n p_k = 1$, $\sum_{k=1}^n q_k = 1$です。この時次の関係が成り立ちます。
$$ – \sum_{k=1}^n p_k\log{p_k} \leq – \sum_{k=1}^n p_k\log{q_k}.$$
以上が、シャノンの補助定理の主張です。左辺は$A$のエントロピーで、右辺は対数関数の中身だけ別の確率事象系の確率になっていますね。
証明
定理を証明する前に、自然体数に関する$\ln{x} \leq x – 1$ $(x > 0)$という関係を使うのでこれを先に証明します。
正の実数$x$に対して、$f(x) = x -1 – \ln{x}$ とおきます。すると$f'(x) = 1 – \frac{1}{x}$となります。$f'(x)$の値を見ていくと、 $0 < x < 1$ の時$f'(x)<0$であり、$f'(1)=0$、そして$1 < x$の時$f'(x)>0$となるので、$x=1$で最小値をとり、その値は$f(1) = 1-1-\ln{1} = 0$です。
よって、$f(x) \leq 0$であり、$\ln{x} \leq x – 1$ が示されました。
ここから定理の証明に入ります。定理の左辺から右辺を引いたものを考えて、底の変換をし、先ほどの関係式を適用します。
$$ \begin{align}
– \sum_k p_k \log{p_k} + \sum_k p_k\log{q_k} &= \sum_k p_k \log{\frac{q_k}{p_k}}\\
&=\frac{1}{\ln{2}} \sum_k p_k \ln{\frac{q_k}{p_k}}\\
&\leq \frac{1}{\ln{2}} \sum_k p_k \left(\frac{q_k}{p_k} – 1 \right)\\
&= \frac{1}{\ln{2}} \sum_k (q_k – p_k)\\
&= \frac{1}{\ln{2}} \sum_k q_k – \frac{1}{\ln{2}} \sum_k p_k\\
&=0\end{align}.$$
よって、$ – \sum_{k=1}^n p_k\log{p_k} \leq – \sum_{k=1}^n p_k\log{q_k}$ が示されました。等号が成立するのは$p_k = q_k$の場合です。
この補助定理を使って、エントロピー関連の性質を見ていきます。
応用1. エントロピーの最大値
最初に見ていくのは、「平均情報量(エントロピー)の定義について」で見た、エントロピーの範囲、$0 \le H(a) \le \log{n}$ の最大値の方です。これは、$q_k = \frac{1}{n}$としてシャノンの補助定理を使うと証明できます。
$$H(a) = – \sum_k p_k\log{p_k} \leq – \sum_k p_k\log{\frac{1}{n}} = \log{n}$$
となります。
応用2. 相互情報量が0以上であること
次に証明するのは、「相互情報量について」で最後に書いた、相互情報量が非負の値を取るという話です。
これは、シャノンの補助定理をそのまま2次元の確率分布に拡張して使います。
$k = 1, \dots, n$, $l = 1, \dots, m$とし、$\sum_{k, l} p_{kl} = 1$、$\sum_{k, l} q_{kl} = 1$とすると、
$$- \sum_k \sum_l p_{kl} \log{p_{kl}} \leq – \sum_k \sum_l p_{kl} \log{q_{kl}}$$
ですから、
$$\sum_k \sum_l p_{kl} \log{\frac{p_{kl}}{q_{kl}}} \geq 0$$
となります。ここで、$p_{kl} = P(a_k, b_l)$とし、$q_{kl} = P(a_k) P(b_l)$とすると、
$$\sum_k \sum_l P(a_k, b_l) \log{\frac{P(a_k, b_l)}{P(a_k) P(b_l)}} \geq 0$$
となります。この左辺が相互情報量$I(A; B)$の定義そのものなのでこれが非負であることが示されました。
応用3. 条件付きエントロピーがエントロピーより小さいこと
3つ目はさっきの相互情報量の話から続けて導けるものです。「結合エントロピーと条件付きエントロピー」で、重要な性質として$H(A|B) \le H(A)$が成り立つと証明無しで言いました。
これはシンプルに、$I(A; B) = H(A) – H(A|B)$であり、$I(A; B) \geq 0$なので、移項するだけで、$$H(A) \geq H(A|B)$$ が言えます。
まとめ
この記事ではシャノンの補助定理とその応用をいくつか紹介しました。応用1,2,3で証明したことはそれぞれの記事で証明無しで紹介していたのを個人的にモヤモヤしていたので、それを解消できてよかったです。
エントロピーの最大値についても、相互情報量の非負性についても結構シンプルな主張なのですが、シャノンの補助定理無しで証明するのは結構難しいのでこの定理の偉大さを感じます。
ここしばらくエントロピーの理論面の記事が続いていますが、次あたりでPythonで実際に計算する方法を紹介してこのシリーズを完結させようかなと思っています。