Automata Learning

Automata learning is a field in machine learning that consists in learning an automaton. There are two main frameworks to do that:

1. Active learning, which makes use of an oracle model (that can be seen as a black box) that acts as the teacher.
2. Passive learning, where the automaton is learned by only using a dataset of good and bad examples. The goal is to learn the smallest automata that accepts the good examples and rejects the bad examples;

Since multi-class classifiers can be reduced into several binary classifiers, most of the automata learning methods focus their reasoning with binary classifiers (called network-acceptors in [@xuExtractingAutomataNeural2021]).

Active learning framework

The main framework to make this possible (as stated in [@xuExtractingAutomataNeural2021]) is Active learning, proposed by [@angluinLearningRegularSets1987].

L-star Algorithm

A famous active learning algorithm is called $L^{\ast }$ [@angluinLearningRegularSets1987], and it shows how a finite automata that is able to recognize Regular Sets can be learned precisely from a minimally adequate teacher (MAT), which is an oracle that is capable of answering the so-called membership and equivalence queries, which are described as follows:

• Membership queries (MQs): the learner asks whether a given word is accepted by the automaton or not, and the teacher answers with the result
• Equivalence queries (EQs): the learner asks whether a given hypothesis automaton $\mathcal{H}$ is equal to the automaton model $\mathcal{M}$ currently held by the teacher. If the answer is no, then the teacher supplies a counterexample, which is a word accepted by $\mathcal{H}$ but not by $\mathcal{M}$.

The learner asks a sequence of MQs to the teacher, and after a sufficient number of queries, it builds an hypothesis automaton $\mathcal{H}$, and sends an EQ. If the teacher answers yes, then the hypothesis is returned as the final result, otherwise more MQs are done in order to fine-tune the hypothesis model.

Since the $L^{\ast }$ algorithm is able to learn Regular Sets, the algorithm falls into the category of Regular Inference algorithms.

Another example of regular inference algorithm is the pPNI algorithm proposed in [@joseoncinaInferringRegularLanguages2014].

RPNI - Regular Pattern Non-deterministic Identification

See RPNI - Regular Pattern Non-deterministic Identification

Passive Learning Framework

Citing [@xuExtractingAutomataNeural2021]:

Xu et al. - Extracting automata from neural networks using active learning (p.5) The MAT framework is shown in Fig. 1. Initially, the learner knows the static interface of the SUL, that is, the sets of input (i.e., multi-dimensional array for neural networks) and output (i.e., yes or no for recognizers). Then the learner starts to ask a sequence of membership queries (MQs) and receives the corresponding responses from the teacher. After a “sufficient” number of queries, the learner builds a hypothesis H from the obtained information, and then sends an equivalence query (EQ). If the teacher answers yes, then the hypothesis H is returned. Otherwise, the learner refines the information with the returned counterexample, and continues on querying. Passive learning Different from active learning, passive learning constructs automata from sets of examples directly. Many approaches in grammatical inference can be described as passive learning. In the paper, we consider the polynomial-time RPNI algorithms provided in the library LearnLib (Howar et al., 2012). Oncina & Garca (1992) proposed the Regular Positive and Negative Inference (RPNI) algorithm for DFA learning. RPNI starts with a prefix tree acceptor, a tree-like DFA built from the learning examples by taking all the prefixes of the examples as states, and then greedily creates clusters of states (by merging) in order to come up with an automaton that is always consistent with the examples. Two heuristic strategies can be employed in state merging: Evidence Driven State Merging (EDSM) (Cicchello & Kremer, 2002) and Minimum Description Length (MDL) (Adriaans & Jacobs, 2006).

---

tags: automata machine-learning related: Is it possible to approximate any deep learning opaque model with an automaton?