Replies: 1 comment
-
The "minimally adequate teacher" (MAT) framework conceptualizes two forms of interactions between a learner and a system under learning: membership queries (for querying behavioral properties) and equivalence queries (for testing equivalence). You are right that in practice, these are often implemented via testing, i.e., simply executing (membership) queries on the SUL and using test-words to answer (or rather approximate) equivalence queries. Often (and especially in terms of LearnLib architecture) the SUL only describes the actual software/hardware system that provides the input -> output function. Answering the above queries is often abstracted from via so-called membership query oracles and equivalence query oracles. Whereas MQOs can be implemented rather straight-forward, EQOs are the main challenge in practice. Here, many techniques from model-based testing (especially conformance testing) often yield satisfying results. You may have a look at this paper (or the book in general) to get some starting points. However, in general, the black-box equivalence problem is impossible to solve, so without any further assumptions, AAL is neither correct nor complete. As for your remark that AAL implicitly assumes that the SUL can be described by a DFA: It depends on the learning algorithm. There are many extensions to the early learning algorithms that deal with more expressive automaton model types (Mealy machines, push-down automata, register automata, etc.). But you are right in that each learning algorithm has a specific expectation of the "complexity class" of the SUL. If you take a DFA-learner to learn a push-down system, the DFA would require an infinite amount of states / you could find an infinite amount of counterexamples. However, you could still look at approximative scenarios which at some point simply stop providing counterexamples to terminate the learning process. |
Beta Was this translation helpful? Give feedback.
-
The overall complexity of the learning algorithm depends on the implementations of the teacher, i.e. how long it takes for the membership queries and equivalencequeries to be calculated
I am not sure if I have understood it correctly but I assume a SUL (System under Learning) is the objects that implements the teacher, i.e. defines how equivalence querries and membershipqueries are realized. And using Active Learning would only make sense if you dont know yet how or whether or not the target system can be described as a DFA or not.
I assume one example of how membershipqueries are realized (where the SUL is not simply explicitly the target DFA) if you have access to a system (a function/program that accepts a word as an input and returns 1 or 0) of which you assume can be described as a DFA (for example prime number checker would not be a DFA), and the membership query is answered by entering the input into the system and then receiving the output. A equivalence query could be realized by comparing the hypothesis, with the target-system by using again membership queries on a certain set of test-words (either randomly generated with a certain length, or all possible words to a certain length) and then a counterexample would be given if there is a divergence in the behaviour, otherwise the equivalence query would be declared as positive.
I cannot find any papers that deal with different implementations of the teacher, especialy a teacher that can gurantee correctness. Could you maybe give me more ressources that deal with this topic?
Beta Was this translation helpful? Give feedback.
All reactions