Embedding Layers

In the previous two lessons every step of the input was a ready-made number. Sequences do not arrive like this. In a counter record, next to the reading there is an event code — calibration, communication outage, cover opening, manual reading — and this code is a symbol. It has no numeric value; that the seventeenth code is larger than the sixteenth says nothing.

The Data Preparation and Feature Engineering course had turned these symbols into one-hot columns: one indicator column for each code. The procedure works, but it has two costs. The input dimension grows with the number of codes, and no closeness between the symbols is carried — two codes that can substitute for each other are as far apart as two unrelated codes. The question of this lesson is this: which number moves if the representation of the code is learned instead of given by hand, and what is the difference between the learned representation and a representation fixed without ever looking at the task.

• AR64. The sequence setup of the Architectures topic was built in architectures/06 and is fictional. In this lesson a fictional event code is added to each step: 24 codes, one per step, seed 20260218. The readings do not change.
• AR65. Eight codes are marked as suspect and the numbers of these eight in the series are not adjacent. The label is the presence of a suspect code in at least five of the twelve steps.
• AR66. The baseline is the most frequent class. Because the order of the code numbers is unrelated to the label, an ordinal numeric encoding is not expected to pass the baseline, and this is measured.
• AR67. The model is written inside the lesson and is a model: the representations of the steps are averaged, passed through a hidden layer (six units, rectified linear unit) and connected to a single output. No library is called.
• AR68. The four setups share the same body and differ only in the representation of the code: one-hot, learned embedding, frozen embedding, ordinal numeric code.
• AR69. In the one-hot setup the table is the identity matrix and is not stored; the code realizes it with counting. In the parameter count the identity matrix is not counted as parameters, because it has no free value.
• AR70. The frozen embedding is a table of the same size that is initialized and never updated. The projection of the dimensionality-reduction topic of the Unsupervised Learning course was also fixed without looking at the task; the measure there was the reconstruction error, here it is the held-out figure.
• AR71. Training is full-batch gradient descent with learning rate 0.9 and is measured at four epoch budgets: 150, 300, 450, 600.
• AR72. Each setup is printed with two runs; the runs differ in the initialization seed.

The Same Body, Four Representations

The task depends on the count of the codes, not on their order. For this reason the model averages the step representations and gives the average to a small hidden layer. Because the label is determined exactly by the codes, a representation that can separate the suspect codes from the others can solve the task perfectly; a representation that cannot separate them cannot solve it in any epoch budget.

# common.py — MODEL. The FICTIONAL sequence set of `architectures/06` is regenerated with the same seed;
# a FICTIONAL event code is added to every step.
import math

SEED, M32, STEPS = 20260218, 0xFFFFFFFF, 12
CODES, SUSPECT, MIN_SUSPECT = 24, (1, 4, 5, 9, 13, 16, 20, 22), 5


def generator(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 build_sequences(n, seed):
    D = []
    for i in range(n):
        r = generator(seed + i)
        r()
        reading = [0.0] + [round((r() + r() + r() - 1.5) * 1.9, 3) for _ in range(STEPS - 1)]
        r()
        o = generator(seed + 8000 + i)
        codes = [int(o() * CODES) for _ in range(STEPS)]
        D.append({"reading": reading, "codes": codes,
                  "y": 1 if sum(c in SUSPECT for c in codes) >= MIN_SUSPECT else 0})
    return D


DATA = build_sequences(720, SEED)
TRAIN, TEST = DATA[:200], DATA[540:]
rate = sum(x["y"] for x in TEST) / len(TEST)
BASELINE = max(rate, 1 - rate)
print(f"sequences {len(DATA)}, length {STEPS}, codes {CODES}, suspect codes {len(SUSPECT)}")
print(f"label rate train {sum(x['y'] for x in TRAIN) / len(TRAIN):.4f}, held-out {rate:.4f}")
print(f"baseline (most frequent class) {BASELINE:.4f}")
print(f"example code sequence {DATA[0]['codes']}, suspect count "
      f"{sum(c in SUSPECT for c in DATA[0]['codes'])}, label {DATA[0]['y']}")

sequences 720, length 12, codes 24, suspect codes 8
label rate train 0.3450, held-out 0.3556
baseline (most frequent class) 0.6444
example code sequence [0, 8, 0, 16, 22, 10, 17, 7, 14, 19, 7, 18], suspect count 2, label 0

The embedding layer is a table: as many rows as the number of codes, as many columns as the embedding dimension. The representation of a code is the row read from that table, and the row is a parameter — the gradient updates it too. In the one-hot setup there is no table, because multiplying the indicator vector by a linear layer is already reading a column of that layer. The difference between the two setups is not a difference of principle but of where the row is written and how many there are.

HIDDEN, STOPS = 6, (150, 300, 450, 600)


def represent(T, codes):
    if T is None:                       # one-hot: the table is the identity matrix, counting is enough
        h = [0.0] * CODES
        for c in codes:
            h[c] += 1.0 / STEPS
        return h
    h = [0.0] * len(T[0])
    for c in codes:
        for j in range(len(h)):
            h[j] += T[c][j] / STEPS
    return h


def make_table(kind, seed, d=3):
    if kind == "one-hot":
        return None, CODES
    if kind == "numeric":
        return [[c / (CODES - 1)] for c in range(CODES)], 1
    r = generator(seed)
    return [[(r() + r() + r() - 1.5) * 1.1 for _ in range(d)] for _ in range(CODES)], d


def train_model(seed, T, dm, learn, TR, lr=0.9):
    r = generator(seed + 500)
    g = lambda: (r() + r() + r() - 1.5) * 0.9
    W1 = [[g() for _ in range(dm)] for _ in range(HIDDEN)]
    b1, w, b, n, scores = [0.0] * HIDDEN, [g() for _ in range(HIDDEN)], [0.0], len(TR), {}
    for epoch in range(1, max(STOPS) + 1):
        gW1 = [[0.0] * dm for _ in range(HIDDEN)]
        gb1, gw, gb = [0.0] * HIDDEN, [0.0] * HIDDEN, 0.0
        gT = [[0.0] * dm for _ in range(CODES)] if learn else None
        for h, codes, y in TR:
            z = [sum(W1[i][j] * h[j] for j in range(dm)) + b1[i] for i in range(HIDDEN)]
            o = sum(w[i] * z[i] for i in range(HIDDEN) if z[i] > 0) + b[0]
            df = 1.0 / (1.0 + math.exp(-max(-30.0, min(30.0, o)))) - y
            gb += df
            da = [df * w[i] if z[i] > 0 else 0.0 for i in range(HIDDEN)]
            for i in range(HIDDEN):
                gw[i] += df * max(0.0, z[i])
                gb1[i] += da[i]
                for j in range(dm):
                    gW1[i][j] += da[i] * h[j]
            if learn:
                dh = [sum(da[i] * W1[i][j] for i in range(HIDDEN)) for j in range(dm)]
                for c in codes:
                    for j in range(dm):
                        gT[c][j] += dh[j] / STEPS
        for i in range(HIDDEN):
            w[i] -= lr * gw[i] / n
            b1[i] -= lr * gb1[i] / n
            for j in range(dm):
                W1[i][j] -= lr * gW1[i][j] / n
        b[0] -= lr * gb / n
        if learn:                       # the embedding table is a parameter too
            for c in range(CODES):
                for j in range(dm):
                    T[c][j] -= lr * gT[c][j] / n
            for k, (_h, codes, y) in enumerate(TR):
                TR[k] = (represent(T, codes), codes, y)
        if epoch in STOPS:
            P = {"T": T, "dm": dm, "W1": [u[:] for u in W1], "b1": b1[:],
                 "w": w[:], "b": b[0]}
            scores[epoch] = accuracy(P, TEST)
    return P, scores


def output(P, codes):
    h = represent(P["T"], codes)
    z = [sum(P["W1"][i][j] * h[j] for j in range(P["dm"])) + P["b1"][i]
         for i in range(HIDDEN)]
    return sum(P["w"][i] * max(0.0, z[i]) for i in range(HIDDEN)) + P["b"]


def accuracy(P, D):
    return sum((output(P, x["codes"]) > 0) == (x["y"] == 1) for x in D) / len(D)


NETS, SETUPS = {}, (("one-hot", "one-hot", False), ("embedding, learned", "embedding", True),
                    ("embedding, frozen", "embedding", False), ("numeric code", "numeric", False))

print(f"hidden units {HIDDEN}, training examples {len(TRAIN)}, "
      f"baseline {BASELINE:.4f}")
print(f"{'setup':<21}{'parameters':>10}{'learned':>10}{'run':>7}"
      + "".join(f"{'epoch ' + str(t):>10}" for t in STOPS))
for name, kind, learn in SETUPS:
    NETS[name] = []
    for k in (1, 2):
        T, dm = make_table(kind, SEED + 900 + k)
        TR = [(represent(T, x["codes"]), x["codes"], x["y"]) for x in TRAIN]
        P, scores = train_model(SEED + k, T, dm, learn, TR)
        NETS[name].append(P)
        emb = CODES * dm if kind == "embedding" else 0
        params = HIDDEN * dm + 2 * HIDDEN + 1 + emb
        learned = params - (0 if learn else emb)
        print(f"{name if k == 1 else '':<21}{params:>10}{learned:>10}{k:>7}"
              + "".join(f"{scores[t]:>10.4f}" for t in STOPS))

hidden units 6, training examples 200, baseline 0.6444
setup                parameters   learned    run epoch 150 epoch 300 epoch 450 epoch 600
one-hot                     157       157      1    0.7167    0.8000    0.9222    0.9611
                            157       157      2    0.7000    0.8111    0.8611    0.9556
embedding, learned          103       103      1    0.9722    1.0000    1.0000    1.0000
                            103       103      2    0.9833    1.0000    1.0000    1.0000
embedding, frozen           103        31      1    0.6944    0.6778    0.6778    0.6833
                            103        31      2    0.7278    0.7389    0.7444    0.7444
numeric code                 19        19      1    0.6444    0.6444    0.6444    0.6444
                             19        19      2    0.6444    0.6444    0.6444    0.6444

Four rows give four separate results. The learned embedding rises to 0.9722 and 0.9833 at 150 epochs and settles at 1.0000 in both runs at 300 epochs — because the task is determined exactly by the codes, this is the expected ceiling. The one-hot setup gives 0.7167 and 0.7000 in the same 150 epochs, that is, a little above the baseline. The difference does not come from expressive power: at 600 epochs it rises to 0.9611 and 0.9556. It arrives at the same place with four times the epoch budget, and it does so with 157 parameters, against 103 for the embedding.

The frozen table has the same size and is connected to the same body; its only difference is that the 72-row table is never updated. It stays between 0.68 and 0.75 in all four epoch budgets. Adding epochs does not help, because what is missing is not budget: three directions chosen without looking at the task do not separate the eight suspect codes from the other sixteen, and the body cannot produce a distinction from a representation that is not separated. The dimensionality-reduction topic of the Unsupervised Learning course had measured the same position with the reconstruction error — there, the two-component projection had given 2.7762 against the 3.3411 of reconstructing with the column means — and the directions there were also chosen from the data, not from the label. That a representation preserves the data well does not mean it carries the distinction the task wants.

The last row is the harshest. The ordinal numeric code gives exactly 0.6444 in all four budgets — the baseline itself. Because the order among the code numbers is unrelated to the label, a single channel carries nothing. The warning of the encoding lesson of the Data Preparation and Feature Engineering course turns into a number here.

How the Parameter Count Grows with the Number of Codes

At twenty-four codes the parameter gain of the embedding is small: 103 against 157. Where the gain comes from becomes visible only as the number of codes and the hidden layer grow. The calculation is a single line and requires no run.

def count_params(V, hidden, d=None):
    if d is None:
        return V * hidden + 2 * hidden + 1        # one-hot vector straight into the layer
    return V * d + d * hidden + 2 * hidden + 1    # embedding table, then the layer


print(f"{'codes':>11}{'hidden units':>13}{'one-hot':>11}{'embedding d=3':>15}"
      f"{'ratio':>8}{'multiplications per step':>26}")
for V in (CODES, 240, 2400):
    for hidden in (HIDDEN, 64):
        a, b = count_params(V, hidden), count_params(V, hidden, 3)
        print(f"{V:>11}{hidden:>13}{a:>11}{b:>15}{b / a:>8.3f}"
              f"{f'{V * hidden} / {3 * hidden}':>26}")

      codes hidden units    one-hot  embedding d=3   ratio  multiplications per step
         24            6        157            103   0.656                  144 / 18
         24           64       1665            393   0.236                1536 / 192
        240            6       1453            751   0.517                 1440 / 18
        240           64      15489           1041   0.067               15360 / 192
       2400            6      14413           7231   0.502                14400 / 18
       2400           64     153729           7521   0.049              153600 / 192

In the one-hot setup the parameter count grows as the product of the number of codes and the number of hidden units. In the embedding the table grows in direct proportion to the number of codes, but the hidden layer depends only on the embedding dimension, so the second factor stays fixed. At 2,400 codes and 64 hidden units the ratio drops to 0.049. The last column reads the number of multiplications in the same way: multiplying by a one-hot vector requires 153,600 multiplications, and 153,536 of them are done with zero; reading a row from the table and doing 192 multiplications gives the same result. Only the first row was measured; the rest are values of the same formula.

What the Learned Table Encoded

The embedding raising the number is a result; which structure it found is a separate question. The task divides the codes into two groups, and if this distinction is visible in the table, the suspect codes should stand closer to one another than to the others. The measure is scale independent: the ratio of the mean distance between groups to the mean distance within groups.

def distance(u, v):
    return sum((u[i] - v[i]) ** 2 for i in range(len(u))) ** 0.5


def mean_pairwise(T, A, B):
    c = [distance(T[i], T[j]) for i in A for j in B if i != j]
    return sum(c) / len(c)


SUSP = [c for c in range(CODES) if c in SUSPECT]
OTHER = [c for c in range(CODES) if c not in SUSPECT]
print(f"suspect codes {len(SUSP)}, others {len(OTHER)}")
print(f"{'table':<26}{'run':>7}{'within suspect':>16}{'within other':>14}"
      f"{'between groups':>16}{'separation ratio':>18}")
for name in ("embedding, learned", "embedding, frozen"):
    for k in (0, 1):
        T = NETS[name][k]["T"]
        i, o, a = (mean_pairwise(T, SUSP, SUSP), mean_pairwise(T, OTHER, OTHER),
                   mean_pairwise(T, SUSP, OTHER))
        print(f"{name if k == 0 else '':<26}{k + 1:>7}{i:>16.4f}{o:>14.4f}"
              f"{a:>16.4f}{a / ((i + o) / 2):>18.4f}")

suspect codes 8, others 16
table                         run  within suspect  within other  between groups  separation ratio
embedding, learned              1          0.7629        0.8020          3.0634            3.9153
                                2          0.8673        0.9887          3.0602            3.2977
embedding, frozen               1          0.9898        1.0181          1.0771            1.0728
                                2          1.0155        1.1029          1.0766            1.0164

In the learned table the two groups are separated from each other: the mean distance between groups is 3.9153 and 3.2977 times the within-group mean. In the frozen table the same ratio is 1.0728 and 1.0164 — that is, the within-group and between-group distances are almost equal, because three randomly chosen directions have scattered the codes in an order the task does not recognize. There is a difference of 0.6176 between the separation ratios of the two runs, and both runs produce 1.0000 accuracy; where exactly the table is placed depends on the run, but whether it makes the distinction does not.

Summary

• Giving a one-hot vector to a linear layer is the same operation as reading a row from an embedding table; the difference is in the parameter count and the multiplication count.
• On the same body, the learned embedding gives 0.9722 and 0.9833 at 150 epochs with 103 parameters; the one-hot setup with 157 parameters stays at 0.7167 and 0.7000 in the same epochs and reaches a similar figure only at 600 epochs.
• The table of the same size frozen without looking at the task stays between 0.68 and 0.75 and adding epochs does not fix this; the projection of the Unsupervised Learning course was in the same position and was measured there with the reconstruction error.
• The ordinal numeric encoding gives exactly the baseline, 0.6444, in all four epoch budgets, because the order of the code numbers is unrelated to the label.
• In the learned table the distance between groups is 3.9153 and 3.2977 times the within-group distance; in the frozen table it is 1.0728 and 1.0164 times, that is, there is no distinction.

Next Step

In this lesson the embedding table was learned with the labels of the task itself, and two hundred training examples were enough for it. Where the label is expensive, this assumption fails: if there are twenty or forty labeled sequences, learning all hundred and three parameters from those forty examples ends in overfitting. There is another way, and the structure built in this lesson uses it directly — the table can be learned on another task and carried over to this one. The next lesson produces a pretrained model by hand from a fictional source task, transfers the weights either by freezing or by fine-tuning, and prints the difference the transfer adds together with how many labeled examples it adds it with, against the same baseline.