k-Nearest Neighbours
Classify a new point by looking at the labelled points closest to it — a method with no training step at all.
Why It Was Important
k-NN stores the training data and defers all work to prediction time, classifying by majority vote among the nearest examples. Cover and Hart proved in 1967 that its error rate is at worst twice the theoretical minimum, which made it the first classifier with a hard guarantee attached. It is still the reference point for instance-based learning, and the intuition behind it — that similar inputs sit near each other in some space — is exactly what modern embeddings formalise.
Who Invented It
Thomas Cover, Peter Hart
Their 1967 paper established the method's theoretical error bound.
Applications
- Pattern Recognition
- Recommendation Systems
- Anomaly Detection
- Embedding Search
Key Papers
- Nearest Neighbor Pattern Classification
Thomas M. Cover, Peter E. Hart · IEEE Transactions on Information Theory · 1967