Nearest Neighbors and Embedding Evaluation | COSMO - Community of Science and Math Outreach

A nearest-neighbor system stores examples and answers a query by finding the stored vectors closest to it. The idea is simple; the evaluation is not.

Given a query vector $q$ and stored vectors $x_1,\ldots,x_n$ , exact $k$ -nearest-neighbor search computes a distance or similarity score for every item and returns the best $k$ . With $d$ coordinates, a direct scan costs roughly $O(nd)$ operations per query.

Classification by neighborhood

In $k$ -nearest-neighbor classification, each neighbor votes for a label. With distance-weighted voting, a closer point gets more influence:

w_i=\frac{1}{d(q,x_i)+\varepsilon}.

The small constant $\varepsilon$ prevents division by zero. Weighted voting can help when one very close example should matter more than several borderline examples, but it can also amplify mislabeled points.

The choice of $k$ controls a tradeoff. A very small $k$ responds to local detail but is sensitive to noise. A large $k$ is steadier but can blur small or rare groups. Choose $k$ using held-out data rather than the examples used to design the embedding.

Retrieval evaluation

When the goal is retrieval rather than classification, precision at $k$ asks how many returned items are relevant:

P@k=\frac{\text{relevant returned items}}{k}.

Recall at $k$ asks how much of the available relevant material was found:

R@k=\frac{\text{relevant returned items}}{\text{all relevant items}}.

Suppose a collection contains eight relevant items. If the first five results contain four of them, then $P@5=4/5$ and $R@5=4/8$ . Precision rewards a clean shortlist; recall rewards coverage.

Build an evaluation set before comparing models

A useful comparison needs fixed queries, relevance judgments, and a metric. Otherwise it is easy to look at a few pleasing examples and declare a winner.

Use this sequence:

Define the relationship the embedding should preserve.
Select representative queries, including rare and difficult cases.
Record relevant items without looking at model rankings.
Compare every embedding with the same metric and query set.
Inspect performance by subgroup and read individual failure cases.

If the embedding will support recommendations, relevance may not be a simple category label. Two songs can share a genre but differ in mood, instrumentation, or audience. Human judgments may be needed, and judges may disagree. That disagreement is evidence about the task, not just noise to discard.

Visualization is not validation

PCA, t-SNE, and UMAP can project high-dimensional vectors onto a page. They are useful for forming hypotheses, but a two-dimensional picture can distort neighborhoods. A cluster in the plot does not prove good retrieval, and overlap does not prove failure.

Evaluate in the original embedding space. Use the plot to choose examples worth investigating.

Error analysis

For each poor query, ask:

Is the query itself ambiguous?
Are the labels or relevance judgments incomplete?
Does the metric ignore useful magnitude information?
Is a common class crowding out a rare one?
Does the embedding preserve an unintended shortcut?

The best embedding is not the one with the most impressive scatterplot. It is the one whose neighbors remain useful on the queries and groups the system must actually serve.