ja.wikipedia.org

Okapi BM25 - Wikipedia

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

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

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

単語{\displaystyle q_{1},...,q_{n}}を含むクエリQが与えられたとき、文書DのBM25スコアは、

{\displaystyle {\text{score}}(D,Q)=\sum _{i=1}^{n}{\text{IDF}}(q_{i})\cdot {\frac {f(q_{i},D)\cdot (k_{1}+1)}{f(q_{i},D)+k_{1}\cdot \left(1-b+b\cdot {\frac {|D|}{\text{avgdl}}}\right)}},}

と定義される。このとき、{\displaystyle f(q_{i},D)}を文書Dにおける単語の出現頻度、{\displaystyle |D|}を文書Dの単語数、avgdlを文書集合の平均単語数とする。{\displaystyle k_{1}}およびbは任意のパラメータであり、{\displaystyle k_{1}\in [1.2,2.0]}、{\displaystyle b=0.75}とされることが多い[1]。また、単語{\displaystyle q_{i}}のidf値は、

{\displaystyle {\text{IDF}}(q_{i})=\log {\frac {N-n(q_{i})+0.5}{n(q_{i})+0.5}},}

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

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

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

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

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

{\displaystyle -\log {\frac {n(q)}{N}}=\log {\frac {N}{n(q)}}.}

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

{\displaystyle {\frac {n(q_{1})}{N}}\cdot {\frac {n(q_{2})}{N}},}

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

{\displaystyle \sum _{i=1}^{2}\log {\frac {N}{n(q_{i})}}.}

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

{\displaystyle {\text{score}}(D,Q)=\sum _{i=1}^{n}{\text{IDF}}(q_{i})\cdot \left[{\frac {f(q_{i},D)\cdot (k_{1}+1)}{f(q_{i},D)+k_{1}\cdot \left(1-b+b\cdot {\frac {|D|}{\text{avgdl}}}\right)}}+\delta \right]}
  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". Foundations and Trends in Information Retrieval. 3 (4): 333–389. CiteSeerX 10.1.1.156.5282. doi:10.1561/1500000019。
  5. ^ Yuanhua Lv and ChengXiang Zhai. Lower-bounding term frequency normalization. In Proceedings of CIKM'2011, pages 7-16.