Fabian M. Suchanek Markov Logic Reminder Max Sat>8 29
Def: Weighted Rule 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?
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