K-Nearest Neighbours

naive bayes is the classifier you get by taking bayes’ rule seriously and probability theory not seriously at all. 𐃏 it assumes every feature is independent of every other feature given the class — an assumption that is false for essentially all real data — and yet it filters spam, routes support tickets and triages documents well enough that it has survived five decades of fancier competition. this page derives it, counts why the “naive” part is the whole point, builds a spam filter from scratch, and is honest about where it breaks (its probabilities, not its decisions).

a straight line is too rigid for a wiggly world, and a global degree-9 polynomial is a hostage negotiation. 𐃏 locally weighted regression (LWR — and its robust cousin LOWESS) takes the diplomatic route: fit the simplest possible model, but fit it freshly at every query point, paying attention only to the training points nearby.

motivation#

• linear regression commits to one \(\theta\) for the whole input space. if the true \(f\) bends, the residue of that commitment is bias everywhere.
• the fix need not be a fancier global family. any smooth function is locally linear — taylor says so — so a linear fit weighted toward a neighbourhood of \(x_0\) can track an arbitrary smooth \(f\).
• the price: there is no longer a “trained model”. LWR is memory-based and non-parametric — like k-nearest neighbours, it keeps the entire training set and does all of its work at prediction time. training is \(O(1)\); every query costs a fresh weighted least-squares solve. 𐃏

the estimator#

weighted least squares at a query point#

fix a query \(x_0\). assign each training point a weight \(w_i(x_0) \ge 0\) that decays with distance from \(x_0\), then solve the weighted least-squares problem

k-means is unsupervised learning’s hello world: pick \(k\) prototype points, assign every datum to its nearest prototype, move each prototype to the centre of its flock, repeat. 𐃏 it is fast, it always terminates, and it is wrong in ways that are so instructive that every clustering course starts here anyway.

Knowledge is a paradox. The more one understand, the more one realises the vastness of his ignorance.