org.jscience.computing.hmm
Class HMM

java.lang.Object
  extended by org.jscience.computing.hmm.HMM

public class HMM
extends java.lang.Object

Implements a hidden Markov model and its algorithms including Forward-Backward, Viterbi, K-means, Baum-Welch, and Kullback-Leibler distance measure.


Field Summary
 double[][] a
          transition probabilities
 double[][] b
          emission probabilities
 int dimensions
          number of dimensions
 int numStates
          number of states
 double[] pi
          initial state probabilities
 int sigmaSize
          size of output vocabulary
 double[][] V
          output vocabulary
 
Constructor Summary
HMM(int numStates, int sigmaSize)
          Class constructor.
HMM(int numStates, int sigmaSize, int dimensions)
          Class constructor.
 
Method Summary
 double[][] backwardProc(int[] o)
          Calculation of Backward variables b(i,t) for state i at time t for sequence o with the current HMM parameters.
 void baumWelch(int[] o, int steps)
          Baum-Welch algorithm for hidden Markov models.
 int[] convert(double[][] sequence, int D, int T)
          Converts a sequence of actually values into their corresponding indices based on the vocabulary of this HMM.
 double[][] forwardProc(int[] o)
          Calculation of Forward variables f(i,t) for state i at time t for sequence o with the current HMM parameters.
 double gamma(int i, int t, int[] o, double[][] fwd, double[][] bwd)
          Calculation of gamma_t(i), which is the probability P(i_t = s_i | o, hmm), that is, the probability of being in state i at time given observation sequence o and this HMM.
 double hmmDistance(HMM hmm2)
          Calculates the distance between two hidden Markov models using the Kullback-Leibler distance measure.
static HMM kmeansLearner(java.lang.String data, int N, int steps)
          K-means algorithm for hidden Markov models.
static HMM load(java.lang.String filename)
          Loads an HMM from a file.
 int[] observationGeneration(int length)
          Generates an observation sequence of a given length using this HMM.
 void print()
          Prints all the parameters of this HMM.
 double[][] viterbi(int[] o)
          Viterbi algorithm for hidden Markov models.
 void write(java.lang.String filename)
          Writes this HMM to a file.
 double xi(int t, int i, int j, int[] o, double[][] fwd, double[][] bwd)
          Calculation of xi_t(i, j), which is the probability P(i_t = s_i, i_t+1 = s_j | o, hmm), that is, the probability of being in state i at time t and state j at time t+1 given observation sequence o and this HMM.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

numStates

public int numStates
number of states


sigmaSize

public int sigmaSize
size of output vocabulary


dimensions

public int dimensions
number of dimensions


V

public double[][] V
output vocabulary


pi

public double[] pi
initial state probabilities


a

public double[][] a
transition probabilities


b

public double[][] b
emission probabilities

Constructor Detail

HMM

public HMM(int numStates,
           int sigmaSize)
Class constructor. Initializes an HMM given number of states and output vocabulary size.

Parameters:
numStates - number of states
sigmaSize - size of output vocabulary

HMM

public HMM(int numStates,
           int sigmaSize,
           int dimensions)
Class constructor. Initializes an HMM a given number of states, output vocabulary size, and number of dimensions for its observation symbols.

Parameters:
numStates - number of states
sigmaSize - size of output vocabulary
dimensions - number of dimensions
Method Detail

baumWelch

public void baumWelch(int[] o,
                      int steps)
Baum-Welch algorithm for hidden Markov models. Given an observation sequence o, it will train this HMM using o to increase the probability of this HMM generating o.

Parameters:
o - the observation sequence
steps - the number of iterations performed

forwardProc

public double[][] forwardProc(int[] o)
Calculation of Forward variables f(i,t) for state i at time t for sequence o with the current HMM parameters.

Parameters:
o - the observation sequence
Returns:
a 2d array containing Forward variables f(i,t) over states and time

backwardProc

public double[][] backwardProc(int[] o)
Calculation of Backward variables b(i,t) for state i at time t for sequence o with the current HMM parameters.

Parameters:
o - the observation sequence
Returns:
a 2d array containing Backward variables b(i,t) over states and time

xi

public double xi(int t,
                 int i,
                 int j,
                 int[] o,
                 double[][] fwd,
                 double[][] bwd)
Calculation of xi_t(i, j), which is the probability P(i_t = s_i, i_t+1 = s_j | o, hmm), that is, the probability of being in state i at time t and state j at time t+1 given observation sequence o and this HMM.

Parameters:
t - the time
i - the number of state s_i
j - the number of state s_j
o - the observation sequence
fwd - the Forward variables for o
bwd - the Backward variables for o
Returns:
P(i_t = s_i,i_t+1 = s_j | o,hmm)

gamma

public double gamma(int i,
                    int t,
                    int[] o,
                    double[][] fwd,
                    double[][] bwd)
Calculation of gamma_t(i), which is the probability P(i_t = s_i | o, hmm), that is, the probability of being in state i at time given observation sequence o and this HMM.

Parameters:
i - the number of state s_i
t - the time
o - the observation sequence
fwd - the Forward variables for o
bwd - the Backward variables for o
Returns:
P(i_t = s_i | o,hmm)

viterbi

public double[][] viterbi(int[] o)
Viterbi algorithm for hidden Markov models. Given an observation sequence o, Viterbi finds the best possible state sequence for o on this HMM, along with the state optimized probability.

Parameters:
o - the observation sequence
Returns:
a 2d array consisting of the minimum cost, U, at position (0,0) and the best possible path beginning at (1,0). The state optimized probability is Euler's number raised to the power of -U.

kmeansLearner

public static HMM kmeansLearner(java.lang.String data,
                                int N,
                                int steps)
                         throws java.io.IOException
K-means algorithm for hidden Markov models. Given training data, this algorithm will classify the data into a specified number of states, then using the final classification, calculate initial, transition, and bias probabilities.

Parameters:
data - the filename of training data file
N - the number of states
steps - the number of iterations
Returns:
DOCUMENT ME!
Throws:
java.io.IOException - If training data file is invalid

hmmDistance

public double hmmDistance(HMM hmm2)
Calculates the distance between two hidden Markov models using the Kullback-Leibler distance measure. The models should have the same size vocabulary.

Parameters:
hmm2 - the hidden Markov model that will be compared against this HMM
Returns:
the symmetric distance between this HMM and hmm2 (if their vocabulary size differs, -1 is returned)

observationGeneration

public int[] observationGeneration(int length)
Generates an observation sequence of a given length using this HMM.

Parameters:
length - the length of the observation sequence to be generated
Returns:
the generated observation sequence

convert

public int[] convert(double[][] sequence,
                     int D,
                     int T)
Converts a sequence of actually values into their corresponding indices based on the vocabulary of this HMM. Any time a hidden Markov model algorithm whose input involves an observation sequence is used, the observation sequence should be converted to indices if it's not already.

Parameters:
sequence - the observation sequence (actual values)
D - the number of dimensions of sequence
T - the length of sequence
Returns:
the observation sequence as indices

print

public void print()
Prints all the parameters of this HMM. Parameters include initial, transition, and output probabilities.


load

public static HMM load(java.lang.String filename)
                throws java.io.IOException
Loads an HMM from a file. A new HMM is created and the read values are stored as the HMM parameters. Returned is the new HMM.

Parameters:
filename - name of file to read the HMM from
Returns:
HMM loaded from the given file
Throws:
java.io.IOException - if the file format is incorrect

write

public void write(java.lang.String filename)
           throws java.io.IOException
Writes this HMM to a file. Information written includes the number of states, output vocabulary size, number of dimensions (-1 if not used), initials, transitions, biases, and, if it was used, the output vocabulary.

Parameters:
filename - name of file to write this HMM to
Throws:
java.io.IOException - if a problem occurred while writing to the file