Unit 09.02: Building a search index over images

An image search index is a normalised matrix and a dot product.

Ranking, and the absence of an empty result

Five hundred vectors, one query, top-five neighbours.

The code builds the index and searches it.

import numpy as np

rng = np.random.default_rng(1)
N, D = 500, 32
index = rng.normal(size=(N, D))
index /= np.linalg.norm(index, axis=1, keepdims=True)
ids = [f"img-{i:03d}" for i in range(N)]

query = index[42] + rng.normal(0, 0.1, D)
query /= np.linalg.norm(query)

scores = index @ query
order = np.argsort(-scores)[:5]
print(f"{'rank':>4} {'id':10} {'score':>7}")
for rank, i in enumerate(order, 1):
    print(f"{rank:>4} {ids[i]:10} {scores[i]:>7.3f}")

gap = scores[order[0]] - scores[order[1]]
print(f"\ngap between rank 1 and 2: {gap:.3f}")
print(f"the search returns 5 results whether or not any are relevant")

# Normalising once at index time makes the search a single matrix multiply.
# And as in text retrieval, there is no empty result -- a threshold on the
# score is what turns a ranking into a decision.

The search returns five results whether or not any are relevant - exactly as in text retrieval, there is no empty result in a nearest-neighbour search unless you add a threshold.

The gap between rank one and rank two is the useful diagnostic. A large gap means the match is decisive; a tiny one means several images are equally close and the ordering is close to arbitrary.

The mistake this prevents

The mistake is presenting the top result as 'the match'. It is the nearest available vector, which in an index that does not contain the object is the nearest irrelevant one.

Takeaway

Nearest-neighbour search always returns k results. Add a score threshold, and read the rank-1-to-rank-2 gap as a measure of how decisive the match was.

Mark complete