論文の概要: Linear-Time Demonstration Selection for In-Context Learning via Gradient Estimation

• arxiv url: http://arxiv.org/abs/2508.19999v1
• Date: Wed, 27 Aug 2025 15:59:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-28 19:07:41.694419
• Title: Linear-Time Demonstration Selection for In-Context Learning via Gradient Estimation
• Title（参考訳）: 勾配推定によるインコンテキスト学習のための線形時間デモストレーション選択
• Authors: Ziniu Zhang, Zhenshuo Zhang, Dongyue Li, Lu Wang, Jennifer Dy, Hongyang R. Zhang,
• Abstract要約: 例えば$n$の例があれば、$n$から$k$を素早く選択して、ダウンストリーム推論の条件付けとして役立てるにはどうすればよいでしょうか? この問題は、迅速なチューニングとチェーン・オブ・ソート推論に幅広い応用がある。 勾配推定法は6つのデータセットに対して$mathbf1%$誤差の完全な推論の近似を導出することを示す。
• 参考スコア（独自算出の注目度）: 19.158395403281734
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper introduces an algorithm to select demonstration examples for in-context learning of a query set. Given a set of $n$ examples, how can we quickly select $k$ out of $n$ to best serve as the conditioning for downstream inference? This problem has broad applications in prompt tuning and chain-of-thought reasoning. Since model weights remain fixed during in-context learning, previous work has sought to design methods based on the similarity of token embeddings. This work proposes a new approach based on gradients of the output taken in the input embedding space. Our approach estimates model outputs through a first-order approximation using the gradients. Then, we apply this estimation to multiple randomly sampled subsets. Finally, we aggregate the sampled subset outcomes to form an influence score for each demonstration, and select $k$ most relevant examples. This procedure only requires pre-computing model outputs and gradients once, resulting in a linear-time algorithm relative to model and training set sizes. Extensive experiments across various models and datasets validate the efficiency of our approach. We show that the gradient estimation procedure yields approximations of full inference with less than $\mathbf{1}\%$ error across six datasets. This allows us to scale up subset selection that would otherwise run full inference by up to $\mathbf{37.7}\times$ on models with up to $34$ billion parameters, and outperform existing selection methods based on input embeddings by $\mathbf{11}\%$ on average.
• Abstract（参考訳）: 本稿では,クエリセットのコンテキスト内学習のための実例を選択するアルゴリズムを提案する。 例えば$n$の例があれば、$n$から$k$を素早く選択して、ダウンストリーム推論の条件付けとして役立てるにはどうすればよいでしょうか? この問題は、迅速なチューニングとチェーン・オブ・ソート推論に幅広い応用がある。 文脈内学習においてモデルの重みが固定されているため、従来の研究はトークン埋め込みの類似性に基づいて手法を設計しようとしてきた。 本研究は,入力埋め込み空間における出力の勾配に基づく新しい手法を提案する。 本手法は勾配を用いた一階近似によるモデル出力を推定する。 次に、この推定をランダムにサンプリングした複数のサブセットに適用する。 最後に、サンプル化されたサブセットの結果を集約し、各デモに対する影響スコアを作成し、最も関連する例を$k$で選択する。 この手順では、事前計算されたモデル出力と勾配しか必要とせず、結果としてモデルとトレーニングセットのサイズに対して線形時間アルゴリズムが生成される。 さまざまなモデルやデータセットにわたる大規模な実験は、我々のアプローチの効率性を検証する。 勾配推定法は6つのデータセットに対して$\mathbf{1}\%$誤差の完全な推論を近似することを示した。 これにより、最大34億ドルのパラメータを持つモデル上で、最大$\mathbf{37.7}\times$で完全な推論を実行するサブセットの選択をスケールし、$\mathbf{11}\%$平均で入力埋め込みに基づいて既存の選択メソッドを上回ります。

関連論文リスト

• Revisiting Score Function Estimators for $k$-Subset Sampling [5.464421236280698]
  離散フーリエ変換を用いて,$k$-subset分布のスコア関数を効率的に計算する方法を示す。 得られた推定器は、正確なサンプルと偏りのない勾配推定の両方を提供する。 特徴選択の実験は、仮定が弱いにもかかわらず、現在の手法と競合する結果を示している。
  論文  参考訳（メタデータ） (2024-07-22T21:26:39Z)
• Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond [28.651041302245538]
  我々は$k$-meansクラスタリングとサンプリング感度に基づく新しいデータ選択手法を提案する。 線形回帰にどのように適用できるかを示すとともに,レバレッジスコアサンプリングの性能と驚くほど一致した新しいサンプリング戦略がもたらされる。
  論文  参考訳（メタデータ） (2024-02-27T09:03:43Z)
• An Efficient Rehearsal Scheme for Catastrophic Forgetting Mitigation during Multi-stage Fine-tuning [55.467047686093025]
  このような忘れを緩和するための一般的なアプローチは、微調整中に以前のタスクからサンプルをリハーサルすることである。 側方損傷のリハーサルを優先するサンプリング手法である textttbf mix-cd を提案する。 我々の手法は計算効率が高く、実装が容易で、計算制約のある設定においていくつかの主要な連続学習手法より優れています。
  論文  参考訳（メタデータ） (2024-02-12T22:32:12Z)
• Testable Learning with Distribution Shift [9.036777309376697]
  分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。 テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。 ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
  論文  参考訳（メタデータ） (2023-11-25T23:57:45Z)
• Towards Free Data Selection with General-Purpose Models [71.92151210413374]
  望ましいデータ選択アルゴリズムは、限られたアノテーション予算の有用性を最大化するために、最も情報性の高いサンプルを効率的に選択することができる。 アクティブな学習手法で表現された現在のアプローチは、通常、時間を要するモデルのトレーニングとバッチデータ選択を繰り返し繰り返す、面倒なパイプラインに従う。 FreeSelは重いバッチ選択プロセスをバイパスし、効率を大幅に改善し、既存のアクティブラーニングメソッドよりも530倍高速である。
  論文  参考訳（メタデータ） (2023-09-29T15:50:14Z)
• Bias Mimicking: A Simple Sampling Approach for Bias Mitigation [57.17709477668213]
  本稿では,新しいクラス条件サンプリング手法であるBias Mimickingを紹介する。 Bias Mimickingは、4つのベンチマークで3%の精度でサンプリングの精度を向上する。
  論文  参考訳（メタデータ） (2022-09-30T17:33:00Z)
• Learning the Stein Discrepancy for Training and Evaluating Energy-Based Models without Sampling [30.406623987492726]
  非正規化密度モデルの評価と訓練のための新しい手法を提案する。 データ密度$p(x)$とデータのベクトル関数で定義されるモデル密度$q(x)$とのスタイン差を推定する。 これは、既存の手法を高次元データで上回る、新しい適合性テストをもたらす。
  論文  参考訳（メタデータ） (2020-02-13T16:39:07Z)

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

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