LabTrained in brainfuck

Trained in brainfuck

The chat programs on this site run models that were trained elsewhere, on graphics cards. brnfck-train-names-bigram-756, brnfck-train-names-mlp-7k and brnfck-train-names-attn-10k learn themselves. Each starts from random numbers, reads a list of 1,402 names through its comma command, and learns from it, one step after another: it guesses the next letter, measures how wrong it was, and moves every weight a little. When it is done, it prints a second brainfuck program, its child, which holds what it learned and makes up new names. Another kind prints itself, with what it learned written in, so that the next program trains on. brnfck-train-shakespeare-attn-55k, larger, learned Shakespeare overnight.

Train one here

Pick a program and press Train. Your browser builds the training program from its generator, which takes a fraction of a second, and runs it in the same brainfuck runtime as the chatbot. The program reads the names, twenty times over in a new order each time for the two larger ones, 32 letters per step. After every step it prints its loss: how surprised it was by those 32 letters, in nats. Each line it prints is checked against the line the plain JavaScript version of the same training printed.

Program
 
Step
 
Loss
 
Time
 
Equal to the reference
 

Loss per step

Weights on the tape

 

 

Grey dots: the loss of every step as the plain JavaScript version of the training printed it (compiler/train/reference.js); the line is the average of 100 steps. A run here draws its own dots over them; they land exactly on the grey ones. The weights: every cell of the tape that holds a weight, as a pixel, orange above zero and blue below, row by row as the program stores them. During a run they are read from the running program; otherwise from the same training in JavaScript, at the step on the slider.

Three networks

All three learn the same thing: given the letters of a name so far, the next letter, or the end of the name. They differ in how far back they look.

brnfck-names-bigram-756
Looks one letter back. A table of 27 by 27 numbers: for every letter, how likely each next letter is. 756 weights, 902 steps.
brnfck-names-mlp-7k
Looks three letters back. 64 hidden units each add up a number for each of the three letters, squash the sum with tanh, and pass it on to the 27 possible next letters. 7,003 weights, 6,018 steps.
brnfck-names-attn-10k
The same, plus one attention head over the last eight letters. The newest letter asks a question (a query of 16 numbers); every earlier position offers a key and a value; the dot products of the query with the keys, through a softmax, say how much of each value to take. 10,251 weights.

Training is the same loop for all three, 32 letters per step: for every letter, run the network forward, compute the loss, and go back through the network to find out how each weight should change (backpropagation). After 32 letters, move every weight, with momentum: each weight keeps 7/8 of its last move.

Learning in whole numbers

A brainfuck cell holds a whole number, here of 32 bits. So every number of the training is a whole number with an agreed scale: a weight of 0.25 is stored as 4096, in 16384ths. The tanh, the exponential of the softmax, 1 divided by a sum and the logarithm of the loss come from tables. Every division is a shift with a fixed way of rounding. The learning rate is a shift too: the error of each guess is divided by a power of two before it goes back through the network, 16 in the two larger programs.

Because nothing in it is a floating-point number, there is nothing to round differently on another computer. Any brainfuck interpreter with 32-bit cells, on any machine, ends with the same weights, to the last bit. That is also how the programs are checked: a plain JavaScript version of the same arithmetic must print the same lines and end with the same numbers.

The tape is laid out for brainfuck's one way of reaching memory, moving left and right. Each hidden unit has a frame of cells with all its weights, 145 slots of 13 cells for the attention program. The forward pass walks from frame to frame with one shared piece of code, carrying the letters and the sums along. The backward pass walks back.

The program to scale

Every training program is one line of brainfuck. Below, the whole program as a field of pixels, in the order of its characters, each part in its colour. Most of it is code that runs once per letter or once per step; the largest single part is the child, which the program prints character by character at the end. Click to zoom in, down to the characters themselves.

 

    The program is built in your browser by the same generator that writes it on the command line (compiler/train/gen.js), with a mark where each part begins. A pixel is a run of characters; the zoom goes down to one character per square, where the colours are those of the eight commands. The Program map shows the four training programs as well, folded into a square, with places and a tour.

    Where the attention looks

    Type the start of a name. The attention head of brnfck-names-attn-10k weighs the last eight letters, and the bars show how much of each it takes in to guess the next letter. Nobody told it where to look: it found out during training. It often looks at the first letters of the name, which say much about how it goes on.

    Its guesses for the next letter

     

    Computed in your browser exactly as the child program computes it: the trained weights at the child's scale (compiler/train/reference.js, forward), whole numbers throughout. A dot is a place before the name starts. The guesses are the chances the child draws its next letter with; the end of a name is shown as ↵.

    Names they made up

    Each child program prints 30 names, drawn letter by letter with its own random numbers. The more a network sees of a name, the more the names it makes up sound like names. Names that are in the list it learned from are marked.

    It prints its next generation

    Brainfuck has no files, and nothing on the tape outlives the run. A program that has learned something can keep it only one way: by printing it, as a new program. The training programs above print a child that can only make up names. A second kind prints itself: the same training program, with the weights it ended with, their momentum, its step count and the last letters it read written into it. Run that program on more names and it trains on from where the last one stopped, then prints the next. A generation that is fed nothing prints the child.

    Below, brnfck-train-names-bigram-756 in 20 generations: each trains on a twentieth of the names and prints the next. The table is read from the programs themselves. Every generation, fed nothing, prints a child, and the child holds each weight as a run of + or −.

     

    Its child, fed nothing, writes

    Every state is a program that the one before it printed: gen1 to gen20 come from tools/site-generations.js, which runs each generation in the WebAssembly runtime and checks every loss line and every printed program against compiler/train/reference.js; the child of gen20 equals the child of one run over all the names. Left, the chance of each next letter after each letter, as the child computes it; right, the run the child holds for the end of a name after each letter, in characters.

    What a generation is made of, here gen1 and gen2 of brnfck-train-names-attn-10k, to scale. Most of it is the body written out as data: that is what lets the body print itself, character for character, behind the new weights.

    The parts measured in the printed programs themselves; the first characters of each part as they stand in gen1 (the loss lines: gen2). The loss lines and the two walks along the tape are drawn at least 3 pixels wide.

    brnfck-train-names-attn-10k in 20 generations, and the names the child of each one writes. On the right, the loss of the steps that the generation before it trained.

    Printed by each generation's child when it ran in the WebAssembly runtime: the first ten of its 30 names, cut at 18 letters. The child of gen0 has random weights.

    How it was checked

    node tools/train.js builds the three training programs, runs each through the WebAssembly runtime on the names, and compares it with compiler/train/reference.js, the same training in plain JavaScript whole numbers:

    That shows the program does what the reference does. That the reference learns the right thing was checked against a version of the attention network in floating point: for each group of weights, the change the whole-number training makes points the same way as the true gradient, with a cosine of 0.9996 or more and a size within 4%. Each building block of the programs, from multiplying two cells to printing a number, is tested on its own in compiler/train/test-kernels.js.

    What it costs

    One letter backThree letters backWith attention
    Weights7567,00310,251
    Training program1,246,022 characters2,956,550 characters9,023,355 characters
    Child program347,284 characters1,373,979 characters3,510,735 characters
    Tape11,774 cells95,572 cells140,867 cells
    Steps of 32 letters9026,0186,018
    Training time0.5 s29.1 s80.0 s
    Per step0.54 ms4.84 ms13.3 ms
    Loss, last 500 steps2.452.001.91

    Measured with Node.js 24 on the computer that built the chat programs (8 cores), one run each, in the WebAssembly runtime of this site; logs in compiler/train/out/. The loss is the average of the loss lines of the last 500 steps (the last 75 for one letter back), in nats per letter. A run in your browser takes about as long.

    Shakespeare, overnight

    The same kind of network, made larger, learned Shakespeare. brnfck-shakespeare-attn-55k looks at the last 16 characters with its attention and at the last 4 with 128 hidden units, and has 54,513 weights. Its training program, 29 million characters of brainfuck, read the plays of Tiny Shakespeare through its comma command on one core of a home computer, in passes of a million characters, about three quarters of an hour each. It learns from the first 90% of the text. The last 10% it never reads; that part measures how well it does on text it has not seen. The Program map shows its training program, all of it, down to single commands.

    Passes
     
    Characters read
     
    Time
     
    Loss on unseen text
     
    Equal to the reference
     

     

    The line: the loss the training program printed, in nats per character, the mean of the steps between two progress lines of the run (about every two minutes); the first 2,000 steps from the plain JavaScript version of the training, in groups of 20, which prints the same lines. The dots: the loss on the 10% kept apart, after each pass. The dashed lines are what simpler guesses score on that part: every character equally likely, how often each character comes, and the character before only. The steps are on a square-root scale, so that the first minutes, when it learns the most, are wide enough to see. Below it, the loss on the unseen text alone, after each pass, on a scale that fits those numbers. Click to pick a pass.

    What each pass wrote

    After every pass the training program printed its child: a second brainfuck program of about 12 million characters, the weights as runs of plus and minus, then an engine that writes 40 lines. Pass 0 is the child of the random weights it started from.

     

    Run a child here

    Your browser builds the child of the pass above from its weights, compiles the brainfuck to WebAssembly and runs it. With seed 1021 and 40 lines it is the program the training printed, and it must write the same text, character for character. Any other seed draws other characters from the same chances.

    Child of pass
     
    Program
     
    Built and compiled
     
    Writing
     
    Same as overnight
     

     

    Where it looks

    Type the start of a line. The child of the pass above weighs the last 16 characters; the bars show how much of each it takes in to guess the next one, and below are its guesses. Take its guess adds its first guess and goes on from there.

    Its guesses for the next character

     

    Computed in your browser exactly as the child program computes it: its weights, read from the child the training printed, through the same whole-number arithmetic (compiler/train/reference.js, forward). The bars are drawn against the largest; the numbers below them are per cent. A space is shown as ·, the end of a line as ↵, and a place before the text starts as an end of line.

    Notes and sources