カルバック・ライブラーダイバージェンスの覚え方とか

機械学習

久しぶりにブログ記事を書いてみる．リハビリがてらに軽いノリの記事を．

機械学習の勉強を始めてロジスティック回帰あたりに来ると出てくるカルバック・ライブラーダイバージェンス (以下KLd) ．機械学習以外の文脈でも分布同士を比較する場合にまっさきに出てくる．僕は輪講などでKLdが出てくるたびに


「ふぅん，ここでカルバック・ライブラーダイバージェンスを使うんだぁ・・・」


とか言って通ぶっていたけれど，実は空で式を書けなかった．実に痛い子である．だって覚えづらい．とにかく覚えづらい．- \sum_x P(x) \log \frac{P(x)}{Q(x)} だっけ? - \sum_x P(x) \log \frac{Q(x)}{P(x)} だっけ? Q/P とか P/Q とかせっかく分子分母の順番を覚えても先頭にマイナスつけると分子分母が入れ替わるからまた性質が悪い．


というわけで「じゃあちょっと書いてみて」と先生に当てられた際に，黒板に向かってスラスラと書くための覚え方を紹介してみる．


さて，KLdといえば (非対称な) 分布の類似度である．よく説明で言われるのが「真の分布Pと，それ以外の分布Qとの類似度」というもの．KLdでは，平均符号長の差で類似度を測る．

(類似度というと大きい方が似ているように聞こえてまぎらわしいと思う方は，「逆類似度」と呼んだり，(非対称なので厳密な意味で距離ではないのだけれど，語感的にしっくりくる方は) 「距離」と呼んだりしてください．「ダイバージェンス」と呼ぶのが一番いいのかな．)


そこでKLdという名前でまるっと覚えないで，「真の分布Pで符号化した際の平均符号長 (A)」と「分布Qで符号化した際の平均符号長 (B)」の差で覚えてみる．

(A)はエントロピーの定義，(B)はクロスエントロピーと呼ばれる．クロスエントロピーは真の分布以外の分布に基づいて符号化したものについて，真の分布で期待値を取ったもの．Qが真の分布に近ければ近いほど，平均符号長はエントロピーに近づく．

さて，(A)と(B)どちらの符号の方が長くなるかといえば，当然(B)である．無記憶情報源においてはエントロピーが最小符号になるため，どんなにがんばっても(B)を(A)未満の符号にすることはできない．これについては後ほど証明する．

なので，

KLd =  (B) - (A)

あとは，それぞれを書き下してみる．

(B) = \sum_x P(x) \log \frac{1}{Q(x)}
(A) = \sum_x P(x) \log \frac{1}{P(x)}

(B) - (A) = \sum_x P(x) \log \frac{1}{Q(x)} - \sum_x P(x) \log \frac{1}{P(x)} = \sum_x P(x) \log \frac{P(x)}{Q(x)}

というわけで，これが正解．先頭にマイナスをつけるときはlogの分子分母を反転させる．

僕は，KLdの式を書くときに

平均符号長の差だから，長い方(B: クロスエントロピー)から短い方(A: エントロピー) を引く

とつぶやきながら書いている．この覚え方を始めてからKLdを忘れなくなった．今までKLdを覚えられなかったみなさまもドヤ顔で説明してください．

KLd ≧ 0 の証明 (= エントロピーが最小符号になる証明)

ついでにKLdが0以上になる証明，言い換えるとエントロピーが (無記憶情報源，すなわちユニグラムの世界において) 最小符号になる証明の自分用メモ．

- \sum_x P(x) \log P(x) \le - \sum_x P(x) \log Q(x)

ちなみにこいつはどうやらギブスの不等式と呼ばれるらしい．(シャノンの補助定理だと思い込んでいたけれど，どうやらちょっと違うみたい)

これには色んな証明方法がある，例えばぱっと見つかるだけで

  • (1) \log x \le x - 1 を利用するもの (ギブスの不等式 - Wikiedia)
  • (2) 対数和不等式を利用するもの ([1]など)
  • (3) Jensenの不等式を利用するもの ([1]など)

がある．全部眺めたけれど，自分にとって一番簡単な方法が(3)Jensenの不等式を使った方法だったので，これを紹介．

Jensenの不等式とはなんぞや? という方はググるか，このブログで以前書いたJensenの不等式の使い方に関する記事をご覧ください．


さて，

- \sum_x P(x) \log P(x) \le - \sum_x P(x) \log Q(x)

これをKLdの形にする

- \sum_x P(x) \log \frac{Q(x)}{P(x)} \ge 0

マイナス符号をシグマの中に入れる (ちょっとテクい)

\sum_x P(x) \left( - \log \frac{Q(x)}{P(x)} \right) \ge 0

ここでY = Q(x)/P(x)とおくと，上式の左辺は

\sum_x P(x) \left( - \log Y \right)

となる．対数は凹関数なので - \log Y は凸関数になる．ここでJensenの不等式が発動する．Jensenの不等式によるとE( f(x) ) \ge f( E(x) )なので，

\sum_x P(x) \left( - \log Y \right) \ge - \log \sum_x P(x) Y = - \log \sum_x P(x) \frac{Q(x)}{P(x)} = - \log 1 = 0

したがって，

- \sum_x P(x) \log \frac{Q(x)}{P(x)} \ge 0

を示すことができた．(証明おわり)

等号が成立するのはQ(x) = P(x) のときだけで，それ以外の場合はP(x)に基づく符号化が最小符号になることを示した．


情報理論の教科書の最初の方に書いてあることだけれど，こうやって手持ちの道具で説明できるとなんだかうれしい．[1]は，一昨年に購入してからずっと積読だったけれど，少しずつ読み進められるようになってきた．情報理論に関する名著は多いと思うけれど，この本も間違いなく名著の一冊だと思う．

参考文献

  • [1] 情報と符号化の数理

情報と符号化の数理

情報と符号化の数理


2011-07-23追記

takeda25 さんいただいたご指摘を元にtypoと見づらい部分を修正しました．どうもありがとうございます!