Okapi BM25

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

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

順位付け手法

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

単語 $q_{1}, . . ., q_{n}$ を含むクエリテンプレート:Mvarが与えられたとき、文書テンプレート:MvarのBM25スコアは、

score (D, Q) = \sum_{i = 1}^{n} IDF (q_{i}) \cdot \frac{f (q_{i}, D) \cdot (k_{1} + 1)}{f (q_{i}, D) + k_{1} \cdot (1 - b + b \cdot \frac{| D |}{avgdl})},

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

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

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

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

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

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

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

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

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

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

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

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

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

score (D, Q) = \sum_{i = 1}^{n} IDF (q_{i}) \cdot [\frac{f (q_{i}, D) \cdot (k_{1} + 1)}{f (q_{i}, D) + k_{1} \cdot (1 - b + b \cdot \frac{| D |}{avgdl})} + δ]

↑ Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze. An Introduction to Information Retrieval, Cambridge University Press, 2009, p. 233.
↑ http://xapian.org/docs/bm25.html
↑ 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.
↑ テンプレート:Cite journal2
↑ Yuanhua Lv and ChengXiang Zhai. Lower-bounding term frequency normalization. In Proceedings of CIKM'2011, pages 7-16.