inferlo.pairwise.optimization.convex_hierarchies.sherali_adams

inferlo.pairwise.optimization.convex_hierarchies.sherali_adams(model: PairWiseFiniteModel, level=3) → sherali_adams_result[source]

This is an implementation of Sherali-Adams hierarchy, also called lift-and-project method. This method produces hierarchy of linear programming (LP) relaxations for the most probable state estimation (MAP problem).

Let k be the level of hierarchy. Then for every cluster of variables of size k, we introduce a new variable. All these variables, called lifted variables, should satisfy normalization, marginalization constraints and be non-negative.

After solving the corresponding LP, we get upper bound to the energy function at a most probable state and extract projected variable that correspond to single nodes of the model.

More on LP hierarchies may be found in D.Sontag’s thesis “Approximate Inference in Graphical Models using LP relaxations”. https://people.csail.mit.edu/dsontag/papers/sontag_phd_thesis.pdf