Okapi BM25

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が必ず正となる定義式に変える

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

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値の定義式と似た式が現れる。

BM25の改変版

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

${\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.

参考文献

• Stephen E. Robertson; Steve Walker; Susan Jones; Micheline Hancock-Beaulieu & Mike Gatford (November 1994). Okapi at TREC-3. Proceedings of the Third Text REtrieval Conference (TREC 1994). Gaithersburg, USA.
• Stephen E. Robertson; Steve Walker & Micheline Hancock-Beaulieu (November 1998). Okapi at TREC-7. Proceedings of the Seventh Text REtrieval Conference. Gaithersburg, USA.
• Spärck Jones, K.; Walker, S.; Robertson, S. E. (2000). “A probabilistic model of information retrieval: Development and comparative experiments: Part 1”. Information Processing & Management 36 (6): 779–808. doi:10.1016/S0306-4573(00)00015-7. 
• Spärck Jones, K.; Walker, S.; Robertson, S. E. (2000). “A probabilistic model of information retrieval: Development and comparative experiments: Part 2”. Information Processing & Management 36 (6): 809–840. doi:10.1016/S0306-4573(00)00016-9. 
• Stephen Robertson & Hugo Zaragoza (2009). "The Probabilistic Relevance Framework: BM25 and Beyond". 3 (4). Found. Trends Inf. Retr.: 333–389. CiteSeerX 10.1.1.156.5282. doi:10.1561/1500000019。

関連項目

• 自然言語処理
• tf-idf

外部リンク

• Robertson, Stephen; Zaragoza, Hugo (2009). The Probabilistic Relevance Framework: BM25 and Beyond. NOW Publishers, Inc.. ISBN 978-1-60198-308-4. http://staff.city.ac.uk/~sb317/papers/foundations_bm25_review.pdf