Week 6: Instance-Based Learning

Question 1

Instance-based Classification

Answer 1

To classify a new instance, search the memory for the training instance that most resembles the new instance. A distance metric is used to compare the training instances.

Main components:
- Distance Function, which calculates the distance between any two instances.
- Combination function, which combines results from neighbours to arrive at an answer

Pros:
- Not restricted by data format
- Efficiently adaptable to the additional of new instances
- Requires relatively low training effort

Cons:
- Memory intensive
- Can be more time consuming that neural networks or decision trees
- Making suitable distance and combination functions can be tough

Question 2

Similarity/Distance

Answer 2

This is the means by which different training instances can be measured for suitability with the new instance.

Question 3

Absolute Difference

Answer 3

\left\lvert x_{i,j} - x_{i^{‘}, j} \right\rvert

Question 4

Squared Difference

Answer 4

(x_{i,j} - x_{i^{‘},j})^2

Question 5

Normalised Absolute Value

Answer 5

\frac{\left\lvert x_{i,j} - x_{i^{‘},j} \right\rvert}{\max_j - \min_j}

Question 6

Absolute Difference of Standardised Values

Answer 6

\frac{\left\lvert x_{i,j} - \mu_j \right\rvert}{\sigma_j} - \frac{\left\lvert x_{i^{‘},j} - \mu_j \right\rvert}{\sigma_j}

Question 7

Distance Metric for Nominal Attributes

Answer 7

d(x_{i,j}, x_{i^{‘},j}) = \left{ \begin{array}{cc} 0, & if x_{i,j} = v and x_{i^{‘},j} = v \ 1 & if x_{i,j} = v and x_{i^{‘},j} \ne v \end{array}

Question 8

Euclidean Distance

Answer 8

d(\boldsymbol{x}i, \boldsymbol{x}{i^{‘}}) = \sqrt{\sum_{j=1}^n(x_{i,j} - x_{i^{‘},j})^2}

Question 9

Manhattan Distance

Answer 9

d(\boldsymbol{x}i, \boldsymbol{x}{i^{‘}}) = \sum_{j=1}^n \left\lvert x_{i,j} - x_{i^{‘},j} \right\rvert

Question 10

Weighted Voting

Answer 10

In this setup, not all neighbours are treated equally. The weight of the vote is proportional to the similarity with the new instance. Weighted voting allows for preventing ties.

Question 11

Spectrogram

Answer 11

Can represent audio data in the frequency domain. Use for identifying songs from audio samples.

In the case of music identification, the vertical axis correspond to music frequencies. The horizontal axis represents time. The data can be transformed into constellation plots.

Question 12

Constellation Plot

Answer 12

A graph of the frequency peaks for a song in the frequency domain. It only has the spectrogram peaks. Each song is defined by a unique constellation of peaks in the frequency domain, with background noise minimised.

Question 13

Metric for Finding Similar Songs

Answer 13

Number of peaks that the two songs have in common / Number of all distinct Peaks

Question 14

Anchor Points

Answer 14

An anchor point is a peak in the constellation chart that is paired with other peaks that follow in the time axis within a specified range of frequencies.

In the context of song identification, each anchor-peak pair is associated with a time difference between the peak and the anchor pair, and the frequency difference between the peak and the anchor.

Question 15

Song Identification Method

Answer 15

1. Convert the new snippet into a constellation plot.
2. Turn the constellation plot into anchor points with anchor-peak pairs.
3. Identify matching anchor points between the listened song and songs in the database. Determine the longest consecutive sequence of overlap between the two.
4. Return the song with the longest overlap, i.e. the nearest neighbour.

Question 16

kD-tree

Answer 16

An efficient data structure for storing instances in the k-dimensional space, where k is the number of attributes. It partitions the feature space into different regions, similar to Random Forests.

Question 17

Finding Nearest Neighbours in kD-trees

Answer 17

Follow the appropriate path in the tree from the root to the relevant leaf node to find the nearest neighbour for a new instance. It’s not always correct, but is a good approximation.

Question 18

Model

Answer 18

An abstract representation of a real-world process or artefact.

Question 19

Predictive Modelling

Answer 19

Making a model that predicts future data. Examples: classification, regression

Question 20

Descriptive Modelling

Answer 20

Making a model of known data. Examples: clustering, density estimation

Question 21

Prescriptive Modelling

Answer 21

Making a model using data for making optimal decisions. Examples: mathematical programming

Question 22

Parametric Models

Answer 22

Assumes a functional form. Uses the training data to estimate a fixed set of parameters for a model summarising the data. The number of parameters is independent of the number of training examples.

Examples: linear regression, logistic regression, neural networks

Question 23

Non-Parametric Models

Answer 23

Data-driven approach. Has very few assumptions about the functional form. Don’t have a bounded set of parameters.

Examples: histograms, nearest neighbours, kernel methods

Question 24

Histograms

Answer 24

Counts the number of points that fall in a certain bin. The bin heights estimate density. Is non-parametric.

Question 25

Kernel Density Estimate

Answer 25

Estimate the density function by taking a local weighted average of measurements around the point x of interest.

\hat{f}(\boldsymbol{x}) = \frac{1}{m} \sum_{i=1}^m K \left( \frac{\boldsymbol{x} - \boldsymbol{x}_i}{h} \right)

The choice of h determines the smoothness of the density function estimate. Large h values lead to oversmoothing, while small values lead to spiky estimates without much smoothing.

In practice, kernel models work only for low-dimensional data due to being memory-based. It’s also similar to nearest neighbour methods.

Note that the choice of the kernel function is more important than the choice of the bandwidth.

Question 26

Regression

Answer 26

Given a set of inputs in format of (x,y), learn y = \hat{f}(x)

Question 27

Connect-the-dots Regression

Answer 27

Compute a piecewise linear function connecting each data point x with two points on the left and right, respectively. The function is spiky and doesn’t generalise well, but is used in visualisations.

Question 28

k-Nearest Neighbours Regression

Answer 28

For each data point x, compute the mean of the data points in N_k(x), i.e. the k nearest neighbours of x. It’s somewhat smooth, but still has discontinuities.

Question 29

k-Nearest Neighbours Linear Regression

Answer 29

For a new data point x, compute a linear regression line through the set N_k(x) of k-nearest neighbours.

Question 30

Locally Weighted Linear Regression

Answer 30

For a new datapoint x, instances close to x are weighted heavily, while data points far away are weighted less heavily. A kernel is used to compute the weights.

Question 31

Support Vector Machines

Answer 31

Categorises data points by using a kernel to construct a linear separator by building maximum margin separators. The linear separators act as a binary classifier. Support vectors are the points closest to the separator.