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.Marina Meila, "Comparing Clusterings by the Variation of Information", Learning Theory and Kernel Machines (2003), vol. 2777, pp. 173–187, , Lecture Notes in Computer Science,

Definition

Suppose we have two partitions $X$ and $Y$ of a set $A$ into disjoint subsets, namely $X = \$ and $Y = \$.

Let:
:$n = \sum_ , X_, = \sum_ , Y_, =, A,$
:$p_ = , X_, / n$ and $q_ = , Y_, / n$
:$r_ = , X_i\cap Y_, / n$

Then the variation of information between the two partitions is:

:\mathrm(X; Y ) = - \sum_ r_ \left log(r_/p_i)+\log(r_/q_j) \right/math>.

This is equivalent to the shared information distance between the random variables ''i'' and ''j'' with respect to the uniform probability measure on $A$ defined by $\mu(B):=, B, /n$ for $B\subseteq A$.

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 where the partial order induces two operations, the meet $\wedge$ and the join $\vee$, where the maximum $\overline$ is the partition with only one block, i.e., all elements grouped together, and the minimum is $\overline$, the partition consisting of all elements as singletons. The meet of two partitions $X$ and $Y$ is easy to understand as that partition formed by all pair intersections of one block of, $X_$, of $X$ and one, $Y_$, of $Y$. It then follows that $X\wedge Y\subseteq X$ and $X\wedge Y\subseteq Y$.

Let's define the entropy of a partition $X$ as

:$H\left( X\right)\,=\,-\sum_i\,p_\log p_$,

where $p_=, X_i, /n$. Clearly, $H(\overline)=0$ and $H(\overline)=\log\,n$. The entropy of a partition is a monotonous function on the lattice of partitions in the sense that $X\subseteq Y\Rightarrow H(X) \geq H(Y)$.

Then the VI distance between $X$ and $Y$ is given by

:$\mathrm(X,Y)\,=\,2 H( X\wedge Y )\,-\,H(X)\,-\,H(Y)$.

The difference $d(X,Y)\equiv , H\left(X\right)-H\left(Y\right),$ is a pseudo-metric as $d(X,Y)=0$ doesn't necessarily imply that $X=Y$. From the definition of $\overline$, it is $\mathrm(X,\mathrm)\,=\,H\left(X\right)$.

If in the Hasse diagram we draw an edge from every partition to the maximum $\overline$ and assign it a weight equal to the VI distance between the given partition and $\overline$, we can interpret the VI distance as basically an average of differences of edge weights to the maximum

:$\mathrm(X,Y)\,=\,, \mathrm(X,\overline)\,-\,\mathrm(X\wedge Y,\overline), \,+\,, \mathrm(Y,\overline)\,-\,\mathrm(X\wedge Y,\overline), \,=\,d(X,X\wedge Y)\,+\,d(Y,X\wedge Y)$.

For $H(X)$ as defined above, it holds that the joint information of two partitions coincides with the entropy of the meet

:$H(X,Y)\,=\,H(X\wedge Y)$

and we also have that $d(X,X\wedge Y)\,=\,H(X\wedge Y, X)$ coincides with the conditional entropy of the meet (intersection) $X\wedge Y$ relative to $X$.

Identities

The variation of information satisfies

:$\mathrm(X; Y ) = H(X) + H(Y) - 2I(X, Y)$,

where $H(X)$ is the entropy of $X$, and $I(X, Y)$ is mutual information between $X$ and $Y$ with respect to the uniform probability measure on $A$. This can be rewritten as

:$\mathrm(X; Y ) = H(X,Y) - I(X, Y)$,

where $H(X,Y)$ is the joint entropy of $X$ and $Y$, or

:$\mathrm(X; Y ) = H(X, Y) + H(Y, X)$,

where $H(X, Y)$ and $H(Y, X)$ are the respective conditional entropies.

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

:$\mathrm(X; Y)\leq \log(n)$,

Or with respect to a maximum number of clusters, $K^*$:

:$\mathrm(X ; Y) \leq 2 \log(K^*)$

References

Further reading

*
*
*
*
*

External links

Partanalyzer
includes a C++ implementation of VI and other metrics and indices for analyzing partitions and clusterings

C++ implementation with MATLAB mex files

{{DEFAULTSORT:Variation Of Information
Entropy and information
Summary statistics for contingency tables
Clustering criteria