Fabian M. Suchanek Information Extraction by Reasoning 67
Semantic IE You are here 2 Source Selection and Preparation Entity Recognition Entity Disambiguation singer Fact Extraction                  KB construction Instance Extraction singer Elvis
Problems in extending a KB 3 “Hermione is married to Ron”
Problems in extending a KB 4 “Hermione is married to Ron” +  ? “Ron”
Problems in extending a KB 5 “Hermione is married to Ron” +  ? “Ron” ? ?
Problems in extending a KB 6 “Hermione is married to Ron” +  ? “Ron” ? ? killed  ? spouse  ?
Problems in extending a KB killed  ? spouse  ? 7 “Hermione is married to Ron” +  ? “Ron” ? ? IE faces at least 3 problems: • Understand patterns • Disambiguate entities • Resolve inconsistencies (“X is married to Y” = killed(X,Y)?) (“Ron”= Ronald Reagan?) (Reagan married to 2 women?)
Problems in extending a KB killed  ? spouse  ? 8 “Hermione is married to Ron” +  ? “Ron” ? ? • Disambiguation avoids inconsistency • Pattern helps disambiguation • Consistency  helps finding pattern => Solve all 3 problems together!
Idea: Solve all problems together 9 “Hermione is married to Ron” “Ron” Magic happens here
How to holistically reason on IE 10 Implications>13 Magic happens here There are several ways to model an information extraction (IE) problem under constraints (disambiguation, logical coherence, etc.): •   as a maximum satisfiability (MaxSat) problem •   as an integer logic programming problem •   as a constraint satisfaction problem •   as a Markov Logic problem Most of these are relaxations or generalizations of the MaxSat problem -> we’ll look into this one!
11 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
12 likes envies likes 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.   ?   ?
13 likes envies likes Refresh: Implications 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. An implication    holds  in a KB if   does not hold or   holds.
14 likes envies likes 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