Chapter 3: Classification

Regression models $E[y|\mathbf{x}] \in \mathbb{R}$ — a continuous conditional expectation. Classification models $P(y = k | \mathbf{x})$ for discrete $k \in \{0, 1, \ldots, K-1\}$ — a probability distribution over categories. Using MSE for classification creates a loss surface with flat regions (gradient $\approx 0$) where the sigmoid saturates, stalling gradient descent. Cross-entropy fixes this because $-\log(\sigma(z))$ has gradient $\sigma(z) - 1$, which remains large even when $\sigma(z)$ is near 0 or 1.

The sigmoid $\sigma(z) = \frac{1}{1 + e^{-z}}$ maps $\mathbb{R} \to (0, 1)$. Its derivative is $\sigma'(z) = \sigma(z)(1 - \sigma(z))$, which peaks at $z = 0$ (value $0.25$) and vanishes exponentially as $|z| \to \infty$. The sigmoid is the canonical link function for Bernoulli-distributed responses in generalized linear models. It arises naturally from the log-odds: if $\log \frac{P(y=1)}{P(y=0)} = z$ (a linear function of features), then solving for $P(y=1)$ gives exactly the sigmoid. The inverse is the logit function: $\sigma^{-1}(p) = \log(p/(1-p))$.

The symmetry $\sigma(-z) = 1 - \sigma(z)$ means the sigmoid is symmetric about the point $(0, 0.5)$. This implies that if the linear score $z$ flips sign, the predicted probability for class 1 and class 0 swap. Saturation at the extremes ($\sigma(z) \approx 0$ for $z \ll 0$ and $\sigma(z) \approx 1$ for $z \gg 0$) means the function is approximately linear only in a narrow band around $z = 0$ where $\sigma(z) \approx 0.5 + 0.25z$. Outside this band, changes in $z$ barely affect the output.

The decision rule $\hat{y} = 1$ if $\sigma(z) \geq t$ is equivalent to $\hat{y} = 1$ if $z \geq \log\frac{t}{1-t}$ (the logit of $t$). At $t = 0.5$, the boundary is $z = 0$. Lowering $t$ to 0.1 shifts the boundary to $z = \log(1/9) \approx -2.2$, dramatically expanding the positive prediction region. The optimal threshold minimizes expected cost: $t^* = \frac{C_{FP}}{C_{FP} + C_{FN}}$, where $C_{FP}$ and $C_{FN}$ are the costs of false positives and false negatives respectively.

The decision boundary $\{\mathbf{x} : \mathbf{w}^T\mathbf{x} + b = 0\}$ is a hyperplane in $\mathbb{R}^p$ with normal vector $\mathbf{w}$. The signed distance from any point $\mathbf{x}_0$ to this hyperplane is $\frac{\mathbf{w}^T \mathbf{x}_0 + b}{\|\mathbf{w}\|}$, which is proportional to the log-odds. Points farther from the boundary have higher confidence. The margin (distance between the nearest points of each class and the boundary) determines how robust the classifier is to small perturbations in the input.

The ROC curve plots true positive rate $TPR = TP/(TP+FN)$ against false positive rate $FPR = FP/(FP+TN)$ as the threshold varies from 0 to 1. The area under this curve (AUC) measures discrimination ability independent of threshold. The precision-recall curve is more informative for imbalanced data: precision $= TP/(TP+FP)$ and recall $= TP/(TP+FN)$ directly reflect performance on the minority class. The $F_1$ score $= 2 \cdot \frac{\text{precision} \cdot \text{recall}}{\text{precision} + \text{recall}}$ summarizes the tradeoff as a single number.

The model $P(y=1|\mathbf{x}) = \sigma(\mathbf{w}^T \mathbf{x} + b)$ is a discriminative classifier — it directly models the posterior $P(y|\mathbf{x})$ without modeling the joint distribution $P(\mathbf{x}, y)$. The weight vector $\mathbf{w}$ is perpendicular to the decision boundary, and $b/\|\mathbf{w}\|$ is the signed distance from the origin to the boundary. Each weight $w_j$ represents the change in log-odds per unit change in feature $x_j$: $\frac{\partial}{\partial x_j} \log\frac{P(y=1)}{P(y=0)} = w_j$.

The loss $J = -\frac{1}{n}\sum[y_i \log \hat{y}_i + (1-y_i)\log(1-\hat{y}_i)]$ is derived from the negative log-likelihood of the Bernoulli distribution. For $y=1$, the loss is $-\log \hat{y}$, which goes to infinity as $\hat{y} \to 0$ (confident wrong prediction). The loss surface is convex in $\mathbf{w}$ when the model is $\hat{y} = \sigma(\mathbf{w}^T\mathbf{x})$, guaranteeing a unique global minimum. Information-theoretically, cross-entropy $H(p, q)$ measures the expected number of bits needed to encode events from distribution $p$ using a code optimized for distribution $q$.

Maximum likelihood seeks $\mathbf{w}^* = \arg\max_\mathbf{w} \prod_i P(y_i | \mathbf{x}_i; \mathbf{w})$. Taking the log and negating converts the product to a sum and max to min: $\mathbf{w}^* = \arg\min_\mathbf{w} -\sum_i \log P(y_i | \mathbf{x}_i; \mathbf{w})$, which is exactly cross-entropy. This means minimizing cross-entropy is equivalent to finding the parameters that make the observed labels most probable under the model. The MLE has desirable statistical properties: it is consistent (converges to true parameters as $n \to \infty$) and asymptotically efficient (lowest variance among unbiased estimators).

The gradient $\frac{\partial J}{\partial w_j} = \frac{1}{n}\sum_i (\hat{y}_i - y_i) x_{ij}$ has the same form as linear regression's gradient — the sigmoid's derivative cancels neatly with the log in cross-entropy. This is not a coincidence: both are members of the exponential family, and the gradient of the negative log-likelihood always takes the form $(\text{prediction} - \text{target}) \times \text{input}$. This elegant form means the same gradient descent code works for both linear and logistic regression with only the loss function changed.

The odds ratio $\frac{P(y=1)}{P(y=0)} = e^{\mathbf{w}^T\mathbf{x} + b}$ is the exponential of the linear predictor. The log-odds (logit) $\log\frac{P}{1-P} = \mathbf{w}^T\mathbf{x} + b$ is linear in the features, which is why logistic regression is a linear classifier despite having a nonlinear output. A unit increase in $x_j$ multiplies the odds by $e^{w_j}$: if $w_j = 0.7$, the odds double ($e^{0.7} \approx 2.0$). This multiplicative interpretation makes logistic regression highly interpretable in domains like medicine and social science.

Adding L2 penalty gives $J = -\frac{1}{n}\sum[y\log\hat{y} + (1-y)\log(1-\hat{y})] + \lambda\|\mathbf{w}\|^2$. The penalty prevents weights from growing to infinity when classes are perfectly separable — without regularization, the optimizer keeps increasing $\|\mathbf{w}\|$ to make the sigmoid steeper, approaching a hard step function. Regularization caps this growth, maintaining a smooth probability transition and better generalization. In scikit-learn, the parameter $C = 1/\lambda$ inverts the convention: larger $C$ means less regularization.

For a binary feature $x_j \in \{0, 1\}$, the weight $w_j$ equals the log odds-ratio: $\log\frac{\text{odds when } x_j = 1}{\text{odds when } x_j = 0} = w_j$. For a continuous feature, $w_j$ represents the change in log-odds per unit increase. After standardization, the magnitude $|w_j|$ indicates relative feature importance. Confidence intervals for $w_j$ can be computed from the Fisher information matrix $I(\mathbf{w}) = \frac{1}{n} X^T \text{diag}(\hat{y}_i(1-\hat{y}_i)) X$, giving $w_j \pm z_{\alpha/2} \sqrt{[I^{-1}]_{jj}}$.

OvR trains $K$ binary classifiers $f_k(\mathbf{x})$, each treating class $k$ as positive and all others as negative. Prediction assigns the class with the highest score: $\hat{y} = \arg\max_k f_k(\mathbf{x})$. Training cost is $O(K)$ times a single binary classifier. The key limitation: each classifier sees a different class imbalance (1 class vs. $K-1$), which biases probability estimates. Platt scaling (fitting a sigmoid on the scores) can calibrate the outputs, but fundamentally the $K$ classifiers are not jointly optimized.

OvO trains $\binom{K}{2} = K(K-1)/2$ classifiers, one per class pair. Prediction uses majority voting: each classifier casts a vote, and the class with the most votes wins. For $K = 10$, this means 45 classifiers, but each trains on only 2 classes (smaller subsets). OvO is preferred for kernel methods like SVMs where training cost is superlinear in $n$ — training 45 small classifiers is faster than 10 large ones. The drawback: prediction time grows as $O(K^2)$ since every classifier must be evaluated.

Softmax converts $K$ raw scores into a probability distribution: $P(y = k) = \frac{e^{z_k}}{\sum_{j=1}^{K} e^{z_j}}$ where $z_k = \mathbf{w}_k^T \mathbf{x} + b_k$. This requires $K \times p$ weight parameters (a weight vector per class). The softmax function is the multi-class generalization of the sigmoid: for $K = 2$, softmax reduces to sigmoid. The temperature parameter $\tau$ controls confidence: $P(y=k) = \frac{e^{z_k / \tau}}{\sum e^{z_j / \tau}}$ — as $\tau \to 0$, the distribution becomes one-hot; as $\tau \to \infty$, it becomes uniform.

Softmax is invariant to constant shifts: $\text{softmax}(\mathbf{z} + c) = \text{softmax}(\mathbf{z})$ for any scalar $c$. This is exploited for numerical stability by subtracting $\max(z_k)$ before exponentiating, preventing overflow. The Jacobian $\frac{\partial P_k}{\partial z_j} = P_k(\delta_{kj} - P_j)$ has the same form as the sigmoid derivative when $K = 2$. Softmax outputs are calibrated probabilities only when trained with cross-entropy loss — otherwise the outputs may be overconfident or underconfident and require temperature scaling.

The multiclass cross-entropy loss $J = -\frac{1}{n}\sum_{i=1}^{n}\sum_{k=1}^{K} y_{ik} \log \hat{y}_{ik}$ uses one-hot encoded labels where $y_{ik} = 1$ if sample $i$ belongs to class $k$. This simplifies to $J = -\frac{1}{n}\sum_i \log \hat{y}_{i, c_i}$ where $c_i$ is the true class. The gradient $\frac{\partial J}{\partial z_k} = \hat{y}_k - y_k$ has the same elegant form as the binary case. Cross-entropy is the KL divergence between the true label distribution and the model's predicted distribution, plus the entropy of the true distribution (which is constant).

Multiclass: each sample belongs to exactly one of $K$ mutually exclusive classes — outputs sum to 1 via softmax. Multilabel: each sample can belong to multiple classes simultaneously — each output is an independent sigmoid $\sigma(z_k)$ producing $K$ independent probabilities. The loss for multilabel is the sum of $K$ binary cross-entropies. A photo can be tagged "cat" AND "outdoor" (multilabel) but a tumor can only be "benign" OR "malignant" (multiclass). The distinction determines the output activation (softmax vs. independent sigmoids) and loss function.

Bayes' theorem $P(y|\mathbf{x}) = \frac{P(\mathbf{x}|y) P(y)}{P(\mathbf{x})}$ inverts the direction of conditioning. The prior $P(y)$ encodes class frequency in the training data. The likelihood $P(\mathbf{x}|y)$ captures the distribution of features within each class. The evidence $P(\mathbf{x}) = \sum_k P(\mathbf{x}|y=k)P(y=k)$ is a normalizing constant. Since we only need $\arg\max_y P(y|\mathbf{x})$, we can ignore $P(\mathbf{x})$ and compare numerators directly. This makes Naive Bayes a generative classifier — it models the joint $P(\mathbf{x}, y)$ rather than the posterior $P(y|\mathbf{x})$ directly.

The "naive" assumption $P(\mathbf{x}|y) = \prod_{j=1}^{p} P(x_j|y)$ factorizes the joint likelihood into a product of marginals. This reduces the number of parameters from $O(d^p)$ (full joint) to $O(dp)$ (marginals), making estimation feasible with limited data. The assumption is almost always violated in practice — features like "word A" and "word B" co-occur in spam emails. Despite this, Naive Bayes often works well because classification only requires getting the ranking of $P(y|\mathbf{x})$ correct, not the exact probabilities. The decision boundary is still correct even when probability estimates are poorly calibrated.

The decision rule $\hat{y} = \arg\max_k P(y=k) \prod_j P(x_j|y=k)$ avoids computing the denominator $P(\mathbf{x})$. In practice, we work with log-probabilities: $\hat{y} = \arg\max_k [\log P(y=k) + \sum_j \log P(x_j|y=k)]$ to avoid numerical underflow from multiplying many small probabilities. The decision boundary is linear in the log-probability space: $\log P(y=1|\mathbf{x}) - \log P(y=0|\mathbf{x}) = 0$ defines a hyperplane when the class-conditional distributions are Gaussian with equal covariance.

Assumes $P(x_j | y = k) = \mathcal{N}(\mu_{jk}, \sigma_{jk}^2)$ — each feature follows a Gaussian distribution within each class, with class-specific mean $\mu_{jk}$ and variance $\sigma_{jk}^2$. This requires estimating $2pK$ parameters ($\mu$ and $\sigma^2$ for each feature-class pair). The log-likelihood for feature $j$ given class $k$ is $-\frac{1}{2}\log(2\pi\sigma_{jk}^2) - \frac{(x_j - \mu_{jk})^2}{2\sigma_{jk}^2}$. The decision boundary between classes depends on the quadratic $(x_j - \mu_{j1})^2/\sigma_{j1}^2$ vs. $(x_j - \mu_{j0})^2/\sigma_{j0}^2$ terms.

For text classification with word counts, $P(x_j|y=k) = \theta_{jk}$ where $\theta_{jk}$ is the probability of word $j$ appearing in class $k$. Given a document with word counts $\mathbf{x} = (x_1, \ldots, x_V)$ for vocabulary of size $V$, the likelihood is $P(\mathbf{x}|y=k) \propto \prod_j \theta_{jk}^{x_j}$. Parameters are estimated by counting: $\hat{\theta}_{jk} = \frac{\text{count of word } j \text{ in class } k}{\text{total words in class } k}$. This is the maximum likelihood estimate for the multinomial distribution.

Adding a pseudocount $\alpha$ to every word-class count: $\hat{\theta}_{jk} = \frac{n_{jk} + \alpha}{n_k + \alpha V}$ where $V$ is vocabulary size. Without smoothing, a word never seen in class $k$ gives $P(x_j|y=k) = 0$, zeroing out the entire posterior regardless of other features. With $\alpha = 1$ (Laplace), unseen words get probability $1/(n_k + V)$ instead of 0. This is equivalent to placing a uniform Dirichlet prior $\text{Dir}(\alpha, \ldots, \alpha)$ on the multinomial parameters — a Bayesian approach where the prior regularizes the maximum likelihood estimate.

With class ratio 1:100, a model predicting the majority class always achieves 99% accuracy but 0% recall on the minority class. The loss function is dominated by the majority class: $J = \frac{1}{n}(n_{maj} \cdot J_{maj} + n_{min} \cdot J_{min})$, and since $n_{maj} \gg n_{min}$, the gradient points almost entirely toward minimizing majority class errors. The decision threshold at $P = 0.5$ is miscalibrated — the model's estimated $P(y=1|\mathbf{x})$ is biased toward the prior $P(y=1)$, so even samples that are truly positive often get probabilities below 0.5.

Random oversampling duplicates minority class examples, creating a balanced training set. SMOTE (Synthetic Minority Over-sampling TEchnique) generates synthetic examples by interpolating between nearest neighbors: $\mathbf{x}_{new} = \mathbf{x}_i + \lambda(\mathbf{x}_{nn} - \mathbf{x}_i)$ where $\lambda \sim U(0, 1)$. This expands the minority class region in feature space rather than just duplicating points. The risk is generating noisy synthetic points in overlapping regions between classes, which can blur the decision boundary.

Random undersampling discards majority class examples to match minority count. This is simple but throws away potentially useful data — if the minority class has 100 samples, we keep only 100 of 10,000 majority samples. Informed undersampling methods like Tomek Links remove majority samples that are nearest neighbors of minority samples (cleaning the boundary region). Ensemble approaches like EasyEnsemble train multiple classifiers on different random subsets of the majority class, then combine predictions via voting.

Weighted loss $J = \frac{1}{n}\sum_i w_{y_i} \cdot L_i$ assigns weight $w_k \propto 1/n_k$ to class $k$, so each class contributes equally to the total loss regardless of size. With 100:1 ratio, minority samples get weight 100. This is equivalent to oversampling without actually duplicating data. In scikit-learn, class_weight='balanced' computes $w_k = \frac{n}{K \cdot n_k}$. The gradient for a minority sample becomes 100$\times$ larger, forcing the model to pay attention to minority class errors during optimization.

Even with balanced training, the default threshold of 0.5 may not be optimal. For imbalanced problems, the optimal threshold is often lower than 0.5 because we want to catch more minority class instances. The precision-recall curve directly shows the tradeoff for each threshold. The optimal threshold can be selected to maximize $F_\beta$ score: $F_\beta = (1 + \beta^2) \frac{\text{precision} \cdot \text{recall}}{\beta^2 \cdot \text{precision} + \text{recall}}$, where $\beta > 1$ weighs recall higher (appropriate when missing positives is costly).

Accuracy is misleading for imbalanced data — always predict majority class for 99% accuracy with 0% minority recall. Better metrics: precision $= \frac{TP}{TP+FP}$ (of those predicted positive, how many are correct), recall $= \frac{TP}{TP+FN}$ (of those actually positive, how many did we find), and $F_1 = \frac{2 \cdot P \cdot R}{P + R}$ (harmonic mean — low if either is low). Matthews Correlation Coefficient $MCC = \frac{TP \cdot TN - FP \cdot FN}{\sqrt{(TP+FP)(TP+FN)(TN+FP)(TN+FN)}}$ uses all four confusion matrix entries and ranges from -1 to +1.

Adding polynomial terms $[x, x^2, x^3, \ldots]$ and interaction terms $[x_1 x_2, x_1 x_3, \ldots]$ enables linear classifiers to learn nonlinear decision boundaries. The decision boundary $\mathbf{w}^T \phi(\mathbf{x}) + b = 0$ is linear in the transformed space $\phi(\mathbf{x})$ but nonlinear in the original space $\mathbf{x}$. For example, $w_1 x_1^2 + w_2 x_2^2 + b = 0$ defines a circle or ellipse in $(x_1, x_2)$ space. The number of degree-$d$ features for $p$ inputs is $\binom{p+d}{d}$, which grows rapidly.

Gradient-based optimizers converge faster when features have similar scales. Standardization ($z = (x-\mu)/\sigma$) centers at zero with unit variance; normalization ($z = (x-x_{min})/(x_{max}-x_{min})$) maps to $[0,1]$. For logistic regression, unscaled features cause the loss landscape to have elongated contours — gradient descent zigzags instead of heading straight to the minimum. Distance-based methods (KNN, SVM) are particularly sensitive: a feature ranging 0-1000 will dominate Euclidean distance over a feature ranging 0-1.

Converts a categorical variable with $K$ levels into $K$ binary columns: category $k$ maps to a vector with 1 in position $k$ and 0 elsewhere. For linear models, use $K-1$ columns (drop one as reference) to avoid perfect multicollinearity with the intercept — the dropped category's effect is absorbed into the intercept. One-hot encoding preserves the categorical nature: the model can learn a different coefficient for each level. The cost is dimensionality — a feature with 1000 categories adds 999 dimensions.

Maps each category to an integer: $\{\text{cat}, \text{dog}, \text{bird}\} \to \{0, 1, 2\}$. This implicitly assumes an ordinal relationship (dog is "between" cat and bird), which is incorrect for nominal categories. For tree-based models (decision trees, random forests), label encoding works fine because splits like $x \leq 1$ can isolate any subset of categories. For linear models, the imposed ordering introduces spurious linear relationships — always use one-hot encoding for nominal features with linear classifiers.

Replaces each category level with the mean of the target variable for that level: $\text{encode}(k) = E[y | x = k]$. This reduces a high-cardinality feature (e.g., zip code with 40,000 levels) to a single numeric column while preserving predictive information. The risk is target leakage: the encoding uses $y$ values from the training set, which can overfit — rare categories with few samples get noisy estimates. Regularization strategies include adding noise, using leave-one-out encoding (exclude the current sample's $y$), or Bayesian shrinkage toward the global mean.

Filter methods rank features by statistical association with the target, independent of the model. Common scores: mutual information $I(X_j; Y) = \sum P(x_j, y) \log \frac{P(x_j, y)}{P(x_j)P(y)}$ (captures nonlinear dependencies), chi-squared $\chi^2 = \sum \frac{(O - E)^2}{E}$ (for categorical features), and ANOVA F-statistic (ratio of between-group to within-group variance). Filter methods are fast ($O(np)$) but evaluate features independently — they miss redundant features and informative feature combinations.

Wrapper methods evaluate feature subsets by training and testing the actual model. Forward selection starts with zero features and greedily adds the best one at each step ($O(p^2)$ model fits). Backward elimination starts with all features and removes the least useful ($O(p^2)$ fits). Exhaustive search over all $2^p$ subsets is optimal but intractable for $p > 20$. Recursive Feature Elimination (RFE) trains the model, ranks features by importance (e.g., weight magnitude), removes the weakest, and repeats — a practical approximation to backward elimination.

PCA finds directions of maximum variance: the first principal component $\mathbf{v}_1 = \arg\max_{\|v\|=1} \text{Var}(X\mathbf{v})$ captures the most variance, and subsequent components are orthogonal. The eigenvalues $\lambda_1 \geq \lambda_2 \geq \cdots$ of the covariance matrix measure variance along each component. Retaining $k$ components that explain 95% of total variance ($\sum_{i=1}^k \lambda_i / \sum \lambda_i \geq 0.95$) is a common heuristic. Unlike feature selection, PCA creates new features that are linear combinations of originals, making interpretation harder but often capturing more information in fewer dimensions.