Learning given an initial hypothesis

[omarzd]

I would like to inquire about a certain feature, to start learning given an initial hypothesis. This can be implemented in the LearnLib adapter/client/test driver/SuL wrapper (whichever is the term) such that it will simulate the real SuL by replying to queries according to the initial hypothesis. However, I want it implemented in LearnLib itself and would like to know what that requires. The idea is that on the first iteration, instead of building a hypothesis using membership queries, LL would use the given hypothesis and start doing equivalence queries and continue normally from there. Of course the given hypothesis must match the given input alphabet plus other prerequisites. The advantage of this can be seen in two cases. The first case is simply resuming learning from a previously reached hypothesis instead of from the very beginning. This is helpful in case for some reason the learning process is halted. The second case is more complex. Suppose we can represent some knowledge about the SuL as a hypothesis. We want to introduce that hypothesis to LearnLib as a conjecture that it will treat the same way, i.e. start by testing it using equivalence queries.

In short, I would like to know how easy it is to implement a feature in LearnLib where it starts learning given a hypothesis.

Thank you

[mtf90]

Hm, I think implementing this requires more work than expected.

For a lot of algorithms, the internal hypothesis is closely connected to different datastructures. E.g. for discrimination-tree based learners, the leaves of the DT reference hypothesis states. So in order to start from a certain hypothesis, you would have to supply the corresponding DT as well. This however involves determining (or supplying) the correct discriminators/distinguishing suffixes to (re-)construct said DT.

Furthermore, the internal model is only a hypothesis, so there are behaviors/runs that differ from the true system. Normally, you only know the true system behavior for runs along the spanning tree edges (e.g. the upper half of the ObservationTable) -- every other transition is only behavioral correct up to the currently discovered distinguishing suffixes. So you would also have to provide this differentiation between information.

If you're just interested in pausing and resuming the learning process, you can use the ResumableLearner functionality, which has been introduced in version 0.13. This allows you to snapshot the current state of the learning process (hypothesis + relevant internal data) in a serializable blob.

You second point sounds like, you not only want to use previous information to potentially cache membership queries but also equivalence queries. If you have initial knowledge about the system, you can also extract relevant traces and use them in e.g. a SampleSetEQOracle to perform equivalence checks.

[omarzd]

Thanks for the thorough answer. Points:

1. I have to provide the discrimination tree, which means providing distinguishing suffixes.
2. I need to provide the differentiation between upper part (spanning tree edges) and lower part (distinguishing suffixes) of the observation table.
3. I shall try out ResumableLearner.
4. I can guide the equivalence oracle to use certain traces using a SampleSetEQOracle.

Great. OK. Now I haven't thought about how I can transform a hypothesis from a DFA (or a Mealy machine) to an observation table, but I assumed it was doable only because the opposite transofrmation is. You're saying that such transformation is however not doable.

Point 2 seems to me the same as point 1. If I do provide distinguishing suffixes, then I will certainly be able to provide the distinction between upper and lower parts of the observation table. But I'm not familiar with the concept of spanning tree in this context. But a spanning tree is not unique, which means we can't extract the exact upper part of the observation table. I will investigate this further. Mainly the question is how would I translate knowledge about a system into an observation table.

[mtf90]

What I meant by 'spanning tree edges' was essentially the information about the upper part of an observation table. Since the row labels are a prefix-closed set of representatives of the equivalence classes, they form a spanning tree of your hypothesis. DT-based learners need the same information but encode it (at least in Learnlib) directly in the hypothesis. To make things easier, you can just think of (hypothesis + DT) as a partially filled OT.

Your last point perfectly describes the issue: In an ObservationTable you have all the knowledge to construct a hypothesis. However, once you have constructed the hypothesis, you cannot reliably reverse this construction, because there exist multiple OTs that could have resulted in the hypothesis. You need information about the rows (access sequences) and columns (distinguishing suffixes) to extract the "original" knowledge about your hypothesis.

Essentially, you would have to provide the complete OT for OT-based learners and a hypothesis + DT for DT-based learners. From an implementation point of view, you would have to implement specialized initialization methods for every learning algorithm.

I think it is cleaner to wrap any initial knowledge you have about your system in membership-/equivalence-oracles and use these defined interaction points to guide the learning process. This allows for an approach, that

• works the same for every learning algorithm,
• without having to change any of them.

[mtf90]

@omarzd any progress on this? Would you still regard this as an issue of LearnLib?

[omarzd]

@mtf90 No. I decided to go with your suggestion of guiding the learning process using my own oracle wrapper.

Another idea I got out of this is I can make a higher-level component that acts as a director and---instead of guiding the learning process of a single learning experiment---it would set up multiple experiments with different alphabets (perhaps different levels of abstraction of the same alphabet) with the goal of learning several models that can somehow be combined together afterwards.

Thank you.