論文の概要: Learning to Ask: Decision Transformers for Adaptive Quantitative Group Testing

• arxiv url: http://arxiv.org/abs/2509.01723v1
• Date: Mon, 01 Sep 2025 19:05:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-04 15:17:03.82664
• Title: Learning to Ask: Decision Transformers for Adaptive Quantitative Group Testing
• Title（参考訳）: 質問への学習:適応的定量化グループテストのための決定変換器
• Authors: Mahdi Soleymani, Tara Javidi,
• Abstract要約: 定量的グループテスト(QGT)の問題点を考察する。 目標は、集合サブセットサムクエリからスパースバイナリベクタを復元することである。 文献の中ではじめて、我々の適応アルゴリズムは、よく知られた非適応的情報理論境界よりも平均的なクエリ数を減らした。
• 参考スコア（独自算出の注目度）: 9.861775841965384
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of quantitative group testing (QGT), where the goal is to recover a sparse binary vector from aggregate subset-sum queries: each query selects a subset of indices and returns the sum of those entries. Information-theoretic results suggest that adaptivity could yield up to a twofold reduction in the total number of required queries, yet no algorithm has surpassed the non-adaptive bound, leaving its practical benefit an open question. In this paper, we reduce the QGT problem to an integer-vector recovery task whose dimension scales with the sparsity of the original problem rather than its full ambient size. We then formulate this reduced recovery task as an offline reinforcement learning problem and employ Decision Transformers to solve it adaptively. By combining these two steps, we obtain an effective end-to-end method for solving the QGT problem. Our experiments show that, for the first time in the literature, our adaptive algorithm reduces the average number of queries below the well-known non-adaptive information-theoretic bound, demonstrating that adaptivity can indeed reduce the number of queries.
• Abstract（参考訳）: 本稿では,各クエリがインデックスのサブセットを選択し,それらのエントリの総和を返却する,集合サブセットサムクエリからスパースバイナリベクタを復元する,量的グループテスト(QGT)の問題を考える。 情報理論の結果、適応性は要求されるクエリの総数を最大2倍に削減できるが、非適応的境界を超えるアルゴリズムは存在しない。 本稿では,QGT問題を,その全周囲サイズではなく,元の問題の範囲で次元がスケールする整数ベクトル回復タスクに還元する。 次に、この削減された回復タスクをオフラインの強化学習問題として定式化し、決定変換器を用いて適応的に解決する。 これら2つのステップを組み合わせることで、QGT問題を解決するための効率的なエンドツーエンドの手法を得る。 実験の結果, 適応アルゴリズムは, 既知の非適応的情報理論境界よりも平均クエリ数を減らし, 適応性が実際にクエリ数を減少させることを示した。

関連論文リスト

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) は、質問回答(QA)のようなタスクにおける応答精度を高めるための有望なアプローチとして登場した。 本稿では,クエリの複雑さに基づいて,LLMの最適戦略を動的に選択できる適応型QAフレームワークを提案する。 オープンドメインのQAデータセットを用いて、複数のクエリの複雑さを網羅し、QAシステムの全体的な効率性と精度を高めることを示す。
  論文  参考訳（メタデータ） (2024-03-21T13:52:30Z)
• RIGA: A Regret-Based Interactive Genetic Algorithm [14.388696798649658]
  そこで本研究では,多目的最適化問題を優先的精度で解くための対話型遺伝的アルゴリズムを提案する。 我々のアルゴリズムはRIGAと呼ばれ、集約関数がパラメータ内で線形であることから、任意の多目的最適化問題に適用できる。 いくつかのパフォーマンス指標(計算時間、最適性とクエリ数のギャップ)に対して、RIGAは最先端のアルゴリズムよりも優れた結果を得る。
  論文  参考訳（メタデータ） (2023-11-10T13:56:15Z)
• On Elimination Strategies for Bandit Fixed-Confidence Identification [12.782423203398094]
  提案手法は, 停止法とサンプリング法の両方において, 除去法を用いて修正可能であることを示す。 我々はこれらの利点を実験的に確認し、除去は適応的手法の計算複雑性を大幅に改善する。
  論文  参考訳（メタデータ） (2022-05-22T21:41:57Z)
• Generalization in the Face of Adaptivity: A Bayesian Perspective [3.0202264016476623]
  適応的に選択されたクエリによるデータサンプルの繰り返し使用は、急速に過度な適合につながる可能性がある。 単純なノイズアンバウンド付加アルゴリズムは、この問題を防ぐのに十分であることがわかった。 提案手法では, 過去のクエリに対する応答にデータサンプルに関する情報がどの程度エンコードされたか, ベイズ因子と新しいクエリの共分散から適応性の害が生じることを示す。
  論文  参考訳（メタデータ） (2021-06-20T22:06:44Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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