Mplp

class pgmpy.inference.Mplp(model)

Bases: Inference

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)

Bases: object

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
>>> import numpy as np
>>> rng = np.random.default_rng(42)
>>> 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_single = [
...     DiscreteFactor([node], [2], rng.random(2))
...     for node in mm.nodes()
... ]
>>> phi_pair = [
...     DiscreteFactor(edge, [2, 2], rng.random(4))
...     for edge in mm.edges()
... ]
>>> mm.add_factors(*(phi_single + phi_pair))
>>> mplp = Mplp(mm)
>>> mplp.map_query()
>>> {k: int(v) for k, v in mplp.map_query().items()}
{'x1': 0, 'x2': 1, 'x3': 1, 'x4': 0, 'x5': 1, 'x6': 1, 'x7': 1}
>>> 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()
>>> {k: int(v) for k, v in result.items()}
{'A': 1, 'B': 0, 'C': 1, 'D': 1, 'E': 1, 'F': 0}

query()