CC-BY
Fabian M. Suchanek
Markov Logic
29
Reminder: Weighted MAX SAT
A weighted formula is a logical formula with a real‐valued weight.
ｄｕｍｂ（Ｒｏｎ） [10], ｄｕｍｂ（ｘ） ⇒ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） [3.2]
equivalently written as a clause:
instantiated:
｛¬ ｄｕｍｂ（ｘ）， ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）｝ [3.2]
Given a set of instantiated clauses with weights,
weighted MAX SAT
is the problem of finding the KB
with the highest weight. If there are several, find the one with the least number of atoms.
｛¬ ｄｕｍｂ（Ｒｏｎ）， ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ）｝ [3.2]
Given weighted clauses, the weight of a KB (= set of facts) is the sum of the weights of the
clauses that are satisfied in the KB.
is
dumb
weight: 10
is
dumb
weight: 13.2
loves
Let us see every ground literal as a random variable with values TRUE and FALSE:
A probabilistic view
ｓｐｏｕｓｅ（Ｈａｒｒｙ，Ｒｏｎ）
Ｆ
Ｆ
Ｆ
Ｆ
Ｆ
Ｔ
Ｔ
Ｆ
Ｆ
possible worlds with probabilities
3
Then we can draw up all possible worlds with their probabilities:
But what are these probabilities?
A
Markov Random Field
(MRF) is a set of random variables that satisfies:
where
is the set of random variables that are “neighbors” of
.
That is: The probability of
taking a certain value given
the values of the other variables depends only on the values
of the variables in the neighborhood of
.
Def: Markov Random Field
4
Example: Markov Random Field
5
X2
shouts
shouts
purrs
purrs
shouts
...
X1
Shrek
Shrek
Shrek
Shrek
Puss
...
X3
ferociously
ferociously
-
-
ferociously
...
X4
with
-
with
-
with
...
X5
pleasure
-
pleasure
-
pleasure
...
world
w1
w2
w3
w4
w5
...
probability
P(w1)=0.1
P(w2)=0.1
P(w3)=0.02
P(w4)=0.04
P(w5)=0.01
...
Example: Markov Random Field
6
X1, X2, and X3 depend on each other: shouting is always ferociously,
purring is never ferociously, shouting is more likely to be by Shrek.
X4 and X5 depend on each other: either both are the empty string, or X4=with and X5=pleasure.
(X1,X2,X3) and (X4,X5) are independent
X2
shouts
shouts
purrs
purrs
shouts
...
X1
Shrek
Shrek
Shrek
Shrek
Puss
...
X3
ferociously
ferociously
-
-
ferociously
...
X4
with
-
with
-
with
...
X5
pleasure
-
pleasure
-
pleasure
...
world
w1
w2
w3
w4
w5
...
probability
P(w1)=0.1
P(w2)=0.1
P(w3)=0.02
P(w4)=0.04
P(w5)=0.01
...
Example: Markov Random Field
7
Neighbor sets:
X2
shouts
shouts
purrs
purrs
shouts
...
X1
Shrek
Shrek
Shrek
Shrek
Puss
...
X3
ferociously
ferociously
-
-
ferociously
...
X4
with
-
with
-
with
...
X5
pleasure
-
pleasure
-
pleasure
...
world
w1
w2
w3
w4
w5
...
probability
P(w1)=0.1
P(w2)=0.1
P(w3)=0.02
P(w4)=0.04
P(w5)=0.01
...
The
graph of a MRF
is an undirected graph, where the nodes are variables,
and
is an edge if
.
Def: Markov Random Field Graph
8
X2
shouts
shouts
purrs
purrs
shouts
...
X1
Shrek
Shrek
Shrek
Shrek
Puss
...
X3
ferociously
ferociously
-
-
ferociously
...
X4
with
-
with
-
with
...
X5
pleasure
-
pleasure
-
pleasure
...
world
w1
w2
w3
w4
w5
...
probability
P(w1)=0.1
P(w2)=0.1
P(w3)=0.02
P(w4)=0.04
P(w5)=0.01
...
We consider the maximal cliques in the neighborhood graph.
Maximal cliques
9
We write
X2
shouts
shouts
purrs
purrs
shouts
...
X1
Shrek
Shrek
Shrek
Shrek
Puss
...
X3
ferociously
ferociously
-
-
ferociously
...
X4
with
-
with
-
with
...
X5
pleasure
-
pleasure
-
pleasure
...
world
w1
w2
w3
w4
w5
...
probability
P(w1)=0.1
P(w2)=0.1
P(w3)=0.02
P(w4)=0.04
P(w5)=0.01
...
Hammersley-Clifford-Theorem
10
If all probabilities in an MRF are ＞０ , then
such that
,
where the
are the maximal
cliques f the MRF graph.
>example
X2
shouts
shouts
purrs
purrs
shouts
...
X1
Shrek
Shrek
Shrek
Shrek
Puss
...
X3
ferociously
ferociously
-
-
ferociously
...
X4
with
-
with
-
with
...
X5
pleasure
-
pleasure
-
pleasure
...
world
w1
w2
w3
w4
w5
...
probability
P(w1)=0.1
P(w2)=0.1
P(w3)=0.02
P(w4)=0.04
P(w5)=0.01
...
Hammersley-Clifford-Theorem
11
(example might not sum to 1)
If all probabilities in an MRF are ＞０ , then
such that
.
X2
shouts
shouts
purrs
purrs
shouts
...
X1
Shrek
Shrek
Shrek
Shrek
Puss
...
X3
ferociously
ferociously
-
-
ferociously
...
X4
with
-
with
-
with
...
X5
pleasure
-
pleasure
-
pleasure
...
world
w1
w2
w3
w4
w5
...
probability
P(w1)=0.1
P(w2)=0.1
P(w3)=0.02
P(w4)=0.04
P(w5)=0.01
...
Back to the logical worlds
Rule 42: ｓｐｏｕｓｅ（Ｈａｒｒｙ，Ｒｏｎ） ⇒ ｓｐｏｕｓｅ（Ｒｏｎ，Ｈａｒｒｙ）［５］
12
Let’s define
rule ｉ satisfied with
?
: ０ )
>example
spouse(Harry, Ron)
F
F
...
likes(H., Ron)
T
T
...
spouse(Ron, Harry)
F
F
...
world
w1
w2
...
probability
P(w1)=0.1
P(w2)=0.1
...
Back to the logical worlds
13
Let’s define
rule ｉ satisfied with
?
: ０ )
>example
? ５：０）
Rule 42: ｓｐｏｕｓｅ（Ｈａｒｒｙ，Ｒｏｎ） ⇒ ｓｐｏｕｓｅ（Ｒｏｎ，Ｈａｒｒｙ）［５］
spouse(Harry, Ron)
F
F
...
likes(H., Ron)
T
T
...
spouse(Ron, Harry)
F
F
...
world
w1
w2
...
probability
P(w1)=0.1
P(w2)=0.1
...
Example: Markov Logic Network
14
Original Weighted MAX SAT problem:
Assignment to variables:
Factors:
ｉｓ（Ｒｏｎ， ｉｍｍａｔｕｒｅ） ［１０］
ｉｓ（Ｒｏｎ， ｉｍｍａｔｕｒｅ） ∧ ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ⇒ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ［３］
ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ［４］
Example: Markov Logic Network
15
Original Weighted MAX SAT problem:
Assignment to variables:
Factors:
ｅｘｐ（１０） if
else
｛
ｉｓ（Ｒｏｎ， ｉｍｍａｔｕｒｅ） ［１０］
ｉｓ（Ｒｏｎ， ｉｍｍａｔｕｒｅ） ∧ ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ⇒ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ［３］
ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ［４］
Example: Markov Logic Network
16
ｉｓ（Ｒｏｎ， ｉｍｍａｔｕｒｅ） ［１０］
ｉｓ（Ｒｏｎ， ｉｍｍａｔｕｒｅ） ∧ ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ⇒ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ［３］
ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ［４］
Original Weighted MAX SAT problem:
Assignment to variables:
Factors:
A world becomes
more
likely if formula ｉ is satisfied.
The neighbors of one variable
are the other variables
with which it shares a formula.
｛
A factor is a formula
ｅｘｐ（１０） if
else
17
LivePhysics Plotter
Normalization still missing
Factors as continuums
TRUE
FALSE
TRUE
FALSE
TRUE
Example: Markov Logic Network
>Normalization
ｉｓ（Ｒｏｎ， ｉｍｍａｔｕｒｅ） ［１０］
ｉｓ（Ｒｏｎ， ｉｍｍａｔｕｒｅ） ∧ ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ⇒ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ［３］
ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ［４］
Original Weighted MAX SAT problem:
Let us assume:
Then the probability distribution is:
To obtain a value in [0,1], we normalize by Ｚ
Normalization
where Ｚ is simply the sum over the products for all possible sequences of values
:
Yes, run over all possible sequences
and sum up the products!
18
This ensures
.
Def: Markov Logic Network
A
Markov Logic Network
(MLN) for a set of weighted rules (or weighted propositional formulae)
is a Markov Random Network, where the variables are the positive literals and the factors are
rule ｉ satisfied with
?
literals involved in rule ｉ
weight of rule ｉ
19
>end
Quantified formulas
20
Formulas with universally quantified variables such as
ｓｐｏｕｓｅ（Ｘ，Ｙ） ⇒ ｓｐｏｕｓｅ（Ｙ，Ｘ） ［５］
have to be replaced by all of their ground instances:
ｓｐｏｕｓｅ（Ｒｏｎ，Ｈｅｒｍｉｏｎｅ） ⇒ ｓｐｏｕｓｅ（Ｈｅｒｍｉｏｎｅ，Ｒｏｎ） ［５］
ｓｐｏｕｓｅ（Ｒｏｎ，Ｈａｒｒｙ） ⇒ ｓｐｏｕｓｅ（Ｈａｒｒｙ，Ｒｏｎ） ［５］
...
>MAX SAT
A
Markov Logic Network
(MLN) for a set of weighted rules (or weighted propositional formulae)
is a Markov Random Network, where the variables are the positive literals and the factors are
rule ｉ satisfied with
?
Markov Logic and Weighted MAX SAT
rule ｉ satisfied ?
rule ｉ satisfied ?
21
Let us find the most likely world:
This is Weighted MAX SAT
->end
What MLNs can do
MLNs can
• compute the most likely world
• compute the marginals
• model the distribution of probabilities
Ｔ
likely worlds
Ｆ
Ｔ
Ｆ
22
->end
The probability of Ｘ＝ｖ depends only on the value of
the predecessor of Ｘ .
The probability of Ｘ＝ｖ depends only on the value of
the neighbors of Ｘ , but neighborhood is symmetric,
and the probability is also conditioned on the “future”
.
MRFs and Markov Chains
23
Markov Random Fields:
Markov Chains:
Summary: Markov Logic
24
Given a set of weighted propositional formulae
a
Markov Logic Network
(MLN) is a Markov Random Network, where the variables are the positive
literals and the factors are
rule ｉ satisfied with
?
.
ｉｓ（Ｒｏｎ， ｉｍｍａｔｕｒｅ） ［１０］
ｉｓ（Ｒｏｎ， ｉｍｍａｔｕｒｅ） ∧ ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ⇒ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ［３］
ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ［４］
?
TRUE
FALSE
TRUE
FALSE
References
25
Markov Logic Networks