BM25S: Orders of magnitude faster lexical search via eager sparse scoring

nogawanogawa commented 4 months ago

論文URL

https://arxiv.org/abs/2407.03618

著者

Xing Han Lù

会議

なし

背景

目的

従来のBM25より高速なスコアリングの実現

アプローチ

BM25S
- 事前計算によるスコアリング計算量の削減
- 疎行列の活用によるメモリ効率向上
- トークン化・Top0-kアルゴリズムの高速化

ひとことメモ

最近BM42とか出てたので一応

nogawanogawa commented 4 months ago

背景

nogawanogawa commented 4 months ago

目的

従来のBM25より高速なスコアリングの実現

アプローチ

BM25S
- 事前計算によるスコアリング計算量の削減
- 疎行列の活用によるメモリ効率向上
- トークン化・Top0-kアルゴリズムの高速化

nogawanogawa commented 4 months ago

ポイント

要するに高速・軽量な検索アルゴリズム

事前計算による計算量の削減

考えられるすべてのトークンについて、事前にドキュメントのスコアを計算する。これによって、検索時にスコアを動的に計算することがなくなるので高速化する。

スパース行列の活用によるメモリ効率の向上

インデックス作成時にすべてのクエリ単語とドキュメントのペアに対して、出現する可能性のあるトークンごとのBM25スコアを事前に計算しますが、この計算の多くは行列計算となっている。

とくに多くのtermはドキュメントに含まれることはないので、疎行列になる。これをPythonの疎行列計算ライブラリを使って軽量・高速に計算するしている。

高速なトークン化とTop-k選択アルゴリズムの採用

トークン化にsklearnのtokenizerを使用することがで高速化（本当？）

更にorderingはQuickselectというアルゴリズムで上位k件を発見するらしい。（あんまり分かってないがsortだと計算量O(nlogn)だったものがtop-kだけならO(n)になり効率は良いらしい） https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BB%E3%83%AC%E3%82%AF%E3%83%88#:~:text=%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BB%E3%83%AC%E3%82%AF%E3%83%88%EF%BC%88%E8%8B%B1%3A%20quickselect%EF%BC%89,%E3%81%AE%E9%81%B8%E6%8A%9E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%82%82%E5%91%BC%E3%81%B0%E3%82%8C%E3%82%8B%E3%80%82

nogawanogawa commented 4 months ago

性能評価

-> 高速化していることを確認（vs ES, PT）

-> 性能的には他アルゴリズムと遜色なさそう

nogawanogawa / paper_memo