CC-BY Fabian M. Suchanek Rule Mining 140
© TV week © Dailymail © Public Domain CC by Jean-Marc Ayrault CC by Matthieu Riegler © Voici Rules hasChild citizenOf hasChild marriedTo marriedTo citizenOf hasChild hasChild hasChild 2 presidentOf hasChild
© TV week © Dailymail © Public Domain CC by Jean-Marc Ayrault CC by Matthieu Riegler © Voici Rules 3 “Whenever someone has a child, this is also the child of the spouse” ｙ  ｚ  ｘ  marriedTo hasChild hasChild hasChild citizenOf hasChild marriedTo marriedTo citizenOf hasChild hasChild hasChild presidentOf hasChild
© TV week © Dailymail © Public Domain ｈａｓＣｈｉｌｄ（ｘ，ｙ）  ∧ ｍａｒｒｉｅｄＴｏ（ｘ，ｚ）  ⇒ ｈａｓＣｈｉｌｄ（ｚ，ｙ）  (rules don’t have to be always correct) Rule Mining 4 hasChild citizenOf hasChild marriedTo marriedTo citizenOf hasChild presidentOf hasChild
ｐｒｅｓｉｄｅｎｔＯｆ（ｘ，ｚ） ∧ ｈａｓＣｈｉｌｄ（ｙ，Ｍａｌｉ）  ⇒ ｍａｒｒｉｅｄＴｏ（ｘ，ｙ）  Rule Mining 5 ? >uses © TV week © Dailymail © Public Domain hasChild citizenOf hasChild marriedTo marriedTo citizenOf hasChild presidentOf hasChild
ｈａｓＣｈｉｌｄ（ｘ，ｙ） ∧ ｍａｒｒｉｅｄＴｏ（ｘ，ｚ）  ⇒ ｈａｓＣｈｉｌｄ（ｚ，ｙ）  Rule Mining for Completion 6 >uses marriedTo hasChild
Rule Mining for Completion 7 hasChild >uses ｈａｓＣｈｉｌｄ（ｘ，ｙ） ∧ ｍａｒｒｉｅｄＴｏ（ｘ，ｚ）  ⇒ ｈａｓＣｈｉｌｄ（ｚ，ｙ）  marriedTo hasChild
Rule Mining for Correction 8 marriedTo hasChild hasChild >uses ｈａｓＣｈｉｌｄ（ｘ，ｙ） ∧ ｍａｒｒｉｅｄＴｏ（ｘ，ｚ）  ⇒ ｈａｓＣｈｉｌｄ（ｚ，ｙ） 
Rule Mining for Correction 9 marriedTo hasChild hasChild >uses ｈａｓＣｈｉｌｄ（ｘ，ｙ） ∧ ｍａｒｒｉｅｄＴｏ（ｘ，ｚ）  ⇒ ｈａｓＣｈｉｌｄ（ｚ，ｙ）  x
ｈａｓＣｈｉｌｄ（ｘ，ｙ） ∧ ｍａｒｒｉｅｄＴｏ（ｘ，ｚ） ⇒ ｈａｓＣｈｉｌｄ（ｚ，ｙ）  ｉｎ（ｘ， Ｅｕｒｏｐｅ） ∧ ｐｒｅｓｉｄｅｎｔ（ｘ， ｙ） ⇒ ｍａｌｅ（ｘ）  ｍａｒｒｉｅｄ（ｘ， ｙ） ⇒ ｍａｒｒｉｅｄ（ｙ， ｘ）  ... obvious for us, but non-trivial for a computer. Applications in •   artificial intelligence / question answering •   information extraction (see lecture) •   science •   engineering (fault finding) •   medicine •   social network mining Rule Mining for Insights 10 ... in ｎ % of the cases ... in ｎ % of the cases
ｔｙｐｅ（ｘ， ｓｏｒｃｅｒｅｓｓ） ∧ ｄｕｍｂ（ｙ） ⇒ ｌｉｋｅｓ（ｘ， ｙ）  ?  Running example 11 likes likes is dumb childish is smart is is male gender gender sorceress type >atoms ->bindings
12 likes envies likes Refresh: Atoms and KBs An atom Ａ  is a propositional statement. Ａ  is a positive literal, and ¬ Ａ  is a negative literal. The polarity is positive for Ａ , and negative for  ¬ Ａ . A positive literal holds (“is true”) in a KB, if it appears in the KB. A negative literal ¬ Ａ  holds in a KB if Ａ  does not hold. ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ）   ? ¬ ｅｎｖｉｅｓ（Ｒｏｎ， Ｈａｒｒｙ）   ? We work here under the closed world assumption: what is not in the KB is assumed to be false
13 Refresh: Atoms and KBs An positive literal holds (“is true”) in a KB, if it appears in the KB. A negative literal ¬ Ａ  holds in a KB if Ａ  does not hold. A conjunction Ａ ∧ Ｂ ∧．．． ∧ Ｚ  holds in a KB, if all of its elements hold. ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ）   ? ¬ ｅｎｖｉｅｓ（Ｒｏｎ， Ｈａｒｒｙ）   ? ¬ ｅｎｖｉｅｓ（Ｒｏｎ， Ｈａｒｒｙ） ∧ ｌｉｋｅｓ（Ｈａｒｒｙ， Ｈｅｒｍｉｏｎｅ）  ｅｎｖｉｅｓ（Ｈａｒｒｙ， Ｒｏｎ） ∧ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ∧ ｌｉｋｅｓ（Ｈａｒｒｙ， Ｅｌｖｉｓ）  likes envies likes
ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ⇒ ｌｉｋｅｓ（Ｈａｒｒｙ，Ｒｏｎ）  ｌｉｋｅｓ（Ｈａｒｒｙ， Ｒｏｎ） ⇒ ｈａｓＳｐｏｕｓｅ（Ｈａｒｒｙ，Ｈｅｒｍｉｏｎｅ）  ¬ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｈａｒｒｙ） ⇒ ｅｎｖｉｅｓ（Ｈａｒｒｙ，Ｒｏｎ）  ¬ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｈａｒｒｙ） ⇒ ｈａｓＳｐｏｕｓｅ（Ｈａｒｒｙ，Ｒｏｎ）  ｌｉｋｅｓ（Ｈｅｒｍ．， Ｒｏｎ）∧ ¬ ｅｎｖｉｅｓ（Ｈａｒｒｙ，Ｒｏｎ）⇒ ｆｆｅ（Ｈａｒｒｙ，Ｒｏｎ）  14 Refresh: Implications If   is a conjunction (called the body), and Ｈ  is an atom (called the head), then an implication   holds in a KB if   does not hold or Ｈ  holds. likes envies likes
ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ）  15 Refresh: Implications If   is a conjunction (called the body), and Ｈ  is an atom (called the head), then an implication   holds in a KB if   does not hold or Ｈ  holds. The body can also be empty. is a body‐less rule, i.e., equivalent to: ⇒ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ）  likes envies likes
16 Def: Rules, Disjunctions, Clauses An implication (also: rule)  is equivalent to a disjunction  which we also write as a clause  . ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ⇒ ｌｉｋｅｓ（Ｈａｒｒｙ，Ｒｏｎ）  ¬ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ∨ ｌｉｋｅｓ（Ｈａｒｒｙ，Ｒｏｎ）  ｛¬ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ）， ｌｉｋｅｓ（Ｈａｒｒｙ，Ｒｏｎ） ｝  “at least one of  these has to hold” is equivalent to is equivalent to likes envies likes
A substitution is a function from variables to constants or variables. Def: Substitution 17 (This is done only once, not iterated) For a formula φ  and a substitution θ , we write θ（φ）  to mean the formula obtained by replacing all variables as given by the substitution. We now allow variables to appear in atoms and formulas, as in: Intuitively, a formula with variables holds if it holds for all values of the variable (the variables are universally quantified). We will now make this intuition more formal. ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ⇒ ｈａｔｅｓ（Ｈａｒｒｙ， ｘ）  θ ＝ ｛ ｘ → ｙ， ｙ → ｚ， ｚ → Ｒｏｎ ｝ 
θ（φ） ＝ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｙ） ⇒ ｈａｔｅｓ（Ｈａｒｒｙ， ｙ）  ｙ  is not replaced! Def: Substitution 18 We now allow variables to appear in atoms and formulas, as in: ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ⇒ ｈａｔｅｓ（Ｈａｒｒｙ， ｘ）  >subst A substitution is a function from variables to constants or variables. For a formula φ  and a substitution θ , we write θ（φ）  to mean the formula obtained by replacing all variables as given by the substitution. θ ＝ ｛ ｘ → ｙ， ｙ → ｚ， ｚ → Ｒｏｎ ｝  Intuitively, a formula with variables holds if it holds for all values of the variable (the variables are universally quantified). We will now make this intuition more formal. (This is done only once, not iterated)
θ ＝ ｛ ｘ → Ｒｏｎ， ｙ → Ｅｌｖｉｓ ｝  An instantiation (ground instance) of a rule by a binding is the rule obtained by substituting all variables by the constants given by the binding. θ（φ）＝   ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ） ⇒ ｈａｔｅｓ（Ｈａｒｒｙ， Ｒｏｎ）  Def: Bindings 19 A binding is a substitution that maps variables to constants (not to other variables): We now allow variables to appear in atoms and formulas, as in: φ＝  ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ⇒ ｈａｔｅｓ（Ｈａｒｒｙ， ｘ）  A rule with variables holds if all of its instantiations hold.
An atom ｐ  is the prediction of a rule ｒ  on a KB, if there is a binding so that all body atoms are in the KB and ｐ  is the head atom. We write ＫＢ ∧ ｒ ⊧ ｐ . ｍａｒｒｉｅｄＴｏ（ｘ， ｙ） ∧ ｈａｓＣｈｉｌｄ（ｘ， ｚ） ⇒ ｈａｓＣｈｉｌｄ（ｙ， ｚ）  Predictions of a Rule 20 hasChild marriedTo hasChild
ｍａｒｒｉｅｄＴｏ（ｘ， ｙ） ∧ ｈａｓＣｈｉｌｄ（ｘ， ｚ） ⇒ ｈａｓＣｈｉｌｄ（ｙ， ｚ）  Predictions: •   x=Barack, y=Michelle, z=Malia: hasChild(Michelle, Malia) •  x=Barack, y=Michelle, z=Sasha: hasChild(Michelle, Sasha) Predictions of a Rule hasChild marriedTo hasChild 21 >spec&queries An atom ｐ  is the prediction of a rule ｒ  on a KB, if there is a binding so that all body atoms are in the KB and ｐ  is the head atom. We write ＫＢ ∧ ｒ ⊧ ｐ .
Intuitively, some rules are more general than others: ｄｕｍｂ（ｘ） ∧ ｇｅｎｄｅｒ（ｘ， ｙ） ⇒ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）  General and specific rules 1/2 22
Intuitively, some rules are more general than others: ｄｕｍｂ（ｘ） ∧ ｇｅｎｄｅｒ（ｘ， ｙ） ⇒ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）  General and specific rules 1/2 23 General rule The more specific rule adds more conditions, and applies to less people. ｄｕｍｂ（ｘ） ∧ ｇｅｎｄｅｒ（ｘ， ｍａｌｅ） ⇒ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）  Applies only to male ｘ  More specific rule
Intuitively, some rules are more general than others: ｄｕｍｂ（ｘ） ∧ ｇｅｎｄｅｒ（ｘ， ｙ） ⇒ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）  General and specific rules 2/2 24 The more specific rule adds more conditions, and applies to less people. ｄｕｍｂ（ｘ） ∧ ｇｅｎｄｅｒ（ｘ， ｙ） ∧ ｐｏｏｒ（ｘ） ⇒ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）  Applies only to ｘ  that are also poor >subsume&queries General rule More specific rule
A clause φ  subsumes another clause φ＇  if there is a substitution θ ,  such that θ（φ） ⊆ φ＇ . The first clause is more general than the second. Def: Subsumption 25 ｄｕｍｂ（ｘ） ∧ ｇｅｎｄｅｒ（ｘ， ｙ） ⇒ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）  ｄｕｍｂ（ｘ） ∧ ｇｅｎｄｅｒ（ｘ， ｍａｌｅ） ⇒ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）  ｛¬ ｄｕｍｂ（ｘ）， ¬ ｇｅｎｄｅｒ（ｘ， ｙ）， ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ｝  ｛¬ ｄｕｍｂ（ｘ）， ¬ ｇｅｎｄｅｒ（ｘ， ｍａｌｅ）， ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ｝  θ＝｛ｙ→ ｍａｌｅ｝  ⊆ 
A clause φ  subsumes another clause φ＇  if there is a substitution θ ,  such that θ（φ） ⊆ φ＇ . The first clause is more general than the second. Def: Subsumption 26 ｄｕｍｂ（ｘ） ∧ ｇｅｎｄｅｒ（ｘ， ｙ） ⇒ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）  ｄｕｍｂ（ｘ） ∧ ｇｅｎｄｅｒ（ｘ， ｙ） ∧ ｐｏｏｒ（ｘ） ⇒ ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）  ｛¬ ｄｕｍｂ（ｘ）， ¬ ｇｅｎｄｅｒ（ｘ， ｙ）， ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ｝  ｛¬ ｄｕｍｂ（ｘ）， ¬ ｇｅｎｄｅｒ（ｘ， ｙ）， ¬ ｐｏｏｒ（ｘ）， ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ｝  θ＝｛｝  ⊆ 
omit atom ｔｙｐｅ（ｘ， ｓｏｒｃｅｒｅｓｓ） ∧ ｄｕｍｂ（Ｒｏｎ）  ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ∧ ｃｈｉｌｄｉｓｈ（Ｒｏｎ）  ⇒ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ）  ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ∧ ｄｕｍｂ（Ｒｏｎ）  ∧ ｃｈｉｌｄｉｓｈ（Ｒｏｎ） ⇒ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， Ｒｏｎ）  ∧ ｃｈｉｌｄｉｓｈ（Ｒｏｎ） ⇒ ｌｉｋｅｓ（ｘ， Ｒｏｎ）  introduce variable ｌｉｋｅｓ（ｘ， ｙ）  Generalization lattice 27
add atom ∧ ｃｈｉｌｄｉｓｈ（Ｒｏｎ） ⇒ ｌｉｋｅｓ（Ｈｅｒｍ．， Ｒｏｎ）  Specialization lattice 28 >queries ⇒ ｌｉｋｅｓ（Ｈｅｒｍ．， Ｒｏｎ）  ｔｙｐｅ（ｘ， ｓｏｒｃｅｒｅｓｓ） ∧ ｄｕｍｂ（Ｒｏｎ）  ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ∧ ｃｈｉｌｄｉｓｈ（Ｒｏｎ）  ∧ ｃｈｉｌｄｉｓｈ（Ｒｏｎ） ⇒ ｌｉｋｅｓ（ｘ， Ｒｏｎ）  remove variable ｌｉｋｅｓ（ｘ， ｙ）  ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ， ｓｏｒｃｅｒｅｓｓ） ∧ ｄｕｍｂ（Ｒｏｎ） 
A (conjunctive) query is a conjunction of literals An answer to a query for a given KB is a binding that makes the query true in the KB. ｌｏｖｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ） ∧ ｄｕｍｂ（ｘ） ∧ ｓｍａｒｔ（ｙ）   ? ｛ ｘ → Ｒｏｎ， ｙ → Ｈａｒｒｙ ｝  Query 29 >queries
• More general, subsuming query Q1: • More specific, subsumed queries Q2, Q2': ｉｓ（ｘ，ｓｍａｒｔ） ∧ ｌｉｋｅｓ（ｘ，ｙ） ⇒ ａｎｓｗｅｒ（ｘ）  ｉｓ（ｘ，ｓｍａｒｔ） ∧ ｌｉｋｅｓ（ｘ， Ｒｏｎ） ⇒ ａｎｓｗｅｒ（ｘ）  ｉｓ（ｘ，ｓｍａｒｔ） ∧ ｌｉｋｅｓ（ｘ，ｙ） ∧ ｇｅｎｄｅｒ（ｘ，ｍａｌｅ） ⇒ ａｎｓｗｅｒ（ｘ）  Query subsumption 30 is gender is likes male likes gender smart likes >queries
ｉｓ（ｘ，ｓｍａｒｔ） ∧ ｌｉｋｅｓ（ｘ， Ｒｏｎ） ⇒ ａｎｓｗｅｒ（ｘ）  All answers to a more specific query are also answers to the more general query (with the same head). Query subsumption 31 ｉｓ（ｘ，ｓｍａｒｔ） ∧ ｌｉｋｅｓ（ｘ，ｙ） ⇒ ａｎｓｗｅｒ（ｘ）  ｉｓ（ｘ，ｓｍａｒｔ） ∧ ｌｉｋｅｓ（ｘ，ｙ） ∧ ｇｅｎｄｅｒ（ｘ，ｍａｌｅ） ⇒ ａｎｓｗｅｒ（ｘ）  >queries • More general, subsuming query Q1: • More specific, subsumed queries Q2, Q2':
ｌｉｋｅｓ（ｘ， ｙ） ∧ ｇｅｎｄｅｒ（ｘ， ｍａｌｅ）  ?  ｇｅｎｄｅｒ（ｘ， ｍａｌｅ）  ?  ｌｉｋｅｓ（ｘ， ｙ） ∧ ｉｓ（ｙ， ｓｍａｒｔ） ∧ ｇｅｎｄｅｒ（ｙ， ｍａｌｅ） ?  Example 32 likes likes is dumb childish is smart is is male gender gender sorceress type likes >queries
A query can be written as a rule. The body of a rule is basically a query. ｌｉｋｅｓ（ｘ， ｙ） ∧ ｇｅｎｄｅｒ（ｘ， ｍａｌｅ）  ⇒ ａｎｓｗｅｒ（ｘ， ｙ）  ｇｅｎｄｅｒ（ｘ， ｍａｌｅ） ∧ ｉｓ（ｘ， ｄｕｍｂ） ⇒ ｌｉｋｅｓ（Ｈｅｒｍｉｏｎｅ， ｘ）  Queries and Rules 33 likes likes is dumb childish is smart is is male gender gender sorceress type likes query
Overview Introduction to Rules Rule Mining •  Inductive Logic Programming •  Confidence in a KB •  Top-Down Rule Mining •  Bottom-Up Rule Mining  34
35 smart is is gender male dumb likes Summary: Rule Mining Inductive Logic Programming (ILP) is the task of finding hypotheses that cover examples •   ILP can be performed top-down by specialization (AMIE, Rudik) •   ... or bottom-up by generalization (GOLEM, AnyBURL) Something similar can be achieved by embeddings.
Summary: Rule Mining 36 dumb gender male is is likes smart likes Open World Assumption! Inductive Logic Programming (ILP) is the task of finding hypotheses that cover examples •   ILP can be performed top-down by specialization (AMIE, Rudik) •   ... or bottom-up by generalization (GOLEM, AnyBURL) Something similar can be achieved by embeddings. ->Embeddings ->Deep-learning
Luis Galárraga, Christina Teflioudi, Katja Hose, Fabian M. Suchanek: “AMIE: Association rule mining under incomplete evidence” Full paper at the International World Wide Web Conference  (WWW) , 2013 N. Lavrač, S. Džeroski: Inductive Logic Programming — techniques and applications References F. Suchanek, J. Lajus, A. Boschin, G. Weikum: “Knowledge Representation and Rule Mining in Entity-Centric KBs” Invited paper at the Reasoning Web Summer School  (RW) , 2019 37 Armand Boschin, Nitisha Jain, Gurami Keretchashvili, Fabian M. Suchanek: “Combining Embeddings and Rules for Fact Prediction” Summer School on Artificial Intelligence in Bergen  (AIB)  2022