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_markovnetwork_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 C C D D C--D F F G G F--G D--F D--G A A A--C B B A--B E E A--E H H J J H--J B--C B--F B--E E--F

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_markovnetwork_view'])
gum.config['notebook','default_markovnetwork_view']='graph'
print("modified to: "+gum.config['notebook','default_markovnetwork_view'])
mn
Default view for Markov random field: factorgraph
modified to: graph
Out[4]:
G C C D D C--D F F G G F--G D--F D--G A A A--C B B A--B E E A--E H H J J H--J B--C B--F B--E E--F
In [5]:
gnb.sideBySide(gnb.getMRF(mn,view="graph",size="5"),
               gnb.getMRF(mn,view="factorgraph",size="5"))
G C C D D C--D F F G G F--G D--F D--G A A A--C B B A--B E E A--E H H J J H--J B--C B--F B--E E--F
G C C F F G G D D A A H H B B E E J J f0#1#2 f0#1#2--C f0#1#2--A f0#1#2--B f2#3 f2#3--C f2#3--D f7#8 f7#8--H f7#8--J f1#4#5 f1#4#5--F f1#4#5--B f1#4#5--E f3#5#6 f3#5#6--F f3#5#6--G f3#5#6--D 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  : {'C', 'F', 'G', 'D', 'A', 'H', 'B', 'E', '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  : {0: {0, 1, 2, 3, 4, 5, 6}, 7: {8, 7}}
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.2062  | 0.9916  |
1     || 0.3573  | 0.7746  |

factor(C,D) :
      ||  C                |
D     ||0        |1        |
------||---------|---------|
0     || 0.2062  | 0.9916  |
1     || 0.3573  | 0.7746  |

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.25430.0796
1
0.55440.0226
1
0
0.23090.2423
1
0.76030.7466
In [10]:
mn.factor({'A','B','C'})[{'B':0}]
Out[10]:
array([[0.25425358, 0.07960127],
       [0.23087176, 0.24233804]])
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.55440.0226
1
0
3.00004.0000
1
0.76030.7466

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'])
G C C D D C--D F F G G F--G D--F D--G A A A--C B B A--B E E A--E H H J J H--J B--C B--F B--E E--F
Markov random field
G C C D D C--D F F G G F--G D--F D--G A A A--C B B A--B E E A--E H H J J H--J B--C B--F B--E E--F
MarkovRandomField with colored node w.r.t number of neighbours
G C C F F G G D D A A H H B B E E J J f0#1#2 f0#1#2--C f0#1#2--A f0#1#2--B f2#3 f2#3--C f2#3--D f7#8 f7#8--H f7#8--J f1#4#5 f1#4#5--F f1#4#5--B f1#4#5--E f3#5#6 f3#5#6--F f3#5#6--G f3#5#6--D f0#4 f0#4--A f0#4--E f8 f8--J
MarkovRandomField as factor graph
G C C F F G G D D A A H H B B E E J J f0#1#2 f0#1#2--C f0#1#2--A f0#1#2--B f2#3 f2#3--C f2#3--D f7#8 f7#8--H f7#8--J f1#4#5 f1#4#5--F f1#4#5--B f1#4#5--E f3#5#6 f3#5#6--F f3#5#6--G f3#5#6--D 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'])
G C C D D C->D B B C->B J J C->J F F G G G->B E E D->E A A H H A->H A->B K K K->J L L L->K I I H->I B->F E->F
a Bayesian network
G C C G G C--G D D C--D K K C--K J J C--J F F E E D--E A A A--C A--G H H A--H B B A--B L L K--L I I H--I B--C B--F B--G B--E E--F J--K
the corresponding Markov random field
In [14]:
# The corresponding factor graph
m2g.MRF2FactorGraphdot(mn)
Out[14]:
G C C F F G G D D A A K K L L H H I I B B E E J J f0#1#2#6 f0#1#2#6--C f0#1#2#6--G f0#1#2#6--A f0#1#2#6--B f2#3 f2#3--C f2#3--D f3#4 f3#4--D f3#4--E f0#7 f0#7--A f0#7--H f7#8 f7#8--H f7#8--I f2#9#10 f2#9#10--C f2#9#10--K 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--F f1#4#5--B f1#4#5--E 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.58330.4167
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 Markoc 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 Markoc Random Field worlds when the MRF comes from a BN
A
0
1
0.79850.2015
G
0
1
0.51130.4887
C
0
1
0.51590.4841

Inference in the Bayesian network bn with evidence {}
A
0
1
0.79850.2015
G
0
1
0.51130.4887
C
0
1
0.51590.4841

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

Inference in the Bayesian network bn with evidence {'C': 1}
A
0
1
0.79850.2015
G
0
1
0.51130.4887
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.81960.1804
G
0
1
0.30600.6940
C
0
1
0.50320.4968

Inference in the Bayesian network bn with evidence {'B': 1}
A
0
1
0.81960.1804
G
0
1
0.30600.6940
C
0
1
0.50320.4968

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

Inference in the Bayesian network bn with evidence {'B': 1, 'C': 0}
A
0
1
0.89030.1097
G
0
1
0.36900.6310
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.79850.2015
G
0
1
0.51130.4887
C
0
1
0.51590.4841

Inference in the Bayesian network bn with evidence {}
A
0
1
0.92480.0752
G
0
1
0.58120.4188
C
0
1
0.20340.7966

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

Inference in the Bayesian network bn with evidence {'C': 1}
A
0
1
0.96860.0314
G
0
1
0.62250.3775
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"])
G (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
G (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
G 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
G 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_markovnetwork_view']='graph'
gnb.showInference(mn,size="8",evs={"D":1,"H":0})
../_images/notebooks_23-Models_MarkovRandomField_31_0.svg