drwnPGM

Class List for drwnPGM

• drwnFactorGraph : Container and utility functions for factor graphs.
• drwnFactorGraphUtils : Utility functions for factor graphs.
• drwnFactorOperation : Base class for implementing various operations on table factors. The derived classes store mappings between factor entries making them very fast for iterative algorithms.
• drwnFullAssignment : defines a complete assignment to all variables in the universe
• drwnGraphUtils : Generic graph utilities.
• drwnInference : Interface for various (marginal) inference algorithms.
• drwnMAPInference : Interface for various MAP inference (energy minimization) algorithms.
• drwnMAPInferenceFactory : Factory for creating drwnMAPInference objects.
• drwnMaxFlow : Interface for maxflow/min-cut algorithms (for minimizing submodular quadratic pseudo-Boolean functions)
• drwnPartialAssignment : defines an assignment to a subset of the variables
• drwnTableFactor : Factor which stores the value of each assignment explicitly in table form.
• drwnTableFactorMapping : Creates a mapping between entries in two tables.
• drwnVarUniverse : Data structure for definining the random variables (name and cardinality) for a given problem instance.

Note

The current version of Darwin includes graphical model inference routines such as max-product message passing. Future release will also include learning algorithms for log-linear CRF models.

Max-flow/Min-cut

drwnMaxFlow and derived classes implement algorithms for solving the maxflow/mincut problem on directed graphs (see http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem). This is particularly useful for minimizing submodular quadratic pseudo-Boolean functions.

The following example shows how to find the value of the minimum st-cut on a simple graph.

drwnEdmondsKarpMaxFlow graph;  // create graph

graph.addNodes(5);             // add five (internal) nodes
graph.addSourceEdge(0, 3);     // add edges from source
graph.addSourceEdge(2, 3);
graph.addEdge(0, 1, 4);        // add internal edges
graph.addEdge(1, 2, 1);
graph.addEdge(1, 3, 2);
graph.addEdge(2, 3, 2);
graph.addEdge(2, 4, 6);
graph.addTargetEdge(3, 1);     // add edges to target (sink)
graph.addTargetEdge(4, 9);

double mincut = graph.solve(); // should be 5.0

Table Factors and Factor Operations

Darwin provide a suite of routines and datastructures for learning and inference in graphical models (or energy functions). Variables in the graphical model are defined by the drwnVarUniverse object. An instance of this object should be created once and shared between all objects in the graphical model.

The most basic entity in a graphical model is the factor. The drwnFactor class defines the interface for factors. The derived drwnTableFactor class provides storage for table factors, which explicitly store the value for each variable assignment. Operations on these factors are executed by classes derived from drwnFactorOperation. The advantage of using these classes is that they can cache mappings between table entries for fast execution in interative algorithms.

The following code provides an example of multiplying two factors and then marginalizing out one of the variables. Note that the variable names are optional and only provided for convenience—most large-scale applications will not make use of them and reference variables by index.

// define variables
drwnVarUniversePtr universe(new drwnVarUniverse());
universe->addVariable(3, "a");   // variable "a" has cardinality 3
universe->addVariable(2, "b");   // variable "b" has cardinality 2
universe->addVariable(2, "c");   // variable "c" has cardinality 2

// define factor over "a" and "b"
drwnTableFactor psiA(universe);
psiA.addVariable("b", "a", NULL);   // or psiA.addVariable(1); psiA.addVariable(0);
psiA[0] = 0.5; psiA[1] = 0.8; psiA[2] = 0.1;
psiA[3] = 0.0; psiA[4] = 0.3; psiA[5] = 0.9;

// define factor over "b" and "c"
drwnTableFactor psiB(universe);
psiB.addVariables("c", "b", NULL);  // or psiB.addVariable(2); psiB.addVariable(1);
psiB[0] = 0.5; psiB[1] = 0.7;
psiB[2] = 0.1; psiB[3] = 0.2;

// multiply factors together
drwnTableFactor psiC(universe);
drwnFactorProductOp(&psiC, &psiA, &psiB).execute();

// marginalize "b"
drwnTableFactor psiD(universe);
drwnFactorMarginalizeOp(&psiD, &psiC, universe->findVariable("b")).execute();

// show results
psiD.dump();

Factor operations can either be executed using temporary objects or, if executed multiple times, as named objects. For example the following two code segments have the save affect:

// operation using temporary object
drwnPlusEqualsOp(&sum, &summand).execute();

// operation using named object
drwnPlusEqualsOp addOp(&sum, &summand);
addOp.execute();

These operations form the basis of many of the inference routines (see Graphical Model Inference and MAP Inference (Energy Minimization)).

Graphical Model Inference

Graphical Model inference is conducted on factor graphs (drwnFactorGraph) and involves computing marginals (or approximate marginals) on a structured probability distribution,

The drwnInference class defines the interfaces for many of the inference algorithms implemented in Darwin. The following code snippet shows an example of loading a factor graph and running the sum-product inference algorithm on it.

// load graph
drwnFactorGraph graph;
graph.read(filename);

// run inference
drwnSumProdInference inf(graph);
inf.inference();

// show marginal over the first variable
drwnTableFactor belief = inf[0];
belief.dump();

See Also

MAP Inference (Energy Minimization)

MAP Inference (Energy Minimization)

MAP Inference is conducted on factor graphs where each factor is defined in (negative) log-space, i.e., energy space,

Unlike Graphical Model Inference, the goal of MAP Inference is to find the joint assignment to the variables with highest probability (lowest energy). The interface for MAP inference is defined by the drwnMAPInference class. Currently Darwin implements the following algorithms:

• exact inference using the junction-tree algorithm (see drwnJunctionTreeInference)
• iterated conditional modes (see drwnICMInference)
• synchronous and asychronous max-product belief propagation (see drwnMaxProdInference and drwnAsyncMaxProdInference)
• sequential tree-reweighted message passing (see drwnTRWSInference)
• Globerson and Jaakkola's GEMPLP (see drwnGEMPLPInference)
• Sontag et al.'s iterative tightening of GEMPLP (see drwnSontag08Inference)
• Komodakis' dual decomposition inference (see drwnDualDecompositionInference)
• Alpha-Expansion and Alpha-Beta Swap (see drwnAlphaExpansionInference and drwnAlphaBetaSwapInference)
• Meshi and Globerson's alternating directions method (see drwnADLPInference)

The following code snippet shows an example of running the max-product algorithm on a factor graph.

// load graph
drwnFactorGraph graph;
graph.read(filename);

// run MAP inference
drwnMaxProdInference mp(graph);
drwnFullAssignment assignment;
pair<double, double> e = mp.inference(assignment);
DRWN_LOG_MESSAGE("map assignment has energy " << e.first);
if (e.second != -DRWN_DBL_MAX) {
    DRWN_LOG_MESSAGE("lower bound energy is " << e.second);
}
DRWN_LOG_VERBOSE("map assignment is " << toString(assignment));

The MAP Inference for Rosetta Protein Design demonstrates these algorithms on the Rosetta Protein Design dataset.

See Also

Graphical Model Inference