ã‚®ãƒ¬ãƒ³ã‚‚ç™»å ´ï¼BM25なPerlモジュール書いたよ

久しぶりに何か書きます。

情報検索のアルゴリズムで「BM25」というものがあります。
何年か前に某研究所に遊びに行ったときに「TF/IDFより精度のいいやつ」みたいな感じでかなりアバウトに教えてもらいました。
その時は「名前だけでも覚えて帰ろう」と思っていたのですが、帰りに安い居酒屋で大酒をのみ、電車のなかで騒いでしまうほど酔っ払ってすっかりその名前を忘れてしまってました。（なにやってんだか・・・）

で、最近Web+DB pressをパラパラ見ていたらBM25の名前を発見！ああ、これだこれだ、思い出したよ！
というわけで、重い腰を上げてモジュール化してみました。

githubに上げてあります。

Lingua::JA::OkapiBM25
http://github.com/miki/Lingua-JA-OkapiBM25

そのうちCPANからも落とせるようになります。

正式名称は「Okapi-BM25」と呼びます。okapiってなんだか岡っ引みたいな響きですが、情報検索の世界ではそれなりに有名なアルゴリズムらしいです。

TF/IDFの欠点を補っている、といえばいいのでしょうか？
自分の浅い理解によると、TF/IDFは文書長が長いものほどTFの値が大きくなりすぎる傾向があって、１ドキュメントのなから特徴語を抽出して相対比較するだけなら大して問題ないかもしれないけど、多くのテキストを解析しつつ絶対評価的にスコアリングするような場合、特徴語のスコアにムラが出てしまう、という欠点あるわけです。

BM25では、そこの欠点を補うべく「平均的な文書の長さ」というものを適当に持ってきて、その文書が大体どれくらいの長さなのかを比率的に計算しておいて、TFの値にかけあわせるような処理をしています。なので、感覚的な言い方になってしまいますが、TFの値が文書長に対してマイルドになっているようなイメージです。

↓詳しく知りたい人はこっちを見てください
http://en.wikipedia.org/wiki/Probabilistic_relevance_model_%28BM25%29

わかり易い例を上げましょう。
以下のギレンの３つの演説を上げます。ガンヲタならだれでも知ってる例のアレです。

これをTF/IDFとBM25で評価してみましょう。

１つ目

ついでにモジュールの使い方も紹介しておきます。
以下の例だとスコアの上位２０件をリスト表示します。

use strict;
use warnings;
use Lingua::JA::OkapiBM25;
use Data::Dumper;

my $text  = _text();

my $okapi =  Lingua::JA::OkapiBM25->new;
my $list  = $okapi->bm25($text)->list(20);

print Dumper $list;

sub _text {
    my $text = <<"END";
我々は一人の英雄を失った。これは敗北を意味するのか？否！始まりなのだ！地球連邦に比べ我がジオンの国力は３０分の>１以下である。にも関わらず今日まで戦い抜いてこられたのは何故か！諸君！我がジオンの戦争目的が正しいからだ！一握>りのエリートが宇宙にまで膨れ上がった地球連邦を支配して５０余年、宇宙に住む我々が自由を要求して、何度連邦に踏み>にじられたかを思い起こすがいい。ジオン公国の掲げる、人類一人一人の自由のための戦いを、神が見捨てる訳は無い。
私の弟、諸君らが愛してくれたガルマ・ザビは死んだ、何故だ！
戦いはやや落着いた。諸君らはこの戦争を対岸の火と見過ごしているのではないのか？しかし、それは重大な過ちである。>地球連邦は聖なる唯一の地球を汚して生き残ろうとしている。我々はその愚かしさを地球連邦のエリート共に教えねばなら>んのだ。
ガルマは、諸君らの甘い考えを目覚めさせるために、死んだ！戦いはこれからである。
我々の軍備はますます復興しつつある。地球連邦軍とてこのままではあるまい。
諸君の父も兄も、連邦の無思慮な抵抗の前に死んでいったのだ。この悲しみも怒りも忘れてはならない！それをガルマは死>を以って我々に示してくれたのだ！我々は今、この怒りを結集し、連邦軍に叩きつけて初め真の勝利を得ることが出来る。>この勝利こそ、戦死者全てへの最大の慰めとなる。
国民よ立て！悲しみを怒りに変えて、立てよ国民！ジオンは諸君等の力を欲しているのだ。
ジーク・ジオン！！
END
    return $text;
}

同じようにLingua::JA::TFIDFで評価もしてみます。コードはほとんど同じなので省略。

で、結果はこうなりました。

これだけ見ると言葉の差はあまりないですね。でもスコアのばらつき具合はだいぶ違います。

２つ目

続いてこれ。

sub _text {
    my $text = <<"END";
今ここに諸君等有望なる新入生を迎えて、大いなる期待を禁じえない。
時代は現在、新たな局面へと向かいつつある！いかなる局面へか！？人類史の偉大な発展への局面である！！
宇宙に進出することによって、我々は無限の可能性を手にした。誰の可能性か！？人類全体のか！？否！！我等スペースノ>イドにのみ許された可能性であるっ！！スペースノイドの新しい能力こそが停滞した人類史を打破するのである！
移民一世以来の困難な時代を経て、かつて棄民とさえ呼ばれていたスペースコロニーの住民達は選ばれた民となった！期せ>ずして、人類史の最前列に立ったのだ！！
諸君は更にその前衛である！！エリートを自負することに躊躇するな諸君！諸君はエリートだ！選ばれた民の中から更に厳>しく選抜されてここにいる諸君等こそ、コロニー社会の守護者であると共に新人類のリーダーである！
奮起せよ！
未来の将星をめざして邁進せよ！
我と我が戦線に加われ！！
END
    return $text;
}

結果はこうなります。ふむ。これもまぁ同じようではありますね。

3つ目

3つ目の演説はこれ。これはやや短めです。こういったケースで差が出てきます。

sub _text {
    my $text = <<"END";
我が忠勇なるジオン軍兵士達よ、今や地球連邦軍艦隊の半数が我がソーラ・レイによって宇宙に消えた。この輝きこそ我等>ジオンの正義の証しである。決定的打撃を受けた地球連邦軍に如何ほどの戦力が残っていようとも、それは既に形骸である>。
敢えて言おう、カスであると！
それら軟弱の集団が、このア・バオア・クーを抜くことは出来ないと私は断言する。
人類は我等選ばれた優良種たるジオン国々民に管理運営されて、初めて永久に生き延びることが出来る。これ以上戦い続け>ては人類そのものの危機である。地球連邦の無能なる者どもに思い知らせてやらねばならん。今こそ人類は明日の未来に向>かって立たねばなぬ時であると！
ジーク・ジオン！
END
    return $text;
}

差が出てくるっていっても、なんだか大差ないようにみえますね。。。

結果

やれやれ。なんだかキッショイ感じになってしまいました。
とはいえ、なんとか無事にギレンの３つの演説をBM25とTFIDFで評価することができました。

で、なにが言いたかったのかというと、１つ目と２つ目の演説にくらべて３つ目の演説は短いけども、BM25だと比較的公平にスコアが出てるよ、ということです。

なにが公平かというと、１つ目、２つ目の演説において、TF/IDFだと1位のキーワードのスコアは40前後なのに対して、3つ目だけ文書長が短いので、第1位のキーワードですら16.91ということで、だいぶムラがあります。

それに対してBM25だと、文書長に拘わらず、どれもだいたい同じくらいのスコアの範囲に収まっていますね。

これがどう効いてくるかというと、3つの演説データを別々に評価したスコアを積算してくたときに影響がでてきます。

上記は3つの演説のスコアをバラバラに評価し、キーワードごとに足しこんでいったものの上位20個です。

注目すべきは色が濃い部分。これはどちらも、そちら側にしか登場しなかった言葉です。

TFIDFだと「怒り」とか「戦い」「悲しみ」のようなやや抽象的な語彙がランクインしているのに大して、BM25だと「忠勇」「棄民」「形骸」のようなとてもギレン様風味の語彙が見受けられます。
ソーラー・レイとかも出ちゃってるよ！

つまり、文書長の短かった3つめの演説の内容も、そこそこ公平に取り込まれており、結果としてより特徴的な語彙が上位に食い込む形となりました。

注意点

えっと、注意点というかなんというか、BM25のことあまり理解しないで書いてます。
もしかしたら全然勘違い野郎かもしれないので、あんまり本気にしないでね！

あとLingua::JA::TFIDFもLingua::JA::OkapiBM25も、IDFの計算は推測値です。
くわしくはこっちにかいてありますが、正確なデータではないので、そこら辺も含めて、「なんとなくこんな感じなのね」ぐらいにみていただけるとありがたいです。

あ、あとこのサンプルで掲載したデータは、実際にはMeCabにはてなキーワードやwikipediaの見出し語を突っ込んだりして、独自に拡張してるので、モジュール落としてきて同じことやっても同じ結果にはなりません。あしからず。

こんな中途半端な内容でブログを書いたりモジュールを上げたりして、なんの意味があるのだろうか。

それはすでに形骸である！
敢えて言おう、「カス」であると！

スミマセン、これが書きたかっただけです。オヤスミナサイ。