Serializing learning data structures

[Jaxan]

Hi all,

Sometimes during learning, the setup may crash, or it is run on a server which has to reboot. In these cases we have to rerun the whole learning algorithm. It may take a long time to come back to the hypothesis we had before the crash. We might reuse a bit from the previous hypothesis (it can act like a cache and we can find counter examples with it), but the learning algorithm will still pose queries from start.

Is it possible to serialize the state of the learning algorithm?

If not, what can I do to improve the situation? I think for L*-based algorithms, it shouldn't be too hard (just (de)serialize the observation table).

[praseodym]

It might be possible to store the observation table in something like Redis as well.

[juangamnik]

There is a whole body of work available on this topic (although it has been used for more than "just reattaching"):

http://dl.acm.org/citation.cfm?id=2465469
http://link.springer.com/article/10.1007/s10009-014-0321-6

AFAIK there is no ready-to-use code in the learnlib for serializing/deserializing the data structures, in order to "reattach" to a given learn experiment.

[Jaxan]

Thanks for your input.

I think it should be a matter of separating the data structures and the algorithms cleanly, so that one can use the Serializable interfaces from Java (or do more fancy things, like redis), this way the serialization comes for free. For the L*-like algorithms this should be relatively easy, as the data structure is just a table (maybe together with a list for the prefixes and suffixes). For TTT I'm not familiar enough with the internals to say what is needed.

Looking around a bit, I see there is some functionality for observation tables. There are writers for the tables. The only reader currently is one which only reads suffixes (I do not know the use case for this). So definitely not enough to reattach an experiment.

@juangamnik : I am not so much interested in such applications. Just reattaching in a simple way should be a feature of LearnLib. And I am fine if this feature is a bit restrictive (for example, LearnLib may assume the alphabet did not change, it may assume the membership oracle is consistent with the table, it may assume the same settings are used...).

[juangamnik]

A first step might be to use the hypothesis (which is already trivially serializable) and rebuild the table from it (for L* at least). In our (more complex scenario) the behavior of the SUL might have changed between the learn processes, so that we had to reevaluate, but could at least save EQs.

Perhaps a special form of "serializable learn algo" (via an additional
Interface) could be introduced in learnlib, so that each algo developer can decide, whether it should be serializable or not (I think it won't be of same complexity to implement this for all algos).

[Jaxan]

@juangamnik : That does not work (even in the case the SUL stays the same). If the hypothesis is wrong, one can construct a table which is inconsistent with the oracle from the hypothesis. The best thing you can do from a hypothesis is creating prefixes and suffixes, and the refill the table (with membership queries).

[juangamnik]

Therefore you should reevaluate it. You save all EQs still.

But, you can use the spanning tree for S and IIRC SA should be usable too since the hypothesis is complete and closed. The hypothesis cannot be completely wrong for the found states and the access sequences. Of course you cannot rebuild the "same" OT with Suffixes. But I didn't double check this. But for sure the really time consuming task (EQs) that have already been done, can be saved.

[Jaxan]

I don't agree that EQs are the most time consuming, posing membership queries are very time consuming as well. So I want to store all the information which is learnt already! Just re-using prefixes and suffixes I think is insufficient (although maybe a nice first step).

To give a bit of context, the experiments were performed for the RERS challenge, which involves mealy machines with more than 20'000 states (this is how far we were able to learn), which took me a week to learn, most of the time was actually spent on membership queries (we have very efficient testers for EQs). So when the experiment crashed, I was lost, as I had to restart everything. It will take a week to come to more or less the same stage of learning, simply because of the big number (and size) of membership queries, even if we know the prefixes and suffixes!

The testers we use are described in #40. IIRC (I lost the exact figures due to the crash) the ratio of membership traces vs testing traces was around 2:1. So many more membership queries.

[juangamnik]

In most cases EQs are emulated by many MQs (Random Walk, W(P)-method, ...). Of course it is the problem then, that the MQs are "slow", but still in L* (and all the other algos) the first phase is at most O(n^3) IIRC and the EQs are undecidable as the underlying problem is. This is the inherent complexity. Of course there are EQs around which are quite efficient in the average case, but...

But TL;DR, if your scenario is, that you need serialization of the data structures, then I won't say "it isn't, you're holding it wrong", I'm not Steve Jobs 🤓. I just hoped I could give you a hint, which helps you now, without having to wait for a new feature in the LearnLib.

[mtf90]

I think the previous discussions neglected a quite important point: the serializability of user-provided input. While it is conceptionally easy to e.g. serialize an observation table or a hypothesis, it may technically be quite a challenge, because we have no information about the serializability of the input alphabet (or rather the input symbols). Some symbols may e.g. execute remote code on a server in an open transaction, etc. which are simply not reasonable to serialize. (... and I dislike the idea to force serializability upon the users)

I would even go this far, and say we'd have to deep-copy the essential datastructures (hypothesis, observation table, discrimination tree, you name it) of the learning algorithms to use a guaranteed serializable datatype. I'm thinking of something along the lines of the FullIntAbstraction interface for automata, etc. We'd still have problems with MealyMachines though, because again, we have no guarantees about the serializability of an output symbol. And since there is often no need to provide an explicit output alphabet, we cannot simply abstract it by using e.g. the symbol position within in the alphabet.

I think it boils down to every learning algorithm having to provide its own serializable "snapshot" type, which contains all the necessary information. As a draft I thought of something along the lines of:

public interface ResumableLearningAlgorithm<M extends Serializable, O> {

	M suspend(ToIntFunction<O> outputAbstraction);
	void resume(M data, IntFunction<O> outputMapper);

	interface DFALearner<M extends Serializable> extends ResumableLearningAlgorithm<M, Boolean> {
		default M suspend() {
			return suspend((b) -> b ? 0 : 1);
		}
		default void resume(M data) {
			resume(data, (val) -> val == 0);
		}
	}

	interface MealyLearner<M extends Serializable, O> extends ResumableLearningAlgorithm<M, O>{}
}

where e.g. the BaselineLStar binds M to something like "BaselineLStarContext" which essentially stores a ObservationTable<Integer>.

[mtf90]

Dear all,

in the past weeks/months we have added the ResumableLearner interface and made most of the learning algorithms implement it. It allows you to extract the state of the learning process after each successful refinement step and resume from that snapshot (see the unit tests for an example).

Any feedback about this API/functionality is appreciated. Otherwise I will close this ticket in the near future.

[mtf90]

Since there has been no feedback for about a month, I will close this ticket, as I see the requested functionality as implemented.