« August 2007 | Main | October 2007 »

2007.09.30

AND検索の最尤推定

検索技術においてAND検索、つまり二つの単語を指定して、それが両方出現している文書数の推定を高速に行うのは難しい問題です。

問題を正しく書くと単語w_xが出ている文書番号(x1,x2,x3,..,xn)とw_yが出ている文書番号(y1,y2,y3,...,ym)が与えられたら | {(i,j)|x_i = y_j} | の数を求める問題です。
これは前もって全通り求めて保存しておくにも単語種類数の二乗のオーダー分必要なのでできません。

これは機械学習でも特徴関数が0/1の値しかとらないとき、二つの要素の特徴ベクトルの内積を求める問題と同じで、またデータベースでもJOINの順番を決めるときにでてくる問題です。

普通は全体の文書からサンプルをとって、その中で数えてみて、それを元のサイズにスケールさせることをします。例えば全体文書1億件の中から文書1000件だけとってきて、その中でw_xとw_yが同時に出ている文書数が5ならば、実際の文書では5 * (1億/1000) = 50万件とか推定するわけです。ただしこの方法は相当大雑把で大抵真の値からは大きくずれます。

最近 [1]で提案された手法では、サンプル値に加えw_xとw_yのそれぞれ単体での全文書での出現回数(論文中ではマージンと読んでいる)を使って推定値を大幅改善させています。w_xとw_yの出現回数は単語数に比例するオーダーで保存しておけます。

その手法では、サンプルされた数が出てくる確率を最大にする同時出現回数を探す、いわゆる最尤推定を使って求めます。

これが理論的に単純なサンプリングより分散が小さいことを示していることもすごいのですが、実用的に面白いのが近似をいくつか使うと推定値が以下のように閉じた式ででてくるところです。
eq
ここでの各変数の意味は
f1 : xの出現回数
f2 : yの出現回数
a_s : サンプリングされた中でxとyが同時に出現した回数
b_s : サンプリングされた中でxだけが出現した回数
c_s : サンプリングされた中でyだけが出現した回数
d_s : サンプリングされた中でxもyも出現しなかった回数

この手法を使うと大体半分のサンプル数で同等の精度が得られるみたいです。
実際にはa_s, b_s, c_s, d_sそれぞれを実際の値に+1しておくスムージングやるともうちょっとよくなります。

関連する話は著者のページにいろいろあります。論文だしすぎ。

[1] "Sketch Algorithm for Estimating Two-Way and Multi-Way associations" , Ping Li, Kenneth W. Church Computational Linguistics Vol 33, Issue 3, 2007, pp 305-354

| | Comments (3) | TrackBack (0)

2007.09.22

書いていないと

いうことはいろいろあるということで、元気でやっております。
久しぶりに家帰ってばたんQするくらい詰まってます。

私の近々の発表としてNLP若手の会で2つと、IBISで1つあります。

| | Comments (1) | TrackBack (0)

2007.09.05

伊東、福岡

ここ最近は毎週どっかに行ってます。
先週は伊東でプログラミングをごりごり書きまして、今は九大に1週間ほど滞在して解析・実装してます。冬頃にいろいろでてくるでしょう

伊東では魚尽くし・福岡では水炊き、ラーメン、ラーメンです。おいしかったので思わずラーメンを二日繰り返しました。

九大の新しくできた伊都キャンパスは街から遠いですね。私は街中で天神に滞在しているのですが、そこからバスか電車で1時間ぐらいかかります。しかも結構混んでるのですね。むむぅ。(参考学生アンケート)。うちの学校もどんどん郊外に出て行ってますが、実験系を除いては学校もこれからまた、なんだかんだ都心回帰した方がいいんじゃないかな。いろいろあってそうは簡単にいかんだろうけど。

| | Comments (0) | TrackBack (0)

« August 2007 | Main | October 2007 »