6433387082

Committed 06 Oct 2023 03:10PM UTC coverage: 92.296% (-0.007%) from 92.303%

Build # 6433387082

Build Type

push

github

Committed by

mtf90

Commit Message

update Falk's developer id

Run Details

11573 of 12539 relevant lines covered (92.3%)

1.67 hits per line

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

96.0

/algorithms/passive/rpni-mdl/src/main/java/de/learnlib/algorithms/rpni/BlueFringeMDLDFA.java

/* Copyright (C) 2013-2023 TU Dortmund
 * This file is part of LearnLib, http://www.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.algorithms.rpni;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.stream.Stream;

import de.learnlib.api.algorithm.PassiveLearningAlgorithm;
import de.learnlib.api.algorithm.PassiveLearningAlgorithm.PassiveDFALearner;
import de.learnlib.api.query.DefaultQuery;
import de.learnlib.datastructure.pta.PTAUtil;
import de.learnlib.datastructure.pta.pta.BlueFringePTA;
import de.learnlib.datastructure.pta.pta.BlueFringePTAState;
import de.learnlib.datastructure.pta.pta.RedBlueMerge;
import net.automatalib.automata.fsa.DFA;
import net.automatalib.commons.smartcollections.IntSeq;
import net.automatalib.words.Alphabet;

/**
 * A state-merging learning algorithm based on the minimal description length principle. On an operational level this
 * algorithm is very similar to the {@link BlueFringeRPNIDFA} algorithm. However, whereas the basic RPNI approach merges
 * the very first pair of nodes that resemble a valid merge, the MDL variant computes an additional score and only
 * commits to a merge, if the resulting hypothesis will yield a better score.
 * <p>
 * This passive approach to state-merging works better in scenarios where only positive training data is available.
 * Hence, this algorithm only expect positive training data.
 * <p>
 * <b>Implementation note:</b> This implementation does support repeated calls to {@link
 * PassiveLearningAlgorithm#computeModel()}.
 *
 * @param <I>
 *         input symbol type
 */
public class BlueFringeMDLDFA<I> extends AbstractBlueFringeRPNI<I, Boolean, Boolean, Void, DFA<?, I>>
        implements PassiveDFALearner<I> {

    private final List<IntSeq> positive = new ArrayList<>();

    private double currentScore = Double.POSITIVE_INFINITY;

    /**
     * Constructor.
     *
     * @param alphabet
     *         the alphabet
     */
    public BlueFringeMDLDFA(Alphabet<I> alphabet) {
        super(alphabet);
    }

    @Override
    public void addSamples(Collection<? extends DefaultQuery<I, Boolean>> samples) {
        for (DefaultQuery<I, Boolean> query : samples) {
            if (!query.getOutput()) {
                throw new IllegalArgumentException("Only positive examples are allowed");
            }
            positive.add(query.getInput().asIntSeq(alphabet));
        }
    }

    @Override
    public DFA<?, I> computeModel() {
        // disable parallelism because our track-keeping of the current score is not thread-safe
        super.setDeterministic(true);
        super.setParallel(false);
        return super.computeModel();
    }

    @Override
    protected BlueFringePTA<Boolean, Void> fetchPTA() {
        final BlueFringePTA<Boolean, Void> pta = new BlueFringePTA<>(alphabetSize);

        for (IntSeq pos : positive) {
            pta.addSample(pos, true);
        }

        return pta;
    }

    @Override
    protected Stream<RedBlueMerge<Boolean, Void, BlueFringePTAState<Boolean, Void>>> selectMerges(Stream<RedBlueMerge<Boolean, Void, BlueFringePTAState<Boolean, Void>>> merges) {
        return merges.filter(this::decideOnValidMerge);
    }

    private boolean decideOnValidMerge(RedBlueMerge<Boolean, Void, BlueFringePTAState<Boolean, Void>> merge) {
        final double score = MDLUtil.score(merge.toMergedAutomaton(), super.alphabetSize, positive);
        if (score < currentScore) {
            currentScore = score;
            return true;
        }

        return false;
    }

    @Override
    protected DFA<?, I> ptaToModel(BlueFringePTA<Boolean, Void> pta) {
        return PTAUtil.toDFA(pta, alphabet);
    }
}

1	/* Copyright (C) 2013-2023 TU Dortmund
2	* This file is part of LearnLib, http://www.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.algorithms.rpni;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.List;
21	import java.util.stream.Stream;
22
23	import de.learnlib.api.algorithm.PassiveLearningAlgorithm;
24	import de.learnlib.api.algorithm.PassiveLearningAlgorithm.PassiveDFALearner;
25	import de.learnlib.api.query.DefaultQuery;
26	import de.learnlib.datastructure.pta.PTAUtil;
27	import de.learnlib.datastructure.pta.pta.BlueFringePTA;
28	import de.learnlib.datastructure.pta.pta.BlueFringePTAState;
29	import de.learnlib.datastructure.pta.pta.RedBlueMerge;
30	import net.automatalib.automata.fsa.DFA;
31	import net.automatalib.commons.smartcollections.IntSeq;
32	import net.automatalib.words.Alphabet;
33
34	/**
35	* A state-merging learning algorithm based on the minimal description length principle. On an operational level this
36	* algorithm is very similar to the {@link BlueFringeRPNIDFA} algorithm. However, whereas the basic RPNI approach merges
37	* the very first pair of nodes that resemble a valid merge, the MDL variant computes an additional score and only
38	* commits to a merge, if the resulting hypothesis will yield a better score.
39	* <p>
40	* This passive approach to state-merging works better in scenarios where only positive training data is available.
41	* Hence, this algorithm only expect positive training data.
42	* <p>
43	* <b>Implementation note:</b> This implementation does support repeated calls to {@link
44	* PassiveLearningAlgorithm#computeModel()}.
45	*
46	* @param <I>
47	* input symbol type
48	*/
49	public class BlueFringeMDLDFA<I> extends AbstractBlueFringeRPNI<I, Boolean, Boolean, Void, DFA<?, I>>
50	implements PassiveDFALearner<I> {
51
52	private final List<IntSeq> positive = new ArrayList<>();	2✔
53
54	private double currentScore = Double.POSITIVE_INFINITY;	2✔
55
56	/**
57	* Constructor.
58	*
59	* @param alphabet
60	* the alphabet
61	*/
62	public BlueFringeMDLDFA(Alphabet<I> alphabet) {
63	super(alphabet);	2✔
64	}	2✔
65
66	@Override
67	public void addSamples(Collection<? extends DefaultQuery<I, Boolean>> samples) {
68	for (DefaultQuery<I, Boolean> query : samples) {	2✔
69	if (!query.getOutput()) {	2✔
70	throw new IllegalArgumentException("Only positive examples are allowed");	×
71	}
72	positive.add(query.getInput().asIntSeq(alphabet));	2✔
73	}	2✔
74	}	2✔
75
76	@Override
77	public DFA<?, I> computeModel() {
78	// disable parallelism because our track-keeping of the current score is not thread-safe
79	super.setDeterministic(true);	2✔
80	super.setParallel(false);	2✔
81	return super.computeModel();	2✔
82	}
83
84	@Override
85	protected BlueFringePTA<Boolean, Void> fetchPTA() {
86	final BlueFringePTA<Boolean, Void> pta = new BlueFringePTA<>(alphabetSize);	2✔
87
88	for (IntSeq pos : positive) {	2✔
89	pta.addSample(pos, true);	2✔
90	}	2✔
91
92	return pta;	2✔
93	}
94
95	@Override
96	protected Stream<RedBlueMerge<Boolean, Void, BlueFringePTAState<Boolean, Void>>> selectMerges(Stream<RedBlueMerge<Boolean, Void, BlueFringePTAState<Boolean, Void>>> merges) {
97	return merges.filter(this::decideOnValidMerge);	2✔
98	}
99
100	private boolean decideOnValidMerge(RedBlueMerge<Boolean, Void, BlueFringePTAState<Boolean, Void>> merge) {
101	final double score = MDLUtil.score(merge.toMergedAutomaton(), super.alphabetSize, positive);	2✔
102	if (score < currentScore) {	2✔
103	currentScore = score;	2✔
104	return true;	2✔
105	}
106
107	return false;	2✔
108	}
109
110	@Override
111	protected DFA<?, I> ptaToModel(BlueFringePTA<Boolean, Void> pta) {
112	return PTAUtil.toDFA(pta, alphabet);	2✔
113	}
114	}

LearnLib / learnlib / 6433387082

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