技術

BM25とは

Okapi BM25

単語の出現頻度と文書長を考慮してスコアリングする、キーワードベースの検索アルゴリズム

ひとことで言うと

単語の出現回数などをもとに文書の関連度を計算する、昔からあるキーワード検索の計算方法。

概要

BM25(Okapi BM25)とは、クエリに含まれる単語が文書内でどれだけ出現するか(単語頻度)と、その単語がコーパス全体でどれだけ珍しいか(逆文書頻度)、さらに文書の長さを考慮してクエリと文書の関連度をスコアリングする、キーワードベースの情報検索アルゴリズム。埋め込みベクトルを使わず単語の統計情報のみで計算できるため軽量かつ高速で、長年にわたり検索エンジンの標準的なランキング手法として使われてきた。近年はセマンティック検索と組み合わせるハイブリッド検索の一方の要素としても広く利用されている。パラメータ k1 と b によって単語頻度の飽和具合や文書長の影響度を調整でき、多くの検索エンジン・ベクトルデータベースで標準実装として提供されている。

背景

情報検索では、クエリと文書の関連度をどう数値化するかが中心的な課題であり、単純な単語頻度だけでは長い文書が過剰に高いスコアを持ちやすいといった問題があった。 BM25は、確率的検索モデルの理論に基づき、単語頻度・逆文書頻度・文書長の3つの要素を組み合わせることで、実用的な検索精度を達成するために考案された。

歴史

1994年: RobertsonらがOkapiシステムの一部としてBM25の原型となるスコアリング関数を発表。 1990年代後半: BM25として理論が整理され、TREC(Text REtrieval Conference)等の情報検索評価タスクで有効性が示される。 2000年代以降: Elasticsearch・Apache Solr等主要な検索エンジンのデフォルトスコアリングアルゴリズムとして採用され普及。

アーキテクチャ

各文書に対するスコアは、クエリに含まれる各単語について「単語の文書内出現頻度」「単語のコーパス全体での希少性(逆文書頻度)」「文書長を平均文書長で正規化した係数」を組み合わせた式で計算され、これらをクエリ中の全単語について合計することで最終スコアを得る。

コード例

rank_bm25でBM25スコアを計算する

from rank_bm25 import BM25Okapi

corpus = [
    "猫が窓辺で眠っている".split(),
    "犬が公園で走っている".split(),
    "今日の天気は晴れ".split(),
]
bm25 = BM25Okapi(corpus)

query = "公園 犬".split()
scores = bm25.get_scores(query)

print(scores)

利点

埋め込みモデルを必要とせず、計算が軽量で高速に動作する
固有名詞や型番等、表記の完全一致が重要なクエリに強い
長年の実績があり、実装・チューニングのノウハウが豊富

欠点

クエリと文書で表記が異なる同義語や言い換えには対応できない
単語の意味やクエリの文脈を考慮しないため、セマンティック検索と比べ意味的な検索には弱い
日本語等、単語の区切りが明確でない言語では事前の形態素解析が必要になる

比較

セマンティック検索 — BM25は、セマンティック検索と対比される代表的なキーワードベースの検索アルゴリズム
ハイブリッド検索 — ハイブリッド検索では、キーワード検索側のアルゴリズムとしてBM25がよく使われる
RRF — RRFは、BM25によるキーワード検索の結果とベクトル検索の結果を統合する際によく使われる

よくある質問

BM25は今でも使われている？

埋め込みベースの検索が普及した現在も、軽量さと固有名詞検索への強さから、ハイブリッド検索の一方の要素として広く使われ続けている。

BM25のパラメータは何を調整する？

単語頻度によるスコアの飽和具合を調整するパラメータ(k1)と、文書長がスコアに与える影響度を調整するパラメータ(文書長正規化係数)があり、コーパスの性質に応じてチューニングされることがある。

参考文献

Research PaperThe Probabilistic Relevance Framework: BM25 and Beyond
DocumentationElasticsearch: Okapi BM25 Similarity