Okapi BM25

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

Okapi BM25は、情報検索における順位付けの手法である。検索エンジンクエリとの関連性に応じて、文書を順位付けするのに用いられる。1970年代から1980年代にかけて、スティーブン・ロバートソンやカレン・スパーク・ジョーンズらが確率適合モデル英語版に基づいて開発した。BM25の "BM" は、 "Best Matching" の略である。

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

順位付け手法[編集]

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

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

と定義される。このとき、を文書Dにおける単語の出現頻度、を文書Dの単語数、avgdlを文書集合の平均単語数とする。およびbは任意のパラメータであり、とされることが多い[1]。また、単語のidf値は、

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

ただし、上記の定義式では、半分以上の文書集合に出現する単語のidf値が負になるため、ほぼ同一の2つの文書について、半分以上の文書集合に出現する単語を含む文書と含まない文書とでは、後者のBM25スコアが大きくなってしまうことがある。そのため、実用上は、

  • idf値の最小値を0とし、一般的な用語を完全に無視する
  • idf値の最小値を定数とし、一般的な用語を完全に無視することを避けつつ、影響を減らす
  • idfが必ず正となる定義式に変える

といった処理がなされる。

idfの情報理論的な解釈[編集]

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

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

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

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

BM25の改変版[編集]

  • BM25の係数bを極値に変えたものは、BM11のとき)やBM15のとき)という[2]
  • BM25F[3][4]:重要度や長さが異なるフィールド(見出しや本文、アンカーテキストなど)で構成される文書を考慮した、BM25の改変版である。
  • BM25+[5]:BM25では、単語出現頻度が文書長で適切に正規化されていないため、クエリを含む長い文書よりクエリを含まない短い文書の方がBM25スコアが高くなることがある。BM25+は、BM25の上記について改良するために開発された。BM25+の定義式では任意のパラメータが追加されている(訓練データがないときの初期値は1.0)。BM25+の定義式は、下式である。

出典[編集]

  1. ^ Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze. An Introduction to Information Retrieval, Cambridge University Press, 2009, p. 233.
  2. ^ http://xapian.org/docs/bm25.html
  3. ^ Hugo Zaragoza, Nick Craswell, Michael Taylor, Suchi Saria, and Stephen Robertson. Microsoft Cambridge at TREC-13: Web and HARD tracks. In Proceedings of TREC-2004.
  4. ^ Stephen Robertson & Hugo Zaragoza (2009年). The Probabilistic Relevance Framework: BM25 and Beyond. 3. Found. Trends Inf. Retr.. pp. 333–389. doi:10.1561/1500000019. http://dl.acm.org/citation.cfm?id=1704810. 
  5. ^ Yuanhua Lv and ChengXiang Zhai. Lower-bounding term frequency normalization. In Proceedings of CIKM'2011, pages 7-16.

参考文献[編集]

外部リンク[編集]