The deck now opens the third model of the lecture: k-Nearest Neighbors. kNN is the archetype of instance-based learning — the category from Chapter 8's taxonomy where the model compares new data points to known ones instead of detecting a pattern in the training data:
max_depth to grow, no weights to learn — the whole model is the data;k — the number of neighbors consulted. Small k follows the nearest point (sensitive to noise); large k averages over a neighborhood (smoother, but can blur a sharp boundary).Chapter 9's rule applies here too: understand the dynamics, not only the result. For kNN the dynamics are governed by distance — and distance depends on the scale of the features. That is the subject of the next four sections.
As with max_depth in Chapter 9, the deck stops before running anything and asks: what do you expect?
Expectation: every point takes the label of its single nearest neighbor. The boundary will be maximally detailed — jagged regions that hug the training points, with every isolated flower owning a private territory. Sensitive to noise: one atypical point creates a bubble around itself.
Expectation: each point consults a neighborhood of 10 and takes the majority label. The boundary becomes smoother — small islands disappear because no single neighbor can swing a vote of ten. The price: a genuinely isolated point may be overruled by its neighbors.
There is a second expectation the deck sets up quietly: normalization. The next two slides run the same model (k=1) twice — once on the raw petal features and once after min-max normalization — to show that the boundary changes purely because the distance function changed.
from sklearn.neighbors import KNeighborsClassifier
knn = plot_boundary(KNeighborsClassifier(n_neighbors=1), "knn_cplot", norm=False)Without normalization, the two petal features live on different scales: petal length ranges up to ~6.9 cm, petal width only up to ~2.5 cm. Euclidean distance therefore measures almost only petal length — the width contributes little. The effect:
This is the first dynamics lesson of the chapter: kNN has no internal notion of feature importance — the scale of the features is the importance, silently encoded in the distance.
knn = plot_boundary(KNeighborsClassifier(n_neighbors=1), "knn_cplot", norm=True)Min-max normalization rescales each feature to the range [0, 1] before the distances are computed:
x' = (x - min(x)) / (max(x) - min(x))Now both features span the same interval, and Euclidean distance weighs them equally. The k=1 boundary changes shape: regions that were pure vertical strips (Plate 11.1, left) become two-dimensional — the width of a flower finally counts in the nearest-neighbor ranking.
The deck's point is not that one boundary is "better" — it is that the model's behavior is a function of the preprocessing. Two runs with identical data, model and k produce different regions solely because the features were rescaled. When the exam asks "why does the boundary change?", the answer is normalization, not a different algorithm.
knn = plot_boundary(KNeighborsClassifier(n_neighbors=10), "knn_cplot", norm=True)Keeping normalization and raising k to 10 shows the second dynamics: the majority vote smooths the boundary.
The widget below computes true k-NN decisions on the 150 real iris flowers (petal plane). Move k and toggle normalization to reproduce the deck's three plots — and the ones in between.
As with the decision tree, the deck closes the kNN story with a training-vs-test accuracy plot over k = 1..9. But the loop as printed in the deck contains copy-paste errors — and the lecture's own disclaimer (§4 of Chapter 8) says it out loud: do not rely on external code without knowing what the code is doing. Here is exactly what the deck prints (slide 49):
# Prepare to store max_depth values and corresponding accuracies
k_s = range(1, 10)
train_accuracies, test_accuracies = [], []
for k in k_s: # Train decision trees with increasing max_depth
knn = KNeighborsClassifier(n_neighbors=k)
knn.fit(X_train, y_train)
train_acc = accuracy_score(y_train, clf.predict(X_train)) # Compute accuracy for training set
test_acc = accuracy_score(y_test, clf.predict(X_test)) # Compute accuracy for test set
train_accuracies.append(train_acc)
test_accuracies.append(test_acc)
# Plot accuracies
plt.plot(max_depths, train_accuracies, label="Training", marker='o')
plt.plot(max_depths, test_accuracies, label="Test", marker='o')
plt.xticks(max_depths)
plt.xlabel("k"); plt.ylabel("Accuracy"); plt.legend(); plt.grid(True)Verified against the source deck (slide 49), the loop above cannot produce the curve it claims, for three independent reasons:
clf.predict(X_train) / clf.predict(X_test) inside a loop that fits knn: clf is the decision tree from slide 26, still in scope — so the two accuracy lines do not measure the kNN at all, and they are constant across the loop (the tree does not change while k does);plt.plot(max_depths, ...) and plt.xticks(max_depths): max_depths is the decision-tree loop variable from slide 36, not defined here — the plot call would raise NameError;This is precisely the kind of bug the lecture warns about: a plausible-looking plot that, if never questioned, teaches the wrong lesson. The corrected loop measures what the section intends:
k_s = range(1, 10)
train_accuracies, test_accuracies = [], []
for k in k_s:
knn = KNeighborsClassifier(n_neighbors=k)
knn.fit(X_train, y_train)
train_acc = accuracy_score(y_train, knn.predict(X_train))
test_acc = accuracy_score(y_test, knn.predict(X_test))
train_accuracies.append(train_acc)
test_accuracies.append(test_acc)
plt.plot(k_s, train_accuracies, label="Training", marker='o')
plt.plot(k_s, test_accuracies, label="Test", marker='o')
plt.xticks(k_s)
plt.xlabel("k"); plt.ylabel("Accuracy"); plt.legend(); plt.grid(True)The table below gives the real values of the corrected loop on the deck's setup (seed 42, test size 0.2), for the raw features exactly as the deck's split provides them, and after min-max normalization:
| k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| Raw · Training | 1.0 | 0.9667 | 0.95 | 0.9583 | 0.9667 | 0.9667 | 0.975 | 0.9583 | 0.9667 |
| Raw · Test | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 0.9667 | 1.0 | 1.0 |
| Min-max · Training | 1.0 | 0.9667 | 0.9583 | 0.9583 | 0.9583 | 0.9583 | 0.9667 | 0.9667 | 0.9667 |
| Min-max · Test | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 |
Read honestly: on this clean dataset, kNN is excellent across all k — the test accuracy is 1.0 almost everywhere, and even k=7 (raw) only drops one flower. The differences between k values that the boundary plots make so visible (jagged vs smooth) barely move the score. The boundary picture, not the number, is where the model's dynamics live — exactly the lecture's rule.
Hover the markers for the exact values.
The deck switches model family: from distances to weights. The perceptron is the historical starting point of neural networks (and the bridge to Chapter 7's networks):
sign(w₍ + w₁x₁ + w₂x₂ + …);The deck's question is immediate and sharp: "Perceptron is binary classifier. How can we use it in Iris?" Iris has three classes, and the perceptron speaks in two. The next slide gives the answer.
The strategy is One Versus All (OVA):
OVA provides a way to use binary classification for a series of yes or no predictions across multiple possible labels. Given a classification problem with N possible solutions, an OVA solution consists of N separate binary classifiers — one binary classifier for each possible outcome.
The deck's example is fruit recognition: four recognizers, each answering a different question — is this an apple? is this an orange? is this a banana? is this a grape? During training, each binary classifier learns its own yes/no question; at prediction time, the answers are combined: pick the prediction of the non-zero class which is the most certain, and use the argmax of these scores (the class index with the largest score) to predict a class.
Real OVA perceptrons trained on the petal plane. Click anywhere: each recognizer reports its score, and the argmax picks the class.
from sklearn.linear_model import Perceptron
perceptron = plot_boundary(Perceptron(random_state=seed), "perceptron_cplot")With OVA under the hood, the perceptron learns three straight boundaries on the petal plane. The result is the classic linear picture: three half-planes meeting in the middle, with the versicolor/virginica frontier as the fragile one — the two species overlap enough that no single line separates them perfectly.
Measured on the deck's setup (seed 42), the perceptron is honest about this weakness: training accuracy 0.675, test accuracy 0.6333 — far below the tree, the forest and the kNN, all of which reached 1.0 on the same split. The straight-line family simply cannot draw the curved boundary that the petal data needs. This is a feature, not a failure: it is the model's dynamics made visible, and it is why the next slide and the MLP exist.
perceptron = plot_boundary(Perceptron(random_state=1), "perceptron_cplot")Only the seed changes — and the boundary moves. On this run the perceptron scores training 0.9167, test 0.9: a completely different model, from the same code.
The perceptron's training is order-dependent: samples are presented in a shuffled sequence (controlled by random_state), and each mistake updates the weights. Different orders walk different paths to (possibly different) solutions — and when the data is not linearly separable, as versicolor vs virginica is, the final boundary depends on where the walk stopped. The decision tree had tie-breaking randomness (Chapter 9); the perceptron has learning randomness: the same hyperparameters, a different seed, a different model. Compare the two boundaries in the widget below by re-training.
This widget trains real OVA perceptrons on the petal plane. Press the button to re-train with a different seed and watch the three straight boundaries (and the accuracy) change.
from sklearn.neural_network import MLPClassifier
mlp = plot_boundary(MLPClassifier(hidden_layer_sizes=(10, 20), random_state=seed, max_iter=1000), "mlp_cplot")The multi-layer perceptron (MLP) adds hidden layers between input and output — here two layers with 10 and 20 neurons — and each neuron applies a nonlinearity. That single change removes the straight-line limitation:
max_iter=1000 is not decoration: gradient-descent training needs many passes to converge, and the default (200) usually ends with a convergence warning.This widget trains a real 2-8-3 network (two inputs, one hidden layer of 8 neurons, softmax output) on the petal plane by gradient descent. Watch the boundary become nonlinear as training proceeds.
The deck closes the lecture with the exercise that the exam's style anticipates:
The exercise is deliberately open — it asks you to run the whole workflow of Chapters 8-10 on a new dataset. The deck's rules apply: do not stop at the first good result; question the pipeline; be able to explain every line.
Wine: 178 samples, 13 features, 3 classes, split 142/36. A plain decision tree with random_state=42 reaches test accuracy 0.9444 (34/36) at depth 3-4. The most relevant features are flavanoids (0.42), color_intensity (0.39) and proline (0.17) — three features carry nearly all the decision power. Tuning max_depth (and optionally min_samples_leaf) does not improve on 0.9444 on this split; a random search over the forest, as in Chapter 10, will typically match or tie it. The honest lesson: on a small clean dataset the model choice moves the score less than the understanding of the features.
kNN does not extract a pattern from training: the model is the stored training set, and prediction compares new points to the stored ones by distance (the instance-based category of Chapter 8). Its hyperparameter is k, the number of nearest neighbors whose labels vote for the prediction.
Only the distance function changes. Petal length spans ~0-6.9 cm while petal width spans ~0-2.5 cm, so raw Euclidean distance is dominated by petal length and the boundary is mostly vertical strips. Min-max normalization rescales each feature to [0, 1], both features contribute equally to the distance, and the boundary becomes genuinely two-dimensional. Same model, same data, same k — different preprocessing, different behavior.
The majority vote of 10 neighbors smooths the boundary: private bubbles around isolated points disappear and regions follow the data clouds. The trade-off is that genuinely informative isolated structure is also smoothed away — with very large k the boundary stops following the data (the kNN analogue of underfitting).
The loop fits knn but evaluates clf — the decision tree from earlier, still in scope — so the "kNN" accuracies are the tree's and constant across k. The plotting lines also use max_depths (undefined here; a NameError) instead of k_s. Fix: call knn.predict(...) and plot with k_s/xticks(k_s). This is the deck's own warning made concrete: code that looks right but teaches the wrong lesson if never questioned.
OVA trains N binary classifiers for N classes, each answering one yes/no question (setosa vs rest, versicolor vs rest, virginica vs rest). At prediction time each recognizer outputs a score, and the final class is argmax of the scores — the most certain yes wins. scikit-learn applies OVA automatically for multiclass.
Perceptron training is order-dependent: samples are shuffled (controlled by random_state) and each mistake updates the weights, so different orders follow different paths. When classes are not linearly separable (versicolor vs virginica), the final line depends on where the walk stopped. On the deck's split: seed 42 → test 0.6333, seed 1 → test 0.9 — same code, different models.
The MLP adds hidden layers (here 10 and 20 neurons) with nonlinearities, so its boundary is curved instead of straight. On the deck's setup: perceptron test 0.6333, MLP (10, 20, max_iter=1000) test 0.9333, training 0.9583. The MLP closes most of the gap to the tree/forest/kNN (1.0) but not all: even a flexible network does not perfectly capture the iris clouds.
Load load_wine() (178 samples, 13 features, 3 classes), split with train_test_split(..., test_size=0.2, random_state=42), train a DecisionTreeClassifier, then vary hyperparameters (max_depth, min_samples_leaf; or a random forest search as in Chapter 10). Reference values: best test accuracy 0.9444 at depth 3-4; most relevant features flavanoids, color_intensity, proline (together ≈0.98 of the importance).