Not Knowing Costs 85 Bits

In the last post a twenty-line counting model got within a hair of the entropy floor on random text, beating gzip, bzip2, xz and zstd by miles. But only because I told it how many previous letters matter. Give it too little memory and it was 50–110% above the floor. Give it too much and it was still 11% above after a million letters.

The fix I ended on was to blend counting models with different amounts of memory and let the data pick. There's a classic way to do that properly, context tree weighting (Willems, Shtarkov and Tjalkens, 1995), and it comes with a strong promise: it does almost as well as if you'd known the right memory all along, and the "almost" is a fixed number of bits. Not a percentage, not something that grows with the text. A fixed cost, paid once.

I wanted to see that number. It turns out you can predict it to the bit.

How it blends

Picture every context the model could use as a node in a tree. The root is "no memory". Its four children are "the last symbol was a", "…was b", and so on. Their children look two symbols back, down to some maximum depth D. Every node keeps its own counting model of what comes next in that context.

Each node then hedges: its probability for the text it has seen is half "my own counts are the right model here" plus half "my children's are, multiplied together". The leaves at depth D can't split, so they just use their counts. Unfold that recursion and the root ends up averaging over every possible shape of tree, from "no memory at all" to "full memory D everywhere", with each shape weighted by 2^{−(its description length)}, where describing a tree costs one bit per node: "split here" or "stop here". The nodes at depth D are free, because there's nothing to decide.

That gives a sharp prediction. Once the data has made the right tree overwhelmingly likely, the mixture is dominated by that one tree, and the cost of not knowing it should be exactly its description length. Not roughly. To the bit.

It's also cheap: each new symbol updates one path from root to leaf, D + 1 nodes. My plain JavaScript version does about 6 million symbols a second at depth 6.

The toll, predicted and measured

I reused the six sources from last time, three samples of 16 million symbols each, and ran CTW with a range of maximum depths. Each row compares it with a counting model that was told the right memory, on the same text.

Total extra bits CTW spends compared with a counting model that knows the memory, after 64 thousand, 1 million and 16 million symbols. Average of three samples; at 1M and 16M the three agree to within 0.01 bits.

A fair coin compressed by a model allowed to look 16 flips back costs exactly one bit more than a model told "no memory": the bit that says "don't split the root". On "4 symbols, memory 3", the tree is full to depth 3: 1 + 4 + 16 = 21 splits, each a bit. If depth 3 is also the maximum, the 64 leaves are free, and the toll is 21 bits. Allow more depth and each of those 64 leaves now has to say "stop", one bit each: 85. Allowing depth 10 instead of 4 costs nothing more, because the model never goes below the leaves once it's sure they're leaves.

Before checking these numbers I made sure the code was right: a straightforward recursive version, computed from the final counts, gives the same total as the streaming one to within a millionth of a bit, and the version on this page matches the one I ran the big batch with exactly.

Eighty-five bits on 16 million symbols is nothing (0.0004%). On short text it isn't: at 4,096 symbols, the counting model told "memory 3" is 7.9% above the floor, CTW limited to depth 3 is 8.4%, and CTW allowed depth 10 is 9.4%. The toll is fixed, so it matters exactly when the text is short. But compare that with the last post's table, where the wrong fixed memory on this source cost 46–61%.

When the memory varies

Every source so far has the same memory in every context, which is the easy case for picking one fixed memory too. Real text isn't like that: after "q" you need one letter of memory to predict "u"; elsewhere you need several. So I made two sources where the memory itself varies. Starting from "no memory", each context looks one symbol further back with probability 0.4 or 0.5, up to six symbols, and each final context gets its own random odds. The first one ended up with 70 contexts, from one to six symbols long; the second with 61. The demo's "variable memory" button builds one the same way, with 58.

Now no fixed memory is right. Too short and it misses the long contexts; long enough for the long contexts and it splits all the short ones into thousands of pieces that each have to be learned separately:

The 70-context source: above the floor, average of three samples. Bold is the best fixed memory at that length. CTW with maximum depth 6. xz at its strongest setting is 17.7% above the floor at 16M.

The best fixed memory keeps changing as the text grows, from 2 to 3 to 5, and it falls further behind CTW the longer the text gets: about 2 times further from the floor at 4k symbols, 4 times at 64k, 9 times at 1M, 20 times at 16M. Even at 16 million symbols, memory 6, the deepest the source actually uses, still loses to memory 5: it has 4,096 contexts to learn, most of them copies of the same few. CTW, meanwhile, tracks the model that was handed the tree from the start: its gap is 17% bigger at 4k symbols and 5% bigger at 16M. The second source tells the same story.

The toll isn't paid all at once

Here the prediction misses, in an interesting way. Describing the 70-context tree costs 65 bits with maximum depth 6. The measured toll is 36 bits at 64k symbols, 49 at 1M, and 56 at 16M. It's still climbing.

Less than the prediction means CTW is betting on a smaller tree than the true one, and doing well by it. Looking at which of the 23 splits in the true tree CTW prefers at each length (on one sample) shows what's going on: it's all about how often a context comes up.

One sample of the 70-context source, checked each time the text grew fourfold. "Has them from" is the first length after which CTW prefers that split at every later check.

A split gets adopted after its context has been seen anywhere from a handful of times to a few hundred, depending on how different the children's odds are. Before that, lumping the children together is the better bet: one counting model learns faster than four, and the price of being slightly wrong about rare contexts is smaller than the price of learning four sets of odds from a handful of examples. CTW doesn't need a rule for this. The halving at every node makes the trade automatically, and it keeps making it as the evidence comes in.

You can watch it in the demo. Early on, the tree is mostly orange: CTW stops short almost everywhere. The orange cells turn blue as each context collects enough evidence, the common ones first, and the toll creeps up toward the price of the whole tree. Turn the maximum depth below the source's deepest context and the toll keeps growing instead, because now CTW can never describe the tree exactly.

What I take from it

The last post ended with "knowing the right amount of context is most of the battle". CTW turns that battle into a bill you can read off in advance: one bit per decision about the tree, paid once. On the fixed-memory sources it's paid in full by a few tens of thousands of symbols, exactly as predicted. On the variable ones it's paid gradually, context by context, as each one earns its keep.

One caution: these sources are exactly the kind of thing CTW is built for. They're generated by a context tree, and CTW's mixture includes the right tree. Real text has long exact repeats, which LZ-style compressors like xz exploit and a context tree can only approximate. The strongest practical compressors mix both kinds of model. But as a demonstration that "let the data pick the memory" can be done with a known, fixed, small price, it's hard to beat.

The sources and the model are in one small file, the same code as the demo.