« IMEにおける「文節」とは何ぞや | メイン | 情報抽出アルゴリズムEspresso の謎、私の勘違いでした。 »

2007年10月15日

情報抽出アルゴリズム Espresso の謎

Espresso という情報抽出アルゴリズムを使った研究が散見されるようになったので、 ちょっと深追いしてみました。基本的に Bootstrapping をベースにしているようです。 Bootstrapping のアイデアはわかりやすいのですが、実際動かすには設定すべき パラメータがいくつもあります(各Iteration でどういう基準で何個パターンを 見つけたらいいのかなど)。 Espresso は、この設定すべきパラーメータが アルゴリズムとして明示的に記述されており、わりと再現・実装がしやすい アルゴリズムだと感じました。

しかし、式を追ってみると、最終的な結果は Seed に依存しないのではないか という疑惑が出てきました。

オリジナルの論文の式をみていきましょう。 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

となり、1/|P||I| * M^{T} * M = A とおけば、Iterationを繰り返していった定常状態では、 r_instance = A * r_intance なります。これは、まさしく A の固有ベクトルを 求めているにすぎません。反復計算のプロセスは、冪乗法による固有値計算に似ている(正確にはちょっと違う) ため、結果として、
「初期値によらず、パターンの信頼度/インスタンスの信頼度は、 M^{T} * M もしくは M * M^{T} の最大固有値に対応する固有ベクトルになる」
が Espresso の導く結果だと考察できます。もしこれが真なら、情報抽出の意味がありません。

NAIST方面に聞いてみると、こういう考察はないとのことです。実際には、 各Iterationで、信頼度の高いものtop 50を使ったりして、動的に |P|や|I|を変更 するそうです。そうなると、厳密な解析は困難で、ひょっとしたらローカルミニマムが あるのかもしれません。

ということで、Espresso を使うときは、ちょっと注意したほうがよいかもしれません。

投稿者 taku : 2007年10月15日 19:57

トラックバック

このエントリーのトラックバックURL:
http://chasen.org/~taku/blog/mt-tb.cgi/233