Instance-Based Learning & k-Nearest Neighbors

Unlike parametric models that compress training examples into a fixed set of weights during an upfront training phase, Instance-Based Learning (often termed lazy learning) postpones computation until inference time.

The canonical algorithm in this family, k-Nearest Neighbors (k-NN), makes predictions by querying the local geometric neighborhood of a query point in a defined metric space.

1. Distance Metrics in Metric Spaces#

For a function $D(x, z)$ to qualify as a valid metric on a set $\mathcal{X}$, it must satisfy four axioms for all $x, y, z \in \mathcal{X}$:

1. Non-negativity: $D(x, z) \ge 0$
2. Identity of Indiscernibles: $D(x, z) = 0 \iff x = z$
3. Symmetry: $D(x, z) = D(z, x)$
4. Triangle Inequality: $D(x, z) \le D(x, y) + D(y, z)$

The Minkowski Distance Family#

The Minkowski distance of order $p \ge 1$ generalizes standard geometric distances across coordinate spaces $\mathbb{R}^d$:

Cosine Distance vs Angular Similarity#

In text retrieval and dense embedding vectors, directional orientation matters more than Euclidean magnitude. The Cosine Similarity measures the angle $\theta$ between vectors:

The associated Cosine Distance is:

2. Mathematical Proof: The Curse of Dimensionality#

As the dimensionality $d$ increases, intuitive geometric properties break down. We prove why distance-based algorithms like k-NN suffer degradation in high-dimensional spaces.

Hypersphere to Hypercube Volume Ratio#

Consider a $d$-dimensional hypercube of side length $2r$, with volume:

Now consider an inscribed $d$-dimensional hypersphere of radius $r$. Its volume is given by:

Where $\Gamma$ denotes Euler's Gamma function ($\Gamma(n) = (n-1)!$ for positive integers).

Let us compute the ratio of the volume of the inscribed hypersphere to the enclosing hypercube:

Applying Stirling's asymptotic formula $\Gamma(k + 1) \approx \sqrt{2\pi k} (k/e)^k$ with $k = d/2$:

As $d \to \infty$, the term $\left(\frac{\pi e}{2d}\right) \to 0$ exponentially:

3. KD-Trees: Accelerating Spatial Queries#

Brute-force k-NN requires scanning all $N$ data points, yielding $O(N \cdot d)$ query latency. A k-d Tree (k-dimensional tree) is a space-partitioning binary search tree that indexes data to enable $O(\log N)$ expected search time.

Partitioning Rules:#

1. Cycling Dimensions: At depth $m$, split on feature dimension:

1. Median Split: Find the median along coordinate $\text{axis}$ to partition instances into balanced left and right subtrees.
2. Branch Pruning: During nearest neighbor queries, if the distance from the query point $q$ to the splitting hyperplane $|q_{\text{axis}} - v_{\text{split}}|$ is greater than the current radius to the $k$-th best neighbor, the opposite subtree can be completely pruned.

4. From-Scratch Implementation: Zero Dependencies#

The following implementations demonstrate pure mathematical k-NN classification in Python and Rust without external packages.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import math
from typing import List, Tuple
from collections import Counter

class KNNClassifierFromScratch:
    def __init__(self, k: int = 3, metric: str = "euclidean"):
        self.k = k
        self.metric = metric
        self.X_train: List[List[float]] = []
        self.y_train: List[int] = []

    def fit(self, X: List[List[float]], y: List[int]) -> None:
        # Non-parametric lazy model: store instances directly
        self.X_train = [list(row) for row in X]
        self.y_train = list(y)

    def _compute_distance(self, a: List[float], b: List[float]) -> float:
        if self.metric == "manhattan":
            return sum(abs(x_i - y_i) for x_i, y_i in zip(a, b))
        # Default: Euclidean distance (L2)
        return math.sqrt(sum((x_i - y_i) ** 2 for x_i, y_i in zip(a, b)))

    def predict_single(self, query: List[float]) -> int:
        distances: List[Tuple[float, int]] = []
        for i, sample in enumerate(self.X_train):
            dist = self._compute_distance(query, sample)
            distances.append((dist, self.y_train[i]))

        # Sort by distance in ascending order
        distances.sort(key=lambda item: item[0])

        # Extract top k nearest labels
        k_nearest_labels = [label for _, label in distances[:self.k]]

        # Majority vote
        vote_counts = Counter(k_nearest_labels)
        most_common = vote_counts.most_common(1)[0][0]
        return most_common

    def predict(self, X_test: List[List[float]]) -> List[int]:
        return [self.predict_single(query) for query in X_test]

if __name__ == "__main__":
    X_train = [[1.0, 2.0], [1.5, 1.8], [5.0, 8.0], [8.0, 8.0], [1.0, 0.6], [9.0, 11.0]]
    y_train = [0, 0, 1, 1, 0, 1]

    knn = KNNClassifierFromScratch(k=3, metric="euclidean")
    knn.fit(X_train, y_train)

    X_test = [[1.2, 1.5], [6.0, 7.5]]
    predictions = knn.predict(X_test)
    print(f"Predicted labels: {predictions}")

5. Active Knowledge Checks#