Similarity Based Learning

To classify something, find things that are similar and label it with the same class as the most similar thing.

The feature space is \(N-d\), where \(N\) is the number of features. Each instance is mapped to a point. The descriptive features become the axes.

The Similarity Metric

Mathematically, it must conform to these 4 criteria:

• Non-negativity: \(f(a, b) \ge 0\)
• Identity of Indiscernables: \( f(a, b) = 0 \iff a = b \)
• Symmetry: \( f(a, b) = f(b, a) \)
• Subaddivity (Triangular inequality): \( f(a, b) \le f(a, c) + f(c, b) \)

The Algorithm

1. Iterate across the instances in memory. Find the instance that has the shortest distance from the query.

2. Make a prediction for the query equal to the value of the target feature of the nearest neighbor

Remarks on the Algorithm

Updating the model is quite cheap. Adding an instance updates the Voronoi tessellation and therefore the decision boundary.

Similarity-based learning is intuitive and gives people confidence in the model.

There is an inductive bias that instances that have similar descriptive features belong to the same class.

Similarity learning has a stationary assumption, i.e. the joint PDF of the data doesn’t change (new classifications do not come up). This assumption is shared by supervised ML.

Furthermore, an NN model can only give answers that are present in the training set. Ergo, is your training set representative?

Majority Voting

The \(k\) nearest neighbors model predicts the target level from the majority vote from the set of the \(k\) nearest neighbors to the query \(q\).

Where \(\delta\) is an indicator function such that \(\delta(t_i, l) = 1 \iff t_i = l\):

$$ \mathbb{M}_{k} (q) = argmax_{l \in levels(t)} \left( \sum_{i=1}^{k} \delta(t_i, l) \right) $$

For categorical features, \(k\) should be odd to avoid ties.

When you have features taking different range if values, you may have odd predictions.

To mitigate this, normalize the feature’s ranges to \([r_{low}, r_{high}]\):

$$ a’_i = \frac{a_i - a_{min}}{ a_{max} - a_{min}} \cdot (r_{high} - r_{low}) + r_{low} $$

Return the Average Value

One possible solution is to return the average value in the neighborhood, i.e.

$$ \mathbb{M}_{k}(q) = \frac{1}{k} \sum_{i=1}^{k} t_i $$

We can improve this by using weighted \(k-NN\):

$$ \mathbb{M}_{k}(q) = \frac{ \sum_{i=1}^{k} \left( \frac{1}{dist(q, d_i)^2} \cdot t_i \right) }{ \sum_{i=1}^{k} \frac{1}{dist(q, d_i)^2} } $$

This list is not exhaustive. For example, lists multiple distance and similarity measures for different kinds of data: numerical (12), boolean (8), string (5), images & color (2), geospatial & temporal (4), and general & mixed (1).

The Curse of Dimensionality

The predictive power of an induced model is based either on:

• Partitioning the feature space into regions based on clusters of training instances and assigning a query located in region \(X\) the target value of the training instances in that cluster.

• Interpolating a target value from the target values of individual training instances that are near the query in the feature space.

Therefore, the sampling density (the average density of training instances across the feature space) is an important factor.