Question on LStar Algorithm
99 views
Skip to first unread message
Khanh Ho
Jun 11, 2021, 10:12:34 AM6/11/21
to LearnLib Q&A
Hello,
I've started using Learnlib and I'm trying to run LStar Algorithm on my own DFAs, but it's impossible for me to get the correct results.
I took the "Example1.java" file in the "learnlib/examples/src/main/java/de/learnlib/examples/" folder on GitHub and used the .fsm format to deserialize the automata. Each letter in the alphabet is a string, as you can see in my files. I tried to modify the EPLORATION_DEPTH, switch to another EQOracle such that RandomWords or RandomWMethod but either it couldn't find a counter-example or it generated an automaton with a unique state.
I couldn't find the issue, maybe my automata are too big? They have always a maximum of 30 states and my alphabet size is also about 30.
Could you help me out, please?
Kind regards,
Khanh.
P/s: I've attached here the java file with the main (which is based on your "Example1.java") and some of my .fsm files.
Markus Frohme
Jun 11, 2021, 12:43:51 PM6/11/21
to Khanh Ho, LearnLib Q&A
Dear Khanh,
the "problem" with your automata is that they have a very linear structure. You basically have a sequence of states that you need to traverse in a specific order for detecting the only accepting (resp. rejecting) state.
Testing-based equivalence checks usually take the current hypothesis as ground truth and verify its transitions (+ a potential look-ahead). However, if you start with your initial hypothesis (which contains only a single state) and explore, e.g., 4 steps in the future, you will never be able to detect a state that is 12 steps away. This is why the equivalence oracle does not detect any counterexamples and you are left with your initial hypothesis.
Increasing the exploration depth enough will eventually resolve this problem. However, the number of queries grows exponentially with the exploration depth, as basically all possible input sequences are used for exploring the system (so a (number of input symbols)^(exploration depth) blow-up) and the learning will take a lot longer.
If this is an issue, you can also think about using an equivalence oracle chain that combines difference equivalence heurists. E.g. first try some thousand random words (of a specific length) and then use testing-based eqivalence checks when your hypotheses have more structure.
Hope this gives you a starting point to continue.
Kind regards,
Markus
Am Fri, Jun 11, 2021 at 07:12:34AM -0700 schrieb Khanh Ho:
> Hello,
>
> I've started using Learnlib and I'm trying to run LStar Algorithm on my own
> DFAs, but it's impossible for me to get the correct results.
> I took the "Example1.java" file in the "learnlib
> <https://github.com/LearnLib/learnlib>/examples
> <https://github.com/LearnLib/learnlib/tree/develop/examples>/src
> <https://github.com/LearnLib/learnlib/tree/develop/examples/src>/main
> <https://github.com/LearnLib/learnlib/tree/develop/examples/src/main>/java
> <https://github.com/LearnLib/learnlib/tree/develop/examples/src/main/java>/
> de
> <https://github.com/LearnLib/learnlib/tree/develop/examples/src/main/java/de>
> /learnlib
> <https://github.com/LearnLib/learnlib/tree/develop/examples/src/main/java/de/learnlib>
> /*examples*/" folder on GitHub and used the .fsm format to deserialize the
> You received this message because you are subscribed to the Google Groups "LearnLib Q&A" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to learnlib-qa...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/learnlib-qa/a0e8ba08-3a81-4fe5-b59e-308e566c8399n%40googlegroups.com.
the "problem" with your automata is that they have a very linear structure. You basically have a sequence of states that you need to traverse in a specific order for detecting the only accepting (resp. rejecting) state.
Testing-based equivalence checks usually take the current hypothesis as ground truth and verify its transitions (+ a potential look-ahead). However, if you start with your initial hypothesis (which contains only a single state) and explore, e.g., 4 steps in the future, you will never be able to detect a state that is 12 steps away. This is why the equivalence oracle does not detect any counterexamples and you are left with your initial hypothesis.
Increasing the exploration depth enough will eventually resolve this problem. However, the number of queries grows exponentially with the exploration depth, as basically all possible input sequences are used for exploring the system (so a (number of input symbols)^(exploration depth) blow-up) and the learning will take a lot longer.
If this is an issue, you can also think about using an equivalence oracle chain that combines difference equivalence heurists. E.g. first try some thousand random words (of a specific length) and then use testing-based eqivalence checks when your hypotheses have more structure.
Hope this gives you a starting point to continue.
Kind regards,
Markus
Am Fri, Jun 11, 2021 at 07:12:34AM -0700 schrieb Khanh Ho:
> Hello,
>
> I've started using Learnlib and I'm trying to run LStar Algorithm on my own
> DFAs, but it's impossible for me to get the correct results.
> I took the "Example1.java" file in the "learnlib
> <https://github.com/LearnLib/learnlib/tree/develop/examples>/src
> <https://github.com/LearnLib/learnlib/tree/develop/examples/src>/main
> <https://github.com/LearnLib/learnlib/tree/develop/examples/src/main>/java
> <https://github.com/LearnLib/learnlib/tree/develop/examples/src/main/java>/
> de
> <https://github.com/LearnLib/learnlib/tree/develop/examples/src/main/java/de>
> /learnlib
> <https://github.com/LearnLib/learnlib/tree/develop/examples/src/main/java/de/learnlib>
> /*examples*/" folder on GitHub and used the .fsm format to deserialize the
> automata. Each letter in the alphabet is a string, as you can see in my
> files. I tried to modify the EPLORATION_DEPTH, switch to another EQOracle
> such that RandomWords or RandomWMethod but either it couldn't find a
> counter-example or it generated an automaton with a unique state.
> I couldn't find the issue, maybe my automata are too big? They have always
> a maximum of 30 states and my alphabet size is also about 30.
> Could you help me out, please?
>
> Kind regards,
> Khanh.
> P/s: I've attached here the java file with the main (which is based on
> your "Example1.java") and some of my .fsm files.
>
> --
> files. I tried to modify the EPLORATION_DEPTH, switch to another EQOracle
> such that RandomWords or RandomWMethod but either it couldn't find a
> counter-example or it generated an automaton with a unique state.
> I couldn't find the issue, maybe my automata are too big? They have always
> a maximum of 30 states and my alphabet size is also about 30.
> Could you help me out, please?
>
> Kind regards,
> Khanh.
> P/s: I've attached here the java file with the main (which is based on
> your "Example1.java") and some of my .fsm files.
>
> You received this message because you are subscribed to the Google Groups "LearnLib Q&A" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to learnlib-qa...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/learnlib-qa/a0e8ba08-3a81-4fe5-b59e-308e566c8399n%40googlegroups.com.
Khanh Ho
Jun 13, 2021, 6:08:44 AM6/13/21
to LearnLib Q&A
Hello Markus,
Thank you for your response.
I've found that the LStar Algorithm always generates complete automata, which are might not necessary in my case. Since my alphabet size is big but I just need a very small number of outputs for each state, is it possible to create incomplete automata with the algorithm?
I also saw that you have some minimizers for DFAs, do you think if I, for the equivalence test, minimize the hypotheses and compare them to the original one (i.e the target one), I will get the same result?
Kind regards,
Khanh.
Vào lúc 18:43:51 UTC+2 ngày Thứ Sáu, 11 tháng 6, 2021, Markus Frohme đã viết:
Markus Frohme
Jun 13, 2021, 5:31:56 PM6/13/21
to Khanh Ho, LearnLib Q&A
Dear Khanh,
no, most active learning algorithms (and specifically all algorithms in LearnLib) construct complete hypotheses.
You can play a little bit with the input symbols by using, e.g., the SupportsGrowingAlphabet feature of the learners to add input symbols later in the learning process and start the initial iterations with a smaller subset of input symbols. Also, using the concept of StateLocalInputs, you can somewhat simulate partial systems, as the system will only be queried the symbols that are available at each state. But this is more of a query-performance improvement: the hypotheses will still be complete -- only the relevant queries will be early-exited at oracle level.
However, consider that in your case not the actual learning of the hypotheses is the problem, but finding counterexamples. Here, the more knowledge you have about your target systems (and the more effort you are willing to put into heuristics for finding counterexamples) the more performance you will be able to gain. As the general black-box equivalence problem is undecidable, there is usually no universal "best" approach to counterexample search.
Regarding minimizing hypotheses: Most reasonable (active) learning algorithms already construct minized hypotheses, as most learning algorithms try to detect equivalence classes of the Myhill-Nerode congruence of the formal language (from which minimal automata are/can be constructed). So this wouldn't change anything.
Kind regards,
Markus
> To view this discussion on the web visit https://groups.google.com/d/msgid/learnlib-qa/5cf8302a-6ff4-4a02-addd-60c6e7aa56f9n%40googlegroups.com.
no, most active learning algorithms (and specifically all algorithms in LearnLib) construct complete hypotheses.
You can play a little bit with the input symbols by using, e.g., the SupportsGrowingAlphabet feature of the learners to add input symbols later in the learning process and start the initial iterations with a smaller subset of input symbols. Also, using the concept of StateLocalInputs, you can somewhat simulate partial systems, as the system will only be queried the symbols that are available at each state. But this is more of a query-performance improvement: the hypotheses will still be complete -- only the relevant queries will be early-exited at oracle level.
However, consider that in your case not the actual learning of the hypotheses is the problem, but finding counterexamples. Here, the more knowledge you have about your target systems (and the more effort you are willing to put into heuristics for finding counterexamples) the more performance you will be able to gain. As the general black-box equivalence problem is undecidable, there is usually no universal "best" approach to counterexample search.
Regarding minimizing hypotheses: Most reasonable (active) learning algorithms already construct minized hypotheses, as most learning algorithms try to detect equivalence classes of the Myhill-Nerode congruence of the formal language (from which minimal automata are/can be constructed). So this wouldn't change anything.
Kind regards,
Markus
Reply all
Reply to author
Forward
0 new messages