« 2007年07月 | メイン | 2008年01月 »
2007年10月18日
情報抽出アルゴリズム 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は無限大) を 重要視する場合と解釈できます。
こんなかんじで、ブートストラッピングがわりと解析的に説明できるのではないでしょうか。
2007年10月16日
情報抽出アルゴリズムEspresso の謎、私の勘違いでした。
昨日のエントリーは私の完全な勘違いでした。大学数学やりなおします。orz行列表現にはまちがいはないのですが、あの形はマルコフ連鎖そのものなので、
x_instance = A * x_instance の解は、x_instance = A^{n} * x_instance0 なので、x_instance0 の初期値 に依存します。A^{n} が収束し B になるとすれば、x_instance = B * x_instance0 となります。
A^{n} が収束することが条件ですが、相互情報量の最大値で正規化されているので、たぶん収束するでしょう。
しかし、Espresso のおもしろいところは, B が求まってしまえば、どんな初期値でもただ1回の行列のかけ算で 最終的な答えがでてしまうところです。 B は、全パターンと全インスタンスの類似度から生成される行列で、信頼度とは無関係です。相互情報量～行列 B の関係がクリアになれば、かなりおもしろいとおもいます。直感的にはパターンという世界でのインスタンス同士の類似度行列をかけるかけるのだろうと考察できるのですが、私の頭ではここまでが限界です。リンク解析の専門家に聞きたいす。
2007年10月15日
情報抽出アルゴリズム Espresso の謎
Espresso という情報抽出アルゴリズムを使った研究が散見されるようになったので、 ちょっと深追いしてみました。基本的に Bootstrapping をベースにしているようです。 Bootstrapping のアイデアはわかりやすいのですが、実際動かすには設定すべき パラメータがいくつもあります(各Iteration でどういう基準で何個パターンを 見つけたらいいのかなど)。 Espresso は、この設定すべきパラーメータが アルゴリズムとして明示的に記述されており、わりと再現・実装がしやすい アルゴリズムだと感じました。オリジナルの論文の式をみていきましょう。 http://www.patrickpantel.com/Download/Papers/2006/acl06-01.pdf
阿部さんの論文の9ページをみた方がいいかもしれません。 http://cl.naist.jp/~shuya-a/research/061123-abe-signl176-14-slides.pdf
pmi(i, p) / max_pmi は、|I| * |P| の行列表現できるので、これを M としましょう。
すると、再帰的なパターン、インスタンスの抽出は
- r_pattern = 1/|I| * M * r_instance
- r_instance = 1/|P| * M^{T} * r_pattern
のように行列表記できます。 r_pattern は、pattern の信頼度のベクトル、r_instance は instance の信頼度ベクトル、|I| はインスタンスの数、|P| はパターンの数です。
以上の式から、
- r_intance = 1/|P||I| * M^{T} * M * r_instance
- r_pattern = 1/|P||I| * M * M^{T} * r_pattern
「初期値によらず、パターンの信頼度/インスタンスの信頼度は、 M^{T} * M もしくは M * M^{T} の最大固有値に対応する固有ベクトルになる」
が Espresso の導く結果だと考察できます。もしこれが真なら、情報抽出の意味がありません。
NAIST方面に聞いてみると、こういう考察はないとのことです。実際には、 各Iterationで、信頼度の高いものtop 50を使ったりして、動的に |P|や|I|を変更 するそうです。そうなると、厳密な解析は困難で、ひょっとしたらローカルミニマムが あるのかもしれません。
ということで、Espresso を使うときは、ちょっと注意したほうがよいかもしれません。