Word Embeddings

The bag of words turned a note into 96 columns, but the columns were strangers to one another: the muhur (seal) column was as far from the kelepce (clamp) column as from the <number> column. Yet in the notes these two occur in the same phrases, next to the same words. In this lesson every vocabulary item is given a vector, and the vector is learned not from the label but from the context. The claim is distributional meaning: words that occur in similar contexts get similar vectors.

The embedding table itself was measured in the Deep Learning course, in architectures/08, and its procedure is not repeated. What is added here is moving the measure: the number is not the accuracy of a classifier but the order of the vectors themselves. Two tests are run, and both are read against their own baseline.

• NL17. Tokenization here is the second decision of nlp/01: dropping punctuation, lowercasing, number folding. Stemming is not applied, because one of the things to be measured is whether inflectional suffixes leave a trace in the vectors. The vocabulary is 124 items.
• NL18. The embedding table was measured in the Deep Learning course, architectures/08; the layer procedure is not repeated.
• NL19. The model is written within the lesson and it is the model: a center vector and a context vector for every item, eight dimensions, 1,984 parameters in total.
• NL20. Training: context window of two, two negative samples for every distinct pair, a weight of $\log(1+n)$ on the pair count, 40 epochs, step 0.08. The negative sample is drawn from the vocabulary with its own frequency.
• NL21. The vectors are learned from the training set only; the pairs are extracted from 1,200 notes.
• NL22. The metric is cosine similarity: the vectors are brought to unit length and the dot product is read.
• NL23. The truth of the neighborhood test comes from the setup: a form belongs to the group of a phrase pool if its root occurs in that one pool only. 81 of the 124 items are like this.
• NL24. The domain baseline is the raw co-occurrence vector: it learns nothing, it only counts. The absolute baseline is the random neighbor, and its expected rate is computed from the group sizes.

Vectors Learned from Context

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.

Training sees every distinct context pair once: the vector of the center word is moved closer to the context vector of the true neighbor and away from those of the two negative samples drawn from the vocabulary.

import math
from collections import Counter

DIM, WINDOW, NEGATIVES, EPOCHS, STEP = 8, 2, 2, 40, 0.08

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

FREQ = Counter(t for x in TRAIN for t in x["tokens"])
VOCAB = sorted(FREQ, key=lambda t: (-FREQ[t], t))
POS = {t: i for i, t in enumerate(VOCAB)}
PAIRS = Counter()
for x in TRAIN:
    ids = [POS[t] for t in x["tokens"]]
    for i, a in enumerate(ids):
        for j in range(max(0, i - WINDOW), min(len(ids), i + WINDOW + 1)):
            if j != i:
                PAIRS[(a, ids[j])] += 1

T = sum(FREQ.values())
NOISE = [FREQ[t] / T for t in VOCAB]  # the negative sample is drawn with the word's own frequency
r = rng(SEED + 31000)
U = [[(r() - 0.5) * 0.6 for _ in range(DIM)] for _ in VOCAB]
C = [[0.0] * DIM for _ in VOCAB]
for _ in range(EPOCHS):
    for (a, b), n in PAIRS.items():
        w = math.log(1 + n)
        for k, target in [(b, 1.0)] + [(pick(r(), NOISE), 0.0) for _ in range(NEGATIVES)]:
            z = sum(U[a][i] * C[k][i] for i in range(DIM))
            err = STEP * w * (1 / (1 + math.exp(-max(-30.0, min(30.0, z)))) - target)
            for i in range(DIM):
                U[a][i], C[k][i] = U[a][i] - err * C[k][i], C[k][i] - err * U[a][i]

print(f"{len(VOCAB)} vocabulary items, {len(PAIRS)} distinct context pairs, "
      f"{2 * len(VOCAB) * DIM} parameters, {EPOCHS} epochs")


def unit(v):
    u = math.sqrt(sum(x * x for x in v)) or 1.0
    return [x / u for x in v]


UNIT = [unit(v) for v in U]


def cosine(i, j):
    return sum(UNIT[i][k] * UNIT[j][k] for k in range(DIM))


GROUP = {}
for kind, templates in PHRASES.items():
    for template in templates:
        for s in template.split():
            name = s[1:-1].partition(".")[0] if s.startswith("{") else s
            GROUP.setdefault(name, set()).add(kind)
for template in EXTRA_PHRASES:
    for s in template.split():
        name = s[1:-1].partition(".")[0] if s.startswith("{") else s
        GROUP.setdefault(name, set()).add("extra")
for f in RARE:
    GROUP[f[0]] = {"rare"}
SINGLE = {name for name, v in GROUP.items() if len(v) == 1}
FORM_GROUP = {t: list(GROUP[ROOT[t]])[0] for t in VOCAB
              if t in ROOT and ROOT[t] in SINGLE}
GROUP_SIZE = Counter(FORM_GROUP.values())
print(f"{len(FORM_GROUP)} forms belong to a single phrase pool: "
      + ", ".join(f"{g} {n}" for g, n in sorted(GROUP_SIZE.items())))

124 vocabulary items, 3216 distinct context pairs, 1984 parameters, 40 epochs
81 forms belong to a single phrase pool: extra 7, fault 7, illicit 6, ordinary 4, rare 49, unreachable 8

Who Gets the Neighborhood

For every form the nearest neighbor is found and the group of the neighbor is compared with the group of the form. The same test is applied to three representations: the expected rate of a random neighbor, the raw co-occurrence vector and the learned embedding.

COUNT_VEC = [[0.0] * len(VOCAB) for _ in VOCAB]
for (a, b), n in PAIRS.items():
    COUNT_VEC[a][b] = float(n)
COUNT_UNIT = [unit(v) for v in COUNT_VEC]


def neighbor(vecs, i):
    best, best_j = -2.0, i
    for j in range(len(VOCAB)):
        if j != i:
            d = sum(vecs[i][k] * vecs[j][k] for k in range(len(vecs[i])))
            if d > best:
                best, best_j = d, j
    return VOCAB[best_j]


def hit_rate(vecs, forms):
    return sum(FORM_GROUP.get(neighbor(vecs, POS[f])) == FORM_GROUP[f] for f in forms) / len(forms)


def row(name, forms):
    expected = sum(GROUP_SIZE[FORM_GROUP[f]] - 1 for f in forms) / (len(forms) * (len(VOCAB) - 1))
    print(f"{name:<24} {len(forms):>5} {expected:>9.4f} {hit_rate(COUNT_UNIT, forms):>10.4f}"
          f" {hit_rate(UNIT, forms):>10.4f}")


ALL_FORMS = list(FORM_GROUP)
print(f"\n{'neighborhood test':<24} {'forms':>5} {'random':>9} {'raw counts':>10}"
      f" {'learned':>10}")
row("all", ALL_FORMS)
row("frequent forms only", [f for f in ALL_FORMS if FORM_GROUP[f] != "rare"])
row("rare nouns only", [f for f in ALL_FORMS if FORM_GROUP[f] == "rare"])

neighborhood test        forms    random raw counts    learned
all                         81    0.2543     0.4938     0.6049
frequent forms only         32    0.0462     0.0625     0.2500
rare nouns only             49    0.3902     0.7755     0.8367

The total row gives the expected order: random 0.2543, raw counts 0.4938, learned embedding 0.6049. The learned representation adds 0.1111 over the counts, which learn nothing. Without reading the subrows this number is misleading: 49 of the 81 forms tested are rare nouns, and all of them occur in a single phrase pattern, which means they are one another’s context. There the random expectation is 0.3902 and the raw counts give 0.7755.

On frequent forms the table reverses. On the 32 frequent forms the random expectation is 0.0462, and the raw counts at 0.0625 are only 0.0163 above it — the baseline that learns nothing really knows nothing here. The learned embedding gives 0.2500, which is five times random and four times the raw counts. This is where learning adds something, and it does not show in the total row. This is exactly the second claim of the course: when a domain metric is reduced to a single number, which subgroup the number comes from is lost.

Does Vector Arithmetic Hold

The second test is harsher. Two roots that take the same inflectional suffix are chosen, and the question is asked with the vectors: if the difference that goes from the form sayac (meter) to the form sayacin (of the meter) is added to muhur (seal), which form comes out. The first vector is subtracted from the second, the third is added, the form closest to the result is searched for, and the correct answer is muhurun (of the seal).

ANALOGIES = []
for k in range(1, 5):
    pairs_k = [NOUNS[a].split() for a in NOUNS
               if NOUNS[a].split()[0] in VOCAB and NOUNS[a].split()[k] in VOCAB]
    for a in pairs_k:
        for b in pairs_k:
            if a[0] != b[0]:
                ANALOGIES.append((a[0], a[k], b[0], b[k]))


def solve(vecs, a, b, c):
    v = [vecs[POS[b]][i] - vecs[POS[a]][i] + vecs[POS[c]][i] for i in range(len(vecs[0]))]
    best, best_j = -2.0, 0
    for j in range(len(VOCAB)):
        if VOCAB[j] not in (a, b, c):
            d = sum(v[i] * vecs[j][i] for i in range(len(v)))
            if d > best:
                best, best_j = d, j
    return VOCAB[best_j]


print(f"\n{'analogy':<18} {'tests':>6} {'hits':>7} {'same root':>9}"
      f"  most given answer")
for name, vecs in (("raw counts", COUNT_UNIT), ("learned embedding", UNIT)):
    hits = same_root = 0
    answers = Counter()
    for a, b, c, y in ANALOGIES:
        t = solve(vecs, a, b, c)
        hits, same_root = hits + (t == y), same_root + (t != y and ROOT.get(t) == ROOT.get(c))
        answers[t] += 1
    n, (top, top_n) = len(ANALOGIES), answers.most_common(1)[0]
    print(f"{name:<18} {n:>6} {hits / n:>7.4f} {same_root / n:>9.4f}  {top} {top_n / n:.4f}")

analogy             tests    hits same root  most given answer
raw counts             72  0.1250    0.0000  kelepcede 0.1111
learned embedding      72  0.0972    0.0556  kelepcesi 0.0694

Of the seventy-two tests, 0.1250 hold with the raw counts and 0.0972 with the learned embedding. Both are low, and this result is not hidden: at this scale analogy does not hold. For a suffix to leave a shared shift in the vectors, the same suffix has to be seen on many roots and in contexts that are separate from one another. In this setup every root and suffix pair occurs in one or two patterns; the vector carries the context of the root, not the context of the suffix. Of the seventy-two tests, 0.0556 land on another form of the same root, which means the root is captured and the suffix is not.

The expected flaw does not appear. The three most frequent forms are okuma (reading), <number> and olcum (measurement), and none of them comes out as an answer; the answers gather on the forms with the narrowest context — kelepcede (in the clamp) with 0.1111 with the raw counts, kelepcesi (its clamp) with 0.0694 with the embedding. The same representation beats the baseline in the neighborhood test and fails to in analogy; the two metrics read the same vectors in two different orders.

Summary

• An eight-dimensional embedding with 1,984 parameters was trained for 40 epochs on the 3,216 distinct context pairs from 1,200 notes; the vectors were learned from the context, not from the label.
• In the neighborhood test the random expectation gave 0.2543, the raw co-occurrence 0.4938, the learned embedding 0.6049; what the learned representation adds over the counts is 0.1111.
• The total number misleads: 49 of the 81 forms are rare nouns that occur in a single pattern, and there even the raw counts give 0.7755. On the 32 frequent forms random gives 0.0462, raw counts 0.0625, the learned embedding 0.2500 — this is where learning adds something, and it does not show in the total row.
• Analogy does not hold: of 72 tests 0.1250 are right with the raw counts and 0.0972 with the embedding. For the suffix to leave a trace in the vector, the same suffix has to be seen in many separate contexts.
• Of the seventy-two tests, 0.0556 land on another form of the same root; the answers gather not on the most frequent word but on the forms with the narrowest context (kelepcesi 0.0694).

Next Step

Over three lessons a note was reduced to a single line: first the token list, then the 96-column bag, then one vector per word. The decision given was every time about the whole document — is this note suspicious. Yet what each token inside the note reports was never asked: in the note sayacin kapagi kirik (the meter’s cover is broken), which token names the hardware, which the location, which the state. The next lesson takes the label from the document and gives it to every token separately. Then what accuracy counts changes as well: per token, or per entity that spans several tokens.