Conditional factor graph model
The grante library is a complete solution for probabilistic discrete factor graph models. In the library factor graphs specify probabilistic distributions over sets of discrete random variables. The distributions can be parametrized in a flexible way and these parameters can be estimated from training data. To make predictions using factor graphs the library contains a large number of different inference methods for both probabilistic inference of marginal distributions and for discrete energy minimization to infer the most likely configuration of unobserved variables.
For a detailed description of most of the algorithms implemented, please refer to the publications section.
grante includes source codes for the following functionalities:
- Factor graph representation for discrete state models
- Unary, pairwise, and high-order factors
- Support for linear data-dependent factors and parameter sharing in factors
- Support for complex tying patterns within factor energies (symmetry, sparse energy tables, Potts, etc.)
- Support for non-linear data-dependent factors (e.g. RBF networks)
- Support for sparse factor data and for shared data among multiple factors
- Multi-core support through OpenMP
- Few dependencies: a C++0x compiler (MSVC 2010 or GCC 4.5) is needed to compile the library, and boost, version 1.40 or higher is required
- Exact inference, sampling and MAP for tree-structured factor graphs
- Naive Gibbs sampling inference for general factor graphs
- Sum-product and max-product Loopy Belief Propagation, sequential and parallel schedules
- Structured Mean Field for v-acyclic decompositions
- Annealed Importance Sampling (AIS) inference for general factor graphs
- Generalized Swendsen-Wang MCMC inference for pairwise factor graphs where each variable has the same state space
- Approximate MAP-MRF Linear Programming inference (tree-based)
- Approximate MAP-MRF inference by simulated annealing
- Min-sum/sum-product diffusion
- Conditioning of distributions by discrete observations and factor-decomposable expectations
Learning and Estimation
Parameters can be estimated for every model that can be specified in the library.
- Maximum (Conditional) Likelihood Learning for tree-structured factor graphs
- Maximum Pseudolikelihood Learning for general factor graphs
- Maximum Composite Likelihood Learning for general factor graphs specialized variant for 4-neighborhood grid graphs
- Contrastive divergence learning from fully observed and partially observed data
- Structured SVM for factor-decomposable loss functions (batch and stochastic training)
- Structured Perceptron (averaged)
- Prior distributions (and regularizers): multivariate Normal (L2), multivariate Laplace (L1), multivariate Student-t, multivariate Hyperbolic
- Expectation Maximization (EM) for partially observed data
- Barzilai-Borwein method for unconstrained differentiable minimization
- Limited memory BFGS method for unconstrained differentiable minimization
- FISTA composite minimization method for sparsity priors
- Approximately optimal v-acyclic decompositions of factor graphs
- Approximate tree-covering decomposition
- Matlab interface for learning, inference, and sampling
- Native C++ interface
Showcase of a few C++ API examples from the test cases.
// ... // Parameter estimation using Maximum Likelihood Grante::MaximumLikelihood mle(&model); mle.SetupTrainingData(training_data, inference_methods); mle.AddPrior("pairwise", new Grante::NormalPrior(10.0, w.size())); mle.Train(1e-5); // ... // ... // Inference using loopy belief propagation Grante::BeliefPropagation bpinf(&fg); bpinf.PerformInference(); std::cout << "BP log_z " << bpinf.LogPartitionFunction() << std::endl; const std::vector<double>& bp_fac0 = bpinf.Marginal(0); // ... // ... // Empirical risk minimization training using Structured SVM Grante::StructuredSVM ssvm_s(&model, 100.0, "bmrm"); ssvm_s.AddPrior("pairwise", new Grante::NormalPrior(10.0, w.size())); ssvm_s.SetupTrainingData(instances, loss, inference_methods); ssvm_s.Train(1e-4, 100); // ...
Example use of the Matlab interface to sample from a 2D Ising model using Gibbs sampling.
% Define model with a pairwise factor type model=; model.factor_types(1).name = 'pw'; num_class=5; % 5 labels for each pixel model.factor_types(1).card = [num_class, num_class]; % Define pairwise Potts potential strength = 1/3; model.factor_types(1).weights = strength*ones(num_class,num_class); model.factor_types(1).weights = model.factor_types(1).weights - ... 2.0*diag(strength*ones(num_class,1)); % Build factor graph fg=; xdim = 64; ydim = 64; fg.card=num_class*ones(1, ydim*xdim); % Set of random variables % Instantiate pairwise factors num_factors=(ydim-1)*xdim + (xdim-1)*ydim; vfg=cell(1,num_factors); fg.factors=struct('type',vfg,'vars',vfg,'data',vfg); fi=1; for yi=1:ydim for xi=1:xdim var_id=(xi-1)*ydim+yi; % column-major if yi > 1 % vertical pairwise edge fg.factors(fi).type='pw'; fg.factors(fi).vars=[var_id-1, var_id]; fg.factors(fi).data=; fi=fi+1; end if xi > 1 % horizontal pairwise edge fg.factors(fi).type='pw'; fg.factors(fi).vars=[var_id-ydim, var_id]; fg.factors(fi).data=; fi=fi+1; end end end % Produce 100 samples from the probability distribution options=; options.gibbs_burnin = 1000; options.gibbs_spacing = 100; [states] = grante_sample(model, fg, 'gibbs', 100, options);
Distribution: source code, documentation, examples
- Microsoft Research Download (0.6Mb)
License: The software is licensed under the Microsoft Research License Agreement (MSR-LA). A copy of the license document is included in the distribution.
Installation: see the INSTALL.txt file included in the distribution.
- Sebastian.Nowozin@microsoft.com, author of the library.
If you have comments or questions, please feel free to contact me. Thanks!