Markov random fields (a.k.a. Markov Networks)

Creative Commons License

aGrUM

interactive online version

In [1]:
import pyagrum.lib.mrf2graph as m2g
import pyagrum.lib.notebook as gnb
import pyagrum.markov_random_field as gum

building a Markov random field

In [2]:
gum.config.reset()  # back to default
gum.config["notebook", "markovRandomFieldView"] = "graph"
mn = gum.fastMRF("A--B--C;C--D;B--E--F;F--D--G;H--J;E--A;J")
mn
Out[2]:
anonymousMRF A A B B A--B C C A--C E E A--E B--C B--E F F B--F D D C--D D--F G G D--G E--F F--G H H J J H--J

Using pyagrum.config, it is possible to adapt the graphical representations for Markov random field (see the notebook 99-Tools_configForPyAgrum.ipynb).

In [3]:
gum.config.reset()  # back to default
gum.config["factorgraph", "edgeLength"] = "0.4"
gnb.showMRF(mn)
../_images/notebooks_23-Models_MarkovRandomField_6_0.svg
In [4]:
gum.config.reset()  # back to default
print("Default view for Markov random field: " + gum.config["notebook", "markovRandomFieldView"])
gum.config["notebook", "markovRandomFieldView"] = "graph"
print("modified to: " + gum.config["notebook", "markovRandomFieldView"])
mn
Default view for Markov random field: factorgraph
modified to: graph
Out[4]:
anonymousMRF A A B B A--B C C A--C E E A--E B--C B--E F F B--F D D C--D D--F G G D--G E--F F--G H H J J H--J
In [5]:
gnb.sideBySide(gnb.getMRF(mn, view="graph", size="5"), gnb.getMRF(mn, view="factorgraph", size="5"))
anonymousMRF A A B B A--B C C A--C E E A--E B--C B--E F F B--F D D C--D D--F G G D--G E--F F--G H H J J H--J
anonymousMRF A A B B C C D D E E F F G G H H J J f#A#B#C f#A#B#C--A f#A#B#C--B f#A#B#C--C f#A#E f#A#E--A f#A#E--E f#B#E#F f#B#E#F--B f#B#E#F--E f#B#E#F--F f#C#D f#C#D--C f#C#D--D f#D#F#G f#D#F#G--D f#D#F#G--F f#D#F#G--G f#H#J f#H#J--H f#H#J--J f#J f#J--J
In [6]:
gnb.showMRF(mn)
print(mn)
../_images/notebooks_23-Models_MarkovRandomField_9_0.svg
MRF{nodes: 9, edges: 12, domainSize: 512, dim: 38}

Accessors for Markov random fields

In [7]:
print(f"nodes       : {mn.nodes()}")
print(f"node names  : {mn.names()}")
print(f"edges       : {mn.edges()}")
print(f"components  : {mn.connectedComponents()}")
print(f"factors     : {mn.factors()}")
print(f"factor(C,D) : {mn.factor({2, 3})}")
print(f"factor(C,D) : {mn.factor({'C', 'D'})}")
nodes       : {0, 1, 2, 3, 4, 5, 6, 7, 8}
node names  : {'D', 'C', 'J', 'G', 'B', 'F', 'H', 'A', 'E'}
edges       : {(0, 1), (1, 2), (0, 4), (1, 5), (1, 4), (2, 3), (4, 5), (0, 2), (5, 6), (7, 8), (3, 6), (3, 5)}
components  : {3: 0, 8: 1, 1: 0, 6: 0, 4: 0, 7: 1, 0: 0, 2: 0, 5: 0}
factors     : [{0, 1, 2}, {2, 3}, {8, 7}, {1, 4, 5}, {3, 5, 6}, {0, 4}, {8}]
factor(C,D) :
      ║  C                │
D     ║0        │1        │
──────║─────────│─────────│
0     ║ 0.9146  │ 0.9112  │
1     ║ 0.7835  │ 0.7341  │

factor(C,D) :
      ║  C                │
D     ║0        │1        │
──────║─────────│─────────│
0     ║ 0.9146  │ 0.9112  │
1     ║ 0.7835  │ 0.7341  │

In [8]:
try:
  mn.factor({0, 1})
except gum.GumException as e:
  print(e)
try:
  mn.factor({"A", "B"})
except gum.GumException as e:
  print(e)
[pyAgrum] Object not found: No element with the key <{1,0}>
[pyAgrum] Object not found: No element with the key <{1,0}>

Manipulating factors

In [9]:
mn.factor({"A", "B", "C"})
Out[9]:
A
C
B
0
1
0
0
0.36790.5217
1
0.36060.9216
1
0
0.55860.9201
1
0.88220.5509
In [10]:
mn.factor({"A", "B", "C"})[{"B": 0}]
Out[10]:
array([[0.36788246, 0.52166084],
       [0.55857622, 0.92005756]])
In [11]:
mn.factor({"A", "B", "C"})[{"B": 0}] = [[1, 2], [3, 4]]
mn.factor({"A", "B", "C"})
Out[11]:
A
C
B
0
1
0
0
1.00002.0000
1
0.36060.9216
1
0
3.00004.0000
1
0.88220.5509

Customizing graphical representation

In [12]:
gum.config.reset()  # back to default
gum.config["factorgraph", "edgeLength"] = "0.5"

maxnei = max([len(mn.neighbours(n)) for n in mn.nodes()])
nodemap = {n: len(mn.neighbours(mn.idFromName(n))) / maxnei for n in mn.names()}

facmax = max([len(f) for f in mn.factors()])


def fgma(factor):
  return (1 + len(factor) ** 2) / (1 + facmax * facmax)


gnb.flow.row(
  gnb.getGraph(m2g.MRF2UGdot(mn)),
  gnb.getGraph(m2g.MRF2UGdot(mn, nodeColor=nodemap)),
  gnb.getGraph(m2g.MRF2FactorGraphdot(mn)),
  gnb.getGraph(m2g.MRF2FactorGraphdot(mn, factorColor=fgma, nodeColor=nodemap)),
  captions=[
    "Markov random field",
    "MarkovRandomField with colored node w.r.t number of neighbours",
    "MarkovRandomField as factor graph",
    "MRF with colored factor w.r.t to the size of scope",
  ],
)
Out[12]:
anonymousMRF A A B B A--B C C A--C E E A--E B--C B--E F F B--F D D C--D D--F G G D--G E--F F--G H H J J H--J
Markov random field
anonymousMRF A A B B A--B C C A--C E E A--E B--C B--E F F B--F D D C--D D--F G G D--G E--F F--G H H J J H--J
MarkovRandomField with colored node w.r.t number of neighbours
anonymousMRF A A B B C C D D E E F F G G H H J J f#A#B#C f#A#B#C--A f#A#B#C--B f#A#B#C--C f#A#E f#A#E--A f#A#E--E f#B#E#F f#B#E#F--B f#B#E#F--E f#B#E#F--F f#C#D f#C#D--C f#C#D--D f#D#F#G f#D#F#G--D f#D#F#G--F f#D#F#G--G f#H#J f#H#J--H f#H#J--J f#J f#J--J
MarkovRandomField as factor graph
anonymousMRF A A B B C C D D E E F F G G H H J J f#A#B#C f#A#B#C--A f#A#B#C--B f#A#B#C--C f#A#E f#A#E--A f#A#E--E f#B#E#F f#B#E#F--B f#B#E#F--E f#B#E#F--F f#C#D f#C#D--C f#C#D--D f#D#F#G f#D#F#G--D f#D#F#G--F f#D#F#G--G f#H#J f#H#J--H f#H#J--J f#J f#J--J
MRF with colored factor w.r.t to the size of scope

from BayesNet to MarkovRandomField

In [13]:
bn = gum.fastBN("A->B<-C->D->E->F<-B<-G;A->H->I;C->J<-K<-L")
mn = gum.MarkovRandomField.fromBN(bn)
gnb.flow.row(
  bn, gnb.getGraph(m2g.MRF2UGdot(mn)), captions=["a Bayesian network", "the corresponding Markov random field"]
)
Out[13]:
anonymousBN A A B B A->B H H A->H F F B->F C C C->B D D C->D J J C->J E E D->E E->F G G G->B I I H->I K K K->J L L L->K
a Bayesian network
anonymousBN A A B B A--B C C A--C G G A--G H H A--H B--C E E B--E F F B--F B--G D D C--D C--G J J C--J K K C--K D--E E--F I I H--I J--K L L K--L
the corresponding Markov random field
In [14]:
# The corresponding factor graph
m2g.MRF2FactorGraphdot(mn)
Out[14]:
anonymousBN A A B B C C D D E E F F G G H H I I J J K K L L f#A f#A--A f#A#B#C#G f#A#B#C#G--A f#A#B#C#G--B f#A#B#C#G--C f#A#B#C#G--G f#A#H f#A#H--A f#A#H--H f#B#E#F f#B#E#F--B f#B#E#F--E f#B#E#F--F f#C f#C--C f#C#D f#C#D--C f#C#D--D f#C#J#K f#C#J#K--C f#C#J#K--J f#C#J#K--K f#D#E f#D#E--D f#D#E--E f#G f#G--G f#H#I f#H#I--H f#H#I--I f#K#L f#K#L--K f#K#L--L f#L f#L--L

Inference in Markov random field

In [15]:
bn = gum.fastBN("A->B<-C->D->E->F<-B<-G;A->H->I;C->J<-K<-L")
iebn = gum.LazyPropagation(bn)

mn = gum.MarkovRandomField.fromBN(bn)
iemn = gum.ShaferShenoyMRFInference(mn)
iemn.setEvidence({"A": 1, "F": [0.4, 0.8]})
iemn.makeInference()
iemn.posterior("B")
Out[15]:
B
0
1
0.63950.3605
In [16]:
def affAGC(evs):
  gnb.sideBySide(
    gnb.getSideBySide(
      gum.getPosterior(bn, target="A", evs=evs),
      gum.getPosterior(bn, target="G", evs=evs),
      gum.getPosterior(bn, target="C", evs=evs),
    ),
    gnb.getSideBySide(
      gum.getPosterior(mn, target="A", evs=evs),
      gum.getPosterior(mn, target="G", evs=evs),
      gum.getPosterior(mn, target="C", evs=evs),
    ),
    captions=[
      "Inference in the Bayesian network bn with evidence " + str(evs),
      "Inference in the Markov random field mn with evidence " + str(evs),
    ],
  )


print(
  "Inference for both the corresponding models in BayesNet and Markov Random Field worlds when the MRF comes from a BN"
)
affAGC({})
print("C has no impact on A and G")
affAGC({"C": 1})

print("But if B is observed")
affAGC({"B": 1})
print("C has an impact on A and G")
affAGC({"B": 1, "C": 0})
Inference for both the corresponding models in BayesNet and Markov Random Field worlds when the MRF comes from a BN
A
0
1
0.66470.3353
G
0
1
0.46070.5393
C
0
1
0.46590.5341

Inference in the Bayesian network bn with evidence {}
A
0
1
0.66470.3353
G
0
1
0.46070.5393
C
0
1
0.46590.5341

Inference in the Markov random field mn with evidence {}
C has no impact on A and G
A
0
1
0.66470.3353
G
0
1
0.46070.5393
C
0
1
0.00001.0000

Inference in the Bayesian network bn with evidence {'C': 1}
A
0
1
0.66470.3353
G
0
1
0.46070.5393
C
0
1
0.00001.0000

Inference in the Markov random field mn with evidence {'C': 1}
But if B is observed
A
0
1
0.47650.5235
G
0
1
0.26860.7314
C
0
1
0.84040.1596

Inference in the Bayesian network bn with evidence {'B': 1}
A
0
1
0.47650.5235
G
0
1
0.26860.7314
C
0
1
0.84040.1596

Inference in the Markov random field mn with evidence {'B': 1}
C has an impact on A and G
A
0
1
0.51780.4822
G
0
1
0.22650.7735
C
0
1
1.00000.0000

Inference in the Bayesian network bn with evidence {'B': 1, 'C': 0}
A
0
1
0.51780.4822
G
0
1
0.22650.7735
C
0
1
1.00000.0000

Inference in the Markov random field mn with evidence {'B': 1, 'C': 0}
In [17]:
mn.generateFactors()
print("But with more general factors")
affAGC({})
print("C has impact on A and G even without knowing B")
affAGC({"C": 1})
But with more general factors
A
0
1
0.66470.3353
G
0
1
0.46070.5393
C
0
1
0.46590.5341

Inference in the Bayesian network bn with evidence {}
A
0
1
0.53140.4686
G
0
1
0.85720.1428
C
0
1
0.46590.5341

Inference in the Markov random field mn with evidence {}
C has impact on A and G even without knowing B
A
0
1
0.66470.3353
G
0
1
0.46070.5393
C
0
1
0.00001.0000

Inference in the Bayesian network bn with evidence {'C': 1}
A
0
1
0.54390.4561
G
0
1
0.84760.1524
C
0
1
0.00001.0000

Inference in the Markov random field mn with evidence {'C': 1}

Graphical inference in Markov random field

In [18]:
bn = gum.fastBN("A->B<-C->D->E->F<-B<-G;A->H->I;C->J<-K<-L")
mn = gum.MarkovRandomField.fromBN(bn)

gnb.sideBySide(
  gnb.getJunctionTree(bn),
  gnb.getJunctionTree(mn),
  captions=["Junction tree for the BN", "Junction tree for the induced MN"],
)
gnb.sideBySide(
  gnb.getJunctionTreeMap(bn, size="3!"),
  gnb.getJunctionTreeMap(mn, size="3!"),
  captions=["Map of the junction tree for the BN", "Map of the junction tree for the induced MN"],
)
0 (0):H,I 0~4 H 0--0~4 1 (1):K,L 1~3 K 1--1~3 2 (2):A,B,C,G 2~8 B,C 2--2~8 2~4 A 2--2~4 3 (3):C,J,K 3~8 C 3--3~8 4 (4):A,H 6 (6):B,E,F 6~8 B,E 6--6~8 8 (8):B,C,E 8~9 C,E 8--8~9 9 (9):C,D,E 8~9--9 1~3--3 0~4--4 6~8--8 2~8--8 2~4--4 3~8--8
Junction tree for the BN
0 (0):H,I 0~4 H 0--0~4 1 (1):K,L 1~3 K 1--1~3 2 (2):A,B,C,G 2~8 B,C 2--2~8 2~4 A 2--2~4 3 (3):C,J,K 3~8 C 3--3~8 4 (4):A,H 6 (6):B,E,F 6~8 B,E 6--6~8 8 (8):B,C,E 8~9 C,E 8--8~9 9 (9):C,D,E 8~9--9 1~3--3 0~4--4 6~8--8 2~8--8 2~4--4 3~8--8
Junction tree for the induced MN
0 0~4 0--0~4 1 1~3 1--1~3 2 2~8 2--2~8 2~4 2--2~4 3 3~8 3--3~8 4 6 6~8 6--6~8 8 8~9 8--8~9 9 8~9--9 1~3--3 0~4--4 6~8--8 2~8--8 2~4--4 3~8--8
Map of the junction tree for the BN
0 0~4 0--0~4 1 1~3 1--1~3 2 2~8 2--2~8 2~4 2--2~4 3 3~8 3--3~8 4 6 6~8 6--6~8 8 8~9 8--8~9 9 8~9--9 1~3--3 0~4--4 6~8--8 2~8--8 2~4--4 3~8--8
Map of the junction tree for the induced MN
In [19]:
gnb.showInference(bn, evs={"D": 1, "H": 0})
../_images/notebooks_23-Models_MarkovRandomField_28_0.svg
In [20]:
gum.config.reset()
gnb.showInference(mn, size="8", evs={"D": 1, "H": 0})
../_images/notebooks_23-Models_MarkovRandomField_29_0.svg
In [21]:
gum.config["factorgraph", "edge_length_inference"] = "1.1"
gnb.showInference(mn, size="11", evs={"D": 1, "H": 0})
../_images/notebooks_23-Models_MarkovRandomField_30_0.svg
In [22]:
gum.config["notebook", "markovRandomFieldView"] = "graph"
gnb.showInference(mn, size="8", evs={"D": 1, "H": 0})
../_images/notebooks_23-Models_MarkovRandomField_31_0.svg