Understanding Artificial Intelligence
through Algorithmic Information Theory
NID:
A "universal" distance
aiai.telecom-paris.fr
In 1998, Charles Bennett and his colleagues introduced
the Normalized Information Distance (NID).NID is a universal distance.
For any pair of objects, NID determines what is common to them, and only keeps their difference to measure the distance that separates them.
By doing so, NID can be regarded as "the most intelligent" distance!
NID is based on conditional complexity K(x|y). Conditional complexity measures the amount of information contained in x that is not already present in y.
We’ll proceed from K(x|y) to NID(x,y) in three steps.
K(x|y)Step 1: symmetry.Let’s make conditional complexity symmetrical, by considering max[K(x|y), K(y|x)] instead of K(x|y). This will measure the amount of information that is not shared between x and y.
max[K(x|y), K(y|x)]Step 2: normalization.Suppose that two objects differ by n bits of information. If n is significant compared to their complexity, then they are very different.
However, if the objects are complex and now the same n bits represent a small amount compared to their complexity, then the two objects are very similar.
max[K(x|y), K(y|x)]Step 2: normalization.To take this relative effect into account, let’s divide the similarity measure by the objects’ complexity.
$$ \frac{max[K(x|y), K(y|x)]}{max[K(x), K(y)]} $$
\(\frac{max[K(x|y), K(y|x)]}{max[K(x), K(y)]}\)Step 3: chain rule.The Chain Rule for K says that (up to an additional constant, neglected here):
K(x, y) < K(x|y) + K(y).
If we replace K(x|y) by K(x, y) – K(y) in the above expression, we get what Bennett and his colleagues defined as Normalized Information Distance, or NID.
$$ NID(x, y) = \frac{K(x, y) - min[K(x), K(y)]}{max[K(x), K(y)]} $$
\(NID(x, y) = \frac{K(x, y) - min[K(x), K(y)]}{max[K(x), K(y)]}\)This distance has values between 0 and 1. Unlike usual distances that rely on predetermined computations, NID discovers for each pair {x,y} what x and y have in common.
For this reason, NID may be considered as the "most itelligent" distance one may think of.
This means that if two objects x and y are close to each other according to any given computable distance, then x and y will be found close to each other by NID.
See (Li, Chen & Li, 2004) for details.