Similarity Function
Introduction
A similarity function refers to a function defined so as to measure how similar two data are. To work properly for such a purpose, it must be defined as a function satisfying a few mathematical conditions. Semantically, the larger the function value $s(x, y)$ is, the more one should be able to interpret the two data as being similar to each other.
Definition
For a set $X$, a map $s : X \times X \to \mathbb{R}$ satisfying the following conditions is called a similarity function.
Maximal self-similarity: $$ s(x, y) \le s(x, x) \quad \forall x, y \in X $$
Symmetry: $$ s(x, y) = s(y, x) \quad \forall x, y \in X $$
Explanation
Among the conditions in the definition, maximal self-similarity can be said to be the core of a similarity function. It is from this property that two objects with a large value can be said to be similar to each other. It is also common to normalize the range of a similarity function into one of the following forms.
$$ s(x, y) \in [0, 1], \qquad s(x, y) \in [-1, 1] $$
Since the KL divergence becomes smaller as two distributions become more similar, it can be called a dissimilarity.
Difference from Distance Functions
Something that serves the function of expressing how close two objects are is the distance function, so let us think about why the notion of similarity is needed at all. Basically, a distance function $d$, true to its name, measures the degree of closeness, so its value becomes smaller as two objects get closer. On the other hand, a similarity $s$ becomes larger as two objects become more similar. A distance measures the degree of separation while a similarity measures the degree of agreement, so the directions of the quantity we want to look at are opposite to each other. That is why, unlike distance functions, similarity functions are often normalized.
$$ 0 = d(x, x) \le d(x, y), \qquad s(x, y) \le s(x, x) $$
Another reason is that the conditions demanded by a distance function are quite strict. The triangle inequality and the identity axiom are strong constraints for being a "real distance", but the inner product or cosine similarity commonly used when dealing with data do not satisfy these conditions. A similarity measures how related two objects are and whether they are aligned in the same direction, rather than how close they are, and since it is also allowed to take negative values, it can be defined far more freely than a distance.
Meanwhile, a distance $d$ and a similarity $s$ are two viewpoints of "closeness" that differ only in direction, so they can be converted into each other through a monotonically decreasing transformation that becomes smaller as the distance $d$ grows. Transformations such as $s = -d$ or $s = e^{-d}$ are examples. However, whether the similarity obtained in this way satisfies the maximal self-similarity or symmetry defined above depends on the transformation.
| Type \ Property | Symmetry | Non-negativity | Triangle Inequality | Identity | Self-value |
|---|---|---|---|---|---|
| Distance | ✅ | ✅ | ✅ | ✅ | $0$ (minimum) |
| Pseudometric | ✅ | ✅ | ✅ | ❌ | $0$ (minimum) |
| Similarity | ✅ | ❌ | ❌ | — | maximum |
| Divergence | ❌ | ✅ | ❌ | ✅ | $0$ (minimum) |
- Symmetry: $f(x, y) = f(y, x)$
- Non-negativity: $f(x, y) \ge 0$
- Triangle inequality: $f(x, z) \le f(x, y) + f(y, z)$
- Identity: $f(x, y) = 0 \implies x = y$
- Self-value: $f(x, x)$
Types
Representative similarity and dissimilarity functions include the following.
Similarity
inner product: The definition of the inner product itself has nothing to do with similarity, but it is suitable for use as a similarity. The value becomes larger as two vectors are aligned in the same direction with greater magnitude. If the magnitude is ignored, it becomes the cosine similarity below.
cosine similarity: This is the cosine of the angle between two vectors, and can be said to be a normalized inner product. It ignores the magnitudes of the vectors and measures only how well their directions are aligned. $$ s(\mathbf{x}, \mathbf{y}) = \frac{\mathbf{x} \cdot \mathbf{y}}{\left\lVert \mathbf{x} \right\rVert \left\lVert \mathbf{y} \right\rVert} $$
Dissimilarity
- Kullback–Leibler divergence: A dissimilarity that measures how different two probability distributions are from each other; its value becomes smaller as the two distributions become more similar.