BM25
よく聞く
$ \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)}
IDF: Inverse document frequency
$ N: 文書数 / $ n(q_i): $ q_i を含む文書数
$ \text{IDF}(q_i) = \log\frac{N}{n(q_i)} が普通の IDF?
$ \text{IDF}(q_i) = \ln\left(\frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} + 1\right) BM25 ではこれを使う?
0.5 ずつ足すのは Robertson-Spärck Jones weight、確率推定の話から、ゼロ除算回避にもなる
+1 してスムージング: 単語が半分以上の文書に出現すると負になるので補正する
$ d: 文書
$ D: 文書集合, $ d \in D
なら IDF の $ N = |D| じゃん
$ |d| : 文書dの長さ(ワード数)
$ avgdl: 文書の平均の長さ(ワード数)
$ q: クエリ / $ q_i クエリの i 番目のワード
パラメータ
$ k_1 飽和度を制御するパラメータ
出現頻度が高くても(ワードが d に何回も出てきても) 右側が $ k_i + 1でクリップする
1.2~2.0 よく使われる
$ b 文章長のペナルティ・ボーナスをどれだけ効かせるか
文書が短いのに単語が出てきたらスコア大きく / 長い文書で単語が出てきてもそれほどすごくない の制御
1 だと文書の長さ / 平均文書長をそのまま適用
0 だと $$ |d| / avgdlが消えて文書長を考慮しない
0.75 がよく使われる
$ f(q_i, d) 文書中の $ q_i の出現頻度を表す関数
$ count(q_i) や $ \sqrt{count(q_i)}
これみたらいいです
更新性 & スパースベクトルでの実装
文書の追加&更新ごとに全体を計算するのは大変
IDF, avgdl は非同期の定期更新に
トークン化は事前の辞書で済ませる (未知語は気にしない)
何がいい?
各文書は以下だけ持っておけばいい?
$ f(q_i, d) のスパースベクトル、単なる TF
文書長
検索の時
Σ で足し合わせているのをスパースベクトルの内積やコサイン距離で代替する
$ score(d, q) = \vec{q} \cdot \vec{d}
クエリベクトルを作る
トークン化 & 各トークンの IDF を引いてくる
検索
pgvector は sparsevec にスカラー倍できないのか
↩️ もどる
TF IDF ベース上位とってきて一部だけ計算するのもありではある
転置インデックスを作っておく
単語ID, 文書ID, 頻度 のテーブル
文書追加・更新時に更新
検索のとき
クエリをトークン列にする & IDF を取得
転置インデックスと JOIN しつつスコア計算してソート
GROUP BY 文書ID で SUM
あれ、スパースベクトル要らなくなった
実装
DuckDB FTS + Lindera
統計情報は index 作成時に行われるので drop_fts_index & create_fts_index
Qdrant/bm25 のトークナイズ処理はテキストをハッシュ値にしている abs(mmh3.hash(token))
MurmurHash3