The prediction zoo · Close Enough

1Prediction is conditioning

The per-coordinate model on 6.2 Everything is a probability model codes $x$ with $q(x)$ . A predictor replaces that with $q(x \mid \text{context})$ : a narrower curve, centred on a better guess.

How much narrower? If the context has correlation $\rho$ with the coordinate, the best linear guess leaves a spread of

\kres{\sigma_{\text{after}}} \;=\; \sigma\,\sqrt{1-\rho^2} \qquad\Longrightarrow\qquad \text{saving} \;=\; \tfrac12\log_2\frac{1}{1-\rho^2}\ \text{bits per coordinate}

The energy ratio $1/(1-\rho^2)$ is the classical prediction gain.

Fig 6.5.1What a known neighbour saves

Slide ρ The wide curve is a coordinate on its own; the narrow one is the same coordinate once a correlated value is known. The saving in bits is the log of the ratio of widths.

2The zoo

Anything the decoder has before it decodes $x_t$ can be context.

Predictor	Context	Guess for $x_t$	Parameters	Needs order?
The mean	nothing	$\mu$	$d$	no
Previous vector (delta coding)	$x_{t-1}$	$\beta\,x_{t-1}$	1	yes
Linear, full matrix	$x_{t-1}$	$A\,x_{t-1}$	$d^2$	yes
Earlier coordinates (triangular)	$x_{t,1..j-1}$	row $j$ of $L$	$d^2/2$	no
A coarse code (side information)	an RQ or PCA code stored first	its reconstruction	codebooks	no
Nearest stored neighbour	the index	a similar vector already decoded	none	a graph
The query	the client’s own query vector	$a\,q$	1	no (wire only)

Two of these are free in the sense that they send nothing extra: the previous vector and the earlier coordinates. The coarse code costs bits up front and gets its own page.

3Measured: the previous window

Consecutive windows of a book have correlation 0.63 after centring. The formula predicts a saving of 0.37 bits per coordinate, or 141 bits per vector.

2,477 bits: a bell curve per coordinate
2,344 bits: predict $\beta\,x_{t-1}$ first (one parameter)
2,339 bits: predict $A\,x_{t-1}$ with a full 384 × 384 matrix

The measured saving is 133 bits, as predicted. And 147,000 extra parameters buy 5 more bits: the relationship between neighbouring windows really is “the same vector, faded”.

4The two free predictors stack

Previous-window prediction removes what the last passage explains. Triangular prediction (6.4 The transform zoo) removes what the other coordinates explain. They are about different things, so:

5The rule that changes: open or closed loop

In lossy predictive coding the decoder only has reconstructions, so the encoder must predict from the reconstruction too:

Fig 6.5.2Quantizing prediction errors

The lossy case, in two dimensions The same 4 bits per step either way: a 16-entry codebook for the vectors themselves, or for the prediction errors. Yellow: the true path. Mint: the reconstruction. Red: the error. Diamonds are keyframes, coded independently every 16 steps. Slide ρ down to 0.5 and the advantage evaporates.

In lossless coding the distinction disappears: the decoder has the previous vector exactly, so predicting from the original is predicting from the reconstruction. There is no drift to manage. What remains is a different discipline:

6Keyframes buy random access

A chain of predictions must be decoded from its start. Break the chain every $K$ vectors with a keyframe (a vector coded with no temporal context) and you can start decoding at any keyframe.

The price is small, because a keyframe still gets the triangular predictor:

Keyframe every	Extra bits per vector	Worst-case vectors decoded to reach one
16	5.4	16
64	1.3	64
never	0	the whole book

At 1.3 bits per vector there is no reason to economise on keyframes.

7Predict only when it helps

Video encoders try each block both ways and keep the better, paying a flag bit. The same mode decision applies here: at a chapter break the previous window is a bad predictor, and coding the vector independently is cheaper. In the lossy experiment of 4.8 Measured on real embeddings the choice mattered a great deal (64% of windows chose prediction). In lossless coding it is a smaller refinement, because a bad prediction costs a few bits where a lossy codec would lose accuracy.