de.jstacs.sequenceScores.statisticalModels.trainable.hmm
Class AbstractHMM

java.lang.Object
  de.jstacs.sequenceScores.statisticalModels.trainable.AbstractTrainableStatisticalModel
      de.jstacs.sequenceScores.statisticalModels.trainable.hmm.AbstractHMM

All Implemented Interfaces:

SequenceScore, StatisticalModel, TrainableStatisticalModel, Storable, Cloneable

Direct Known Subclasses:

HigherOrderHMM

public abstract class AbstractHMM
extends AbstractTrainableStatisticalModel
implements Cloneable, Storable

This class is the super class of all implementations hidden Markov models (HMMs) in Jstacs. The training algorithm of the the HMM is determined by a specialized ParameterSet denoted as HMMTrainingParameterSet.

Author:

Jan Grau, Jens Keilwagen, Michael Scharfe

See Also:

State, Transition

Field Summary

protected double[][]	bwdMatrix matrix for all backward-computed variables; bwdMatrix[l][c] = log P(x_{l+1},...
protected Emission[]	emission The emissions used in the states.
protected int[]	emissionIdx The index of the used emission of each state.
protected boolean[]	finalState An array of switches that contains for each state whether is is a final state or not (cf.
protected boolean[]	forward An array of switches that contains for each state whether the emission is forward or the reverse strand.
protected double[][]	fwdMatrix matrix for all forward-computed variables; fwdMatrix[l][c] = log P(x_1,...
protected String[]	name The names of the states.
protected SafeOutputStream	sostream This is the stream for writing information while training.
static String	START_NODE The String for the start node used in Graphviz annotation.
protected State[]	states The (hidden) states of the HMM.
protected int	threads The number of threads that is internally used.
protected HMMTrainingParameterSet	trainingParameter The ParameterSet containing all Parameters for the training of the HMM.
protected Transition	transition The transitions between all (hidden) states of the HMM.

Fields inherited from class de.jstacs.sequenceScores.statisticalModels.trainable.AbstractTrainableStatisticalModel

alphabets, length

Constructor Summary

protected	AbstractHMM(HMMTrainingParameterSet trainingParameterSet, String[] name, int[] emissionIdx, boolean[] forward, Emission[] emission) This is the main constructor for an HMM.
protected	AbstractHMM(StringBuffer xml) The standard constructor for the interface Storable.

Method Summary

protected abstract void	appendFurtherInformation(StringBuffer xml) This method appends further information to the XML representation.
AbstractHMM	clone() Follows the conventions of Object's clone()-method.
protected abstract void	createHelperVariables() This method instantiates all helper variables that are need inside the model for instance for filling forward and backward matrix, ...
protected double[][]	createMatrixForStatePosterior(int startPos, int endPos) This method creates an empty matrix for the log state posterior.
protected abstract void	createStates() This method creates states for the internal usage.
String[]	decodePath(IntList path) This method decodes any path of the HMM, i.e. it converts the integer representation of the path in a String representation.
static int[][]	decodeStatePosterior(double[][]... statePosterior) The method returns the decoded state posterior, i.e. a sequence of states.
protected void	determineFinalStates() This method determines the final states of the HMM.
protected abstract void	extractFurtherInformation(StringBuffer xml) This method extracts further information from the XML representation.
protected abstract void	fillBwdMatrix(int startPos, int endPos, Sequence seq) This method fills the backward-matrix for a given sequence.
protected abstract void	fillFwdMatrix(int startPos, int endPos, Sequence seq) This method fills the forward-matrix for a given sequence.
protected abstract void	fillLogStatePosteriorMatrix(double[][] statePosterior, int startPos, int endPos, Sequence seq, boolean silentZero) This method fills the log state posterior of Sequence seq in a given matrix.
protected void	finalize()
protected void	fromXML(StringBuffer xml) This method is used by the AbstractHMM(StringBuffer) constructor for creating an instance from an XML representation.
protected double[][]	getFinalStatePosterioriMatrix(double[][] intermediate) This method is used if fillLogStatePosteriorMatrix(double[][], int, int, Sequence, boolean) is used with code>silentZero==true to eliminate the first row.
String	getGraphvizRepresentation(NumberFormat nf) This method returns a String representation of the structure that can be used in Graphviz to create an image.
String	getGraphvizRepresentation(NumberFormat nf, boolean sameTypeSameRank) This method returns a String representation of the structure that can be used in Graphviz to create an image.
String	getGraphvizRepresentation(NumberFormat nf, DataSet data, double[] weight, boolean sameTypeSameRank) This method returns a String representation of the structure that can be used in Graphviz to create an image.
String	getGraphvizRepresentation(NumberFormat nf, DataSet data, double[] weight, HashMap<String,String> rankPatterns) This method returns a String representation of the structure that can be used in Graphviz to create an image.
double	getLogProbFor(Sequence sequence, int startpos, int endpos) Returns the logarithm of the probability of (a part of) the given sequence given the model.
abstract double	getLogProbForPath(IntList path, int startPos, Sequence seq)
double[][][]	getLogStatePosteriorMatrixFor(DataSet data) This method returns the log state posteriors for all sequences of the sample data.
double[][]	getLogStatePosteriorMatrixFor(int startPos, int endPos, Sequence seq) This method returns the log state posterior of all states for a sequence.
int	getNumberOfStates() This method returns the number of the (hidden) states
int	getNumberOfThreads() This method returns the number of threads that is internally used.
protected static RuntimeException	getRunTimeException(Exception e) This method creates an RuntimeException from any other Exception
double[][][]	getStatePosteriorMatrixFor(DataSet data) This method returns the state posteriors for all sequences of the sample data.
double[][]	getStatePosteriorMatrixFor(Sequence seq) This method returns the log state posterior of all states for a sequence.
abstract Pair<IntList,Double>	getViterbiPathFor(int startPos, int endPos, Sequence seq)
Pair<IntList,Double>	getViterbiPathFor(Sequence seq)
Pair<IntList,Double>[]	getViterbiPathsFor(DataSet data) This method returns the viterbi paths and scores for all sequences of the sample data.
protected abstract String	getXMLTag() Returns the tag for the XML representation.
protected void	initTransition(BasicHigherOrderTransition.AbstractTransitionElement... te) This method creates the internal transition.
protected double	logProb(int startpos, int endpos, Sequence sequence) This method computes the logarithm of the probability of the corresponding subsequences.
protected void	provideMatrix(int type, int length) This method invokes the method createHelperVariables() and provides the matrix with given type.
void	setOutputStream(OutputStream o) Sets the OutputStream that is used e.g. for writing information while training.
String	toString() Should give a simple representation (text) of the model as String.
StringBuffer	toXML() This method returns an XML representation as StringBuffer of an instance of the implementing class.
void	train(DataSet data) Trains the TrainableStatisticalModel object given the data as DataSet.

Methods inherited from class de.jstacs.sequenceScores.statisticalModels.trainable.AbstractTrainableStatisticalModel

check, emitDataSet, getAlphabetContainer, getCharacteristics, getLength, getLogProbFor, getLogProbFor, getLogScoreFor, getLogScoreFor, getLogScoreFor, getLogScoreFor, getLogScoreFor, getMaximalMarkovOrder

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface de.jstacs.sequenceScores.statisticalModels.trainable.TrainableStatisticalModel

train

Methods inherited from interface de.jstacs.sequenceScores.statisticalModels.StatisticalModel

getLogPriorTerm

Methods inherited from interface de.jstacs.sequenceScores.SequenceScore

getInstanceName, getNumericalCharacteristics, isInitialized

Field Detail

states

protected State[] states

The (hidden) states of the HMM.

name

protected String[] name

The names of the states.

emissionIdx

protected int[] emissionIdx

The index of the used emission of each state.

forward

protected boolean[] forward

An array of switches that contains for each state whether the emission is forward or the reverse strand. Only of interest for discrete, reverse complementable sequences.

See Also:

ComplementableDiscreteAlphabet

emission

protected Emission[] emission

The emissions used in the states.

transition

protected Transition transition

The transitions between all (hidden) states of the HMM.

fwdMatrix

protected double[][] fwdMatrix

matrix for all forward-computed variables; fwdMatrix[l][c] = log P(x_1,...,x_l,(s_{l-order+1},...,s_l)=c | parameter)

bwdMatrix

protected double[][] bwdMatrix

matrix for all backward-computed variables; bwdMatrix[l][c] = log P(x_{l+1},...,x_L | (s_{l-order+1},...,s_l)=c , parameter)

trainingParameter

protected HMMTrainingParameterSet trainingParameter

The ParameterSet containing all Parameters for the training of the HMM.

sostream

protected SafeOutputStream sostream

This is the stream for writing information while training.

finalState

protected boolean[] finalState

An array of switches that contains for each state whether is is a final state or not (cf. final states).

threads

protected int threads

The number of threads that is internally used.

START_NODE

public static final String START_NODE

The String for the start node used in Graphviz annotation.

See Also:

getGraphvizRepresentation(NumberFormat), Constant Field Values

Constructor Detail

AbstractHMM

protected AbstractHMM(HMMTrainingParameterSet trainingParameterSet,
                      String[] name,
                      int[] emissionIdx,
                      boolean[] forward,
                      Emission[] emission)
               throws CloneNotSupportedException,
                      WrongAlphabetException

This is the main constructor for an HMM.

Parameters:

trainingParameterSet - a ParameterSet containing all Parameters for the training of the HMM

name - the names of the states

emissionIdx - the indices of the emissions that should be used for each state, if null state i will use emission i

forward - a boolean array that indicates whether the symbol on the forward or the reverse complementary strand should be used, if null all states use the forward strand

emission - the emissions

Throws:

CloneNotSupportedException - if trainingParameterSet can not be cloned

WrongAlphabetException - if not all (non-silent) emissions have use the same AlphabetContainer

AbstractHMM

protected AbstractHMM(StringBuffer xml)
               throws NonParsableException

The standard constructor for the interface Storable. Constructs a AbstractHMM out of an XML representation.

Parameters:

xml - the XML representation as StringBuffer

Throws:

NonParsableException - if the AbstractHMM could not be reconstructed out of the StringBuffer xml

Method Detail

initTransition

protected void initTransition(BasicHigherOrderTransition.AbstractTransitionElement... te)
                       throws Exception

This method creates the internal transition.

Parameters:

te - the individual transition elements

Throws:

Exception - if the transition can not handle the current states

getXMLTag

protected abstract String getXMLTag()

Returns the tag for the XML representation.

Returns:

the tag for the XML representation

See Also:

fromXML(StringBuffer), toXML()

toXML

public StringBuffer toXML()

Description copied from interface: Storable

This method returns an XML representation as StringBuffer of an instance of the implementing class.

Specified by:

toXML in interface Storable

Returns:

the XML representation

fromXML

protected void fromXML(StringBuffer xml)
                throws NonParsableException

This method is used by the AbstractHMM(StringBuffer) constructor for creating an instance from an XML representation. This method should never be made public.

Specified by:

fromXML in class AbstractTrainableStatisticalModel

Parameters:

xml - the XML representation

Throws:

NonParsableException - if the XML representation can not be parsed properly

See Also:

AbstractTrainableStatisticalModel.AbstractTrainableStatisticalModel(StringBuffer)

appendFurtherInformation

protected abstract void appendFurtherInformation(StringBuffer xml)

This method appends further information to the XML representation. It allows subclasses to save further parameters that are not defined in the superclass.

Parameters:

xml - the XML representation

extractFurtherInformation

protected abstract void extractFurtherInformation(StringBuffer xml)
                                           throws NonParsableException

This method extracts further information from the XML representation. It allows subclasses to cast further parameters that are not defined in the superclass.

Parameters:

xml - the XML representation

Throws:

NonParsableException - if the information could not be reconstructed out of the StringBuffer xml

clone

public AbstractHMM clone()
                  throws CloneNotSupportedException

Description copied from class: AbstractTrainableStatisticalModel

Follows the conventions of Object's clone()-method.

Specified by:

clone in interface SequenceScore

Specified by:

clone in interface TrainableStatisticalModel

Overrides:

clone in class AbstractTrainableStatisticalModel

Returns:

an object, that is a copy of the current AbstractTrainableStatisticalModel (the member-AlphabetContainer isn't deeply cloned since it is assumed to be immutable). The type of the returned object is defined by the class X directly inherited from AbstractTrainableStatisticalModel. Hence X's clone()-method should work as:
1. Object o = (X)super.clone();
2. all additional member variables of o defined by X that are not of simple data-types like int, double, ... have to be deeply copied
3. return o

Throws:

CloneNotSupportedException - if something went wrong while cloning

createStates

protected abstract void createStates()

This method creates states for the internal usage.

fillFwdMatrix

protected abstract void fillFwdMatrix(int startPos,
                                      int endPos,
                                      Sequence seq)
                               throws Exception

This method fills the forward-matrix for a given sequence.

Parameters:

startPos - the start position (inclusive) in the sequence

endPos - the end position (inclusive) in the sequence

seq - the sequence

Throws:

Exception - if some error occurs during the computation

fillBwdMatrix

protected abstract void fillBwdMatrix(int startPos,
                                      int endPos,
                                      Sequence seq)
                               throws Exception

This method fills the backward-matrix for a given sequence.

Parameters:

startPos - the start position (inclusive) in the sequence

endPos - the end position (inclusive) in the sequence

seq - the sequence

Throws:

Exception - if some error occurs during the computation

getNumberOfThreads

public int getNumberOfThreads()

This method returns the number of threads that is internally used.

Returns:

the number of threads that is internally used

getGraphvizRepresentation

public String getGraphvizRepresentation(NumberFormat nf)

This method returns a String representation of the structure that can be used in Graphviz to create an image.

Parameters:

nf - an instance of NumberFormat for formating the probabilities of the transition

Returns:

a String representation of the structure

See Also:

getGraphvizRepresentation(NumberFormat, DataSet, double[], boolean)

getGraphvizRepresentation

public String getGraphvizRepresentation(NumberFormat nf,
                                        boolean sameTypeSameRank)

This method returns a String representation of the structure that can be used in Graphviz to create an image.

Parameters:

nf - an instance of NumberFormat for formating the probabilities of the transition

sameTypeSameRank - if true, states of the same type, i.e., having the same type of emission, are displayed on the same rank

Returns:

a String representation of the structure

See Also:

getGraphvizRepresentation(NumberFormat, DataSet, double[], boolean)

getGraphvizRepresentation

public String getGraphvizRepresentation(NumberFormat nf,
                                        DataSet data,
                                        double[] weight,
                                        boolean sameTypeSameRank)

This method returns a String representation of the structure that can be used in Graphviz to create an image.

Parameters:

nf - an instance of NumberFormat for formating the probabilities of the transition

data - the data to determine the state posterior; can be null

weight - the weights to weight the determined state posterior; can be null

sameTypeSameRank - if true, states of the same type, i.e., having the same type of emission, are displayed on the same rank

Returns:

a String representation of the structure

getGraphvizRepresentation

public String getGraphvizRepresentation(NumberFormat nf,
                                        DataSet data,
                                        double[] weight,
                                        HashMap<String,String> rankPatterns)

This method returns a String representation of the structure that can be used in Graphviz to create an image.

Parameters:

nf - an instance of NumberFormat for formating the probabilities of the transition

data - the data to determine the state posterior; can be null

weight - the weights to weight the determined state posterior; can be null

rankPatterns - a HashMap contain regular expressions and their corresponding value for the option rank in Graphviz

Returns:

a String representation of the structure

See Also:

HMMFactory.getHashMap()

createMatrixForStatePosterior

protected double[][] createMatrixForStatePosterior(int startPos,
                                                   int endPos)

This method creates an empty matrix for the log state posterior.

Parameters:

startPos - the start position

endPos - the end position

Returns:

an empty matrix for the log state posterior

See Also:

getLogStatePosteriorMatrixFor(int, int, Sequence), fillLogStatePosteriorMatrix(double[][], int, int, Sequence, boolean)

fillLogStatePosteriorMatrix

protected abstract void fillLogStatePosteriorMatrix(double[][] statePosterior,
                                                    int startPos,
                                                    int endPos,
                                                    Sequence seq,
                                                    boolean silentZero)
                                             throws Exception

This method fills the log state posterior of Sequence seq in a given matrix.

Parameters:

statePosterior - the matrix for the log state posterior

startPos - the start position

endPos - the end position

seq - the sequence

silentZero - true if the state posterior for silent states is defined to be zero, otherwise false

Throws:

Exception - if an error occurs during the computation

See Also:

getLogStatePosteriorMatrixFor(int, int, Sequence), createMatrixForStatePosterior(int, int)

getLogStatePosteriorMatrixFor

public double[][] getLogStatePosteriorMatrixFor(int startPos,
                                                int endPos,
                                                Sequence seq)
                                         throws Exception

This method returns the log state posterior of all states for a sequence.

Parameters:

startPos - the start position within the sequence

endPos - the end position within the sequence

seq - the sequence

Returns:

the score for each state an each sequence position

Throws:

Exception - if the state posterior could not be computed, for instance if the model is not trained, ...

getFinalStatePosterioriMatrix

protected double[][] getFinalStatePosterioriMatrix(double[][] intermediate)

This method is used if fillLogStatePosteriorMatrix(double[][], int, int, Sequence, boolean) is used with code>silentZero==true to eliminate the first row.

Parameters:

intermediate - the intermediate (log) state posterior matrix containing one additional row for silent states before the first emission

Returns:

the final (log) state posterior matrix

getStatePosteriorMatrixFor

public double[][] getStatePosteriorMatrixFor(Sequence seq)
                                      throws Exception

This method returns the log state posterior of all states for a sequence.

Parameters:

seq - the sequence

Returns:

the score for each state an each sequence position

Throws:

Exception - if the state posterior could not be computed, for instance if the model is not trained, ...

See Also:

getLogStatePosteriorMatrixFor(int, int, Sequence)

getLogStatePosteriorMatrixFor

public double[][][] getLogStatePosteriorMatrixFor(DataSet data)
                                           throws Exception

This method returns the log state posteriors for all sequences of the sample data.

Parameters:

data - the sequences

Returns:

the log state posterior matrices for all sequences

Throws:

Exception - if the state posterior could not be computed, for instance if the model is not trained, ...

See Also:

getLogStatePosteriorMatrixFor(int, int, Sequence)

getStatePosteriorMatrixFor

public double[][][] getStatePosteriorMatrixFor(DataSet data)
                                        throws Exception

This method returns the state posteriors for all sequences of the sample data.

Parameters:

data - the sequences

Returns:

the state posterior matrices for all sequences

Throws:

Exception - if the state posterior could not be computed, for instance if the model is not trained, ...

See Also:

getStatePosteriorMatrixFor(Sequence)

getViterbiPathFor

public abstract Pair<IntList,Double> getViterbiPathFor(int startPos,
                                                       int endPos,
                                                       Sequence seq)
                                                throws Exception

Parameters:

startPos - the start position within the sequence

endPos - the end position within the sequence

seq - the sequence

Returns:

a Pair containing the viterbi state path and the corresponding score

Throws:

Exception - if the viterbi path could not be computed, for instance if the model is not trained, ...

getViterbiPathFor

public Pair<IntList,Double> getViterbiPathFor(Sequence seq)
                                       throws Exception

Parameters:

seq - the sequence

Returns:

a Pair containing the viterbi state path and the corresponding score

Throws:

Exception - if the viterbi path could not be computed, for instance if the model is not trained, ...

See Also:

getViterbiPathFor(int, int, Sequence)

getViterbiPathsFor

public Pair<IntList,Double>[] getViterbiPathsFor(DataSet data)
                                          throws Exception

This method returns the viterbi paths and scores for all sequences of the sample data.

Parameters:

data - the sequences

Returns:

the viterbi paths and scores for all sequences

Throws:

Exception - if the viterbi paths and scores could not be computed, for instance if the model is not trained, ...

See Also:

getViterbiPathFor(Sequence)

decodePath

public final String[] decodePath(IntList path)

This method decodes any path of the HMM, i.e. it converts the integer representation of the path in a String representation.

Parameters:

path - the path in integer representation

Returns:

the path in String representation, the i-th entry is the i-th visited state

See Also:

getViterbiPathFor(Sequence), getViterbiPathFor(int, int, Sequence)

getLogProbForPath

public abstract double getLogProbForPath(IntList path,
                                         int startPos,
                                         Sequence seq)
                                  throws Exception

Parameters:

path - the given state path

startPos - the start position within the sequence(s) (inclusive)

seq - the sequence(s)

Returns:

the logarithm of the probability for the given path and the given sequence(s)

Throws:

Exception - if the probability for the sequence given path could not be computed, for instance if the model is not trained, ...

createHelperVariables

protected abstract void createHelperVariables()

This method instantiates all helper variables that are need inside the model for instance for filling forward and backward matrix, ...

provideMatrix

protected void provideMatrix(int type,
                             int length)

This method invokes the method createHelperVariables() and provides the matrix with given type. Type 0 stands for fwdMatrix, and type 1 stands for bwdMatrix.

Parameters:

type - the type of the matrix

length - the maximal sequence length

getNumberOfStates

public int getNumberOfStates()

This method returns the number of the (hidden) states

Returns:

the number of the states

getLogProbFor

public double getLogProbFor(Sequence sequence,
                            int startpos,
                            int endpos)
                     throws Exception

Description copied from interface: StatisticalModel

Returns the logarithm of the probability of (a part of) the given sequence given the model. If at least one random variable is continuous the value of density function is returned.

It extends the possibility given by the method StatisticalModel.getLogProbFor(Sequence, int) by the fact, that the model could be e.g. homogeneous and therefore the length of the sequences, whose probability should be returned, is not fixed. Additionally, the end position of the part of the given sequence is given and the probability of the part from position startpos to endpos (inclusive) should be returned.
The length and the alphabets define the type of data that can be modeled and therefore both has to be checked.

Specified by:

getLogProbFor in interface StatisticalModel

Parameters:

sequence - the given sequence

startpos - the start position within the given sequence

endpos - the last position to be taken into account

Returns:

the logarithm of the probability or the value of the density function of (the part of) the given sequence given the model

Throws:

Exception - if the sequence could not be handled (e.g. startpos > , endpos > sequence.length, ...) by the model

NotTrainedException - if the model is not trained yet

getRunTimeException

protected static RuntimeException getRunTimeException(Exception e)

This method creates an RuntimeException from any other Exception

Parameters:

e - the Exception

Returns:

a RuntimeException

logProb

protected double logProb(int startpos,
                         int endpos,
                         Sequence sequence)
                  throws Exception

This method computes the logarithm of the probability of the corresponding subsequences. The method does not check the AlphabetContainer and possible further features before starting the computation.

Parameters:

startpos - the start position (inclusive)

endpos - the end position (inclusive)

sequence - the Sequence(s)

Returns:

the logarithm of the probability

Throws:

Exception - if the model has no parameters (for instance if it is not trained)

train

public void train(DataSet data)
           throws Exception

Description copied from interface: TrainableStatisticalModel

Trains the TrainableStatisticalModel object given the data as DataSet.
This method should work non-incrementally. That means the result of the following series: train(data1); train(data2) should be a fully trained model over data2 and not over data1+data2. All parameters of the model were given by the call of the constructor.

Specified by:

train in interface TrainableStatisticalModel

Overrides:

train in class AbstractTrainableStatisticalModel

Parameters:

data - the given sequences as DataSet

Throws:

Exception - if the training did not succeed

See Also:

DataSet.getElementAt(int), DataSet.ElementEnumerator

setOutputStream

public final void setOutputStream(OutputStream o)

Sets the OutputStream that is used e.g. for writing information while training. It is possible to set o=null, than nothing will be written.

Parameters:

o - the OutputStream

finalize

protected void finalize()
                 throws Throwable

Overrides:

finalize in class Object

Throws:

Throwable

determineFinalStates

protected void determineFinalStates()

This method determines the final states of the HMM.

See Also:

finalState

decodeStatePosterior

public static int[][] decodeStatePosterior(double[][]... statePosterior)

The method returns the decoded state posterior, i.e. a sequence of states. Be careful: For HMMs that do not allow all transitions between states this sequence does not have to be a valid path of the HMM.

Parameters:

statePosterior - the (log) state posterior(s)

Returns:

the decoded state posterior(s)

See Also:

getLogStatePosteriorMatrixFor(int, int, Sequence)

toString

public String toString()

Description copied from interface: TrainableStatisticalModel

Should give a simple representation (text) of the model as String.

Specified by:

toString in interface TrainableStatisticalModel

Overrides:

toString in class Object

Returns:

the representation as String