Fatal Error ClubFatal Error
Roadmap

Week 5 · Classical ML

KNN, decision trees, random forests

01

One line is not enough

Logistic regression drew one line, or one plane, through the data, then cut it with a threshold. That works until the true boundary bends around a cluster, or curves between two groups that overlap. Tonight, three more ways to sort points into buckets: looks at who is nearby. ask yes or no questions. grows many trees and votes. Same goal every time, inputs to the correct label, three different shapes for the boundary.

02

K-Nearest Neighbors

Drop a new point on the plane. Find the closest training points by straight line distance, then let them vote. Whichever label wins the majority becomes the prediction. No line to fit and no weights to train, the training data itself is the model.

y^=majority of k nearest labels\hat{y} = \text{majority of } k \text{ nearest labels}

K-nearest neighbors

Tap the plane. The k nearest train points vote.

3
Vote → class 1
03

Distance needs scale

KNN picks neighbors by distance, so the units you use matter. Hours studied runs from 0 to 10. Account balance runs from 0 to 5000. Raw Euclidean distance just adds the numbers together, which means a 500 dollar gap in balance looks the same as a 500 hour gap in study time, and nobody studies 500 hours. In practice, the balance axis is so much bigger that it completely drowns out the study axis. Your nearest neighbors end up being whoever has a similar bank account, not whoever studied the same amount.

every feature before measuring: subtract the mean, divide by the spread. Both axes now live on the same scale. A one-unit gap in study time counts exactly as much as a one-unit gap in balance, so distance finally reflects what actually predicts pass or fail.

PassFail
024681001k2k3k4k5kHOURSBALANCE00.250.50.75100.250.50.751HOURS · STDBALANCE · STD

Predicted: Fail

04

Decision Trees

A different idea: instead of measuring distance, ask a sequence of yes or no questions about the features. Hours studied above five? Sleep above six hours? Each answer splits the data into two smaller groups, and each new group gets asked its own next question. No distance, no scaling, just questions, one at a time.

05

Choosing the best question

Not every question is equally good. A weak question splits the data into two groups that are still close to a coin flip of pass and fail. A strong question splits it into two groups that are mostly one label. measures how mixed a group is: zero when every row shares a label, highest at a fifty-fifty mix. At each step, the tree tries every available question, keeps the one that drops entropy the most, and repeats on each new group.

Entropy

H=−∑pilog⁡2piH = -\sum p_i \log_2 p_i
06

Depth is a dial, not a free lunch

One split barely captures the pattern: both train and holdout agreement stay low and close together. Two splits push both up at once, the tree is still learning the real shape of the data. Keep going past that and train agreement keeps climbing while holdout stalls or drops hard: the tree has started drawing a rectangle around every quirk in the training data, including the noise. Same trap as week two: the training points get memorized while the held out points start to disagree.

1
Train agreement73%
Holdout agreement75%

Still aligned at this depth.

07

Random Forest

One deep tree memorizes. So do not train one deep tree, train many, each on a different draw of the data and a random subset of features, then let them vote. Every tree still overfits its own sample, but in a different, uncorrelated way, so the mistakes cancel out on average.

Tap the plane to place a query. 5 slightly different trees each cast a vote, then the forest takes the majority.

Tree 11
Tree 21
Tree 31
Tree 41
Tree 51
Majority · 5 of 5 vote class 1Forest → class 1

Three new ways to draw a boundary tonight: neighbors that vote by distance, a tree that asks yes/no questions, a forest that averages many trees. None of them fit a single line, and all three can still overfit if you let them. Next week: the metrics that catch a model when accuracy looks great but the model isn't.