Active Learning of Mealy Machines with Timers
- URL: http://arxiv.org/abs/2403.02019v1
- Date: Mon, 4 Mar 2024 13:20:52 GMT
- Title: Active Learning of Mealy Machines with Timers
- Authors: V\'eronique Bruy\`ere, Bharat Garhewal, Guillermo A. P\'erez, Ga\"etan
Staquet, Frits W. Vaandrager
- Abstract summary: We present the first algorithm for query learning of a general class of Mealy machines with timers (MMTs)
Our algorithm is an extension of the L# algorithm of Vaandrager et al. to a timed setting.
Experiments with a prototype implementation, written in Rust, show that our algorithm is able to efficiently learn realistic benchmarks.
- Score: 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.
Related papers
- Batch Active Learning of Reward Functions from Human Preferences [33.39413552270375]
Preference-based learning enables reliable labeling by querying users with preference questions.
Active querying methods are commonly employed in preference-based learning to generate more informative data.
We develop a set of novel algorithms that enable efficient learning of reward functions using as few data samples as possible.
arXiv Detail & Related papers (2024-02-24T08:07:48Z) - Learning the Positions in CountSketch [49.57951567374372]
We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem.
In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
arXiv Detail & Related papers (2023-06-11T07:28:35Z) - 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) - Algorithms for Weighted Pushdown Automata [118.67634716230025]
Weighted pushdown automata (WPDAs) are at the core of many natural language processing tasks.
We develop novel algorithms that operate directly on WPDAs.
arXiv Detail & Related papers (2022-10-13T10:21:31Z) - 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) - An Algorithm for Fast Supervised Learning in Variational Circuits
through Simultaneous Processing of Multiple Samples [0.0]
We propose a novel algorithm for fast training of variational classifiers by processing multiple samples parallelly.
The presented algorithm utilizes qRAM and other quantum circuits in the forward pass.
Although we discuss only binary classification in the paper, the algorithm can be easily generalized to multi-class classification.
arXiv Detail & Related papers (2020-11-29T06:14:41Z) - Siamese Meta-Learning and Algorithm Selection with
'Algorithm-Performance Personas' [Proposal] [0.0]
Key to algorithm selection via meta-learning is often the (meta) features, which sometimes do not provide enough information to train a meta-learner effectively.
We propose a Siamese Neural Network architecture for automated algorithm selection that focuses more on 'alike performing' instances than meta-features.
arXiv Detail & Related papers (2020-06-22T15:12:21Z) - Adaptive Teaching of Temporal Logic Formulas to Learners with
Preferences [44.63937003271641]
We investigate machine teaching for temporal logic formulas.
An exhaustive search even for a myopic solution takes exponential time.
We propose an efficient approach for teaching parametric linear temporal logic formulas.
arXiv Detail & Related papers (2020-01-27T18:22:53Z)
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.