↑ arvau

Wikipedia / Variation of information

In probability theory and information theory, the variation of information or shared information distance is a measure of the distance between two clusterings (partitions of elements). It is closely related to mutual information; indeed, it is a simple linear expression involving the mutual information. Unlike the mutual information, however, the variation of information is a true metric, in that it obeys the triangle inequality.

Definition

Suppose we have two partitions of a set.

Let:

Then the variation of information between the two partitions is:

  1. .

This is equivalent to the shared information distance between the random variables i and j.

Explicit information content

We can rewrite this definition in terms that explicitly highlight the information content of this metric.

The set of all partitions of a set form a compact lattice.

as

  1. ,

.

is given by

  1. .

.

If in the Hasse diagram, we can interpret the VI distance as basically an average of differences of edge weights to the maximum

  1. .

as defined above, it holds that the joint information of two partitions coincides with the entropy of the meet

.

Identities

The variation of information satisfies

  1. ,

is the entropy is mutual information. This can be rewritten as

  1. ,

is the joint entropy, or

  1. ,

are the respective conditional entropies.

The variation of information can also be bounded, either in terms of the number of elements:

  1. ,

:

Triangle inequality

which is no less than the left side.

References

Further reading