Hatena::ブログ(Diary)

Mi manca qualche giovedi`? このページをアンテナに追加 RSSフィード Twitter

2010-08-27 おかげで情報量回りをしっかりやり直せた。

FSNLP 5.4 Mutual Information(相互情報量)

"Foundations of Statistical Natural Language Processing"(FSNLP, サイコロ本)を読んでいるが、5.4 Mutual Information で詰まった。

書いてあることがいろいろ腑に落ちない。

まあエントロピー関連がどうにも苦手というのもあるのだが、いくつか「本当にそうなの? なんかおかしくない?」という部分があるので、そこら辺含めてちょっとまとめてみた。


【追記】フォロー記事書きました → http://d.hatena.ne.jp/n_shuyo/20101006/pmi 【/追記】


なお、章題は "Mutual Information" だが、実際に扱っているのは pointwise mutual information(PMI) の事ばかり。


まず self-information(自己情報量) を定義しておこう。

確率変数 X とその事象 x について、「事象 x が起こったことを知らされたときに受け取る情報量」を I(X=x) = log 1/P(X=x) = -log P(X=x) と定義する。これが self-information。

log の底はeを使ったり10を使ったりするが、ここでは全部2とする。このとき情報量の単位は bit 。

例えばトランプを引いてどのマークか、はそれぞれ確率1/4なので、I(X= スペード)=-log(1/4)=2 となる。これは4種類のマークのどれを引いたのか、を表すのに 2bits の領域が必要であることに対応している。

定義から I(x)≧0。


次に確率変数 X, Y とそれぞれの事象 x, y について、「2つの事象 x, y の間の共起の度合いを測る尺度(の1つ)」を

  • PMI(X=x, Y=y)=¥log¥frac{P(X=x, Y=y)}{P(X=x)P(Y=y)}

と定義。これが pointwise mutual information(PMI)。

FSNLP では I(x',y') と書かれているが、self-information と紛れないように PMI() とした。


PMI は以下のように self-information で書き直せるので、一応単位は bit といってもいいはず。

  • PMI(x, y) = I(x)+I(y)-I(x, y)

ただし self-information と違い、PMI は負の値になることもある。


FSNLP では、'Ayatolah' と 'Ruhollah' という2つの単語(イスラム教の尊称かな?)の共起度を例としてあげている。

N = 14307668 tokens からなる New York Times コーパス中、'Ayatolah' が42回、'Ruhollah' が20回、そして 'Ayatolah Ruhollah' という bigram が20回出現している場合。

それぞれの確率を最尤法で推定すると、

  • P(Ayatolah) = 42/N
  • P(Ruhollah) = 20/N
  • P(Ayatolah Ruhollah) = 20/N

となり(bigram の分母はどうして N-1 じゃあないんだろう? まあ誤差だけど)、したがって PMI は

  • PMI(Ayatolah, Ruhollah) = ¥log¥frac{20/N}{42/N¥cdot 20/N} ¥approx 18.38

と求められる。


ここまではOK。

わからないのはこの次。以下 FSNLP の p179 より引用。

For example, the mutual information measure tells us that the amount of information we have about the occurence of 'Ayatolah' at position i in the corpus increses by 18.38 bits if we are told that 'Ruhollah' occurs at position i+1.

コーパス内の i 番目に 'Ayatolah' が出現していることについて得ている情報量は、i+1 番目に 'Ruhollah' が出現すると教えられれば、18.38 bits 増える」と書かれているわけだが……。

さらに続けて PMI の対称性に触れて、「i+1 番目に 'Ruhollah' が出現していることについて得ている情報量は、 i 番目に 'Ayatolah' が出現すると教えられれば、(同じく) 18.38 bits 増える」と述べられている。


が、そもそも PMI ってそういう値なのか?

self-information で書き直した式 PMI(x, y) = I(x)+I(y)-I(x, y) から PMI の意味を読むと、「(x, y)を同時分布と見なした場合に得ている情報量が、x と y を独立であると考え直した場合にどのように変化するか」という量であることがわかる。FSNLP の解釈は明らかにこれにそぐわない。

それに PMI は負になる場合もある。そのケースでは、「××と教えられれば、情報量は○○減る」 ?


「'Ayatolah' の後ろが 'Ruhollah' と教えられたときの情報量の増分」は字句通りに解釈すれば、 conditional self-information I(Ruhollah|Ayatolah) というものになるだろう。単純計算で 0.322 bits くらい。

  •  I(Ruhollah|Ayatolah) = -¥log¥frac{20}{42} = 0.322

また、'Ruhollah' と bigram 'Ayatolah Ruhollah' の頻度がともに等しく20回であるということは、'Ruhollah' の1つ前は必ず 'Ayatolah' であることがわかる。

確率 1、つまり情報量は 0 bit だ。

まあ 0 かどうかはおいておくとしても、もともとの頻度が倍以上異なる2つの単語が対称である、とは到底思えない。


というわけで、すっかり FSNLP が間違っている的に語ってみたが、相手は10年の実績を持つ定評のある自然言語処理の教科書なので、こんな単純な間違いが残っているとも思いにくい……。

takeda25takeda25 2010/08/29 04:07 引用部最後の "i+i" は "i+1" ですよね。
また、"Ayatolah Ruhollah" は、いわゆる「ホメイニ師」を指します。

これは英語の解釈問題が絡んでいる(しかし、それだけではない)ように思えます。"the amount of information we have about the occurence of 'Ayatolah'" は、私は「'Ayatolah' が出現していることについて得ている情報量」というよりも、「('Ayatolah'が実際に出現するかどうかを知る前の時点で) 'Ayatolah' の出現について既に持っている情報量」というニュアンスで読みました。本文の例でいうと、i+1番目に 'Ruhollah' が出現しているということを知っていれば、i番目に 'Ayatolah' が出現するということの情報量はおっしゃるように 0 bit です(出現することがわかっている)が、そうでなければ 'Ayatolah' が出現するということの情報量は 18.38 bit です。i 番目に 'Ayatolah' が出現した場合、そのことを伝えるのに普通は 18.38 bit 必要ですが、i+1 番目に 'Ruhollah' が出現していることを伝えれば 0 bit しか必要でないことになるので、このことを指して、「i 番目での 'Ayatolah' の出現について既に持っている情報量が 18.38 bit 増える」と表現しているのだと思います。逆の場合は、19.45 bit が 1.07 bit になります。

PMI が負になる場合について考えると、例えば、それぞれ 1/2 の確率で起こる事象 A, B があり、両方同時に起こる確率が 1/8 である場合、A が起こっていると伝えていなければ、B が起こったことを伝えるのに 1 bit しか使わないのですが、A が起こっていると伝えた場合、B が起こったことを伝えるのに 2 bit 使うことになります。この場合、B が「起こらない」ということの情報量は -log3/4 になり、平均情報量は、元の 1 bit から 2 * 1/4 + (-log3/4) * 3/4 = 0.811 bit ぐらいに減り、それだけ情報を得ていることになります。

それにしても、言われてみると本文の表現は気持ち悪いですね…。上の場合について考えると、本文の表現では「B の出現について持っている情報量が 1 bit 減る」ということになってしまいますね。

n_shuyon_shuyo 2010/08/29 23:15 おお、長文コメントありがとうございます。

> 引用部最後の "i+i" は "i+1" ですよね。
直しました!

> また、"Ayatolah Ruhollah" は、いわゆる「ホメイニ師」を指します。
"Ayatolah Khomeini" もしくは "Ayatolah Ruhollah Khomeini" でホメイニ師を指す、というところまでは調べられていたのですが、
"Ruhollah Khomeini" がホメイニ師のお名前なんですね。 http://en.wikipedia.org/wiki/Ruhollah_Khomeini

> これは英語の解釈問題が絡んでいる(しかし、それだけではない)ように思えます。
その可能性も考えて原文を引用しておきました(英語に自信はないので……w)。

> 例えば、それぞれ 1/2 の確率で起こる事象 A, B があり、(中略)それだけ情報を得ていることになります。

そうか、PMI(A=1, B=1) = I(B=1) - I(B=1|A=1) ということですね。
これが -1 となることから、「B の出現について持っている情報量が(A の出現がわかっているときと比べて) 1 bit 減る」と言えるわけですね(表現の気持ち悪さはこの際おいておいて)。
そしてこの式は PMI(A=1, B=1) = I(A=1) - I(A=1|B=1) と書き直せることから、対称の命題「A の出現について持っている情報量が(B の出現がわかっているときと比べて) 1 bit 減る」も言える、と。

なるほど、わかりにくい(注:主観)けど間違ってはいない、ということがわかってきました。
もう少し消化できたらブログの内容も更新したいと思います。
ありがとうございました。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証