UGM: Matlab code for undirected graphical models

Mark Schmidt (2007)

Summary

UGM is a set of Matlab functions implementing various tasks in probabilistic undirected graphical models of discrete data with pairwise (and unary) potentials. Specifically, it implements a variety of methods for the following four tasks: The first three tasks are implemented for arbitrary discrete undirected graphical models with pairwise potentials. The last task focuses on Markov random fields and conditional random fields with log-linear potentials. The code is written entirely in Matlab, although more efficient mex versions of many parts of the code are also available.

Documentation and Tutorial on Markov Random Fields and Conditional Random Fields

The documentation for UGM consists of a series of demos, showing how to use UGM to perform various tasks. These demos also contain some tutorial material on undirected graphical models. In Summer 2015 we also did a crash course on UGMs and the material from these courses is available here.

The first set of demos covers exact decoding/inference/sampling:

The second set of demos covers approximate decoding/inference/sampling methods: The third set of demos covers parameter estimation:

Available Methods

Decoding

UGM has a variety of decoding methods using the functions UGM_Decode_*, where * is one of the following: Exact, Chain, Tree, Condition, Junction, GraphCut, ICM, Greedy, ICMrestart, Sample, MaxOfMarginals, LBP, TRBP, Block_ICM, AlphaBetaSwap, AlphaExpansion, AlphaExpansionBetaShrink, IntProg, LinProg.

Inference

UGM has a variety of inference methods using the functions UGM_Infer_*, where * is one of the following: Exact, Chain, Tree, Condition, Cutset, Junction, Sample, ViterbiApx, MeanField, LBP, TRBP, Block_MF.

Sampling

UGM has a variety of sampling methods using the functions UGM_Sample_*, where * is on of the following: Exact, Chain, Tree, Condition, Cutset, Junction, Gibbs, VarMMC, Block_Gibbs.

Training

UGM has a variety of training methods available for fitting Markov random fields and conditional random fields from data. It uses a log-linear parameterization but otherwise is very flexible: the graph structure can be arbitrary, each node can have a different number of states, the parameter can be tied in arbitrary ways, several approximate training methods like pseudo-likelihood and using approximate inference are available, different forms of regularization can be added, associatve constraints on the objective function can be added, features can be real-valued or binary, features can be used on both nodse and edges, and a variety of optimizers are available.

Download

The last fully-documented release of UGM was in 2011. The complete set of files for the 2011 version are available here (for parameter estimation, this package includes the 2009 versions of minFunc and minConf).

The latest version is avialable as part of a larger package here, which includes many additional features that are not included in the 2011 version.

Alternately, see the individual files below which can be added to the 2011 version to add various features. To significantly speed up the decoding methods based on graph cuts (GraphCuts, AlphaBetaSwap, AlphaExpansion, AlphaExpansionBetaShrink), you can install the mex wrapper to the maxflow code into a sub-directory of the UGM directory.

To run the demos, in Matlab type: 

cd UGM
addpath(genpath(pwd))
example_UGM_*
Where in the above * is the name of one of the demos. For example, to run the Small demo, type example_UGM_Small.

We have included mex files for several operating systems, but if you try to use the mex files on other operating systems you will get errors saying that a file is not found (where the file ends with 'C'). To compile the mex files for other operating systems, run the included mexAll function (then e-mail me the mex files so I can add them to the zip file for others to use). On some architectures the mexAll function does not seem to handle the directory structure properly, and in these cases you can compile the mex files by switching to the mex directory and directly using the mex function to compile the files in that directory.

Citations

If you use this software in a publication, please cite the work using the following information:

Updates

2020

I haven't been updating this page recently, but note that a newer version of UGM is available as part of a larger code package here. This version notably has some additional features that I haven't documented. These are demonstrated in the following examples from that package:

2019

Updated the "mexAll.m" function to be compatible with the current versions of Matlab, by adding the "-compatibleArrayDims" flag (thanks to Yingnan Cui and Aglaia Chan).

2015

Here are updates that are not included in the 2011 version of UGM:

2014

Here are updates that are not included in the 2011 version of UGM:

2013

Here are updates that are not included in the 2011 version of UGM:

2012

Here are updates that are not included in the 2011 version of UGM:

2011

This is a major update to UGM. ALL mex files must be re-compiled to use this new version. In addition, parameter estimation now works in a completely different way to allow arbitrary parameter tying (there is no more infoStruct).

Below is the list of updates:

2009

Although the first line of code for UGM was written in 2007 and I included parts of it in previous packages (e.g. examples of using minFunc, examples of using L1General, Gsparse, and UGMlearn), the first complete and stand-alone version of UGM was released in 2009. Note that parameter estimation in this version works in a completely different way than the current version (while mex files from this older version may be incompatible with the newer version). This original version can still be downloaded here

Debugging Mex Files

UGM makes use of mex files (C functions that Matlab can call) in order to speed up certain computations. Unlike calling a Matlab function where an error will lead to a graceful exact and a trace of where the error occured, errors in mex files can lead to segmentation faults. But, all mex files in UGM have a corresponding Matlab equivalent that (while slower) should perform the exact same computation. This gives a readable version of the mex file that can also be used for debugging. Normally, the Matlab code is ignored and the mex code is used, but you can force the Matlab code to be used and the mex code to be ignored by setting edgeStruct.useMex = 0. So, if UGM gives you a segmentation fault and you cannot find the source of the error, I would recommend re-running the code with edgeStruct.useMex = 0 in order to see why the error is arising.

UGM in Publications

I have used UGM in a few publications: To reference UGM in a publication, please include my name and a link to this website. You may also want to include the date, since I may update the software in the future.

If you have made a modification of UGM or added extra functionality (i.e. an alternate decoding method), please send it to me and I can include it here for others to use.

Mark Schmidt > Software > UGM