MPLP

class pgmpy.inference.mplp.Mplp(model)

Class for performing approximate inference using Max-Product Linear Programming method.

We derive message passing updates that result in monotone decrease of the dual of the MAP LP Relaxation.

Parameters:

model (DiscreteMarkovNetwork for which inference is to be performed.)

Examples

>>> import numpy as np
>>> from pgmpy.models import DiscreteMarkovNetwork
>>> from pgmpy.inference import Mplp
>>> from pgmpy.factors.discrete import DiscreteFactor
>>> student = DiscreteMarkovNetwork()
>>> student.add_edges_from([("A", "B"), ("B", "C"), ("C", "D"), ("E", "F")])
>>> factor_a = DiscreteFactor(
...     ["A"], cardinality=[2], values=np.array([0.54577, 1.8323])
... )
>>> factor_b = DiscreteFactor(
...     ["B"], cardinality=[2], values=np.array([0.93894, 1.065])
... )
>>> factor_c = DiscreteFactor(
...     ["C"], cardinality=[2], values=np.array([0.89205, 1.121])
... )
>>> factor_d = DiscreteFactor(
...     ["D"], cardinality=[2], values=np.array([0.56292, 1.7765])
... )
>>> factor_e = DiscreteFactor(
...     ["E"], cardinality=[2], values=np.array([0.47117, 2.1224])
... )
>>> factor_f = DiscreteFactor(
...     ["F"], cardinality=[2], values=np.array([1.5093, 0.66257])
... )
>>> factor_a_b = DiscreteFactor(
...     ["A", "B"],
...     cardinality=[2, 2],
...     values=np.array([1.3207, 0.75717, 0.75717, 1.3207]),
... )
>>> factor_b_c = DiscreteFactor(
...     ["B", "C"],
...     cardinality=[2, 2],
...     values=np.array([0.00024189, 4134.2, 4134.2, 0.00024189]),
... )
>>> factor_c_d = DiscreteFactor(
...     ["C", "D"],
...     cardinality=[2, 2],
...     values=np.array([0.0043227, 231.34, 231.34, 0.0043227]),
... )
>>> factor_d_e = DiscreteFactor(
...     ["E", "F"],
...     cardinality=[2, 2],
...     values=np.array([31.228, 0.032023, 0.032023, 31.228]),
... )
>>> student.add_factors(
...     factor_a,
...     factor_b,
...     factor_c,
...     factor_d,
...     factor_e,
...     factor_f,
...     factor_a_b,
...     factor_b_c,
...     factor_c_d,
...     factor_d_e,
... )
>>> mplp = Mplp(student)

class Cluster(intersection_set_variables, cluster_potential)

Inner class for representing a cluster. A cluster is a subset of variables.

Parameters:

• set_of_variables (tuple) – This is the set of variables that form the cluster.

• intersection_set_variables (set containing frozensets.) –

  collection of intersection of all pairs of cluster variables.

  For eg: {{C_1 cap C_2}, {C_2 cap C_3}, {C_3 cap C_1} }

  for clusters C_1, C_2 & C_3.

• cluster_potential (DiscreteFactor) – Each cluster has an initial probability distribution provided beforehand.

find_triangles()

Finds all the triangles present in the given model

Examples

>>> from pgmpy.models import DiscreteMarkovNetwork
>>> from pgmpy.factors.discrete import DiscreteFactor
>>> from pgmpy.inference import Mplp
>>> mm = DiscreteMarkovNetwork()
>>> mm.add_nodes_from(["x1", "x2", "x3", "x4", "x5", "x6", "x7"])
>>> mm.add_edges_from(
...     [
...         ("x1", "x3"),
...         ("x1", "x4"),
...         ("x2", "x4"),
...         ("x2", "x5"),
...         ("x3", "x6"),
...         ("x4", "x6"),
...         ("x4", "x7"),
...         ("x5", "x7"),
...     ]
... )
>>> phi = [
...     DiscreteFactor(edge, [2, 2], np.random.rand(4)) for edge in mm.edges()
... ]
>>> mm.add_factors(*phi)
>>> mplp = Mplp(mm)
>>> mplp.find_triangles()

get_integrality_gap()

Returns the integrality gap of the current state of the Mplp algorithm. The lesser it is, the closer we are

towards the exact solution.

Examples

>>> from pgmpy.models import DiscreteMarkovNetwork
>>> from pgmpy.factors.discrete import DiscreteFactor
>>> from pgmpy.inference import Mplp
>>> mm = DiscreteMarkovNetwork()
>>> mm.add_nodes_from(["x1", "x2", "x3", "x4", "x5", "x6", "x7"])
>>> mm.add_edges_from(
...     [
...         ("x1", "x3"),
...         ("x1", "x4"),
...         ("x2", "x4"),
...         ("x2", "x5"),
...         ("x3", "x6"),
...         ("x4", "x6"),
...         ("x4", "x7"),
...         ("x5", "x7"),
...     ]
... )
>>> phi = [
...     DiscreteFactor(edge, [2, 2], np.random.rand(4)) for edge in mm.edges()
... ]
>>> mm.add_factors(*phi)
>>> mplp = Mplp(mm)
>>> mplp.map_query()
>>> int_gap = mplp.get_integrality_gap()

map_query(init_iter=1000, later_iter=20, dual_threshold=0.0002, integrality_gap_threshold=0.0002, tighten_triplet=True, max_triplets=5, max_iterations=100, prolong=False)

MAP query method using Max Product LP method. This returns the best assignment of the nodes in the form of a dictionary.

Parameters:

• init_iter (integer) – Number of maximum iterations that we want MPLP to run for the first time.

• later_iter (integer) – Number of maximum iterations that we want MPLP to run for later iterations

• dual_threshold (double) – This sets the minimum width between the dual objective decrements. If the decrement is lesser than the threshold, then that means we have stuck on a local minima.

• integrality_gap_threshold (double) – This sets the threshold for the integrality gap below which we say that the solution is satisfactory.

• tighten_triplet (bool) – set whether to use triplets as clusters or not.

• max_triplets (integer) – Set the maximum number of triplets that can be added at once.

• max_iterations (integer) – Maximum number of times we tighten the relaxation. Used only when tighten_triplet is set True.

• prolong (bool) –

  If set False: The moment we exhaust of all the triplets the tightening stops. If set True: The tightening will be performed max_iterations

  number of times irrespective of the triplets.

References

Section 3.3: The Dual Algorithm; Tightening LP Relaxation for MAP using Message Passing (2008) By Sontag Et al.

Examples

>>> from pgmpy.models import DiscreteMarkovNetwork
>>> from pgmpy.factors.discrete import DiscreteFactor
>>> from pgmpy.inference import Mplp
>>> import numpy as np
>>> student = DiscreteMarkovNetwork()
>>> student.add_edges_from([("A", "B"), ("B", "C"), ("C", "D"), ("E", "F")])
>>> factor_a = DiscreteFactor(
...     ["A"], cardinality=[2], values=np.array([0.54577, 1.8323])
... )
>>> factor_b = DiscreteFactor(
...     ["B"], cardinality=[2], values=np.array([0.93894, 1.065])
... )
>>> factor_c = DiscreteFactor(
...     ["C"], cardinality=[2], values=np.array([0.89205, 1.121])
... )
>>> factor_d = DiscreteFactor(
...     ["D"], cardinality=[2], values=np.array([0.56292, 1.7765])
... )
>>> factor_e = DiscreteFactor(
...     ["E"], cardinality=[2], values=np.array([0.47117, 2.1224])
... )
>>> factor_f = DiscreteFactor(
...     ["F"], cardinality=[2], values=np.array([1.5093, 0.66257])
... )
>>> factor_a_b = DiscreteFactor(
...     ["A", "B"],
...     cardinality=[2, 2],
...     values=np.array([1.3207, 0.75717, 0.75717, 1.3207]),
... )
>>> factor_b_c = DiscreteFactor(
...     ["B", "C"],
...     cardinality=[2, 2],
...     values=np.array([0.00024189, 4134.2, 4134.2, 0.0002418]),
... )
>>> factor_c_d = DiscreteFactor(
...     ["C", "D"],
...     cardinality=[2, 2],
...     values=np.array([0.0043227, 231.34, 231.34, 0.0043227]),
... )
>>> factor_d_e = DiscreteFactor(
...     ["E", "F"],
...     cardinality=[2, 2],
...     values=np.array([31.228, 0.032023, 0.032023, 31.228]),
... )
>>> student.add_factors(
...     factor_a,
...     factor_b,
...     factor_c,
...     factor_d,
...     factor_e,
...     factor_f,
...     factor_a_b,
...     factor_b_c,
...     factor_c_d,
...     factor_d_e,
... )
>>> mplp = Mplp(student)
>>> result = mplp.map_query()
>>> result
{'B': 0.93894, 'C': 1.121, 'A': 1.8323, 'F': 1.5093, 'D': 1.7765, 'E': 2.12239}