論文の概要: Active Learning of Mealy Machines with Timers

• arxiv url: http://arxiv.org/abs/2403.02019v1
• Date: Mon, 4 Mar 2024 13:20:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-06 18:49:15.411176
• Title: Active Learning of Mealy Machines with Timers
• Title（参考訳）: タイマーを用いた機械の能動的学習
• Authors: V\'eronique Bruy\`ere, Bharat Garhewal, Guillermo A. P\'erez, Ga\"etan Staquet, Frits W. Vaandrager
• Abstract要約: タイマーを用いた一般機械の問合せ学習のための最初のアルゴリズムを提案する。 我々のアルゴリズムはVaandragerらのL#アルゴリズムを時間設定に拡張したものである。 Rustで書かれたプロトタイプ実装の実験は、我々のアルゴリズムがリアルなベンチマークを効率的に学習できることを示しています。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present the first algorithm for query learning of a general class of Mealy machines with timers (MMTs) in a black-box context. Our algorithm is an extension of the L# algorithm of Vaandrager et al. to a timed setting. Like the algorithm for learning timed automata proposed by Waga, our algorithm is inspired by ideas of Maler & Pnueli. Based on the elementary languages of, both Waga's and our algorithm use symbolic queries, which are then implemented using finitely many concrete queries. However, whereas Waga needs exponentially many concrete queries to implement a single symbolic query, we only need a polynomial number. This is because in order to learn a timed automaton, a learner needs to determine the exact guard and reset for each transition (out of exponentially many possibilities), whereas for learning an MMT a learner only needs to figure out which of the preceding transitions caused a timeout. As shown in our previous work, this can be done efficiently for a subclass of MMTs that are race-avoiding: if a timeout is caused by a preceding input then a slight change in the timing of this input will induce a corresponding change in the timing of the timeout ("wiggling"). Experiments with a prototype implementation, written in Rust, show that our algorithm is able to efficiently learn realistic benchmarks.
• Abstract（参考訳）: ブラックボックスコンテキストにおけるタイマー付きMealyマシンの一般的なクラス(MMT)を問合せ学習するための最初のアルゴリズムを提案する。 我々のアルゴリズムは、vaandragerらのl#アルゴリズムをタイムド設定に拡張したものである。 waga が提案した時間的オートマトン学習アルゴリズムと同様に,本アルゴリズムは maler と pnueli のアイデアに触発されたものである。 基本言語に基づいて,wagaとアルゴリズムはともにシンボリッククエリを使用し,有限個の具体的なクエリを用いて実装する。 しかしながら、wagaは単一のシンボリッククエリを実装するために指数関数的に多くの具体的なクエリを必要とするが、多項式数だけが必要である。 これは、時間付きオートマトンを学習するためには、学習者が各遷移の正確なガードとリセット(指数関数的に多くの可能性から)を決定する必要があるのに対し、MMTを学ぶためには、学習者は前回の遷移のどれがタイムアウトを引き起こしたかを知る必要があるからである。 我々の以前の研究で示されているように、これは競合回避であるmmtのサブクラスに対して効率的に行うことができる:もし前回の入力によってタイムアウトが発生すると、この入力のタイミングがわずかに変化すれば、タイムアウトのタイミングに対応する変化(ウィグリング)が引き起こされる。 Rustで書かれたプロトタイプ実装の実験は、我々のアルゴリズムがリアルなベンチマークを効率的に学習できることを示しています。

関連論文リスト

• CASET: Complexity Analysis using Simple Execution Traces for CS* submissions [0.0]
  CS1 や CS2 コースで学生の提出を自動アップグレードする最も一般的な方法は、事前に定義されたテストスイートに対して実行し、結果と参照結果を比較することである。 この手法は、解の正しさが、結果を得るために使われるアルゴリズムのような単純な出力を超えると利用できない。 動的トレースと教師なし機械学習を用いてアルゴリズムの時間的複雑さを解析する新しいツールCASETを提案する。
  論文  参考訳（メタデータ） (2024-10-20T15:29:50Z)
• The CLRS-Text Algorithmic Reasoning Language Benchmark [48.45201665463275]
  CLRS-TextはCLRSベンチマークのテキストバージョンである。 CLRS-Textは、30の多様な、挑戦的なアルゴリズムタスクのためのトレースデータを手続き的に生成することができる。 このベンチマークでは、様々なLMをジェネラリストエグゼクタとして微調整し評価する。
  論文  参考訳（メタデータ） (2024-06-06T16:29:25Z)
• Beryllium: Neural Search for Algorithm Implementations [14.11934122454653]
  我々は,p言語と命名された新しい言語を設計し,p言語のための静的解析器を設計し,アルゴリズム記述から情報を自動的に抽出する。 我々は,p言語(p-code)とソースコードの出力を自己教師付き機械学習手法を用いて共通ベクトル空間に埋め込んだ。 Berylliumは、CとJavaの両方で最先端のコード検索ツールを著しく上回った。
  論文  参考訳（メタデータ） (2023-05-25T03:49:36Z)
• 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)
• The CLRS Algorithmic Reasoning Benchmark [28.789225199559834]
  アルゴリズムの学習表現は機械学習の新たな領域であり、ニューラルネットワークから古典的なアルゴリズムで概念をブリッジしようとしている。 本稿では,従来のアルゴリズムを包括するCLRS Algorithmic Reasoning Benchmarkを提案する。 我々のベンチマークは、ソート、探索、動的プログラミング、グラフアルゴリズム、文字列アルゴリズム、幾何アルゴリズムなど、様々なアルゴリズムの推論手順にまたがっている。
  論文  参考訳（メタデータ） (2022-05-31T09:56:44Z)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。 実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
  論文  参考訳（メタデータ） (2021-09-14T20:52:55Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Rethinking Few-Shot Image Classification: a Good Embedding Is All You Need? [72.00712736992618]
  メタトレーニングセット上で教師付きあるいは自己教師型表現を学習する単純なベースラインが、最先端の数ショット学習方法より優れていることを示す。 追加の増量は自己蒸留によって達成できる。 我々は,この発見が,画像分類ベンチマークとメタ学習アルゴリズムの役割を再考する動機となっていると考えている。
  論文  参考訳（メタデータ） (2020-03-25T17:58:42Z)
• Guidelines for enhancing data locality in selected machine learning algorithms [0.0]
  データ局所性を利用した機械学習アルゴリズムの性能向上手法の1つを分析する。 繰り返しのデータアクセスは、データ移動における冗長性と見なすことができる。 この研究は、結果を直接再利用することによって、これらの冗長性を避けるためのいくつかの機会を特定する。
  論文  参考訳（メタデータ） (2020-01-09T14:16:40Z)

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

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