Okapi BM25

Okapi BM25は、情報検索における順位付けの手法である。検索エンジンがクエリとの関連性に応じて、文書を順位付けするのに用いられる。1970年代から1980年代にかけて、やらがに基づいて開発した。BM25の"BM"は、"Best Matching"の略である。
ロンドン大学シティ校が1980年代から1990年代にかけて開発したオカピ情報検索システム (Okapi information retrieval system) に最初に実装されたため、 "Okapi BM25" と呼ばれるが、単に、この手法自体の名称であるBM25とも呼ばれる。
順位付け手法.
BM25は、bag-of-wordsを拡張した手法であり、文書内のクエリの単語同士の相互関係ではなく、文書におけるクエリの単語の出現頻度に基づいて、文書集合を順位付けする。
単語formula_1を含むクエリが与えられたとき、文書のBM25スコアは、
と定義される。このとき、formula_3を文書における単語の出現頻度、formula_4を文書の単語数、を文書集合の平均単語数とする。formula_5およびは任意のパラメータであり、formula_6、formula_7とされることが多い。また、単語formula_8のidf値は、
と定義される。このとき、を全文書数、formula_10をformula_8を含む文書数とする。また、formula_12には複数の定義があり、上記の定義式はその1つである。BM25では二項独立モデルに基づいて導出された。
ただし、上記の定義式では、半分以上の文書集合に出現する単語のidf値が負になるため、ほぼ同一の2つの文書について、半分以上の文書集合に出現する単語を含む文書と含まない文書とでは、後者のBM25スコアが大きくなってしまうことがある。そのため、実用上は、
といった処理がなされる。
idfの情報理論的な解釈.
クエリの単語formula_14がformula_15個の文書に出現したとき、無作為に選択した文書formula_16に単語formula_14が含まれる確率はformula_18である（formula_19は全文書数）。したがって、「formula_16がformula_14を含む」という事象の情報量は、
である。このとき、2つのクエリの単語formula_23, formula_24が与えられたとする。2つの単語が完全に独立して文書内に存在するとき、無作為に選択した文書formula_16に2つの単語が出現する確率は、
となる。したがって、このときの情報量は、
となり、BM25のidf値の定義式と似た式が現れる。