CC-BY
Fabian M. Suchanek
Fact Extraction by Reasoning
60
>path
Semantic IE
You
are
here
2
Knowledge representation
Entity Recognition
Entity Disambiguation
singer
Fact Extraction
KB
construction
Entity Typing
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
7
“Hermione is married to Ron”
“Ron”
?
?
Fact extraction 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?)
killed
?
spouse
?
Let’s solve all three
problems together!
+ ?
Idea: Solve all problems together
ｈａｓＳｐｏｕｓｅ（Ｈｅｒｍｉｏｎｅ，ＲｏｎＷｅａｓｌｅｙ）
8
“Hermione is married to Ron”
“Ron”
Magic
happens
here
How to holistically reason on Fact Extraction
9
There are several ways to model a fact extraction 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!
->Weighted-max-sat
Magic
happens
here
Back to our problem
Ａ ∧ Ｂ ⇒ Ｃ
transform
everything
to logical
formulas
ｈａｓＳｐｏｕｓｅ（Ｈｅｒｍｉｏｎｅ，ＲｏｎＷｅａｓｌｅｙ）
Find best conclusion
10
“Hermione is married to Ron”
“Ron”
Consistency
Consistency constraints can be expressed by rules:
Rules and weights can be designed manually. Such rules will guide our
information extraction process.
ｈａｓＳｐｏｕｓｅ（Ｘ，Ｙ）∧ｄｉｆｆｅｒｅｎｔ（Ｙ，Ｚ）⇒ ¬ ｈａｓＳｐｏｕｓｅ（Ｘ，Ｚ） ［１０］
ｈａｓＳｐｏｕｓｅ（Ｘ，Ｙ） ⇒ ｔｙｐｅ（Ｘ，ｐｅｒｓｏｎ） ［２０］
ｌｏｖｅｓ（Ｘ，Ｙ）∧ ¬ ｈａｓＳｐｏｕｓｅ（Ｘ，Ｙ） ⇒ ｔｙｐｅ（Ｘ，ｓｔｕｐｉｄＰｅｒｓｏｎ） ［３］
11
...
A KB can be expressed as rules
Every fact from the KB can be expressed as a weighted rule:
ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ，Ｐｅｒｓｏｎ） ［１００］
⇒ ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ，Ｐｅｒｓｏｎ） ［１００］
12
High weight
This is corresponds to the rule
Assuming completeness
If we assume the KB to be complete on a relation, we can create negative rules:
¬ ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ，ｃｈｉｃｋｅｎ） ［１００］
¬ ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ，ｃａｔ） ［１００］
¬ ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ，ｍｏｕｓｅ） ［１００］
¬ ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ，Ｘ） ［１００］
For all Ｘ where ｔｙｐｅ（Ｈｅｒｍｉｏｎｅ，Ｘ） ∕∈ ＫＢ , add
13
...
i.e.
Expressing the corpus as rules
14
Hermione married Ron.
D42:
ｏｃｃｕｒｓ (“Hermione”, “married”, “Ron”)
Expressing the corpus as rules
ｏｃｃｕｒｓ (“Hermione”, “married”, “Ron”)
15
Hermione married Ron.
D42:
ｍｅａｎｓ (“Ron”, ＲｏｎａｌｄＲｅａｇａｎ )
ｍｅａｎｓ (“Ron”, ＲｏｎＷｅａｓｌｅｙ )
The word “Ron” can mean different entities (from the KB):
But only one entity in practice:
ｍｅａｎｓ（Ｘ，Ｙ） ∧ ｄｉｆｆｅｒｅｎｔ（Ｙ，Ｚ） ⇒ ¬ ｍｅａｎｓ（Ｘ，Ｚ）
Weights for corpus rules
16
ｏｃｃｕｒｓ (“Hermione”, “married”, “Ron”)[3]
ｍｅａｎｓ (“Ron”, ＲｏｎａｌｄＲｅａｇａｎ )[5]
ｍｅａｎｓ (“Ron”, ＲｏｎＷｅａｓｌｅｙ )[10]
ｍｅａｎｓ（Ｘ，Ｙ） ∧ ｄｉｆｆｅｒｅｎｔ（Ｙ，Ｚ） ⇒ ¬ ｍｅａｎｓ（Ｘ，Ｚ） [100]
# occurrences
From disambiguation
by context/prior
“Hard” rule with very high weight
Let us ignore the weights for a moment.
Deducing patterns
17
hasSpouse
KB
Ron married Nacy.
+
Deducing patterns
18
hasSpouse
KB
Ron married Nacy.
“X married Y”
is pattern for
ｈａｓＳｐｏｕｓｅ (X,Y)
+
=
Deducing patterns
“X married Y”
is pattern for
ｈａｓＳｐｏｕｓｅ (X,Y)
19
hasSpouse
KB
Ron married Nacy.
+
=
ｈａｓＳｐｏｕｓｅ（ＲｏｎａｌｄＲｅａｇａｎ，ＮａｎｃｙＤａｖｉｓ）
Deducing patterns
“X married Y”
is pattern for
ｈａｓＳｐｏｕｓｅ (X,Y)
20
hasSpouse
KB
Ron married Nacy.
ｏｃｃｕｒｓ (“Ron”,“married”, “Nancy”)
ｍｅａｎｓ (“Ron”, ＲｏｎａｌｄＲｅａｇａｎ )
ｍｅａｎｓ (“Nancy”, ＮａｎｃｙＤａｖｉｓ )
+
=
ｈａｓＳｐｏｕｓｅ（ＲｏｎａｌｄＲｅａｇａｎ，ＮａｎｃｙＤａｖｉｓ）
Deducing patterns
“X married Y”
is pattern for
ｈａｓＳｐｏｕｓｅ (X,Y)
21
hasSpouse
KB
Ron married Nacy.
ｏｃｃｕｒｓ (“Ron”,“married”, “Nancy”)
ｍｅａｎｓ (“Ron”, ＲｏｎａｌｄＲｅａｇａｎ )
ｍｅａｎｓ (“Nancy”, ＮａｎｃｙＤａｖｉｓ )
+
=
ｏｃｃｕｒｓ（Ｘ，Ｐ，Ｙ）
∧ ｍｅａｎｓ（Ｘ，Ｘ＇）
∧ ｍｅａｎｓ（Ｙ，Ｙ＇）
⇒ ｉｓＰａｔｔｅｒｎＦｏｒ（Ｐ，Ｒ）
∧ Ｒ（Ｘ＇，Ｙ＇）
ｈａｓＳｐｏｕｓｅ（ＲｏｎａｌｄＲｅａｇａｎ，ＮａｎｃｙＤａｖｉｓ）
Deducing patterns
“X married Y”
is pattern for
ｈａｓＳｐｏｕｓｅ (X,Y)
ｏｃｃｕｒｓ（Ｘ，Ｐ，Ｙ）
∧ ｍｅａｎｓ（Ｘ，Ｘ＇）
∧ ｍｅａｎｓ（Ｙ，Ｙ＇）
⇒ ｉｓＰａｔｔｅｒｎＦｏｒ（Ｐ，Ｒ）
∧ Ｒ（Ｘ＇，Ｙ＇）
22
hasSpouse
KB
Ron married Nacy.
ｏｃｃｕｒｓ (“Ron”,“married”, “Nancy”)
ｍｅａｎｓ (“Ron”, ＲｏｎａｌｄＲｅａｇａｎ )
ｍｅａｎｓ (“Nancy”, ＮａｎｃｙＤａｖｉｓ )
ｈａｓＳｐｏｕｓｅ（ＲｏｎａｌｄＲｅａｇａｎ，ＮａｎｃｙＤａｖｉｓ）
+
=
ｉｓＰａｔｔｅｒｎＦｏｒ（ “married”，ｈａｓＳｐｏｕｓｅ）
Applying patterns
“X married Y”
is pattern for
ｈａｓＳｐｏｕｓｅ (X,Y)
23
Elvis married Priscilla.
>task
+
Applying patterns
“X married Y”
is pattern for
ｈａｓＳｐｏｕｓｅ (X,Y)
24
Elvis married Priscilla.
>task
hasSpouse
+
=
Applying patterns
“X married Y”
is pattern for
ｈａｓＳｐｏｕｓｅ (X,Y)
25
hasSpouse
Elvis married Priscilla.
>task
ｏｃｃｕｒｓ（Ｘ，Ｐ，Ｙ）
∧ ｍｅａｎｓ（Ｘ，Ｘ＇）
∧ ｍｅａｎｓ（Ｙ，Ｙ＇）
ｉｓＰａｔｔｅｒｎＦｏｒ (“married”,ｈａｓＳｐｏｕｓｅ )
∧ ｉｓＰａｔｔｅｒｎＦｏｒ（Ｐ，Ｒ）
⇒ Ｒ（Ｘ＇，Ｙ＇）
ｏｃｃｕｒｓ (“Elvis”, “married”, “Priscilla”)
ｍｅａｎｓ (“Elvis”, ＥｌｖｉｓＰｒｅｓｌｅｙ )
ｍｅａｎｓ (“Priscilla”, ＰｒｉｓｃｉｌｌａＰｒｅｓｌｅｙ )
+
=
Applying patterns
“X married Y”
is pattern for
ｈａｓＳｐｏｕｓｅ (X,Y)
ｏｃｃｕｒｓ（Ｘ，Ｐ，Ｙ）
∧ ｍｅａｎｓ（Ｘ，Ｘ＇）
∧ ｍｅａｎｓ（Ｙ，Ｙ＇）
ｉｓＰａｔｔｅｒｎＦｏｒ (“married”,ｈａｓＳｐｏｕｓｅ )
∧ ｉｓＰａｔｔｅｒｎＦｏｒ（Ｐ，Ｒ）
⇒ Ｒ（Ｘ＇，Ｙ＇）
26
hasSpouse
Elvis married Priscilla.
ｏｃｃｕｒｓ (“Elvis”, “married”, “Priscilla”)
ｍｅａｎｓ (“Elvis”, ＥｌｖｉｓＰｒｅｓｌｅｙ )
ｍｅａｎｓ (“Priscilla”, ＰｒｉｓｃｉｌｌａＰｒｅｓｌｅｙ )
>task
ｈａｓＳｐｏｕｓｅ（ＥｌｖｉｓＰｒｅｓｌｅｙ，ＰｒｉｓｃｉｌｌａＰｒｅｓｌｅｙ）
+
=
ｏｃｃｕｒｓ（Ｘ，Ｐ，Ｙ）
∧ ｍｅａｎｓ（Ｘ，Ｘ＇）
∧ ｍｅａｎｓ（Ｙ，Ｙ＇）
∧ ｉｓＰａｔｔｅｒｎＦｏｒ（Ｐ，Ｒ）
⇒ Ｒ（Ｘ＇，Ｙ＇）
Task: Pattern deduction by rules
∧ Ｒ（Ｘ＇，Ｙ＇）
⇒ ｉｓＰａｔｔｅｒｎＦｏｒ（Ｐ，Ｒ）
∧ ｍｅａｎｓ（Ｘ，Ｘ＇）
∧ ｍｅａｎｓ（Ｙ，Ｙ＇）
ｏｃｃｕｒｓ（Ｘ，Ｐ，Ｙ）
２： ｍｅａｎｓ (“Elvis”,ＥｌｖｉｓＰｒｅｓｌｅｙ )
３： ｍｅａｎｓ (“Priscilla”, ＰｒｉｓｃｉｌｌａＰｒｅｓｌｅｙ )
４： ｈａｓＳｐｏｕｓｅ（ＰｒｉｓｃｉｌｌａＰｒｅｓｌｅｙ，ＥｌｖｉｓＰｒｅｓｌｅｙ）
１： ｏｃｃｕｒｓ (“Priscilla”, “adores”, “Elvis”)
５： ｏｃｃｕｒｓ (“Madonna”, “adores”, “Elvis”)
６： ｍｅａｎｓ (“Madonna”, Ｍａｄｏｎｎａ )
27
Pattern deduction:
Pattern application:
Compute facts that will be in the best world.
All rules have weight 1.
Life is not easy
• words are ambiguous
• corpora may err
• parsing may fail
• contradictions may occur
ｏｃｃｕｒｓ (“Priscilla”, “loves”, “Mike”)
28
“Ron”
“Madonna is married to Elvis”
“Elvis thinks that Priscilla loves Mike.”
Reagan was married twice.
=> we will compute the most plausible world
Finding the most plausible world
“Hermione married Ron”
“Ron”
spouse
29
World1:
spouse
World2:
spouse
Finding the most plausible world
“Hermione married Ron”
World1:
spouse
World2:
spouse
ｏｃｃｕｒｓ (“Hermione”, “married”,“Ron”)[1]
ｉｓＰａｔｔｅｒｎＦｏｒ (“married”, ｓｐｏｕｓｅ )[1]
ｍｅａｎｓ (“Hermione”, Ｈｅｒｍｉｏｎｅ )[5]
ｍｅａｎｓ (“Ron”, ＲｏｎＷｅａｓｌｅｙ )[2]
ｍｅａｎｓ (“Ron”, ＲｏｎａｌｄＲｅａｇａｎ )[3]
ｍｅａｎｓ（Ｘ， Ｙ） ∧ Ｙ ∕ ＝ Ｚ ⇒ ¬ ｍｅａｎｓ（Ｘ， Ｚ） [10]
ｓｐｏｕｓｅ（Ｘ， Ｙ） ∧ Ｙ∕ ＝ Ｚ ⇒ ¬ ｓｐｏｕｓｅ（Ｚ， Ｘ） [6]
+ Symmetry of marriage
+ Pattern Application Rule [10]
+ Facts from the KB [100]
30
“Ron”
spouse
Finding the most plausible world
“Hermione married Ron”
ｏｃｃｕｒｓ (“Hermione”, “married”,“Ron”)[1]
ｉｓＰａｔｔｅｒｎＦｏｒ (“married”, ｓｐｏｕｓｅ )[1]
ｍｅａｎｓ (“Hermione”, Ｈｅｒｍｉｏｎｅ )[5]
ｍｅａｎｓ (“Ron”, ＲｏｎＷｅａｓｌｅｙ )[2]
ｍｅａｎｓ (“Ron”, ＲｏｎａｌｄＲｅａｇａｎ )[3]
ｍｅａｎｓ（Ｘ， Ｙ） ∧ Ｙ ∕ ＝ Ｚ ⇒ ¬ ｍｅａｎｓ（Ｘ， Ｚ） [10]
ｓｐｏｕｓｅ（Ｘ， Ｙ） ∧ Ｙ∕ ＝ Ｚ ⇒ ¬ ｓｐｏｕｓｅ（Ｚ， Ｘ） [6]
+ Symmetry of marriage
+ Pattern Application Rule [10]
+ Facts from the KB [100]
loses 2
wins 3
loses 6
31
World1:
spouse
World2:
spouse
“Ron”
spouse
Finding the most plausible world
loses 2
wins 3
loses 6
“Hermione married Ron”
ｏｃｃｕｒｓ (“Hermione”, “married”,“Ron”)[1]
ｉｓＰａｔｔｅｒｎＦｏｒ (“married”, ｓｐｏｕｓｅ )[1]
ｍｅａｎｓ (“Hermione”, Ｈｅｒｍｉｏｎｅ )[5]
ｍｅａｎｓ (“Ron”, ＲｏｎＷｅａｓｌｅｙ )[2]
ｍｅａｎｓ (“Ron”, ＲｏｎａｌｄＲｅａｇａｎ )[3]
ｍｅａｎｓ（Ｘ， Ｙ） ∧ Ｙ ∕ ＝ Ｚ ⇒ ¬ ｍｅａｎｓ（Ｘ， Ｚ） [10]
ｓｐｏｕｓｅ（Ｘ， Ｙ） ∧ Ｙ∕ ＝ Ｚ ⇒ ¬ ｓｐｏｕｓｅ（Ｚ， Ｘ） [6]
+ Symmetry of marriage
+ Pattern Application Rule [10]
+ Facts from the KB [100]
loses 3
wins 6
wins 2
32
World1:
spouse
World2:
spouse
“Ron”
spouse
Summary: Fact extraction by reasoning
Fact extraction by reasoning converts
• background knowledge (existing KB)
• logical constraints
• the corpus
into logical rules and aims to find the most plausible possible world given these evidences.
33
stupid
happy
spouse
is
is
References
Suchanek et al: “
SOFIE - a self-organizing framework for IE
”, WWW 2009
Weikum et al: “
Machine Knowledge
” , 2021
34