Caching and learning algorithms

[Lucie Matušová]

Hi there,

I am working on my diploma thesis with the title Automatic Construction of Checking Circuits Based on Finite Automata. I would like to use LearnLib connected with ModelSim simulator in order to infer a VHDL design. 

I have been using the former closed-source version of LearnLib for some time. Now, I switched to the open-source which I find more convenient in terms of possible further research on this topic at our faculty.

I would like to ask some questions. I have adjusted example2 (BoundedStringQueue) to my needs. I am working with a simple SUL which I was able to learn with the former Learnlib using ObservationPack and WMethodEquivalenceTest.  When I use caching, the execution finishes with the following exception:

net.automatalib.incremental.ConflictException: Error inserting execute_symbol[0] execute_symbol[0] / 1 1: Incompatible output symbols: 1 vs 0

at net.automatalib.incremental.mealy.IncrementalMealyBuilder.insert(IncrementalMealyBuilder.java:197)

at de.learnlib.cache.sul.SULCache.reset(SULCache.java:28)

at de.learnlib.oracles.SULOracle.answerQuery(SULOracle.java:39)

at de.learnlib.oracles.SULOracle.answerQuery(SULOracle.java:29)

at de.learnlib.oracles.MQUtil.answerQueries(MQUtil.java:51)

at de.learnlib.oracles.AbstractSingleQueryOracle.processQueries(AbstractSingleQueryOracle.java:35)

at de.learnlib.algorithms.lstargeneric.table.ObservationTable.initialize(ObservationTable.java:145)

at de.learnlib.algorithms.lstargeneric.AbstractLStar.startLearning(AbstractLStar.java:74)

at de.learnlib.experiments.Experiment$ExperimentImpl.run(Experiment.java:75)

at de.learnlib.experiments.Experiment.run(Experiment.java:128)

at diplomka.example.EasyLearner.main(EasyLearner.java:144)

I tried to run the learning without caching (by setting mqOracle to SUL<...> sul). It has been running for more than an hour and gave no result so I shut the execution down. Former version inferred the model within 30 seconds. What am I doing wrong? Can you please give me some tips how to set the learning?

Another problem I am dealing with is, I cannot construct any other learning algorithm than ExtensibleLStarMealy. For instance, I found MealyDHC class in the API, but I am not able to import de.learnlib.algorithms.dhc. I am using NetBeans and I have created the maven project in command prompt (LearnLib version 0.9.1). I am a little confused with git/API and maven source code versions. How accurate is the API and does it somehow correspond with the source maven is using?

Regards,

Lucie

[Malte Isberner]

Dear Lucie,

thanks for your interest in LearnLib. Could you maybe provide us with some more detailed information on what your setup looks like? Maybe you can paste it in a Gist (https://gist.github.com) or so.

Regarding your questions: Assuming that the reset in your SUL is configured correctly, the cache problem is most likely due to a bug that exists in versions up to 0.9.1-ase2013-tutorial. Try changing the LearnLib version to 0.9.1-ase2013-tutorial-r1 (or you develop against the latest development snapshot 0.10.0-SNAPSHOT, which however comes with some API changes and is not yet stable version - we plan to release version 0.10.0 within the next two weeks. On the other hand, we can quickly react on user input - such as through this list). Below I will paste instructions on how to easily do this.

Regarding the different running times between the old and new LearnLib: the meaning of the integer parameter in the WMethod equivalence test has changed. In the old LearnLib, it was called "maxSize", and referred to the maximum expected size of the automaton. This means that if the hypothesis had at least maxSize states, the W-method could never find a counterexample.

In the new LearnLib, this has been changed; the parameter is now named "maxDepth" and refers to how deeply the W-method "looks" into the future. This makes the W-method adaptive to growing model sizes. As the test set of the W-method grows exponentially with the depth (formerly, depth = max(maxSize - hypothesis.size(), 0)), this different notions can have quite a dramatic impact.

Regarding other learning algorithms etc.: You probably followed the Wiki description on setting up a new LearnLib project using the "typical" archetype, which does not contain the DHC algorithm. You could add this Maven module through your IDE (not sure how this is done in NetBeans), by editing your pom.xml, or by switching to the complete archetype.

To do so, execute the following command on the command line in the directory which contains your pom.xml:

mvn archetype:generate -DarchetypeGroupId=de.learnlib.archetypes -DarchetypeArtifactId=complete -DarchetypeVersion=0.9.1-ase2013-tutorial-r1 -DarchetypeCatalog=remote

This will a) switch to the complete artifact (i.e., add dependencies to learnlib-dhc and so on), and b) change the LearnLib version to 0.9.1-ase2013-tutorial-r1


Hope that helps,
Malte

[Lucie Matušová]

Hi Malte,

I have switched to ase2013-tutorial release. And as you pointed out, the bug was in the reset of my SUL :)

To have a clear vision, I would like to ask about learning algorithms, equivalence test aproximation algorithms and their implementations. 

So far, I have tried ExtensibleLStarMealy, MealyDHC and ClassicLStarMealy. I have also checked BaselineLStarOracle and ExtensibleLStarDFA but they do not fit my needs as their oracles expect yes/no answers. The rest are abstract classes (ExtensibleAutomatonLStar, AbstractAutomatonLStar, AbstractLStar). I am using RandomWalkEQOracle.

On the LearnLib websites in Features section, there are listed four learning algorithms and some equivalence test aproximation algorithms. Can you tel me which classes implement which algorithms at the moment?

You can find my current experiments here https://github.com/Fergiinka/checkers-learnlib.

Thank you for your kind help!

Lucy

[Andreas Abel]

Hi,

I'm using the jar-version of 0.9.1-ase2013-tutorial-r1 (learnlib-0.9.1-ase2013-tutorial-r1-dependencies-bundle.jar). However, I occasionally get similar errors:

Exception in thread "main" net.automatalib.incremental.ConflictException: Error inserting 2 0 0 0 1 1 2 1 0 2 2 3 2 2 3 1 0 0 0 0 0 / 1 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0: Incompatible output symbols: 0 vs 1
    at net.automatalib.incremental.mealy.IncrementalMealyBuilder.insert(IncrementalMealyBuilder.java:181)
    at de.learnlib.cache.mealy.MealyCacheOracle.postProcess(MealyCacheOracle.java:157)
    at de.learnlib.cache.mealy.MealyCacheOracle.processQueries(MealyCacheOracle.java:149)
    at de.learnlib.algorithms.lstargeneric.table.ObservationTable.toShortPrefixes(ObservationTable.java:296)
    at de.learnlib.algorithms.lstargeneric.AbstractLStar.completeConsistentTable(AbstractLStar.java:105)
    at de.learnlib.algorithms.lstargeneric.ExtensibleAutomatonLStar.doRefineHypothesis(ExtensibleAutomatonLStar.java:56)
    at de.learnlib.algorithms.lstargeneric.AbstractLStar.refineHypothesis(AbstractLStar.java:86)
    at de.uni_saarland.romm.MealySerialRightTest.runLearnlib(MealySerialRightTest.java:337)
    at de.uni_saarland.romm.MealySerialRightTest.RandomTest(MealySerialRightTest.java:175)
    at de.uni_saarland.romm.MealySerialRightTest.main(MealySerialRightTest.java:50)

My setup is shown here (MealyMachine<T> is a type of my system): https://gist.github.com/anonymous/1959d0a90d7bab5721c8
What could be the reason for this problem?

And another question: Are there any jar-versions of newer releases available for download anywhere?

Regards,

Andreas

[Mark Janssen]

New jar files are available from Maven Central and https://github.com/LearnLib/learnlib/releases.

I'm also seeing occasional reproducible ConflictExceptions with the MealyCacheOracle in version 0.12, so it looks like this will needs some investigation.