Supervised Learning Models

Linear classifier decision region

A linear classifier predicts the class from the sign of an affine score f(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b. Its decision boundary is the hyperplane \mathbf{w}^\top \mathbf{x} + b = 0, which is a line in \mathbb{R}^2. The two decision regions are the open half-planes on either side of this boundary.

Two classes are linearly separable when some hyperplane strictly separates them, so every training point of one class has f > 0 and every point of the other class has f < 0. A practical test is to check whether the convex hulls of the two classes intersect. If a point of one class lies inside the convex hull of the other class, no line can separate them. If the segments joining opposite-class pairs share a common midpoint, the convex hulls intersect.

The separating hyperplane is generally not unique. Among all separating lines, a hard-margin SVM selects the one with the largest gap to the nearest points, and the points lying on that gap are the support vectors. When several points lie on the margin, the set of support vectors may be one of several admissible choices.

A nearest-mean classifier compares squared Euclidean distances to two class means. Expanding the squared norms, the \|\mathbf{x}\|^2 terms cancel in the difference, so the rule reduces to \mathbf{w}^\top \mathbf{x} + b with \mathbf{w} = 2(\boldsymbol{\mu}_2 - \boldsymbol{\mu}_1) and b = \|\boldsymbol{\mu}_1\|^2 - \|\boldsymbol{\mu}_2\|^2. The decision boundary is therefore a hyperplane, even though the raw expression looks quadratic.

Naive Bayes parameter count

Naive Bayes assumes that the features are conditionally independent given the class, so P(\mathbf{x}\mid C_j) = \prod_k P(x_k \mid C_j). This assumption is what keeps the number of parameters small. A full joint model over K binary attributes needs 2^K - 1 free values per class, which grows exponentially, whereas naive Bayes grows linearly.

For a two-class problem with K binary attributes, the parameters are as follows. The class prior P(C_1) is one free number, since P(C_2) = 1 - P(C_1). For each class and each attribute, one conditional probability such as P(x_k = 1 \mid C_j) is needed, because the value x_k = 0 has the complementary probability. This gives 2K parameters, and the total is 2K + 1.

For an attribute with m categorical values, each class needs m - 1 free parameters. The decision rule chooses the class with the largest unnormalised score P(C_j)\,P(\mathbf{x}\mid C_j). For a given \mathbf{x}, the probability of misclassification equals the posterior of the class that is not chosen, that is, 1 minus the maximum posterior. For example, with priors 0.5 and 0.5 and likelihoods 0.2 and 0.6, the scores are 0.1 and 0.3, the posteriors are 0.25 and 0.75, the second class is chosen, and the error probability is 0.25.

ReLU neural network computation

A ReLU unit computes \max(0, z), where z is its weighted input plus bias. ReLU is the identity on non-negative inputs and zero on negative inputs. A network built from ReLU units therefore acts as a fixed linear map on any input region where the sign of every pre-activation stays unchanged.

If all inputs are positive and all weights are non-negative, every pre-activation is non-negative, so every ReLU passes its input unchanged and the whole network is linear in its inputs. In that case the coefficient of each input is the sum, over all paths from that input to the output, of the product of the weights along the path. Two such networks are equivalent when they give the same coefficient for every input. For example, a path with weights a and b contributes ab to the coefficient. Multiplying one layer's weights by a constant scales the output by the product of the constants along the path.

For backpropagation, the derivative of the output with respect to a weight is the product of the chain-rule factors along the path, where each ReLU contributes 1 if its pre-activation is positive and 0 if it is negative. A weight whose path passes through an inactive unit therefore has zero gradient. For example, if y = e\,R(z_1) with z_1 = au + bv, then \partial y/\partial a = e\,u when z_1 > 0 and \partial y/\partial a = 0 when z_1 < 0. The same rule applies to weights in a parallel branch whose unit is inactive.

Ridge regression regularization

Ridge regression minimises the squared-error loss plus an L_2 penalty, \sum_i (y_i - \mathbf{w}^\top \mathbf{x}_i)^2 + \lambda \|\mathbf{w}\|_2^2, where \lambda \ge 0 controls the strength of the penalty. The regularizer shrinks the coefficients toward zero. Unlike the L_1 penalty used in Lasso, it generally does not set coefficients exactly to zero, and it does not select features by counting negative weights.

The purpose of the penalty is to control overfitting, which means a model that fits the training data closely but generalises poorly to test data. Shrinking the weights introduces some bias into the estimate while reducing the variance of the predictions. This is the bias-variance trade-off, and it is the key idea behind the regularizer.

When the loss is an absolute error, the regularised objective for one instance is |y_{pred} - y_{true}| + \lambda \|\mathbf{w}\|_2^2. For example, with \mathbf{w} = (1, 2), \mathbf{x} = (3, 1), y_{true} = 5 and \lambda = 0.5, the prediction is 5, the error term is 0, and the penalty is 0.5 \cdot 5 = 2.5, so the total is 2.5. Remember to compute the penalty on the weights only, not on the prediction.

Generative vs discriminative models

A generative model learns the joint distribution P(\mathbf{x}, y) = P(\mathbf{x}\mid y)\,P(y). It models how the inputs are produced for each class, and it obtains the posterior P(y\mid \mathbf{x}) through Bayes' rule. Naive Bayes, Gaussian discriminant analysis and hidden Markov models are standard examples.

A discriminative model learns the conditional distribution P(y\mid \mathbf{x}) or the decision boundary directly, without modelling how \mathbf{x} is generated. Logistic regression, support vector machines, the perceptron and neural networks trained for classification are standard examples.

Dimensionality reduction is a different category. Principal component analysis is unsupervised and maps \mathbf{x} to a lower-dimensional representation that keeps the directions of maximum variance. It is neither a generative nor a discriminative classifier. Students often confuse these labels, so the matching should be checked against the model's purpose.

Fisher linear discriminant

Fisher's linear discriminant chooses a projection direction \mathbf{u} that maximises the ratio of between-class scatter to within-class scatter, J(\mathbf{u}) = \dfrac{\mathbf{u}^\top S_B \mathbf{u}}{\mathbf{u}^\top S_W \mathbf{u}}. Here S_B is the between-class scatter matrix and S_W is the within-class scatter matrix.

Setting the gradient of J to zero gives the generalised eigenvalue equation S_B \mathbf{u} = \lambda S_W \mathbf{u}, where \lambda = J(\mathbf{u}^*) at the optimum. If S_W is non-singular, multiplying by S_W^{-1} gives S_W^{-1} S_B \mathbf{u}^* = \lambda \mathbf{u}^*. The optimal direction is therefore the eigenvector of S_W^{-1} S_B with the largest eigenvalue, and the maximum value of J equals that eigenvalue. The order of the product matters, since S_B S_W^{-1} has different eigenvectors in general.