MPLP¶
- class pgmpy.inference.mplp.Mplp(model)[source]¶
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 (MarkovNetwork for which inference is to be performed.)
Examples
>>> import numpy as np >>> from pgmpy.models import MarkovNetwork >>> from pgmpy.inference import Mplp >>> from pgmpy.factors.discrete import DiscreteFactor >>> student = MarkovNetwork() >>> 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)[source]¶
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()[source]¶
Finds all the triangles present in the given model
Examples
>>> from pgmpy.models import MarkovNetwork >>> from pgmpy.factors.discrete import DiscreteFactor >>> from pgmpy.inference import Mplp >>> mm = MarkovNetwork() >>> 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()[source]¶
- 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 MarkovNetwork >>> from pgmpy.factors.discrete import DiscreteFactor >>> from pgmpy.inference import Mplp >>> mm = MarkovNetwork() >>> 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)[source]¶
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 MarkovNetwork >>> from pgmpy.factors.discrete import DiscreteFactor >>> from pgmpy.inference import Mplp >>> import numpy as np >>> student = MarkovNetwork() >>> 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}