Searching a Collection of Pictures

Every picture on this page is sixteen pixels a side and holds one of four shapes, a cross, a square outline, a filled disc or a diagonal bar, drawn at a random place, size and brightness with a little noise over every pixel. The network from the page on a vector for a picture reads each one and, one layer before it names the shape, answers with sixteen numbers, and those sixteen numbers are the picture’s position.

Finding the pictures most like a given one becomes finding the positions nearest its position, and no pixel is compared again.

picture  →  network  →  v  =  (v₁, v₂, …, v₁₆),     each vᵢ between −1 and 1

The collection searched is 4000 pictures, 1000 of each kind, drawn under a seed of 11, which is far more than the 240 the network learned from, and a forward pass costs little enough that drawing more is free. The questions are the other 240 pictures of the network’s own draw, 60 of each kind, the half it was scored on and never trained on, so no question is a picture the network memorised and none of them is in the collection.

Each of the sixteen numbers comes out of a hyperbolic tangent and so lies between −1 and 1, and the collection’s vectors average a length of 3.03, against the 4 a vector sitting in a corner of that range would have, so most pictures push most of their sixteen numbers close to one end or the other.

Ask for the pictures nearest held-out picture 0, a cross, and the answer is a list, the k pictures of the collection whose positions are closest to its position, nearest first. The playground shows that list for any question, each picture framed in the colour of its kind, and for picture 0 all ten of the nearest are crosses. The nearest is 0.5278 away and the tenth 0.7691 away, while the farthest picture in the collection is 5.3240 away.

d(q, x)  =  √( Σᵢ (qᵢ − xᵢ)² )

answer(q, k)  =  the k pictures x of the collection with the smallest d(q, x), nearest first

This is the search the k-nearest neighbours page votes with, with the vote taken away, since here the neighbours are the answer. Straight-line distance is the choice made throughout, because the network’s sixteen numbers are all on one scale and a picture’s length carries something, how hard the network committed to it. Part 4 measures by angle instead, for a reason that belongs to that route.

Every entry of that list rests on one sum, done the same way for each of the 4000 pictures. Take held-out picture 0 and the picture the search put nearest it, collection picture 2072, also a cross, subtract their sixteen numbers one pair at a time, square each gap and add the squares.

There is no person on hand to say whether the pictures a search returns look like the question, so the page judges them by the one thing every picture carries, its kind. For each question we count how many of its k nearest are of the same kind, divide by k, and average over the 240 questions, which is called precision at k. If the positions carried nothing, a neighbour would share the kind a quarter of the time.

precision at k  =  (1 / 240)  Σ over questions q of  (how many of q’s k nearest share q’s kind) / k

Precision falls a little as k grows, since the twentieth nearest picture is further out than the fifth and further out is where the kinds begin to meet. By kind, at ten neighbours, crosses score 0.9683, squares 0.9800, discs 0.9767 and bars 0.9850. Let the ten vote and the majority kind is the question’s own for 0.9875 of the 240, which is higher than the 0.9708 the network scores naming the same 240 pictures with its own last layer, a layer that reads exactly these sixteen numbers.

I had expected the vote to do no better than that layer, and section 6 checks whether the difference survives a retrain.

Four of the 240 questions have a nearest picture of another kind. Held-out picture 16, a cross, has a disc nearest at 0.7969 and only three crosses among its ten; picture 35, a bar, has a disc at 1.0619 and two bars among its ten; picture 140, a cross, has a disc at 0.7080 and six crosses; and picture 185, a square, has a bar at 1.0721 and not one square among its ten.

The button in the playground steps through them, and it is worth looking at each question beside what came back, since all four nearest distances are larger than picture 0’s 0.5278, which puts these questions where the collection is thin.

None of the four is a mistake by the search. Each answer is exactly the nearest position in the collection, measured against every picture there is, so the disagreement is between the network’s arrangement and the label, and no index can do better on this measure than the exact answer does. That is why the rest of the page scores an index by recall, how much of the exact answer it finds, and never by precision, which would mix what the index lost with what the network got wrong.

Every figure so far depends on one trained network, and a network trained from different starting weights gives every picture a different position. So the table trains it again from two other weight seeds and asks the same 240 questions of the same 4000 pictures. Every widget on the page draws seed 0.

The ten nearest share the question’s kind 0.9775, 0.9646 and 0.9779 of the time across the three seeds, and two cells of the inverted file recover 0.9583, 0.9404 and 0.9450 of the true ten, so neither headline figure belongs to one lucky network. The comparison from section 4 held on all three seeds and grew on one of them.

Seed 1’s network names only 0.9208 of the held-out pictures correctly with its own last layer, while the single nearest picture in its sixteen numbers shares the kind 0.9917 of the time, so a network whose own answer is its weakest of the three still arranged its pictures as well as the others did.

To be sure which picture is nearest, the search has to measure every picture, since the one it skips could have been the nearest. For one question that is 4000 distances of sixteen numbers each, 64000 multiply-adds, and for the 240 questions it is 960000 distances. None of that is slow at this size. What matters is how it grows, one full pass over the collection for every question, so the cost of a question rises in step with the collection and never falls.

cost of one question  =  N × d  =  4000 × 16  =  64 000 multiply-adds
cost of Q questions   =  Q × N × d  =  240 × 4000 × 16  =  15 360 000

Suppose the search has measured every picture but one and found a best so far. Nothing it has measured says anything about the last picture, which could sit anywhere in the sixteen-dimensional space, including right on top of the question, so the only way to know is to measure it. Skipping a picture safely needs something known in advance that says how near that picture can possibly be, and a plain list of vectors carries no such thing.

The something is usually a stored distance to a landmark. If a picture x is known to be a distance d(c, x) from a centre c, then once the question’s distance to c is measured, the triangle inequality puts a floor under d(q, x) without computing it, and every picture whose floor is already beyond the best found can be passed over.

d(q, x)  ≥  d(q, c) − d(c, x)

skip x whenever  d(q, c) − d(c, x)  >  the k-th best distance found so far

Bentley’s k-d tree uses boxes as its landmarks and the inverted file uses k-means centres, and no tree is built on this page. There is one difference worth holding on to before Part 3. A search that skips only what the bound rules out is still exact. The inverted file as it is used in practice, and as it is built here, does not check the bound at all, and simply stops after a fixed number of cells, which is why it can miss.

With all 4000 distances measured, the k smallest still have to be picked out. Sorting all 4000 would put every picture in order, which is more than the question asks, since only the first k matter. The search behind this page splits the distances around the k-th smallest, which takes one pass of a few comparisons per picture, and then sorts only the k in front of it.

sort everything     ≈  N log₂ N  =  4000 × 12  ≈  48 000 comparisons
split at the k-th   ≈  a few × N,  then k log₂ k  to order the k

The split also shows how sharp the answer is. For picture 0 the tenth nearest is 0.7691 away and the eleventh 0.8108, a gap of 0.0417, so asking for ten rather than eleven was a real choice there. Where the tenth and eleventh are at the same distance, the set of the ten nearest stops being one set, which is one of the cases Part 6 takes up.

The inverted file does some of the work once, before any question arrives. It runs k-means over the 4000 positions to find 32 centres, puts every picture in the cell of the centre it is nearest, and keeps, for each cell, the list of pictures in it. That list is the inverted list the method is named after, and each cell stands for a region of the space, every point of which is nearer its centre than any other centre, so a question that was never in the collection still falls in exactly one cell.

cell(x)  =  the c among the centres μ₁ … μ₃₂ that makes  ‖x − μ_c‖  smallest

Here k-means runs from three seedings and keeps the best, which settled in 46 rounds, and the 32 cells hold between 44 and 356 pictures each, none of them empty. The map under the playground draws every picture on the two directions of greatest spread, which keep 70.8% of it, with the cell centres as open circles. The cells follow the pictures, several to each kind, since k-means puts centres where the pictures are dense and knows nothing about kinds.

A question is first measured against the 32 centres, which ranks the cells by how near their centres are. The search then opens the nearest few cells, measures only the pictures listed in them, and returns the k nearest of those. How many cells it opens is the one setting it has, and the playground slider moves it.

distances  =  centres + pictures in the opened cells  =  32 + 80  =  112,   against 4000

recall at 10  =  |index answer ∩ exact answer| / 10  =  10 / 10  =  1.0

Recall is what an index is scored by from here on. It is the share of the exact k nearest that the index also returned, so an index that found the same ten pictures scores one, whatever their kinds, and an index that found ten other pictures scores zero even if they are all of the right kind.

Picture 0 was an easy question. Averaged over all 240, opening the nearest cell recovers 0.8329 of the true ten while reading 4.2% of the collection, and 121 questions get all ten. Each further cell buys less than the one before it, and by six cells every question gets every one of its ten.

…

The chart sets every setting at its recall and its share read. For now read the solid lines, which are the inverted file at 16, 32 and 64 cells; the dashed ones are Part 4’s. Every solid line rises steeply and then flattens, and a reader choosing a setting is choosing a point on that tradeoff curve.

The average hides a question for which one cell recovers nothing at all. Held-out picture 46, a disc, is nearest the centre of a cell of 181 pictures, 0.8160 away, and not one of its ten true nearest is in that cell. Five of them are in a cell whose centre is 0.8877 away and five in one whose centre is 0.8929 away, so its three nearest centres are within 0.0769 of one another, and the question sits close to where all three cells meet.

The playground’s button for the question one cell serves worst loads it.

the k nearest all lie within  r_k  of q      (for picture 46,  r₁₀ = 0.4853)

one cell is enough only if that ball lies inside q’s own cell

A second cell recovers half of its ten and a third recovers all of them. Nearness to a centre and nearness to the pictures a cell holds are different things, and they part company exactly where a question sits near a boundary, since the ball holding its ten nearest then reaches over into cells whose centres are a little further off.

The number of cells is set when the index is built. More, smaller cells follow the pictures more closely, so for the same share read a finer cut recovers more, and the table sets the three cuts side by side at roughly 8% of the collection read.

The finer cut costs in two other places. Every question measures every centre, so 64 cells add 48 distances a question to what 16 cells charge, and the k-means fit that builds the cells has more centres to place, though at 64 cells it settled in 26 rounds against 50 for 16. The smallest of the 64 cells holds 16 pictures, which matters once k is larger than a cell, as Part 6 says.

If 32 cells held 125 pictures each, one cell would be 3.1% of the collection, and yet opening one cell reads 4.2% on average. The cells are uneven, from 44 pictures to 356, and a question drawn the way the collection was drawn falls into a cell in proportion to how many pictures that cell holds, so the large cells are opened more often than the small ones and each time they are opened they cost more.

share read with one cell, expected  =  Σ over cells c of (n_c / N) × (n_c / N)  =  Σ n_c² / N²

The second route draws its cuts at random and never looks at the pictures. Draw a plane through the origin of the sixteen-dimensional space in a random direction, and give every picture a one if its vector lies on one side and a zero if it lies on the other. Twelve planes give every picture a code of twelve bits, pictures with the same code share a bucket, and a question is searched only against its own bucket and those close to it.

bitⱼ(v)  =  1 if rⱼ · v > 0,  else 0,        rⱼ drawn from a standard normal in each of the 16 numbers

P( bitⱼ(u) = bitⱼ(v) )  =  1 − θ(u, v) / π

…

The nearest picture to picture 0 by angle is again picture 2072, 10.1° away, and its code agrees with picture 0’s on 11 of the 12 bits, where the formula expects 11.33. A square at 80.0° agrees on 6, with 6.66 expected, and a bar at 118.3° agrees on 4, with 4.11 expected. Each count is twelve coin flips, so the counts land near the expectation rather than on it.

The whole route rests on that one probability, so it is worth checking on these vectors rather than trusting. The widget sets picture 0 against 200 pictures of the collection on 2000 fresh planes each, takes the share of planes that put each pair on the same side, and compares it with one minus the pair’s angle over π. The mean gap is 0.0059 and the largest 0.0232.

spread of a share of 2000 fair coin flips  ≤  √(0.25 / 2000)  =  0.0112

The mean gap is about half of that spread and the largest of the 200 gaps about twice it, which is where the largest of two hundred such shares ought to land, so the formula holds on these pictures to within the noise the finite count of planes puts on it.

Twelve planes allow 4096 codes, and the 4000 pictures use only 341 of them, the busiest holding 274 pictures. Searching only the question’s own bucket recovers 0.4583 of the true ten by angle while reading 2.2% of the collection, so the method looks further, to every code within one bit of the question’s, then within two, and the number of buckets to look in grows quickly.

codes within r bits of a b-bit code  =  Σ from i = 0 to r of C(b, i)

12 bits, r = 2:   1 + 12 + 66  =  79 buckets

More planes make each bucket smaller and more alike, and they make the neighbourhood of a code larger. At sixteen planes a search within four bits looks in 2517 buckets, when only 659 of the 65536 possible codes are used by any picture at all, so most of the looking finds nothing.

Switch the chart in section 12 to both routes and the dashed lines sit below the solid ones at every share read. Four cells of 32 read 14.7% of the collection and recover 0.9958 of the true ten, twelve planes searched within two bits read 14.6% and recover 0.9408, and sixteen planes within three bits read 14.1% and recover 0.9612. On these pictures the hashing is the worse bargain at every share the chart shows.

The cells were placed by k-means where the pictures are, and the planes were drawn without looking. The collection does not sit around the origin, since 11 of the 16 numbers average above zero across it, so a random plane through the origin often passes to one side of most of the pictures and gives nearly all of them the same bit, which spends a bit on no distinction.

At eight planes the busiest bucket holds 481 pictures, 12% of the collection. The two routes are also scored against two exact answers, the nearest by distance and the nearest by angle, and those share 0.8017 of their ten, so the comparison is between two methods each doing its own job.

The hashing has what the cells lack elsewhere. It needs no fit over the collection, a new picture’s code is twelve dot products, and the probability of a shared bit holds for any pair of vectors whatever the collection looks like, which is what made it the first route with a guarantee in high dimension. None of that shows as recall at this size.

An index skips pictures because it can tell that they are far from the question. That only works if far and near are very different distances, so the thing to measure is how much nearer the nearest picture is than the farthest. For each question we divide one by the other, and a ratio near zero means the nearest is much nearer than the rest, while a ratio near one means every picture is about as far away as every other.

ratio(q)  =  min over x of d(q, x)  /  max over x of d(q, x)

…

On the picture vectors the ratio averages 0.0775. On vectors of the same sixteen numbers drawn evenly between −1 and 1 it averages 0.3230, and as the random vectors widen it rises, 0.5982 at 64 numbers, 0.7798 at 256 and 0.8842 at 1024, where the nearest of 4000 points is only 12% nearer than the farthest. The raw pixels of the same pictures, 256 numbers each, average 0.2243.

The ratio predicts what an index will do, and the right-hand panel of the chart tests the prediction. The same inverted file of 32 cells, fitted the same way, is run on the pictures and on 4000 random vectors of 16 and of 64 numbers, and asked the same question, how much of the true ten a number of cells recovers.

On random vectors of 64 numbers, recovering 0.96 of the true ten takes 24 of the 32 cells, which reads 75.3% of the collection and costs 3045.8 distances a question with the centres. The exact scan costs 4000 and is certain, so for a saving of about a quarter the index gives up about a twenty-sixth of the answer, and in that setting the plain scan is the better method.

The picture vectors and the first random set both have sixteen numbers, and they behave like different spaces. The difference is in how the sixteen numbers are spread. Six directions hold 90% of the pictures’ spread, and the widest holds 48.7% on its own, while random vectors need fifteen of their sixteen directions for the same 90% and their widest holds 7.0%. The pictures fill a thin, clumped part of their space, four kinds each gathered in its own region, and the random vectors fill all of it.

The rule of thumb that indexes stop helping past ten or twenty dimensions held here for the random vectors and did not hold for the pictures, which have sixteen numbers and an index that works well. The raw pixels make the same point from the other side, with 256 numbers and a ratio of 0.2243, lower than random vectors of sixteen.

Beyer and his colleagues stated their result under conditions on how the points are drawn, of which independent, identically spread coordinates are the plainest case, and a network’s positions for four kinds of shape are nothing like that.

The exact search is a minimum taken over the collection, k times over, and a minimum needs something to take it over and a way of telling two candidates apart. Each case below removes one of those, and the table says what the mathematics then says.

The inverted file adds two decisions to the exact search, which cell a question belongs to and which cells to open, and the hashing adds one, which side of a plane a vector is on. Each can fail to have an answer, and each has a case where the index stops saving anything.