Fabian M. Suchanek
Evaluation
53
Semantic IE
You
are
here
2
Source Selection and Preparation
Entity Recognition
Entity Disambiguation
singer
Fact Extraction
Reasoning
Instance Extraction
singer Elvis
Detect members of the Simpsons
in The Simpsons, Homer Simpson is the
father of Bart Simpson and Lisa Simpson.
The M above his ear is for Matt Groening.
3
1. [A-Z][a-z]+ Simpson
4
Detect members of the Simpsons
in The Simpsons, Homer Simpson is the
father of Bart Simpson and Lisa Simpson.
The M above his ear is for Matt Groening.
1. [A-Z][a-z]+ Simpson
5
Detect members of the Simpsons
in The Simpsons, Homer Simpson is the
father of Bart Simpson and Lisa Simpson.
The M above his ear is for Matt Groening.
4 matches (1 wrong)
1. [A-Z][a-z]+ Simpson
2. [A-Z][a-z]+ [A-Z][a-z]+
6
4 matches (1 wrong)
Detect members of the Simpsons
in The Simpsons, Homer Simpson is the
father of Bart Simpson and Lisa Simpson.
The M above his ear is for Matt Groening.
1. [A-Z][a-z]+ Simpson
2. [A-Z][a-z]+ [A-Z][a-z]+
7
4 matches (1 wrong)
Detect members of the Simpsons
in The Simpsons, Homer Simpson is the
father of Bart Simpson and Lisa Simpson.
The M above his ear is for Matt Groening.
5 matches (2 wrong)
1. [A-Z][a-z]+ Simpson
2. [A-Z][a-z]+ [A-Z][a-z]+
3. Homer Simpson
8
4 matches (1 wrong)
Detect members of the Simpsons
in The Simpsons, Homer Simpson is the
father of Bart Simpson and Lisa Simpson.
The M above his ear is for Matt Groening.
5 matches (2 wrong)
1 match
1. [A-Z][a-z]+ Simpson
2. [A-Z][a-z]+ [A-Z][a-z]+
3. Homer Simpson
9
4 matches (1 wrong)
Detect members of the Simpsons
in The Simpsons, Homer Simpson is the
father of Bart Simpson and Lisa Simpson.
The M above his ear is for Matt Groening.
5 matches (2 wrong)
Def: Gold Standard
The gold standard (also: ground truth) for an IE task is the set of
desired results of the task on a given corpus.
10
{Homer Simpson, Bart Simpson, Lisa Simpson}
in The Simpsons, Homer Simpson is the
father of Bart Simpson and Lisa Simpson.
The M above his ear is for Matt Groening.
Task: Detect Simpson members
Corpus:
Gold Standard:
Def: Precision
The
precision
of an IE algorithm is the ratio of its outputs
that are in the respective gold standard.
11
Output: {Homer, Bart, Groening}
G.Standard: {Homer, Bart, Lisa, Marge}
Def: Precision
12
Output: {Homer, Bart, Groening}
G.Standard: {Homer, Bart, Lisa, Marge}
The
precision
of an IE algorithm is the ratio of its outputs
that are in the respective gold standard.
Def: Precision
13
Output: {Homer, Bart, Groening}
G.Standard: {Homer, Bart, Lisa, Marge}
The
precision
of an IE algorithm is the ratio of its outputs
that are in the respective gold standard.
Def: Precision
14
Output: {Homer, Bart, Groening}
G.Standard: {Homer, Bart, Lisa, Marge}
The
precision
of an IE algorithm is the ratio of its outputs
that are in the respective gold standard.
Def: Precision
15
Output: {Homer, Bart, Groening}
G.Standard: {Homer, Bart, Lisa, Marge}
=> Precision: 2/3 = 66%
The
precision
of an IE algorithm is the ratio of its outputs
that are in the respective gold standard.
Def: Recall
The
recall
(also: sensitivity, true positive rate, hit rate) of an IE algorithm
is the ratio of the gold standard that is output.
16
Output: {Homer, Bart, Groening}
G.Standard: {Homer, Bart, Lisa, Marge}
Def: Recall
17
Output: {Homer, Bart, Groening}
G.Standard: {Homer, Bart, Lisa, Marge}
The
recall
(also: sensitivity, true positive rate, hit rate) of an IE algorithm
is the ratio of the gold standard that is output.
Def: Recall
18
Output: {Homer, Bart, Groening}
G.Standard: {Homer, Bart, Lisa, Marge}
The
recall
(also: sensitivity, true positive rate, hit rate) of an IE algorithm
is the ratio of the gold standard that is output.
Def: Recall
19
Output: {Homer, Bart, Groening}
G.Standard: {Homer, Bart, Lisa, Marge}
The
recall
(also: sensitivity, true positive rate, hit rate) of an IE algorithm
is the ratio of the gold standard that is output.
Def: Recall
20
Output: {Homer, Bart, Groening}
G.Standard: {Homer, Bart, Lisa, Marge}
The
recall
(also: sensitivity, true positive rate, hit rate) of an IE algorithm
is the ratio of the gold standard that is output.
Def: Recall
Output: {Homer, Bart, Groening}
G.Standard: {Homer, Bart, Lisa, Marge}
=> Recall: 2/4 = 50%
21
The
recall
(also: sensitivity, true positive rate, hit rate) of an IE algorithm
is the ratio of the gold standard that is output.
>F1
Precision-Recall-Tradeoff
It is very hard to get both good precision and good recall.
Algorithms usually allowing varying one at the expense of the other
(e.g., by choosing different threshold values). This usually yields:
22
Precision
Recall
Very good results,
but too few of them
All good results, but
many wrong ones, too
What we
want
Def: F1
23
Gold Standard: {Homer, Bart, Lisa, Snowball_4, ..., Snowball_100}
Output: {Homer Simpson}
To trade off precision and recall, we could use the average:
Def: F1
24
Gold Standard: {Homer, Bart, Lisa, Snowball_4, ..., Snowball_100}
Output: {Homer Simpson}
To trade off precision and recall, we could use the average:
The
F1 measure
is the harmonic mean of precision and recall.
Precision: 1/1=100%, Recall: 1/100=1%
Average: (100%+1%)/2=50%
Outputting just
a single result
already gives a
score of 50%!
Precision: 1/1=100%, Recall: 1/100=1%
F1: 2
100%
1%/(100%+1%)=2%
Task: Precision & Recall
What is the algorithm output, the gold standard,
the precision and the recall in the following cases?
1. Nostradamus predicts a trip to the moon for every century
from the 15th to the 20th incl.
2. The weather forecast predicts that the next 3 days will
be sunny. It does not say anything about the 2 days
that follow. In reality, it is sunny during all 5 days.
3.On Elvis Radio™ , 90% of the songs are by Elvis. An algorithm learns
to detect Elvis songs. Out of 100 songs on Elvis Radio, the algorithm
says that 20 are by Elvis (and says nothing about the other 80). Out
of these 20 songs, 15 were by Elvis and 5 were not.
4. How can you improve the algorithm?
25
>ROC
Imbalanced classes
26
Population:
Gold Standard:
Output:
{Snowball_1,..., Snowball_99, Snowball_100}
{Snowball_1,..., Snowball_99}
{Snowball_1,..., Snowball_99, Snowball_100}
27
Population:
Gold Standard:
Output:
{Snowball_1,..., Snowball_99, Snowball_100}
{Snowball_1,..., Snowball_99}
{Snowball_1,..., Snowball_99, Snowball_100}
Precision: 99/100=99%
Recall: 99/99=100%
If there are very few negatives,
just outputting all elements
gives great scores.
The problem of
imbalanced classes
appears when only very few of the
items of the population are not in the gold standard: An approach
that outputs the entire population has a very high precison and a
perfect recall.
The
negatives
are the elements of the population that are
not in the gold standard.
Def: Problem of imbalanced classes
>confusion
28
Population:
Gold Standard:
Output:
{Snowball_1,..., Snowball_99, Snowball_100}
{Snowball_1,..., Snowball_99}
{Snowball_1,..., Snowball_99, Snowball_100}
The
confusion matrix
for the output of an algorithm looks as follows:
Def: Confusion Matrix
Gold standard
Output
Positive
Negative
Positive
Positive
Negative
Items of the
population that
are not output
Items of the population that
are not in the gold standard
True Positives
False Positives
False Negatives
True Negatives
“Negative” because it was
not output, “True” because
that was correct.
(Gold) Positives
(Gold) Negatives
Predicted Positives
Predicted Negatives
29
Population:
Gold Standard:
Output:
{Snowball_1,..., Snowball_99, Snowball_100}
{Snowball_1,..., Snowball_99}
{Snowball_1,..., Snowball_99, Snowball_100}
The
confusion matrix
for the output of an algorithm looks as follows:
Def: Confusion Matrix
Gold standard
Output
Positive
Negative
Positive
Positive
Negative
99
0
1
0
1 item was output as positive,
but was negative in the
gold standard
100
0
99
1
Precision = true positives / predicted positives
= 99/100 = 99%
Recall = true positives / gold positives
= 99/99 = 100%
30
Population:
Gold Standard:
Output:
{H, Ho, Hom, ..., o, om, ome, ..., r Sim, r Simps, ...}
{Homer}
{Homer}
A confusion matrix does not always make sense in an information
extraction scenario:
Confusion with confusion matrixes
Gold standard
Positive
Negative
Positive
99
0
39462440205
0
A confusion matrix makes sense only when the population is limited
(e.g., in classification tasks)!
39462440206
Positive
Negative
Output
31
Our problem
The problem is that the algorithm did not catch the negatives,
it has a “low recall” on the negatives.
Population:
Gold Standard:
Output:
{Snowball_1,..., Snowball_99, Snowball_100}
{Snowball_1,..., Snowball_99}
{Snowball_1,..., Snowball_99, Snowball_100}
Gold standard
Positive
Negative
Positive
99
0
1
0
Positive
Negative
Output
32
Def: True Negative Rate & FPR
Population:
Gold Standard:
Output:
{Snowball_1,..., Snowball_99, Snowball_100}
{Snowball_1,..., Snowball_99}
{Snowball_1,..., Snowball_99, Snowball_100}
Positive
Negative
Positive
99
0
1
0
Positive
Negative
Output
The
true negative rate
(also: TNR, specificity, selectivity) is the ratio of
negatives that are output as negatives (= the recall on the negatives):
TNR = true negatives / gold negatives
= 0 / 1 = 0%
The
False Positive Rate
(also: FPR, fall-out) is 1-TNR.
>ROC
>details
TNR & Precision
33
Population:
Gold Standard:
Output:
{Snowball_1,..., Snowball_99, Snowball_100}
{Snowball_1,..., Snowball_99}
{Snowball_1,..., Snowball_99, Snowball_100}
Precision: 99/100=99%
Recall: 99/99=100%
TNR: 0/1=0%
TNR and precision both measure the “correctness” of the output.
Precision:
• measures wrt. the output
• suffers from imbalanced classes
• works if population is infinite
(e.g., set of all extractable entities)
TNR:
• measures wrt. the population
• guards against imbalance
• works if population is limited
(e.g., in classification)
>details
>ROC
Informedness
34
The
informedness
(also: Youden’s J statistic, Youden’s index) combines
TNR and Recall as follows:
informedness = recall + TNR - 1 = recall - FPR
= 100% + 0% - 1 = 0
(It’s kind of the F1 measure in the case of a limited population.)
Population:
Gold Standard:
Output:
Precision: 99/100=99%
Recall: 99/99=100%
TNR: 0/1=0%
{Snowball_1,..., Snowball_99, Snowball_100}
{Snowball_1,..., Snowball_99}
{Snowball_1,..., Snowball_99, Snowball_100}
>details
>ROC
Def: ROC
35
Recall
False Positive Rate (FPR)
No bad results,
but also no good ones
Many good results,
but also many bad ones.
What we
want
The
ROC
(receiver operating characteristic) curve plots recall against
the FPR for different thresholds of the algorithm. It guards against
imbalanced classes, and is applicable when the population is finite.
>details
Def: ROC
36
Recall
False Positive Rate (FPR)
What we
want
The
ROC
(receiver operating characteristic) curve plots recall against
the FPR for different thresholds of the algorithm. It guards against
imbalanced classes, and is applicable when the population is finite.
If an algorithm has no threshold to
tune, we can always simulate a curve...
...by randomy adding items
from the population to the output
...and randomly removing items
from the output
>details
Def: ROC
37
Recall
True Negative Rate (TNR)
What we
want
What an algorithm
would get if it
randomly chooses
the positive items
from the population.
Informedness
The
ROC
(receiver operating characteristic) curve plots recall against
the FPR for different thresholds of the algorithm. It guards against
imbalanced classes, and is applicable when the population is finite.
Def: AUC
38
Recall
False Positive Rate (FPR)
What we
want
The
AUC
(area under curve) is the area under the ROC curve.
It corresponds to the probability that the classifier ranks a random
positive item over a random negative item. (It’s kind of the F1 for a
limited population and a varying threshold.)
How not to design an IE algorithm
39
Task: Find Simpson pets
Corpus:
Algorithm:
Regex "Snowball I*"
How not to design an IE algorithm
40
Task: Find Simpson pets
Corpus:
Algorithm:
Regex "Snowball I*"
{Snowball I, Snowball II}
Output:
How not to design an IE algorithm
41
Task: Find Simpson pets
Corpus:
Algorithm:
Regex: "Snowball (I|V)*"
How not to design an IE algorithm
42
Task: Find Simpson pets
Corpus:
Algorithm:
Regex: "Snowball (I|V)*"
{Snowball I,Snowball II,Snowball IV}
Output:
How not to design an IE algorithm
43
Task: Find Simpson pets
Corpus:
Algorithm:
Regex: "Snowball (I|V)*"
{Snowball I,Snowball II,Snowball IV}
Output:
Is this algorithm good?
How to design an IE algorithm
Take only a sample
of the corpus
Lisa decides to play music on her saxophone for Coltrane,
but the noise frightens him and he commits suicide.
As Gil swerves to avoid hitting Snowball V, his car
hits a tree and bursts into flames. Since the cat is unhurt,
Lisa takes it as a sign of good luck and adopts her. [...]
44
Task: Find Simpson pets
Corpus:
How to design an IE algorithm
45
Task: Find Simpson pets
Corpus:
Consider only
the sample corpus.
How to design an IE algorithm
46
Task: Find Simpson pets
Corpus:
Consider only
the sample corpus.
Manually make
a gold standard
{Coltrane, Snowball I, ...}
Gold Standard:
How to design an IE algorithm
47
Task: Find Simpson pets
Corpus:
{Coltrane, Snowball I, ...}
Gold Standard:
Algorithm
How to design an IE algorithm
48
Task: Find Simpson pets
Corpus:
{Coltrane, Snowball I, ...}
Gold Standard:
Algorithm
Output:
{...}
How to design an IE algorithm
49
Task: Find Simpson pets
Corpus:
{Coltrane, Snowball I, ...}
Gold Standard:
Output:
{...}
Algorithm
Evaluator
How to design an IE algorithm
50
Task: Find Simpson pets
Corpus:
{Coltrane, Snowball I, ...}
Gold Standard:
Output:
{...}
Algorithm
Evaluator
Precision/Recall
How to design an IE algorithm
51
Task: Find Simpson pets
Corpus:
{Coltrane, Snowball I, ...}
Gold Standard:
Output:
{...}
Algorithm
Evaluator
Precision/Recall
improve
->end
Evaluation on a Sample
52
Corpus:
1: ...A...B...
2: ...C....
3: ..D.....E...
4: .....H.....
5: ..I...J...K...
3: ..D.....E...
4: .....H.....
Sample:
{D, E, H}
Gold Standard:
Algorithm:
{1: A, Z
2: C
3: D, E, K
4: L,
5: I, K, X}
Sample:
{
3: D, E, K
4: L
}
Precision: 2/4
Recall: 2/3
A, B, etc. can be entities, but also facts
Evaluation on a Sample
53
Corpus:
1: ...A...B...
2: ...C....
3: ..D.....E...
4: .....H.....
5: ..I...J...K...
3: ..D.....E...
4: .....H.....
Sample:
{D, E, H}
Gold Standard:
Algorithm:
{1: A, Z
2: C
3: D, E, K
4: L,
5: I, K, X}
Sample:
{
3: D, E, K
4: L
}
Precision: 2/4
Recall: 2/3
Document 5 not considered
for computing recall!
->end
Simple case: 1 target per document
54
Corpus:
A: ...A’...
B: ...B’...
C: ...C’...
D: ...D’...
E: ...E’...
C: ...C’...
D: ...D’...
E: ...E’...
Sample:
{C:C’, D:D’, E:E’}
Algorithm:
{A: A’
B: X
C: Z
D: D’
}
Precision: 1/ 2
Recall: 1/3
Gold Standard
on sample:
Sample output:
{
C: Z,
D: D’
}
55
Corpus:
A: ...A’...
B: ...B’...
C: ...C’...
D: ...D’...
E: ...E’...
C: ...C’...
D: ...D’...
E: ...E’...
Sample:
{C:C’, D:D’, E:E’}
Gold Standard
on sample:
Algorithm:
{A: A’
B: X
C: Z
D: D’
E: K
}
Sample output:
{
C: Z,
D: D’,
E: K
}
Precision: 1/3
Recall: 1/3
If the algorithm produces
one output per input, prec=rec.
Simple case: 1 target per document
Semantic IE
You
are
here
56
Source Selection and Preparation
Entity Recognition
Entity Disambiguation
singer
Fact Extraction
Reasoning
Instance Extraction
singer Elvis
->disambiguation
->instance‐extraction
->NERC