Dec 08 2013

つい30分前まで6時間眠っていたというのに
体を横にして布団を体の上から被せるだけで簡単に眠れる
横にして布団を体の上から被せなければ寝ないのかもしれないが
それでも眠りたいのだから仕方がなかった
ベッドに向かう途中
僕は伯父さんに寝てばかりなのが恥ずかしくて冗談を言ってみた
睡眠を売る仕事があるとしたら,僕はかなり真面目な労働者ですね
伯父さんは一言も発さずに笑った

私が完全に眠りに落ちた後
私はこんな夢を見ていた
夢を見ていたというのは完全に眠りに落ちたという他ならぬ証拠だ
伯父さんは私の見る夢をパイプに繋いで取り出そうとしてる
パイプの先は見えないけれど
SFかなんかにありがちで如何にもという機械でないのはきっとだ
夢は高く売れるから大事に取り出したいけれど
どうしてもパイプの繋ぎ目から夢が漏れ
夢を覗き見てしまう
こんな日にまで,こんな夢を見なくたっていいだろうに
でも実はこのことは私が目が覚めてから考えたことなので
果たして夢と見れるのか分からない

SNLP Chapter7 - 確認したことと疑問にもったことのメモ

Brown et al. 1991b Flip-Flop algorithm An information-theoretic approach

意味を複数持つような"曖昧語"の意味(sense)をどう解釈するかのアルゴリズム

Brownさんはどこの人か知らないけど この人はフランス語の文を英語文に自動翻訳することを用例として このアルゴリズムを考案してる

w というフランス語の単語は

\[ts = \{t_1, t_2, t_3 ... t_N \}\]

というN個の意味を持つ.但し t はtranslateの t なので意味ではなくて 翻訳,と言ったほうが良いかもしれない

どの意味であるかの指標の値をindicatorと呼ぶ.indicatorというのは 具体的には w が動詞ならその目的語がこれこれである(ならば1,でなければ0) だとか,w のすぐ左の語が数値であるか,とか,w を含む文の時制が現在である だとか

複数考えられるindicatorの値を

\[xs = \{x_1, x_2 ... x_M \}\]

とする

indicatorというのは w に対して自分で用意しないといけないみたい 自分で用意する時点でもう,個別のアルゴリズムが書けると思うんだけど

Flip-Flopアルゴリズムは ts を2つに分割して,つまり w の解釈を二通りに 分割して,それぞれに対応するように xs を2つに分割するためのもの

と分割できたら, w に対して indicator x\(Q_1\) に属してたら \(P_1\) の意味 と判別する

で,その分割をどうするか 訓練データの中で相互情報量

\[I(P; Q) = I(\{P_1,P_2\}, \{Q_1,Q_2\})\]

を最大となるような分割を探索する

ある訓練データの中で曖昧語 w について 次の4つが1つずつ,見つけられた

indicator sense
x a
x b
y b
z d

確率は単純に割合だとすることにして

ということになる

相互情報量は次のように求められる

function I (p1, p2, q1, q2) {
  function sub(p, q) {
    var h = Pr2(p,q);
    if (h < 0.0001) return h;
    return h * Math.log( h / Pr0(p) / Pr1(q) );
  }
  return sub(p1,q1) + sub(p1,q2) + sub(p2,q1) + sub(p2,q2);
}

function Pr0(p) {
  "use strict";
  var ps = p.split(",");
  return ps.map(function(p) {
    if (p == "b") return 0.5;
    else return 0.25;
  }).reduce(function(x,y){return x+y})
}

function Pr1(q) {
  "use strict";
  var qs = q.split(",");
  return qs.map(function(q) {
    if (q === "x") return 0.5;
    else return 0.25;
  }).reduce(function(x,y){return x+y})
}

function Pr2(p,q) {
  var ps = p.split(",");
  var qs = q.split(",");
  var sum = 0;

  ps.forEach(function(p) {
    qs.forEach(function(q) {
      var r = 0;
      if (p === "x" && q === "a") r = 0.25;
      if (p === "x" && q === "a") r = 0.25;
      if (p === "y" && q === "b") r = 0.25;
      if (p === "z" && q === "d") r = 0.25;
      sum += r;
    })
  });

  return sum;
}

実際の値は

console.log( I("x,y","z", "a,b", "d") );
console.log( I("x","y,z", "a,b", "d") );
console.log( I("","x,y,z", "a,b", "d") );
console.log( I("x,y","z", "b", "a,d") );

// 0.6931471805599453
// 0.34657359027997264
// 0.21576155433883565
// 0.34657359027997264

というわけで

\(P_1 = \{x,y\}, P_2 = \{z\}\) \(Q_1 = \{a,b\}, Q_2 = \{d\}\)

が情報量を最大とさせる

で疑問点として 式の対称性から \(P_1\)\(P_2\) を入れ替えても \(I(P;Q)\) の値は変わらない

\(Q_1 \mapsto P_1, Q_2 \mapsto P_2\)

という曖昧解消のアルゴリズムに一番大切なトコロなのに \(P_1\)\(P_2\) が入れ替わったら真逆になっちゃうじゃんか

どっか読み落としたのかな