Chapter 6b: The Unsupervised Basis Encoder

In Chapter 6 we reviewed the kT-RAM supervised classifier routine. Read every lane, drive the labeled lane’s weights high, drive the confident-wrong weights low, and make use of the regularizing ‘FF-RZ’ instruction for the rest. The result was equivalent to established methods in machine learning like logistic regression.

What happens if you take the label away?

Show the lanes an example AAT pattern and it reads back a set of voltages, one per lane, and the loudest lane wins. The winner becomes its own target: reward the lane that won, depress the confident losers, and repeat. This is the same routine from last chapter with one substitution.

Run that over a set of AATs with no labels and each lane drifts toward a prototype, a little pattern it comes to represent. The lanes turn into a codebook: a small dictionary of patterns, where the “code” for any input is just the index of the lane that won with the highest activation. This is old and well understood and comes with a number of names: competitive learning, online vector quantization, and learning a dictionary are a few of them. Sounds simple, but there is a catch. A plain winner-take-all competition will eat itself unless we construct constraints that limit the ability of the rich to eat everybody else.

pip install "git+https://github.com/knowm/ktram-neural-core.git#subdirectory=python"

The code is in examples/basis-encoder in the repo.

Rich get richer#

Picture the first few example AATs. Some neural lane, by luck of its starting state, reads a hair louder than the rest and randomly wins. We reward it, which makes it read louder still on anything similar, which biases it to win the next round too, and the one after that, and so on. It is a rich-get-richer loop, where an early luck of circumstance compounds into a monopoly. A lane that never wins is never rewarded. Run it long enough and a bank of sixty-four lanes collapses to two or three or even just one that answer for everything. The diverse codebook you wanted, a collection of unique prototypes, degenerates into a monopoly that can only say one thing. I call it the null state. A pure rich-get-richer collapses in short time to the degenerate null state.

We must find a way to reward the winners without causing total system collapse. On the one hand, rewarding a winner lets that lane establish its proto-type, to understand what it represents. On the other hand, it is the competition between multiple lanes, each representative of ‘synaptic territory’, that leads to decision boundaries that maximize the support vectors between patterns. We must allow winners to win, but somehow limit the positive feedback spiral that ends with the null state. We will do this via exclusion.

Exclusion (of the rich)#

What gets excluded is the winner. A lane that has already won once during a defined cycle period steps aside and takes no second reward until the others have had their turn. Without exclusion a single lane wins everything and keeps every other lane out of the codebook for good. A “cycle” is simply a defined period of time, measured in input patterns seen, plus one addition discussed below.

That one rule keeps the rich in check, and allows a codebook to form. The early leader still wins its first example, but then it is benched. The next reward goes instead to whoever reads highest among the lanes that haven’t won yet, which spreads the learning across the whole bank. In hardware this mechanism is one bit per lane: won this cycle, or not.

Write $\mathcal{L}$ for the lanes in the group, $y_\ell$ for the sub-threshold read of lane $\ell$, and $W \subseteq \mathcal{L}$ for the set of lanes that have already won this cycle. The read winner is $w = \arg\max_{\ell \in \mathcal{L}} y_\ell$, and exclusion gates the reward on membership in $W$: feedback is issued when $w \notin W$, and withheld when $w \in W$.

Recruitment (of the poor)#

Exclusion keeps the rich in check, but it doesn’t guarantee that a lane which started in a bad spot ever gets going. Such a lane can lose every read forever, sit at its initial state, and contribute nothing. The same random chance initialization that gifted the rich with their privileged start can work in the opposite way, preventing any lane from ever being a winner. So a second rule is needed that pushes from the other side.

When a long stretch of updates goes by without the cycle completing, we stop waiting and force it. Reward the highest-reading lane among those that haven’t won yet, even though it did not win this round. Gather winners for a while, rewarding them all just once, and if some defined cycle time has passed then abandon the wait and simply start recruiting the lanes that have yet to win anything. This procedure drags idle lanes into service so all lanes become utilized and we form a diverse basis set or dictionary. In hardware this is simply a counter.

Recruitment reads the same set $W$ the other way. Let $n$ count the updates since the cycle last cleared and let $G$ be the gather_abandon threshold. Once $n \ge G$ with lanes still unwon, the group stops waiting and force-rewards the highest-reading lane among those that have not won yet. Lane $r$ takes an FF+RH reward and joins $W$, whether or not it won the read.

The cycle#

Both the exclusion and recruitment rules utilize the same bookkeeping. Each lane carries one bit: has the lane won this cycle? When every lane has won at least once, the cycle is considered complete. The bits are cleared and the competition starts over. The bit is what exclusion checks before providing a reward, and the number of bits set is what recruitment watches to decide if the round has stalled. The transition between exclusion and recruit occurs on a cycle time determined by a counter and a threshold we call gather_abandon, i.e., when we abandon the strategy of gathering winners. When the counter for the round hits the gather_abandon threshold, we start the process of force recruitment. When all lanes have become winners, the cycle starts over.

The routine#

Let’s put the pieces together. We start by performing low-voltage read, FFLV, over all the lanes. The winner is the lane with the largest $y$, which is what we return as the output. We gate the reward by our two mechanisms. That’s it.

def adapt(x):                        # one unsupervised update on input AAT x
    y = [read(x, lane, FFLV) for lane in group]   # 1. decide — sub-threshold, disturbs nothing
    winner = argmax(y)

    if not won_this_cycle(winner):   # 2. exclusion
        correct(x, winner, RH)       #      reward the winner       — FF then RH (up)
        for lane in group:           #      depress the fired losers — FF then RL (down)
            if lane != winner and y[lane] > 0:
                correct(x, lane, RL)

    if cycle_stalled():              # 3. counter>gather_abandon, start recruitment
        r = highest_reading_unwon_lane(y)
        correct(x, r, RH)            #      pull an idle lane in     — FF then RH (up)

    mark(winner); tick_cycle()       # 4. one bit per lane; clear the cycle when all have won

def correct(x, lane, reverse):       # the ONLY place a forward instruction is issued
    evaluate(x, FF, lane)            #   forward read at full voltage — this one adapts
    evaluate(x, reverse, lane)       #   its paired reverse — no path ever leaves an FF unpaired

FFLV is the sub-threshold read. FF is the same read at full voltage, and this read will decay the conductances slightly. RH and RL are the reverse instructions for driving the lane high and low, respectively. Review the kT-RAM instruction set in Chapter 4b. Every forward instruction must be paired with a reverse instruction, so a correction is FF+RH (the winner) or FF+RL (the confident runner-ups). It is the same instruction set as the supervised classifier’s FF → RH/RL/RF, minus the true-negative RF case. This basis encoder touches only the lanes that spoke up and leaves the rest of the bank alone. There are many possible kT-RAM routines. This is one that works and that we can measure, and it is not the definitive basis encoder. Other routines will trade differently between codebook quality, instruction count, and how much bookkeeping the hardware carries. On sixty-four lanes, most get no instruction at all on a given update.

Forming & Sharpening#

Run the cycle above and every lane is kept in play and pulled toward some prototype. This is good, but recruitment can cause issues by propping up lanes that the data doesn’t support. For example, if we are asking 64 lanes to learn a basis set and only 32 patterns actually exist, then the codebook will ‘smear’: a couple of lanes end up answering for two different things at once. The cost shows up in purity, and it grows with the mismatch. Holding recruitment on for the whole run, 64 lanes score 0.88 on a source of 48 patterns, 0.84 on 32, and 0.75 on 16.

To resolve the smearing, we can run the training in two phases.

First, we form using the cycle routine above. Recruitment is on and the whole bank populates, a full and varied set of prototypes develops, and nothing gets starved before it has a chance to specialize. But once we get to this point, we need to let the lanes ‘sharpen’. Partway through we turn recruitment off. Now nothing props up a lane that has quit winning. When we reach the end of the cycle (counter>gather_abandon), rather than forcing recruitment we simply reset the cycle. The lanes that keep winning get crisper. The ones that were only kept in the round by recruitment stop being rewarded and fade out. The codebook prunes itself down to what the data actually supports.

You can watch it happen below. Here is one bank run on binarized Fashion MNIST images, with sixteen lanes and no labels. You can see the forming and then the sharpening right at the very end.

Does it work?#

Two questions to focus on now: does the codebook come out clean? Is codebook good for anything?

“Clean” is a measurable quantity because we know the true prototypes that generated the data on a synthetic source. So we can ask what fraction of the true prototypes got claimed by a lane, which we call coverage, as well as how single-minded each lane stayed, which we call purity.

Both numbers come from one tally table. Freeze the group and run it over a batch of samples whose true source pattern we know. Each time a lane wins a sample, add one to the cell for that lane and that pattern. The result is a table with one row per lane and one column per true pattern, and the cell $M_{\ell g}$ is the number of times lane $\ell$ won a sample that came from pattern $g$. A perfect codebook has one bright cell per row, each in a different column. That is the diagonal in the figure below.

Purity is the fraction of a lane’s wins that came from its single most common pattern, averaged over the lanes that won anything. Coverage is the fraction of the true patterns that at least one lane claims as its most common win.

If two lanes both claim the same pattern, it counts once. If no lane claims a pattern, that pattern is missing from the codebook. So a group that merges several patterns onto one lane, or lets patterns go unclaimed, reads as low coverage, while a lane that answers for two patterns at once reads as low purity. A third number is simpler still: the fraction of lanes that won anything at all is utilization.

With both exclusion and recruitment on, coverage and purity run high. Knock exclusion out and only one winner remains, the degenerate null state. Knock recruitment out and fewer than half the lanes ever win a read, so coverage drops from 0.94 to 0.60. Every pattern still finds a winner, so what breaks is the one-to-one recovery. Thirty survivors therefore cap coverage at thirty of the forty-eight patterns. Exclusion protects purity while recruitment protects coverage. Recruitment buys coverage and costs a little purity, so we keep it on to fill the bank and give all lanes a change, then take it off to refine and sharpen.

On the synthetic source the code is also markedly more separable than the raw input. A single linear read climbs from about 0.81 on the raw signal to 0.95 on the frozen basis code. That what learning a good representation buys you.

Patch Codebook#

Rather than the whole image, we can learn a codebook over sub-patches of the images of Fashion MNIST, which we show below.

Each tile is one lane’s prototype pattern. These are the same things the sparse-coding folks have been extracting from natural images for thirty years: oriented edges, bars, corners, little scraps of texture.

One group covers one 7×7 tile. A 28×28 image takes sixteen of them, each with its own sixty-four lanes and its own codebook. Read all sixteen, keep the winner from each, and the image comes back as sixteen integers. That tuple is the image’s AAT.

Sixteen integers now stand in for 784 pixels, so it is worth asking what survives the squeeze. A lane can read the garment’s class off the code, and a bank of lanes can rebuild the picture from it. Both are the routine we already have, pointed at a different target, and the second one is what closes the loop into a generator.

A simple kT-RAM auto-encoder-decoder-classifier network#

Everything until now has been one group of lanes at a time. Lets build and train our first “multi-module” kT-RAM network. Two of them you have already met: the supervised classifier from Chapter 6 and the basis group from the top of this chapter. The new part is how we wire them up.

Topology#

Start with a Fashion MNIST image of 28×28 pixels. We threshold every image at its own mean gray level, so each pixel is either white (1) or no black (0) and the whole picture is 784 bits. Then we cut it into a 4×4 grid of sixteen 7×7 tiles that do not overlap. Tile 0 is the top-left corner, tile 3 is the top-right, tile 15 is the bottom-right.

The encoder is sixteen basis groups, one per tile. Each one is a 64-lane WTA group from earlier in this chapter. Group $g$ sees only tile $g$, and never anything else. Its input AAT has 49 spaces, one per pixel in the tile, and each space has two addresses: white or black. Sixteen groups give sixteen integers, and that 16-tuple is the image’s code. It is itself an AAT, sixteen spaces of 64 addresses each. 784 bits go in and sixteen integers come out.

The decoder takes the encoded 16-integer AAT and outputs predicted pixel values. It is one kT-RAM core of 1,568 lanes, two per pixel: one lane stands for white (1) and the other for black (0). Every decoder lane reads the full sixteen-space AAT, so it holds $16 \times 64 = 1{,}024$ synapses. Two such lanes form a WTA group that predicts the pixel value, 0 or 1. Because both of a pixel’s lanes read every tile’s code at once, a change in one tile’s winner can propagate all over the picture.

The label read-out is ten lanes, one per Fashion class, reading the same sixteen-space AAT the decoder reads, 1,024 pairs per lane. Just like the decoder, this is just an instance of the Chapter 6 classifier.

This network holds 1.7M differential pair synapses, and the decoder owns nearly all of them. The encoder is ~100k synapses and the read-out is ~10k synapses.

Training#

The encoder trains first unsupervised. Each group runs the adapt loop from above over 12,000 training images, with gather_abandon = 96. Then the encoder is frozen.

Next we run the frozen encoder over 8,000 training images once and keep the 8,000 AAT codes. The decoder and the label read-out both train on those codes. The decoder’s target for pixel $p$ is the true bit of pixel $p$ in the training image. Four passes over the 8,000 codes. The read-out’s target is the class label.

Inference#

Once frozen, the entire network operates on FFLV reads. An image becomes a sixteen integer AAT representation. The AAT becomes 1,568 decoder reads and 784 bits, and ten read-out reads and a label.

Closing the loop#

The decoder’s output is a 784-bit image, which is exactly what the encoder takes as input. So we feed it back to itself. The state of the machine is an image. One step is encode then decode. With no read noise every read is a deterministic map from images to images, and the picture falls into an image that encodes and decodes back to itself within a few steps.

The temperature is the read-noise gain on the encoder’s FFLV read. Every one of the 1,024 encoder lanes draws its own noise on every read, at the width $\sigma(V)$ from the read-noise chapter, and the group’s winner is whichever lane reads highest after the added noise. The decoder and the read-out stay sharp. Encoder noise is the one knob the widget exposes.

Turning up the temperature#

Start with an image, encode it to a code, decode the code back to an image, encode that, and around again over and over. At low noise the loop quickly settles onto an image that encodes and decodes back to itself. That is a fixed point attractor: a clean garment the encoder and decoder agree on. Start it from almost anything and it falls into one.

A kT-RAM read is not silent. It carries the kT-bit’s own read noise, the thermal noise on the sense line, and we have a dial for it: the read voltage. Turn the read voltage down and the same read gets louder with noise. The winner is sampled, weighted toward the loud lanes but free to grab a near-runner-up when the noise tips it over. That noise width $\sigma(V)$ is our temperature, the thermal-plus-flicker noise introduced from Chapter 3b. At zero noise the loop settles and holds a garment attractor. Turn it up and the winner starts to wander, the code drifts, the decoded image morphs, etc. A boot morphing into a sneaker, a coat morphing into dress. Turn it back down and it snaps into the nearest clean attractor.

So run it yourself.

Drag the temperature up and watch it explore. Drop it and watch it settle. Click any patch to open its codebook and see the sixty-four features that patch was choosing between, the current winner boxed. Click ‘Codebook’ to get back to the generated image. The header classifies what you are looking at.

What this maps to#

This whole series has one job: map methods of machine learning to kT-RAM neural lanes. We are typically not reinventing any of these algorithms or techniques. Rather, we are learning what the hardware is capable of, one capability at a time.

The winner-take-all update is called competitive learning. The codebook of prototypes is a vector quantizer. Exclusion is a hard, cycle-scoped version of DeSieno’s conscience — the 1988 trick of penalizing a unit that wins too often so the rest get a turn. Recruitment is the online form of the dead-unit reinitialization k-means does when a cluster empties. The learned patch features are the sparse-coding dictionary, without the L1 penalty or the gradient descent. And the encoder-and-decoder loop — code in, image out — is an auto-encoder one of the oldest unsupervised architectures there is.

The basis encoder takes its place next to the classifier as a second L1 module, a named and reusable routine that can be executed over kT-RAM neural lanes. Memory, logic, a supervised classifier, and now an auto-encoder.

Sneak peek#

This chapter’s generator is deliberately small: binary pixels, sixteen integers, one encoder, one decoder, and one classifier. I could not leave it there so I spent a weekend working on larger full-bit-precision kT-RAM image generation networks, and the image below are samples from one. I’ll write it up in a future chapter once we lay down some chapters on more sophisticated methods of AAT encoding. Its also a tangent to my stated goal of neural network assimilation, so I cant get too distracted!

Next: Chapter 7: The AAT Codec