« 情報抽出アルゴリズムEspresso の謎、私の勘違いでした。 | メイン | 情報抽出アルゴリズム Espresso 最終章 »
2007年10月17日
情報抽出アルゴリズム Espresso 最終章
Espresso を飲みながらさらに Espresso を考えていました。r_instance = A^n * r_instance_0
となるのは間違いないと思います。A は P * P^{T}、さらに P = 1/|I||P| * pmi(i, p)/ maxpmi です。 A は、インスタンスどうしの類似度を表現した正方対称行列です。A_{i,j} はインスタンス i, j の類似度です。 類似度は、パターン個数次元からなるベクトルの内積で、各次元は pmi となります。 この形だと、r_instanc は r_instance_0 できまるので、初期値に依存してるように思えますが、A^n がいったい どういう意味を持つのかずっと考えていました。
A_{i,j} が 0, 1 の場合、A は無向グラフの接続行列となります。i,j がつながっている場合は A_{i,j} = 1となります。この場合、A^n_{i,j} は、i から j へつながる 長さ n の経路の数となります。A_{i,j}が実数値の場合は、 これの類推で、i から j へつながる経路上の類似度の積をすべての経路で総和したものとなります。
A^n で nを無限大に飛ばした場合どうなるでしょうか。あるインスタンス i を固定して、A^n_{i,0}, A^n_{i,1}, A^n_{i,2}, を見ていくことにします。n が無限大の場合は、i と j を結ぶあらゆる経路を ほぼランダムウォークで動くことになるので、結局、どのインスタンスと計測しても類似度が高いような ジェネラルインスタンス j との値 A^n_{i,j} が大きくなります。なぜならば、ジェネラルインスタンスは どのインスタンスともそれなりに類似度があるので、そこへだとりつく経路の数が確率的に多いからです。 ここで重要なのは、最初に固定した i とは無関係だということです。A^n_{i,j} (nは無限大) のどの行をとっても、その絶対値は違うにせよ、大小関係はどれくらいジェネリックかという基準で 並んでしまいます。
初期値として、１つのシードインスタンスを選んだ場合、A^n の１行をとってくるだけなので、結果として ジェネリック順に r_instance が決まります。2つ以上のシードインスタンスを選んだとしても、A^n の各行の 大小関係はどの行をとっても保たれているために、ジェネリック順に r_intsance が決まります。 結論として、r_instance は 初期値に依存しません。
実データでは、最初の類似度行列 A はスパースなので、グラフであらわすと、全部のインスタンスがつながっているわけではなく、複数の島ができていると考えられます。初期値としてある島のなかにある１インスタンスを選ぶと、その島の中のジェネリック順に並んだ r_instance が得られます。別の島を選ぶと、別の r_instance が得られます。しかし、島の中で閉じている初期値であれば、初期値をどう設定しようが結果は同じになります。
さて、この状況を打開するにはどうしたらいいのでしょうか。すぐに思いつく方法は、ノイマンカーネル です。
r_instance = (A + b^2 * A^2 + b^3 * A^3 + .... + b^n * A^n) * r_instance_0
とします。 b 任意の減衰パラメータです。 A^n で、n が小さいと、オリジナルの類似度行列をそのまま使うので、 初期値にセンシティブになります。n がしだいに大きくなるにつれて、初期値に依存せず、グローバルなジェネリック度みたいなものが重要視されます。この二つの軸を b というパラメータをつかって足しこんでいくことで、いいとこどりをしようというのがアイデアです。
生駒日記によると、ブートストラッピングには以下のような議論があるようです。
インスタンスを獲得するときに毎回前回に獲得したインスタンスを残しておいて累積的にインスタンスを獲得していくのがいいのか、それとも毎回インスタンスのプールはフラッシュして最後の反復のときに得られたパターンで取れたインスタンスの上位k個を出力するのがいいのか
これはまさしくノイマンカーネルで説明できます。累積的にというのは、b が小さいとき、すなわち、 初期値にセンシティブになる状況で、フラッシュするというのは、b が大きく、A^n (nは無限大) を 重要視する場合と解釈できます。
こんなかんじで、ブートストラッピングがわりと解析的に説明できるのではないでしょうか。
投稿者 taku : 2007年10月17日 17:58
トラックバック
このエントリーのトラックバックURL:
http://chasen.org/~taku/blog/mt-tb.cgi/235