New Rules for Domain-Independent Lifted MAP Inference

In this work by Happy Mittal and team at IIT Delhi, new rules for domain-independent lifted MAP inference are introduced. The study covers motivations, notations, preliminaries, and two main rules. Markov Logic Networks (MLN) are discussed along with examples illustrating friendship, smoking habits, and cancer in a relational model. Various constants and relationships are explored to demonstrate how friendship and smoking behaviors can be inferred.

• Lifted MAP Inference
• Markov Logic Networks
• Relational Models
• Cancer Prediction
• IIT Delhi

alis_39 Follow

Uploaded on Dec 14, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. New Rules for Domain Independent Lifted MAP Inference Happy Mittal (Joint work with Prasoon Goyal, Parag Singla and Vibhav Gogate) Happy.Mittal@cse.iitd.ac.in IIT Delhi

2. Overview Introduction Motivation Notations and preliminaries First rule Second rule Experiments Conclusion and Future work

3. Markov Logic Networks (MLN) Friendship leads to Similar Smoking habits Smoking leads to Cancer Real world problems characterized by Entities and Relationships & Uncertain Behavior Relational Models : Horn clauses, SQL, first-order logic Statistical Models: Markov networks, Bayesian networks Markov Logic [Richardson & Domingos 06] Weighted First Order Formulas

4. Example: Friends & Smokers ( ) ( ) x Smokes x Cancer x , ( , ) ( ) ( ) x y Friends x y Smokes x Smokes y

5. Example: Friends & Smokers ( ) ( ) x Smokes x Cancer x 5 . 1 , ( , ) ( ) ( ) x y Friends x y Smokes x Smokes y 1 . 1

6. Example: Friends & Smokers ( ) ( ) x Smokes x Cancer x 5 . 1 , ( , ) ( ) ( ) x y Friends x y Smokes x Smokes y 1 . 1 Two constants: Ana (A) and Bob (B)

7. Example: Friends & Smokers ( ) ( ) x Smokes x Cancer x 5 . 1 , ( , ) ( ) ( ) x y Friends x y Smokes x Smokes y 1 . 1 Two constants: Ana (A) and Bob (B) Smokes(A) Smokes(B) Cancer(A) Cancer(B)

8. Example: Friends & Smokers ( ) ( ) x Smokes x Cancer x 5 . 1 , ( , ) ( ) ( ) x y Friends x y Smokes x Smokes y 1 . 1 Two constants: Ana (A) and Bob (B) Friends(A,B) Friends(A,A) Smokes(A) Smokes(B) Friends(B,B) Cancer(A) Cancer(B) Friends(B,A)

9. Example: Friends & Smokers ( ) ( ) x Smokes x Cancer x 5 . 1 , ( , ) ( ) ( ) x y Friends x y Smokes x Smokes y 1 . 1 Two constants: Ana (A) and Bob (B) Friends(A,B) Friends(A,A) Smokes(A) Smokes(B) Friends(B,B) Cancer(A) Cancer(B) Friends(B,A)

10. Example: Friends & Smokers ( ) ( ) x Smokes x Cancer x 5 . 1 , ( , ) ( ) ( ) x y Friends x y Smokes x Smokes y 1 . 1 Two constants: Ana (A) and Bob (B) Friends(A,B) Friends(A,A) Smokes(A) Smokes(B) Friends(B,B) Cancer(A) Cancer(B) Friends(B,A)

11. Markov Logic Networks MLN is template for ground Markov nets Probability of a world x: 1 = ( ) exp ( ) P x w f x k k Z k ground formulas 1 Z formulas MLN = ( ) exp ( ) P x w n x i i i Weight of formula i No. of true groundings of formula i in x

12. MAP/MPE Inference 1 arg max exp ( ) w n x i i Z x i arg max ( ) w n x i i x i This is just the weighted MaxSAT problem Use weighted SAT solver (e.g., MaxWalkSAT [Kautz et al. 97] )

13. Normal MLN An MLN is in normal form iff : No constants in any formula Variables X and Y at same position of predicate implies dom(X) = dom(Y) = = ( ) ( ); { , } S X S Y a b Normal Form X Y = = ( ) ( ); { }, { } S X S Y a b Not Normal Form X Y Any MLN can be converted into normal form in polynomial time.

14. Overview Introduction Motivation Notations and preliminaries First rule Second rule Experiments Conclusion

15. MAP/MPE Inference Na ve way : Solve on fully grounded theory Exponential in size of domain of predicates. Exploit symmetries in the theory Example : , ( Y X P ) ( ) ( ) Q X R X ( , ) ( ) ( ) P a Y Q a R a ( , ) ( ) ( ) ( , ) ( ) ( ) P b Y Q b R b P z Y Q z R z All are identical up to constant renaming. Solve one, get solutions for others also. Used decomposer : a variable must appear in each atom of formula

16. MAP/MPE Inference What about No decomposer here. No current technique handle below rule without grounding : ) , ( ) , ( Z Y Friend Y X Friend ( , ) ( , ) ( , ) Parent X Y Friend Y Z Knows X Z ( , ) Friend X Z We give two rules which make MLN having above formulas domain independent Domain Independent inference : Time complexity independent of size of variable domains.

17. Overview Introduction Motivation Notations and preliminaries First rule Second rule Experiments Conclusion and Future work

18. Notations and preliminaries Binding relation : variables X and Y are related if : They appear in same position of a predicate P, or X,Z and Y,Z are related. Example : ) 1 ( ) ( , ) P X Q X Y ) 2 ( ) ( , ) P Z Q U V X ,Z are related, X,U are related, Y,V are related. Intuitively, related variables have to be split together. Relation is symmetric, and transitive, hence splits variables into equivalence classes. X and Y bind to each other if they belong to same equivalence class (denote as X ~ Y) In above example : two equivalence classes {X,Z,U}, {Y,V}

19. Single occurrence Single occurrence equivalence class : If no two variables of that class appear together in any formula. Example : ) , ( ) ( ) 1 V U Q Z P P X Q X Y ) 2 ( ) ( , ) {Y,V} is single occurrence {X,Z,U} is not single occurrence (Z,U appear together) Single occurrence MLN : If each equivalence class is single occurrence. Intuition : Variables in any formula are not tied together.

20. Overview Introduction Motivation Notations and preliminaries First rule Second rule Experiments Conclusion and Future work

21. First rule for lifted MAP inference Given an MLN theory M. Let a single occurrence equivalence class be E. MAP inference over M can be reduced to MAP inference over simpler theory M such that M has : Same formulas as of M (with modified weights) Domain of E is single constant.

22. Constructing M Consider MLN M : ) ( : 1 Z P w ( , ) w P X Q X Y 2 : ( ) ( , ) Q U V : 3 w ( ) R W Let domain of all variables be {a,b,c} 3 equivalence classes : E1={X,Z,U}, E2={Y,V}, E3={W} E2,E3 are single occurrence, E1 is not. Split according to single occurrence equivalence classes. Lets split according to E2 first.

23. Constructing M E2={Y,V} : 1 w ( ) ( , ) w P X Q X Y 2 : ( ) ( , ) P Z Q U V : 3 w ( ) R W Split into E2 theories (having same formulas)

24. Constructing M E2={Y,V} : 1 w ( ) ( , ) w P X Q X Y 2 : ( ) ( , ) P Z Q U V : 3 w ( ) R W : 1 w : 3 w ( ) ( , ) : 1 w : 3 w ( ) ( , ) : 1 w ( ) ( , ) w P X Q X a w P X Q X b w P X Q X c ) 2 : ( ( ) ) ( , ) 2 : ( ( ) ) ( , ) 2 : 3 w : ( ( ) ( , ) P R Z W Q U a P R Z W Q U b P R Z W Q U c M3 M2 M1 For every formula not containing equivalence class E2, divide its weight by E2

25. Constructing M E2={Y,V} : 1 w ( ) ( , ) w P X Q X Y 2 : ( ) ( , ) P Z Q U V : 3 w ( ) R W : 1 w ( ) ( , ) : 1 w ( ) ( , ) : 1 w / 3 w ( ) ( , ) w P X Q X a w P X Q X b w P X Q X c W W 2 / 3 w : ( ) ( ( , ) 2 / 3 w : ( ) ( ( , ) 2 : : 3 ( ) ( ( , ) P : 3 Z R Q ) U a P : 3 Z R Q ) U b P Z R Q ) U c W M2 M3 M1 M can be any of the M1, M2, or M3 MAP inference over M can be reduced to MAP inference over M .

26. Constructing M E2={Y,V} : 1 w ( ) ( , ) w P X Q X Y 2 : ( ) ( , ) P Z Q U V : 3 w ( ) R W : 1 w ( ) ( , ) : 1 w ( ) ( , ) : 1 w / 3 w ( ) ( , ) w P X Q X a w P X Q X b w P X Q X c W W 2 / 3 w : ( ) ( ( , ) 2 / 3 w : ( ) ( ( , ) 2 : : 3 ( ) ( ( , ) P Z R Q ) U a P : 3 Z R Q ) U b P Z R Q ) U c : 3 W M2 M3 M1 Split M2 according to E3 = {W} now

27. Constructing M E3={W} : 1 w ( ) ( , ) w P X Q X Y 2 : ( ) ( , ) P Z Q U V : 3 w ( ) R W : 1 w ( ) ( , ) : 1 w ( ) ( , ) : 1 w / 3 w ( ) ( , ) w P X Q X a w P X Q X b w P X Q X c W W 2 / 3 w : ( ) ( ( , ) 2 / 3 w : ( ) ( ( , ) 2 : : 3 ( ) ( ( , ) P Z R Q ) U a P : 3 Z R Q ) U b P Z R Q ) U c : 3 W M2 M3 M1 : 1 w ( ) ( , ) : 1 w ( ) ( , ) : 1 w ( ) ( , ) w P X Q X b w P X Q X b w P X Q X b a ) b ) c 2 / 3 w : ( ) ( ( , ) 2 / 3 w : ( ) ( ( , ) 2 / 3 w : ( ) ( ( , ) P : 3 Z R Q U b P : 3 Z R Q U b P : 3 Z R Q U b )

28. Constructing M E3={W} : 1 w ( ) ( , ) w P X Q X Y 2 : ( ) ( , ) P Z Q U V : 3 w ( ) R W : 1 w ( ) ( , ) : 1 w ( ) ( , ) : 1 w / 3 w ( ) ( , ) w P X Q X a w P X Q X b w P X Q X c W W 2 / 3 w : ( ) ( ( , ) 2 / 3 w : ( ) ( ( , ) 2 : : 3 ( ) ( ( , ) P Z R Q ) U a P : 3 Z R Q ) U b P Z R Q ) U c : 3 W M2 M3 M1 / 1 w : 3 ( ) ( , ) / 1 w : 3 ( ) ( , ) / 1 w : 3 ( ) ( , ) w P X Q X b w P X Q X b w P X Q X b 2 / 3 w : 3 / : 3 ( ( ) ( , ) 2 / 3 w : 3 / : 3 ( ( ) ( , ) 2 / 3 w : 3 / : 3 ( ( ) ( , ) P R Z a Q U b P R Z b Q U b P R Z c Q U b ) ) )

29. First rule for lifted MAP inference Given an MLN theory M. Let a single occurrence equivalence class be E. MAP inference over M can be reduced to MAP inference over simpler theory M such that M has : Same formulas as of M (with modified weights) Domain of E is single constant.

30. Proof Proof can be divided into 4 steps : Step 1 Set of weighted constraints in M is union of set of weighted constraints in sub theories M1, M2, , Mr ) , ( ) ( : 1 a U Q Z P w ) ( : 3 / 3 W R w : 3 / 3 w w P X Q X a : 1 w ( ) ( , ) : 1 w / 3 w ( ) ( , ) w P X Q X b w P X Q X c 2 : ( ) ( , ) 2 : ( ) ( ( , ) 2 : : 3 ( ) ( ( , ) P Z R Q ) U b P Z R Q ) U c W W

31. Proof Proof can be divided into 4 steps : Step 1 Set of weighted constraints in M is union of set of weighted constraints in sub theories M1, M2, , Mr ) , ( ) ( : 1 a U Q Z P w ) ( : 3 / 3 W R w : 3 / 3 w w P X Q X a : 1 w ( ) ( , ) : 1 w / 3 w ( ) ( , ) w P X Q X b w P X Q X c 2 : ( ) ( , ) 2 : ( ) ( ( , ) 2 : : 3 ( ) ( ( , ) P Z R Q ) U b P Z R Q ) U c W W Proof : For formula containing variable of class E2 : partial groundings split across all sub theories.

32. Proof Proof can be divided into 4 steps : Step 1 Set of weighted constraints in M is union of set of weighted constraints in sub theories M1, M2, , Mr : 1 w ( ) ( , ) w P X Q X a : 1 w / 3 w ( ) ( , ) : 1 w / 3 w ( ) ( , ) w P X Q X b w P X Q X c W 2 / 3 w : : 3 ( ) ( ( , ) P Z R Q ) U a 2 : : 3 ( ) ( ( , ) 2 : : 3 ( ) ( ( , ) P Z R Q ) U b P Z R Q ) U c W W Proof : For formula containing variable of class E2 : partial groundings split across all sub theories. For formula not containing variable of class E2 : weight divided equally among all sub theories, hence total weight is original weight in M.

33. Proof Step 1 Set of weighted constraints in M is union of set of weighted constraints in sub theories M1, M2, , Mr : 1 w ( ) ( , ) w P X Q X a : 1 w / 3 w ( ) ( , ) : 1 w / 3 w ( ) ( , ) w P X Q X b w P X Q X c W 2 / 3 w : ( ) ( ( , ) P : 3 Z R Q ) U a 2 : : 3 ( ) ( ( , ) 2 : : 3 ( ) ( ( , ) P Z R Q ) U b P Z R Q ) U c W W Proof : For formula containing variable of equivalence class E2 : partial groundings are split across all sub theories. For formula not containing variable of class E2 : weight divided equally among all sub theories, hence total weight is original weight in M.

34. Proof Step 2 MAP assignments across sub theories are same up to constant renaming. ) , ( ) ( : 1 a U Q Z P w ) ( : 3 / 3 W R w : 1 w ( ) ( , ) : 1 w ( ) ( , ) w P X Q X c w P X Q X a w P X Q X b 2 : ( ) ( , ) 2 : ( ) ( , ) 2 : ( ) ( , ) P Z Q U c P Z Q U b / 3 w : 3 ( ) R W / 3 w : 3 ( ) R W Proof : Follows from symmetry of sub theories.

35. Proof Step 3 MAP solution XMAP for M can be obtained from any of the sub-theory Mj.. ) , ( ) ( : 1 a U Q Z P w ( : 3 / 3 W R w : 1 w ( ) ( , ) : 1 w ( ) ( , ) w P X Q X b w P X Q X c w P X Q X a 2 : ( ) ( , ) 2 : ( ) ( , ) 2 : ( ) ( , ) P Z Q U c P Z Q U b / 3 w : 3 ( ) R W / 3 w : 3 ( ) ) R W Create MAP solution XMAP for M as follows : Predicate not containing variable of class E2, : Use solution from MAP of M1 . Ex : P(X), R(W) Predicate containing variable from class E2, Read off any of its partial grounding s assignment in any theory Mj. Ex : Any of the Q(X,a), Q(X,b), or Q(X,c) will work.

36. Proof Step 4 XMAP is indeed a MAP solution for M : 1 w ( ) ( , ) : 1 w ( ) ( , ) : 1 w ( ) ( , ) w P X Q X b w P X Q X c w P X Q X a 2 : ( ) ( , ) P Z Q U a 2 : ( ) ( , ) 2 : ( ) ( , ) P Z Q U c P Z Q U b / 3 w : 3 ( ) R W / 3 w : 3 ( ) / 3 w : 3 ( ) R W R W Proof : Suppose it is not, then let XALT exists such that WM(XALT) > WM(XMAP) But then WM(XjALT) > WM(XjMAP) Which means there is some sub theory j, whose XjMAP is not a MAP solution, which is a contradiction. r r = j 1 = j 1

37. Algorithm Input : MLN M Initialize M = M For each single occurrence equivalence class E in M : For each formula F in M : If F doesn t contain any variable from E : Set WF = WF/ E Set domain E to be single constant Return M

38. Domain Independent Lifted MAP Theorem : MAP inference in single occurrence MLN is domain independent. Proof : Since MLN is single occurrence, Successively reduce domain of each single occurrence equivalence class to be a constant. Since MLN is single occurrence, all variables domain reduced to constant. Hence domain independent MAP inference.

39. Overview Introduction Motivation Notations and preliminaries First rule Second rule Experiments Conclusion and Future work

40. Exploiting Extremes Extreme assignment : In assignment x, predicate P is at extreme if all its groundings are either true or false. F(X,Y) ^ F(Y,Z) => F(X,Z) Suppose F is at extreme 0 ^ 0 => 0 OR 1 ^ 1 => 1 Tautology at extreme How can we exploit this tautology ?

41. Exploiting Extremes Consider MLN : W1 : P(X) => Q(X,Y) W2 : Q(X,Y) ^ Q(Y,Z) => Q(X,Z) Suppose Q is at extreme Then Q(X,Y) ^ Q(Y,Z) => Q(X,Z) is tautology We can just solve W1 : P(X) => Q(X,Y) W2 : Q(X,Y) ^ Q(Y,Z) => Q(X,Z) How do we know if some predicate is at extreme ? First rule tells that

42. Exploiting Extremes Theorem : If Predicate P is single occurrence in M, then P has an extreme assignment in XMAP : 1 w ( ) ( , ) w P X Q X Y E3={W} 2 : ( ) ( , ) P Z Q U V : 3 w ( ) R W : 1 w ( ) ( , ) : 1 w ( ) ( , ) : 1 w ( ) ( , ) w P X Q X Y w P X Q X Y w P X Q X Y 2 : 3 w : ( ( ) ) ( , ) 2 : 3 w : ( ) ) ( , ) 2 : 3 w : ( ) ) ( , ) P R Z a Q U V P R Z ( b Q U V P R Z ( Q U V c M3 M2 M1 In single occurrence MLN, all predicates are at extreme in MAP assignment.

43. Second rule for lifted MAP Consider MLN : W1 : P(X) => Q(X,Y) W2 : Q(X,Y) ^ Q(Y,Z) => Q(X,Z) Is it single occurrence MLN ? No Now ? W1 : P(X) => Q(X,Y) W2 : Q(X,Y) ^ Q(Y,Z) => Q(X,Z) Yes P and Q have extreme assignments in MAP But Q(X,Y) ^ Q(Y,Z) => Q(X,Z) is tautology at extreme. So solve W1 : P(X) => Q(X,Y) W2 : Q(X,Y) ^ Q(Y,Z) => Q(X,Z)

44. Second rule for Lifting MAP Second Rule : If MLN is single occurrence after removing tautology at extremes, then MAP inference in original MLN is domain independent. In general, only variables appearing in tautology at extremes must be single occurrence for second rule to apply.

45. Second rule for Lifting MAP How to identify tautology at extremes : Necessary and sufficient condition : A clause must have both positive and negative occurrences of same predicate symbol. !F(X,Y) V !F(Y,Z) V F(X,Z)

46. Algorithm to find single occurrence tautology at extremes Input : MLN M Initialization : Fte = all tautologies at extreme F = remaining formulas (F Fte) Done = False While(not Done) Done = True EQ = single occurrence variables in F For each formula f in Fte If there is variable in f not in EQ Add f into F ; Done = False Return F - F

47. Comparison with others work Decomposer : If class E is decomposer, it is also single occurrence. E is decomposer iff : 1. If variable of E appears in formula, then it occurs in all preds of that formula. 2. No two variables in E appear together in a predicate i.e. P(X,Y) is not allowed if X,Y are in E. E is single occurrence : Because no two variables X and Y from E can occur together in formula Sarkhel et. al [2014] s non-shared MLN approach : If MLN is non-shared and without self join, it is single occurrence. P(X) V Q(Y,Z) P(A) V Q(B,C) Equivalence classes : {X,A} , {Y,B}, {Z,C} -> same predicate, same position No two variables in an equivalence class can occur in same formula : Because of non-self join.

48. Overview Introduction Motivation Notations and preliminaries First rule Second rule Experiments Conclusion and Future Work

49. Experiments Compared our performance with Purely grounded version of benchmark MLNs Sarkhel et al. [2014] s non shared MLN approach Used ILP based solver Gurobi as base solver. Notation : GRB : purely grounded version NSLGRB : Sarkhel et al. [2014] s non shared MLN approach SOLGRB : our approach (single occurrence lifted GRB)

50. Datasets and Methodology Used 2 benchmark MLNs : Dataset No. of Single Occurrence No (Mix) Taut. At extereme No Example formulas formulas 7 IE Token(t,p,c)=>InField(p,f,c) !Equal(f1,f2) ^ InField(p,f1,c) => !InField(p,f2,c) etc S(x) => C(x) F(x,y) ^ F(y,z) => F(x,z) etc FS 5 No (Mix) Yes For each algorithm, we report : Time to reach optimal with varying domain size. Cost of unsatisfied clauses with varying running time (fixed domain size of 500) Ground theory size with varying domain size.

Load More ...