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

Creative Commons License

aGrUM

interactive online version

 
In [1]:

import pyagrum as gum
import pyagrum.lib.notebook as gnb
import pyagrum.lib.mrf2graph as m2g

building a Markov random field

In [2]:

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

Out[2]:
G A A E E A--E B B A--B C C A--C F F E--F D D D--F G G D--G H H J J H--J B--E B--F B--C F--G C--D

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", "edge_length"] = "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", "default_markovrandomfield_view"])
gum.config["notebook", "default_markovrandomfield_view"] = "graph"
print("modified to: " + gum.config["notebook", "default_markovrandomfield_view"])
mn

Default view for Markov random field: factorgraph
modified to: graph

Out[4]:
G A A E E A--E B B A--B C C A--C F F E--F D D D--F G G D--G H H J J H--J B--E B--F B--C F--G C--D 
In [5]:

gnb.sideBySide(gnb.getMRF(mn, view="graph", size="5"), gnb.getMRF(mn, view="factorgraph", size="5"))
G A A E E A--E B B A--B C C A--C F F E--F D D D--F G G D--G H H J J H--J B--E B--F B--C F--G C--D
G A A E E D D H H B B F F C C G G J J f0#1#2 f0#1#2--A f0#1#2--B f0#1#2--C f2#3 f2#3--D f2#3--C f7#8 f7#8--H f7#8--J f1#4#5 f1#4#5--E f1#4#5--B f1#4#5--F f3#5#6 f3#5#6--D f3#5#6--F f3#5#6--G f0#4 f0#4--A f0#4--E f8 f8--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  : {'A', 'E', 'D', 'H', 'B', 'F', 'C', 'G', 'J'}
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.7361  │ 0.7227  │
1     ║ 0.3453  │ 0.8448  │

factor(C,D) :
      ║  C                │
D     ║0        │1        │
──────║─────────│─────────│
0     ║ 0.7361  │ 0.7227  │
1     ║ 0.3453  │ 0.8448  │


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.91900.7368
1
0.30970.2404
1
0
0.98080.5334
1
0.97670.7963
In [10]:

mn.factor({"A", "B", "C"})[{"B": 0}]

Out[10]:

array([[0.91902752, 0.7368242 ],
       [0.98084643, 0.53339998]])

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.30970.2404
1
0
3.00004.0000
1
0.97670.7963

Customizing graphical representation

In [12]:

gum.config.reset()  # back to default
gum.config["factorgraph", "edge_length"] = "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()])
fgma = lambda factor: (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]:
G A A E E A--E B B A--B C C A--C F F E--F D D D--F G G D--G H H J J H--J B--E B--F B--C F--G C--D
Markov random field
G A A E E A--E B B A--B C C A--C F F E--F D D D--F G G D--G H H J J H--J B--E B--F B--C F--G C--D
MarkovRandomField with colored node w.r.t number of neighbours
G A A E E D D H H B B F F C C G G J J f0#1#2 f0#1#2--A f0#1#2--B f0#1#2--C f2#3 f2#3--D f2#3--C f7#8 f7#8--H f7#8--J f1#4#5 f1#4#5--E f1#4#5--B f1#4#5--F f3#5#6 f3#5#6--D f3#5#6--F f3#5#6--G f0#4 f0#4--A f0#4--E f8 f8--J
MarkovRandomField as factor graph
G A A E E D D H H B B F F C C G G J J f0#1#2 f0#1#2--A f0#1#2--B f0#1#2--C f2#3 f2#3--D f2#3--C f7#8 f7#8--H f7#8--J f1#4#5 f1#4#5--E f1#4#5--B f1#4#5--F f3#5#6 f3#5#6--D f3#5#6--F f3#5#6--G f0#4 f0#4--A f0#4--E f8 f8--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]:
G A A H H A->H B B A->B E E F F E->F D D D->E I I H->I K K J J K->J B->F L L L->K C C C->D C->B C->J G G G->B
a Bayesian network
G A A H H A--H B B A--B C C A--C G G A--G E E F F E--F D D D--E I I H--I K K L L K--L B--E B--F B--C B--G C--D C--K C--G J J C--J J--K
the corresponding Markov random field
In [14]:

# The corresponding factor graph
m2g.MRF2FactorGraphdot(mn)

Out[14]:
G A A E E D D H H K K I I B B F F L L C C G G J J f0#1#2#6 f0#1#2#6--A f0#1#2#6--B f0#1#2#6--C f0#1#2#6--G f2#3 f2#3--D f2#3--C f3#4 f3#4--E f3#4--D f0#7 f0#7--A f0#7--H f7#8 f7#8--H f7#8--I f2#9#10 f2#9#10--K f2#9#10--C f2#9#10--J f10#11 f10#11--K f10#11--L f11 f11--L f0 f0--A f2 f2--C f1#4#5 f1#4#5--E f1#4#5--B f1#4#5--F f6 f6--G

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.81150.1885
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.34330.6567
G
0
1
0.19510.8049
C
0
1
0.00710.9929

Inference in the Bayesian network bn with evidence {}
A
0
1
0.34330.6567
G
0
1
0.19510.8049
C
0
1
0.00710.9929

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

Inference in the Bayesian network bn with evidence {'C': 1}
A
0
1
0.34330.6567
G
0
1
0.19510.8049
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.59810.4019
G
0
1
0.18920.8108
C
0
1
0.00950.9905

Inference in the Bayesian network bn with evidence {'B': 1}
A
0
1
0.59810.4019
G
0
1
0.18920.8108
C
0
1
0.00950.9905

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

Inference in the Bayesian network bn with evidence {'B': 1, 'C': 0}
A
0
1
0.32370.6763
G
0
1
0.12940.8706
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.34330.6567
G
0
1
0.19510.8049
C
0
1
0.00710.9929

Inference in the Bayesian network bn with evidence {}
A
0
1
0.32310.6769
G
0
1
0.62880.3712
C
0
1
0.82300.1770

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

Inference in the Bayesian network bn with evidence {'C': 1}
A
0
1
0.38940.6106
G
0
1
0.62500.3750
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) 7-8 H I (0) 7-8^(4) 0-7 H (0) 7-8--(0) 7-8^(4) 0-7 (1) 10-11 K L (1) 10-11^(3) 2-9-10 K (1) 10-11--(1) 10-11^(3) 2-9-10 (2) 0-1-2-6 A B C G (2) 0-1-2-6^(8) 1-2-4 B C (2) 0-1-2-6--(2) 0-1-2-6^(8) 1-2-4 (2) 0-1-2-6^(4) 0-7 A (2) 0-1-2-6--(2) 0-1-2-6^(4) 0-7 (3) 2-9-10 C J K (3) 2-9-10^(8) 1-2-4 C (3) 2-9-10--(3) 2-9-10^(8) 1-2-4 (4) 0-7 A H (6) 1-4-5 B E F (6) 1-4-5^(8) 1-2-4 B E (6) 1-4-5--(6) 1-4-5^(8) 1-2-4 (8) 1-2-4 B C E (8) 1-2-4^(9) 2-3-4 C E (8) 1-2-4--(8) 1-2-4^(9) 2-3-4 (9) 2-3-4 C D E (8) 1-2-4^(9) 2-3-4--(9) 2-3-4 (1) 10-11^(3) 2-9-10--(3) 2-9-10 (0) 7-8^(4) 0-7--(4) 0-7 (6) 1-4-5^(8) 1-2-4--(8) 1-2-4 (2) 0-1-2-6^(8) 1-2-4--(8) 1-2-4 (2) 0-1-2-6^(4) 0-7--(4) 0-7 (3) 2-9-10^(8) 1-2-4--(8) 1-2-4
Junction tree for the BN
(0) 7-8 H I (0) 7-8^(4) 0-7 H (0) 7-8--(0) 7-8^(4) 0-7 (1) 10-11 K L (1) 10-11^(3) 2-9-10 K (1) 10-11--(1) 10-11^(3) 2-9-10 (2) 0-1-2-6 A B C G (2) 0-1-2-6^(8) 1-2-4 B C (2) 0-1-2-6--(2) 0-1-2-6^(8) 1-2-4 (2) 0-1-2-6^(4) 0-7 A (2) 0-1-2-6--(2) 0-1-2-6^(4) 0-7 (3) 2-9-10 C J K (3) 2-9-10^(8) 1-2-4 C (3) 2-9-10--(3) 2-9-10^(8) 1-2-4 (4) 0-7 A H (6) 1-4-5 B E F (6) 1-4-5^(8) 1-2-4 B E (6) 1-4-5--(6) 1-4-5^(8) 1-2-4 (8) 1-2-4 B C E (8) 1-2-4^(9) 2-3-4 C E (8) 1-2-4--(8) 1-2-4^(9) 2-3-4 (9) 2-3-4 C D E (8) 1-2-4^(9) 2-3-4--(9) 2-3-4 (1) 10-11^(3) 2-9-10--(3) 2-9-10 (0) 7-8^(4) 0-7--(4) 0-7 (6) 1-4-5^(8) 1-2-4--(8) 1-2-4 (2) 0-1-2-6^(8) 1-2-4--(8) 1-2-4 (2) 0-1-2-6^(4) 0-7--(4) 0-7 (3) 2-9-10^(8) 1-2-4--(8) 1-2-4
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", "default_markovrandomfield_view"] = "graph"
gnb.showInference(mn, size="8", evs={"D": 1, "H": 0})
../_images/notebooks_23-Models_MarkovRandomField_31_0.svg