Unit 3.5 · about 3 h
148 / 324k-nearest neighbors, search cost and the curse of dimensionality
kNN is the purest similarity classifier: no training, all geometry. It punishes unscaled features and high dimensions faster than any other family, which makes it the ideal instrument for learning scale discipline.
- implement
- measure
You can now
- Implement brute-force kNN with uniform and distance weights and match sklearn predictions including a distance tie.
- Explain how neighborhood size, weighting and feature scale move bias, variance and cost, and when trees lose to brute force.
- Measure distance concentration and search time as dimension grows and state the scaling policy you would ship.
Covers
- k-nearest neighbors, distance, weighting and feature scale
- Neighbor search cost and the curse of dimensionality
Study, in this order
3 steps
- Murphy Chapter 16: KNN and the curse of dimensionalityProbabilistic Machine Learning, Chapter 16: exemplar-based methods
Sections 16.1 to 16.1.3 (pp. 547 to 550): the KNN decision rule, the curse of dimensionality with the growing-hypercube example, and k-d trees, hashing and approximate search for speed
- sklearn neighbors: classification, regression and weightsscikit-learn - neighbors, SVMs, trees and ensembles
1.6.2 Classification and 1.6.3 Regression:
n_neighborsdefault 5,uniformversusdistanceweights, and the regressor averaging rule - sklearn neighbor search algorithms and costscikit-learn - neighbors, SVMs, trees and ensembles
1.6.4 Nearest Neighbor Algorithms: brute force against K-D and ball trees, the auto-selection rule with
leaf_size30, and when high dimension or sparse input falls back to brute force
Focus on
- The vote is a majority under uniform weights and an inverse-distance vote under distance weights. On the toy, query 2.5 has \(x = 0\) and \(x = 5\) tied for third place. sklearn warns that such ties depend on training order: in the given order \(x = 0\) joins, so uniform predicts 0 and distance weights give 1 at probability 0.652; reorder the rows and \(x = 5\) joins, so uniform predicts 1.
- Scale is the model. With an informative feature on \([0, 1]\) (label \(x_0 > 0.5\)) and a nuisance feature on \([0, 1000]\), 5-NN scores 0.47 unscaled and 0.995 standardized (400 train and 200 test points, seed 0). Standardize inside a
Pipelineso test data meets the same transform. - Distances concentrate fast: for 50 uniform points in the unit cube, the \((\text{max} - \text{min})/\text{min}\) ratio of pairwise distances falls from 101.9 at \(d = 2\) to 0.13 at \(d = 1000\), so fixed neighborhoods stop being local.
- Trees win at low dimension and lose at high dimension. Timing fit plus 200 queries at \(k = 5\) on \(n = 20000\) uniform points: at \(d = 5\) ball tree takes 0.007 seconds against brute 0.02, while at \(d = 50\) brute takes 0.007 against KD 0.196 (one run on an i9-12900K, sklearn 1.9.1).
Reproduce closed-book
From a blank file, implement brute-force kNN with uniform and distance weights and match sklearn on
X = [0, 1, 2, 5, 6] with y = [0, 0, 1, 1, 1] at query 2.5 and \(k = 3\). Make your tie rule explicit (lower training index wins), then reorder the training rows and show sklearn's uniform answer flip from 0 to 1. Rerun the scaling pair and report 0.47 unscaled against 0.995 standardized.Traps
- Tuning \(k\) on train error always picks \(k = 1\). Memorization looks perfect and generalizes worst, so tune \(k\) by cross-validation.
- Scaling before the split leaks test ranges into the train transform. Fit the scaler on train only and apply it to test.
algorithmautois not a promise of trees. Sparse input, high dimension or \(k\) above half of \(n\) silently selects brute force, so confirm with timing rather than the parameter name.
Practice
HoML Chapter 3, Exercise 1: MNIST classifier above 97 percent
Exercise solutions, Exercise 1: grid search KNeighborsClassifier over weights and n_neighbors on MNIST past 97 percent test accuracy
Fit on the standard train split and score the held-out test set. Narrow the grid before running it at full size.
Self-test
-
At query 2.5 with \(k = 3\), which third neighbor joins \(x = 2\) and \(x = 1\), and what does uniform voting predict?
\(x = 0\) and \(x = 5\) tie at distance 2.5. In the given order sklearn takes \(x = 0\), so votes are 1, 0, 0 and uniform predicts 0; with the rows reordered it takes \(x = 5\) and predicts 1. A tie at the \(k\)-th place makes the answer depend on data order, so state your rule. -
Why does the unscaled toy score 0.47 while the standardized one scores 0.995?
The nuisance feature spans 1000x the informative one, so Euclidean neighborhoods are chosen by noise. Standardizing restores the informative axis. -
The concentration ratio reads 101.9 at \(d = 2\) and 0.13 at \(d = 1000\). What breaks for kNN?
Relative distance contrasts vanish, so the nearest and farthest points sit almost equally far. Fixed-\(k\) neighborhoods cover non-local regions and the vote carries little signal. -
At \(n = 20000\) and \(d = 50\), which search algorithm wins and why?
Brute force at 0.007 seconds against 0.196 for KD-tree. Partitioning overhead and dimensionality defeat the trees while blocked matrix distance stays cheap.
Completion criterion
Stop when
Your kNN matches sklearn on the toy including the tie, your scaling rerun shows the collapse and the recovery, and the MNIST grid clears 97 percent.
Mark passed, then open 3.6 Only mark this when you can do it without notes.Leads to
- 3.6 Support vector machines: margins, hinge loss and slack Replace votes with margins on the same geometry.
- 3.7 Kernels, bandwidth and kernel matrix cost Smooth the vote with RBF similarity.
Comes after
- 4.3 PCA via SVD: directions, explained variance and sign ambiguityConnect variance concentration to distance behavior in high dimensions.
Resources for this unit
- scikit-learn - neighbors, SVMs, trees and ensembles Check official estimator constraints, complexity, preprocessing needs, missing-value behavior and probability caveats. Do not use library calls as the mechanism implementation.
- Probabilistic Machine Learning, Chapter 16: exemplar-based methods Read Sections 16.1 to 16.1.3 for the KNN decision rule, the curse of dimensionality with the growing-hypercube example, and the speed section on k-d trees, hashing and approximate search.
Also in this section
- Hands-On Machine Learning with Scikit-Learn and PyTorch - nonlinear classical models Read Chapters 3, 5 and 6 and the online Appendix C notebook as the first pass through performance measures, trees, ensembles and SVMs, running notebooks 03, 05 and 06 alongside. Vary depth, estimators, learning rate, k, C and RBF width under fixed splits.
- ISLP - tree-based methods and support vector machines Use Chapters 8 and 9 with their Python labs for the statistical account of trees, bagging, random forests, boosting and SVMs that the notebooks leave implicit, and for model-choice and feature-importance arguments.
- Deep-ML - tree, ensemble and kernel problems Use 138 Best Gini-Based Split, 20 Decision Tree Learning, 307 Bagging Classifier, 21 Pegasos Kernel SVM and 280 RBF Kernel as unit checks after the local implementation passes. Their tests were read in review; each card states what they pin, including tie and update-order conventions.
- XGBoost parameters and sklearn estimator interface Read the tree-booster parameter list for
eta, depth, sampling and regularization names and defaults, and the sklearn page for early stopping witheval_set. - LightGBM parameters Read
learning_rate,num_leaves,max_depth,min_data_in_leaf,feature_fraction,bagging_fractionwithbagging_freq,lambda_l2and early stopping defaults. - CatBoost common parameters and categorical features Read
iterations,learning_rate,l2_leaf_reg,depth,grow_policy,subsample,rsm,boosting_type,use_best_modelandone_hot_max_sizedefaults, plus native categorical handling.