論文の概要: Adaptive Selection of Anchor Items for CUR-based k-NN search with Cross-Encoders

• arxiv url: http://arxiv.org/abs/2305.02996v1
• Date: Thu, 4 May 2023 17:01:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-05 14:37:23.021054
• Title: Adaptive Selection of Anchor Items for CUR-based k-NN search with Cross-Encoders
• Title（参考訳）: クロスエンコーダを用いたCURに基づくk-NN探索におけるアンカー項目の適応選択
• Authors: Nishant Yadav, Nicholas Monath, Manzil Zaheer, Andrew McCallum
• Abstract要約: クロスエンコーダモデルは、クェリイムペアを共同でエンコードし、スコア付けするが、典型的にはkエンコーダの探索には高額である。 本稿では,計算オーバーヘッドが最小限であるクエリに対して,事実上重要なトップk近傍の近似誤差を最小限に抑えるアンカー項目を適応的に選択する手法を提案する。
• 参考スコア（独自算出の注目度）: 64.4817461473056
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cross-encoder models, which jointly encode and score a query-item pair, are typically prohibitively expensive for k-nearest neighbor search. Consequently, k-NN search is performed not with a cross-encoder, but with a heuristic retrieve (e.g., using BM25 or dual-encoder) and re-rank approach. Recent work proposes ANNCUR (Yadav et al., 2022) which uses CUR matrix factorization to produce an embedding space for efficient vector-based search that directly approximates the cross-encoder without the need for dual-encoders. ANNCUR defines this shared query-item embedding space by scoring the test query against anchor items which are sampled uniformly at random. While this minimizes average approximation error over all items, unsuitably high approximation error on top-k items remains and leads to poor recall of top-k (and especially top-1) items. Increasing the number of anchor items is a straightforward way of improving the approximation error and hence k-NN recall of ANNCUR but at the cost of increased inference latency. In this paper, we propose a new method for adaptively choosing anchor items that minimizes the approximation error for the practically important top-k neighbors for a query with minimal computational overhead. Our proposed method incrementally selects a suitable set of anchor items for a given test query over several rounds, using anchors chosen in previous rounds to inform selection of more anchor items. Empirically, our method consistently improves k-NN recall as compared to both ANNCUR and the widely-used dual-encoder-based retrieve-and-rerank approach.
• Abstract（参考訳）: クロスエンコーダモデルは、クエリとitemのペアを共同でエンコードしスコア付けするが、一般的にはk-nearestの隣の探索には高価である。 その結果、k-NNサーチはクロスエンコーダではなく、ヒューリスティックレトリバー(BM25やデュアルエンコーダなど)と再ランクアプローチで実行される。 近年,二重エンコーダを必要とせずにクロスエンコーダを直接近似する効率的なベクトル探索のための埋め込み空間を生成するために,cur行列分解を用いたanncur (yadav et al., 2022) を提案する。 ANNCURは、ランダムにサンプリングされたアンカーアイテムに対してテストクエリをスコアリングすることで、この共有クエリ-イム埋め込み空間を定義する。 これはすべてのアイテムの平均近似誤差を最小化するが、トップkアイテムの平均近似誤差は不適切であり、トップkアイテム(特にトップ1)のリコールが貧弱になる。 アンカーアイテムの数を増やすことは近似誤差を改善するための簡単な方法であり、そのためANNCURをk-NNでリコールするが、推論遅延を増加させるコストがかかる。 本稿では,計算オーバーヘッドが最小のクエリに対して,実際に重要なtop-k近傍の近似誤差を最小化するアンカー項目を適応的に選択する手法を提案する。 提案手法では,前ラウンドから選択したアンカーを使用して,複数のラウンドに対して所定のテストクエリを行うための適切なアンカー項目を段階的に選択する。 提案手法は、ANNCURと広範に使われているデュアルエンコーダベースのレシーバ・アンド・レランダ方式と比較して、k-NNリコールを一貫して改善する。

関連論文リスト

• 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)

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

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