jml.sequence
Class HMM

java.lang.Object
  extended by jml.sequence.HMM

public class HMM
extends java.lang.Object

A Java implementation of basic Hidden Markov Model. Observation symbols and state symbols are discrete integers starting from 0. It is the responsibility of users to maintain the mapping from IDs to observation symbols and the mapping from IDs to state symbols.

Version:
1.0, Feb. 15th, 2013
Author:
Mingjie Qian

Field Summary
(package private)  double[][] A
          State transition probability matrix.
(package private)  double[][] B
          Observation probability matrix.
(package private)  double epsilon
          Convergence precision.
(package private)  int M
          Number of distinct observation symbols per state.
(package private)  int maxIter
          Maximal number of iterations.
(package private)  int N
          Number of states in the model.
(package private)  int[][] Os
          Observation sequences for training.
(package private)  double[] pi
          Initial state distribution.
(package private)  int[][] Qs
          Hidden state sequences for training data.
 
Constructor Summary
HMM()
          Default constructor.
HMM(int N, int M)
          Construct an HMM with default convergence precision being 1e-6 and maximal number of iterations being 1000.
HMM(int N, int M, double epsilon, int maxIter)
          Construct an HMM.
 
Method Summary
 double[][] allocateMatrix(int nRows, int nCols)
          Allocate memory for a 2D double array.
 double[] allocateVector(int n)
          Allocate continuous memory block for a 1D double array.
 int argmax(double[] V)
          Compute the maximum argument.
 void assignVector(double[] V, double v)
          Assign a 1D double array by a real scalar.
 void assignVector(double[] V1, double[] V2)
          Element-wise assignment operation.
 void clearMatrix(double[][] M)
          Clear all elements of a 2D double array to zero.
 void clearVector(double[] V)
          Clear all elements of a 1D double array to zero.
 void divideAssign(double[] V, double v)
          Element-wise division and assignment operation.
 double evaluate(int[] O)
          Compute P(O|Theta), the probability of the observation sequence given the model, by forward recursion with scaling.
 double evaluate2(int[] O)
          Compute P(O|Theta), the probability of the observation sequence given the model, by forward recursion without scaling.
 void feedData(int[][] Os)
          Feed observation sequences for training.
 void feedLabels(int[][] Qs)
          Feed state sequences for training data.
 double[] genDiscreteDistribution(int n)
          Generate a discrete distribution with sample size of n.
static int[][][] generateDataSequences(int D, int T_min, int T_max, double[] pi, double[][] A, double[][] B)
          Generate observation sequences with hidden state sequences given model parameters and number of data sequences.
 double[][] getA()
           
 double[][] getB()
           
 double[] getPi()
           
private  double[][] initializeA()
           
private  double[][] initializeB()
           
private  double[] initializePi()
           
 void loadModel(java.lang.String filePath)
          Load an HMM model from a file.
static void main(java.lang.String[] args)
           
 void plusAssign(double[] V1, double[] V2)
          Element-wise addition and assignment operation.
 int[] predict(int[] O)
          Predict the best single state path for a given observation sequence using Viterbi algorithm with logarithms.
 int[] predict2(int[] O)
          Predict the best single state path for a given observation sequence using Viterbi algorithm.
 void saveModel(java.lang.String filePath)
          Save this HMM model to a file.
 void setA(double[][] A)
           
 void setB(double[][] B)
           
 void setOs(int[][] Os)
           
 void setPi(double[] pi)
           
 void setQs(int[][] Qs)
           
 void showObservationSequence(int[] O)
          Show an observation sequence.
 void showStateSequence(int[] Q)
          Show a state sequence.
 double sum(double[] V)
          Compute the sum of a 1D double array.
 void sum2one(double[] V)
          Sum a 1D double array to one, i.e., V[i] = V[i] / sum(V).
 void timesAssign(double[] V, double v)
          Element-wise multiplication and assignment operation.
 void timesAssign(double[] V1, double[] V2)
          Element-wise multiplication and assignment operation.
 void train()
          Inference the basic HMM with scaling.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

Os

int[][] Os
Observation sequences for training. Os[n][t] = O_t^n, n = 0,...,D - 1, t = 0,...,T_n - 1.


Qs

int[][] Qs
Hidden state sequences for training data. Qs[n][t] = q_t^n, n = 0,...,D - 1, t = 0,...,T_n - 1.


N

int N
Number of states in the model.


M

int M
Number of distinct observation symbols per state.


pi

double[] pi
Initial state distribution. pi[i] = P(q_1 = S_i).


A

double[][] A
State transition probability matrix. A[i][j] = P(q_{t+1} = S_j|q_t = S_i).


B

double[][] B
Observation probability matrix. B[j][k] = P(v_k|S_j).


epsilon

double epsilon
Convergence precision.


maxIter

int maxIter
Maximal number of iterations.

Constructor Detail

HMM

public HMM()
Default constructor.


HMM

public HMM(int N,
           int M,
           double epsilon,
           int maxIter)
Construct an HMM.

Parameters:
N - number of states in the model
M - number of distinct observation symbols per state
epsilon - convergence precision
maxIter - maximal number of iterations

HMM

public HMM(int N,
           int M)
Construct an HMM with default convergence precision being 1e-6 and maximal number of iterations being 1000.

Parameters:
N - number of states in the model
M - number of distinct observation symbols per state
Method Detail

main

public static void main(java.lang.String[] args)
Parameters:
args -

feedData

public void feedData(int[][] Os)
Feed observation sequences for training. Os[n][t] = O_t^n, n = 0,...,D - 1, t = 0,...,T_n - 1.

Parameters:
Os - observation sequences

feedLabels

public void feedLabels(int[][] Qs)
Feed state sequences for training data. Qs[n][t] = q_t^n, n = 0,...,D - 1, t = 0,...,T_n - 1.

Parameters:
Qs - state sequences

evaluate2

public double evaluate2(int[] O)
Compute P(O|Theta), the probability of the observation sequence given the model, by forward recursion without scaling.

Parameters:
O - an observation sequence
Returns:
P(O|Theta)

evaluate

public double evaluate(int[] O)
Compute P(O|Theta), the probability of the observation sequence given the model, by forward recursion with scaling.

Parameters:
O - an observation sequence
Returns:
P(O|Theta)

argmax

public int argmax(double[] V)
Compute the maximum argument.

Parameters:
V - a double array
Returns:
maximum argument

predict2

public int[] predict2(int[] O)
Predict the best single state path for a given observation sequence using Viterbi algorithm.

Parameters:
O - an observation sequence
Returns:
the most probable state path

predict

public int[] predict(int[] O)
Predict the best single state path for a given observation sequence using Viterbi algorithm with logarithms.

Parameters:
O - an observation sequence
Returns:
the most probable state path

train

public void train()
Inference the basic HMM with scaling. Memory complexity is O(TN) + O(N^2) + O(NM), and computation complexity is O(tDTN^2), where t is the number of outer iterations.


genDiscreteDistribution

public double[] genDiscreteDistribution(int n)
Generate a discrete distribution with sample size of n.

Parameters:
n - sample size
Returns:
a double array with sum 1

initializeB

private double[][] initializeB()

initializeA

private double[][] initializeA()

initializePi

private double[] initializePi()

assignVector

public void assignVector(double[] V,
                         double v)
Assign a 1D double array by a real scalar.

Parameters:
V - a 1D double array
v - a real scalar

clearVector

public void clearVector(double[] V)
Clear all elements of a 1D double array to zero.

Parameters:
V - a double array

clearMatrix

public void clearMatrix(double[][] M)
Clear all elements of a 2D double array to zero.

Parameters:
M - a 2D double array

allocateVector

public double[] allocateVector(int n)
Allocate continuous memory block for a 1D double array.

Parameters:
n - number of elements to be allocated
Returns:
a 1D double array of length n

allocateMatrix

public double[][] allocateMatrix(int nRows,
                                 int nCols)
Allocate memory for a 2D double array.

Parameters:
nRows - number of rows
nCols - number of columns
Returns:
a nRows by nCols 2D double array

divideAssign

public void divideAssign(double[] V,
                         double v)
Element-wise division and assignment operation. It divides the first argument with the second argument and assign the result to the first argument, i.e., V = V / v.

Parameters:
V - a 1D double array
v - a real scalar

timesAssign

public void timesAssign(double[] V,
                        double v)
Element-wise multiplication and assignment operation. It multiplies the first argument with the second argument and assign the result to the first argument, i.e., V = V * v.

Parameters:
V - a 1D double array
v - a real scalar

timesAssign

public void timesAssign(double[] V1,
                        double[] V2)
Element-wise multiplication and assignment operation. It multiplies the first argument with the second argument and assign the result to the first argument, i.e., V1 = V1 .* V2.

Parameters:
V1 - a 1D double array
V2 - a 1D double array

sum

public double sum(double[] V)
Compute the sum of a 1D double array.

Parameters:
V - a 1D double array
Returns:
sum(V)

sum2one

public void sum2one(double[] V)
Sum a 1D double array to one, i.e., V[i] = V[i] / sum(V).

Parameters:
V - a 1D double array

plusAssign

public void plusAssign(double[] V1,
                       double[] V2)
Element-wise addition and assignment operation. It adds the first argument with the second argument and assign the result to the first argument, i.e., V1 = V1 + V2.

Parameters:
V1 - a 1D double array
V2 - a 1D double array

assignVector

public void assignVector(double[] V1,
                         double[] V2)
Element-wise assignment operation. It assigns the first argument with the second argument, i.e., V1 = V2.

Parameters:
V1 - a 1D double array
V2 - a 1D double array

saveModel

public void saveModel(java.lang.String filePath)
Save this HMM model to a file.

Parameters:
filePath - file path to save the model

loadModel

public void loadModel(java.lang.String filePath)
Load an HMM model from a file.

Parameters:
filePath - file Path to load an HMM model from

setQs

public void setQs(int[][] Qs)

setOs

public void setOs(int[][] Os)

setPi

public void setPi(double[] pi)

setA

public void setA(double[][] A)

setB

public void setB(double[][] B)

getPi

public double[] getPi()

getA

public double[][] getA()

getB

public double[][] getB()

showStateSequence

public void showStateSequence(int[] Q)
Show a state sequence.

Parameters:
Q - a state sequence represented by a 1D int array

showObservationSequence

public void showObservationSequence(int[] O)
Show an observation sequence.

Parameters:
O - an observation sequence represented by a 1D int array

generateDataSequences

public static int[][][] generateDataSequences(int D,
                                              int T_min,
                                              int T_max,
                                              double[] pi,
                                              double[][] A,
                                              double[][] B)
Generate observation sequences with hidden state sequences given model parameters and number of data sequences.

Parameters:
D - number of data sequences to be generated
T_min - minimal sequence length
T_max - maximal sequence length
pi - initial state distribution
A - state transition probability matrix
B - observation probability matrix
Returns:
a 3D integer array composed of two 2D integer array with the first one being the observation sequences and second one being the hidden state sequences