**Decoding**: Computing the most likely configuration.**Inference**: Computing the partition function and marginal probabilities.**Sampling**: Generating samples from the distribution.**Training**: Fitting a model to a given dataset.

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

- 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.

- 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.

To run the demos, in Matlab type:

Where in the abovecd UGM addpath(genpath(pwd)) example_UGM_*

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.

- M. Schmidt.
**UGM: A Matlab toolbox for probabilistic undirected graphical models**. http://www.cs.ubc.ca/~schmidtm/Software/UGM.html, 2007.

- UGM_CRF_NLL_HiddenC.zip: Code by James Atwood giving a mex version of the loss for CRFs with hidden variables.
- UGM_makeClampedPotentialsC.c: A variant that fixes a potential indexing bug (thanks to Manuel Claeys Bouuert).

- mexAll_hacked: A variant of mexAll from James Atwood for compiling under octave on OS X.

- hcrf.zip: Code by Konstantinos Bousmalis that uses UGM for the hidden conditional random field model of Quattoni et al. [PAMI, 2007].
- UGM_getEdges.m: Returns a row vector instead of a column vector to increase code readability when using the result.
- UGM_LoopyBP.m: Fixed the NaN caused by an integer-division by nStates in the Matlab version of the code (thanks to Javier Juan Albarracin). Note that this function requires the new
*UGM_getEdges.m*function above. - UGM_Junction.zip: Fixed the junction tree methods to allow nodes to have different numbers of states (thanks to Elad Mezuman). Note that this function requires the new
*UGM_getEdges.m*function above.

- 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).

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.

- 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
- Generalized Fast Approximate Energy Minimization via Graph Cuts: Alpha-Expansion Beta-Shrink Moves. M. Schmidt, K. Alahari. UAI'11.
- Hybrid Deterministic-Stochastic Methods for Data Fitting. M. Friedlander, M. Schmidt, SISC'12.

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