jml.sequence
Class CRF

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

public class CRF
extends java.lang.Object

A Java implementation for the basic Conditional Random Field (CRF).

Version:
1.0, Feb. 22ed, 2013
Author:
Mingjie Qian

Field Summary
(package private)  int d
          Number of parameters or number of features
(package private)  int D
          Number of data sequences for training.
(package private)  double epsilon
          Convergence precision.
(package private)  org.apache.commons.math.linear.RealMatrix[][][] Fs
          A 3D RealMatrix array, where F[k][i][j] is the sparse feature matrix for the j-th feature of the k-th observation sequence at position i, i.e., f_{j}^{{\bf x}_k, i}.
(package private)  int maxIter
          Maximal number of iterations.
(package private)  int numStates
          Number of states in the state space.
(package private)  double sigma
          Regularization parameter
(package private)  int startIdx
          Index for the start state in the state space.
(package private)  org.apache.commons.math.linear.RealMatrix W
          d x 1 parameter vector.
(package private)  int[][] Ys
          A 2D integer array, where Ys[k][i] is the label index for the label of the k-th training data sequence at position i in the label space.
 
Constructor Summary
CRF()
          Constructor for a CRF instance.
CRF(double epsilon)
          Constructor for a CRF instance.
CRF(int d)
          Constructor for a CRF instance.
CRF(int d, double epsilon)
          Constructor for a CRF instance.
 
Method Summary
 org.apache.commons.math.linear.RealMatrix backwardRecursion4Viterbi(org.apache.commons.math.linear.RealMatrix[] Ms)
          Alternative backward recursion with scaling for the Viterbi algorithm.
 org.apache.commons.math.linear.RealMatrix computeFeatureVector(org.apache.commons.math.linear.RealMatrix[][] Fs, int[] Ys)
          Compute global feature vector for a data sequences Fs with label Ys.
 double computeObjectiveFunctionValue(boolean calcGrad, org.apache.commons.math.linear.RealMatrix Grad, org.apache.commons.math.linear.RealMatrix W)
          Compute the objective function value (the mean log-likelihood on training data for CRFs).
 org.apache.commons.math.linear.RealMatrix[] computeTransitionMatrix(org.apache.commons.math.linear.RealMatrix[][] Fs)
          Compute transition matrix set, i.e., {M^{\bf x}_i}, i = 1, 2, ..., n_x
 void feedData(org.apache.commons.math.linear.RealMatrix[][][] Fs)
          Feed data sequences for training.
 void feedLabels(int[][] Ys)
          Feed labels for training data sequences.
static java.lang.Object[] generateDataSequences(int D, int n_min, int n_max, int d, int N, double sparseness)
          Generate random data sequences to train a CRF model.
 void loadModel(java.lang.String filePath)
          Load the model from a file.
static void main(java.lang.String[] args)
           
 int[] predict(org.apache.commons.math.linear.RealMatrix[][] Fs)
          Predict the single best label sequence given the features for an observation sequence by Viterbi algorithm.
 int[] predict2(org.apache.commons.math.linear.RealMatrix[][] Fs)
          Predict the single best label sequence given the features for an observation sequence by Viterbi algorithm without normalization.
 void saveModel(java.lang.String filePath)
          Save the model to a file.
 void train()
          Estimate parameters for the basic CRF by a maximum conditional log-likelihood estimation principle.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

Fs

org.apache.commons.math.linear.RealMatrix[][][] Fs
A 3D RealMatrix array, where F[k][i][j] is the sparse feature matrix for the j-th feature of the k-th observation sequence at position i, i.e., f_{j}^{{\bf x}_k, i}.


D

int D
Number of data sequences for training.


d

int d
Number of parameters or number of features


numStates

int numStates
Number of states in the state space.


startIdx

int startIdx
Index for the start state in the state space.


Ys

int[][] Ys
A 2D integer array, where Ys[k][i] is the label index for the label of the k-th training data sequence at position i in the label space.


W

org.apache.commons.math.linear.RealMatrix W
d x 1 parameter vector.


epsilon

double epsilon
Convergence precision.


sigma

double sigma
Regularization parameter


maxIter

int maxIter
Maximal number of iterations.

Constructor Detail

CRF

public CRF()
Constructor for a CRF instance.


CRF

public CRF(double epsilon)
Constructor for a CRF instance.

Parameters:
epsilon - convergence precision

CRF

public CRF(int d)
Constructor for a CRF instance.

Parameters:
d - number of feature functions

CRF

public CRF(int d,
           double epsilon)
Constructor for a CRF instance.

Parameters:
d - number of feature functions
epsilon - convergence precision
Method Detail

main

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

feedData

public void feedData(org.apache.commons.math.linear.RealMatrix[][][] Fs)
Feed data sequences for training.

Parameters:
Fs - a 3D RealMatrix array, where F[k][i][j] is the sparse feature matrix for the j-th feature of the k-th observation sequence at position i, i.e., f_{j}^{{\bf x}_k, i}

feedLabels

public void feedLabels(int[][] Ys)
Feed labels for training data sequences.

Parameters:
Ys - a 2D integer array, where Ys[k][i] is the label index for the label of the k-th training data sequence at position i in the label space

generateDataSequences

public static java.lang.Object[] generateDataSequences(int D,
                                                       int n_min,
                                                       int n_max,
                                                       int d,
                                                       int N,
                                                       double sparseness)
Generate random data sequences to train a CRF model.

Parameters:
D - number of data sequences to be generated
n_min - minimal length for the randomly generated data sequences
n_max - maximal length for the randomly generated data sequences
d - number of feature functions
N - number of states
sparseness - sparseness for the feature matrices
Returns:
a data label pair res[2], res[0] is the data sequences and res[1] is the corresponding label sequences

train

public void train()
Estimate parameters for the basic CRF by a maximum conditional log-likelihood estimation principle.


computeObjectiveFunctionValue

public double computeObjectiveFunctionValue(boolean calcGrad,
                                            org.apache.commons.math.linear.RealMatrix Grad,
                                            org.apache.commons.math.linear.RealMatrix W)
Compute the objective function value (the mean log-likelihood on training data for CRFs). Gradient is also calculated if required.

Parameters:
calcGrad - if gradient required
Grad - gradient to be assigned in place if required
W - model parameters
Returns:
objective function value

predict2

public int[] predict2(org.apache.commons.math.linear.RealMatrix[][] Fs)
Predict the single best label sequence given the features for an observation sequence by Viterbi algorithm without normalization.

Parameters:
Fs - a 2D RealMatrix array, where F[i][j] is the sparse feature matrix for the j-th feature of the observation sequence at position i, i.e., f_{j}^{{\bf x}, i}
Returns:
the single best label sequence for an observation sequence

predict

public int[] predict(org.apache.commons.math.linear.RealMatrix[][] Fs)
Predict the single best label sequence given the features for an observation sequence by Viterbi algorithm.

Parameters:
Fs - a 2D RealMatrix array, where F[i][j] is the sparse feature matrix for the j-th feature of the observation sequence at position i, i.e., f_{j}^{{\bf x}, i}
Returns:
the single best label sequence for an observation sequence

computeTransitionMatrix

public org.apache.commons.math.linear.RealMatrix[] computeTransitionMatrix(org.apache.commons.math.linear.RealMatrix[][] Fs)
Compute transition matrix set, i.e., {M^{\bf x}_i}, i = 1, 2, ..., n_x

Parameters:
Fs - A 2D RealMatrix array, where F[i][j] is the sparse feature matrix for the j-th feature of the observation sequence at position i, i.e., f_{j}^{{\bf x}, i}
Returns:
a transition matrix sequences of length n_x

computeFeatureVector

public org.apache.commons.math.linear.RealMatrix computeFeatureVector(org.apache.commons.math.linear.RealMatrix[][] Fs,
                                                                      int[] Ys)
Compute global feature vector for a data sequences Fs with label Ys.

Parameters:
Fs - a 2D RealMatrix array, where F[i][j] is the sparse feature matrix for the j-th feature of the observation sequence at position i, i.e., f_{j}^{{\bf x}, i}
Ys - a 1D integer array, where Ys[i] is the label index in the label space for the label at position i for the data sequence
Returns:
global feature vector

backwardRecursion4Viterbi

public org.apache.commons.math.linear.RealMatrix backwardRecursion4Viterbi(org.apache.commons.math.linear.RealMatrix[] Ms)
Alternative backward recursion with scaling for the Viterbi algorithm.

Parameters:
Ms - a set of transition matrices, i.e., {M^{\bf x}_i}, i = 1, 2, ..., n_x
Returns:
scaled backward matrix variable {\bf \tilde \beta}(y_i, i)

saveModel

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

Parameters:
filePath - file path to save the model

loadModel

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

Parameters:
filePath - file Path to load the model from