Sequence Labeling

Over three lessons a note was reduced to a single line, and the decision given was every time about the whole document. Which token names what inside the note was never asked. In the note sayacin kapagi kirik (the meter’s cover is broken) the first two tokens name a piece of hardware and the third reports its state; yet in the note boruda kelepce eksik (the clamp is missing on the pipe) the first two tokens are two separate pieces of hardware. This lesson distributes the label to the tokens.

When the label moves, the metric changes too: at the token level accuracy counts every token separately, while at the entity level an entity is counted only when it holds its start, its end and its type together. The domain baseline here is writing the most frequent label to every token, and at the token level it comes out surprisingly high.

• NL25. Tokenization is the decision of nlp/03: dropping punctuation, lowercasing, number folding. Stemming is not applied, because part of the boundary decision is read from the suffix.
• NL26. The entity types are fiction and are derived from the fiction’s own dictionary: hardware has seven roots, location nine roots, measurement two roots plus the number token. The other tokens are outside any entity.
• NL27. The boundary rule: if a noun in the base or genitive case is followed by a noun in the possessive case, the two are a single entity; a number token attaches to the preceding measurement token. In all other cases every token is its own entity.
• NL28. The part-of-speech label is also read from the dictionary: noun, adjective, verb, stop word, number.
• NL29. The domain baseline is writing the most frequent label to every token, in both tasks.
• NL30. The model is a memorization table: for every key the most frequent label in the training set. Two keys are tried — the token itself and its last three characters.
• NL31. There are two labeling schemes: type only, and type with a begin/inside distinction (B/I). Token-level accuracy is counted in both over the type, so that the two schemes are compared with the same metric.
• NL32. The entity-level metric is exact match. The definitions of precision, recall and F1 were built in the Supervised Learning course and are not repeated; the only thing added here is what is counted.

Entities and the Two Labeling Schemes

The notes are generated from the same seed as the setup of nlp/01.

# COMMON — FICTIONAL. The field notes are generated within the lesson, seed 20260218;
# they do not come from a source system. The vocabulary has 45 inflected roots and
# 40 rare nouns.
SEED, NOTE_COUNT, M32 = 20260218, 1800, 0xFFFFFFFF

NOUNS = {  # 0 base, 1 genitive, 2 locative, 3 possessive, 4 plural
    "sayac": "sayac sayacin sayacta sayaci sayaclar",
    "kapak": "kapak kapagin kapakta kapagi kapaklar",
    "muhur": "muhur muhurun muhurde muhuru muhurler",
    "vana": "vana vananin vanada vanasi vanalar",
    "kelepce": "kelepce kelepcenin kelepcede kelepcesi kelepceler",
    "boru": "boru borunun boruda borusu borular",
    "pano": "pano panonun panoda panosu panolar",
    "kapi": "kapi kapinin kapida kapisi kapilar",
    "zil": "zil zilin zilde zili ziller",
    "bahce": "bahce bahcenin bahcede bahcesi bahceler",
    "apartman": "apartman apartmanin apartmanda apartmani apartmanlar",
    "bodrum": "bodrum bodrumun bodrumda bodrumu bodrumlar",
    "giris": "giris girisin giriste girisi girisler",
    "adres": "adres adresin adreste adresi adresler",
    "okuma": "okuma okumanin okumada okumasi okumalar",
    "olcum": "olcum olcumun olcumde olcumu olcumler",
    "erisim": "erisim erisimin erisimde erisimi erisimler",
    "ziyaret": "ziyaret ziyaretin ziyarette ziyareti ziyaretler",
    "abone": "abone abonenin abonede abonesi aboneler",
    "arac": "arac aracin aracta araci araclar",
    "kir": "kir kirin kirde kiri kirler",
    "iz": "iz izin izde izi izler",
    "sokak": "sokak sokagin sokakta sokagi sokaklar",
    "ev": "ev evin evde evi evler",
}
ADJECTIVES = "kirik gevsek kirli normal bozuk acik kapali eksik temiz yeni yok".split()
VERBS = {  # 0 passive past, 1 negative
    "calis": "calisiyor calismiyor", "don": "donuyor donmuyor", "oku": "okundu okunmadi",
    "ac": "acildi acilmadi", "gir": "girildi girilemedi", "ulas": "ulasildi ulasilamadi",
    "tekrarla": "tekrarlandi tekrarlanmadi", "bul": "bulundu bulunmadi",
    "sagla": "saglandi saglanamadi", "degil": "degil degildi",
}
RARE_NOUNS = """kablo kablosu kabloda|cam cami camda|tel teli telde|mandal mandali mandalda
merdiven merdiveni merdivende|tahta tahtasi tahtada|cukur cukuru cukurda|kar kari karda
buz buzu buzda|cop copu copta|duvar duvari duvarda|kutu kutusu kutuda|vida vidasi vidada
conta contasi contada|filtre filtresi filtrede|bant banti bantta|etiket etiketi etikette
kilit kiliti kilitte|asansor asansoru asansorde|zemin zemini zeminde|tavan tavani tavanda
kuyu kuyusu kuyuda|depo deposu depoda|ocak ocagi ocakta|direk diregi direkte
kanal kanali kanalda|numara numarasi numarada|cati catisi catida|baca bacasi bacada
kova kovasi kovada|levha levhasi levhada|somun somunu somunda|tapa tapasi tapada
izolasyon izolasyonu izolasyonda|supap supabi supapta|menfez menfezi menfezde
kayit kaydi kayitta|temel temeli temelde|kose kosesi kosede|koruma korumasi korumada"""
PHRASES = {
    "ordinary": ["{sayac.0} {calis.0}", "{okuma.0} normal", "{olcum.0} {tekrarla.0}",
               "{sayac.1} {erisim.3} {sagla.0}", "{kapak.0} temiz", "{vana.0} acik",
               "{sayac.2} {iz.0} {bul.1}", "{olcum.0} icin {erisim.0} {sagla.0}",
               "{sayac.1} {kapak.3} yeni", "{muhur.0} ile {kapak.0} temiz"],
    "fault": ["{sayac.0} {don.1}", "{kapak.0} kirik", "{pano.0} bozuk",
              "{sayac.1} {kapak.3} kirik", "{olcum.0} {oku.1}", "{vana.0} bozuk",
              "{sayac.2} {kir.0} {bul.0}", "{sayac.4} {calis.1}",
              "{sayac.0} {calis.0} ama {okuma.0} yok",
              "{pano.1} {kapak.3} eksik"],
    "unreachable": ["{kapi.0} {ac.1}", "{zil.0} {calis.1}", "{abone.0} {ev.2} {degil.1}",
                    "{erisim.0} {sagla.1}", "{bodrum.0} {kapi.3} kapali",
                    "{apartman.1} {giris.3} kapali", "{adres.2} {ulas.1}",
                    "{bahce.1} {kapi.3} kapali", "{apartman.2} {zil.0} {calis.1}",
                    "{sayac.2} {erisim.0} yok"],
    "illicit": ["{muhur.0} kirik", "{kelepce.0} gevsek", "{muhur.2} {iz.0} {bul.0}",
              "{sayac.1} {muhur.3} kirik", "{kelepce.2} {iz.0} {bul.0}",
              "{muhur.0} eksik", "{vana.1} {kelepce.3} gevsek",
              "{muhur.1} {iz.3} {bul.0}", "{boru.2} {kelepce.0} eksik",
              "{kapak.2} bir {iz.0} {bul.0}"],
}
EXTRA_PHRASES = ["{ziyaret.0} {tekrarla.0}", "{sokak.2} {arac.0} {bul.0}", "{adres.0} yeni",
           "{bahce.1} {kapi.3} acik", "{apartman.2} {gir.0}", "{ev.1} {kapi.3} acik",
           "{kapak.0} kirli", "{olcum.0} {tekrarla.1}", "{arac.0} {sokak.2}",
           "bu {ziyaret.2} {olcum.0} {tekrarla.0}"]
KINDS = [("ordinary", 0.36, 0.04), ("fault", 0.26, 0.28),
         ("unreachable", 0.16, 0.15), ("illicit", 0.22, 0.82)]
FORMS = {k: v.split() for d in (NOUNS, VERBS) for k, v in d.items()}
RARE = [s.split() for s in RARE_NOUNS.replace("\n", "|").split("|")]
WEIGHTS = [1 / (i + 1) ** 1.6 for i in range(len(RARE))]
WEIGHTS = [w / sum(WEIGHTS) for w in WEIGHTS]
ROOT = {f: k for k, fs in FORMS.items() for f in fs}
ROOT.update({f: fs[0] for fs in RARE for f in fs})
ROOT.update({w: w for w in ADJECTIVES})
STOP_WORDS = ["ve", "ile", "bir", "bu", "ama", "icin"]
ROOT.update({w: w for w in STOP_WORDS})


def rng(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def next_value():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return next_value


def pick(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


def render_phrase(template):
    parts = []
    for part in template.split():
        if part.startswith("{"):
            name, _, i = part[1:-1].partition(".")
            parts.append(FORMS[name][int(i)])
        else:
            parts.append(part)
    return " ".join(parts)


DATA = []
for i in range(NOTE_COUNT):
    r = rng(SEED + i)
    kind = KINDS[pick(r(), [x[1] for x in KINDS])]
    clauses = [render_phrase(PHRASES[kind[0]][int(r() * 10)])]
    if r() < 0.55:
        clauses.append(render_phrase(EXTRA_PHRASES[int(r() * 10)]))
    if r() < 0.30:
        clauses.append(render_phrase(PHRASES[kind[0]][int(r() * 10)]))
    if r() < 0.22:
        forms, adjective = RARE[pick(r(), WEIGHTS)], ADJECTIVES[int(r() * len(ADJECTIVES))]
        clauses.append(forms[2] + " kir bulundu" if r() < 0.34
                       else forms[int(r() * 2)] + " " + adjective)
    note = clauses[0]
    for x in clauses[1:]:
        note += (" ve " if r() < 0.22 else ", ") + x
    if r() < 0.52:
        note += ", okuma " + str(240 + int(r() * 1760))
    DATA.append({"id": 10001 + i, "note": note[0].upper() + note[1:] + ".",
                 "kind": kind[0], "suspicious": int(r() < kind[2])})

TRAIN, HELD_OUT = DATA[:1200], DATA[1200:]

print(f"{len(DATA)} fictional notes, {len(FORMS) + len(RARE) + len(ADJECTIVES)} roots, "
      f"suspicion rate {sum(x['suspicious'] for x in DATA) / len(DATA):.4f}")
print(DATA[3]["note"])

1800 fictional notes, 85 roots, suspicion rate 0.2956
Olcum icin erisim saglandi, sayacin kapagi yeni, mandalda kir bulundu.

Entities and token labels are derived from the fiction’s dictionary, with the same boundary rule in both schemes. The prediction procedure is the same in both: the most frequent label per key.

from collections import Counter

ENTITY_TYPES = {"hardware": "sayac kapak muhur vana kelepce boru pano",
                "location": "kapi zil bahce apartman bodrum giris adres ev sokak",
                "measurement": "okuma olcum"}
ROOT_TYPE = {k: t for t, v in ENTITY_TYPES.items() for k in v.split()}
CASE = {f: i for v in NOUNS.values() for i, f in enumerate(v.split())}
POS_TAG = {f: "noun" for v in list(NOUNS.values()) + [" ".join(s) for s in RARE]
           for f in v.split()}
POS_TAG.update({f: "adjective" for f in ADJECTIVES})
POS_TAG.update({f: "verb" for v in VERBS.values() for f in v.split()})
POS_TAG.update({f: "stop word" for f in STOP_WORDS}, **{"<number>": "number"})

for x in DATA:
    x["tokens"] = [("<number>" if t.isdigit() else t)
                   for t in (s.strip(",.").lower() for s in x["note"].split()) if t]


def entity_type(t):
    return "measurement" if t == "<number>" else ROOT_TYPE.get(ROOT.get(t))


def attaches(a, b):  # genitive or base + possessive is a single entity; a number attaches to the reading
    return b == "<number>" or (CASE.get(a) in (0, 1) and CASE.get(b) == 3)


def entities(tokens):
    found, i = [], 0
    while i < len(tokens):
        if entity_type(tokens[i]) is None:
            i += 1
            continue
        j = i + 1
        while j < len(tokens) and entity_type(tokens[j]) and attaches(tokens[j - 1], tokens[j]):
            j += 1
        found.append((i, j, entity_type(tokens[j - 1])))
        i = j
    return found


def label(tokens, begin_inside):
    out = ["outside"] * len(tokens)
    for i, j, kind in entities(tokens):
        for k in range(i, j):
            out[k] = (("B-" if k == i else "I-") + kind) if begin_inside else kind
    return out


def decode(tokens, predicted, begin_inside):
    found, i = [], 0
    while i < len(tokens):
        t = predicted[i]
        if t == "outside":
            i += 1
            continue
        kind = t[2:] if begin_inside else t
        j = i + 1
        while j < len(tokens) and predicted[j] == ("I-" + kind if begin_inside else kind):
            j += 1
        found.append((i, j, kind))
        i = j
    return found


def build_table(begin_inside, key):
    counts = {}
    for x in TRAIN:
        for t, e in zip(x["tokens"], label(x["tokens"], begin_inside)):
            counts.setdefault(key(t), Counter())[e] += 1
    default = Counter(e for x in TRAIN
                      for e in label(x["tokens"], begin_inside)).most_common(1)[0][0]
    return {t: c.most_common(1)[0][0] for t, c in counts.items()}, default


def evaluate(name, begin_inside, key=lambda t: t, constant=None):
    table, default = build_table(begin_inside, key)
    hit = total = tp = predicted_n = gold_n = 0
    for x in HELD_OUT:
        tokens = x["tokens"]
        predicted = ([constant] * len(tokens) if constant
                     else [table.get(key(t), default) for t in tokens])
        kinds = [e[2:] if begin_inside and e != "outside" else e for e in predicted]
        hit += sum(a == b for a, b in zip(label(tokens, False), kinds))
        total += len(tokens)
        found, gold = decode(tokens, predicted, begin_inside), entities(tokens)
        tp += sum(v in gold for v in found)
        predicted_n += len(found)
        gold_n += len(gold)
    precision, recall = tp / predicted_n if predicted_n else 0.0, tp / gold_n
    f1 = 2 * precision * recall / (precision + recall) if precision + recall else 0.0
    print(f"{name:<28} {hit / total:>9.4f} {precision:>9.4f} {recall:>11.4f} {f1:>7.4f}")


MOST_COMMON = Counter(e for x in TRAIN for e in label(x["tokens"], False)).most_common(1)[0][0]
print(f"{len(DATA)} notes contain {sum(len(entities(x['tokens'])) for x in DATA)} entities, "
      f"{sum(j - i > 1 for x in DATA for i, j, _ in entities(x['tokens']))} of them multi-token; "
      f"the most frequent token label is '{MOST_COMMON}'")
print(f"\n{'named entity':<28} {'token':>9} {'precision':>9} {'recall':>11}"
      f" {'F1':>7}")
LAST3 = (lambda t: t[-3:])
evaluate("most frequent label", False, constant=MOST_COMMON)
evaluate("last 3 chars, type", False, LAST3)
evaluate("last 3 chars, B/I", True, LAST3)
evaluate("token identity, type", False)
evaluate("token identity, B/I", True)

1800 notes contain 4378 entities, 1583 of them multi-token; the most frequent token label is 'outside'

named entity                     token precision      recall      F1
most frequent label             0.5061    0.0000      0.0000  0.0000
last 3 chars, type              0.9824    0.9191      0.9343  0.9267
last 3 chars, B/I               0.9824    0.9421      0.9786  0.9600
token identity, type            1.0000    0.9774      0.9558  0.9665
token identity, B/I             1.0000    1.0000      1.0000  1.0000

The set contains 4,378 entities and 1,583 of them span more than one token. The most frequent token label is outside any entity, and writing it to every token gives an accuracy of 0.5061 on the held-out set: more than half of the tokens are labeled correctly. The entity-level number for the same output is 0.0000, because not a single entity is found. The rule of the course offers no sharper example than this — read alone, 0.5061 makes one think the procedure has gone half the way, yet it has found nothing.

The middle two rows show the real split. The procedure that looks at the last three characters gives the same token accuracy under both schemes: 0.9824. At the entity level it gives 0.9267 and 0.9600. The two schemes make the same token decisions; the only place they part is how they read the boundary, and the token-level metric cannot see this difference. The same output has two numbers, and which one gets written depends on the definition of the metric.

How a token error turns into an entity error can also be read in the table: a token-level error of 0.0176 gives an F1 loss of 0.0733 in the type scheme. An entity counts only if all of its tokens are right, which means the error is multiplied along the entity. The last pair of rows shows this at the extreme: memorization gives a token accuracy of 1.0000 and stays at 0.9665 in the type scheme. Even with perfect token decisions there is a loss, because the type scheme counts two adjacent entities of the same type as a single entity — in the note boruda kelepce eksik two separate pieces of hardware collapse into one span. The begin/inside distinction carries this into the label and gives 1.0000.

The Same Baseline, Another Task

The second task is part of speech and has no entity level: the label is one-to-one with the token.

POS_COUNTS = Counter(POS_TAG[t] for x in HELD_OUT for t in x["tokens"])
POS_DEFAULT = Counter(POS_TAG[t] for x in TRAIN for t in x["tokens"]).most_common(1)[0][0]


def measure_pos(name, key=None):
    table = {}
    if key:
        counts = {}
        for x in TRAIN:
            for t in x["tokens"]:
                counts.setdefault(key(t), Counter())[POS_TAG[t]] += 1
        table = {k: v.most_common(1)[0][0] for k, v in counts.items()}
    hit = total = 0
    for x in HELD_OUT:
        for t in x["tokens"]:
            hit += (table.get(key(t), POS_DEFAULT) if key else POS_DEFAULT) == POS_TAG[t]
            total += 1
    print(f"{name:<28} {hit / total:>9.4f}")


print("token types in the held-out set: "
      + ", ".join(f"{k} {v}" for k, v in POS_COUNTS.most_common()))
print(f"\n{'part of speech':<28} {'token':>9}")
measure_pos(f"most frequent label ({POS_DEFAULT})")
measure_pos("last 3 chars", LAST3)
measure_pos("token identity", lambda t: t)

token types in the held-out set: noun 2181, adjective 622, verb 603, number 312, stop word 267

part of speech                   token
most frequent label (noun)      0.5473
last 3 chars                    0.9905
token identity                  1.0000

Writing the most frequent label to every token gives 0.5473 here, which is even higher than for the named entity. Of the 3,985 tokens of the held-out set 2,181 are nouns, and this share alone sets the baseline. The last three characters give 0.9905 and the token identity gives 1.0000. The numbers are high because the task is easy in this setup: the part of speech of a surface form does not change.

The real reading is in comparing the two tasks. The baseline of the same form carries two different meanings in two tasks: in part of speech 0.5473 honestly reports the difficulty of the task, while in the named entity 0.5061 shows a procedure that has found nothing as halfway there. The difference is not in the procedure but in the metric — in one the labeled unit and the counted unit are the same, in the other they are not.

Summary

• The label was taken from the document and distributed to the tokens; the 1,800 notes hold 4,378 entities and 1,583 of them span more than one token.
• The domain baseline is writing the most frequent label to every token: 0.5061 at the token level, F1 0.0000 at the entity level. Read alone, the token-level number makes one think the procedure has gone half the way.
• The procedure that looks at the last three characters gives the same token accuracy (0.9824) under both labeling schemes while it gives 0.9267 and 0.9600 at the entity level; the difference lies only in how the boundary is read, and the token-level metric cannot see it.
• A token-level error of 0.0176 gives an F1 loss of 0.0733 in the type scheme; memorization stays at 0.9665 in the type scheme with a token accuracy of 1.0000, because two adjacent entities of the same type collapse into one span.
• In part of speech the baseline of the same form gives 0.5473 and does not mislead: there the labeled unit and the counted unit are the same.

Next Step

Over four lessons the text was turned into numbers: it was split into tokens, opened into columns, embedded into vectors and, in the last lesson, the label was distributed to the tokens. The decision given to the whole document was asked in this series only once, with a single binary question, and what was measured there was not the decision itself but the representation: what each representation adds. The event kind the note reports has four classes, however, and that decision was never made. The pipeline itself was never taken apart either — tokenization, weighting and classifier were measured together, and how many points each step adds was not asked separately. The next lesson classifies the document as a whole and counts the share of every step of the pipeline one by one.