org.jscience.computing.hmm
Class HMM

java.lang.Object
  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