inferlo.forney.optimization.nfg_map_lp.map_lp

inferlo.forney.optimization.nfg_map_lp.map_lp(model: NormalFactorGraphModel) → map_lp_result

LP relaxation of MAP problem for NFG model.

This function implements linear programming (LP) relaxation of maximum a posteriori assignment problem (MAP) for normal factor graph 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 polynomial over finite field.

For every variable, 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 factor we introduce Q^deg beliefs where deg is a number of variables in factor.

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

We also add marginalization constraint: for every factor, summing factor beliefs over all except one node must equal to the node belief at that 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); factor_beliefs - optimal values of factor beliefs; variable_beliefs - optimal values of variable 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.