Codebook Quantisation

Every other page in this section carries one sentence, Dr. Alvarez didn’t expect the low-cost re-analysis. It is there because it breaks things, and none of the things it breaks are things this method can meet. The method here is vector quantisation, and it reads vectors rather than writing, so a sentence would have to be turned into vectors before it arrived, and every interesting decision would then have been taken by whatever did the turning. So this page carries a picture instead, and says so plainly rather than pretending the sentence still fits.

The picture is sixteen pixels down and sixteen across, each pixel a brightness between 0 and 1. That is 256 numbers, and we will cut them into 128 pieces of two, each piece being a pixel and the pixel to its right. Two numbers per piece is a small piece by the standards of anything that codes real images, where sixteen or sixty-four is ordinary, and it is chosen here because a piece of two numbers is a point in the plane and can therefore be drawn on a page and checked with a pencil.

Four pictures run through the whole page, and they are not four illustrations of one thing. Each one makes the same measurement come out differently, and the differences are where most of the argument lives. The photograph is smooth, so a pixel and the pixel beside it are nearly equal almost everywhere. The poster is four flat bands of tone.

The printed chart is hard-edged stripes. The speckled square has every pixel drawn independently of every other, which is the case with no structure in it at all and is the control the other three are measured against.

The playground above quantises any of the four at any table size. It is worth turning the table size down to 2 on the photograph and watching the reconstruction beside it, before reading any of the arithmetic below.

A model reads whole numbers and nothing else, and that is as true of a model reading a picture as of one reading a sentence. The vocabulary page sets out what has to be settled before a stream of numbers means anything, which is what the pieces are, how they are found, what happens at a piece the table has never seen, and whether the round trip is exact. Those four questions do not stop applying when the pieces stop being writing.

What changes is the answer to the last of them. A character vocabulary that has met every character in a text reproduces that text exactly, so the round trip loses nothing and the fourth question has a clean yes. Here the answer is no, always, and the interesting part is that it is a number rather than a yes or a no, which is what the middle of this page measures.

The obvious thing to try first is to skip the vocabulary altogether and let the pieces be their own numbers. It fails for a reason that has nothing to do with this picture. A vocabulary is a finite list, and every number in it names one entry, so a scheme that hands the pieces over as they are is claiming there is a finite list of pieces to name. A brightness is a real number, so there is no such list.

Rounding brightness to two decimal places still leaves 101 possible values per pixel. A two-pixel piece can combine any of them.

possible two-pixel pieces = 101 × 101 = 10,201

The photograph uses only fifty-three of those possibilities. Enumerating every possible piece spends most of the table on combinations absent from this picture.

two pixels:     101² = 10,201 possibilities
sixteen pixels: 101¹⁶ ≈ 1.17 × 10³² possibilities

Keep a fixed list of vectors. Each one owns the number that is its position in the list, counting from zero. To give a new vector a number, measure how far it is from every entry and answer with the position of the nearest. That is the whole method, and everything else on this page is a consequence of it or a cost of it.

number of v  =  the position i minimising  ||v − entryᵢ||²

The square is there for convenience rather than for meaning. Squaring is increasing on non-negative numbers, so the entry that minimises the squared distance is the entry that minimises the distance, and the square saves a square root that would change no answer.

Before any picture, the smallest instance that shows every part of the rule. Three entries in the plane, at (0, 0), (4, 0) and (0, 3), owning the numbers 0, 1 and 2. Four vectors to quantise, at (1, 0), (3, 1), (1, 2) and (2, 0). The table below is every squared distance, with the winner in each row marked, and it is small enough that a reader can check any cell of it.

…

entry 0 at (0, 0): 3² + 1² = 10
entry 1 at (4, 0): (−1)² + 1² = 2
entry 2 at (0, 3): 3² + (−2)² = 13

The last of the four vectors, (2, 0), is 4 away in squared distance from entry 0 and 4 away from entry 1. Nothing in the rule says which of them it should get, because the rule says nearest and there are two of those. Something has to decide, and whatever decides is arbitrary in the strict sense that a different choice would be equally correct.

The convention taken here is the lower position, which means the entry that comes first in the table rather than the entry that is smaller as a vector. That distinction is not idle. Writing the same three entries down in a different order, with (4, 0) first, sends the tied vector to the other one, and every other answer and the total cost stay exactly where they were.

…

A short list of positions, each standing for whatever is nearest to it, chosen so that the things nearest to it are close to it. That is the description of a codebook, and it is also, word for word, the description of the centres the k-means page finds. The two are the same object. Cluster k becomes entry k, the assign step of k-means is exactly the lookup described in section 5, and the quantity k-means calls inertia is the total this page is about to call the rounding error, before it is divided by the number of pieces.

Naming that connection is not a nicety. It settles where the table comes from, which is Part 6, and it settles what the table is good at, which is being close to whatever it was chosen from and nothing else. Every warning the clustering page gives about a grouping being a property of the rows it was fitted on transfers here without a word changed, and lands harder, because a grouping is usually inspected by somebody before it is used, while a table of codes is read straight into a model with no way of reporting a poor match.

Going the other way is a lookup and nothing more. Number 1 means the vector sitting at position 1 of the table, so a run of numbers becomes a run of vectors by reading them off, and the picture is reassembled by putting those vectors back where their pieces came from. A number outside the table has no meaning at all, exactly as a number past the end of a word list does, and there is nothing to give back for it.

What comes back is the entry, not the piece. That sentence is short and is the whole of the next Part, because it is the point at which this method parts company with a vocabulary of characters, where what comes back is the character that went in.

Send a piece through and back. The piece (0.35, 0.39) of the photograph, under a table of four entries, becomes the number 0, and the number 0 means the vector (0.4490, 0.5119). The piece did not survive. What survives is the entry it was nearest to, and the difference between the two is gone in the sense that nothing downstream holds it.

That is not a defect to be repaired by a better implementation. A table of four entries can distinguish four things, and the photograph has 53 different pieces, so at least 49 of them have to arrive somewhere they did not start. What is worth asking is how much is lost rather than whether anything is, and the answer to that is a number.

Take each piece, subtract the entry it became, square the result coordinate by coordinate, add those up, and average over the pieces. That average is the rounding error of the whole collection under that table, and it is what a coder calls the distortion.

error  =  (1 / n) × Σᵢ ||pieceᵢ − entry(pieceᵢ)||²

On the four vectors of section 6 the squared gaps are 1, 2, 2 and 4, so the error is their mean, 2.25. Every number this page quotes for a picture is that same average, and because it is a mean of squares its units are the square of a brightness, which is awkward to read. Taking the square root of the error divided by the two coordinates gives a figure in brightness again, and that is the typical miss on a single pixel.

Now the measurement. The photograph’s 128 pieces against a table of sixteen entries chosen from those same pieces give a rounding error of 0.000418, which is a typical miss of 0.0145 on a pixel whose brightness runs from 0 to 1. The furthest any piece had to travel is a squared gap of 0.00243, which is 0.0493 in the plane. Every one of the sixteen entries wins at least one piece.

Turn the table size down and watch two things at once. The points in the plane are the pieces and the marked positions are the entries, and at two entries the picture visibly becomes two tones while the error goes up by a factor of nearly sixty. The pieces lie in a narrow band along the diagonal, because a pixel and its neighbour are nearly equal in a smooth picture, and that band is what makes a small table do as well as it does here.

A table of sixteen entries owns the numbers 0 to 15, so each number takes four bits, and the whole picture becomes 128 numbers of four bits, which is 512 bits. The original was 256 brightnesses. Whether that is a saving depends entirely on what a brightness was costing, and at any ordinary precision it is a large one.

The codebook must travel with the IDs, or the receiver cannot reconstruct their meaning. This example uses sixteen entries with two coordinates each.

codebook = 16 × 2 = 32 brightness values
encoded picture = 128 IDs + 32 codebook values
original picture = 256 brightness values

These are counts of stored values, not equal-sized bytes: an ID and a brightness value may use different representations. Sharing the same table across many pictures amortizes the codebook cost.

One more bit per piece for every doubling of the table, and in exchange the rounding error falls. How far it falls is the trade, and it is not the same trade on every picture. The chart below draws the error against the table size on a logarithmic scale, where a constant factor per doubling is a straight line, and beside it lists the factor at each step.

…

The photograph’s error falls by 4.57, then 3.24, then 4.10, then 4.49, then 7.96. The speckled square’s falls by 1.74, then 2.52, then 2.22, then 2.30, then 2.63. The two are the same method on the same number of pieces at the same table sizes, and one of them is getting roughly twice as much for its bit as the other.

There is a standard result for how this trade should behave when the table is large. For a collection filling d coordinates, the best achievable error falls roughly as the table size raised to the power of minus two over d, so with two coordinates a doubling should buy a factor of two, and with one coordinate it should buy a factor of four.

The speckled square is the case that result describes, since every pixel there was drawn independently and the pieces genuinely fill the square, and its measured factors of 1.74 to 2.63 sit around the predicted two.

The two coordinates in these photograph patches are strongly related: neighboring pixels usually have similar brightness. The patches therefore cluster near the line where the coordinates are equal.

The measured spread along that line is 163.6 times the perpendicular spread. Although each patch is written with two coordinates, most observed variation lies close to one direction. This helps explain why its error reduction differs from a uniformly occupied two-dimensional example.

The measured reduction factors are 4.57, 3.24, 4.10, 4.49, and 7.96. Several are close to the idealized one-dimensional factor of four. The last occurs when the codebook is approaching the number of distinct patches in this small photograph, where a large-sample scaling argument is no longer a reliable description.

The comparison supports a useful distinction: the number of coordinates and the effective dimension occupied by the data need not be the same. It does not turn the idealized rate into an exact prediction for every finite codebook.

The poster is four flat bands of tone with a faint grain over them, and its sweep does something neither of the others does. Going from two entries to four cuts the error by 69.81, which is far outside anything the smooth curve of the photograph reaches. Going from four to eight cuts it by 1.76, which is worse than the speckled square manages at the same step.

The explanation is not subtle and is worth saying anyway. The poster has four tones, so the fourth entry is the one that finishes the job, and every entry after that is spent on the grain. When a collection genuinely has a number of parts, the curve has a corner at that number, and that corner is a fact about the picture rather than about the method. When it does not, as with the photograph and the speckled square, the curve is smooth and no table size is distinguished.

The curve cannot go on forever, and where it stops is decided by the collection rather than by the method. The photograph has 53 different pieces, so a table of 53 entries can hold one of each and reproduce it exactly, and the rounding error at that size comes out at 4.6 × 10⁻³³, which is zero to every bit the arithmetic keeps.

Asking for 54 is asking for an entry that has nothing of its own to be, and the result is two entries at one point, which is two numbers meaning one thing.

The printed chart reaches that wall much sooner, because it has only five different pieces. Eight entries already reproduce it exactly, and three of the eight win nothing at all. Sixteen cannot be built. The chart is the useful case here precisely because it is extreme, since the same thing is happening on the photograph at 54 and is simply further away.

Fewer entries than different pieces means some pieces share a number, and the interesting question is how different two pieces sharing a number can be. On the photograph at two entries, the pieces (0.00, 0.00) and (0.41, 0.45) both become the number 0, and both come back as (0.2067, 0.2366). Those two pieces are 0.6088 apart in the plane, one of them being black and the other being close to mid grey.

…

The widest such pair narrows as the table grows, from 0.6088 at two entries to 0.0894 at sixteen, which is the same trade the previous Part measured seen from a different side. It never reaches zero while there are fewer entries than different pieces, and at every size there is some pair the numbers cannot tell apart.

Everything so far has quantised a picture against a table chosen from that same picture. Take the photograph’s table of sixteen entries and put the printed chart to it instead. The rounding error goes from 0.000418 to 0.104290, which is 249.5 times worse, and 11 of the 16 entries are never asked for at all.

…

The reason is visible in the plane. The photograph’s entries all lie in the narrow band near the diagonal, since that is where its pieces were, and the chart’s pieces include (0.90, 0.05), a bright pixel next to a dark one, which is a place no entry has any reason to be. That piece is given the number 13, and 13 means the vector (0.4286, 0.4771), which is mid grey twice over. A hard edge has become a flat patch.

Look at the two rows of the previous table together. The chart’s piece (0.05, 0.05) lands on entry 11 at a squared gap of 0.001, which is as good a match as anything on the photograph gets. Its piece (0.90, 0.05) lands on entry 13 at a squared gap of 0.404696, four hundred times as large. What is sent downstream in the two cases is the number 11 and the number 13, and nothing else.

A model reading those numbers has no way to tell the excellent match from the hopeless one, because the output alphabet is whole numbers and a whole number is all it gets. That is the same fact the vocabulary page ends on, that a token number says which entry and nothing more, and it is sharper here, since the entries do have positions in a space and it is tempting to believe some of that survives.

It does not. Carrying the gap alongside the number is possible and is a different scheme, one that is no longer sending whole numbers.

Nothing so far has said how the entries were placed, and the answer is that they were fitted. Start from some positions, give every piece to the nearest, move each entry to the mean of the pieces that chose it, and repeat until nothing moves. That is Lloyd’s procedure and it is k-means, and the entries used everywhere on this page are the centres it settles on.

It inherits every property of that procedure, including the awkward one that it finds a local answer rather than the best one and which local answer depends on where it started. On this photograph that turns out to matter very little. Six different starting draws at eight entries reach two answers, 0.0018756 and 0.0018772, which differ in the sixth decimal place. That is a fact about this collection, whose pieces lie along a line, rather than a guarantee, and on a collection with several genuinely different good tables the spread would be real.

An entry that no piece is ever nearest to is a row of the table that is carried, transmitted and never used. It costs bits on every piece, since the number of bits is set by the size of the table and not by how much of it is live, and it returns nothing. Fitted on the collection it will quantise, the procedure leaves none of these, and every table on the photograph up to 32 entries has all of them in use.

Fit on half the photograph and measure on the other half and they appear. The table below fits on the top 64 pieces and then quantises both halves, and at sixteen entries the half it never saw asks for only ten of them while rounding three times worse than the half it was fitted on.

…

The last column is the same idea taken further, a table fitted on the whole photograph and put to the printed chart, where 27 of 32 entries are never asked for. A model reading five distinct numbers out of a possible 32 is paying five bits a piece to say something that needed three, and nothing in the numbers says so.

The smallest table has one entry, and it is worth looking at because it is exactly the case where the method does nothing. Every piece becomes the number 0, the number costs zero bits because it could not have been anything else, and the rounding error is 0.113862, which is precisely the mean squared distance from the pieces to their own mean. The single entry is the mean, so the error is the spread of the collection and the numbers carry none of it.

The largest table is the one section 17 reached, 53 entries for the photograph, where each piece has its own number and the error is as close to zero as float arithmetic gets. Between those two ends is the entire method, and the only thing being traded along the way is bits against error.

Several of the things this page has shown are decisions taken alongside the rule rather than consequences of it, and a description of the method that leaves them out has not described it. There are five, and each is a real choice with a cost attached rather than a detail.

Separately from the choices there are inputs on which the rule has no answer at all, and they are worth separating from the choices because arguing about them is wasted effort. In each case something the rule needs is a quantity the input does not have. The table gathers them, with what the mathematics says.

The third of the five decisions in section 24 deserves its own measurement, because it is the one most often read as a definition. Nearest is a property of two vectors together with a rule for measuring rather than of the two vectors alone, and the rule used throughout this page is the straight line. Adding the two coordinate gaps instead is an equally ordinary rule, and it does not always give the same answer.

…

Of the photograph’s 128 pieces against a table of eight entries, exactly one changes hands. The piece (0.13, 0.30) is 0.1078 from entry 5 and 0.1303 from entry 1 by the straight line, so it goes to entry 5, and it is 0.1480 from entry 5 and 0.1437 from entry 1 by the sum of the gaps, so it goes to entry 1.

One piece in 128 is a small effect, and it is not zero. The choice is constrained in a second way as well, since the straight line is the measure the fitting step lowers, so changing the rule used at lookup time without changing the one used at fitting time leaves the two halves of the method aiming at different quantities.