"""The XOR remap, done again on words. Chapter 8, Neural Network Fundamentals, worked as that chapter works it. XOR showed a hidden layer taking two inputs that look different, (0,1) and (1,0), and putting them in the same place because they behave alike. This script does the same thing to a five word vocabulary. Five words, five contexts, a hidden layer of two units. python3 xor_to_words.py # every table the chapter prints python3 xor_to_words.py --input # only the one-hot input space python3 xor_to_words.py --hand # only the hand-set embedding python3 xor_to_words.py --train # learn the embedding instead python3 xor_to_words.py --holdout # what the remap buys you Stdlib only. Written to be read, not to be fast. """ import argparse import math import random # -------------------------------------------------------------------------- # The corpus. Eleven (word, context) pairs, read off eleven short sentences. # -------------------------------------------------------------------------- WORDS = ["cat", "dog", "horse", "car", "bus"] CONTEXTS = ["feed", "sleeps", "ride", "drive", "park"] SENTENCES = [ ("feed the cat", "cat", "feed"), ("the cat sleeps", "cat", "sleeps"), ("feed the dog", "dog", "feed"), ("the dog sleeps", "dog", "sleeps"), ("feed the horse", "horse", "feed"), ("the horse sleeps", "horse", "sleeps"), ("ride the horse", "horse", "ride"), ("drive the car", "car", "drive"), ("park the car", "car", "park"), ("drive the bus", "bus", "drive"), ("ride the bus", "bus", "ride"), ] PAIRS = [(WORDS.index(w), CONTEXTS.index(c)) for _, w, c in SENTENCES] # The hand-set embedding of the chapter. Two hidden units, small integers. HAND_E = { "cat": (2, 0), "dog": (2, 0), "horse": (2, 1), "car": (0, 2), "bus": (1, 2), } # The hand-set output layer. One unit per context: (w1, w2, bias). HAND_W = { "feed": (1, -1, 0.0), "sleeps": (1, -1, 0.0), "ride": (1, 1, -2.5), "drive": (-1, 1, -0.5), "park": (-1, 1, -1.5), } def counts(): """The word by context count matrix.""" m = [[0] * len(CONTEXTS) for _ in WORDS] for i, j in PAIRS: m[i][j] += 1 return m def one_hot(word): return [1 if w == word else 0 for w in WORDS] def distance(u, v): return math.sqrt(sum((a - b) ** 2 for a, b in zip(u, v))) def cosine(u, v): dot = sum(a * b for a, b in zip(u, v)) nu = math.sqrt(sum(a * a for a in u)) nv = math.sqrt(sum(b * b for b in v)) return dot / (nu * nv) if nu and nv else 0.0 def pairs_of_words(): for i in range(len(WORDS)): for j in range(i + 1, len(WORDS)): yield WORDS[i], WORDS[j] def rule(title): print() print(title) print("-" * len(title)) # -------------------------------------------------------------------------- # 1. The input space # -------------------------------------------------------------------------- def show_input_space(): rule("The corpus, and the counts it gives") print("%-8s %s" % ("", " ".join("%7s" % c for c in CONTEXTS))) for w, row in zip(WORDS, counts()): print("%-8s %s" % (w, " ".join("%7d" % v for v in row))) print() print("Five contexts, but only four distinct columns: feed and sleeps") print("pick the same three words. That is why two hidden units suffice.") rule("One-hot inputs: five words, five dimensions") for w in WORDS: print("%-8s %s" % (w, one_hot(w))) rule("Every pair, in the input space") print("%-16s %9s %8s" % ("pair", "distance", "cosine")) for a, b in pairs_of_words(): print("%-16s %9.4f %8.2f" % ("%s, %s" % (a, b), distance(one_hot(a), one_hot(b)), cosine(one_hot(a), one_hot(b)))) print() print("Ten pairs, one distance. cat is exactly as far from dog") print("as it is from bus. The input space knows nothing.") # -------------------------------------------------------------------------- # 2. The hand-set embedding # -------------------------------------------------------------------------- def score(word, context): h1, h2 = HAND_E[word] w1, w2, b = HAND_W[context] return w1 * h1 + w2 * h2 + b def show_hand(): rule("The lookup: a one-hot times E selects a row of E") print("%-8s %-14s %-10s" % ("word", "one-hot x", "x E = h")) for w in WORDS: print("%-8s %-14s %-10s" % (w, one_hot(w), list(HAND_E[w]))) rule("Five input vectors land on four hidden points") landing_table(lambda w: HAND_E[w], lambda w: [c for c in CONTEXTS if score(w, c) > 0]) print() print("That is the XOR table again, with words in it. Two vectors that are") print("orthogonal in the input, cat and dog, arrive at the same place.") print("The hidden layer decided they are the same kind of thing.") rule("The output layer: one line per context, drawn in hidden space") print("%-8s %s %s" % ("", " ".join("%8s" % c for c in CONTEXTS), " fires for")) for w in WORDS: row = [score(w, c) for c in CONTEXTS] fires = [c for c in CONTEXTS if score(w, c) > 0] print("%-8s %s %s" % (w, " ".join("%8.1f" % v for v in row), " ".join(fires))) print() print("Compare the fires column with the count matrix. Same cells.") ok = all((score(w, c) > 0) == (counts()[i][j] > 0) for i, w in enumerate(WORDS) for j, c in enumerate(CONTEXTS)) print("every cell reproduced:", ok) rule("Every pair, in the hidden space") print("%-16s %9s %8s %9s" % ("pair", "distance", "cosine", "was")) for a, b in pairs_of_words(): print("%-16s %9.4f %8.2f %9.4f" % ("%s, %s" % (a, b), distance(HAND_E[a], HAND_E[b]), cosine(HAND_E[a], HAND_E[b]), math.sqrt(2))) print() print("One distance became nine. cat and dog collapsed to 0.") print("cat and car moved apart, from 1.4142 to 2.8284.") # -------------------------------------------------------------------------- # 3. Learning the embedding instead of setting it # -------------------------------------------------------------------------- def sigmoid(z): if z >= 0: return 1.0 / (1.0 + math.exp(-z)) e = math.exp(z) return e / (1.0 + e) def targets(): """One binary target per cell: did this word ever appear in this context.""" return [[1.0 if v > 0 else 0.0 for v in row] for row in counts()] def train(mask=None, hidden=2, epochs=6000, lr=1.0, decay=0.01, seed=7, verbose=False): """One unit per context, exactly like the hand-set output layer. Each cell of the word by context grid is a yes or no question, so the loss is binary cross-entropy over the grid. mask holds the cells to skip. hidden=0 removes the hidden layer, leaving a direct one-hot lookup. Returns (E, W, b); E is None when there is no hidden layer. """ rng = random.Random(seed) mask = set(mask or []) nv, nc = len(WORDS), len(CONTEXTS) d = hidden if hidden else nv y = targets() E = None if hidden == 0 else [[rng.uniform(-0.5, 0.5) for _ in range(d)] for _ in range(nv)] W = [[rng.uniform(-0.5, 0.5) for _ in range(nc)] for _ in range(d)] b = [0.0] * nc cells = [(i, j) for i in range(nv) for j in range(nc) if (i, j) not in mask] for epoch in range(epochs): gE = None if E is None else [[0.0] * d for _ in range(nv)] gW = [[0.0] * nc for _ in range(d)] gb = [0.0] * nc loss = 0.0 for i, j in cells: h = E[i] if E is not None else one_hot(WORDS[i]) z = sum(h[k] * W[k][j] for k in range(d)) + b[j] p = sigmoid(z) loss -= y[i][j] * math.log(max(p, 1e-12)) \ + (1 - y[i][j]) * math.log(max(1 - p, 1e-12)) dz = p - y[i][j] for k in range(d): gW[k][j] += h[k] * dz if gE is not None: gE[i][k] += W[k][j] * dz gb[j] += dz n = len(cells) for k in range(d): for j in range(nc): W[k][j] -= lr * (gW[k][j] / n + decay * W[k][j]) for j in range(nc): b[j] -= lr * gb[j] / n if gE is not None: for i in range(nv): for k in range(d): E[i][k] -= lr * (gE[i][k] / n + decay * E[i][k]) if verbose and epoch % 2000 == 0: print("epoch %5d loss %.4f" % (epoch, loss / n)) return E, W, b def predict(E, W, b, i): """P(context | word) for every context, each judged on its own.""" d = len(W) h = E[i] if E is not None else one_hot(WORDS[i]) return [sigmoid(sum(h[k] * W[k][j] for k in range(d)) + b[j]) for j in range(len(CONTEXTS))] def landing_table(place, fires): """The relocation table: where each input vector arrived, grouped. Both the hand-set and the learned embedding are read the same way, which is the whole point of printing it twice. """ seen = {} for w in WORDS: seen.setdefault(place(w), []).append(w) print("%-20s %-42s %s" % ("lands at", "arrived from", "fires for")) for point in sorted(seen, key=lambda p: WORDS.index(seen[p][0])): came = " and ".join( "%s (%s)" % (w, ",".join(str(v) for v in one_hot(w))) for w in seen[point]) shown = "(" + ", ".join(("%g" if float(v).is_integer() else "%.3f") % v for v in point) + ")" print("%-20s %-42s %s" % (shown, came, ", ".join(fires(seen[point][0])))) def show_train(): rule("Learning E by gradient descent, from the eleven pairs") E, W, b = train(verbose=True) print() rule("Five input vectors land on four hidden points, learned this time") emb = {w: tuple(round(v, 3) for v in row) for w, row in zip(WORDS, E)} fires = lambda w: [c for c, p in zip(CONTEXTS, predict(E, W, b, WORDS.index(w))) if p > 0.5] landing_table(lambda w: emb[w], fires) print() print("Same four groups as the hand-set table, and the same fires-for") print("column. Different coordinates, because nothing fixes the axes.") print("Read the distances, which a rotation cannot change.") rule("The learned grid, against the corpus") print("%-8s %s" % ("", " ".join("%7s" % c for c in CONTEXTS))) for i, w in enumerate(WORDS): p = predict(E, W, b, i) print("%-8s %s" % (w, " ".join("%7.2f" % v for v in p))) print() print("count matrix, for comparison") for w, row in zip(WORDS, counts()): print("%-8s %s" % (w, " ".join("%7d" % v for v in row))) rule("Every pair, in the learned hidden space") emb = dict(zip(WORDS, E)) ranked = sorted(pairs_of_words(), key=lambda p: distance(emb[p[0]], emb[p[1]])) print("%-16s %9s %8s %10s" % ("pair", "distance", "cosine", "hand-set")) for a, c in ranked: print("%-16s %9.4f %8.2f %10.4f" % ("%s, %s" % (a, c), distance(emb[a], emb[c]), cosine(emb[a], emb[c]), distance(HAND_E[a], HAND_E[c]))) print() print("Nearest pair: %s. Furthest: %s." % (" and ".join(ranked[0]), " and ".join(ranked[-1]))) print("Learning was told nothing about animals. It was shown") print("eleven sentences and given two dimensions to fit them in.") # -------------------------------------------------------------------------- # 4. What the remap buys: a cell the corpus never showed # -------------------------------------------------------------------------- # Add ("dog", "sleeps") here to delete every dog sentence at once. HELD_OUT = [("dog", "feed")] def held_out_cells(): return [(WORDS.index(w), CONTEXTS.index(c)) for w, c in HELD_OUT] def show_holdout(): rule("Delete one cell: the corpus never says feed the dog") print("deleted: %s" % ", ".join("%s %s" % (c, w) for w, c in HELD_OUT)) print("dog keeps the dog sleeps. The feed cell is removed from the loss,") print("so no gradient of any kind reaches it.") print() cells = held_out_cells() i = cells[0][0] j = CONTEXTS.index("feed") for name, hidden in [("no hidden layer, a lookup", 0), ("hidden layer of 2", 2)]: E, W, b = train(mask=cells, hidden=hidden) rule("P(context | word), %s" % name) print("%-8s %s" % ("", " ".join("%7s" % c for c in CONTEXTS))) for k, w in enumerate(WORDS): p = predict(E, W, b, k) flag = " <- the deleted cell" if k == i else "" print("%-8s %s%s" % (w, " ".join("%7.2f" % v for v in p), flag)) print() print("P(feed | dog) = %.2f" % predict(E, W, b, i)[j]) print() print("The lookup has one free weight per word per context. Delete the") print("cell and that weight never moves, so the answer is whatever the") print("bias says. The model has nothing to tell you.") print("The hidden layer has no weight for that cell. It has a place for") print("dog, and four facts survive to fix it. The dog sleeps, and a dog is") print("never ridden, driven or parked. One corner of the plane fits all") print("four, and cat and horse are already in it. feed came back for free.") print() print("Put (\"dog\", \"sleeps\") in HELD_OUT too, so that no sentence about") print("dogs survives at all. The answer only falls to 0.88. Absences place") print("a word as surely as sentences do.") def main(): ap = argparse.ArgumentParser(description=__doc__, formatter_class=argparse.RawDescriptionHelpFormatter) ap.add_argument("--input", action="store_true", help="the one-hot input space") ap.add_argument("--hand", action="store_true", help="the hand-set embedding") ap.add_argument("--train", action="store_true", help="learn the embedding") ap.add_argument("--holdout", action="store_true", help="the generalisation test") args = ap.parse_args() chosen = [args.input, args.hand, args.train, args.holdout] run_all = not any(chosen) if run_all or args.input: show_input_space() if run_all or args.hand: show_hand() if run_all or args.train: show_train() if run_all or args.holdout: show_holdout() if __name__ == "__main__": main()