General Conditional Random Field (CRF) Toolbox for Matlab

Written by Kevin Murphy, 2004.
Last updated 20 January 2006.

This toolbox supports inference and learning for CRFs, with the following topologies: chains, 2D lattices, arbitrary graphs. It assumes all potentials are pairwise. Inference is done using belief propagation (my BPMRF2 and BPlattice code). For chains and trees, this is exact, otherwise it is approximate.

Download

Click here Unziping creates a directory called CRFall, which contains several subdirectories.

This code contains netlab 3.3 bundled in.

Installation

Assuming you unzip it to C:/CRFall...

>> addpath(genpath('C:/CRFall'))
>> testCRF

This will run various simple 1D and 2D demos. Look at the source code for more details...

Documentation

The code is modelled on netlab.

Represenation

Several kinds of CRF structures are supported:

crfchain for 1D chains (in CRF1D)
crf2Ddemo for 2D lattices (in CRF2D)
crf for general graphs (in CRF)

All models have potentials defined as follows:

For local evidence for node i in state qi:
```
  phi{i}(qi) = exp[ sum_d w{i}(d,qi) f{i}(d) ]
```
where f{i}(d) is the d'th element of the feature vector for node i and w{i}(d, qi) is the weight matrix representing the compatibility of feature d to state qi.
For hidden edge e conecting nodes i and j in states qi, qj:
```
   psi{e}(qi,qj) is a table.
```
Note that the current implementation does not support data-dependent edge potnetials. Also, the edge potentials take O(K^2) space to represent, although they can be tied.

Inference

crfchain always uses crfchaininfer (forwards-backwards) for inference. For general CRFs, crfinfer can call several possible inference engines:

BP (belief propagation), which is exact for chains and trees
Exact-2D (by converting the 2D lattice to an HMM - this only works for small grids)
Graph cuts: to be added.

To use an inference engine, you have to call its constructor. For the 2D case, you can proceed as follows. To specify an infernece engine, do the following

net.infEngineName = 'lattice2hmmCell'; % exact 
net.infEngineName = 'bp_mrf2_lattice';
net.infEngineName = 'bploopy';

Then call crf2DdemoInfEngine, which will call one of

lattice2hmmCellEngine
bp_mrf2_lattice2Engine
bploopyEngine.

(Unfortunately these constructors have different arguments.)
Once these structures are initialized, crfErrAndGrad will call

lattice2hmmCellInfer
bp_mrf2_latticeInfer
bploopyInfer

as appropriate.

Learning

Currently we support the following max likelihood parameter learning engines. crfchaintrain has a limited number of gradient-based methods. crf2DdemoTrain has several more gradient-based methods.

The gradient methods use the following pieces:

crfpack to extract all the parameters from the CRF structure into an initial parameter vector.
crfunpack to store the final parameter vector inside the CRF structure.
Some function to compute the gradient such as crfchainErrAndGrad or in general crfErrAndGrad. The 'net' crf structure contains the name of the inference engine internally.
Some gradient based optimizer (eg fminsearch).