inferlo.pairwise.optimization.map_lp.map_lp

inferlo.pairwise.optimization.map_lp.map_lp(model: PairWiseFiniteModel) → map_lp_result

LP relaxation of MAP problem for pairwise model.

This function implements linear programming (LP) relaxation of maximum a posteriori assignment problem (MAP) for pairwise graphical model with finite alphabet.

The goal of MAP estimation is to find most probable assignment of original variables by maximizing probability density function. For the case of pairwise finite model it reduces to maximization of quadratic function over finite field.

For every node, we introduce Q non-negative belief variables where Q is the size of the alphabet. Every such variable is our ‘belief’ that variable at node takes particular value.

Analogously, for every edge we introduce Q*Q pairwise beliefs.

For both node and edge beliefs we require normalization constraints: 1) for every node, the sum of beliefs equals one and 2) for every edge the sum of edge-beliefs equals one.

We also add marginalization constraint: for every edge, summing edge beliefs over one of the nodes must equal to the node belief of the second node.

Finally we get a linear program and its solution is an upper bound on the MAP value. We restore the lower bound on MAP value as the solution of the dual relaxation.

More details may be found in “MAP Estimation, Linear Programming and BeliefPropagation with Convex Free Energies” by Yair Weiss, Chen Yanover and Talya Meltzer. https://arxiv.org/pdf/1206.5286.pdf

Parameters:

model – Model for which to solve MAP problem.

Returns:

Object with the following fields: upper_bound - upper bound on MAP value (solution of LP); lower_bound - lower bound on MAP value (dual solution); node_beliefs - optimal values of node beliefs; edge_beliefs - optimal values of edge beliefs; normalization_duals - optimal values of dual variables that correspond to normalization constraints; marginalization_duals - optimal values of dual variables that correspond to marginalization constraints.