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 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 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 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