UGM: Matlab code for undirected graphical models
Mark Schmidt (2007)
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 some parts of the code are also available.
- Decoding: Computing the most likely configuration.
- Inference: Computing the partition function and marginal probabilities.
- Sampling: Generating samples from the distribution.
- Parameter Estimation: Given data, computing maximum likelihood (or MAP) estimates of the parameters.
UGM implements the following decoding methods:
The corresponding functions are UGM_Decode_* (where * is the name of the method above).
- Exact: Exact decoding for small graphs with an exhaustive search.
- Chain: Exact decoding for chain-structured graphs with the Viterbi algorithm.
- Tree: Exact decoding for tree- and forest-structured graphs with max-product belief propagation.
- Condition: Decoding when conditioning on some variables (takes another decoding method as input).
- Cutset: Exact decoding for graphs with a small cutset using cutset conditioning.
- Junction: Exact decoding for low-treewidth graphs using junction trees.
- GraphCut: Exact decoding for binary models with sub-modular potentials using graph cuts.
- ICM: Approximate decoding with the iterated conditional modes algorithm.
- Greedy: Approximate decoding with greedy hill-climbing.
- ICMrestart: Approximate decoding with the iterated conditional modes algorithm and restarts.
- Sample: Approximate decoding using sampling (takes a sampling method as input).
- MaxOfMarginals: Approximate decoding using inference (takes an inference method as input).
- LBP: Approximate decoding using max-product loopy belief propagation.
- TRBP: Approximate decoding using max-product tree-reweighted belief propagtion.
- Block_ICM: Approximate decoding using block iterated conditional mode (takes a decoding method as input).
- AlphaBetaSwap: Approximate decoding in pairwise-sub-modular models with alpha-beta swaps.
- AlphaExpansion: Approximate decoding with a generalized triangle inequality with alpha-expansions.
- AlphaExpansionBetaShrink: Approximate decoding with a generalized triangle inequality with alpha-expansion beta-shrink moves.
- IntProg: Exact decoding with an integer programming formulation.
- LinProg: Approximate decoding using a linear programming relaxation.
UGM implements the following inference methods:
The corresponding functions are UGM_Infer_* (where * is the name of the method above).
- Exact: Exact inference for small graphs with exhaustive enumeration.
- Chain: Exact inference for chain-structured graphs with the forward-backward algorithm.
- Tree: Exact inference for tree- and forest-structured graphs with sum-product belief propagation.
- Condition: Inference when conditioning on some variables (takes another inference method as input).
- Cutset: Exact inference for graphs with a small cutset using cutset conditioning.
- Junction: Exact inference for low-treewidth graphs using junction trees.
- Sample: Approximate inference using sampling (takes a sampling method as input).
- ViterbiApx: Approximate inference using decoding (takes a decoding method as input).
- MeanField: Approximate inference using the variational mean field method.
- LBP: Approximate inference using sum-product loopy belief propagation.
- TRBP: Approximate inference using sum-product tree-reweighted belief propagation.
- Block_MF: Approximate inference using block variational mean field (takes an inference method as input).
UGM implements the following sampling methods:
The corresponding functions are UGM_Sample_* (where * is the name of the method above).
- Exact: Exact sampling for small graphs with inverse cumulative distribution transform.
- Chain: Exact sampling for chain-structured graphs with the forward-filter backward-sample algorithm.
- Tree: Exact sampling for tree- and forest-structured graphs with sum-product belief propagation and backward-sampling.
- Condition: Sampling when conditioning on some variables (takes another sampling method as input).
- Cutset: Exact sampling for graphs with a small cutset using cutset conditioning.
- Junction: Exact sampling for low-treewidth graphs using junction trees.
- Gibbs: Approximate sampling using a single-site Gibbs sampler.
- VarMCMC: Approximate sampling using variational Markov chain Monte Carlo.
- Block_Gibbs: Approximate sampling using block Gibbs sampling (takes a sampling method as input).
For parameter estimation, UGM uses a log-linear parameterization and allows training of Markov random fields or conditional random fields in the following scenarios:
- The graph structure can be arbitrary.
- Each node can have a different number of states.
- The parameters can be tied in arbitrary ways.
- The objective function can be the exact likelihood (takes an exact inference method as input), a pseudo-likelihood, or an approximate likelihood (takes an approximate inference method as input).
- Regularization can be added to the objective function.
- Sub-modularity constraints can be placed on the edge potentials.
- Features can be real-valued or binary.
- Features can be used for both nodes and edges.
- The optimization can be done exactly using a deterministic L-BFGS method, approximately with stochastic gradient descent, or exactly using a hybrid approach.
How to use the code
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.
The first set of demos covers exact decoding/inference/sampling:
The second set of demos covers approximate decoding/inference/sampling methods:
- Small: An introduction to UGMs and the tasks of decoding/inference/sampling on a a simple UGM where we can do everything by hand. This tutorial also introduces the edgeStruct used by all the codes.
- Chain: A chain-structured UGM, illustrating how the Markov independence properties present in the chain lead to efficient dynamic programming algorithms for decoding/inference/sampling.
- Tree: A tree-structured UGM, where dynamic
programming methods also apply.
- Condition: A demo that shows how we can
do conditional decoding/inference/sampling, if we know the values of some
of the variables.
- Cutset: Two examples of simple loopy UGMs, where we take advantage of the simplified graph structure after conditioning to perform exact decoding/inference/sampling.
- Junction: A more complicated loopy UGM, where we take advantage of the low treewidth of the graph structure to perform exact decoding/inference/sampling.
- GraphCuts: An example of a complicated loopy UGM, where the use of sub-moodular potentials (over binary data) allows us to perform exact decoding.
The third set of demos covers parameter estimation:
- ICM: A demo showing how to use the iterated
conditional mode algorithm (and other local search algorithms) for approximate decoding.
- MCMC: A demo showing how to use Gibbs sampling for approximate sampling, and how to use sampling methods for approximate decoding/inference.
- Variational: A demo showing how to use the variational mean
field approximation for approximate inference, how to apply loopy belief
propagation for approximate inference/decoding, and how to use the (convex)
tree-reweighted belief propagation algorithms for these same tasks.
- Block: A demo showing how to use 'block' versions several
algorithms to impprove their performance. This includes a block ICM method that gives a
decoding satisfying stronger optimality conditions, a block-Gibbs sampler
that has a lower variance, and a block mean field method for inference that
uses a more complex approximating distribution.
- AlphaBeta: A demo showing how to use alpha-beta swaps, alpha-expansiosn, and alpha-expansion beta-shrink moves for approximate decoding in a model with some conditional sub-modular structure.
- Linprog: A demo showing how to use an integer programming formulation of decoding, as well as the linear programming relaxation of this problem.
- TrainMRF: A demo showing how to train Markov random fields when exact inference is possible. This demo also introduces the nodeMap and edgeMap structures used by all parameter estimation methods.
- TrainCRF: A demo showing how to train conditional random fields when exact inference is possible. This demo also shows how the nodeMap and edgeMap are used in the conditional scenario.
- TrainApprox: A demo showing how to train UGMs with a pseudo-likelihood or variational approximation, for scenarios where exact inference is not tractable.
- TrainSGD: A demo showing how to train conditional random fields with stochastic gradient descent, and with a hybrid deterministic/stochastic L-BFGS method.
The complete set of files for the 2011 version of UGM are available here (for parameter estimation, this package includes the 2009 versions of minFunc and minConf). For updates beyond the 2011 version, see the individual files below. 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:
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.
Here are updates that are not included in the 2011 version of UGM:
- UGM_Junction.zip: Fixed the junction tree methods to allow nodes to have different numbers of states (thanks to Elad Mezuman).
Here are updates that are not included in the 2011 version of UGM:
- UGM_CRF_NLL_Hidden.m: A variant of UGM_CRF_NLL.m that allows hidden/missing values in Y (though it is quite slow because I haven't written a mex version). Setting Y(i,n)=0 indicates that the value is hidden (thanks to Benjamin Marlin, and especially to Lei Shi).
- CRFcell.zip: The function UGM_CRFcell_NLL.m, as well as example_UGM_OCR.m which is a demo showing how to apply UGM to data sets where different examples have different numbers of nodes and/or different graph structures, which was by far the most requested feature to add to UGM.
- UGM_Infer_TRBPC.c: Fixed an indexing bug in the message-passing.
- UGM_ChainFwd.m: Fixed the error when running Viterbi decoding on a chain with only one node (thanks to Simon Lacoste-Julien).
- UGM_CRF_PseudoNLL.m: Fixed the indexing problem for the non-mex version of this code (thanks to Natraj Raman).
- UGM_makeEdgeStruct.m: Fixed the error ("Undefined function or method 'prod' for input arguments of type 'int32'.") when calling prod with an int32 argument for older versions of Matlab (thanks to Nikolai Lebedev).
- example_UGM_quickStart.m: This function is intended to allow new users to quickly see how the UGM data structures and function calls work. In particular, it shows how to use UGM to perform the tasks of decoding/inference/sampling in a tree-structure graphical model, as well as parameter estimation in both MRFs and CRFs. Note that this function requires the UGM_makeMRFmaps.m and UGM_makeCRFmaps.m functions below.
- UGM_makeMRFmaps.m and UGM_makeCRFmaps.m: These functions construct the nodeMap and edgeMap variables required by the 2011 version of UGM that are equivalent to some of the special cases provided by the infoStruct variable used in earlier version of UGM. For example, if you set tied = 1 and ising = 1, then parameters will be shared across nodes and an Ising parameterization will be used. In contrast, setting tied = 0 and ising = 0 will make each node have its own parameters and will use a full parameterization of the node and edge potentials.
- UGM_Sample_Junction.m: Fixed a major bug in the junction tree sampler (made obsolete by the 2013 update to all junction tree codes).
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:
- Replaced the infoStruct with the nodeMap and edgeMap. These allow arbitrary parameter tying and make it easier to have different graph structures for different training examples.
- Added the alpha-expansion and alpha-expansion beta-shrink moves for approximate decoding in models satisfying a generalized triangle inequality, as well as the truncation trick to allow these methods to be applied when this inequality is not satisfied.
- Added a rudimentary implementation of junction trees for decoding/inference/sampling in models with low treewidth.
- The belief propagation code for tree-structured models now uses a proper message-passing schedule.
- The methods based on graph cuts can now be made significantly faster, since they will call the mex
wrapper to the maxflow code if it is found on the Matlab path.
- The graph construction in UGM_Decode_GraphCut was fixed for cases where the edge potentials are asymmetric (thanks to Mohamed Ghalwash).
- The max-product loopy belief propagation code now uses a mex file to speed up the computation (thanks to Hanwang Zhang).
- The tree-reweighted belief propagation codes now use mex files to speed up the computation.
- Added simulated annealing.
- A memory leak was fixed in the max_mult function, and a Matlab version of the function was added (thanks to Uday Kurkure).
- The minSpan function now does something sensible for disconnected graphs.
- The adjacency matrix construction for non-square lattice structures was fixed in the demos (thanks to Calden Wloka and Xuba Zhang).
- The UGM_Decode_ICMrestart function no longer ignores the number of restarts argument (thanks to Hanwang Zhang).
- The code no longer uses repmatC (the performance of repmat has been improved in recent versions of Matlab).
- The UGM_makeEdgeVE function now includes some better documentation (thanks to Adam Nitzan).
- Added the win32 mex files (thanks to Rajnish Kumar Yadav).
- Added the win64 mex files (thanks to Ka-Chun Wong).
- Thanks also to Dana Cobzas, Neil Birkbeck, and Jana Kosecka for other contributions that did not make it into the new version.
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
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.
- Structure Learning in
Random Fields for Heart Motion Abnormality Detection. M. Schmidt, K. Murphy, G. Fung, R. Rosales. CVPR'08.
- Optimizing Costly Functions with Simple Constraints: A Limited-Memory Projected
Quasi-Newton Algorithm. M. Schmidt, E. van den Berg, M. Friedlander, K. Murphy. AISTATS'09.
- Increased Discrimination in Level Set Methods with Embedded Conditional Random Fields. D. Cobzas, M. Schmidt. CVPR'09.
- Modeling Discrete Interventional Data using Directed Cyclic Graphical Models. M. Schmidt, K. Murphy. UAI'09.
- Causal Learning without DAGs. D. Duvenaud, D. Eaton, K. Murphy, M. Schmidt. JMLR W&CP'10
Fast Approximate Energy Minimization via Graph Cuts: Alpha-Expansion
Beta-Shrink Moves. M. Schmidt, K. Alahari. UAI'11.
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