Machine Learning

Machine learning is the field of study that gives computers the ability to learn without being explicitly programmed (Arthur Samuel, 1959).

Can also be defined as:

• “Computational methods using experience to improve performance or to make accurate predictions”.
• “A computer observes some data, builds a model based on the data, and uses the model as both a hypothesis about the world and a piece of software that can solve problems”.
• “A set of methods that can automatically detect patterns in data, and then use the uncovered patterns to predict future data”.

Link to original

Types of ML

Supervised Learning

Supervised Learning

Supervised Learning: the program is ‘trained’ on a given set of examples (with labels). It learns how to reach an accurate conclusion when given new data.

Link to original

Components of successful machine learning

1. Representative training data: annotated data the model learns from
2. Sophisticated methods for extracting features used to represent data Features are easily observable properties of the data based on which the model will try to make predictions
3. Sophisticated choice of machine learning algorithm

How does supervised learning work?

We use $x_i$ to represent the attributes / features of some data, usually $D$ dimensional vectors of numbers. Can be complex objects e.g. coordinates, images, time series. We use $y_i$ to represent the class which some given data belongs to.

Start from a training set that contains the right answers $y_i$: $\mathcal{D}=\{(x_i,y_i){\}}_{i=1}^N$

The training set is a set of input features $x_i$ (can be a vector of values) and outputs $y_i$ (single elements / classes).

A supervised learning algorithm can study the training set and learn to classify iris flowers into the three different classes $y_i$ based on their features $x_i$ (Goodfellow et al., 2016)

The algorithm must then:

• Learns a function $f$ that maps from features $x_i$ to class $y_i$ $f(x_i)=y_i$
• Given $x_i$, says what the correct $y_i$ is
• Can predict a class using weighted combination of input features

We are particularly interested in $x_j$ such that $x_j,y_j\notin \mathcal{D}$, i.e. we want a learning model that performs well on new, never-before seen data. (we want the model to generalise well)

Suppose we want to recognise species of flowers

Our training data is iris flower pictures with appropriate annotations

Use $y_i$ to represent type of iris: ‘setosa’, ‘versicolor’, ‘virginica’ We can observe features such as petal area (length x width) and sepal area (length x width) as $x_i$.

Classification Problem (AI)

Classification (supervised): organise data in classes and determine the class of new data points $y\in \{1,\dots ,C\}$ Where $C$ is the number of classes.

Common form is binary classification where $C=2$, often written as $\{0,1\}$. If $C>2$ then we have multiclass classification.

Link to original

Abstract

We can think of classification as function approximation, that is assuming $y=f(x)$. We then ‘learn’ by trying to estimate $f$ by creating an estimate $\hat{f}$. After learning, we predict an estimate of $y$ using $\hat{y}=\hat{f}(x)$.

Classification is often not very clear at the boundaries, so we instead interpret the problem such that it returns a probability of being in each class given some input and the set of training data: $p(y_i|{\text{x}}_i,\mathcal{D})$

Probabilistic classifiers give a distribution over classes, so if we have $C$ classes, we get a probability for each class.

Sometimes we may want to explicitly consider the model: $p(y_i|{\text{x}}_i,\mathcal{D},M)$

We can decide on a single class by choosing the one with the highest probability given the input: $\hat{y}=\text{arg}{\max }_{c=1}^{C}p(y=c|{\text{x}}_i,\mathcal{D})$ This is the most likely class label. (mode of the distribution) We also refer to it as the MAP estimate (maximum a posteriori).

Regression Problem (AI)

Regression (supervised): fit functions to data and determine values of new data points Similar to classification, but the output is instead continuous.

Link to original

Abstract

In linear regression, we assume output $y$ is a linear combination of input $x$.

$$y(x)=\sum _{j=1}^D{w}_j{x}_j+ϵ$$

Where $w_j$ make up a weight vector $\mathbf{w}$ and $ϵ$ is the residual error.

‘Learning’ is the process of figuring out what $w_j$ should be to provide a good mapping. With different $w_j$, we get different functions $f$.

For a one dimensional input $x$, we write $\begin{array}{rl}\mathbf{x}& =(x_0,x_1)\\ x_0& =1\\ x_1& =x\end{array}$ Which is the same as saying $\text{x}=(1,x)$. Then $\bar{y}(\mathbf{x})=w_0+w_1{x}_1$.

We call $w_0$ the intercept or bias and $w_1$ is the slope.

Here $x_i\in \mathbb{R}$ and $y_i\in \mathbb{R}$ and the function $f(\mathbf{x})$ is a linear mapping from input to output:

Unsupervised Learning

Unsupervised Learning: the program is given a bunch of unlabelled data and must discover patterns and relationships in them.

In unsupervised learning:

• we are provided with a data set
• we need to find an understanding of interesting relationships within the data
• we identify groups / clusters of interesting information within the data
• can be used to identify where new points ‘fit’ within the data set

We use two common techniques: clustering and association rules.

Link to original

Abstract

We start from a set of examples $\mathcal{D}=\{{\mathbf{x}}_i{\}}_{i=1}^N$ and look for patterns / interesting structure in the data.

Unsupervised learning is sometimes called knowledge discovery. Our task is to build models of the form: $p({\mathbf{x}}_i|\mathcal{D})$

Clustering

Let $K$ be the number of clusters, we estimate the distribution over the number of clusters $p(K|\mathcal{D})$, often we simplify by approximating it by its mode: $K^{\ast }=\text{arg}{\max }_{K}p(K|\mathcal{D})$

Reinforcement Learning

Reinforcement Learning: the program learns from consequences of its actions (reward or punishment), rather than from being explicitly taught and selects its actions on basis of its past experiences (exploitation) and also by new choices (exploration).

Link to original

Parametric models

An ML technique is parametric if it makes assumptions about the structure of the data, otherwise it is non-parametric. (e.g. there are four Gaussian clusters)

Parametric models can be computationally simpler (linear regression) but the assumptions can lead to inaccuracy. Non-parametric models are more flexible (no assumptions) but intractable for large datasets.

Abstract

k-nearest neighbour (kNN) is a simple non-parametric classifier It looks at $k$ points in the training set that are nearest to the test input $x$

More sophisticated version uses $k$ nearest points to estimate probability of class membership: $p(y=c|\mathbf{x},\mathcal{D},K)=\frac{1}{K}{\sum }_{i\in N_K(\mathbf{x},\mathcal{D})}\mathcal{I}(y_i=c)$ Where $N_K(\mathbf{x},\mathcal{D})$ are the indices of the $k$ nearest points to $\mathbf{x}$ in $\mathcal{D}$ and $\mathcal{I}(e)$ is an indicator function such that: $\mathcal{I}(e)=\{\begin{array}{ll}1& \text{if }e\text{ is true}\\ 0& \text{if }e\text{ is false}\end{array}$ Counts how many members of each class are in the $k$ nearest set.

kNN classifiers are simple and work well but they scale badly with high dimensional inputs

The scalability of kNN is related to the more general problem of the curse of dimensionality:

• to better distinguish between examples, we need more features (dimensions)
• this leads to the need for more examples to determine how features distinguish
• otherwise, we overfit

This requirement grows exponentially.

One way to address this is to use parametric models, make sure assumption about best way to distinguish between examples. Meaning we assume something about the way examples are distributed / generated.

Overfitting

Overfitting is when the model fits too much to the training data and fails to generalise to unseen data. (see graph for degree 29)

Link to original

Performance measurement

In supervised learning, we look at “can we predict $y_i$ well given $x_i$?” We compute the misclassification rate: $\text{err}(F,\mathcal{D})=\frac{1}{N}{\sum }_{i=1}^N\mathcal{I}(F(x_i)\ne y)$ on the data we have as examples to learn from. Or its converse, proportion of correctly classified examples.

Abstract

This rate gives us some idea about whether we have learnt well from training data. But doesn’t say anything about new data (the generalisation error), that is, the misclassification rate on data we haven’t yet seen. We can estimate this by trying the classifier on test data that we didn’t see in training.

Learning curve

The learning curve is the % correct on test set as a function of training set size.

Link to original

We partition the training set into three subsets:

• training set (~80%)
• validation set (development set) (~10%) use for model selection / parameter tuning
• test set (~10%) always remains unseen and used to evaluate generalisation performance

K-fold cross-validation

If we don’t have enough training examples, we could use K-fold cross-validation (CV):

• Split data into $k$ equal subsets / folds to test on
• Train on $k-1$ sets and test on remainder fold only
• Repeat $k$ times (test on each fold only once)
• Computer misclassification error averaged over all $k$ test folds

The final performance is the average of the performances for each fold. Average test set score is a better estimate of the error rate than a single score. Common values of $k$ are $5$ and $10$, both giving error estimates that are very likely to be accurate.

Extreme case is when $k=n$, the number of data points.

Link to original

Accuracy (AI)

Accuracy: given a classification algorithm and a test set, the accuracy is the proportion of correct predictions done by the algorithm over all predictions in the test set $\text{accuracy}=\frac{\text{correct}}{\text{total}}$

Link to original

Abstract

In some practical applications, we may be more interested in false negatives than false positives. e.g. breast cancer detection, abusive language detection

Transclude of confusion-matrix

Precision

Precision: proportion of true positives over the true and false positives $\frac{\text{TP}}{\text{TP }+\text{ FP}}$

Link to original

Sensitivity

Sensitivity (or recall): proportion of true positives over true positives and false negatives $\frac{\text{TP}}{\text{TP }+\text{ FN}}$

Link to original

F1 Score

F1 Score: harmonic mean between sensitivity and precision $F_1=\frac{2}{{\text{recall}}^{-1}+{\text{precision}}^{-1}}$

The general weighted form looks like this: $F_{\beta }=\frac{1+{\beta }^2}{{\beta }^2{\text{precision}}^{-1}+{\text{recall}}^{-1}}$

Link to original

ROC Curve

We can plot the ROC Curve (TP against FP as we vary threshold).

Dotted line is performance of random classifier (on average). Area under curve is related to probability that the classifier will correctly classify a randomly chosen example. The closer we are to the top left, the better the model is.

Link to original

Evaluating clusters

If we know what the clusters should be, we can use classification methods above. Otherwise we try:

• external evaluation: how well the number of clusters serves a downstream task (e.g. market segmentation)
• internal evaluation: establish how coherent the clusters are and how well separated they are from each other

Abstract

The Davis-Bouldin index for $n$ clusters: $DB=\frac{1}{N}{\sum }_{i=1}^n{\max }_{j\ne i}\left(\begin{array}{c}\frac{{\sigma }_i+{\sigma }_j}{d(c_i,c_j)}\end{array}\right)$

Not in syllabus!