Overview on LearnLib data structures
The LearnLib data structures are modeled along
the basic structure of (active) learning techniques, i.e., following a
learner/teacher model. The basic data structures are defined in the
de.ls5.jlearn.interfaces
package of the core framework.
Basic interfaces
The most important interfaces will be discussed in the following.Learner (JavaDoc)
Instances of classes implementing this interface encapsulate an active
machine learning algorithm, which creates queries to be executed on the target
system and creates a machine model according to the output created in response
to the generated queries. A well known algorithm, e.g., would be Angluin's
L* algorithm, for which LearnLib provides an
implementation implementing the Learner interface.
Oracle (JavaDoc)
This interface encapsulates teacher instances, which take queries generated
by a learner and return output as a response to the queries. An
Oracle can, e.g., be a system adapter or a
filter that answers queries by applying application-specific knowledge or
an abstraction driver that transforms queries from an abstract realm the
learner may use to a concreate realm the target system can understand.
Most oracles allow for creating chains of Oracle
instances, meaning that if an oracle isn't able to process an incoming query
(e.g., if a filter oracle cannot answer the query by itself) it will consult
the next oracle in the chain, forwarding its result.
EquivalenceOracle (JavaDoc)
Instances of EquivalenceOrace are used prove or disprove the correctness
of a learned hypothesis. If a mismatch between the learned model and the
target system has been detected, a counterexample exposing diverging behavior will
be produced, which can be used by the learner to refine the hypothesis when
resuming learning.
In practice, given that real-life target systems provide no means to compare themselves
to a machine model representation, implementations of EquivalenceOrace
will try to find counterexamples by consulting an Oracle instance.
A first learning setup
With the above basic interfaces it is possible to conceive a very simple setup.
In the picture to the right one can see a very high level overview on the
interplay of the interfaces described above. One can see two Oracle
instances, one of them being a system adapter which tethers the actual
target system. Another Oracle instance implements a query filter
which is designed to decrease the amount of queries presented to the target
system via the system adapter. If the filter cannot answer a query with its
internal logic, it will transfer the query to the system adapter for actual
execution on the target system.
The chain of Oracle instances is consulted by both an instance
of the Learner interface and an instance of the
EquivalenceOracle interface. During the learning process the
learner will generate queries to be executed on the target system and
construct a hypothesis. Once a hypothesis is complete the learner will
transfer the hypothesis to an instance of EquivalenceOracle,
asking for a counterexample. In the setup shown the equivalence oracle will
try to disprove the provided hypothesis using a sequence of queries targeted
at the chain of (membership) oracles. In cases where the machine representation
of the target system is already known a direct comparison between the hypothesis
and the machine model can take place instead. This, however, isn't usually
the case with real-life systems.