SparseEmbedの論文を読んでまとめてみた

個人的に検索に興味があり、特にsparse vectorを使った検索に興味があるので2023年のSIGIRでBest Short PaperだったSparseEmbedの論文について読んで以下にまとめた。
# まとめ
今までのベクトル検索とsparse vector検索はそれぞれいいところがあるので両方の良さを引き出す手法を提案した。
# 背景情報
情報検索とは、ユーザがなんらかの情報を取得したい意図によって作成したクエリと関連するドキュメントを取得することである。クエリとマッチするドキュメントを取得するためにはクエリのtermとドキュメントのtermを比較し、クエリと同じtermが含まれるドキュメントを取得する必要がある。しかし、同じtermが含まれるかどうかで関連するドキュメントかどうかを判断する方法だと、異なるtermだが意味が同じ、近いtermをマッチさせることができない。論文の例だと、「big apple stands for」というクエリは「big appleが何を表しているか」というクエリになるので、「nyc」や「nickname」とマッチさせたいが、クエリにそれらのtermが入っていないのでマッチさせることができない。それを対処するのが、ベクトル検索と呼ばれる手法だ。
# ベクトル検索とは
ベクトル検索とは、クエリとドキュメントの両方をベクトル化し、ベクトルの類似度によって意味の近さを表現することで、termが異なってもmatchさせることができる検索である。
意味の近さによってクエリとドキュメントの関連度を推定できる一方で、クエリやドキュメントをembeddingするため処理が遅い。それを解決したのがこの論文の比較手法で使われるColBERTだ。colBERTでは、事前にドキュメントだけBERTでベクトル化し、推論時はクエリのみベクトル化することで速度の問題をクリアしている。しかし、それでもクエリのベクトルを全てのドキュメントと比較するためには計算資源や時間が必要である。また、ベクトルで表現することが難しいマイナーな固有表現や型番などを、正しいドキュメントにマッチすることも難しい。これらの問題を解決するアイデアの一つとして、sparse vector検索と呼ばれる手法がある。
# sparse vector検索とは
sparse vectorとは、各次元の要素のほとんどが0であるベクトルである。sparse vector検索では、ベクトルの各次元は各termとその重みを表す。そうすることで、クエリとドキュメントの関連度を計算するときは、クエリのベクトルの0じゃない次元のみに注目すればいいのでterm matchと同様の方法で取得できる。もちろん転置インデックスも組み込める。term matchとの大きな違いは、sparse vectorがデンスなベクトルとほぼ同じ手法で学習されることである。そうすることで、クエリやドキュメントに存在しないが意味が近いtermにも重みをつけることができる。本論文では、sparse vector検索の代表としてSPLADEについて言及しており、比較手法として用いられている。

# 提案手法
この論文の提案手法は、上記のdence vectorとsparse vectorの両方でクエリ、ドキュメントを表現し、それぞれを用いて関連するドキュメントを取得する手法である。まず、sparse vectorをindexingで用いることで全てのドキュメントからクエリに関連する一部のドキュメントに絞り、それらのドキュメントをさらにdence vectorを用いて関連度が高い順に並び替える。
# sparse vectorの作成方法
![スクリーンショット 2024-02-17 1.34.13.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3679098/311842d5-f750-6bf8-6835-e7e39e0a9e1b.png)

Figure 2のようにしてsparse vectorを作成する。
クエリまたはドキュメントをBERT等に入れ、その出力層をMLMとpoolingを通してtop-kをとるというシンプルな手法である。
# dence vectorの作成方法
![スクリーンショット 2024-02-17 1.34.26.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3679098/6716442f-193d-9765-8335-7901a65ef2fb.png)

Figure 3のようにしてdence vectorを作成する。このとき、sparse vectorで表現できる単語の一部は入力として含まれない。よって、その単語に関してあらかじめMLMによって学習されたlogitsをアテンションスコアとして用いて、通常のBERT等に入れた際のシーケンスembeddingのattention層で利用する。こうしてsparse vectorでアクティブな単語に関するdence vectorを表現することができる

# 実験
提案手法と既存手法を比較し、精度と実行速度を評価した。提案手法はいくつかのパターンで評価され、平均的に他の手法よりも優れた結果を示した。

## 結果
![スクリーンショット 2024-01-26 22.54.00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3679098/c12da822-a6dd-9c1a-f096-e6732a1f0499.png)

まずはMS MARCOでcolBERTやSPLADEと、関連したドキュメントの取得精度と実行速度について比較した。
精度に関して、MRR@10やR@1kで見ると、colBERTv2には劣るものの、SPLADEより高い精度を出せていることがわかる。TERMSという、ランダムなクエリとランダムなドキュメントでmatchしたterm数を表す指標を見ると、提案手法の上ふたつがSPLADEより小さいので、単純にマッチする単語を増やしたから精度が良くなったのではなく文脈埋め込みの力だということがわかる。平均速度に関しては、残念ながらSPLADEより劣る。

![スクリーンショット 2024-01-26 22.54.11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3679098/583c14cb-1098-7f25-c536-5a7487f0b9d9.png)

MS MARCO以外のデータセットでの評価も添付する。ドメインによって結果は異なるが、平均的に見れば提案手法が他の手法より高い。SPLADEもColBERTより高く、sparse vector検索がうまくいっている。

# 感想
sparse vector検索とdence vector検索のいいとこ取りをしようという発想に対して、しっかりとした実験によって精度や速度面での検証がしっかりできている論文だと思った。
個人的にはSPLADEで十分精度がいいので、検索に関しては単語マッチも今後発展しそうな予感がした。

# 参考論文
Weize Kong and Jeffrey M. Dudek and Cheng Li and Mingyang Zhang and Mike Bendersky. SparseEmbed: Learning Sparse Lexical Representations with Contextual Embeddings for Retrieval. 2023. Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '23)
https://research.google/pubs/sparseembed-learning-sparse-lexical-representations-with-contextual-embeddings-for-retrieval/

sparse vector検索等の用語はこちらを参考にしました
https://qiita.com/wararaki/items/828fa8f5c62fcff3de07