Machine Learning

Machine learning is the study of algorithms that improve their performance on a task by using data rather than by being explicitly programmed with rules. A widely used framing, due to Tom Mitchell, is operational: a program learns from experience E with respect to a task T and a performance measure P if its performance on T, measured by P, improves with E. For a spam filter, T is labeling email as spam or not, E is a corpus of past emails with known labels, and P is the fraction classified correctly on new mail.

The three ingredients of a learning method

Almost every method in this course is assembled from three parts, and naming them keeps your thinking clear:

• The hypothesis class (or model family) is the set of candidate functions we are willing to consider, for example all straight lines, or all decision trees of depth 4. It encodes our assumptions about the world.
• The loss function measures how wrong a single prediction is. Averaging it over data gives a cost (or risk) we want to make small.
• The learning algorithm (the optimizer) searches the hypothesis class for the member with the lowest cost on the training data.

Learning, then, is optimization guided by data: pick a family, define what "wrong" means, and search for the best member.

The real goal is generalization

It is tempting to think the aim is a tiny error on the data we already have. It is not. A lookup table that memorizes every training example has zero training error and is useless on anything new. The true target is generalization: low expected loss on unseen data drawn from the same distribution. We estimate that expected loss by holding out a test set the model never sees during training. The central tension of the whole field is that we can only minimize error on data we have, while we care about error on data we do not.

Formal setup and notation

We write a training set of n examples as pairs, where each input is a feature vector x with d components and (in supervised learning) each has a label or target y. We assume the pairs are drawn independently from an unknown but fixed distribution. A model is a function that maps an input x to a prediction. This i.i.d. (independent and identically distributed) assumption is what makes a test-set estimate trustworthy: past and future come from the same source.

Training data: (x_1, y_1), ..., (x_n, y_n),  each x in R^d
Model:         f_theta(x) with parameters theta
Empirical risk (training cost):
    J(theta) = (1/n) * sum over i of  loss( f_theta(x_i), y_i )
Goal: choose theta so that the EXPECTED loss on new (x, y) is small.

Every algorithm ahead is a specific choice of the hypothesis class and loss, plus a way to minimize J. Keeping generalization in view, rather than raw training error, is what separates machine learning from mere curve-fitting.

Machine learning problems fall into a few broad families, separated mainly by what information the training data carries. The two you will use most are supervised and unsupervised learning.

Supervised learning

In supervised learning, every training example comes with a correct answer, the label y. The algorithm learns a mapping from inputs to labels so it can predict the label of new, unlabeled inputs. It is "supervised" because the labels act like an answer key during training. Supervised tasks split by the type of label:

• Classification: the label is a category from a finite set. Is this tumor benign or malignant? Which of ten digits is in this image? The output is discrete.
• Regression: the label is a continuous number. What will this house sell for? What temperature tomorrow? The output is real-valued.

Most of this course, linear and logistic regression, trees, forests, and SVMs, lives in the supervised world.

Unsupervised learning

In unsupervised learning, there are no labels: only the inputs x. The goal is to discover structure hidden in the data itself. Two staple tasks are:

• Clustering: group similar examples together, for instance segmenting customers into behavioral types. k-means, later in the course, does this.
• Dimensionality reduction: re-express high-dimensional data in fewer dimensions while preserving what matters, for visualization or noise removal. Principal component analysis (PCA) does this.

Because there is no answer key, unsupervised results are harder to score objectively; we judge them by usefulness and by proxy measures of structure.

A quick comparison and the middle ground

Other paradigms round out the map. Semi-supervised learning uses a few labels plus many unlabeled points. Reinforcement learning learns from a reward signal earned by taking actions in an environment, rather than from fixed labeled examples. Knowing which family a problem belongs to is the first decision you make, because it determines which algorithms are even applicable.

Worked classification

Consider three problems. Predicting whether a credit-card transaction is fraudulent is supervised classification (discrete label: fraud or not). Predicting the dollar amount of next month's sales is supervised regression (continuous label). Grouping news articles into topics with no predefined categories is unsupervised clustering (no labels, structure discovered). Naming the paradigm immediately narrows your toolbox to the right methods.

To turn "learn a good model" into a solvable problem, we must say precisely what "good" means. That is the job of the loss function: a rule that assigns a nonnegative number to each prediction, larger when the prediction is worse. Once a loss is fixed, learning becomes the concrete optimization of finding parameters that make the average loss small.

Regression loss: squared error

For regression, the dominant choice is squared-error loss. For one example with prediction y-hat and true value y, the loss is the squared difference, and averaging over the dataset gives the mean squared error (MSE):

per-example loss:  (y_hat - y)^2
MSE = (1/n) * sum over i of ( f(x_i) - y_i )^2

Squaring makes all errors positive, penalizes big misses far more than small ones, and yields smooth calculus that gradient methods love. Worked example. Suppose predictions are 3, 5, 8 and truths are 2, 5, 6. The errors are 1, 0, 2; their squares are 1, 0, 4; the MSE is (1 + 0 + 4) / 3 = 5 / 3 = 1.67.

Classification loss: 0-1 loss

For classification, the most natural loss is 0-1 loss: charge 0 for a correct label and 1 for a wrong one. Its average is exactly the misclassification rate, so 1 minus the average is accuracy. Worked example. On 5 examples, if the model is right on 4 and wrong on 1, the 0-1 losses are 0, 0, 0, 0, 1; the average is 1/5 = 0.20, an accuracy of 80%.

The catch is that 0-1 loss is flat almost everywhere and jumps in a step, so its gradient is zero or undefined and it cannot guide gradient descent. In practice we optimize a smooth surrogate loss (such as the logistic loss in Module 2) that is easy to minimize and tracks the 0-1 loss well, then report 0-1 error (accuracy) at the end.

Empirical risk minimization

The true risk is the expected loss over the whole data distribution, which we cannot compute because the distribution is unknown. Instead we minimize the empirical risk, the average loss over our finite sample. This strategy is empirical risk minimization (ERM), and it underlies nearly every algorithm here.

ERM has one crucial limitation. Driving empirical risk to zero can inflate the true risk, because a flexible model can fit the sample's noise. This gap between empirical and true risk is exactly overfitting, and controlling it, through regularization, validation, and sensible model choice, is a running theme of the course. Choosing the right loss is step one; refusing to trust empirical risk blindly is step two.

Linear regression is the simplest and most important supervised model. It assumes the target is, approximately, a weighted sum of the features plus a constant. Despite its simplicity it is fast, interpretable, and the foundation on which logistic regression and neural networks are built.

The model

With features x1 through xd, linear regression predicts:

y_hat = w_1*x_1 + w_2*x_2 + ... + w_d*x_d + b

The weights w say how much each feature moves the prediction, and the bias (intercept) b is the prediction when all features are zero. Writing a constant feature equal to 1 lets us fold b into the weight vector, so the model is compactly the dot product of a weight vector and the (augmented) input. Geometrically, with one feature this is a straight line; with two, a plane; in general, a hyperplane.

The cost function

We fit the weights by minimizing mean squared error. It is customary to include a factor of one half so the derivative is clean:

J(w, b) = (1 / (2n)) * sum over i of ( y_hat_i - y_i )^2

This cost is a smooth, bowl-shaped (convex) function of the weights, which means it has a single global minimum and no misleading local minima, a very convenient property we exploit when training.

Interpreting a fitted model

Suppose we predict a house price (in thousands) from size in square meters and age in years and obtain price_hat = 3.0*size - 1.5*age + 50. The weight 3.0 says each additional square meter adds about 3 thousand to the predicted price, holding age fixed. The weight -1.5 says each extra year of age subtracts about 1.5 thousand. The intercept 50 is the baseline. This "holding others fixed" reading is why linear models are prized when you need to explain a prediction, not just make one.

Two ways to solve it

Because the cost is convex and quadratic, calculus gives a closed-form answer called the normal equations: set the gradient to zero and solve a linear system for the weights in one shot. This is exact and excellent for modest numbers of features. But it requires inverting a d-by-d matrix, which becomes slow or unstable when d is large. For big or streaming problems we instead minimize the cost iteratively with gradient descent, the subject of the next lesson. Both target the same convex bowl; they differ only in how they reach the bottom.

# Normal equations (matrix form), X has a column of 1s for the bias:
w = (X^T X)^(-1) X^T y      # one exact solve, cost grows with d^3

Gradient descent is the general-purpose engine for minimizing a differentiable cost, and it powers nearly all of modern machine learning. The intuition is simple: to reach the bottom of a valley in fog, feel which way is downhill and take a small step that way, then repeat.

The gradient and the update rule

The gradient of the cost is the vector of partial derivatives with respect to every parameter. It points in the direction of steepest increase, so its negative points steepest downhill. Gradient descent repeatedly nudges the parameters in the negative-gradient direction:

repeat until convergence:
    theta := theta - alpha * gradient_of_J(theta)

Here alpha is the learning rate, a small positive number setting the step size. For linear regression the gradient has a clean form; the update for a single weight w_j is:

w_j := w_j - alpha * (1/n) * sum over i of ( y_hat_i - y_i ) * x_ij

Each step compares predictions to truth, weights the error by the feature, and shifts the weight to shrink the error.

The learning rate is delicate

The learning rate controls everything about convergence:

• Too small: progress is correct but painfully slow, taking many iterations.
• Too large: steps overshoot the minimum and the cost can oscillate or diverge to infinity.
• Just right: the cost falls quickly and levels off near the minimum.

A healthy sign is that the cost decreases on (almost) every iteration. If it rises, lower alpha. Because features on very different scales distort the cost surface into a stretched bowl, we usually standardize features first so descent heads more directly toward the minimum.

Batch, stochastic, and mini-batch

The variants differ in how much data each step uses to estimate the gradient:

Batch gradient descent uses the whole dataset for each update: accurate but expensive on large data. Stochastic gradient descent (SGD) uses one random example per update: each step is cheap and the noise can even help escape flat regions, though the path jitters. Mini-batch uses a small batch, blending stability with speed, and is the default for training neural networks. All three descend the same cost; they trade accuracy of each step against how many steps you can afford.

Despite its name, logistic regression is a classification method, the standard first choice for predicting a binary label such as spam or not, disease or not. It adapts the linear model to output a probability between 0 and 1 rather than an unbounded number.

From a linear score to a probability

Logistic regression first computes a familiar linear score (also called the logit), then squashes it through the sigmoid (logistic) function into the interval (0, 1):

z = w . x + b                 # linear score
sigmoid(z) = 1 / (1 + e^(-z)) # maps any z to a value in (0, 1)
y_hat = P(y = 1 | x) = sigmoid(z)

The sigmoid is an S-shaped curve: large positive z gives an output near 1, large negative z near 0, and z = 0 gives exactly 0.5. We read the output as the estimated probability of the positive class, then apply a threshold (usually 0.5) to decide the label.

Why not squared error? The log loss

Pairing the sigmoid with squared-error loss produces a non-convex cost riddled with local minima, and it barely punishes confident mistakes. Instead we use cross-entropy, also called log loss, which is convex for logistic regression and penalizes confident wrong answers severely:

loss for one example (label y in {0, 1}):
    -[ y * log(y_hat) + (1 - y) * log(1 - y_hat) ]
J = average of that loss over all n examples

Read it in two halves. If the true label is 1, only -log(y_hat) survives: predicting 0.99 costs almost nothing, predicting 0.01 costs a lot. If the true label is 0, only -log(1 - y_hat) survives, symmetrically. The loss goes to infinity as a confident prediction turns out wrong, which strongly discourages overconfidence. We minimize this cost with the same gradient descent from the previous lesson; remarkably, the gradient has the identical clean form, error times feature.

The decision boundary

We predict class 1 when y_hat is at least 0.5, which happens exactly when the score z is at least 0. Since z = w . x + b is linear, the boundary w . x + b = 0 is a straight line (or hyperplane): logistic regression is a linear classifier. It draws one flat divider through feature space, class 1 on one side, class 0 on the other. This makes it interpretable and fast, but unable, on its own, to separate classes that curl around each other; for that we need the nonlinear models later in the course. A useful bonus: because the weights sit inside the sigmoid, a positive weight means that increasing that feature increases the probability of the positive class.

Why does a more powerful model sometimes predict worse? The answer is the bias-variance tradeoff, the single most useful lens for understanding generalization. It decomposes a model's expected error on new data into pieces that pull in opposite directions as we change model complexity.

Three sources of error

Imagine training your model many times on different random datasets from the same source and averaging its errors on a fresh test point. That expected error splits into three parts:

• Bias: error from wrong assumptions, the gap between the average prediction and the truth. A model too simple to capture the pattern (say, a straight line for a curved trend) has high bias. High bias causes underfitting.
• Variance: error from sensitivity to the particular training set, how much predictions wobble as the data changes. A model too flexible chases noise and has high variance. High variance causes overfitting.
• Irreducible error: noise inherent in the problem that no model can remove.

Symbolically, expected test error = bias-squared + variance + irreducible noise.

The tradeoff with complexity

As model complexity rises, bias falls (the model can fit more shapes) but variance rises (it fits each dataset's quirks). A very simple model underfits: high bias, low variance, poor on both training and test data. A very complex model overfits: low bias, high variance, excellent on training data but poor on test data. The total error is a U-shaped curve, minimized at an intermediate sweet spot.

Diagnosing from the numbers

You can read the regime directly off training and validation error:

The large gap between training and validation error is the fingerprint of overfitting. This diagnosis drives every fix in the rest of the module: regularization to curb variance, and cross-validation to measure where the sweet spot lies.

Regularization is the main tool for fighting overfitting. The idea is to discourage the model from becoming too complex by adding a penalty on the size of its weights to the training cost. Large weights let a model make wild, wiggly predictions that chase noise; penalizing them keeps the fit smoother and lowers variance, at the price of a little more bias, moving the model toward the bias-variance sweet spot.

The regularized cost

We minimize the usual loss plus a penalty term scaled by a strength lambda:

J(w) = original_loss(w) + lambda * penalty(w)

The two dominant penalties differ in how they measure "size":

• L2 regularization (ridge) penalizes the sum of squared weights: penalty = sum of w_j^2. It shrinks all weights smoothly toward zero without usually making any exactly zero.
• L1 regularization (lasso) penalizes the sum of absolute weights: penalty = sum of |w_j|. It can drive some weights exactly to zero, performing automatic feature selection and yielding a sparse model.

Note that the bias term b is conventionally left unpenalized, since shrinking the intercept has no bearing on model complexity.

L2 versus L1 at a glance

A blend of the two, called the elastic net, combines smooth shrinkage with sparsity and is popular when features are correlated.

Choosing the strength lambda

The strength lambda controls the tradeoff and is a hyperparameter, a knob we set rather than learn from the training loss directly:

• lambda = 0: no penalty, back to ordinary (possibly overfitting) fitting.
• lambda too large: weights are crushed toward zero, the model underfits (high bias).
• lambda just right: variance drops with only a small rise in bias, and generalization improves.

Because the best lambda cannot be read off the training error (which always prefers lambda = 0), we choose it with a validation set or cross-validation, trying several values and keeping the one with the lowest validation error. Regularization is thus the mechanism, and cross-validation, the next lesson, is how we tune it.

We keep saying "use a validation set." This lesson makes that precise. To estimate generalization honestly and to tune hyperparameters like lambda, we must evaluate on data the model did not train on, and we must be disciplined about how that data is used.

Three roles for data

Data is split by purpose, not just convenience:

• The training set fits the model's parameters (weights).
• The validation set tunes hyperparameters (like lambda or model complexity) and is used to pick between models.
• The test set is touched exactly once, at the very end, to report an unbiased estimate of real-world performance.

The rule is strict: once you make any decision based on the test set, it is no longer an honest test. Guard it.

k-fold cross-validation

A single validation split wastes data and can be lucky or unlucky. k-fold cross-validation uses the data far more efficiently. Split the training data into k equal folds (k = 5 or 10 is typical). Then, for each fold in turn, train on the other k - 1 folds and validate on the held-out fold. Average the k validation scores to get a stable estimate.

k-fold cross-validation (for one hyperparameter setting):
    split data into k folds
    for i = 1 to k:
        train on all folds except fold i
        score_i = evaluate on fold i
    cv_score = average(score_1, ..., score_k)

Worked example. With 5-fold cross-validation on 100 examples, each fold has 20. You train five models, each on 80 examples and validated on the remaining 20, so every example is used for validation exactly once and for training four times. To tune lambda, run this whole procedure for each candidate lambda and choose the value with the best average score. This is more reliable than a single split, at the cost of k times the computation.

Data leakage: the silent killer

Data leakage is when information from outside the training set sneaks into training, producing scores that look great but collapse in deployment. Classic mistakes include standardizing features using statistics computed over the whole dataset (the mean must come from training data only), selecting features while peeking at test labels, or having duplicate rows split across train and test. The discipline that prevents leakage is simple to state: any quantity learned from data, scaling factors, selected features, chosen hyperparameters, must be derived using only the training portion of each split. Combined with a locked-away test set, cross-validation then gives an estimate you can actually trust, which is the whole point of controlling overfitting.

A decision tree predicts by asking a sequence of simple yes/no questions about the features, following the answers down a branching structure until it reaches a leaf that gives the prediction. Trees are prized for being human-readable: the path to a decision is a plain chain of rules, and they need no feature scaling.

Anatomy and how splits are chosen

Each internal node tests one feature against a threshold ("is age < 30?"), sending examples left or right; each leaf holds a prediction (a class for classification, an average for regression). Training builds the tree greedily, top down: at each node it searches over features and thresholds for the split that best separates the classes, then recurses on each side.

"Best" is measured by how pure the resulting groups are, meaning how dominated each is by a single class. Two standard purity measures for a node are:

Gini impurity = 1 - sum over classes of p_c^2
Entropy       = - sum over classes of p_c * log2(p_c)

where p_c is the fraction of the node belonging to class c. Both are 0 for a perfectly pure node (all one class) and largest when classes are evenly mixed. The tree picks the split that most reduces impurity, the information gain. Worked example. A node with 8 positives and 2 negatives has p = 0.8 and 0.2, so its Gini impurity is 1 - (0.8^2 + 0.2^2) = 1 - (0.64 + 0.04) = 0.32. A pure node of all positives would have Gini 1 - 1^2 = 0.

Splits carve the feature space into boxes

Because each split is a threshold on one feature, a decision tree partitions feature space into axis-aligned rectangles, one per leaf, and predicts a constant within each. This gives trees a distinctive staircase-shaped boundary and lets them capture nonlinear patterns and feature interactions that a single linear model cannot.

The overfitting problem

A tree grown without limit will keep splitting until every leaf is pure, often ending with one training example per leaf. Such a tree memorizes the training set: near-zero training error but high variance and poor generalization, a textbook case of overfitting. The cures constrain the tree's growth:

• Limit the maximum depth or require a minimum number of samples to split a node.
• Prune the tree after growing it, cutting back branches that do not improve validation performance.

These controls trade a little bias for much less variance. Even so, a single tuned tree is often mediocre and unstable; small changes in the data can reshape it entirely. That instability is precisely the weakness that ensembles, in the next lesson, are designed to fix.

A single decision tree is unstable: change a few training points and it can look completely different. Ensemble methods turn this weakness into a strength by combining many models whose errors partly cancel. The headline example is the random forest, one of the most reliable off-the-shelf classifiers.

Bagging: averaging away variance

The core idea is bagging (bootstrap aggregating). From the training set of n examples, draw many bootstrap samples, each a random sample of n examples drawn with replacement (so some examples repeat and some are omitted). Train a separate tree on each bootstrap sample, then aggregate: for classification, take a majority vote across trees; for regression, average their predictions.

Why does averaging help? Individual deep trees have low bias but high variance. Averaging many roughly independent high-variance predictions keeps the low bias while sharply cutting the variance, the same reason an average of many noisy measurements is more precise than one. The trees must be somewhat decorrelated for this to work well, which motivates the forest's second trick.

The extra randomness in a random forest

A random forest is bagging with decision trees plus one more source of randomness: at each split, the tree may only choose from a random subset of the features rather than all of them. This feature subsampling stops every tree from leaning on the same one or two dominant features, so the trees disagree more and their average generalizes better. Two knobs matter most: the number of trees (more is better and never hurts accuracy, only compute) and the number of features considered per split.

Random forests are accurate, robust to outliers, need little tuning, and even estimate feature importance. Their main costs are reduced interpretability (a forest of hundreds of trees is not a simple rule) and more computation than a single tree.

Bagging versus boosting

Bagging builds many trees independently and in parallel and averages them, chiefly to reduce variance. Boosting takes a different route: it builds trees sequentially, each new tree focusing on the examples the previous ones got wrong, chiefly to reduce bias. Gradient-boosted trees often edge out random forests in raw accuracy but are more sensitive to their settings and easier to overfit. Both are ensembles; they differ in whether the members are grown together and averaged (bagging) or grown one after another to correct mistakes (boosting).

The support vector machine (SVM) is a powerful classifier built on an elegant geometric idea: among all the hyperplanes that separate two classes, prefer the one that sits as far as possible from the nearest points of either class. That distance is the margin, and maximizing it tends to give boundaries that generalize well.

The maximum-margin hyperplane

Logistic regression finds some separating line; an SVM finds the widest street. Picture the boundary as a road drawn between the two classes: the SVM makes the road as wide as it can, and the boundary runs down its center. The examples that touch the edges of the street, the closest points that "hold it in place", are the support vectors. Remarkably, only these few points determine the boundary; move any other point (without crossing the street) and nothing changes. A wide margin gives a buffer against noise, which is why max-margin classifiers are robust.

The soft margin for messy data

Real data is rarely perfectly separable; a few points sit on the wrong side or inside the street. A soft-margin SVM allows some violations, penalizing each by an amount controlled by a hyperparameter usually called C. Large C insists on few violations (a narrow, hard margin that risks overfitting); small C tolerates more violations for a wider margin (more regularization, more bias). Tuning C is the SVM's version of the bias-variance dial, chosen by cross-validation.

The kernel trick

So far the boundary is linear. The SVM becomes far more powerful through the kernel trick: a kernel function computes similarities between points as if they had been mapped into a much higher-dimensional space, without ever building that space explicitly. A linear boundary in the high-dimensional space corresponds to a curved boundary in the original one, so an SVM with, say, a radial basis function (RBF) kernel can carve out flexible, nonlinear regions. This lets one clean algorithm handle problems where classes wrap around each other. The tradeoffs: SVMs are memory- and compute-heavy on very large datasets, and the kernel and its parameters need tuning, but on medium-sized problems with clear margins they remain a strong, principled choice.

Clustering is the unsupervised task of grouping similar examples together using only the inputs. The most widely used clustering algorithm is k-means, which partitions data into a chosen number k of clusters, each represented by its center.

The objective

k-means seeks k cluster centers, called centroids, and an assignment of each point to a centroid, so as to minimize the total squared distance from points to their assigned centroids. This total is the within-cluster sum of squares (also called inertia):

minimize  sum over points x of  || x - centroid(cluster of x) ||^2

Small inertia means tight, compact clusters. Directly finding the optimal partition is hard, so k-means uses a simple, fast iterative scheme that improves the objective each round.

Lloyd's algorithm: two alternating steps

Starting from k initial centroids (often k random data points), repeat two steps until assignments stop changing:

repeat until no assignment changes:
    ASSIGN:  put each point in the cluster of its nearest centroid
    UPDATE:  move each centroid to the mean of the points assigned to it

Each step can only lower (or hold) the inertia, so the algorithm always converges, usually within a handful of iterations. Worked example. With k = 2 on points at 1, 2, 9, 10 (one dimension), suppose centroids start at 1 and 10. Assign: {1, 2} go to centroid 1, {9, 10} go to centroid 10. Update: the centroids move to the means, 1.5 and 9.5. Reassigning gives the same groups, so it has converged to the natural clusters {1, 2} and {9, 10}.

Two important caveats

• Initialization matters. Because the objective is non-convex, different starting centroids can converge to different, worse solutions (local minima). The standard fix is to run k-means several times with different random starts and keep the result with the lowest inertia; a smarter seeding scheme called k-means++ spreads the initial centroids out to make good outcomes more likely.
• You must choose k. The algorithm needs the number of clusters as input.

Choosing k with the elbow method

Inertia always falls as k rises (more centroids fit the data more tightly), reaching zero when k equals the number of points, so we cannot just minimize it. The elbow method plots inertia against k and looks for the "elbow", the point where adding another cluster yields only a small further drop. That kink suggests a natural number of clusters. k-means is fast and scalable, but it assumes roughly round, similarly sized clusters and is sensitive to feature scaling, so standardize features first and be ready to try other clustering methods when these assumptions fail.

High-dimensional data is hard to visualize, slow to model, and often redundant because features are correlated. Principal component analysis (PCA) is the classic dimensionality reduction method: it re-expresses the data in a new set of axes ordered by how much variation they capture, letting us keep a few axes and discard the rest with minimal loss.

The core idea: directions of maximum variance

PCA finds new directions, the principal components, that are straight-line combinations of the original features. The first principal component is the single direction along which the data varies the most. The second is the direction of greatest remaining variance that is orthogonal (perpendicular) to the first, and so on. Each component is orthogonal to all earlier ones, so the new axes are uncorrelated. Intuitively, PCA rotates the coordinate system to line up with the natural spread of the data.

Explained variance

Each principal component carries a share of the data's total variance, its explained variance. Because the components are ordered from most to least, the first few often account for the bulk of the variation. Reporting the cumulative explained variance tells you how many components you need: if the first two components together explain 90% of the variance, you can replace many original features with just two coordinates and lose only 10% of the spread. This is the payoff, fewer dimensions, most of the information.

Using PCA

The recipe is short: standardize the features (PCA is sensitive to scale, since it chases variance), compute the principal components, then project the data onto the top few. Common uses are:

• Visualization: project to 2 or 3 components to plot high-dimensional data and eyeball its structure.
• Compression and speed: fewer features mean faster, lighter downstream models.
• Noise reduction: discarding low-variance components can drop noise while keeping signal.

Two cautions. PCA is linear: it captures only straight-line structure and can miss curved patterns. And principal components are combinations of original features, so they can be harder to interpret. Used with those limits in mind, PCA is an indispensable first step for exploring and compressing high-dimensional data.

A neural network is a model built by stacking many simple units into layers, so that the whole can represent very complex functions. It generalizes logistic regression: where logistic regression has one linear-then-sigmoid unit, a neural network chains many of them, letting it learn nonlinear patterns automatically.

Neurons and layers

The basic unit, a neuron, does exactly what we have seen: it computes a weighted sum of its inputs plus a bias, then applies a nonlinear activation function. Neurons are organized into layers:

• The input layer holds the features.
• One or more hidden layers transform the data through their neurons; a network with several hidden layers is called deep.
• The output layer produces the prediction (one sigmoid unit for binary classification, several units for multiclass or regression).

Each neuron in a layer connects to every neuron in the next, each connection carrying a learnable weight. A modest network can have thousands of weights, all tuned by training.

Why nonlinearity is the whole point

The activation function must be nonlinear. Here is why: if every neuron were purely linear, then stacking layers would just compose linear maps, and a composition of linear maps is itself a single linear map. The entire deep network would collapse to a plain linear model, no matter how many layers. Nonlinear activations break that collapse, so each layer can bend and fold the representation, and the network as a whole can approximate very complicated functions. Common activations are the sigmoid, the hyperbolic tangent (tanh), and, most popular today, the ReLU (rectified linear unit), which simply outputs max(0, z): cheap to compute and effective in deep networks.

The forward pass

Computing a prediction is the forward pass: feed the inputs into the first layer, apply weights, biases, and activation to get that layer's outputs, feed those into the next layer, and continue to the output. Worked example. A neuron has inputs x = (2, 3), weights w = (0.5, -1), and bias b = 1. Its pre-activation is z = 0.5(2) + (-1)(3) + 1 = 1 - 3 + 1 = -1. With a ReLU activation the output is max(0, -1) = 0; with a sigmoid it would be about 0.27. Chaining such calculations layer by layer yields the network's prediction, which we then compare to the true label with a loss, setting up the training in the next lesson.

A neural network has thousands of weights, and gradient descent needs the gradient of the loss with respect to every one of them. Computing those gradients efficiently is the job of backpropagation, the algorithm that made training deep networks practical. It is nothing more exotic than the calculus chain rule, applied cleverly and reused across the network.

The idea: assign blame backward

Training alternates two passes. The forward pass computes the prediction and the loss, as in the last lesson, caching each layer's intermediate values. The backward pass then works from the loss back toward the inputs, computing how much each weight contributed to the error, its partial derivative. Because a weight in an early layer affects the loss only through the layers that follow it, its influence is a product of the derivatives along that path, exactly what the chain rule multiplies together.

Chain rule intuition for one weight w:
    dLoss/dw = dLoss/d(output) * d(output)/d(hidden) * ... * d(...)/dw
Backprop computes these products once, layer by layer, from output to input,
reusing shared factors instead of recomputing them.

The key efficiency is reuse: the gradient signal arriving at a layer is passed back and combined with that layer's local derivative to produce both the updates for its weights and the signal to send to the previous layer. One backward sweep yields every gradient, at roughly the cost of one forward pass.

Putting it together: the training loop

Backpropagation supplies the gradients; gradient descent (usually mini-batch, from Module 2) uses them to update the weights. The loop is:

repeat for many epochs:
    for each mini-batch:
        forward pass:   compute predictions and loss
        backward pass:  backpropagate to get gradient for every weight
        update:         weight := weight - alpha * gradient

One full sweep through the training data is an epoch; networks typically train for many epochs. All the earlier ideas return here: the learning rate must be tuned, features should be standardized so the loss surface is well-behaved, and regularization (including a neural-network favorite, dropout, which randomly disables neurons during training) fights overfitting.

Practical pitfalls

Two issues deserve naming. The vanishing gradient problem: when many small derivatives multiply together through deep networks, the gradient reaching early layers can shrink toward zero, stalling their learning. This is one reason ReLU (whose derivative is 1 for positive inputs) largely replaced the sigmoid in hidden layers. The opposite, exploding gradients, can also occur. And because the loss surface of a neural network is non-convex, training finds a good local minimum rather than a guaranteed global one, which is usually fine in practice. Backpropagation plus gradient descent, run over many epochs with sensible activations and regularization, is the engine behind essentially all modern deep learning.

A single accuracy number rarely tells the whole story of a classifier, especially when one class is rare or when different mistakes carry different costs. Proper evaluation starts with the confusion matrix and the metrics built from it.

The confusion matrix

For binary classification, every prediction falls into one of four cells, comparing the predicted label to the true label:

A false positive is a false alarm (predicted positive, actually negative); a false negative is a miss (predicted negative, actually positive). Which is worse depends entirely on the application, and that is the point.

The core metrics

From these four counts we build the standard metrics:

Accuracy  = (TP + TN) / (TP + TN + FP + FN)   # fraction correct overall
Precision = TP / (TP + FP)   # of predicted positives, how many are right
Recall    = TP / (TP + FN)   # of actual positives, how many we caught
F1        = 2 * (Precision * Recall) / (Precision + Recall)   # their harmonic mean

Precision answers "when the model says positive, how often is it correct?", it matters when false alarms are costly (for example, flagging a legitimate email as spam). Recall (sensitivity) answers "of all the real positives, how many did we find?", it matters when misses are costly (for example, failing to detect a disease). The F1 score is their harmonic mean, a single balanced number that is high only when both precision and recall are high.

Worked example

A model is evaluated on 100 cases. It produces TP = 40, FP = 10, FN = 20, TN = 30. Then:

• Accuracy = (40 + 30) / 100 = 0.70.
• Precision = 40 / (40 + 10) = 40 / 50 = 0.80.
• Recall = 40 / (40 + 20) = 40 / 60 = 0.67.
• F1 = 2(0.80 x 0.67) / (0.80 + 0.67) = 1.072 / 1.47 = 0.73.

The precision-recall tradeoff and imbalance

Precision and recall usually trade off. Lowering the decision threshold predicts positive more readily, catching more true positives (higher recall) but also raising false alarms (lower precision); raising the threshold does the reverse. You tune the threshold to match which error you fear more. This also exposes why accuracy misleads on imbalanced data: if only 1% of transactions are fraud, a lazy model that predicts "not fraud" for everything scores 99% accuracy while catching zero fraud (recall 0). Precision and recall reveal that failure instantly, which is why they, not raw accuracy, are the right tools for rare-event problems.

Precision and recall describe a classifier at one decision threshold. But a probabilistic classifier offers a whole family of behaviors as you slide the threshold from strict to lenient. The ROC curve summarizes that entire family in one picture, and its area under the curve distills it to a single threshold-independent score.

Building the ROC curve

The receiver operating characteristic (ROC) curve plots two rates against each other as the threshold varies:

True Positive Rate  (TPR, = recall) = TP / (TP + FN)   # y-axis
False Positive Rate (FPR)           = FP / (FP + TN)   # x-axis

At a very strict threshold the model predicts positive almost never, so both TPR and FPR are near 0 (bottom-left). At a very lenient threshold it predicts positive almost always, so both approach 1 (top-right). Sweeping the threshold traces a curve between these corners. The ideal is to climb toward high TPR while keeping FPR low, so a curve that bows toward the top-left corner is better.

Area under the curve (AUC)

The single most useful summary is the AUC, the area under the ROC curve, ranging from 0 to 1:

• AUC = 1.0: a perfect classifier that ranks every positive above every negative.
• AUC = 0.5: no better than random guessing (the diagonal chance line).
• AUC below 0.5: worse than chance (its predictions are anti-correlated with truth).

AUC has a clean interpretation: it is the probability that the model assigns a higher score to a randomly chosen positive example than to a randomly chosen negative one. In other words, AUC measures how well the classifier ranks positives above negatives, independent of any particular threshold.

When to use which

Because AUC is threshold-independent, it is ideal for comparing models overall and for judging ranking quality. Single-threshold metrics like precision and recall are what you report once you have committed to an operating threshold for deployment. One caution: on heavily imbalanced data, ROC curves can look optimistic because a large true-negative count keeps FPR low, so a precision-recall curve often tells a more honest story for rare-positive problems. The disciplined workflow is to compare candidate models by AUC, then choose the threshold that balances precision and recall for your costs, and finally report both on the untouched test set.