論文の概要: Automata Learning from Preference and Equivalence Queries

• arxiv url: http://arxiv.org/abs/2308.09301v2
• Date: Tue, 19 Nov 2024 23:57:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-21 16:10:26.106378
• Title: Automata Learning from Preference and Equivalence Queries
• Title（参考訳）: 優先度と等価クエリによるオートマタ学習
• Authors: Eric Hsiung, Joydeep Biswas, Swarat Chaudhuri,
• Abstract要約: 本稿では,能動オートマトン学習問題の新たな変種として,嗜好クエリを用いて有限オートマトンを積極的に学習する手法を提案する。 ReMAPは、クエリの複雑さの最小限の複雑さを、正確な等価クエリの下で正確に推測することが保証されている。 実験により,REMAPを大規模オートマトンにスケールすることは,一貫した教師から正しいオートマトンを学習するのに有効であることが示唆された。
• 参考スコア（独自算出の注目度）: 17.33092604696224
• License:
• Abstract: Active automata learning from membership and equivalence queries is a foundational problem with numerous applications. We propose a novel variant of the active automata learning problem: actively learn finite automata using preference queries -- i.e., queries about the relative position of two sequences in a total order -- instead of membership queries. Our solution is REMAP, a novel algorithm which leverages a symbolic observation table along with unification and constraint solving to navigate a space of symbolic hypotheses (each representing a set of automata), and uses satisfiability-solving to construct a concrete automaton from a symbolic hypothesis. REMAP is guaranteed to correctly infer the minimal automaton with polynomial query complexity under exact equivalence queries, and achieves PAC-identification ($\varepsilon$-approximate, with high probability) of the minimal automaton using sampling-based equivalence queries. Our empirical evaluations of REMAP on the task of learning reward machines for two reinforcement learning domains indicate REMAP scales to large automata and is effective at learning correct automata from consistent teachers, under both exact and sampling-based equivalence queries.
• Abstract（参考訳）: メンバシップと等価クエリからのアクティブオートマトン学習は、多数のアプリケーションにおいて基礎的な問題である。 本稿では,2つの順序の相対的な位置に関するクエリを,メンバシップクエリではなく,嗜好クエリを用いて積極的に学習する,アクティブオートマトン学習問題の新たな変種を提案する。 我々の解法はREMAPであり, シンボル観測表と統一・制約解を用いて, 記号仮説の空間(いずれもオートマトン)をナビゲートし, 満足度解決を用いて, 記号仮説から具体的なオートマトンを構築する新しいアルゴリズムである。 REMAPは、最小オートマトンと多項式クエリの複雑さを正確に推定し、サンプリングベースの等価クエリを用いて最小オートマトンをPAC識別(高い確率で)する。 2つの強化学習領域における報酬機械の学習課題におけるREMAPの実証的評価は、REMAP尺度を大規模オートマトンに拡張し、正確かつサンプリングに基づく等価なクエリに基づいて、一貫した教師から正しいオートマトンを学習するのに有効であることを示している。

関連論文リスト

• Learning Quantitative Automata Modulo Theories [17.33092604696224]
  本稿では,学習者が帰納的推論によって有効なオートマトンを推論する,能動的学習アルゴリズムQUINTICを提案する。 本評価では, 累積, 減算, 積, 量的オートマトンを学習するために, 有理理論を利用する。
  論文  参考訳（メタデータ） (2024-11-15T21:51:14Z)
• LLMs as Probabilistic Minimally Adequate Teachers for DFA Learning [11.037017229299607]
  大規模言語モデル(LLM)におけるインテリジェンス(インテリジェンス)の出現は、オートマチックラーニングへの統合に関する調査にインスピレーションを与えている。 本稿では,pMAT (probabilistic Minimally Adequate Teacher) の定式化について紹介する。 我々は,解答精度を向上し,学習したオートマタの正確性を確保する技術を開発した。
  論文  参考訳（メタデータ） (2024-08-06T07:12:09Z)
• Prompt Optimization with EASE? Efficient Ordering-aware Automated Selection of Exemplars [66.823588073584]
  大規模言語モデル(LLM)は、現実世界のアプリケーションで印象的な機能を示している。 これらの卓越した作品の品質は、パフォーマンスに大きな影響を与えます。 既存の方法は、先行注文がパフォーマンスに与える影響を適切に説明できない。
  論文  参考訳（メタデータ） (2024-05-25T08:23:05Z)
• 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)
• Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
  本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。 本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。 具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-28T16:53:41Z)
• Unified Functional Hashing in Automatic Machine Learning [58.77232199682271]
  高速に統一された関数型ハッシュを用いることで,大きな効率向上が得られることを示す。 私たちのハッシュは"機能的"であり、表現やコードが異なる場合でも同等の候補を識別します。 ニューラルアーキテクチャ検索やアルゴリズム発見など、複数のAutoMLドメインで劇的な改善がなされている。
  論文  参考訳（メタデータ） (2023-02-10T18:50:37Z)
• Induction and Exploitation of Subgoal Automata for Reinforcement Learning [75.55324974788475]
  本稿では,Regressed Learning (RL)タスクにおけるサブゴールの学習と活用のためのISAを提案する。 ISAは、タスクのサブゴールによってエッジがラベル付けされたオートマトンであるサブゴールオートマトンを誘導することで強化学習をインターリーブする。 サブゴールオートマトンはまた、タスクの完了を示す状態と、タスクが成功せずに完了したことを示す状態の2つの特別な状態で構成されている。
  論文  参考訳（メタデータ） (2020-09-08T16:42:55Z)
• Generating Diverse and Consistent QA pairs from Contexts with Information-Maximizing Hierarchical Conditional VAEs [62.71505254770827]
  非構造化テキストを文脈として与えられたQAペアを生成するための条件付き変分オートエンコーダ(HCVAE)を提案する。 我々のモデルは、トレーニングにわずかなデータしか使わず、両方のタスクの全てのベースラインに対して印象的なパフォーマンス向上が得られる。
  論文  参考訳（メタデータ） (2020-05-28T08:26:06Z)

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

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