« IMEにおける「文節」とは何ぞや | メイン | 情報抽出アルゴリズムEspresso の謎、私の勘違いでした。 »
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 を使うときは、ちょっと注意したほうがよいかもしれません。
投稿者 taku : 2007年10月15日 19:57
トラックバック
このエントリーのトラックバックURL:
http://chasen.org/~taku/blog/mt-tb.cgi/233