論文の概要: Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders

• arxiv url: http://arxiv.org/abs/2405.03651v1
• Date: Mon, 6 May 2024 17:14:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-07 12:57:40.739631
• Title: Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders
• Title（参考訳）: クロスエンコーダを用いたk-NN探索のための適応検索とスケーラブルインデックス化
• Authors: Nishant Yadav, Nicholas Monath, Manzil Zaheer, Rob Fergus, Andrew McCallum,
• Abstract要約: クエリ-イムペアを共同で符号化することで類似性を計算するクロスエンコーダ(CE)モデルは、クエリ-イム関連性を推定する埋め込みベースモデル(デュアルエンコーダ)よりも優れている。 本稿では,潜時クエリとアイテム埋め込みを効率的に計算してCEスコアを近似し,CE類似度を近似したk-NN探索を行うスパース行列分解法を提案する。
• 参考スコア（独自算出の注目度）: 77.84801537608651
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cross-encoder (CE) models which compute similarity by jointly encoding a query-item pair perform better than embedding-based models (dual-encoders) at estimating query-item relevance. Existing approaches perform k-NN search with CE by approximating the CE similarity with a vector embedding space fit either with dual-encoders (DE) or CUR matrix factorization. DE-based retrieve-and-rerank approaches suffer from poor recall on new domains and the retrieval with DE is decoupled from the CE. While CUR-based approaches can be more accurate than the DE-based approach, they require a prohibitively large number of CE calls to compute item embeddings, thus making it impractical for deployment at scale. In this paper, we address these shortcomings with our proposed sparse-matrix factorization based method that efficiently computes latent query and item embeddings to approximate CE scores and performs k-NN search with the approximate CE similarity. We compute item embeddings offline by factorizing a sparse matrix containing query-item CE scores for a set of train queries. Our method produces a high-quality approximation while requiring only a fraction of CE calls as compared to CUR-based methods, and allows for leveraging DE to initialize the embedding space while avoiding compute- and resource-intensive finetuning of DE via distillation. At test time, the item embeddings remain fixed and retrieval occurs over rounds, alternating between a) estimating the test query embedding by minimizing error in approximating CE scores of items retrieved thus far, and b) using the updated test query embedding for retrieving more items. Our k-NN search method improves recall by up to 5% (k=1) and 54% (k=100) over DE-based approaches. Additionally, our indexing approach achieves a speedup of up to 100x over CUR-based and 5x over DE distillation methods, while matching or improving k-NN search recall over baselines.
• Abstract（参考訳）: クエリ-イムペアを共同で符号化することで類似性を計算するクロスエンコーダ(CE)モデルは、クエリ-イム関連性を推定する埋め込みベースモデル(デュアルエンコーダ)よりも優れている。 既存のアプローチでは、CEの類似性を2エンコーダ(DE)またはCUR行列の分解に適合するベクトル埋め込み空間に近似することで、CEを用いたk-NN探索を行う。 DEベースの検索と参照のアプローチは、新しいドメインに対するリコールの低さに悩まされ、Dによる検索はCEから切り離される。 CURベースのアプローチは、DEベースのアプローチよりも正確だが、アイテムの埋め込みを計算するには、非常に多くのCEコールが必要になるため、大規模にデプロイするには実用的ではない。 本稿では,提案したスパース行列因数分解法を用いて,CEスコアを近似するために潜時クエリとアイテム埋め込みを効率的に計算し,CE類似度を近似したk-NN探索を行う。 一連の列車問合せに対する問合せCEスコアを含むスパース行列を分解することにより、アイテム埋め込みをオフラインで計算する。 提案手法は,CUR法に比べて少数のCE呼び出ししか必要とせず,高い品質の近似を生成できるとともに,DEMを利用して蒸留によるDDEの計算および資源集約的な微調整を回避しつつ,埋め込み空間を初期化することができる。 テスト時、アイテムの埋め込みは固定され、検索はラウンドで行われ、相互に交互に行われる。 イ これまでに検索した項目のCEスコアの近似における誤差を最小化して、検査クエリの埋め込みを推定すること。 b) より多くの項目を取得するために更新されたテストクエリの埋め込みを使用する。 我々のk-NNサーチ手法は、D-basedアプローチよりも最大5%(k=1)と54%(k=100)のリコールを改善する。 さらに, 提案手法は, CUR法で最大100倍, DE法で最大5倍の高速化を実現し, ベースライン上でのk-NN検索リコールのマッチングや改善を実現している。

関連論文リスト

• pEBR: A Probabilistic Approach to Embedding Based Retrieval [4.8338111302871525]
  埋め込み検索は、クエリとアイテムの両方の共有セマンティック表現空間を学習することを目的としている。 現在の産業実践では、検索システムは典型的には、異なるクエリに対して一定数のアイテムを検索する。
  論文  参考訳（メタデータ） (2024-10-25T07:14:12Z)
• Efficient Inference of Sub-Item Id-based Sequential Recommendation Models with Millions of Items [63.117573355917465]
  PQTopKアルゴリズムを用いてRecJPQに基づくモデルの推論効率を改善することができることを示す。 我々は、RecJPQで強化されたSASRecを、元のSASRecの推論手法に比べて4.5倍、RecJPQコードで実装された手法に比べて1.56倍の速度で高速化する。
  論文  参考訳（メタデータ） (2024-08-19T13:43:48Z)
• Retrieval with Learned Similarities [2.729516456192901]
  最先端の検索アルゴリズムは、学習された類似点に移行した。 そこで本研究では,Mixture-of-Logits (MoL) を実証的に実現し,多様な検索シナリオにおいて優れた性能が得られることを示す。
  論文  参考訳（メタデータ） (2024-07-22T08:19:34Z)
• Faster Learned Sparse Retrieval with Block-Max Pruning [11.080810272211906]
  本稿では,学習されたスパース検索環境に出現するインデックスに適した,革新的な動的プルーニング戦略であるBlock-Max Pruning(BMP)を紹介する。 BMPは既存の動的プルーニング戦略を大幅に上回り、安全な検索コンテキストにおいて非並列効率を提供する。
  論文  参考訳（メタデータ） (2024-05-02T09:26:30Z)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。 我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-12-17T04:41:07Z)
• Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition [77.4863142882136]
  クロスエンコーダモデルは、直接k-nearest neighbor(k-NN)サーチには不当に高価である。 本稿では,現実的に重要なトップk近傍の近似誤差を適応的に,反復的に,効率的に最小化するADACURを提案する。
  論文  参考訳（メタデータ） (2023-05-04T17:01:17Z)
• Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization [60.91600465922932]
  本稿では,クロスエンコーダのみに頼って,二重エンコーダによる検索を回避する手法を提案する。 我々のアプローチは、現在の広く使われている方法よりも優れたテスト時間リコール-vs計算コストトレードオフを提供する。
  論文  参考訳（メタデータ） (2022-10-23T00:32:04Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。 クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。 我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
  論文  参考訳（メタデータ） (2021-03-17T23:13:25Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。