How to print the intermediate observation table (especially when the create the hypothesis)

[VishalPatel43]

package com.experiment;

import com.google.common.collect.Lists;
import de.learnlib.algorithms.lstar.closing.ClosingStrategies;
import de.learnlib.algorithms.lstar.dfa.ClassicLStarDFA;
import de.learnlib.algorithms.lstar.dfa.ClassicLStarDFABuilder;
import de.learnlib.algorithms.malerpnueli.MalerPnueliDFA;
import de.learnlib.algorithms.rivestschapire.RivestSchapireDFA;
import de.learnlib.algorithms.rivestschapire.RivestSchapireDFABuilder;
import de.learnlib.api.oracle.MembershipOracle;
import de.learnlib.datastructure.observationtable.writer.ObservationTableASCIIWriter;
import de.learnlib.filter.statistic.oracle.DFACounterOracle;
import de.learnlib.oracle.equivalence.DFAWMethodEQOracle;
import de.learnlib.oracle.equivalence.SampleSetEQOracle;
import de.learnlib.oracle.membership.SimulatorOracle;
import de.learnlib.util.Experiment;
import dk.brics.automaton.Automaton;
import dk.brics.automaton.RegExp;
import net.automatalib.automata.fsa.DFA;
import net.automatalib.brics.BricsDFA;
import net.automatalib.util.automata.conformance.WMethodTestsIterator;
import net.automatalib.visualization.Visualization;
import net.automatalib.words.Alphabet;
import net.automatalib.words.impl.Alphabets;

public class Driver {

    private static final int EXPLORATION_DEPTH = 5;

    public static void main(String[] args) {
        String regex = "a|b|.{3,}";

        final Automaton automaton = new RegExp(regex).toAutomaton();
        final Alphabet<Character> alphabet = Alphabets.characters('a', 'b');
        final BricsDFA dfa = new BricsDFA(automaton, true);

        MembershipOracle.DFAMembershipOracle<Character> sul = new SimulatorOracle.DFASimulatorOracle<>(dfa);

        lstarAlgorithm(dfa, alphabet, sul);
        System.out.println("-------------------------------------------------------");
        rsAlgorithm(dfa, alphabet, sul);
        System.out.println("-------------------------------------------------------");
        colAlgorithm(dfa, alphabet, sul);
    }

    private static void lstarAlgorithm(BricsDFA dfa, Alphabet<Character> alphabet, MembershipOracle.DFAMembershipOracle<Character> sul) {
        DFACounterOracle<Character> lstarCounter = new DFACounterOracle<>(sul, "Membership Queries");
        ClassicLStarDFA<Character> lstar = new ClassicLStarDFABuilder<Character>().withAlphabet(alphabet)
                .withOracle(lstarCounter)
                .create();

        final SampleSetEQOracle<Character, Boolean> eqo = new SampleSetEQOracle<>(false);
        eqo.addAll(sul, Lists.newArrayList(new WMethodTestsIterator<>(dfa, alphabet, EXPLORATION_DEPTH)));
        Experiment.DFAExperiment<Character> lstarExperiment = new Experiment.DFAExperiment<>(lstar, eqo, alphabet);

        System.out.println("Initial observation table of LSTAR:");
        new ObservationTableASCIIWriter<>().write(lstar.getObservationTable(), System.out);
        System.out.println();

        long startTime = System.currentTimeMillis();
        lstarExperiment.run();
        long endTime = System.currentTimeMillis();

        printResults("LStar", lstarExperiment, lstarCounter, endTime - startTime);
        System.out.println("Final observation table of LSTAR:");
        new ObservationTableASCIIWriter<>().write(lstar.getObservationTable(), System.out);
    }

    private static void rsAlgorithm(BricsDFA dfa, Alphabet<Character> alphabet, MembershipOracle.DFAMembershipOracle<Character> sul) {
        DFACounterOracle<Character> rsCounter = new DFACounterOracle<>(sul, "Membership Queries");
        RivestSchapireDFA<Character> rs = new RivestSchapireDFABuilder<Character>()
                .withAlphabet(alphabet)
                .withOracle(rsCounter)
                .withClosingStrategy(ClosingStrategies.CLOSE_FIRST)
                .create();

        final SampleSetEQOracle<Character, Boolean> eqo = new SampleSetEQOracle<>(false);
        eqo.addAll(sul, Lists.newArrayList(new WMethodTestsIterator<>(dfa, alphabet, EXPLORATION_DEPTH)));
        Experiment.DFAExperiment<Character> rsExperiment = new Experiment.DFAExperiment<>(rs, eqo, alphabet);

        System.out.println("Initial observation table of L_RS:");
        new ObservationTableASCIIWriter<>().write(rs.getObservationTable(), System.out);
        System.out.println();

        long startTime = System.currentTimeMillis();
        rsExperiment.run();
        long endTime = System.currentTimeMillis();

        printResults("L_RS", rsExperiment, rsCounter, endTime - startTime);
        System.out.println("Final observation table of L_RS:");
        new ObservationTableASCIIWriter<>().write(rs.getObservationTable(), System.out);
    }

    private static void colAlgorithm(BricsDFA dfa, Alphabet<Character> alphabet, MembershipOracle.DFAMembershipOracle<Character> sul) {
        DFACounterOracle<Character> colCounter = new DFACounterOracle<>(sul, "Membership Queries");
        MalerPnueliDFA<Character> col = new MalerPnueliDFA<>(alphabet, colCounter);

        final SampleSetEQOracle<Character, Boolean> eqo = new SampleSetEQOracle<>(false);
        eqo.addAll(sul, Lists.newArrayList(new WMethodTestsIterator<>(dfa, alphabet, EXPLORATION_DEPTH)));
        Experiment.DFAExperiment<Character> colExperiment = new Experiment.DFAExperiment<>(col, eqo, alphabet);

        System.out.println("Initial observation table of L_COL:");
        new ObservationTableASCIIWriter<>().write(col.getObservationTable(), System.out);
        System.out.println();

        long startTime = System.currentTimeMillis();
        colExperiment.run();
        long endTime = System.currentTimeMillis();

        printResults("L_Col", colExperiment, colCounter, endTime - startTime);
        System.out.println("Final observation table of L_COL:");
        new ObservationTableASCIIWriter<>().write(col.getObservationTable(), System.out);
    }

    private static void printResults(String algorithmName, Experiment.DFAExperiment<Character> experiment,
                                     DFACounterOracle<Character> counterOracle, long timeTaken) {
        System.out.println("----------------" + algorithmName + "-------------");
        System.out.println("EQ: " + experiment.getRounds().getCount());
        System.out.println("MQ: " + counterOracle.getCount());
        System.out.println("Time: " + timeTaken);
    }
}

"I provide the code, I want to print the intermediate observation table when hypothesis created or when the each membership queries ask to the teacher (SUL)"

[mtf90]

In this case you need to implement the Experiment#run loop yourself. However, this shouldn't be too hard. Something along the lines of (untested)

lstar.startLearning();

DFA<?, Character> hyp = lstar.getHypothesisModel();
DefaultQuery<Character, Boolean> ce;

while ((ce = eqo.findCounterExample(hyp, alphabet)) != null) {
    while (lstar.refineHypothesis(ce)) {}
    hyp = lstar.getHypothesisModel();
}

Here, you can insert any code you want between the individual steps (e.g., the logging of intermediate observation tables).

[VishalPatel43]

    private static void rsAlgorithm(BricsDFA dfa, Alphabet<Character> alphabet, MembershipOracle.DFAMembershipOracle<Character> sul) {
        DFACounterOracle<Character> rsCounter = new DFACounterOracle<>(sul, "Membership Queries");
        RivestSchapireDFA<Character> rs = new RivestSchapireDFABuilder<Character>()
                .withAlphabet(alphabet)
                .withOracle(rsCounter)
                .withClosingStrategy(ClosingStrategies.CLOSE_FIRST)
                .create();

        final SampleSetEQOracle<Character, Boolean> eqo = new SampleSetEQOracle<>(false);
        eqo.addAll(sul, Lists.newArrayList(new WMethodTestsIterator<>(dfa, alphabet, EXPLORATION_DEPTH)));
        Experiment.DFAExperiment<Character> rsExperiment = new Experiment.DFAExperiment<>(rs, eqo, alphabet);

        rs.startLearning();
        DFA<?, Character> hyp = rs.getHypothesisModel();
        DefaultQuery<Character, Boolean> ce;

        while ((ce = eqo.findCounterExample(hyp, alphabet)) != null) {
            while (rs.refineHypothesis(ce)) {
                System.out.println(ce.toStringWithAnswer(true));
                hyp = rs.getHypothesisModel();
                new ObservationTableASCIIWriter<>().write(rs.getObservationTable(), System.out);
            }
        }

        long startTime = System.currentTimeMillis();
//        rsExperiment.run();
        long endTime = System.currentTimeMillis();

//        printResults("L_RS", rsExperiment, rsCounter, endTime - startTime);
//        System.out.println("Final observation table of L_RS:");
//        new ObservationTableASCIIWriter<>().write(rs.getObservationTable(), System.out);
    }

It will run perfectly fine but I want to know the steps that calculate the excat suffix in the observation in the Rivest Scharpire

[mtf90]

In case of the L* learners, counterexample analysis is outsourced to ObservationTableCEXHandlers. For the RivestSchapireDFA learner ObservationTableCEXHandlers.RIVEST_SCHAPIRE is used. If you want a more fine-grained analysis of the analysis steps, you would have to provide your own ObservationTableCEXHandler implementation. It would probably be easiest, to just copy the existing code from the RIVEST_SCHAPIRE analyzer and insert your logging statements.

[VishalPatel43]

Please provide that when we run the algorithm

        long startTime = System.currentTimeMillis();
        colExperiment.run();
        long endTime = System.currentTimeMillis();

we can measure the entire time, but I want to compute the time in that number of equivalence queries and membership queies separately.

[mtf90]

If you have a custom while loop like in your first reply, you can simply wrap the call to eq.findCounterExample in some timing code.

If you want to use the existing Experiment class, you need to provide your own MembershipOracle and EquivalenceOracle implementations that measure the time themselves. However, this should be relatively easy to implement, since you can delegate most of the calls to the original MQ/EQ (like in the CounterOracle class, except for counting the queries, you track System.currentTimeMillis()).

[VishalPatel43]

actually I ddin't know much about the implementation from the library. Please can we provide the little bit of idea or sample code so I can do it by myself

package com.experiment;

import com.experiment.dfa.DFAOperation;
import com.google.common.collect.Lists;
import de.learnlib.algorithms.lstar.closing.ClosingStrategies;
import de.learnlib.algorithms.lstar.dfa.ClassicLStarDFA;
import de.learnlib.algorithms.lstar.dfa.ClassicLStarDFABuilder;
import de.learnlib.algorithms.malerpnueli.MalerPnueliDFA;
import de.learnlib.algorithms.rivestschapire.RivestSchapireDFA;
import de.learnlib.algorithms.rivestschapire.RivestSchapireDFABuilder;
import de.learnlib.api.oracle.MembershipOracle;
import de.learnlib.api.query.DefaultQuery;
import de.learnlib.datastructure.observationtable.ObservationTable;
import de.learnlib.datastructure.observationtable.writer.ObservationTableASCIIWriter;
import de.learnlib.filter.statistic.oracle.DFACounterOracle;
import de.learnlib.oracle.equivalence.DFAWMethodEQOracle;
import de.learnlib.oracle.equivalence.SampleSetEQOracle;
import de.learnlib.oracle.membership.SimulatorOracle;
import de.learnlib.util.Experiment;
import dk.brics.automaton.Automaton;
import dk.brics.automaton.RegExp;
import net.automatalib.automata.fsa.DFA;
import net.automatalib.brics.BricsDFA;
import net.automatalib.util.automata.conformance.WMethodTestsIterator;
import net.automatalib.visualization.Visualization;
import net.automatalib.words.Alphabet;
import net.automatalib.words.impl.Alphabets;

public class Driver {

    private static final DFAOperation dfaOperation = new DFAOperation();
    private static final int EXPLORATION_DEPTH = 5;

    public static void main(String[] args) {
        String regex = "a|b|.{3,}";

        final Automaton automaton = new RegExp(regex).toAutomaton();
        final Alphabet<Character> alphabet = Alphabets.characters('a', 'b');
        final BricsDFA dfa = new BricsDFA(automaton, true);

        MembershipOracle.DFAMembershipOracle<Character> sul = new SimulatorOracle.DFASimulatorOracle<>(dfa);

        rsAlgorithm(dfa, alphabet, sul);
        System.out.println("-------------------------------------------------------");
    }

    private static void rsAlgorithm(BricsDFA dfa, Alphabet<Character> alphabet, MembershipOracle.DFAMembershipOracle<Character> sul) {
        DFACounterOracle<Character> rsCounter = new DFACounterOracle<>(sul, "Membership Queries");
        RivestSchapireDFA<Character> rs = new RivestSchapireDFABuilder<Character>()
                .withAlphabet(alphabet)
                .withOracle(rsCounter)
                .withClosingStrategy(ClosingStrategies.CLOSE_FIRST)
                .create();

        final SampleSetEQOracle<Character, Boolean> eqo = new SampleSetEQOracle<>(false);
        eqo.addAll(sul, Lists.newArrayList(new WMethodTestsIterator<>(dfa, alphabet, EXPLORATION_DEPTH)));
        Experiment.DFAExperiment<Character> rsExperiment = new Experiment.DFAExperiment<>(rs, eqo, alphabet);

        rs.startLearning();
        DFA<?, Character> hyp = rs.getHypothesisModel();
        DefaultQuery<Character, Boolean> ce;

        int count  = 1;
        while ((ce = eqo.findCounterExample(hyp, alphabet)) != null) {
            while (rs.refineHypothesis(ce)) {
                System.out.println(ce.toStringWithAnswer(true));
                hyp = rs.getHypothesisModel();
//                Visualization.visualize(hyp, alphabet);
                new ObservationTableASCIIWriter<>().write(rs.getObservationTable(), System.out);
                ++count;
            }
        }

        long startTime = System.currentTimeMillis();
//        rsExperiment.run();
        long endTime = System.currentTimeMillis();

        printResults("L_RS", rsExperiment, rsCounter, endTime - startTime);
        System.out.println("Final observation table of L_RS:");
        new ObservationTableASCIIWriter<>().write(rs.getObservationTable(), System.out);
    }

    private static void printResults(String algorithmName, Experiment.DFAExperiment<Character> experiment,
                                     DFACounterOracle<Character> counterOracle, long timeTaken) {
        System.out.println("----------------" + algorithmName + "-------------");
        System.out.println("EQ: " + experiment.getRounds().getCount());
        System.out.println("MQ: " + counterOracle.getCount());
        System.out.println("Time: " + timeTaken);
    }
}

[mtf90]

It is really just a simple delegation pattern. Something like

public class VishalMQOracle<I, D> implements MembershipOracle<I, D> {

    private final MembershipOracle<I, D> delegate;

    public VishalMQOracle(MembershipOracle<I, D> delegate) {
        this.delegate = delegate;
    }

    @Override
    public void processQueries(Collection<? extends Query<I, D>> queries) {
        long before = System.currentTimeMillis();
        delegate.processQueries(queries);
        long after = System.currentTimeMillis();
        System.out.println("Time: " + (after - before) + " ms");
    }
}

(if you need the automaton-specific oracle types, just implement DFAMembershipOracle, etc.).

You can then simply use, e.g., your rsCounter as a delegate (MembershipOracle<Character, Boolean> rsTimer = new VishalMQOracle<>(rsCounter); and use the new oracle wherever you want to measure the runtime. You can do the same thing for equivalence oracles and the findCounterExample method.