確率的情報検索ノート ― Probability Ranking PrincipleからBM25まで ―

GW中にやることリストのひとつである確率的情報検索ノートができたので公開.

確率的情報検索とは,Prbability Ranking Principle (説明はノート参照) をスタート地点にして適合確率をモデル化した情報検索のいち分野.Binary independence modelやBM25などが含まれる (BM25はいろんなヒューリスティクスが入っているのだけれど).

BM25とは,
[tex:\sum_{t \in q} q_t \cdot \frac{f_{t,d} (k_1 + 1)}{k_1*1 + f_{t,d}} \cdot w_t]
という (説明はノート参照),ぱっと見ワケワカラン計算式だけれど当たり前のように情報検索分野でベースラインとして用いられている手法である.

BM25って何? という質問には「文書長正規化したTF-IDF」と答えるようにしており,経験的に性能が良いことが知られている,という情報を加えれば使う分には十分だと思っている.

ただBM25を教科書で見かけると「背景には確率的情報検索てものがあってな」という記述を何度か見かけるし,一応検索をやってますというような人間がBM25が生まれた背景や,その背景とされる確率的情報検索について知りません,というわけにもいかない.

そんな折 (ちょうど昨年の夏頃) にブッチャー本8章の確率的情報検索の入り口からBM25の導出までのわかりやすい解説を読んで感動し,その感動が冷めぬうちにすぐにノートにまとめたかったのだけれど,あっという間に一年近く経過してしまった.

今年のGWは9連休を取ることができたので,こりゃやるしかないとGW中やることリストに加えて丸2日ほど費やして一気に仕上げた.途中から少し補足的な内容なども加えて他人も読めるような資料にしてみた.流れはブッチャー本ほぼまんまなだが,原書に書かれていない情報や補足も加えて,少しは資料ぽくしてみた.

ノート作成に当たって1970年代の論文などをいろいろ眺めたりしたが,あまりの量の多さに全部をきちんと追いかけるは断念.Probability Ranking Principle なんかは引用文献が "personal communication" となっていたりして,おいおいそんなんありかよ,と思いつつも,まだ日の目を見ない時代の情報検索業界に想いを馳せてみたりした.

読む人がいない,読んで嬉しい人がいるのか,と思ったけれど自己満足で終わらせるのもアレなので公開してみた次第.

なんにせよ,立てた目標を達成することができない自分がGW中の目標をなんとか達成できたので自分で自分をちょっと褒めたい.

参考

なお,ブッチャー本というのはこの本のこと.

Information Retrieval: Implementing and Evaluating Search Engines (MIT Press)

Information Retrieval: Implementing and Evaluating Search Engines (MIT Press)

その他のIR教科書については過去の記事をご参考に

*1:1-b) + b(l_d/l_{avg}