Package de.learnlib.algorithm.rpni

Class BlueFringeMDLDFA<I>

java.lang.Object

de.learnlib.algorithm.rpni.AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,DFA<?,I>>

de.learnlib.algorithm.rpni.BlueFringeMDLDFA<I>

Type Parameters:

I - input symbol type

All Implemented Interfaces:

PassiveLearningAlgorithm<DFA<?,I>,I,Boolean>, PassiveLearningAlgorithm.PassiveAcceptorLearner<DFA<?,I>,I>, PassiveLearningAlgorithm.PassiveDFALearner<I>

public class BlueFringeMDLDFA<I>
extends AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,DFA<?,I>>
implements PassiveLearningAlgorithm.PassiveDFALearner<I>

A state-merging learning algorithm based on the minimal description length principle. On an operational level this algorithm is very similar to the 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.

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.

Implementation note: This implementation does support repeated calls to PassiveLearningAlgorithm.computeModel().

Nested Class Summary

Nested classes/interfaces inherited from interface de.learnlib.algorithm.PassiveLearningAlgorithm

PassiveLearningAlgorithm.PassiveAcceptorLearner<M extends FiniteStateAcceptor<?,I>,I>, PassiveLearningAlgorithm.PassiveDFALearner<I>, PassiveLearningAlgorithm.PassiveMealyLearner<I,O>, PassiveLearningAlgorithm.PassiveMooreLearner<I,O>

Field Summary

Fields inherited from class de.learnlib.algorithm.rpni.AbstractBlueFringeRPNI

alphabet, alphabetSize

Constructor Summary

Constructors

Constructor	Description
BlueFringeMDLDFA(Alphabet<I> alphabet)	Constructor.

Method Summary

Modifier and Type	Method	Description
void	addSamples(Collection<? extends DefaultQuery<I,Boolean>> samples)
DFA<?,I>	computeModel()	Computes the model given the previously added samples.
protected BlueFringePTA<Boolean,Void>	fetchPTA()	Fetches the initial PTA for model construction.
protected DFA<?,I>	ptaToModel(BlueFringePTA<Boolean,Void> pta)	Transforms the final PTA into a model.
protected Stream<RedBlueMerge<BlueFringePTAState<Boolean,Void>,Boolean,Void>>	selectMerges(Stream<RedBlueMerge<BlueFringePTAState<Boolean,Void>,Boolean,Void>> merges)	Implementing the method allows subclasses to decide on (and possibly reject) valid merges.

Methods inherited from class de.learnlib.algorithm.rpni.AbstractBlueFringeRPNI

setDeterministic, setParallel, setProcessingOrder, tryMerge

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface de.learnlib.algorithm.PassiveLearningAlgorithm

addSample, addSample, addSamples, addSamples, addSamples

Methods inherited from interface de.learnlib.algorithm.PassiveLearningAlgorithm.PassiveAcceptorLearner

addNegativeSample, addNegativeSamples, addNegativeSamples, addPositiveSample, addPositiveSamples, addPositiveSamples

Constructor Detail

BlueFringeMDLDFA

public BlueFringeMDLDFA(Alphabet<I> alphabet)

Constructor.

Parameters:

alphabet - the alphabet

Method Detail

addSamples

public void addSamples(Collection<? extends DefaultQuery<I,Boolean>> samples)

Specified by:

addSamples in interface PassiveLearningAlgorithm<DFA<?,I>,I,Boolean>

computeModel

public DFA<?,I> computeModel()

Description copied from interface: PassiveLearningAlgorithm

Computes the model given the previously added samples.

Implementation note: It is up to the implementation if this operation is repeatable or not, An implementation may throw an IllegalStateException if additional samples are added after the first model construction.

Specified by:

computeModel in interface PassiveLearningAlgorithm<DFA<?,I>,I,Boolean>

Overrides:

computeModel in class AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,DFA<?,I>>

Returns:

the computed model

fetchPTA

protected BlueFringePTA<Boolean,Void> fetchPTA()

Description copied from class: AbstractBlueFringeRPNI

Fetches the initial PTA for model construction. If subclasses need to cache the training data this may be a fresh instance. If subclasses directly insert training data to a local PTA, they should make sure that repeated invocations of this method are not possible.

Specified by:

fetchPTA in class AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,DFA<?,I>>

Returns:

the PTA for model construction.

selectMerges

protected Stream<RedBlueMerge<BlueFringePTAState<Boolean,Void>,Boolean,Void>> selectMerges(Stream<RedBlueMerge<BlueFringePTAState<Boolean,Void>,Boolean,Void>> merges)

Description copied from class: AbstractBlueFringeRPNI

Implementing the method allows subclasses to decide on (and possibly reject) valid merges.

Overrides:

selectMerges in class AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,DFA<?,I>>

Parameters:

merges - the prosed (valid) merges

Returns:

the merges that should be considered for selecting a merge.

ptaToModel

protected DFA<?,I> ptaToModel(BlueFringePTA<Boolean,Void> pta)

Description copied from class: AbstractBlueFringeRPNI

Transforms the final PTA into a model.

Specified by:

ptaToModel in class AbstractBlueFringeRPNI<I,Boolean,Boolean,Void,DFA<?,I>>

Parameters:

pta - the final PTA

Returns:

a model built from the final PTA