Okapi BM25 Okapi BM25の概要

ウィキペディア

Okapi BM25

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/10/13 02:17 UTC 版)

ロンドン大学シティ校が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値の定義式と似た式が現れる。