Okapi BM25

Okapi BM25は、情報検索における順位付けの手法である。検索エンジンがクエリとの関連性に応じて、文書を順位付けするのに用いられる。1970年代から1980年代にかけて、やらがに基づいて開発した。BM25の"BM"は、"Best Matching"の略である。

ロンドン大学シティ校が1980年代から1990年代にかけて開発したオカピ情報検索システム (Okapi information retrieval system) に最初に実装されたため、 "Okapi BM25" と呼ばれるが、単に、この手法自体の名称であるBM25とも呼ばれる。

 順位付け手法 
BM25は、bag-of-wordsを拡張した手法であり、文書内のクエリの単語同士の相互関係ではなく、文書におけるクエリの単語の出現頻度に基づいて、文書集合を順位付けする。

単語を含むクエリが与えられたとき、文書のBM25スコアは、

と定義される。このとき、を文書における単語の出現頻度、を文書の単語数、を文書集合の平均単語数とする。およびは任意のパラメータであり、、とされることが多いChristopher D. Manning, Prabhakar Raghavan, Hinrich Schütze. An Introduction to Information Retrieval, Cambridge University Press, 2009, p. 233.。また、単語のidf値は、

と定義される。このとき、を全文書数、をを含む文書数とする。また、には複数の定義があり、上記の定義式はその1つである。BM25では二項独立モデルに基づいて導出された。

ただし、上記の定義式では、半分以上の文書集合に出現する単語のidf値が負になるため、ほぼ同一の2つの文書について、半分以上の文書集合に出現する単語を含む文書と含まない文書とでは、後者のBM25スコアが大きくなってしまうことがある。そのため、実用上は、
 idf値の最小値を0とし、一般的な用語を完全に無視する
 idf値の最小値を定数とし、一般的な用語を完全に無視することを避けつつ、影響を減らす
 idfが必ず正となる定義式に変える
といった処理がなされる。

 idfの情報理論的な解釈 
クエリの単語が個の文書に出現したとき、無作為に選択した文書に単語が含まれる確率はである（は全文書数）。したがって、「がを含む」という事象の情報量は、

である。このとき、2つのクエリの単語, が与えられたとする。2つの単語が完全に独立して文書内に存在するとき、無作為に選択した文書に2つの単語が出現する確率は、

となる。したがって、このときの情報量は、

となり、BM25のidf値の定義式と似た式が現れる。

 BM25の改変版 
 BM25の係数を極値に変えたものは、BM11（のとき）やBM15（のとき）というhttp://xapian.org/docs/bm25.html。
 BM25FHugo Zaragoza, Nick Craswell, Michael Taylor, Suchi Saria, and Stephen Robertson. Microsoft Cambridge at TREC-13: Web and HARD tracks. In Proceedings of TREC-2004.：重要度や長さが異なるフィールド（見出しや本文、アンカーテキストなど）で構成される文書を考慮した、BM25の改変版である。
 BM25+Yuanhua Lv and ChengXiang Zhai. Lower-bounding term frequency normalization. In Proceedings of CIKM'2011, pages 7-16.：BM25では、単語出現頻度が文書長で適切に正規化されていないため、クエリを含む長い文書よりクエリを含まない短い文書の方がBM25スコアが高くなることがある。BM25+は、BM25の上記について改良するために開発された。BM25+の定義式では任意のパラメータが追加されている（訓練データがないときの初期値は1.0）。BM25+の定義式は、下式である。

 出典 

 参考文献 






 関連項目 
 自然言語処理
 tf-idf

 外部リンク 


Category:アルゴリズム
Category:自然言語処理