\def\vector#1{\boldsymbol{#1}}

\newcommand{\argmax}{\mathop{\rm arg~max}\limits}

Okapi BM25

2024年7月24日 #OkapiBM25 #BM25

概要

Okapi BM25 は情報検索における文書のランク付けアルゴリズムの一つである。クエリーに対する文書の関連性を評価するために使用される。BM25 は TF-IDF の発展系として、特に文書の長さや単語の頻度に基づいて関連性スコアを調整するために設計されている。

BM25 は TF-IDF と同様に情報検索のランク付けを行うが、BM25 は文章の長さに応じて単語の出現頻度に対するスコアが調整される。

Okapi はロンドン大学シティ校で開発された検索システムである。BM (best match)

$\begin{equation} {\rm BM25}(q,d) = \sum_{t \in q} {\rm IDF}(t) \cdot \frac{f(t,d) \cdot (k_1 + 1)}{f(t,d) + k_1 \left(1 - b + b \frac{|d|}{\rm avgdl} \right)} \label{bm25} \end{equation}$ 式 ( $\ref{bm25}$ ) の最初の項 ${\rm IDF}(t)$ は IDF (inverse document frequency) を表し式 ( $\ref{idf}$ ) のように計算される。 $\begin{equation} {\rm IDF}(t) = \log \frac{N - n(t) + 0.5}{n(t) + 0.5} \label{idf} \end{equation}$ ここで $N$ をすべての文書数、 $n(t)$ をターム $t$ を含む文書数とする。

式 ( $\ref{bm25}$ ) の 2 番目の項は文書の長さで正規化された TF (term frequency) を表す。 $f(t,d)$ は文書 $d$ におけるターム $t$ の出現頻度、 $|d|$ は文書 $d$ のターム数、 ${\rm avgdl}$ はすべての文書の平均の長さである。一般にクエリー中のすべてのタームに対して $1 \le k_1 \lt 2$ と $0 \le b \le 1$ の値が適用される。パラメータ $b$ は文所長による正規化のレベルを調整する。研究論文では規定値として $k_1 = 1.2$ が使われることが多い [1]。

参考文献

Stefan Buttcher, Charles L. A. Clarke, Gordon V. Cormack. 情報検索 :検索エンジンの実装と評価. 森北出版 (2020)