2021/04/23 by Raphaël Berthon, Adrien Boiret, Berthon, Raphaël +5 · 1 citation
Computer Science · #Machine Learning and Algorithms #Algorithms and Data Compression #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2104.11758
Active learning is a setting in which a student queries a teacher, through\nmembership and equivalence queries, in order to learn a language. Performance\non these algorithms is often measured in the number of queries required to\nlearn a target, with an emphasis on costly equivalence queries. In graybox\nlearning, the learning process is accelerated by foreknowledge of some\ninformation on the target. Here, we consider graybox active learning of\nsubsequential string transducers, where a regular overapproximation of the\ndomain is known by the student. We show that there exists an algorithm using\nstring equation solvers that uses this knowledge to learn subsequential string\ntransducers with a better guarantee on the required number of equivalence\nqueries than classical active learning.\n