相対エントロピー (Kullback-Leibler divergence) と シャノンの補助定理

---

1.相対エントロピー

情報源 \(X, X'\) はどちらも\(N\)種類の同じ情報\(\{x\}\)を出力しますが、それぞれの確率は \(p(x),q(x)\) と異なっているとします。このとき、

相対エントロピー (relative entropy) \(H(p||q)\)

は以下で定義されます。 \[H(p||q) = \sum_x p(x)\log p(x) - \sum_x p(x)\log q(x)\tag{1}\] 情報理論の慣例にしたがって、対数の底は\(2\)とします。\(H(p||q)\)は、

Kullback-Leibler divergence

とも呼ばれる量です。今回は\(H(p||q)\)に関して、シャノンの補助定理と呼ばれる性質を証明して、ついでにエントロピーが最大になる確率分布がどんなものか考えます。

でもその前に、天下りに(1)で\(H(p||q)\)を定義したのでは、なぜこんなものを考えるのか全くピンとこないと思いますので、少し(1)式に関してその意味を補足しておきます。(1)式の第一項\(\sum_x p(x)\log p(x)\)は\(X\)のエントロピー\(H(X)\)です。だからこの項に関してはその意味は明らかであり、これは\(X\)の平均情報量という意味を持ちます。したがって、問題は第二項 \(\sum_x p(x)\log q(x)\) がどのような意味になるかということです。

\(-\log q(x)\)とは、\(q(x)\)という確率で生起する情報\(x\)の「情報量」を表しているのでした。この情報を\(0,1\)のビット列に直して、誰かに伝えたいという状況を考えてみましょう。\(q(x)\)という確率で生起する情報\(x\)を送るとき、どのくらいの長さのビット列で表すと、1番効率よく色々な情報\(\{x\}\)を送れるでしょうか。直感的には、情報量\(-\log q(x)\)に比例した長さのビット列で表せば、まれにしか起こらない大きな情報を長いビット列で、頻繁に起こる小さな情報短いビット列で送ることができ、平均的に効率が良くなりそうですよね。つまり\(-\log q(x)\)は情報量という意味の他に、効率的に情報を送りたいとき使うべきビット列の長さ (符号長) を表していると考えられます。

そうすると、通常のエントロピー\(-\sum_x q(x)\log q(x)\)は、\(q(x)\)という確率分布を持つ情報源の情報を送るときに必要な、「平均符号長」であると解釈できます。(1)式の第二項は、エントロピーから少し異なる形、\(-\sum_x p(x)\log q(x)\)でした。「平均符号長」という観点から、この式を解釈してみます。 平均符号長が1番短くできるのは、おそらく正しい確率分布\(p(x)\)で符号化した時でしょう。逆にそれ以外のときには、平均符号長は最適な符号化に比べて少し長くなってしまうと考えられます。そこで以下の性質が成り立ちそうです。 実はこれがシャノンの補助定理です。次のセクションで数学的に証明します。

---

---

2.シャノンの補助定理の証明

証明したいことは、 \[ H(p||q) = \sum_x p(x)\log p(x)-\sum_x p(x)\log q(x) \geq 0\] です。

証明には、\(\ln x\)に関して成り立つ不等式 \[-\ln x \geq 1-x\tag{2}\] を使います。等号成立は\(x=1\)のときだけです。グラフを書いてみれば、この不等式が成り立つことはすぐに分かるかと思います。ただし今回現れるのは底\(2\)の対数なので、(2)を少し書き換えた、 \[-\log x \geq \log e (1-x)\tag{3}\] を使いながら、\(H(p||q)\)を次のように変形して証明します。 \begin{align} H(p||q) &= \sum_x p(x)\log p(x)-\sum_x p(x)\log q(x) \\ &=-\sum_x p(x)\log \frac{q(x)}{p(x)}\\ &\geq \log e\sum_x p(x) \left(1-\frac{q(x)}{p(x)}\right)\\ &= \log e\left(\sum_x p(x) - \sum_x q(x)\right) \end{align} 最後に、\(p(x),q(x)\)がどちらも確率分布を表していたことを踏まえると、\(\sum_x p(x) = \sum_x q(x) = 1\)がですから、 \[H(p||q) \geq 0\] が言えます。これでシャノンの補助定理の骨子は証明できました。続いて等号成立条件について考えます。ここまでの式変形で不等号が入ったのは、(3)式を使って\(-\log \frac{q(x)}{p(x)} \geq 1-\frac{q(x)}{p(x)}\)としたところです。(3)式の等号が成立したのは\(x=1\)のときのみでしたから、\(q(x)=p(x)\)が等号成立条件です。と、いきたいところなのですが、実はそう簡単にはいきません。たしかに「\(q(x)=p(x)\)が成り立っているとき等号が成り立つ」とは言えますが、その逆、「等号が成り立っているならば\(q(x)=p(x)\)である」ということは(3)式の性質だけでは言えません。なぜなら今見た式変形の中には\(\sum_x\)が入ってしまっているからです。そこで、等号成立のための必要十分条件が厳密に\(p(x)=q(x)\)であることを示すには、次の数学的定理、Jensenの不等式を使います。(下に示したのは\(f(x)\)が微分可能であるときに限定したものです。) これを使ってもう一度証明してみましょう。\((-\log x)'' = \frac{\ln 2}{x^2} \gt 0\)が成り立つことに注意して、Jensenの不等式を利用します。 \begin{align} H(p||q) &= \sum_x p(x)\log p(x)-\sum_x p(x)\log q(x) \\ &=-\sum_x p(x)\log \frac{q(x)}{p(x)}\\ &\geq \log \left(\sum_x p(x) \frac{q(x)}{p(x)} \right)\\ &= \log \left(\sum_x q(x)\right)\\ &= 0 \end{align} となって、これでも証明できました。Jensenの不等式の等号成立条件から、等号成立は \(\frac{q(x)}{p(x)}\) が全ての\(x\)について等しくなるときに限られます。そこで定数\(a\)を使って \[\frac{q(x)}{p(x)} = a\] とおいてみます。そうすると、 \begin{align} \frac{q(x)}{p(x)} &= a\\ \sum_x q(x) &= a \sum_x p(x)\\ a &= 1 \end{align} となり、\(a=1\)であることが分かりました。したがって、等号成立は\(p(x)=q(x)\)が成り立つときだけです。一度まとめておきます。 ちなみに\(-\sum_x p(x)\log q(x)\)は

クロスエントロピー

と呼ばれます。クロスエントロピーは\(q(x)\)が\(p(x)\)に一致したときに最大値をとるという性質から、統計モデリングや機械学習の世界で用いられます。与えられたデータの分布\(p(x)\)と、コンピュータが生成する分布\(q(x)\)の一致度を測るのにちょうど良い量なのです。

---

3.エントロピーの最大値

シャノンの補助定理を用いると、エントロピーが最大となる場合を簡単に求められます。やってみましょう。

\(q(x)\)を一様分布\(q(x)=1/N\)とすると、\(\sum_x p(x) =1\)に注意して、シャノンの補助定理は \begin{align} -\sum_x p(x)\log \frac{1}{N} &\geq -\sum_x p(x)\log p(x)\\ \log N &\geq -\sum_x p(x)\log p(x) \end{align} と書き換えられます。この式は任意の確率分布\(p(x)\)について成り立ちますから、左辺は\(p(x)\)に関するエントロピーの最大値を示していると考えられます。さらにシャノンの補助定理の等号成立条件から、最大値となるのは\(p(x)=1/N\)であるときに限られます。したがって、次の定理を得ます。