論文の概要: Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition

• arxiv url: http://arxiv.org/abs/2305.02996v2
• Date: Mon, 23 Oct 2023 17:48:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-25 12:44:43.079772
• Title: Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition
• Title（参考訳）: 適応多元CUR分解を用いたクロスエンコーダを用いた効率的なk-NN探索
• Authors: Nishant Yadav, Nicholas Monath, Manzil Zaheer, Andrew McCallum
• Abstract要約: クロスエンコーダモデルは、直接k-nearest neighbor(k-NN)サーチには不当に高価である。 本稿では,現実的に重要なトップk近傍の近似誤差を適応的に,反復的に,効率的に最小化するADACURを提案する。
• 参考スコア（独自算出の注目度）: 77.4863142882136
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cross-encoder models, which jointly encode and score a query-item pair, are prohibitively expensive for direct k-nearest neighbor (k-NN) search. Consequently, k-NN search typically employs a fast approximate retrieval (e.g. using BM25 or dual-encoder vectors), followed by reranking with a cross-encoder; however, the retrieval approximation often has detrimental recall regret. This problem is tackled by ANNCUR (Yadav et al., 2022), a recent work that employs a cross-encoder only, making search efficient using a relatively small number of anchor items, and a CUR matrix factorization. While ANNCUR's one-time selection of anchors tends to approximate the cross-encoder distances on average, doing so forfeits the capacity to accurately estimate distances to items near the query, leading to regret in the crucial end-task: recall of top-k items. In this paper, we propose ADACUR, a method that adaptively, iteratively, and efficiently minimizes the approximation error for the practically important top-k neighbors. It does so by iteratively performing k-NN search using the anchors available so far, then adding these retrieved nearest neighbors to the anchor set for the next round. Empirically, on multiple datasets, in comparison to previous traditional and state-of-the-art methods such as ANNCUR and dual-encoder-based retrieve-and-rerank, our proposed approach ADACUR consistently reduces recall error-by up to 70% on the important k = 1 setting-while using no more compute than its competitors.
• Abstract（参考訳）: k-nearest neighbor (k-nn) の直接探索にはクロスエンコーダモデル (cross-encoder model) が高価である。 その結果、k-NNサーチでは高速な近似検索(BM25やデュアルエンコーダベクターなど)が採用され、その後クロスエンコーダが採用される。 この問題はANNCUR (Yadav et al., 2022) によって取り組まれており、これはクロスエンコーダのみを使用し、比較的少数のアンカーアイテムとCUR行列の分解を用いて探索を効率化する。 ANNCURの1回限りのアンカーの選択は、平均してエンコーダ間の距離を近似する傾向にあるが、クエリの近くのアイテムまでの距離を正確に推定する能力は失われ、重要なエンドタスクであるトップk項目のリコールを後悔する。 本稿では,実用上重要なトップk近傍の近似誤差を適応的に,反復的に,効率的に最小化するADACURを提案する。 これまでに利用可能なアンカーを使用してk-NN検索を反復的に実行し、次に次のラウンドのアンカーセットに追加する。 anncurやdual-encoderベースのresearch-and-rerankといった従来および最先端のメソッドと比較して,複数のデータセットにおいて,提案手法は,重要なk = 1設定におけるリコールエラーを,コンペティタよりも多く使用しながら,一貫して70%削減する。

関連論文リスト

• Early Exit Strategies for Approximate k-NN Search in Dense Retrieval [10.48678957367324]
  アーリーエグジットのための最先端のA-kNNを構築し,忍耐の概念に基づく教師なし手法を提案する。 我々は,A-kNNの効率を最大5倍の高速化で向上すると同時に,無視可能な効率損失を達成できることを示す。
  論文  参考訳（メタデータ） (2024-08-09T10:17:07Z)
• Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders [77.84801537608651]
  クエリ-イムペアを共同で符号化することで類似性を計算するクロスエンコーダ(CE)モデルは、クエリ-イム関連性を推定する埋め込みベースモデル(デュアルエンコーダ)よりも優れている。 本稿では,潜時クエリとアイテム埋め込みを効率的に計算してCEスコアを近似し,CE類似度を近似したk-NN探索を行うスパース行列分解法を提案する。
  論文  参考訳（メタデータ） (2024-05-06T17:14:34Z)
• Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining [61.09807522366773]
  本稿では,ソフトマックスを証明可能な境界で近似し,木を動的に維持するアルゴリズムを提案する。 我々は,2000万以上のターゲットを持つデータセットについて検討し,オラクル・ブルート力負の鉱業に関して,誤差を半分に削減した。
  論文  参考訳（メタデータ） (2023-03-27T15:18:32Z)
• A Token-Wise Beam Search Algorithm for RNN-T [3.682821163882332]
  本稿では,複数の時間ステップにまたがる共同ネットワークコールをバッチ化する復号ビーム探索アルゴリズムを提案する。 さらに、セグメント上での放射確率の集約は、最も可能性の高いモデル出力を見つけるためのより良い近似と見なすことができる。
  論文  参考訳（メタデータ） (2023-02-28T07:20:49Z)
• Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization [60.91600465922932]
  本稿では,クロスエンコーダのみに頼って,二重エンコーダによる検索を回避する手法を提案する。 我々のアプローチは、現在の広く使われている方法よりも優れたテスト時間リコール-vs計算コストトレードオフを提供する。
  論文  参考訳（メタデータ） (2022-10-23T00:32:04Z)
• ReAct: Temporal Action Detection with Relational Queries [84.76646044604055]
  本研究は,アクションクエリを備えたエンコーダ・デコーダフレームワークを用いて,時間的行動検出(TAD)の進展を図ることを目的とする。 まず,デコーダ内の関係注意機構を提案し,その関係に基づいてクエリ間の関心を誘導する。 最後に、高品質なクエリを区別するために、推論時に各アクションクエリのローカライズ品質を予測することを提案する。
  論文  参考訳（メタデータ） (2022-07-14T17:46:37Z)
• Improving Novelty Detection using the Reconstructions of Nearest Neighbours [0.0]
  自動エンコーダ (AE) の潜伏空間に近接する近傍での使用は, 半教師付きノベルティ検出の性能を著しく向上させることを示した。 提案手法は, 近接する近傍の復元と, 入力の潜時表現の潜時距離の組合せを利用する。
  論文  参考訳（メタデータ） (2021-11-11T11:09:44Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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