20198569605

Committed 13 Dec 2025 10:10PM UTC coverage: 94.914% (+0.4%) from 94.471%

Build # 20198569605

Build Type

Pull #153

github

Committed by

web-flow

Commit Message

Merge 6a71fc929 into 879958926

Pull Request Pull Request #153: Implementation for learning MMLTs, new model for collecting statistics

Run Details

1823 of 1873 new or added lines in 77 files covered. (97.33%)

1 existing line in 1 file now uncovered.

14258 of 15022 relevant lines covered (94.91%)

1.73 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.06

/examples/src/main/java/de/learnlib/example/mmlt/Example3.java

/* Copyright (C) 2013-2025 TU Dortmund University
 * This file is part of LearnLib <https://learnlib.de>.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package de.learnlib.example.mmlt;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import de.learnlib.algorithm.lstar.mmlt.ExtensibleLStarMMLTBuilder;
import de.learnlib.algorithm.lstar.mmlt.filter.MMLTRandomSymbolFilter;
import de.learnlib.algorithm.lstar.mmlt.filter.MMLTStatisticsSymbolFilter;
import de.learnlib.driver.simulator.MMLTSimulatorSUL;
import de.learnlib.filter.SymbolFilter;
import de.learnlib.filter.cache.mmlt.TimedSULTreeCache;
import de.learnlib.filter.cache.mmlt.TimeoutReducerSUL;
import de.learnlib.filter.statistic.oracle.CounterEQOracle;
import de.learnlib.filter.statistic.sul.CounterTimedSUL;
import de.learnlib.filter.symbol.CachedSymbolFilter;
import de.learnlib.oracle.equivalence.MMLTEQOracleChain;
import de.learnlib.oracle.equivalence.mmlt.RandomWpMethodEQOracle;
import de.learnlib.oracle.equivalence.mmlt.ResetSearchEQOracle;
import de.learnlib.oracle.equivalence.mmlt.SimulatorEQOracle;
import de.learnlib.oracle.membership.TimedSULOracle;
import de.learnlib.statistic.Statistics;
import de.learnlib.testsupport.example.mmlt.MMLTExamples;
import net.automatalib.automaton.mmlt.MMLT;
import net.automatalib.symbol.time.InputSymbol;
import net.automatalib.symbol.time.TimedInput;
import net.automatalib.symbol.time.TimeoutSymbol;
import net.automatalib.word.Word;

/**
 * This example illustrates how to learn {@link MMLT}s with symbol filtering.
 * <p>
 * A symbol filter is a component that provides information about transitions that might silently self-loop. The learner
 * exploits this information to avoid redundant queries on the SUL. The symbol filter might incorrectly classify a
 * transition as silent self-loop. The MMLT-learner detects and corrects such errors.
 * <p>
 * LearnLib includes four types of symbol filter:
 * <ul>
 * <li> AcceptAllSymbolFilter: no transition is considered as silent self-loop.
 * This is the default behavior if no filter is provided. </li>
 * <li> PerfectSymbolFilter: simulates perfect knowledge of silent self-loops.
 * Perfect knowledge is useful for benchmarking but rarely the case in practice. </li>
 * <li> IgnoreAllSymbolFilter: considers all transitions to be silent self-loops.
 * If no knowledge of the SUL is available, this filter still often yields strong performance improvements.</li>
 * <li>RandomSymbolFilter: simulates incorrect responses with a certain percentage.</li>
 * </ul>
 * <p>
 * When you apply MMLT-learning in practice, you usually want to implement your own symbol filter that exploits specific
 * domain knowledge.
 */
@SuppressWarnings({"checkstyle:magicnumber", "PMD.UseExplicitTypes"}) // allow magic numbers and vars in examples
public final class Example3 {

    private static final int BOUND = 100;
    private static final double INACC_PROB = 0.1;
    private static final int MIN_SIZE = 16;
    private static final double PERCENTAGE = 1.0;
    private static final int SEED = 100;

    private Example3() {
        // prevent instantiation
    }

    public static void main(String[] args) {
        var model = MMLTExamples.sensorCollector();
        var mmlt = model.getReferenceAutomaton();
        var alphabet = mmlt.getInputAlphabet();

        // We first create a statistics container.
        // This container will store various statistical data during learning:
        var statistics = Statistics.getService();
        statistics.setText(Example1.KEY_MODEL, model.toString());
        statistics.setCounter(Example1.KEY_LOCS, mmlt.getStates().size());
        statistics.setCounter(Example1.KEY_SYMS, alphabet.size());

        // ======================
        // Set up the pipeline:
        // We use a simulator SUL to simulate our automaton:
        var sul = new MMLTSimulatorSUL<>(mmlt);

        // We count all operations that are performed on the SUL with a stats-SUL:
        var statsAfterCache = new CounterTimedSUL<>(sul, "post-cache");

        // We use a cache to avoid redundant operations:
        var cacheSUL = new TimedSULTreeCache<>(statsAfterCache, model.getParams());
        var toReducerSul = new TimeoutReducerSUL<>(cacheSUL, model.getParams().maxTimeoutWaitingTime());
        var statsBeforeCache = new CounterTimedSUL<>(toReducerSul, "pre-cache");

        // We use a query oracle to answer queries from the learner:
        var timeOracle = new TimedSULOracle<>(statsBeforeCache, model.getParams());

        // We use a chain of different equivalence oracles (see Example2):
        MMLTEQOracleChain<String, String> chainOracle = new MMLTEQOracleChain<>();
        chainOracle.addOracle(new CounterEQOracle<>(cacheSUL.createCacheConsistencyTest(), "cache"));
        chainOracle.addOracle(new CounterEQOracle<>(new ResetSearchEQOracle<>(timeOracle, SEED, PERCENTAGE, PERCENTAGE),
                                                    "reset"));
        chainOracle.addOracle(new CounterEQOracle<>(new RandomWpMethodEQOracle<>(timeOracle, SEED, MIN_SIZE, 0, BOUND),
                                                    "wp"));

        // Set up our L* learner:
        List<Word<TimedInput<String>>> suffixes = new ArrayList<>();
        alphabet.forEach(s -> suffixes.add(Word.fromLetter(TimedInput.input(s))));
        suffixes.add(Word.fromLetter(new TimeoutSymbol<>()));

        // A symbol filter allows us to reduce queries by exploiting prior knowledge.
        // For this example, we use a AbstractRandomSymbolFilter. This filter correctly predicts
        // whether a transition silently self-loops with an accuracy of 90%:
        SymbolFilter<TimedInput<String>, InputSymbol<String>> filter =
                new MMLTRandomSymbolFilter<>(mmlt, INACC_PROB, new Random(SEED));

        // We wrap our filter with a StatisticsFilter to collect useful statistics about the filter:
        filter = new MMLTStatisticsSymbolFilter<>(mmlt, filter);

        // The learner may need to update incorrect responses of the filter.
        // To facilitate this, we wrap our filter with a CachedFilter:
        var cachedFilter = new CachedSymbolFilter<>(filter);

        var learner = new ExtensibleLStarMMLTBuilder<String, String>().withAlphabet(alphabet)
                                                                      .withModelParams(model.getParams())
                                                                      .withTimeOracle(timeOracle)
                                                                      .withInitialSuffixes(suffixes)
                                                                      .withSymbolFilter(cachedFilter)
                                                                      .create();

        // Start learning:
        var finalModel = ExampleRunner.runExperiment(learner, chainOracle, mmlt.getSemantics().getInputAlphabet());

        // In this set-up, we actually know the reference automaton.
        // This allows us to check that we learned an accurate model:
        var simOracle = new SimulatorEQOracle<>(mmlt);
        if (simOracle.findCounterExample(finalModel, finalModel.getSemantics().getInputAlphabet()) != null) {
            throw new IllegalStateException("Incorrect model learned.");
        }
    }

}

1	/* Copyright (C) 2013-2025 TU Dortmund University
2	* This file is part of LearnLib <https://learnlib.de>.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package de.learnlib.example.mmlt;
17
18	import java.util.ArrayList;
19	import java.util.List;
20	import java.util.Random;
21
22	import de.learnlib.algorithm.lstar.mmlt.ExtensibleLStarMMLTBuilder;
23	import de.learnlib.algorithm.lstar.mmlt.filter.MMLTRandomSymbolFilter;
24	import de.learnlib.algorithm.lstar.mmlt.filter.MMLTStatisticsSymbolFilter;
25	import de.learnlib.driver.simulator.MMLTSimulatorSUL;
26	import de.learnlib.filter.SymbolFilter;
27	import de.learnlib.filter.cache.mmlt.TimedSULTreeCache;
28	import de.learnlib.filter.cache.mmlt.TimeoutReducerSUL;
29	import de.learnlib.filter.statistic.oracle.CounterEQOracle;
30	import de.learnlib.filter.statistic.sul.CounterTimedSUL;
31	import de.learnlib.filter.symbol.CachedSymbolFilter;
32	import de.learnlib.oracle.equivalence.MMLTEQOracleChain;
33	import de.learnlib.oracle.equivalence.mmlt.RandomWpMethodEQOracle;
34	import de.learnlib.oracle.equivalence.mmlt.ResetSearchEQOracle;
35	import de.learnlib.oracle.equivalence.mmlt.SimulatorEQOracle;
36	import de.learnlib.oracle.membership.TimedSULOracle;
37	import de.learnlib.statistic.Statistics;
38	import de.learnlib.testsupport.example.mmlt.MMLTExamples;
39	import net.automatalib.automaton.mmlt.MMLT;
40	import net.automatalib.symbol.time.InputSymbol;
41	import net.automatalib.symbol.time.TimedInput;
42	import net.automatalib.symbol.time.TimeoutSymbol;
43	import net.automatalib.word.Word;
44
45	/**
46	* This example illustrates how to learn {@link MMLT}s with symbol filtering.
47	* <p>
48	* A symbol filter is a component that provides information about transitions that might silently self-loop. The learner
49	* exploits this information to avoid redundant queries on the SUL. The symbol filter might incorrectly classify a
50	* transition as silent self-loop. The MMLT-learner detects and corrects such errors.
51	* <p>
52	* LearnLib includes four types of symbol filter:
53	* <ul>
54	* <li> AcceptAllSymbolFilter: no transition is considered as silent self-loop.
55	* This is the default behavior if no filter is provided. </li>
56	* <li> PerfectSymbolFilter: simulates perfect knowledge of silent self-loops.
57	* Perfect knowledge is useful for benchmarking but rarely the case in practice. </li>
58	* <li> IgnoreAllSymbolFilter: considers all transitions to be silent self-loops.
59	* If no knowledge of the SUL is available, this filter still often yields strong performance improvements.</li>
60	* <li>RandomSymbolFilter: simulates incorrect responses with a certain percentage.</li>
61	* </ul>
62	* <p>
63	* When you apply MMLT-learning in practice, you usually want to implement your own symbol filter that exploits specific
64	* domain knowledge.
65	*/
66	@SuppressWarnings({"checkstyle:magicnumber", "PMD.UseExplicitTypes"}) // allow magic numbers and vars in examples
67	public final class Example3 {
68
69	private static final int BOUND = 100;
70	private static final double INACC_PROB = 0.1;
71	private static final int MIN_SIZE = 16;
72	private static final double PERCENTAGE = 1.0;
73	private static final int SEED = 100;
74
75	private Example3() {
76	// prevent instantiation
77	}
78
79	public static void main(String[] args) {
80	var model = MMLTExamples.sensorCollector();	1✔
81	var mmlt = model.getReferenceAutomaton();	1✔
82	var alphabet = mmlt.getInputAlphabet();	1✔
83
84	// We first create a statistics container.
85	// This container will store various statistical data during learning:
86	var statistics = Statistics.getService();	1✔
87	statistics.setText(Example1.KEY_MODEL, model.toString());	1✔
88	statistics.setCounter(Example1.KEY_LOCS, mmlt.getStates().size());	1✔
89	statistics.setCounter(Example1.KEY_SYMS, alphabet.size());	1✔
90
91	// ======================
92	// Set up the pipeline:
93	// We use a simulator SUL to simulate our automaton:
94	var sul = new MMLTSimulatorSUL<>(mmlt);	1✔
95
96	// We count all operations that are performed on the SUL with a stats-SUL:
97	var statsAfterCache = new CounterTimedSUL<>(sul, "post-cache");	1✔
98
99	// We use a cache to avoid redundant operations:
100	var cacheSUL = new TimedSULTreeCache<>(statsAfterCache, model.getParams());	1✔
101	var toReducerSul = new TimeoutReducerSUL<>(cacheSUL, model.getParams().maxTimeoutWaitingTime());	1✔
102	var statsBeforeCache = new CounterTimedSUL<>(toReducerSul, "pre-cache");	1✔
103
104	// We use a query oracle to answer queries from the learner:
105	var timeOracle = new TimedSULOracle<>(statsBeforeCache, model.getParams());	1✔
106
107	// We use a chain of different equivalence oracles (see Example2):
108	MMLTEQOracleChain<String, String> chainOracle = new MMLTEQOracleChain<>();	1✔
109	chainOracle.addOracle(new CounterEQOracle<>(cacheSUL.createCacheConsistencyTest(), "cache"));	1✔
110	chainOracle.addOracle(new CounterEQOracle<>(new ResetSearchEQOracle<>(timeOracle, SEED, PERCENTAGE, PERCENTAGE),	1✔
111	"reset"));
112	chainOracle.addOracle(new CounterEQOracle<>(new RandomWpMethodEQOracle<>(timeOracle, SEED, MIN_SIZE, 0, BOUND),	1✔
113	"wp"));
114
115	// Set up our L* learner:
116	List<Word<TimedInput<String>>> suffixes = new ArrayList<>();	1✔
117	alphabet.forEach(s -> suffixes.add(Word.fromLetter(TimedInput.input(s))));	1✔
118	suffixes.add(Word.fromLetter(new TimeoutSymbol<>()));	1✔
119
120	// A symbol filter allows us to reduce queries by exploiting prior knowledge.
121	// For this example, we use a AbstractRandomSymbolFilter. This filter correctly predicts
122	// whether a transition silently self-loops with an accuracy of 90%:
123	SymbolFilter<TimedInput<String>, InputSymbol<String>> filter =	1✔
124	new MMLTRandomSymbolFilter<>(mmlt, INACC_PROB, new Random(SEED));
125
126	// We wrap our filter with a StatisticsFilter to collect useful statistics about the filter:
127	filter = new MMLTStatisticsSymbolFilter<>(mmlt, filter);	1✔
128
129	// The learner may need to update incorrect responses of the filter.
130	// To facilitate this, we wrap our filter with a CachedFilter:
131	var cachedFilter = new CachedSymbolFilter<>(filter);	1✔
132
133	var learner = new ExtensibleLStarMMLTBuilder<String, String>().withAlphabet(alphabet)	1✔
134	.withModelParams(model.getParams())	1✔
135	.withTimeOracle(timeOracle)	1✔
136	.withInitialSuffixes(suffixes)	1✔
137	.withSymbolFilter(cachedFilter)	1✔
138	.create();	1✔
139
140	// Start learning:
141	var finalModel = ExampleRunner.runExperiment(learner, chainOracle, mmlt.getSemantics().getInputAlphabet());	1✔
142
143	// In this set-up, we actually know the reference automaton.
144	// This allows us to check that we learned an accurate model:
145	var simOracle = new SimulatorEQOracle<>(mmlt);	1✔
146	if (simOracle.findCounterExample(finalModel, finalModel.getSemantics().getInputAlphabet()) != null) {	1✔
NEW 147	throw new IllegalStateException("Incorrect model learned.");	×
148	}
149	}	1✔
150
151	}

LearnLib / learnlib / 20198569605

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous