Chapter 3: Classification

The first modeling decision is what kind of output the target is, because it fixes the loss, the metrics, and the final layer of the model. Regression predicts a continuous quantity, such as a price or a temperature, and errors are measured as distances. Classification predicts a discrete category, such as yes or no, or cat, dog, or bird, and errors are counted as right or wrong. Most classifiers first produce a probability for each class and then pick one. A common trap is treating ordered categories, such as ratings from 1 to 5, as regression or as nominal classes without thinking about which errors matter.

Linear regression gives a score $z$ anywhere on the real line, but a probability must lie between 0 and 1. The sigmoid fixes this by mapping $z$ to $1/(1 + e^{-z})$. Large positive scores give outputs near 1, large negative scores give outputs near 0, and $z = 0$ gives exactly 0.5. The output is read as the probability that the label is 1. Its derivative has the convenient form $\sigma(z)(1 - \sigma(z))$, which peaks at 0.25 when $z = 0$. That form makes gradients cheap to compute, and it is why the sigmoid pairs so neatly with cross-entropy loss later in this chapter.

Three properties of the sigmoid shape how classifiers behave. First, its range: outputs approach 0 and 1 but never reach them, so a logistic model never claims total certainty. Second, symmetry: $\sigma(-z) = 1 - \sigma(z)$, so flipping the sign of the score swaps the two class probabilities, and the two classes are treated alike. Third, saturation: for scores beyond about plus or minus 5, the curve is almost flat and its gradient is near zero. Saturation is harmless with cross-entropy loss, which cancels it, but with squared-error loss it stalls learning on badly wrong examples, which is one reason logistic regression does not use MSE.

A classifier's probability is not yet a decision. The threshold $t$ converts it: predict class 1 when the probability is at least $t$, otherwise class 0. Because the sigmoid is monotonic, this is the same as comparing the raw score $z$ with the logit of $t$, which is $\log(t/(1-t))$. The default $t = 0.5$ corresponds to $z = 0$ and minimizes error count only when both mistakes cost the same and probabilities are calibrated. Lowering $t$ labels more examples positive, raising recall and lowering precision, and raising it does the reverse. The threshold is chosen after training, on validation data, without retraining the model.

The set of points where the classifier is undecided is its decision boundary. For a linear score $z = \mathbf{w}^T \mathbf{x} + b$, the boundary is where $z = 0$, which is a line in two dimensions, a plane in three, and a hyperplane in general. The weight vector $\mathbf{w}$ is perpendicular to it and points toward class 1. The value of $z$ divided by the length of $\mathbf{w}$ is the signed distance to the boundary, so points far from it get confident probabilities. The limitation is that a single hyperplane cannot separate classes arranged in rings or in XOR patterns, which motivates the feature engineering at the end of this chapter.

The right threshold comes from the cost of each mistake, not from habit. If a false positive costs $C_{FP}$ and a false negative costs $C_{FN}$, and the probabilities are calibrated, predicting positive is cheaper on average whenever the probability exceeds $C_{FP}/(C_{FP} + C_{FN})$. Equal costs give 0.5. In cancer screening a miss is far worse than a false alarm, so the threshold drops sharply. For a spam filter, losing a real email is worse, so it rises. When costs are hard to price, teams pick the threshold that meets a recall or precision target on validation data. This only works if the model's probabilities are calibrated.

Logistic regression combines the two pieces from the previous topic into one model. It computes a linear score $z = \mathbf{w}^T \mathbf{x} + b$, exactly as linear regression does, and passes it through the sigmoid to get the probability that the label is 1. Each weight $w_j$ says how strongly feature $j$ pushes the score up or down, and the bias $b$ sets the baseline when all features are zero. This is a discriminative model: it learns the conditional probability of the label given the features directly, rather than modeling how the features themselves are distributed, as Naive Bayes does later in this chapter.

Training needs a loss that rewards assigning high probability to the true label. Binary cross-entropy does this: for each example it charges $-\log \hat{y}$ when the label is 1 and $-\log(1 - \hat{y})$ when it is 0, then averages over the $n$ examples. A confident correct prediction costs almost nothing, an unsure one costs about 0.69, and a confident wrong one costs a lot, growing without bound as the probability of the true label approaches 0. Unlike squared error on a sigmoid, this loss is convex in the weights, so gradient descent cannot get trapped in a local minimum.

Cross-entropy is not an arbitrary choice; it falls out of maximum likelihood estimation. Treat each label as a coin flip whose probability of heads is the model's output $\hat{y}$. The likelihood of the whole dataset is the product of the probabilities the model gave to the labels that actually occurred. Products of many small numbers are awkward, so we take logs, which turns the product into a sum, and negate it so we can minimize. The result is exactly the cross-entropy loss. Minimizing cross-entropy therefore finds the weights under which the observed labels were most probable.

To minimize cross-entropy with gradient descent we need its gradient, and it comes out remarkably simple. The sigmoid's derivative cancels against the logarithm in the loss, leaving the gradient for each weight as the average of prediction error times feature value, $(\hat{y} - y) x_j$. This is the same form as linear regression's gradient, except that $\hat{y}$ is now a sigmoid output. When the model predicts too low for a positive example, the error is negative, so the gradient step raises the weights of that example's active features. Examples that are already predicted confidently and correctly contribute almost nothing.

Probabilities are bounded, but odds are not, which makes them a natural scale for a linear model. The odds of an event are its probability divided by the probability that it does not happen, ranging from 0 to infinity. Taking the logarithm gives the log-odds, or logit, which ranges over the whole real line. Logistic regression is exactly the assumption that the log-odds are a linear function of the features. This is why it counts as a linear classifier even though its output curve is S-shaped, and why the score $z$ can be read directly as evidence measured in log-odds.

When the training classes can be separated perfectly, plain logistic regression has no finite best solution. Scaling the weights up always makes the sigmoid steeper and the likelihood higher, so the weights grow without bound and the model becomes overconfident. Adding an L2 penalty $\lambda \lVert \mathbf{w} \rVert^2$ to the loss charges for large weights, giving a finite, smoother solution that generalizes better. A larger $\lambda$ means stronger shrinkage. Scikit-learn uses the inverse, $C = 1/\lambda$, so a smaller C means more regularization. L1 regularization instead drives some weights exactly to zero, which performs feature selection.

Logistic weights have a precise meaning on the odds scale. Increasing feature $x_j$ by one unit, holding the others fixed, adds $w_j$ to the log-odds, which multiplies the odds by $e^{w_j}$, called the odds ratio. A weight of 0.7 roughly doubles the odds, and a negative weight shrinks them. This reading holds in the feature's own units, scaled or not. Standardizing matters only when comparing weights, since a one-unit change in age and a one-unit change in income are not comparable. Correlated features also split credit unpredictably between them, so individual weights should not be read as causal effects.

One-vs-Rest is the simplest way to reuse a binary classifier for K classes. Train K separate classifiers, where classifier $k$ treats class $k$ as positive and every other class as negative. At prediction time, run all K and pick the class whose classifier is most confident. It costs only K training runs and works with any binary model. Its weaknesses: each classifier sees an imbalanced problem, one class against all the rest, and the K scores come from independently trained models, so they are not calibrated against each other and need not sum to one. Rifkin and Klautau showed that, well tuned, OvR is often as accurate as fancier schemes.

One-vs-One trains a separate classifier for every pair of classes, $K(K-1)/2$ in all, and each one learns to tell just two classes apart using only their examples. To predict, every pairwise classifier votes for one of its two classes, and the class with the most votes wins, with ties broken by confidence. Each subproblem is small and balanced, which suits SVMs, whose training cost grows faster than linearly in the number of examples. The drawback is the quadratic count: 10 classes need 45 classifiers and 100 classes need 4,950, so prediction becomes slow for large K.

Softmax regression handles all K classes in one model. It computes a score $z_k$ for each class, each from its own weight vector, then exponentiates every score and divides by the sum of the exponentials. Exponentiating makes every value positive, and dividing makes them sum to 1, so the result is a proper probability distribution. Larger scores get disproportionately more mass, because the exponential grows quickly. With two classes, softmax reduces exactly to the sigmoid of the score difference, so it is the natural generalization of logistic regression. It is also the output layer of almost every neural network classifier.

Two properties of softmax matter in practice. First, shift invariance: adding the same constant to every score leaves the output unchanged. Implementations exploit this by subtracting the largest score before exponentiating, which prevents overflow without changing the answer. Second, temperature: dividing the scores by $T$ before softmax controls how peaked the distribution is. Low temperatures sharpen it toward a one-hot argmax, and high temperatures flatten it toward uniform. Temperature is used to sample text from language models and, in knowledge distillation, to soften a teacher model's outputs so a student can learn from the relative scores of the wrong classes.

Training softmax uses the multiclass version of cross-entropy. The labels are one-hot vectors, with a 1 for the true class and 0 elsewhere, so the double sum over samples and classes collapses: each sample contributes only minus the log probability assigned to its true class. This is again the negative log-likelihood, now of a categorical distribution. The gradient with respect to each score is simply the predicted probability minus the one-hot label, the same elegant form as the binary case. Minimizing this loss pushes up the true class's score and pushes down every other class's score in proportion to the probability it stole.

Multiclass and multilabel problems look similar but need different output layers. In multiclass classification, exactly one label applies to each example, so a softmax distributes one unit of probability across mutually exclusive classes. In multilabel classification, any subset of labels can apply, such as a photo tagged both outdoor and sunset. That calls for K independent sigmoids, one per label, each trained with its own binary cross-entropy, and each thresholded separately. Using softmax for a multilabel task is a common bug: it forces the labels to compete, so a photo that is both cute and fluffy can never score high on both.

Bayes' theorem lets us compute the probability we want from probabilities that are easy to estimate. We want the posterior, the probability of class $y$ given features $\mathbf{x}$. The theorem writes it as the likelihood, the probability of seeing $\mathbf{x}$ in class $y$, times the prior, how common $y$ is, divided by the evidence, the overall probability of $\mathbf{x}$. Likelihoods and priors can be counted from labeled data. The evidence is the same for every class, so it only normalizes. A frequent mistake is confusing the likelihood with the posterior: a word common in spam is not automatically strong evidence of spam if it is also common elsewhere.

Estimating the joint likelihood of all features within each class is hopeless: with 50,000 binary word features there are $2^{50000}$ combinations. The naive assumption is that features are conditionally independent once the class is known, so the joint likelihood factors into a product of one-feature terms. Each term needs only a simple count, and the parameter count grows linearly with the number of features. The assumption is almost always false, since words such as 'free' and 'money' co-occur. It still works for classification because only the ranking of classes matters, even when the probabilities themselves become badly overconfident.

To classify, Naive Bayes picks the class with the largest posterior. The evidence term is shared by every class, so it can be dropped, leaving the prior times the product of feature likelihoods. In practice we compare sums of log probabilities instead of products. Multiplying hundreds of small probabilities underflows floating point to exactly zero, which makes every class tie. Because the logarithm is monotonic, taking logs never changes which class wins. Writing the rule in log space also exposes its structure: for multinomial and Bernoulli models it is a linear function of the features, so Naive Bayes is a linear classifier, just fitted by counting instead of by optimization.

For continuous features, Gaussian Naive Bayes assumes each feature follows a normal distribution within each class. Training is just computing a mean $\mu$ and a variance $\sigma^2$ for every feature-class pair, $2pK$ numbers for $p$ features and $K$ classes. To classify, evaluate each feature's normal density under each class, multiply them with the prior, and pick the largest. Because each class has its own variance, the boundary between classes is quadratic, not linear. The method fails when a feature is strongly non-normal, such as bimodal or heavily skewed, so transforming or binning such features first often helps.

Multinomial Naive Bayes is the standard variant for text. It models a document as a bag of word counts and gives each class its own probability of producing each word, estimated as the word's count in that class divided by the total words in the class. A document's log-likelihood is the sum, over words, of count times log word probability, so repeated words add evidence. Training takes one pass of counting over the corpus. It remains a strong baseline for spam filtering and topic classification, especially with small datasets, though it ignores word order and needs smoothing for rare words.

Counting has a fatal flaw: a word that never appeared with a class in training gets probability zero for it, and one zero in the product wipes out all other evidence. Laplace smoothing adds a pseudocount $\alpha$, usually 1, to every word count, and adds $\alpha$ times the vocabulary size $\lvert V \rvert$ to the denominator so the probabilities still sum to one. Unseen words now get a small positive probability, and estimates for frequent words barely change. Smaller values of $\alpha$, such as 0.1, smooth less and are often tuned by cross-validation. It is a simple form of Bayesian prior on word frequencies.

Imbalance breaks training and evaluation at once. In training, a loss averaged over examples is dominated by the majority class, so the cheapest way to lower it is to push every prediction toward the common label. In evaluation, accuracy rewards exactly that: if 99 percent of examples are negative, predicting negative for everything scores 99 percent while finding no positives. The rare class is usually the one that matters, such as fraud, disease, or defects. The first step is always to compute the majority-class baseline, and then judge models by recall and precision on the minority class.

Oversampling rebalances the training set by adding minority examples. Random oversampling duplicates existing minority points, which is simple but encourages the model to memorize those exact points. SMOTE instead creates synthetic points: for a minority example, pick one of its $k$ nearest minority neighbors and place a new point at a random position on the segment between them. This fills in the minority region rather than stacking copies. Risks remain: SMOTE can create points inside majority territory when classes overlap. Resample only the training folds, never before splitting, or synthetic copies of test points leak into training.

Undersampling rebalances by removing majority examples. Random undersampling keeps a random subset of the majority class, which makes training fast and balanced but throws away information, sometimes most of the dataset. Informed methods remove examples more selectively. Tomek links remove majority points that sit right next to a minority point, cleaning the boundary, and Edited Nearest Neighbors removes majority points misclassified by their neighbors. Another option is to train several models on different random majority subsets and combine them, as in EasyEnsemble, so all the data is used. Undersampling suits huge datasets where the majority class is highly redundant.

Class weights change the loss instead of the data. Each example's loss is multiplied by a weight for its class, so mistakes on the minority class cost more and pull the gradient harder. The common balanced scheme sets $w_k = n/(K n_k)$, where $n$ is the total count, $K$ the number of classes, and $n_k$ the size of class $k$. Each class then contributes equally to the total loss. This matches oversampling in expectation, without enlarging the dataset or creating duplicates. In scikit-learn, set class_weight='balanced'. Weighting shifts predicted probabilities upward for the minority class, so they are no longer calibrated.

The cheapest fix for imbalance needs no retraining: move the decision threshold. A model trained on imbalanced data often ranks examples well but rarely pushes minority probabilities above 0.5, so lowering the threshold recovers many missed positives. The tradeoff is more false alarms, so recall rises while precision falls. Choose the threshold on a validation set, never the test set, using the F1 score, a recall target, or expected cost. It combines well with class weights or resampling, and it is the right first step whenever the model's ranking, measured by ROC or precision-recall AUC, is already good.

Metrics for imbalanced problems must focus on the minority class. Precision is the share of predicted positives that are real, and recall is the share of real positives that are found. F1 is their harmonic mean, which stays low if either is low. ROC-AUC measures ranking across all thresholds but uses the false positive rate, whose denominator is the huge negative class, so thousands of false alarms barely move it. Precision-recall AUC uses precision instead, so it exposes those false alarms. Its random baseline equals the positive rate, which is why it is the preferred summary for rare-event problems.

A linear model can learn curved boundaries if we give it curved features. Polynomial expansion adds powers of each feature, such as $x_1^2$, and interaction terms, such as $x_1 x_2$. The model stays linear in its weights, so training is unchanged, but its boundary in the original space becomes a curve: a circle, an ellipse, or a saddle. The cost is rapid growth: degree 2 on 100 features produces 5,150 features, and degree 3 produces 176,850. That invites overfitting, so polynomial features are almost always paired with regularization, and kernels offer a way to get the same effect without building the features explicitly.

Features measured in different units can distort training. If income ranges into the hundreds of thousands while age ranges up to about 90, the loss surface becomes a long narrow valley, and gradient descent zigzags across it instead of heading to the minimum. Regularization also penalizes weights unevenly, because a feature's weight size depends on its units. Standardization subtracts the mean $\mu$ and divides by the standard deviation $\sigma$, giving zero mean and unit variance. Min-max scaling instead maps values to the range 0 to 1. Fit the scaler on training data only and reuse those numbers on test data. Tree models are unaffected by scaling.

Models need numbers, but many features are nominal categories with no order, such as city or color. One-hot encoding creates one binary column per category, with a 1 in the column for the example's category and 0 elsewhere. No false ordering is introduced, and a linear model learns a separate effect for each category. For an unregularized linear model with an intercept, keep only $K - 1$ of the $K$ columns, because the full set always sums to 1 and duplicates the intercept, the dummy variable trap. Regularized models and trees can keep all $K$. High-cardinality features, such as zip codes, produce thousands of sparse columns.

Label encoding replaces each category with an integer, such as 0, 1, and 2. That is correct for ordinal categories, where the order means something, such as small, medium, and large. For nominal categories it invents a false order and false spacing: a linear model would treat green as twice as far from red as blue is, which is meaningless. Tree-based models are more forgiving, because they split on thresholds and can isolate any integer value with a few splits, so label encoding is often acceptable there. For linear models and neural networks, use one-hot encoding or learned embeddings for nominal features.

High-cardinality categories, such as zip codes with tens of thousands of values, make one-hot encoding unwieldy. Target encoding replaces each category with the mean target value observed for it, producing a single numeric column. Two dangers come with it. Rare categories get noisy means, so we shrink them toward the global mean, weighting by sample size. And computing the encoding from the same rows the model trains on leaks the label into the feature, so encodings must be computed out-of-fold, using only other folds' data. Scikit-learn's TargetEncoder does that cross-fitting automatically.

Filter methods score each feature by itself against the target, then keep the top scorers, without training the final model. Common scores are correlation for linear relationships, mutual information for any dependence, the chi-squared statistic for categorical features, and the ANOVA F-test. They are fast, scaling to thousands of features, and reduce overfitting and training time. Their blind spot is interactions: a feature useless alone, but powerful in combination, gets discarded, and two redundant copies of the same signal are both kept. They are best used as a quick first pass before a more careful method.

Wrapper methods judge feature subsets by actually training and validating the model on them, so they capture interactions and redundancy that filters miss. Forward selection starts empty and repeatedly adds the feature that most improves the validation score. Backward elimination starts with everything and repeatedly removes the least useful feature. Recursive feature elimination drops the features with the smallest model weights or importances in each round. The price is compute: every candidate subset costs a full training run, ideally with cross-validation. Searching too many subsets also overfits the validation set, so confirm the final choice on held-out data.

Instead of choosing a subset of the original features, dimensionality reduction builds a few new ones from all of them. PCA finds orthogonal directions of maximum variance and projects the data onto the top $k$, usually enough to keep about 95 percent of the variance. It removes multicollinearity, cuts training time, and can reduce overfitting. LDA instead uses the labels to find directions that separate the classes best, and autoencoders learn nonlinear compressions. The costs: the new features are mixtures that are hard to interpret, and PCA ignores the labels, so a low-variance direction it discards may be the one that predicts the target.