Machine Learning

Predictive tasks

Target variable from number of features: classification, regression & predictive clustering

Classification

Predicts categorical target variable from set of features (image classification)

Regression

Predicts numerical target variable from set of features (weather temperature forecast)

Predictive clustering

Predicts hidden/latent variable from features and assign labels to clusters of data (fraud detection)

Descriptive tasks

Exploits underlying structure of the data: descriptive clustering, association rule mining & sub-group discovery

Descriptive clustering

Represents different groups in data without predicting the target (pattern mining)

Association rule mining

Rule-based task for relations between variables (online shopping recs)

Sub-group discovery

Associations among variables with respect to property of interest (pattern findings)

Supervised learning

Training set of examples (instances labelled with target value)

Unsupervised learning

No training set examples

First categorisation (main intuition)

Geometric models, probabilistic models & logical models

Second categorisation (modus operandi)

Grouping models & grading models

Bayes Rule

P(Y|X) = (P(X|Y)P(Y)) / P(X)
Posterior = P(Y|X)
Likelihood = P(X|Y)
Prior = P(Y)
Evidence = P(X)

Declarative

Model can be translated into rules for humans

Grouping models

Break instance space into groups/segments.
Fixed and finite resolution.
Cannot distinguish individual instances beyond resolution.

Grading models

Global over instance space.
Infinite resolution (Cartesian space).

Training phase (learning)

Create model to perform tasks using training set of numerous data points (slow).

Inference phase

Use model to perform task on new data points.

Classifier

Mapping where the instances are finite with small set of class labels

Precision/confidence

c(^)(x) = c(x) = +
———————-
c(^)(x) = +

Positive predicted and reality divided by positive predicted.

Notation for formulas

c(x) = reality (ground truth)
c(^)(x) = prediction (of the model)

Accuracy

c(^)(x) = c(x)
——————
total

Predicted and actual are the same.

Error rate

c(^)(x) =! c(x)
——————
total
Predicted and actual are not the same.

True positive rate (sensitivity)

c(^)(x) = c(x) = +
———————
c(x) = +

Positive predicted and actual divided by actual positive.

True negative rate (specificity)

c(^)(x) = c(x) = -
———————
c(x) = -

Negative predicted and actual divided by actual negative.

False positive rate

Predicted positive&actual negative divided by actual negatives.

False negative rate

Predicted negative&actual positive divided by actual positive.

Sensitivity

How many relevant are selected.

Specificity

How many negative selected are negative.

Precision

How many selected are relevant.

Recall

How many relevant are selected.

F-measure/score

2
—————— = 2 x precxrec/prec+rec
1/prec + 1/rec

Train-test splits

Tets set makes predictions in inference phase on data not used in training phase.

Overfitting

Performs well on training data, bad on test data.

Underfitting

Performs bad on both training and test data.

Low generalisability

Overfitting and underfitting.

Decision rule τ

Coverage plot and ROC curve summarize confusion matrices

AUC (area under the curve)

Summary of the model skills.

Scoring classifier

Maps instance space to a k-vector of real numbers.

Loss function

Maps each example margin to loss (L(z(x)) and rewards positive margins and penalizes negative margins.

Probability estimator

Scoring classifier which outputs probability vector over classes. How likely an instance belongs to a class.

Mean squared error (MSE)

Average squared error (SE)

Validating classifiers

Classification (contingency tables, train/test), scoring and ranking & probability estimation.

One vs rest

Learning: train k or k-1 separate classes.
Inference: use classifiers and form a code word based on output.

One vs one or all pairs

Training: separate classifiers for each pair of classes.
Inference: use classifications for code word and compare to all rows and find nearest row.

One versus all complexity

Training: O(km^α)
Inference: O(kβ)

One vs one complexity

Training: O(k²(m/k)^α
Inference: O(k²β)

Macro-average (binary classifier ROC)

TPR₁ + TPR₂ + TPR₃ / 3

Micro-average (binary classifier ROC)

TP₁ + TP₂ + TP₃ / TP₁ + TP₂ + TP₃ + FN₁ + FN₂ + FN₃

Bias-variance dilemma

Low complexity model suffers less from variability (random variations in the training data) but systematic bias. High complexity model eliminates bias but suffers non-systematic errors due to variance.

Distance based clustering

Depend on centre of mass or exemplar.

Exemplar

Minimises some distance-related quantity over all instances (scatter).

Rand-index

Accuracy

Silhouette coefficent

s = b-a / max(a,b)
a: mean distance between instance and points in same cluster.
b: mean distance between instance and points in nearest cluster.

Subgroup discovery

Supervised learning task. Addresses discovery of interesting population subgroups.

Chi-squared test

χ² = Σ (O_i - E_i)² / E_i
E_i: expected value.
O_i: observed value.

Trees

Decision trees, random forest & gradient boosting.

Empirical probability

p(^.) = n⁺ / n⁺ + n^-

Minority class (misclassification error)

Notation for p(^.) = x
min(x, 1-x)

Entropy

Notation for p(^.) = x
-xlog₂x(1-x)log₂(1-x)
Amount of information in terms of number of bits needed to encode probability of an event.
Higher probability → less number of bits.

Gini index

Notation for p(^.) = x
2x(1-x)

Purity gain

Original entropy - entropy after splitting.

Limiting number of threshold

One split in space between two observed values.
Only splits between examples from different classes can improve info gain.

Preventing overfitting

Limit number of iterations.
Pruning the tree (removing branches).

Reduced error pruning

Start at leaves and replace each node with majority class.
Keep change if prediction accuracy is not affected and keep a validation set.

Sources of imbalance

Asymmetric class distribution and mis-classification cost.

Gini

n₁⁺ n₁^- / n_{1
——————}
n⁺ n^- / n

Squared Gini

Minimises relative impurity and is insensitive to changes in class distribution.

Classification trees

Minority class, entropy & Gini index.

Regression trees

Variance

Coefficient of determination

R² = 1 - RSS/TSS

Solutions of outliers

1. Ordinary leasts squares method: train model, filter noisy points & retrain.

2. Total least squares method: generalize least squares method so x and y are noisy (not always unique).

Perceptron

Linear classifier that will achieve perfect separation on linearly separable data. Iterates over training set and updates weight vector every time it encounters an incorrect classified example.

Neural network

Weight vector: w with length #features+1
Learning rate: η showing how fast the perceptron converges to the separating line (0<η<1).

SVM

Optimal decision boundary between different classes.

Margin

m / ||w||

m: distance between decision boundary and nearest training instances as measured along w.

Optimisation problem (maximising margin)

w*, t* = argmin1/2||w||²

Slack variables

Allows examples to be inside the margin or on the wrong side.

Complexity parameter

Trades off margin maximisation against slack variable minimisation.

Non-linear transformation

From original input space to new feature space (kernels).

Kernel

Calculates the dot product in feature space directly from the vectors in the original space.

Kernel trick

Calculate dot product in some feature space but without constructing the feature vectors acquired by φ(x) explicitly.

Feature statistics

Statistics of central tendency, statistic of dispersion & shape statistics.

Range

Difference min and max.

Midrange point

Mean of two extreme values.

p-th percentile

p per cent of the instances fall below it

First central moment

Average deviation from the mean (0).

Second central moment

Average squared deviation from the mean (variance).

Skewness

m₃ / σ³

Kurtosis

m₄/σ⁴

Categorical/nominal features

Do not allow any statistical summary except the node.

Ordinal features

Ordening but no scale.

Quantitative features

Mapping into the reals.

Normalisation

Quantitative to quantitative

Calibration

Ordinal, categorical & boolean to quantitative

Discretisation

Quantitative to ordinal & categorical

Ordering

Ordinal, categorical & boolean to ordinal

Unordering

Ordinal to categorical

Grouping

Categorical to categorical

Thresholding

Quantitative & ordinal to boolean