information gainについてメモ1

information gainについてメモ1

decision treeの説明で出てきたID3アルゴリズムの説明で省略したinformation gainという量についてメモ。 キーワードとしては、Kullback-Leibler divergence, エントロピー、情報量のことが分かればよさそう。 まずは情報量について調べた範囲でメモ。

情報量とは何であってほしいか

Xは離散確率変数で、何らかの事象を表すものとする。 Xの値xを観測したときの「情報量」*1を考える。 情報量は、以下の性質を満たすものとする。 *2

  • 1.情報量は0以上の値をとる。
  • 2.確率p(x)の小さい事象xを観測した（あまり起こりそうにないことが起こった）場合、確率p(x)の大きい事象を観測した（いつでも起こりそうなことが起こった）場合に比べて、得られる情報量は多い。
  • 3.事象x, yが無関係の場合、その2つによって得られる情報量はそれぞれの情報量の和である。
  • 4.事象xは、その確率p(x)を通してのみ、情報量に影響する。

先に結論

事象xによって得られる情報量をh(x)と書くことにする。

{\displaystyle h(x) = -\log(p(x)) }

とするのが妥当である。 *3 *4

理由

上記の性質から、以下を仮定してよい。*5

  • （4から）区間(0,1) *6で定義された関数fが存在して、h(x) = f(p(x)).
  • （1から）上記fは、常に0以上の値をとる。
  • （2から）上記fは、単調減少である。*7
  • （3から）上記fは、s, t \in (0,1)のとき、f(st)=f(s)+f(t)を満たす。

a=\frac{1}{2}, \alpha=f(\frac{1}{2})とする。
このとき正整数m, nに対してf( a^{\frac{m}{n}}) = \frac{m}{n}\alpha.
したがって 0\lt a^{r}\lt 1であるすべての有理数r\gt 0についてf(a^{r})=r \alpha.
したがってt \in \{a^{r}|r \in \mathbb{Q}\} \cap (0,1)のときf(t) = \alpha \log_a t.
区間(0,1)で\{a^{r}|r \in \mathbb{Q}\}は稠密なので、fの単調性から

{\displaystyle f(t) = -\alpha\log_2 t }

がすべてのt\in (0,1)で成り立つ。 *8 *9

ここで\alphaの値は確定されていないが、 fに関する制約が上記の4つの仮定だけであれば、 \alphaは\alpha>0の範囲で自由に選択することができる。

対数の底の変化は、この\alphaの選択によって吸収できる。 たとえば \alpha = \log_e 2 とすれば、

{\displaystyle f(t) = -\log_e t }

が得られる。 その意味で、対数の底は自由に選択することができる。 状況に応じて便利なものを使えばよい。

参考

PRML 1章 http://www.amazon.co.jp/dp/4621061224

■Wikipedia - Information gain in decision trees https://en.wikipedia.org/wiki/Information_gain_in_decision_trees

*1:PRML（という本）では「驚きの度合い」と呼んでいる。

*2:これらの性質は、気分とか感覚によって納得するべき前提であって、何か根拠があって論理的に導かれるようなものではない。 もし納得できなくても、とりあえず仮定しておくことにする。

*3:対数の底は1より大きければ何でもよいが、だいたい2かeを使う。

*4:「妥当である」という言葉遣いに違和感を覚える人がいるかもしれないが、今回は「情報量」という言葉に定義を与えるのが目的である。 主張していることは、何かが数学的に正しいことではなく、定義が妥当であることだから、この表現が正しい。

*5:本当によいかどうか検討が必要な部分はあるが省略する。

*6: 0\lt x\lt 1であるような実数xの集合のこと。

*7:tが大きくなるとf(t)は小さくなるということ。

*8:このあたりの議論はだいぶ省略してあるので、できれば1ステップずつ確認したほうが良い。

*9:fの微分可能性を仮定すれば、このあたりの話はもっと簡単に済む。tf'(t)がtによらず一定であることを言えばよい。