k-Nearest Neighbors & SVMs

k-NN: you are your neighbors

The simplest algorithm in all of ML — so simple it barely "learns":

1. Store the entire training set. (That's the training. Done.)
2. To classify a new point, find its $k$ closest training points (using vector distance — math path).
3. Let them vote. Majority wins.

A new email is spam if most of the $k$ most-similar known emails were spam. With $k=1$ the boundary is jagged and follows every noisy point (overfitting); with huge $k$ everything gets the majority class (underfitting). The parameter $k$ is your first hyperparameter — a knob you set rather than the model learns, tuned by validation (next module).

k-NN's lessons outlive the algorithm itself:

• Distance = similarity is the core geometric faith of ML. Modern vector databases doing "semantic search" over embeddings are running k-NN at internet scale.
• The curse of dimensionality: in very high dimensions, distances between random points become nearly equal, and "nearest" loses meaning. This is why raw pixels make poor features and learned embeddings matter.

Practical costs: prediction requires scanning stored data (slow at scale), and features must be scaled — a feature with big numeric range otherwise dominates the distance.

SVM: the widest street

Many lines can separate two classes. Which is best? The support vector machine answers with geometry: the line that leaves the widest margin — the maximum empty street between the classes. Points touching the street's edges are the support vectors; they alone define the boundary (delete every other training point and nothing changes).

Why maximize margin? A boundary with breathing room is robust: a test point that lands slightly off from its training cousins still ends up on the correct side. Wide margin = better generalization, a rare case where the intuition is also a theorem.

Soft margins allow some points to violate the street (real data overlaps); a parameter $C$ trades margin width against violations.

The kernel trick is SVM's party piece: implicitly map data into a much higher-dimensional space — where a curved problem becomes linearly separable — without ever computing the mapping, only inner products. The circle-inside-circle dataset, unsolvable by any line in 2-D, splits perfectly with an RBF kernel.

Before deep learning took over around 2012, kernel SVMs were the state of the art in text and image classification, and they remain strong for small-to-medium tabular datasets.

Key takeaways

• k-NN: classify by nearest examples — the ancestor of today's vector search; watch $k$, scaling, and high dimensions.
• SVM: the maximum-margin boundary, defined only by support vectors; margins buy generalization.
• Kernels let linear machines draw nonlinear boundaries — mapping to richer spaces is a recurring ML superpower.