BM25全文検索アルゴリズムの理解
(emschwartz.me)- BM25 は、正確なキーワードマッチングが必要な全文検索で今なお広く使われており、ベクトル類似検索を補完する ハイブリッド検索 の一角を担っている
- 確率を直接計算しなくても文書の順位を決められるように、BM25はクエリ項ごとの重みを足し合わせ、関連性が高そうな文書を上位に配置する
- スコアは IDF、文書内の用語頻度、文書長の正規化で構成され、まれな単語はより強く反映し、繰り返し出現は次第に報酬を小さくする
k1は繰り返し出現に対する報酬の逓減速度を、bは文書長正規化の強さを調整し、通常はk1=1.2~2、b=0.75が使われる- BM25スコアは実際の関連確率ではないため、汎用的な比較値のようには使いにくく、同じ文書コレクション の中で比較するときに意味を持つ
BM25が解こうとする検索の問題
- BM25 または Best Match 25 は、全文検索で広く使われているアルゴリズム
- Lucene/Elasticsearch や SQLite などでデフォルトとして使われている
- 最近では、全文検索とベクトル類似検索を組み合わせた ハイブリッド検索 が一般的になっている
- パーソナライズされたコンテンツフィードでは、ベクトル類似検索だけでは正確なキーワード処理が不十分なことがある
- 関心が
Solid.jsの場合、ベクトル類似検索だけを使うと、Solid より React 関連のコンテンツが多く出てくる可能性がある
- 関心が
- 核心となる問いは、ある文書のBM25スコアを複数のクエリ間で比較し、その文書がどのクエリに最もよく合うかを判断できるかどうかである
確率ランキング原理とBM25のアプローチ
- 全文検索の目標は、クエリを基準に、可能な文書集合の中から 最も関連性の高い文書 を見つけること
- 実際の関連性を確実に知ることはできないため、検索は文書がクエリに関連している 確率 を基準に並べ替えようとする
- この考え方は Probability Ranking Principle と呼ばれる
- BM25のような語彙ベース検索は、クエリと文書コレクション内の文書特性だけを使う
- ベクトル類似検索は、外部テキストコーパスで学習された埋め込みモデルを使って、クエリと文書の意味を表現できる
BM25スコアを構成する要素
- BM25は、クエリと文書コレクションの複数のシグナルを組み合わせてスコアを計算する
-
クエリ項
- 検索クエリが複数の用語で構成される場合、各用語ごとのスコアを計算してから合算する
-
逆文書頻度（IDF）
- 特定の検索語が文書コレクション全体でどれだけまれかを表す
the、andのような一般的な単語は情報量が低いとみなし、まれな単語の重要度を高める
-
文書内用語頻度
- 検索語が特定の文書に何回現れるかを反映する
- 同じ用語がより多く繰り返されるほど関連している可能性が高いとみなすが、BM25は繰り返し出現に 逓減効果 を適用する
-
文書長
- 長い文書では、長いという理由だけで検索語がより多く現れる可能性がある
- BM25は文書長を平均文書長と比較し、長い文書が不当に高いスコアを受け取らないよう正規化する
BM25の数式の各部分
- BM25の総合スコアは、文書
DとクエリQに対して、各クエリ項q_iのスコアを足し合わせる形で求めるD: 対象文書Q: クエリ全体n: クエリ項の数q_i: 各クエリ項
-
IDF: コレクション内で希少な単語をより強く反映
- IDF項は、クエリ項が文書コレクション全体でどれだけまれかを計算する
N: コレクション内の総文書数n(q_i): クエリ項を含む文書数N - n(q_i): クエリ項を含まない文書数- 一般的な用語は多くの文書に現れるため、スコアへの影響は小さくなる
- まれな用語は少数の文書にしか現れないため、スコアにより強く反映される
- 数式中の
0.5と1は、用語が極端にまれ、または極端に一般的なときに結果が大きくぶれないよう緩和する役割を持つ
-
用語頻度: 繰り返しは反映するが、無限に報酬を与えない
- 文書内用語頻度は、特定のクエリ項が特定の文書にどれだけ頻繁に現れるかを反映する
f(q_i, D): クエリ項q_iが文書Dに現れる頻度k1: 通常1.2から2の間に設定されるチューニングパラメータ- BM25は用語の繰り返しをスコアに反映するが、繰り返しが増えるほど追加スコアの上昇幅は小さくなる
k1は用語の繰り返しに対する報酬がどれだけ早く減るかを制御する
-
文書長正規化: 長い文書の有利さを調整
- 文書長正規化は、対象文書の長さをコレクションの平均文書長と比較する
|D|: 対象文書の長さavgdl: コレクションの平均文書長b: 文書長正規化の強さを制御するチューニングパラメータ- 平均より長い文書は検索語がより頻繁に現れる可能性があるため、最終式の分母で不利になる
b=0なら文書長正規化は無効になり、b=1なら完全に適用されるbは通常0.75に設定される
BM25の中核アイデア
- BM25は Probability Ranking Principle に基づいているが、文書関連性の 真の確率 を計算することはほぼ不可能である
- 検索で重要なのは正確な確率値よりも文書の 順序 であるため、順序に影響しない項を数式から除いて計算を実用化している
- このためBM25が計算するのは確率そのものではなく重みである
- Robertson/Sparck Jones Weight は、関連文書数とクエリ項を含む文書数を使って確率を推定する方法
r: クエリ項を含む関連文書数N: コレクション内の総文書数R: コレクション内の関連文書数n: クエリ項を含む文書数
- この方法の大きな限界は、まずどの文書が関連しているかを知っていなければならない点にある
「ほとんどの文書は関連しない」という仮定
- BM25の開発者は、任意のクエリに対してほとんどの文書は関連しないと仮定した
- 関連文書数は無視できるほど小さいとみなせば、
R = r = 0と置ける - この値を Robertson/Sparck Jones Weight の式に代入すると、BM25で使われるIDF項とほぼ同じ形が得られる
- 関連性情報を事前に要求せず、それでいて同じ理論的基盤を維持できたため、BM25ははるかに実用的になった
- Victor Lavrenko はこれを "very impressive leap of faith" と表現している
BM25スコア比較の範囲
- BM25スコアは一般に直接比較しにくい
- 0から1の間の確率スコアを作るものではない
- 文書が関連している実際の確率を推定しようとするアルゴリズムでもない
- 特定のコレクション内で、クエリに対する関連可能性の順序を近似することに焦点を当てている
- より高いBM25スコアは、その文書がより関連している可能性が高いというシグナルだが、実際の関連確率ではない
- 同じ文書コレクション内の同じ文書については、複数のクエリのBM25スコアを比較できる
- BM25は各クエリ項のスコアを合算するため、2つのクエリ項のスコア比較と、2つのクエリ全体のスコア比較との間に意味上の差はないと考えられる
- 重要な制約は 同じ文書、同じコレクション であること
- BM25はコレクション内のIDFと平均文書長を使う
- コレクションが変わるとスコアも変わりうるため、時間をまたいだスコア比較は保証されない
- パーソナライズされたコンテンツフィードでは、ユーザーの関心ごとに全文検索を実行してBM25スコアを比較し、どのコンテンツがどの関心により適しているかを判断するのに使える
さらに読むための資料
- BM25の理論と歴史をさらに掘り下げるには、Elastic のエンジニア Britta Weber による2016年の発表 Improved Text Scoring with BM25 を参照できる
- Stephen Robertson と Hugo Zaragoza による The Probabilistic Relevance Framework: BM25 and Beyond は、BM25の確率的関連性フレームワークを扱っている
- BM25と他の全文検索アルゴリズムの比較は、Comparing full text search algorithms: BM25, TF-IDF, and Postgres で読める
1件のコメント
Hacker News のコメント
一般的な検索には https://typesense.org/ を使っているのですが、今はハイブリッド検索にも対応しているので、使ったことがある人がいるのか気になります
ここで Typesense が言及されているのを見てうれしいです。小規模な RAG プロジェクトには合うことが多いはずなのに、不思議とあまり知られていない印象です
デプロイが簡単で、デフォルト値も妥当、ドキュメントも良く、クラスタリングも比較的簡単です。それでいて、より深く掘り下げる必要がある場合にも十分に高性能で強力です
ただし埋め込みモデルに外部プロバイダーを使うとレイテンシが 500ms+ と法外に高くなるので、クラスタ内で自前ホスティングするほうがよいです
ハイブリッド検索の品質は良いですが、調整オプションが非常に限られており、スコアも結果集合内での順位付け以外についてはかなり不透明です
最近のベクトルベースの意味検索の発展を踏まえると、今どきキーワード検索 + 意味検索のハイブリッドに使う最新の検索スタックは何なのか気になります
最近、自由記述欄が10個ずつあるアンケート約300万件を受け取り、会社が対応すべき項目を見つける必要がありました
小さな分類器モデルをいくつか使い、最初の1万件で見えてきたノイズを見て一般的な単語を手作業で除外し、そのうえでモデルの応答に重み付けしたところ、ほぼ完璧に動きました
こういうものは「プログラミング」というより、複数のツールのブラックボックス出力を、テストケースと顧客にとって良さそうに見えるまで調整する作業に近いです
ちなみに、小さなサーバー上で Node.js を使い、複数の Hugging Face 小型モデルをつないで処理しました
結果は通常、**相互順位融合（RRF）**で統合します
RRF の論文は驚くほど単純で印象的ですし、論文自体も2ページしかありません: https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
BM25 系のタスクには Elasticsearch、単純で高速なベクトル検索には Turbopuffer、特定クエリの結果を事前計算したり、価格のように頻繁に変わる動的属性には Redis も使えます
こうしたものを scatter/gather 方式で組み合わせるのがよいと思います
検索スタックの外側には、ほぼ常に再ランキング用の推論サービス層があり、理想的には他の機械学習インフラと似た単純なサービスになります
ユーザーのクエリを理解して、「ID で取得」はあるシステムへ、「ファジーな意味検索」は別のシステムへ送る、といったルーティングもほぼ常に必要です
これらはデータ構造が大きく異なり、検索は概して互いに異なるユースケースを幅広くカバーします
すべてを1つのシステムに押し込むのはアンチパターンだと思います
各システムはそれぞれ異なるワークロードに適しており、内蔵の推論機能は、機械学習エンジニアが慣れている一般的な機械学習ツールの速度にはなかなか追いつけません
Elasticsearch Learning to Rank で試しましたが、見込みのない作業でした
それでも、幅広いユースケースを1つのスタックで解こうとする試みの中では、Vespa がたぶん最も優れています
txtai の作者として言うと、txtai は Python で arrays パッケージを通じて高性能な BM25 インデックスを実装し、用語頻度ベクトルを SQLite に保存します
txtai のハイブリッドインデックス方式は、BM25 スコアが正規化されていれば凸結合を、正規化されていなければ**相互順位融合（RRF）**をサポートします
[1] https://github.com/neuml/txtai
[2] https://neuml.hashnode.dev/building-an-efficient-sparse-keyw...
[3] https://neuml.hashnode.dev/benefits-of-hybrid-search
[4] https://github.com/neuml/txtai/blob/master/src/python/txtai/...
語彙ベース検索（bm25、ファジー検索）、意味検索（埋め込み）、再ランキング（cross-encoder、相互順位融合）、多様性の確保と lost-in-the-middle の緩和のための再ランキングまで、複数の検索手法を使っています
[1] Langroid - CMU/UW-Madison の研究者たちが作ったマルチエージェント LLM フレームワーク https://github.com/langroid/langroid
[2] DocChatAgent の実装 -
https://github.com/langroid/langroid/blob/main/langroid/agen...
answer_from_docs メソッドからたどっていけばよいです
付け加えると、Kadoa の創業者であれば、Kadoa-snack は LLM 関連の HN 議論を探すのに毎日愛用しているツールの1つです
良い記事です。
もう少し見つけにくい背景を付け加えると、BM25は「Best Matching 25」の略で、「best matching」とはクエリ内の語と文書内の語を照合し、順位付けと語の重み付けを行う公式という意味です。
25は単なる通し番号で、それ以前に24個の公式の変種があり、その後の変種もありましたが、25番が最もよく機能したため発表されたものです。
Stephen RobertsonとKaren Spärck Jones（IDFで有名）が考案し、RobertsonのOKAPI情報検索研究システムに初めて実装されました。
OKAPIシステムは米国NISTの年次TREC（Text Retrieval Conference）で何年にもわたってベンチマークされており、これは検索エンジン方法論における国際的な「世界選手権」に近いものです。
ただし、このイベントは優勝よりも比較と相互学習を目的としており、毎年11月にメリーランド州Gaithersburgで開催される、おすすめできるイベントです。
「bag of words」ベクトル空間モデル（語の疎ベクトル）、BM25が属する確率モデル以外にも、クエリが与えられたときに文書集合を順位付けする理論的枠組みは驚くほど多く、増え続けています。
たとえば、Divergence from Randomness、統計的言語モデリング、Learning to Rank、量子情報検索、ニューラルネットワークによるランキングなどがあります。
ICTIRやSIGIRのような学会では、今でも時折まったく新しい検索パラダイムが登場します。
ここでいう「統計的言語モデリング」は、最近流行している大規模言語モデルを指すものではなく、そちらは「ニューラル検索」のカテゴリに入ります。
また「Quantum IR」を検索すると、量子情報検索のチュートリアルではなく、赤外分光法や同名のセメント会社に出会う可能性があります。
21世紀になっても、検索技術にはこうした微妙な点があります。
BM25と代替手法を直接比較してみたいなら、University of Glasgowで開発されたオープンソース検索エンジン兼研究プラットフォームであるTerrierをおすすめします。
BM25は25年以上前のものですが、今なお越えにくいベースラインであることが証明されており、新しい手法を比較する際の基準点としてよく使われます。
より新しい変種であるBM24Fは、タイトル、本文、ハイパーリンクのような複数のフィールドやハイパーテキストを扱えます。
おすすめの論文は、Spärck Jones, K.; Walker, S.; Robertson, S. E. (2000). “A probabilistic model of information retrieval: Development and comparative experiments: Part 1”. Information Processing & Management 36(6): 779–808、および続くPart 2です。
残念ながらオープンアクセスではありません。
18日に始まり、22日に終わります。
詳細: https://trec.nist.gov/
GoogleとGoogle Scholarで探しても、関連する内容は見つけられませんでした。
恥ずかしながら宣伝します: https://github.com/jankovicsandras/plpgsql_bm25
https://github.com/jankovicsandras/bm25opt
https://github.com/softwaredoug/searcharray
似た目的で非常に人気のあるXing Han LuのBM25Sもあわせて宣伝します。
https://github.com/xhluca/bm25s
大量のテキストやPDF文書を管理するための純Pythonラッパープロジェクトがあるのか気になります。
SolrやElasticSearchを考えましたが、今やろうとしていることには重すぎるように見えます。
SQLiteがBM25を使っているので、pysqlite3とPyPDF2を一緒に使う案を検討中です。
話題から少し外れますが、ハイブリッドなBM25 / ベクトルストア / LLMアプリケーションを作るためのツールを探している人は多そうです。
文書長の正規化でいう平均文書長が中央値なのか気になります。
過度に長い文書の重みを適切に下げるには中央値であるべきな気がしますが、そうでないと長すぎる文書が平均を不当に引き上げてしまうのではないかと思います。
中央値を使うのも興味深い実験になりそうです。
文書長の差が非常に大きい検索データセットをご存じか気になります。
たとえばMSMarcoは長さがかなり一定なほうです。
良い記事です。
こうした問題を数学的な形で考える方法と、それをテストする方法を本気で学びたいのですが、参考になる資料はあるでしょうか？
ハイブリッド検索は、検索結果の関連性という古くからの課題を解決します。
キーワードとベクトルの間でランキング融合を使えば、ほとんどの状況で機能するハイブリッド検索を作れます。
BM25は1970年代に開発された古いアルゴリズムである
基本的には粗い統計モデルで、今の統計学者ならもっとはるかにうまくできる
検索は学習ベースの手法に厳密に支配されていると見ている
もちろん学習は検索を入力として使うことができる
まだそれに気づいていない人や、古い技術をできるだけ長く維持するインセンティブがある人は多いが、市場圧力が最終的には変えるだろう
その技術のせいで、敵対的なSEO戦争を避けるために検索語ごとに「+reddit」を付けるようになったのではないか？
古いから悪いというわけではない
発明や発見、手法の年齢より有用性を見るべきなのに、年齢にこだわる奇妙な技術主義的態度が気になる
実際のアプリケーションでBM25を置き換えるほど優れていると考える、具体的な現代の統計的アプローチは何か？
とくにBM25が明示的に扱おうとした、希少語や文書長の正規化のような境界ケースをどう処理するのかが気になる
学習ベースのアプローチが印象的な結果を示してきたことには同意するが、検索が学習手法に「厳密に支配される」とは正確に何を意味するのかも、もう少し聞きたい
特定のベンチマークの話なのか、実運用の事例の話なのかが気になる
多くの検索専門家は同意しないと思う
David Tippet（元OpenSearch、現GitHub）とNicolay Geroldの素晴らしいポッドキャストのタイトルはこうだ:
“BM25 is the workhorse of search; vectors are its visionary cousin”
https://www.youtube.com/watch?v=ENFW1uHsrLM
検索分野には、私が働いてきた間ずっと、数多くの流行やAI関連技術があった
今は巨額のVC投資を受けたベクトル検索企業が、技術エバンジェリストの大部隊を前面に出して特定の見方を押し出している
一方で、Googleのようなところで「意味検索」を実際に動かしている手作業のキュレーションや、基本的で退屈な手作業の分類体系の量は膨大だ
ただ、そうしたものはセクシーではないので、カンファレンスではあまり語られないだけだ