Numerical Representation

The previous lesson split the text into tokens and brought the vocabulary down to 96 stems. What came out was still a list of words; not a single number that a model would see had been produced. This lesson turns the vocabulary into columns: every stem becomes a column, and whether it occurs in the note becomes the value of that column. The name of the procedure is bag of words, because the order is discarded — muhur kirik (seal broken) and kirik muhur (broken seal) give the same row.

The line of the measure is ready. The Data Preparation and Feature Engineering course had extracted five numbers by hand from the same note field, and those five numbers had added 0.0317 on the held-out set to a decision tree. The domain baseline is those five numbers: the cheapest way of extracting numbers from a text. How far above this line does the bag of words go, what does the contribution do as the vocabulary grows, and what does term weighting put on top.

• NL9. The setup, the set and the seed are as in nlp/01. The tokenization decision is the third decision of 01 — dropping punctuation, lowercasing, stemming, number folding — and it is fixed in this lesson.
• NL10. The task is the binary prediction of illicit-use suspicion. The metric is the accuracy on the held-out set (larger is better), and the recall of the suspicious class is written next to it. The metric definitions were set up in the Supervised Learning course and are not repeated.
• NL11. All representations use the same model: a single-layer linear model, full-batch gradient descent, 120 rounds, step 1.5, threshold zero. Because the model and the metric are fixed, the difference can come only from the representation.
• NL12. Every step of the pipeline is learned from the training set only: the vocabulary, the document frequency, the mean and the standard deviation. The rule of the Data Preparation and Feature Engineering course continues.
• NL13. The domain baseline is five hand-counted numbers: note length, word count and three keyword indicators (seal, access, vehicle). The first two are scaled with the mean and standard deviation of the training set. The most frequent class is the absolute baseline, and its recall is zero.
• NL14. The vocabulary size sweep is six candidates: 8, 16, 32, 48, 64, 96. The vocabulary is taken in order from the most frequent stems of the training set.
• NL15. Term weighting is named by its form: raw count, and the count multiplied by the inverse document frequency — the second is brought to unit length per document.
• NL16. The ceiling is the number of a procedure that knows the event kind on the same metric; since the label is generated from the kind alone, this is the highest number that can be read from the text.

Setup

The notes are regenerated 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.

Bag of Words and Vocabulary Size

The model is written once and stays the same on every row. The features are given sparsely: because a note contains a dozen or so stems, a few multiplications per row are enough even when the column count goes up to 96.

import math
from collections import Counter

SUFFIXES = ["lari", "leri", "lar", "ler", "nin", "nun", "dan", "den", "tan", "ten",
            "dir", "tir", "dur", "da", "de", "ta", "te", "in", "un", "yi", "yu",
            "si", "su", "li", "lu", "di", "du", "ti", "tu", "i", "u", "a", "e"]


def stem(token):
    for suffix in SUFFIXES:
        if token.endswith(suffix) and len(token) - len(suffix) >= 3:
            return token[:-len(suffix)]
    return token


for x in DATA:  # third decision of nlp/01: drop punctuation, lowercase, stem, fold numbers
    x["tokens"] = [("<number>" if t.isdigit() else stem(t))
                   for t in (s.strip(",.").lower() for s in x["note"].split()) if t]


def fit_model(features, y, size, rounds=120, step=1.5):
    w = [0.0] * (size + 1)
    for _ in range(rounds):
        grad = [0.0] * (size + 1)
        for x, target in zip(features, y):
            z = w[size] + sum(w[i] * v for i, v in x)
            err = 1 / (1 + math.exp(-max(-30.0, min(30.0, z)))) - target
            for i, v in x:
                grad[i] += err * v
            grad[size] += err
        for i in range(size + 1):
            w[i] -= step * grad[i] / len(y)
    return w


def evaluate(w, features, y, size):
    correct = caught = 0
    for x, truth in zip(features, y):
        pred = int(w[size] + sum(w[i] * v for i, v in x) > 0)
        correct, caught = correct + (pred == truth), caught + (pred == 1 and truth == 1)
    return correct / len(y), caught / sum(y)


def run(name, build, size):  # the first call sets the line
    y_train, y_held = [x["suspicious"] for x in TRAIN], [x["suspicious"] for x in HELD_OUT]
    w = fit_model([build(x) for x in TRAIN], y_train, size)
    acc_train, _ = evaluate(w, [build(x) for x in TRAIN], y_train, size)
    acc_held, recall_held = evaluate(w, [build(x) for x in HELD_OUT], y_held, size)
    if not BASELINE:
        BASELINE.append(acc_held)
    print(f"{name:<26} {size:>7} {acc_train:>9.4f} {acc_held:>9.4f} {recall_held:>10.4f}"
          f" {acc_held - BASELINE[0]:>+8.4f}")
    return acc_held


KEYWORDS, BASELINE = ["muhur", "erisim", "arac"], []
raw = [[len(x["note"]), len(x["tokens"])] for x in TRAIN]
MEAN = [sum(r[i] for r in raw) / len(raw) for i in (0, 1)]
STD = [math.sqrt(sum((r[i] - MEAN[i]) ** 2 for r in raw) / len(raw)) for i in (0, 1)]


def by_hand(x):  # the five numbers of the Data Preparation and Feature Engineering course
    o = [(0, (len(x["note"]) - MEAN[0]) / STD[0]), (1, (len(x["tokens"]) - MEAN[1]) / STD[1])]
    for i, keyword in enumerate(KEYWORDS):
        o.append((2 + i, float(any(t.startswith(keyword) for t in x["tokens"]))))
    return o


MAJORITY = sum(x["suspicious"] == 0 for x in HELD_OUT) / len(HELD_OUT)
print(f"{'representation':<26} {'columns':>7} {'train':>9} {'held-out':>9} {'recall':>10}"
      f" {'vs line':>8}")
run("hand-counted five numbers", by_hand, 5)
print(f"{'most frequent class':<26} {0:>7} {'':>9} {MAJORITY:>9.4f} {0.0:>10.4f}"
      f" {MAJORITY - BASELINE[0]:>+8.4f}")

FREQ = Counter(t for x in TRAIN for t in x["tokens"])
RANKED = sorted(FREQ, key=lambda t: (-FREQ[t], t))
DOC_FREQ = Counter(t for x in TRAIN for t in set(x["tokens"]))
STOP_STEMS = {stem(w) for w in STOP_WORDS}


def bag(terms, mode="indicator"):
    index = {t: i for i, t in enumerate(terms)}
    idf = {t: math.log(len(TRAIN) / DOC_FREQ.get(t, 1)) for t in index}

    def build(x):
        counts = Counter(t for t in x["tokens"] if t in index)
        if mode == "indicator":
            return [(index[t], 1.0) for t in counts]
        if mode == "count":
            return [(index[t], float(v)) for t, v in counts.items()]
        norm = math.sqrt(sum((v * idf[t]) ** 2 for t, v in counts.items())) or 1.0
        return [(index[t], v * idf[t] / norm) for t, v in counts.items()]
    return build


print()
for n in (8, 16, 32, 48, 64, 96):
    run(f"bag of words {n}", bag(RANKED[:n]), n)

representation             columns     train  held-out     recall  vs line
hand-counted five numbers        5    0.7608    0.7383     0.3408  +0.0000
most frequent class              0              0.7017     0.0000  -0.0367

bag of words 8                   8    0.7783    0.7667     0.3296  +0.0283
bag of words 16                 16    0.7908    0.7700     0.3911  +0.0317
bag of words 32                 32    0.8208    0.8067     0.5140  +0.0683
bag of words 48                 48    0.8300    0.8133     0.5363  +0.0750
bag of words 64                 64    0.8333    0.8217     0.5698  +0.0833
bag of words 96                 96    0.8350    0.8217     0.5698  +0.0833

The line is 0.7383, and it passes the most frequent class by 0.0367. In the Data Preparation and Feature Engineering course, the same five numbers had added 0.0317 to a decision tree; the closeness of the two numbers is not a coincidence, because the source of the contribution in both setups is the same three keyword indicators. The recall column shows why the baseline has to be read: while the most frequent class gives an accuracy of 0.7017, it finds none of the suspicious ones.

The bag of words passes the line by 0.0833 — more than twice what the five hand-counted numbers added. Even eight columns add 0.0283, which means the eight most frequent stems do about the same work as five hand-picked indicators. The contribution saturates at 64 columns: between 64 and 96 the held-out score stays exactly the same while the training score rises from 0.8333 to 0.8350. Adding columns always raises the training score; this is not a measurement but a requirement of the definition.

Weighting and the Ceiling

What is written into the cell of the bag is a separate decision: a presence indicator, a raw count, or the frequency weighted by its sparsity across documents.

run("count weighting", bag(RANKED, "count"), len(RANKED))
run("inverse document frequency", bag(RANKED, "weighted"), len(RANKED))
KEPT = [t for t in RANKED if t not in STOP_STEMS]
run("stop words removed", bag(KEPT), len(KEPT))

KIND_LABEL = {}
for name, _, _ in KINDS:
    p = [x["suspicious"] for x in TRAIN if x["kind"] == name]
    KIND_LABEL[name] = int(sum(p) * 2 > len(p))
ceiling = sum(KIND_LABEL[x["kind"]] == x["suspicious"] for x in HELD_OUT) / len(HELD_OUT)
print(f"\n{'ceiling (event kind known)':<26} {'':>7} {'':>9} {ceiling:>9.4f} {'':>10}"
      f" {ceiling - BASELINE[0]:>+8.4f}")

count weighting                 96    0.8333    0.8217     0.5698  +0.0833
inverse document frequency      96    0.8150    0.8217     0.5363  +0.0833
stop words removed              90    0.8292    0.8150     0.5419  +0.0767

ceiling (event kind known)                      0.8250             +0.0867

Term weighting adds nothing in this corpus: all three rows give 0.8217. The reason lies in the text itself. The notes are short, and a stem almost always occurs once in a note, so a raw count cannot be told apart from an indicator column. Inverse document frequency weighting rescales the columns but does not break the ordering; while the accuracy stays the same, the recall falls from 0.5698 to 0.5363. The difference it adds is 0.0000.

Dropping stop words loses 0.0067. Three of the six stop words are markers of particular patterns in this setup: ile (with) occurs only in the ordinary phrase, ama (but) only in the fault phrase. The stop word list is read from the task, not from the language; a general list throws away information here.

The last row closes the remaining gap. A procedure that knows the event kind gives 0.8250, and the bag of words, at 0.8217, is 0.0033 below it. Since the label is generated from the kind alone, this is the highest number that can be read from the text: a better representation cannot win more than 0.0033 in this setup. The source of the difference can be written down as well — the model is the same on every row, the metric and the held-out set are the same, and the difference comes from the representation.

Summary

• The domain baseline is five hand-counted numbers and it gives 0.7383; the most frequent class stays at 0.7017 and finds none of the suspicious ones.
• The bag of words of 96 stems gives 0.8217 and passes the line by 0.0833 — more than twice what the five hand-counted numbers added. Because the model and the metric are fixed, the whole difference comes from the representation.
• Vocabulary size adds contribution from 8 to 64 and saturates there: while the difference between 64 and 96 is exactly zero, the training score rises from 0.8333 to 0.8350.
• Term weighting adds 0.0000; because the notes are short, the count cannot be told apart from the indicator, and inverse document frequency weighting moves the recall rather than the accuracy (from 0.5698 to 0.5363). Dropping stop words loses 0.0067, because three words on the list are pattern markers in this setup.
• The ceiling that knows the event kind is 0.8250; the bag is 0.0033 below the ceiling, and the remaining gap is not in the text.

Next Step

The bag of words turned a note into 96 columns, but the columns are entirely strangers to one another: the muhur (seal) and kelepce (clamp) columns are as far apart as the muhur and <number> columns. All the model learns is the relation of each column to the label, and this relation is learned from scratch for every column. Yet in the notes muhur and kelepce occur next to similar words. The next lesson uses this: every stem is represented by a vector instead of a number, and the vector is learned from the context. The measure is whether the learned neighborhood turns out to be meaningful and in how many cases the vector arithmetic holds.