IDS::Algorithm::MM 1.02

IDS::Algorithm::MM is a Perl module created to learn or test using a first-order Markov Model (MM).

SYNOPSIS

A usage synopsis would go here. Since it is not here, read on.
In section 4.2 in Kruegel and Vignas paper, they ignored the probability information that the MM provided, and produced a binary result. In effect, they were using the constructed MM as a {N,D}FA.

Someday more will be here.

Ideally, we would be using the algorithm from stolcke94bestfirst. Constructing a DFA rather than a NFA in effect has performed most of the state merging that stolcke93hidden do.

Consider also a java or C/C++ implementaion: http://www.ghmm.org/ http://www.run.montefiore.ulg.ac.be/~francois/software/jahmm/

Useful information: http://www.cs.brown.edu/research/ai/dynamics/tutorial/Documents/HiddenMarkovModels.html http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html L R Rabiner and B H Juang, `An introduction to HMMs, IEEE ASSP Magazine, 3, 4-16.

printvcg

printvcg(filehandle)

Print in a form usable by VCG for printing the DFA.

If the filehandle is specified, print there; otherwise, print to STDOUT.
This code was stolen from DFA, and does not know about the probabilities.
load(filehandle)

Load a MM from a file; this is the inverse of "print", and the format we expect is that used in $self->print.

test(tokensref, string, instance)

Test the string of tokens and calculate the probability of the string being seen. At each stage, we get a p in [0,1]. The result is the product of these probabilities.
Note that if a transition cannot be made, we return a 0 probability.

add(tokensref, string, instance)

The collection of tokens (in the list referenced by tokensref) is a complete example of a list that should be accepted by the DFA.

string and instance are IDS::Test framework arguments that we ignore because we do not need them.

WE add the transition from the last token to the (ACCEPT) state.

add_transition(from, token)

Add a transition from one state to another when the specified token is received. It is not an error to try to add an existing transition. In that event, this function quietly returns. If no such transition exists, we look for a transition on the token; if so, we add an edge to the destination node for the existing edge. Finally, if there is no other choice, we create a new state and add the edge.

generalize()

Reduce the number of states in the model.

Our building a DFA rather than a NFA has in effect performed most of the state merging that would have occurred.

XXX We should still be doing some checks for additional merge possibilities.
XXX A proof that the DFA is effectively the NFA with merged states would be useful.