GATE Machine Learning formula sheet

103 formulas in 7 topics, each with when to use it. Each is explained in the topic notes.

MEAN SQUARED ERROR (MSE)

MSE (w) = \frac{1}{n} i = 1 \sum n (y_{i} - \overset{y}{^}_{i})^{2} = \frac{1}{n} ∥ y - X w ∥^{2}

Average squared residual; the sum of squared errors (SSE) is the same without the factor $1/ n$ . Minimising either gives the same $w$ .

LEAST-SQUARES SLOPE AND INTERCEPT

\hat{β}_{1} = \frac{S _{x y}}{S _{xx}} = \frac{\sum x _{i} y _{i} - n x ˉ y ˉ}{\sum x _{i}^{2} - n x ˉ ^{2}}, \hat{β}_{0} = \overset{y}{ˉ} - \hat{β}_{1} \overset{x}{ˉ}

Needs at least two distinct $x$ values ( $S_{xx} > 0$ ). The fitted line always passes through $(\overset{x}{ˉ}, \overset{y}{ˉ})$ .

Logistic regression, k-nearest neighbour and naive Bayes

All 21 formulas

SIGMOID (LOGISTIC FUNCTION)

σ (z) = \frac{1}{1 + e ^{- z}}

The output lies in (0, 1). $σ (0) = 0.5$ ; $σ (z) \to 1$ as $z \to \infty$ and $σ (z) \to 0$ as $z \to - \infty$ .

SIGMOID IDENTITIES

σ (- z) = 1 - σ (z), σ^{'} (z) = σ (z) (1 - σ (z))

The derivative is at most 0.25, reached at $z = 0$ . This identity is what makes the gradient of the cross-entropy loss so simple.

Linear discriminant analysis, support vector machines and decision trees

All 18 formulas

DISTANCE OF A POINT FROM A HYPERPLANE

d (x_{0}) = \frac{∣ w \cdot x _{0} + b ∣}{∥ w ∥}

Euclidean distance from $x_{0}$ to the hyperplane $w \cdot x + b = 0$ , for $w \neq = 0$ .

LDA PARAMETER ESTIMATES (POOLED COVARIANCE)

\hat{μ}_{k} = \frac{1}{n _{k}} i : y_{i} = k \sum x_{i}, \overset{π}{^}_{k} = \frac{n _{k}}{n}, \hat{Σ} = \frac{1}{n - K} k = 1 \sum K i : y_{i} = k \sum (x_{i} - \hat{μ}_{k}) (x_{i} - \hat{μ}_{k})^{T}

Class means, priors and the pooled within-class covariance, where $n_{k}$ is the number of samples in class $k$ . Dividing by $n$ instead of $n - K$ only rescales $\hat{Σ}$ . With equal priors the decisions are unchanged. With unequal priors the $ln π_{k}$ term gets a slightly different relative weight, so borderline decisions can change.

Bias–variance trade-off and cross-validation

All 15 formulas

BIAS OF AN ESTIMATOR AT $X_0$

Bias (\hat{f} (x_{0})) = E [\hat{f} (x_{0})] - f (x_{0})

Systematic error: how far the average prediction over training sets is from the truth.

VARIANCE OF AN ESTIMATOR AT $X_0$

Var (\hat{f} (x_{0})) = E [(\hat{f} (x_{0}) - E [\hat{f} (x_{0})])^{2}]

Sensitivity: how much the prediction changes from one training set to another.

Multi-layer perceptrons and feed-forward neural networks

All 15 formulas

PERCEPTRON OUTPUT (STEP ACTIVATION)

z = w^{⊤} x + b, \overset{y}{^} = {10 z \geq 0 z < 0

Targets are 0 or 1. The tie z = 0 is assigned to class 1 here. A question may use the opposite tie rule or targets of -1 and +1, so read the convention given.

PERCEPTRON LEARNING RULE

w \leftarrow w + η (t - \overset{y}{^}) x, b \leftarrow b + η (t - \overset{y}{^})

Applied sample by sample, where t is the target. If the sample is classified correctly, t - y is 0 and nothing changes. A missed class-1 sample pulls w towards x, and a missed class-0 sample pushes w away from x.

Clustering: k-means, k-medoids and hierarchical clustering

All 14 formulas

EUCLIDEAN DISTANCE

d_{2} (x, y) = j = 1 \sum d (x_{j} - y_{j})^{2}

Default distance. k-means is built around its square.

MANHATTAN DISTANCE

d_{1} (x, y) = j = 1 \sum d ∣ x_{j} - y_{j} ∣

Sum of absolute coordinate differences. For (1,1) and (4,5): Manhattan = 3 + 4 = 7, Euclidean = 5.

Dimensionality reduction and principal component analysis

All 13 formulas

SAMPLE MEAN AND CENTRED DATA

\overset{ˉ}{x} = \frac{1}{n} i = 1 \sum n x_{i}, x_{i}^{c} = x_{i} - \overset{ˉ}{x}

Centre each feature (column) to mean zero. $X_{c}$ denotes the centred matrix, whose rows are $(x_{i}^{c})^{⊤}$ .

SAMPLE COVARIANCE MATRIX

S = \frac{1}{n - 1} X_{c}^{⊤} X_{c} \in R^{d \times d}

Symmetric and positive semi-definite. Diagonal entries are feature variances; off-diagonal entries are covariances. Some texts divide by $n$ instead. The eigenvectors and the proportions of variance do not change; every eigenvalue is scaled by the same factor.