NLP: Score an entity recognizer

Score a named-entity recognizer the way the CoNLL benchmark does.

What to build

A program that compares predicted BIO tags with gold tags and prints entity-level precision, recall and F1.

Requirements

  • Read spans with the BIO rules of the easy exercise: B- starts an entity, I- continues the current entity of the same type or else starts a new one, O ends it. A span is its type, first position and last position.
  • A predicted span is correct only if the same span (type, start and end) is in the gold spans of that sentence.
  • For each type that appears in gold or predicted spans, in alphabetical order, print TYPE precision P recall R f1 F; then overall precision P recall R f1 F from the summed counts. Use 0 for any division by zero; three decimal places.

Input

Line 1: n. Then, for each sentence, a line of gold tags and a line of predicted tags.

Output

One line per type, then the overall line.

Constraints

n ≤ 1,000; sentences have at most 200 tags.

Example

Input:

2
B-PER I-PER O B-LOC
B-PER O O B-LOC
B-ORG I-ORG O O
B-ORG I-ORG O B-LOC

Output:

LOC precision 0.500 recall 1.000 f1 0.667
ORG precision 1.000 recall 1.000 f1 1.000
PER precision 0.000 recall 0.000 f1 0.000
overall precision 0.500 recall 0.667 f1 0.571

Why it works

Comparing whole spans means a recognizer gets credit only for entities it found exactly, and summing counts over types (micro averaging) weights each entity equally.

Examples

Example 1 · Input
2
B-PER I-PER O B-LOC
B-PER O O B-LOC
B-ORG I-ORG O O
B-ORG I-ORG O B-LOC
Expected output
LOC precision 0.500 recall 1.000 f1 0.667
ORG precision 1.000 recall 1.000 f1 1.000
PER precision 0.000 recall 0.000 f1 0.000
overall precision 0.500 recall 0.667 f1 0.571
Example 2 · Input
1
B-LOC I-LOC O
B-LOC I-LOC O
Expected output
LOC precision 1.000 recall 1.000 f1 1.000
overall precision 1.000 recall 1.000 f1 1.000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Turn each tag line into a list of `(type, start, end)` spans with the BIO rules of the easy exercise, then compare the lists.

Hint 2

Keep three counts per type: correct predictions, predicted entities and gold entities; the overall line uses their sums.

Solution

Show one correct solution (try it yourself first)
def spans(tags):
    out, current = [], None
    for i, t in enumerate(tags):
        if t == "O":
            current = None
            continue
        kind, label = t.split("-", 1)
        if kind == "I" and current and current[0] == label:
            current[2] = i
        else:
            current = [label, i, i]
            out.append(current)
    return [tuple(s) for s in out]


def report(tp, predicted, gold):
    p = tp / predicted if predicted else 0.0
    r = tp / gold if gold else 0.0
    f = 2 * p * r / (p + r) if p + r else 0.0
    return f"precision {p:.3f} recall {r:.3f} f1 {f:.3f}"


stats = {}
for _ in range(int(input())):
    gold = spans(input().split())
    predicted = spans(input().split())
    for s in gold:
        stats.setdefault(s[0], [0, 0, 0])[2] += 1
    for s in predicted:
        counts = stats.setdefault(s[0], [0, 0, 0])
        counts[1] += 1
        if s in gold:
            counts[0] += 1
totals = [0, 0, 0]
for label in sorted(stats):
    print(label, report(*stats[label]))
    totals = [a + b for a, b in zip(totals, stats[label])]
print("overall", report(*totals))

Lesson: Named entities and chunking →