Active Learning of Mealy Machines with Timers

• URL: http://arxiv.org/abs/2403.02019v2
• Date: Wed, 30 Oct 2024 13:49:15 GMT
• Title: Active Learning of Mealy Machines with Timers
• Authors: Véronique Bruyère, Bharat Garhewal, Guillermo A. Pérez, Gaëtan Staquet, Frits W. Vaandrager,
• Abstract summary: We present the first algorithm for query learning of a class of Mealy machines with timers in a black-box context. Our algorithm is an extension of the L# algorithm of Vaandrager et al. to a timed setting.
• Score: 3.087487671441056
• License:
• Abstract: We present the first algorithm for query learning of a class of Mealy machines with timers in a black-box context. Our algorithm is an extension of the L# algorithm of Vaandrager et al. to a timed setting. We rely on symbolic queries which empower us to reason on untimed executions while learning. Similarly to the algorithm for learning timed automata of Waga, these symbolic queries can be implemented using finitely many concrete queries. Experiments with a prototype implementation, written in Rust, show that our algorithm is able to efficiently learn realistic benchmarks.

Related papers

• CASET: Complexity Analysis using Simple Execution Traces for CS* submissions [0.0]
  The most common method to auto-grade a student's submission in a CS1 or a CS2 course is to run it against a pre-defined test suite and compare the results against reference results. This technique cannot be used if the correctness of the solution goes beyond simple output, such as the algorithm used to obtain the result. We propose CASET, a novel tool to analyze the time complexity of algorithms using dynamic traces and unsupervised machine learning.
  arXiv  Detail & Related papers  (2024-10-20T15:29:50Z)
• The CLRS-Text Algorithmic Reasoning Language Benchmark [48.45201665463275]
  CLRS-Text is a textual version of the CLRS benchmark. CLRS-Text is capable of procedurally generating trace data for thirty diverse, challenging algorithmic tasks. We fine-tune and evaluate various LMs as generalist executors on this benchmark.
  arXiv  Detail & Related papers  (2024-06-06T16:29:25Z)
• Beryllium: Neural Search for Algorithm Implementations [14.11934122454653]
  We design a new language named p-language to specify the algorithms and a static analyzer for the p-language to automatically extract information from the algorithm descriptions. We embedded the output of p-language (p-code) and source code in a common vector space using self-supervised machine learning methods to match algorithm with code without any manual annotation. Beryllium significantly outperformed the state-of-the-art code search tools in both C and Java.
  arXiv  Detail & Related papers  (2023-05-25T03:49:36Z)
• Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
  This paper is concerned with the computational complexity of learning the Hidden Markov Model (HMM) In this paper, we consider an interactive access model, in which the algorithm can query for samples from the conditional distributions of the HMMs. Specifically, we obtain efficient algorithms for learning HMMs in settings where we have query access to the exact conditional probabilities.
  arXiv  Detail & Related papers  (2023-02-28T16:53:41Z)
• Unified Functional Hashing in Automatic Machine Learning [58.77232199682271]
  We show that large efficiency gains can be obtained by employing a fast unified functional hash. Our hash is "functional" in that it identifies equivalent candidates even if they were represented or coded differently. We show dramatic improvements on multiple AutoML domains, including neural architecture search and algorithm discovery.
  arXiv  Detail & Related papers  (2023-02-10T18:50:37Z)
• The CLRS Algorithmic Reasoning Benchmark [28.789225199559834]
  Learning representations of algorithms is an emerging area of machine learning, seeking to bridge concepts from neural networks with classical algorithms. We propose the CLRS Algorithmic Reasoning Benchmark, covering classical algorithms from the Introduction to Algorithms textbook. Our benchmark spans a variety of algorithmic reasoning procedures, including sorting, searching, dynamic programming, graph algorithms, string algorithms and geometric algorithms.
  arXiv  Detail & Related papers  (2022-05-31T09:56:44Z)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  We describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a search procedure to improve this metric. We show that in practice, automated search can find substantial improvements to the initial program.
  arXiv  Detail & Related papers  (2021-09-14T20:52:55Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Rethinking Few-Shot Image Classification: a Good Embedding Is All You Need? [72.00712736992618]
  We show that a simple baseline: learning a supervised or self-supervised representation on the meta-training set, outperforms state-of-the-art few-shot learning methods. An additional boost can be achieved through the use of self-distillation. We believe that our findings motivate a rethinking of few-shot image classification benchmarks and the associated role of meta-learning algorithms.
  arXiv  Detail & Related papers  (2020-03-25T17:58:42Z)
• Guidelines for enhancing data locality in selected machine learning algorithms [0.0]
  We analyze one of the means to increase the performances of machine learning algorithms which is exploiting data locality. Repeated data access can be seen as redundancy in data movement. This work also identifies some of the opportunities for avoiding these redundancies by directly reusing results.
  arXiv  Detail & Related papers  (2020-01-09T14:16:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.