Chapter 3 — Fundamental Algorithms

Now that we have our vocabulary and notation from Chapter 2, it's time to meet the workhorses. This chapter introduces five classic learning algorithms that every machine learning practitioner should know. Some are powerful on their own; others are the building blocks behind the most effective modern methods.

In this chapter you will learn:

• How linear regression fits a line (or hyperplane) to data, and why it has a one-shot math solution
• Why logistic regression is actually a classification model built on the sigmoid curve
• How decision trees split data using impurity, and why deep trees overfit
• How support vector machines maximize the margin and use the kernel trick for non-linear data
• How k-nearest neighbors classifies by looking at the closest training examples, and how k controls overfitting

3.1 Linear Regression

The idea. We have a set of labeled examples, each one a pair (x, y) where x is a feature vector and y is a real number (not a class label this time). We want a model that predicts y from x. Linear regression assumes the prediction is a linear combination of the features:

f(x) = w · x + b

Here w is a vector of weights (one per feature), " · " means a weighted sum, and b is a bias (intercept) number. The model is "parametrized" by w and b — once we find good values for them, we have our predictor.

The goal is different from the SVM we met in Chapter 1. There, the hyperplane was a decision boundary placed as far as possible from both classes. Here, the hyperplane should sit as close as possible to all the training points, so that when we read off a prediction for a new x, it lands near the true y.

Everyday analogy. Plot people's heights against their shoe size and you'll see an upward trend. Linear regression draws the single straight line through the "middle" of that cloud of dots — the line that, on average, is closest to every point.

The squared-error loss and empirical risk

How do we measure "close to all points"? We need a loss function — a penalty for a wrong prediction. Linear regression uses the squared error loss: (f(x) − y)^2. We square the difference between the prediction and the true target. Squaring does two nice things: it makes every penalty positive (so over- and under-predictions don't cancel out), and it punishes big errors much more than small ones.

The overall cost function is the average loss over all training examples, also called the empirical risk: the mean of (f(x_i) − y_i)^2 across all i. We want the w and b that make this average as small as possible.

Why a square and not the plain absolute value? The square is smooth — it has a continuous derivative everywhere — which lets us solve for the best w and b with simple algebra (a "closed-form" solution) instead of a slow numerical search.

The normal equations: a closed-form solution

Here's the beautiful part. Because the squared-error cost is a smooth, bowl-shaped function of w and b, its minimum sits exactly where the slope (gradient) is zero. Setting the derivatives to zero gives a system of linear equations called the normal equations, which we can solve directly with linear algebra:

w = (X^T X)^(−1) X^T y

(X is the matrix of all feature vectors with a column of 1s appended for the bias, ^T means transpose, and ^(−1) means inverse.) This is a closed-form solution: plug in the data, do one matrix inversion and two multiplications, and you're done — no looping, no learning rate, no epochs. That's a luxury most algorithms don't have.

scikit-learn's LinearRegression uses exactly this math under the hood. Below we'll do it both ways — let sklearn fit the line, then recompute w and b ourselves with numpy — and confirm they agree.

%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_regression
from sklearn.linear_model import LinearRegression

# Consistent, compact figures for the whole notebook
plt.rcParams["figure.figsize"] = (6, 4)
plt.rcParams["axes.grid"] = True

# Step 1 -- a small 1-feature regression dataset (100 points, one target)
X, y = make_regression(n_samples=100, n_features=1, noise=15.0, random_state=42)

# Step 2 -- fit a linear regression model (uses the normal equations internally)
model = LinearRegression()
model.fit(X, y)

# The learned parameters: w (slope) and b (intercept)
w = model.coef_[0]
b = model.intercept_
print(f"Learned slope     w = {w:.3f}")
print(f"Learned intercept b = {b:.3f}")

# Step 3 -- plot the data and the fitted line
line_x = np.linspace(X.min(), X.max(), 100).reshape(-1, 1)
line_y = model.predict(line_x)

plt.scatter(X, y, s=20, color="tab:blue", label="data")
plt.plot(line_x, line_y, color="tab:orange", lw=2, label=f"fit: y = {w:.2f}x + {b:.2f}")
plt.title("Linear Regression — the line that best hugs the data")
plt.xlabel("feature x")
plt.ylabel("target y")
plt.legend()
plt.show()

Learned slope     w = 45.785
Learned intercept b = 1.748

Reading the plot

The orange line is the model f(x) = w · x + b. Notice it runs through the middle of the blue cloud — that's the line that minimizes the average squared vertical distance to all 100 points. For any new x, we just read up to the line to get our prediction.

The model printed its w (slope) and b (intercept). Now let's recompute those ourselves with the normal equation and see that we get the same numbers.

# Recompute w and b with the normal equation:  w = (X^T X)^(-1) X^T y
# We augment X with a column of 1s so the bias b is solved at the same time.
X_aug = np.hstack([X, np.ones((X.shape[0], 1))])      # shape (100, 2): [x, 1]
w_normal = np.linalg.inv(X_aug.T @ X_aug) @ X_aug.T @ y

w_ne, b_ne = w_normal[0], w_normal[1]
print(f"Normal-equation slope     w = {w_ne:.3f}")
print(f"Normal-equation intercept b = {b_ne:.3f}")
print()
print(f"Match with sklearn?  slope diff = {abs(w_ne - w):.2e},  intercept diff = {abs(b_ne - b):.2e}")

Normal-equation slope     w = 45.785
Normal-equation intercept b = 1.748

Match with sklearn?  slope diff = 4.26e-14,  intercept diff = 1.33e-15

They match — exactly

The numbers from our hand-rolled normal equation agree with scikit-learn's to many decimal places (the tiny difference is just floating-point round-off). That's the closed-form solution in action: one matrix formula, no looping, no tuning.

Because the model is so simple and has so few parameters, linear regression rarely overfits — it can't wiggle to chase every training point. (A degree-10 polynomial regression, by contrast, can bend wildly to fit the noise and then fail badly on new data — that's overfitting, which we'll tackle in Chapter 5.)

3.2 Logistic Regression

Surprise: despite the name, logistic regression is a classification algorithm, not a regression. The name comes from statistics because its math resembles linear regression's. But its job is to sort examples into classes (we'll look at the binary case: two classes).

The problem. We still compute the linear combination w · x + b. The trouble is that w · x + b ranges from minus infinity to plus infinity, while a class label is just 0 or 1. We need to squeeze that unbounded score into the range (0, 1) so we can read it as a probability.

The fix is the sigmoid (a.k.a. logistic) function: σ(z) = 1 / (1 + e^(−z)). It takes any number z and maps it to a value between 0 and 1 with an S-shape. The full model is f(x) = 1 / (1 + e^(−(w·x+b))). If f(x) ≥ 0.5 we predict class 1; otherwise class 0. (The 0.5 threshold can be tuned — we'll revisit this in Chapter 5.)

Everyday analogy. Think of the sigmoid as a "soft switch." Instead of snapping abruptly from OFF (0) to ON (1), it smoothly ramps around z = 0. A very negative score is almost surely OFF; a very positive score is almost surely ON; near zero it's a coin flip.

# Plot the sigmoid function to build intuition
z = np.linspace(-7, 7, 200)
sigmoid = 1 / (1 + np.exp(-z))

plt.plot(z, sigmoid, color="tab:green", lw=2)
plt.axhline(0.5, color="gray", ls="--", lw=1)
plt.axvline(0, color="gray", ls="--", lw=1)
plt.title("The sigmoid (logistic) function — a soft switch")
plt.xlabel("z = w·x + b  (the raw score)")
plt.ylabel("σ(z)  (probability of class 1)")
plt.ylim(-0.05, 1.05)
plt.show()

Maximum likelihood, log-loss, and the decision boundary

How do we find the best w and b? Logistic regression doesn't minimize squared error. Instead it maximizes the likelihood of the training labels — it picks parameters that make the observed labels most plausible under the model.

The likelihood of all N labels is a product (because we treat the examples as independent): for each example we take f(x_i) when y_i = 1, or (1 − f(x_i)) when y_i = 0, and multiply them all together. That f^y · (1−f)^(1−y) trick just selects the right term depending on the label.

In practice we maximize the log-likelihood (a log turns the product into a sum, which is easier to work with): the sum over all examples of [ y_i · log f(x_i) + (1 − y_i) · log(1 − f(x_i)) ]. This is equivalent to minimizing the log-loss (a.k.a. cross-entropy).

Unlike linear regression, there is no closed-form solution here — we solve it iteratively with gradient descent, which we'll meet properly in Chapter 4.

The decision boundary is where f(x) = 0.5, which is exactly where w · x + b = 0 — a straight line (or hyperplane). Let's fit a logistic regression and visualize both the boundary and the probability landscape.

from sklearn.datasets import make_classification
from sklearn.linear_model import LogisticRegression

# A small 2-feature, 2-class dataset
X, y = make_classification(n_samples=200, n_features=2, n_redundant=0,
                           n_informative=2, n_clusters_per_class=1,
                           class_sep=1.5, random_state=42)

# Fit logistic regression (gradient descent under the hood)
clf = LogisticRegression(max_iter=200)
clf.fit(X, y)
print(f"Training accuracy: {clf.score(X, y):.3f}")

# Build a meshgrid over the feature space to show decision boundary + probabilities
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
                     np.linspace(y_min, y_max, 200))
grid = np.c_[xx.ravel(), yy.ravel()]
proba = clf.predict_proba(grid)[:, 1].reshape(xx.shape)

# Contour plot: color = predicted probability of class 1
plt.contourf(xx, yy, proba, levels=20, cmap="RdBu", alpha=0.7)
plt.colorbar(label="P(class 1)")
# Draw the 0.5 decision boundary in black
plt.contour(xx, yy, proba, levels=[0.5], colors="black", linestyles="--", linewidths=2)

plt.scatter(X[:, 0][y == 0], X[:, 1][y == 0], color="tab:blue", edgecolor="k", label="class 0")
plt.scatter(X[:, 0][y == 1], X[:, 1][y == 1], color="tab:orange", edgecolor="k", label="class 1")
plt.title("Logistic Regression — decision boundary & probability map")
plt.xlabel("feature 1")
plt.ylabel("feature 2")
plt.legend()
plt.show()

Training accuracy: 0.940

Reading the plot

• The dashed black line is the decision boundary — where the model is exactly 50/50. Points on the blue side are predicted class 0; on the red side, class 1.
• The color gradient shows the predicted probability of class 1. Near the orange cluster the probability is close to 1 (deep red); near the blue cluster it's close to 0 (deep blue). Right on the boundary it's around 0.5 — the model is least confident there.

So logistic regression doesn't just give a hard label; it gives a probability, which is useful when you need to weigh risks (e.g., "85% chance this email is spam" vs. just "spam").

3.3 Decision Tree Learning

A decision tree is a flowchart-like graph used to make decisions. At each branching node you inspect one feature: if its value is below a threshold you go left, otherwise you go right. You keep walking until you hit a leaf, which announces the predicted class. The neat part: a tree can be learned from data automatically.

How splits are chosen. At each node the algorithm searches every feature and every possible threshold, splits the data, and asks: did this split make the children "purer" than the parent? Impurity measures how mixed the labels are in a node. A node containing only one class is perfectly pure (impurity 0); a node split 50/50 is maximally impure.

Two common impurity measures, where p is the proportion of class 1 in the node:

• Entropy = −p · log(p) − (1−p) · log(1−p) — from information theory; measures uncertainty. It's 0 when pure and largest when 50/50.
• Gini impurity = 1 − p^2 − (1−p)^2 — the chance a randomly guessed label (using the node's class frequencies) is wrong. Also 0 when pure and largest at 50/50.

The algorithm picks the split with the biggest information gain (parent impurity minus the weighted child impurity).

Everyday analogy. Twenty Questions. Each question (split) tries to narrow the possibilities as fast as possible — you ask the question that best separates the remaining candidates.

# Compare entropy and Gini impurity as a function of the class-1 proportion p
p = np.linspace(0.001, 0.999, 200)

# Entropy (base-2 log, so it peaks at 1.0)
entropy = -p * np.log2(p) - (1 - p) * np.log2(1 - p)
# Gini impurity
gini = 1 - p**2 - (1 - p)**2

plt.plot(p, entropy, color="tab:red", lw=2, label="Entropy (base-2)")
plt.plot(p, gini, color="tab:purple", lw=2, label="Gini impurity")
plt.axvline(0.5, color="gray", ls="--", lw=1)
plt.title("Impurity peaks at 50/50 and is zero at the extremes")
plt.xlabel("proportion of class 1  (p)")
plt.ylabel("impurity")
plt.legend()
plt.show()

Reading the impurity plot + tree structure

Both curves are 0 at the extremes (a node of all one class is perfectly pure) and peak in the middle (a 50/50 node is the most mixed, the most useless for classification). The tree-growing algorithm greedily picks splits that push each node toward the pure extremes.

Why decision trees overfit. Nothing in the basic algorithm says "stop." Left unchecked, the tree keeps splitting until every leaf is pure — which means it can carve out a tiny box for every single training point, even the noisy ones. Such a tree memorizes the training set and usually fails on new data.

We control this with stopping rules (hyperparameters): limit the maximum depth d, require a minimum impurity decrease ε, or require a minimum number of samples per leaf. Restricting the depth is the simplest form of pruning. Let's see overfitting versus pruning side by side.

from sklearn.datasets import make_moons
from sklearn.tree import DecisionTreeClassifier

# A noisy, non-linear "two moons" dataset
X, y = make_moons(n_samples=200, noise=0.25, random_state=42)

# Two trees: one allowed to grow fully, one restricted to depth 3
tree_deep = DecisionTreeClassifier(random_state=42)              # no depth limit -> overfit
tree_pruned = DecisionTreeClassifier(max_depth=3, random_state=42)  # pruned

tree_deep.fit(X, y)
tree_pruned.fit(X, y)

print(f"Deep tree  : depth={tree_deep.get_depth()}, train acc={tree_deep.score(X, y):.3f}")
print(f"Pruned tree: depth={tree_pruned.get_depth()}, train acc={tree_pruned.score(X, y):.3f}")

# Meshgrid for decision boundaries
x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
xx, yy = np.meshgrid(np.linspace(x_min, x_max, 250),
                     np.linspace(y_min, y_max, 250))
grid = np.c_[xx.ravel(), yy.ravel()]

fig, axes = plt.subplots(1, 2, figsize=(11, 4.5))
for ax, tree, title in [(axes[0], tree_deep, "Deep tree (no limit) — overfits"),
                        (axes[1], tree_pruned, "Pruned tree (max_depth=3)")]:
    Z = tree.predict(grid).reshape(xx.shape)
    ax.contourf(xx, yy, Z, cmap="coolwarm", alpha=0.4)
    ax.scatter(X[:, 0][y == 0], X[:, 1][y == 0], color="tab:blue", edgecolor="k", s=20)
    ax.scatter(X[:, 0][y == 1], X[:, 1][y == 1], color="tab:red", edgecolor="k", s=20)
    ax.set_title(title)
    ax.set_xlabel("feature 1")
    ax.set_ylabel("feature 2")
plt.tight_layout()
plt.show()

Deep tree  : depth=8, train acc=1.000
Pruned tree: depth=3, train acc=0.910

Reading the plot

• The deep tree (left) carves the space into many small, jagged regions to surround every training point — including little islands around noisy points that are really the "wrong" class. Its training accuracy is ~1.00, but those wiggly boundaries won't generalize.
• The pruned tree (right, max_depth=3) produces a few clean, blocky cuts that capture the two-moon shape without chasing the noise. Its training accuracy is a bit lower, but it will usually do better on unseen test data.

This is the classic bias–variance trade-off: a deeper tree has lower bias (it can represent complex shapes) but higher variance (it fits the noise). Pruning trades a little bias for a big drop in variance.

3.4 Support Vector Machine

We met SVM briefly in Chapter 1. Here we fill in the two hard questions:

1. What if the data is noisy and no straight line can perfectly separate the classes?
2. What if the data is inherently non-linear (e.g., the boundary should be a circle)?

The margin. Recall that an SVM doesn't just draw any separating line — it draws the line with the widest gap (margin) between the two classes, placing it as far as possible from the nearest points (the support vectors). A bigger margin tends to generalize better.

Hard margin vs. soft margin. The original SVM (hard margin) requires perfect separation. To handle noise we introduce the hinge loss max(0, 1 − y_i (w·x_i − b)), which is 0 for points correctly classified outside the margin and grows for points on the wrong side. The soft-margin SVM minimizes a combination of a small-margin penalty and the average hinge loss:

C · ||w||^2 + (1/N) · Σ max(0, 1 − y_i (w·x_i − b))

The hyperparameter C balances the two goals:

• Large C: penalize misclassifications heavily → narrow margin, fewer training errors (risk overfitting).
• Small C: tolerate some errors → wider margin, smoother boundary (better generalization, maybe a few training mistakes).

Everyday analogy. Building a fence down the middle of a field with a few sheep that have wandered onto the wrong side. A small C says "leave a wide aisle and don't worry about a couple of stray sheep"; a large C says "build the fence tight around every sheep, even if the aisle gets skinny."

The kernel trick: separating non-linear data

What if no straight line works at all — say the classes form concentric rings? The trick: map the data into a higher-dimensional space where a flat hyperplane can separate them. A 2-D circle problem can become linearly separable in 3-D.

Doing that mapping explicitly would be expensive. The kernel trick avoids it: instead of transforming the points and then taking their dot product, we use a kernel function k(x, x') that computes the result of that dot product directly in the original space. Two favorites:

• Linear kernel k(x, x') = x · x' — no mapping; just a straight boundary.
• RBF (Gaussian) kernel k(x, x') = exp(−||x − x'||^2 / (2 σ^2)) — an effectively infinite-dimensional mapping that yields smooth, curvy boundaries. The width σ (scikit-learn's gamma) controls how curvy.

Let's compare a linear and an RBF SVM on a "circles" dataset, and see how C changes the RBF boundary.

from sklearn.datasets import make_circles
from sklearn.svm import SVC

# Concentric circles: NO straight line can separate these
X, y = make_circles(n_samples=200, noise=0.08, factor=0.5, random_state=42)

# Four models to compare: linear vs RBF, and two values of C
models = [
    ("linear, C=1", SVC(kernel="linear", C=1.0)),
    ("RBF, C=1",    SVC(kernel="rbf", C=1.0)),
    ("RBF, C=0.1",  SVC(kernel="rbf", C=0.1)),
    ("RBF, C=100",  SVC(kernel="rbf", C=100.0)),
]

x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
                     np.linspace(y_min, y_max, 200))
grid = np.c_[xx.ravel(), yy.ravel()]

fig, axes = plt.subplots(2, 2, figsize=(11, 9))
for ax, (label, clf) in zip(axes.ravel(), models):
    clf.fit(X, y)
    Z = clf.predict(grid).reshape(xx.shape)
    ax.contourf(xx, yy, Z, cmap="coolwarm", alpha=0.4)
    ax.scatter(X[:, 0][y == 0], X[:, 1][y == 0], color="tab:blue", edgecolor="k", s=18)
    ax.scatter(X[:, 0][y == 1], X[:, 1][y == 1], color="tab:red", edgecolor="k", s=18)
    ax.set_title(f"{label}  (train acc={clf.score(X, y):.2f})")
    ax.set_xlabel("feature 1")
    ax.set_ylabel("feature 2")
plt.tight_layout()
plt.show()

Reading the plot

• The linear kernel (top-left) is hopeless on concentric circles — it can only draw a straight cut, so it gets ~50% accuracy, basically guessing.
• The RBF kernel carves out a curved (here roughly ring-shaped) boundary that hugs the inner circle.
• C = 0.1 (small) gives a smooth, generous boundary; C = 100 (large) tightens the boundary around the training points, risking overfitting to noise. The middle value, C = 1, is usually a sensible default.

So the kernel gives SVM its non-linear superpower, and C dials how aggressively it fits the training data.

3.5 k-Nearest Neighbors

kNN is delightfully simple and non-parametric: it doesn't build a compact formula and throw away the data — it keeps all the training examples in memory. When a new example x arrives, it finds the k closest training examples and takes a majority vote (for classification) or an average (for regression).

Closeness needs a distance metric. The usual choice is Euclidean distance — the straight-line distance, the square root of the summed squared differences of each feature. Other options: cosine similarity (cares about direction, not magnitude — popular for text), Chebyshev, Mahalanobis, and Hamming. The distance metric and k are hyperparameters you choose before running the algorithm.

The role of k:

• k = 1: every point gets the label of its single nearest neighbor → the boundary is super jagged and the model overfits (one noisy neighbor can flip a prediction).
• Large k: voting over many neighbors smooths the boundary, but too large and you underfit (the model just predicts the majority class everywhere).
• Odd k avoids tie votes in binary classification.

Everyday analogy. You move to a new city and want to guess whether a random house is "expensive." kNN says: look at the k houses nearest to it and take the majority opinion. Look at only one neighbor and a single oddball throws you off; look at 30 and you get the general vibe of the neighborhood.

from sklearn.neighbors import KNeighborsClassifier

# Two moons again, noisy
X, y = make_moons(n_samples=200, noise=0.25, random_state=42)

# k=1 (very flexible) vs k=15 (smooth)
x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
xx, yy = np.meshgrid(np.linspace(x_min, x_max, 250),
                     np.linspace(y_min, y_max, 250))
grid = np.c_[xx.ravel(), yy.ravel()]

fig, axes = plt.subplots(1, 2, figsize=(11, 4.5))
for ax, k in [(axes[0], 1), (axes[1], 15)]:
    clf = KNeighborsClassifier(n_neighbors=k)
    clf.fit(X, y)
    Z = clf.predict(grid).reshape(xx.shape)
    ax.contourf(xx, yy, Z, cmap="coolwarm", alpha=0.4)
    ax.scatter(X[:, 0][y == 0], X[:, 1][y == 0], color="tab:blue", edgecolor="k", s=20)
    ax.scatter(X[:, 0][y == 1], X[:, 1][y == 1], color="tab:red", edgecolor="k", s=20)
    ax.set_title(f"kNN  k={k}  (train acc={clf.score(X, y):.2f})")
    ax.set_xlabel("feature 1")
    ax.set_ylabel("feature 2")
plt.tight_layout()
plt.show()

Reading the plot

• k = 1 (left): each training point is surrounded by its own little colored island. The boundary is fragmented and clearly chases individual noisy points — classic overfitting.
• k = 15 (right): the boundary is smooth and captures the two-moon shape cleanly.

The catch: k = 1 has perfect training accuracy (every point is its own nearest neighbor), which is misleading. To judge fairly we must check held-out test data, not the data we trained on.

from sklearn.model_selection import train_test_split

# Split the moons into train and test sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.4, random_state=42)

ks = range(1, 40, 2)            # odd k from 1 to 39
train_acc = []
test_acc = []
for k in ks:
    clf = KNeighborsClassifier(n_neighbors=k)
    clf.fit(X_train, y_train)
    train_acc.append(clf.score(X_train, y_train))
    test_acc.append(clf.score(X_test, y_test))

plt.plot(ks, train_acc, "o-", color="tab:blue", label="training accuracy")
plt.plot(ks, test_acc, "s-", color="tab:orange", label="test accuracy")
plt.title("kNN: the bias–variance trade-off as k grows")
plt.xlabel("k (number of neighbors)")
plt.ylabel("accuracy")
plt.legend()
plt.show()

Reading the plot

This curve is a textbook bias–variance picture:

• Small k (left): training accuracy is ~100%, but test accuracy is poor — the model is too flexible and overfits the noise (high variance).
• Large k (right): both accuracies drop as the model averages over too many neighbors and underfits (high bias) — eventually it just predicts the majority class.
• The sweet spot is somewhere in the middle, where test accuracy peaks. This is why k is a hyperparameter we tune (Chapter 5) rather than guess.

Notice the training and test curves separate: training accuracy is an optimistic measure. The number we actually care about is the test accuracy — how the model does on data it has never seen.

The five algorithms at a glance

Algorithm	Task	Model shape	How it's trained	Key hyperparameters
Linear regression	regression	straight line / hyperplane	closed form (normal equations)	(almost none)
Logistic regression	classification	linear boundary + sigmoid	gradient descent on log-loss	(regularization C)
Decision tree	both	axis-aligned splits	greedy impurity reduction	max depth, min split
SVM	classification	max-margin; linear or kernel	quadratic programming	C, kernel, gamma / σ
kNN	both	memory-based, no formula	none — just store data	k, distance metric

A useful rule of thumb: linear / logistic regression are your simple, fast, low-overfit baselines; decision trees are interpretable but overfit easily; SVMs with an RBF kernel are powerful for non-linear boundaries; kNN is dead-simple and needs no training, but slows down at prediction time on large datasets.

Key Takeaways

• Linear regression fits f(x) = w·x + b by minimizing the average squared error; thanks to the smooth square, it has a closed-form solution (the normal equations) — no iteration needed.
• Logistic regression is classification, not regression: the sigmoid squeezes a linear score into a probability, and training maximizes likelihood (equivalently minimizes log-loss) via gradient descent.
• Decision trees split data to reduce impurity (entropy or Gini); left uncontrolled they overfit by memorizing noise, so we prune with depth limits.
• SVM maximizes the margin; the soft-margin version with hinge loss and hyperparameter C handles noise, and the kernel trick lets it separate non-linear data without explicit high-dimensional computation.
• kNN classifies by majority vote of the k nearest training points; small k overfits, large k underfits, and we pick k by checking held-out test accuracy.
• All five illustrate the same tension: fit the training data well (low bias) without chasing the noise (low variance).

What's Next

In Chapter 4 — Anatomy of a Learning Algorithm, we'll open up the "engine" inside these models — how an algorithm is really just an objective function plus an optimizer (like gradient descent) — and see how the same recipe powers them all.

Exercises

These exercises cover the five fundamental algorithms from Chapter 3: linear regression, logistic regression, decision trees, SVM, and k-NN. Try each problem before peeking at the hint.

1. (Conceptual) Why does linear regression have a closed-form solution (the normal equations) while logistic regression does not? Which property of the squared-error loss makes that possible? Hint: squared error is a smooth, bowl-shaped function whose gradient is linear in w; the sigmoid makes log-loss non-linear, so there's no zero-derivative formula to solve.
2. (Conceptual) The chapter says linear regression "rarely overfits," yet a degree-10 polynomial regression can fail badly on new data. Explain the difference. Hint: few parameters ⇒ low capacity; polynomial features add many parameters that can wiggle to chase noise.
3. (Conceptual) Why is logistic regression a classification algorithm despite its name, and what exactly does the sigmoid accomplish? Hint: it squeezes the unbounded score w·x+b into the (0,1) range as a probability; thresholding at 0.5 yields the class.
4. (Conceptual) Define impurity and compare entropy with Gini impurity. At what class proportion p is each maximized, and what value do they take at a perfectly pure node? Hint: both are 0 when pure and peak at p = 0.5 (the 50/50, most-mixed node).
5. (Conceptual) Why does an unpruned decision tree overfit, and name two hyperparameters that rein it in. Hint: it keeps splitting until every leaf is pure, carving tiny boxes around noisy points; control it with max_depth, min_samples_leaf, or min_impurity_decrease.
6. (Conceptual) Write the soft-margin SVM objective and explain what the hyperparameter C controls (large C vs small C). Hint: C·‖w‖² + average hinge loss; large C ⇒ narrow margin, few training errors (overfit risk); small C ⇒ wide margin, smoother boundary (better generalization).
7. (Conceptual) How does the kernel trick let an SVM separate non-linear data without explicitly mapping points to a higher-dimensional space? Contrast the linear and RBF kernels. Hint: k(x,x') returns the high-dimensional dot product computed in the original space; RBF (with gamma) yields smooth curvy boundaries, linear gives a straight cut.

Hands-On Coding Problems

8. (Coding) Fit LinearRegression on make_regression(n_samples=100, n_features=1, noise=15, random_state=42), print the slope and intercept, then recompute w and b yourself with the normal equation w = (XᵀX)⁻¹Xᵀy and confirm they match. Hint: append a column of ones to X for the bias term; use np.linalg.inv or np.linalg.solve.
9. (Coding) Fit LogisticRegression on a 2-feature make_classification dataset and plot the decision boundary w·x+b = 0. Hint: clf.coef_[0] and clf.intercept_[0]; boundary is -(w0*xx + b)/w1.
10. (Coding) Show decision-tree overfitting: fit an unrestricted DecisionTreeClassifier() and a pruned one (max_depth=3) on make_moons(noise=0.25, random_state=42), print both training accuracies, and plot both decision regions. Hint: the unrestricted tree should hit ~1.00 train accuracy with jagged regions; depth=3 gives cleaner cuts.
11. (Coding) Implement entropy(p) and gini(p) and evaluate them at p = 0.5, 0.9, and 1.0. Confirm both equal 0 at a pure node (p = 1) and peak at p = 0.5. Hint: entropy = −p log p − (1−p) log(1−p); gini = 1 − p² − (1−p)².
12. (Coding) Compare SVM kernels on make_circles(noise=0.15, factor=0.5, random_state=42): fit SVC(kernel="linear") and SVC(kernel="rbf"), print both accuracies. Hint: the linear kernel should sit near ~0.5 (it can't carve a ring); RBF should succeed.
13. (Coding) Tune SVM C: on the same circles data, fit RBF SVC with C = 0.1, 1, and 100, print each training accuracy, and comment on which risks overfitting. Hint: large C tightens the boundary around the training points.
14. (Coding) Plot the k-NN bias–variance curve: split make_moons(noise=0.25, random_state=42) into train/test, loop k from 1 to 40 (use odd k), record train and test accuracy of KNeighborsClassifier, and plot both vs k. Hint: train_test_split; small k → high train / low test (overfit); find the sweet spot where test accuracy peaks.

# Exercise 8: LinearRegression vs the normal equation
import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.datasets import make_regression

X, y = make_regression(n_samples=100, n_features=1, noise=15, random_state=42)
reg = LinearRegression().fit(X, y)
print("sklearn slope/intercept:", reg.coef_[0], reg.intercept_)

# TODO: solve the normal equation w = (X^T X)^-1 X^T y
# Hint: stack a column of ones onto X for the bias, then use np.linalg.inv or np.linalg.solve
w_normal = np.array([0.0, 0.0])  # placeholder [slope, intercept]
print("normal equation:", w_normal)

# Exercise 9: LogisticRegression decision boundary
import numpy as np
import matplotlib.pyplot as plt
from sklearn.linear_model import LogisticRegression
from sklearn.datasets import make_classification

X, y = make_classification(n_samples=120, n_features=2, n_redundant=0,
                           n_informative=2, n_clusters_per_class=1, random_state=42)

# TODO: fit LogisticRegression(max_iter=200)
clf = None  # placeholder

# TODO: plot the points and the decision boundary w.x + b = 0
# Hint: w = clf.coef_[0], b = clf.intercept_[0]; boundary: -(w[0]*xx + b)/w[1]
plt.show()

# Exercise 10: decision-tree overfitting vs pruning
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_moons

X, y = make_moons(n_samples=200, noise=0.25, random_state=42)

# TODO: fit an unrestricted tree and a pruned tree (max_depth=3)
deep = None      # placeholder
pruned = None    # placeholder

# TODO: print both .score(X, y) and plot both decision regions on a meshgrid
plt.show()

# Exercise 11: entropy and Gini impurity
import numpy as np

def entropy(p):
    # TODO: return -p*log(p) - (1-p)*log(1-p); handle p in {0,1} (return 0)
    return 0.0  # placeholder

def gini(p):
    # TODO: return 1 - p**2 - (1-p)**2
    return 0.0  # placeholder

for p in [0.5, 0.9, 1.0]:
    print(f"p={p}: entropy={entropy(p):.4f}, gini={gini(p):.4f}")

# Exercise 12: linear vs RBF SVM on concentric circles
from sklearn.svm import SVC
from sklearn.datasets import make_circles

X, y = make_circles(n_samples=200, noise=0.15, factor=0.5, random_state=42)

# TODO: fit SVC(kernel="linear") and SVC(kernel="rbf"), print both accuracies
linear_acc = 0.0  # placeholder
rbf_acc = 0.0     # placeholder

print("linear kernel accuracy:", linear_acc)
print("rbf kernel accuracy   :", rbf_acc)

# Exercise 13: tuning SVM C
from sklearn.svm import SVC
from sklearn.datasets import make_circles

X, y = make_circles(n_samples=200, noise=0.15, factor=0.5, random_state=42)

for C in [0.1, 1, 100]:
    # TODO: fit SVC(kernel="rbf", C=C) and print training accuracy
    acc = 0.0  # placeholder
    print(f"C={C}: train accuracy={acc}")

# TODO: add a comment on which value of C risks overfitting

# Exercise 14: k-NN bias-variance curve
import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split

X, y = make_moons(n_samples=300, noise=0.25, random_state=42)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=42)

ks = range(1, 41, 2)  # odd k
train_acc = []
test_acc = []

for k in ks:
    # TODO: fit KNeighborsClassifier(n_neighbors=k), append .score on train and test
    train_acc.append(0.0)  # placeholder
    test_acc.append(0.0)   # placeholder

# TODO: plot train_acc and test_acc vs ks; mark the k with the best test accuracy
plt.show()