論文の概要: On the Sample Complexity of Active Learning with Membership Queries

• arxiv url: http://arxiv.org/abs/2609.27241v1
• Date: Wed, 23 Sep 2026 02:19:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 00:05:17.839554
• Title: On the Sample Complexity of Active Learning with Membership Queries
• Title（参考訳）: メンバーシップクエリによるアクティブラーニングのサンプル複雑さについて
• Abstract要約: この研究は、アクティブラーニングにおける根本的な問題を再考する。任意のクエリを合成する能力は、どの程度強力か? プールをベースとしたアクティブラーニングと比較すると,このクエリ能力の変化が,統計的学習の難しさを劇的に変える可能性がある。 特に、プールベースの設定で本質的に学習が遅く、サンプル数でのエラー減衰のみを達成する仮説クラスは、合成されたクエリが許容されれば指数関数的に学習可能となる。
• 参考スコア（独自算出の注目度）: 7.473832609768352
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, we find that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular, some hypothesis classes that are inherently slow to learn in the pool-based setting, achieving only polynomial error decay in the number of samples, become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its complexity. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.
• Abstract（参考訳）: この研究は、アクティブラーニングにおける根本的な問題を再考する。任意のクエリを合成する能力は、どの程度強力か? プールベースのアクティブラーニングと比較して、学習者は与えられたラベルのないプールからのみクエリを選択するが、この一見穏やかなクエリ能力の変化は統計的ラーニングの難しさを劇的に変える可能性がある。 特に、プールベースの設定で本質的に学習が遅く、サンプル数で多項式誤差しか達成できない仮説クラスは、合成されたクエリが許容されれば指数関数的に学習可能となる。 この顕著なギャップは、メンバーシップクエリ合成が、既存のアクティブラーニング理論によって適切に捉えられず、その複雑さを特徴づけるための新しい分析ツールを要求する、根本的に異なる学習様式を誘導することを示している。 この現象に触発されて、いくつかの十分な条件が開発され、興味深い事例が提示され、仮説クラスが合成されたクエリを通して効率的な学習を認めることの理解に向けた概念的視点が提案される。

関連論文リスト

• Beyond Labels: Information-Efficient Human-in-the-Loop Learning using Ranking and Selection Queries [10.128513811628201]
  我々は、リッチなクエリ型を持つバイナリ分類器を学習するためのHuman-in-the-loopフレームワークを開発した。 次に、リッチなクエリを活用するアクティブな学習アルゴリズムを設計し、インタラクション毎に得られる情報を増やします。 単語感情分類タスクにおけるこのアルゴリズムは、従来のラベルのみのアクティブな学習と比較して学習時間を57%以上削減する。
  論文  参考訳（メタデータ） (2026-02-17T17:14:15Z)
• Probably Approximately Precision and Recall Learning [60.00180898830079]
  機械学習における重要な課題は、一方的なフィードバックの頻度である。 本稿では,確率的近似(PAC)フレームワークを導入し,各入力をラベルの集合にマッピングする仮説を定めている。 我々は、正のデータのみから学習する新しいアルゴリズムを開発し、実現可能な場合において最適なサンプル複雑性を実現する。
  論文  参考訳（メタデータ） (2024-11-20T04:21:07Z)
• 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)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。 これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。 提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
  論文  参考訳（メタデータ） (2023-04-14T11:35:35Z)

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

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