Fabian M. Suchanek
Markov Logic
Reminder Max Sat>8
29
Def: Weighted Rule
A
weighted rule
is a rule with an associated real-valued weight.
2
We consider only rules without variables for now.
Def: Weight of a KB
Given a KB (a “possible world”) and a set of instantiated rules with
weights, the
weight of the KB
is the sum of the weights
of all true rules.
3
hasSpouse
hasSpouse
hasSpouse
KB1
KB2
Def: Weight of a KB
4
hasSpouse
hasSpouse
hasSpouse
KB1
KB2
Weight: 2
Weight: 5
Given a KB (a “possible world”) and a set of instantiated rules with
weights, the
weight of the KB
is the sum of the weights
of all true rules.
Def: Weighted MAX SAT
Given a set of instantiated rules with weights,
weighted MAX SAT
is the
problem of finding the KB with the highest weight.
5
(Since SAT is NP-complete, so is MAX SAT and Weighted MAX SAT. There may be multiple such worlds. We are interested in minimal worlds.)
Def: Weighted MAX SAT
Given a set of instantiated rules with weights,
weighted MAX SAT
is the
problem of finding the KB with the highest weight.
6
(Since SAT is NP-complete, so is MAX SAT and Weighted MAX SAT. There may be multiple such worlds. We are interested in minimal worlds.)
weight: 17
Best world:
task>8
Task: Weighted MAX SAT
Find the KB with the highest weight:
Hint: Start by satisfying disjunctions with one literal and high weight.
7
Let us see every ground literal as a random variable
with values T and F:
A probabilistic view
possible
worlds with
probabilities
8
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
.
Markov Random Fields
9
Example: Markov Random Field
10
X2
w1:
P(w3)=0.02
w4:
P(w4)=0.02
P(w1)=0.1
Shrek
X1
purrs
Shrek
P(w2)=0.1
Shrek
w3:
shouts
Shrek
shouts
w2:
purrs
X3
X4
X5
with
pleasure
with
w5:
pleasure
shouts
with
...
Puss
P(w5)=0.01
world
probability
...
...
ferociously
pleasure
ferociously
ferociously
Example: Markov Random Field
11
X2
w1:
P(w3)=0.02
w4:
P(w4)=0.02
P(w1)=0.1
Shrek
X1
purrs
Shrek
P(w2)=0.1
Shrek
w3:
shouts
Shrek
shouts
w2:
purrs
X3
X4
X5
with
pleasure
with
w5:
pleasure
shouts
with
...
Puss
P(w5)=0.01
world
probability
...
...
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
ferociously
pleasure
ferociously
ferociously
Example: Markov Random Field
12
X2
w1:
P(w3)=0.02
w4:
P(w4)=0.02
P(w1)=0.1
Shrek
X1
purrs
Shrek
P(w2)=0.1
Shrek
w3:
shouts
Shrek
shouts
w2:
purrs
X3
X4
X5
with
pleasure
w5:
pleasure
shouts
with
Puss
P(w5)=0.01
world
probability
Neighbor sets:
...
...
...
with
ferociously
pleasure
ferociously
ferociously
We depict the neighborhood as an undirected graph,
where the nodes are variables, and
is an edge if
.
Def: MRF graph
13
X2
w1:
P(w3)=0.02
w4:
P(w4)=0.02
P(w1)=0.1
Shrek
X1
purrs
Shrek
P(w2)=0.1
Shrek
w3:
shouts
Shrek
shouts
w2:
purrs
X3
X4
X5
ferociously
with
pleasure
pleasure
w5:
pleasure
shouts
with
ferociously
Puss
P(w5)=0.01
world
probability
...
...
...
ferociously
with
We consider the maximal cliques in the neighborhood graph.
Maximal cliques
14
X2
w1:
P(w3)=0.02
w4:
P(w4)=0.02
P(w1)=0.1
Shrek
X1
purrs
Shrek
P(w2)=0.1
Shrek
w3:
shouts
Shrek
shouts
w2:
purrs
X3
X4
X5
ferociously
with
pleasure
pleasure
w5:
pleasure
shouts
with
ferociously
Puss
P(w5)=0.01
world
probability
...
...
...
ferociously
with
We write
Hammersley-Clifford-Theorem
15
X2
w1:
P(w3)=0.02
w4:
P(w4)=0.02
P(w1)=0.1
Shrek
X1
purrs
Shrek
P(w2)=0.1
Shrek
w3:
shouts
Shrek
shouts
w2:
purrs
X3
X4
X5
ferociously
with
pleasure
pleasure
w5:
pleasure
shouts
with
ferociously
Puss
P(w5)=0.01
world
probability
...
...
...
ferociously
with
If all probabilities in an MRF are
, then
such that
.
>example
Hammersley-Clifford-Theorem
16
X2
w1:
P(w3)=0.02
w4:
P(w4)=0.02
P(w1)=0.1
Shrek
X1
purrs
Shrek
P(w2)=0.1
Shrek
w3:
shouts
Shrek
shouts
w2:
purrs
X3
X4
X5
ferociously
with
pleasure
pleasure
w5:
pleasure
shouts
with
ferociously
Puss
P(w5)=0.01
world
probability
...
...
...
ferociously
with
If all probabilities in an MRF are
, then
such that
.
?
?
(example might
not sum to 1)
Back to the logical worlds
Rule 42:
17
w1:
likes(H., Ron)
...
w2:
world
...
P(w1)=0.1
P(w2)=0.1
probability
T
T
spouse(Harry,Ron)
F
F
F
F
Let’s define
rule
satisfied with
?
:
)
spouse(Ron,Harry)
>example
Back to the logical worlds
Rule 42:
18
w1:
likes(H., Ron)
...
w2:
world
...
P(w1)=0.1
P(w2)=0.1
probability
T
T
spouse(Harry,Ron)
F
F
F
F
Let’s define
rule
satisfied with
?
:
)
spouse(Ron,Harry)
>example
?
Example: Markov Logic Network
19
Original Weighted MAX SAT problem:
Assignment to variables:
Factors:
Example: Markov Logic Network
20
Original Weighted MAX SAT problem:
Assignment to variables:
Factors:
?
?
?
if
else
Example: Markov Logic Network
21
Original Weighted MAX SAT problem:
Assignment to variables:
Factors:
?
?
?
if
else
A world becomes
more
likely if formula
is satisfied.
22
LivePhysics Plotter
Normalization still missing
Factors as continuums
TRUE
FALSE
TRUE
FALSE
TRUE
Example: Markov Logic Network
>Normalization
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!
23
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
24
>end
Quantified formulas
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
?
25
Formulas with universally quantified variables such as
have to be replaced by all of their ground instances:
...
>MAX SAT
Markov Logic and Weighted MAX SAT
rule
satisfied ?
rule
satisfied ?
26
Let us find the most likely world:
This is Weighted MAX SAT
What MLNs can do
MLNs can
• compute the most likely world
• compute the marginals
• model the distribution of probabilities
likely worlds
27
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”
.
Appendix: MRFs and Markov Chains
28
Markov Random Fields:
Markov Chains:
References
29
Markov Logic Networks