Mutual information

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Individual (H(X),H(Y)), joint (H(X,Y)), and conditional entropies for a pair of correlated subsystems X,Y with mutual information I(X; Y).

In probability theory and information theory, the mutual information (MI) or (formerly) transinformation of two random variables is a measure of the variables' mutual dependence. Not limited to real-valued random variables like the correlation coefficient, MI is more general and determines how similar the joint distribution p(X,Y) is to the products of factored marginal distribution p(X)p(Y). MI is the expected values of the pointwise mutual information (PMI). The most common unit of measurement of mutual information is the bit.

Definition of mutual information[edit]

Formally, the mutual information of two discrete random variables X and Y can be defined as:

 I(X;Y) = \sum_{y \in Y} \sum_{x \in X} 
                 p(x,y) \log{ \left(\frac{p(x,y)}{p(x)\,p(y)}
                              \right) }, \,\!

where p(x,y) is the joint probability distribution function of X and Y, and p(x) and p(y) are the marginal probability distribution functions of X and Y respectively.

In the case of continuous random variables, the summation is replaced by a definite double integral:

 I(X;Y) = \int_Y \int_X 
                 p(x,y) \log{ \left(\frac{p(x,y)}{p(x)\,p(y)}
                              \right) } \; dx \,dy,

where p(x,y) is now the joint probability density function of X and Y, and p(x) and p(y) are the marginal probability density functions of X and Y respectively.

If the log base 2 is used, the units of mutual information are the bit.

Intuitively, mutual information measures the information that X and Y share: it measures how much knowing one of these variables reduces uncertainty about the other. For example, if X and Y are independent, then knowing X does not give any information about Y and vice versa, so their mutual information is zero. At the other extreme, if X is a deterministic function of Y and Y is a deterministic function of X then all information conveyed by X is shared with Y: knowing X determines the value of Y and vice versa. As a result, in this case the mutual information is the same as the uncertainty contained in Y (or X) alone, namely the entropy of Y (or X). Moreover, this mutual information is the same as the entropy of X and as the entropy of Y. (A very special case of this is when X and Y are the same random variable.)

Mutual information is a measure of the inherent dependence expressed in the joint distribution of X and Y relative to the joint distribution of X and Y under the assumption of independence. Mutual information therefore measures dependence in the following sense: I(X; Y) = 0 if and only if X and Y are independent random variables. This is easy to see in one direction: if X and Y are independent, then p(x,y) = p(x) p(y), and therefore:

 \log{ \left( \frac{p(x,y)}{p(x)\,p(y)} \right) } = \log 1 = 0. \,\!

Moreover, mutual information is nonnegative (i.e. I(X;Y) ≥ 0; see below) and symmetric (i.e. I(X;Y) = I(Y;X)).

Relation to other quantities[edit]

Mutual information can be equivalently expressed as


\begin{align}
I(X;Y) & {} = H(X) - H(X|Y) \\ 
& {} = H(Y) - H(Y|X) \\ 
& {} = H(X) + H(Y) - H(X,Y) \\
& {} = H(X,Y) - H(X|Y) - H(Y|X)
\end{align}

where \ H(X) and \ H(Y) are the marginal entropies, H(X|Y) and H(Y|X) are the conditional entropies, and H(X,Y) is the joint entropy of X and Y. Note the analogy to the union, difference, and intersection of two sets, as illustrated in the Venn diagram.

Using Jensen's inequality on the definition of mutual information we can show that I(X;Y) is non-negative, consequently, \ H(X) \ge H(X|Y). Here we give the detailed deduction of I(X;Y) = H(Y) - H(Y|X):


\begin{align}
I(X;Y) & {} = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)}\\ 
& {} = \sum_{x,y} p(x,y) \log \frac{p(x,y)}{p(x)} - \sum_{x,y} p(x,y) \log p(y)  \\ 

& {} = \sum_{x,y} p(x)p(y|x) \log p(y|x) - \sum_{x,y} p(x,y) \log p(y) \\
& {} = \sum_x p(x) \left(\sum_y p(y|x) \log p(y|x)\right) - \sum_y \log p(y) \left(\sum_x p(x,y)\right) \\

& {} = -\sum_x p(x) H(Y|X=x) - \sum_y \log p(y) p(y) \\
& {} = -H(Y|X) + H(Y)  \\
& {} = H(Y) - H(Y|X).  \\
\end{align}

The proofs of the other identities above are similar.

Intuitively, if entropy H(Y) is regarded as a measure of uncertainty about a random variable, then H(Y|X) is a measure of what X does not say about Y. This is "the amount of uncertainty remaining about Y after X is known", and thus the right side of the first of these equalities can be read as "the amount of uncertainty in Y, minus the amount of uncertainty in Y which remains after X is known", which is equivalent to "the amount of uncertainty in Y which is removed by knowing X". This corroborates the intuitive meaning of mutual information as the amount of information (that is, reduction in uncertainty) that knowing either variable provides about the other.

Note that in the discrete case H(X|X) = 0 and therefore H(X) = I(X;X). Thus I(X;X) ≥ I(X;Y), and one can formulate the basic principle that a variable contains at least as much information about itself as any other variable can provide.

Mutual information can also be expressed as a Kullback–Leibler divergence, of the product p(x) × p(y) of the marginal distributions of the two random variables X and Y, from p(x,y) the random variables' joint distribution:

 I(X;Y) = D_{\mathrm{KL}}(p(x,y)\|p(x)p(y)).

Furthermore, let p(x|y) = p(x, y) / p(y). Then


\begin{align}
I(X;Y) & {} = \sum_y p(y) \sum_x p(x|y) \log_2 \frac{p(x|y)}{p(x)} \\
& {} =  \sum_y p(y) \; D_{\mathrm{KL}}(p(x|y)\|p(x)) \\
& {} = \mathbb{E}_Y\{D_{\mathrm{KL}}(p(x|y)\|p(x))\}.
\end{align}

Note that here, the Kullback-Leibler divergence involves integration with respect to the random variable X only, and the expression D_{\mathrm{KL}}(p(x|y)\|p(x)) is now a random variable in Y. Thus mutual information can also be understood as the expectation of the Kullback–Leibler divergence of the univariate distribution p(x) of X from the conditional distribution p(x|y) of X given Y: the more different the distributions p(x|y) and p(x) are on average, the greater the information gain.

Variations of mutual information[edit]

Several variations on mutual information have been proposed to suit various needs. Among these are normalized variants and generalizations to more than two variables.

Metric[edit]

Many applications require a metric, that is, a distance measure between pairs of points. The quantity

d(X,Y) = H(X,Y) - I(X;Y) = H(X) + H(Y) - 2I(X;Y) = H(X|Y) + H(Y|X)

satisfies the properties of a metric (triangle inequality, non-negativity, indiscernability and symmetry). This distance metric is also known as the Variation of information.

If X, Y are discrete random variables then all the entropy terms are non-negative, so 0 \le d(X,Y) \le H(X,Y) and one can define a normalized distance

D(X,Y) = d(X,Y)/H(X,Y) \le 1.

The metric D is a universal metric, in that if any other distance measure places X and Y close-by, then the D will also judge them close.[1][dubious ]

A set-theoretic interpretation of information (see the figure for Conditional entropy) shows that

D(X,Y) = 1 - I(X;Y)/H(X,Y)

which is effectively the Jaccard distance between X and Y.

Finally,

D^\prime(X,Y)=1-\frac{I(X;Y)}{\max(H(X),H(Y))}

is also a metric.

Conditional mutual information[edit]

Sometimes it is useful to express the mutual information of two random variables conditioned on a third.

I(X;Y|Z) = \mathbb E_Z \big(I(X;Y)|Z\big)
    = \sum_{z\in Z} \sum_{y\in Y} \sum_{x\in X}
      p_Z(z) p_{X,Y|Z}(x,y|z) \log \frac{p_{X,Y|Z}(x,y|z)}{p_{X|Z}(x|z)p_{Y|Z}(y|z)},

which can be simplified as

I(X;Y|Z) = \sum_{z\in Z} \sum_{y\in Y} \sum_{x\in X}
      p_{X,Y,Z}(x,y,z) \log \frac{p_Z(z)p_{X,Y,Z}(x,y,z)}{p_{X,Z}(x,z)p_{Y,Z}(y,z)}.

Conditioning on a third random variable may either increase or decrease the mutual information, but it is always true that

I(X;Y|Z) \ge 0

for discrete, jointly distributed random variables X, Y, Z. This result has been used as a basic building block for proving other inequalities in information theory.

Multivariate mutual information[edit]

Several generalizations of mutual information to more than two random variables have been proposed, such as total correlation and interaction information. If Shannon entropy is viewed as a signed measure in the context of information diagrams, as explained in the article Information theory and measure theory, then the only definition of multivariate mutual information that makes sense[citation needed] is as follows:

I(X_1;X_1) = H(X_1)

and for n > 1,

I(X_1;\,...\,;X_n) = I(X_1;\,...\,;X_{n-1}) - I(X_1;\,...\,;X_{n-1}|X_n),

where (as above) we define

I(X_1;\,...\,;X_{n-1}|X_n) = \mathbb E_{X_n} \big(I(X_1;\,...\,;X_{n-1})|X_n\big).

(This definition of multivariate mutual information is identical to that of interaction information except for a change in sign when the number of random variables is odd.)

If  A and  B are two sets of variables, then the mutual information between them is:

I(A,B) = H(A\cup B)+H(A\cap B) - H(A) - H(B),

Applications[edit]

Applying information diagrams blindly to derive the above definition[citation needed] has been criticised, and indeed it has found rather limited practical application, since it is difficult to visualize or grasp the significance of this quantity for a large number of random variables. It can be zero, positive, or negative for any n \ge 3.

One high-dimensional generalization scheme which maximizes the mutual information between the joint distribution and other target variables is found to be useful in feature selection.[2]

Mutual information is also used in the area of signal processing as a measure of similarity between two signals. For example, FMI metric[3] is an image fusion performance measure that makes use of mutual information in order to measure the amount of information that the fused image contains about the source images. The Matlab code for this metric can be found at.[4]

Normalized variants[edit]

Normalized variants of the mutual information are provided by the coefficients of constraint,[5] uncertainty coefficient [6] or proficiency:[7]


C_{XY}=\frac{I(X;Y)}{H(Y)} ~~~~\mbox{and}~~~~ C_{YX}=\frac{I(X;Y)}{H(X)}.

The two coefficients are not necessarily equal. In some cases a symmetric measure may be desired, such as the following redundancy[citation needed] measure:

R= \frac{I(X;Y)}{H(X)+H(Y)}

which attains a minimum of zero when the variables are independent and a maximum value of

R_{\max }=\frac{\min (H(X),H(Y))}{H(X)+H(Y)}

when one variable becomes completely redundant with the knowledge of the other. See also Redundancy (information theory). Another symmetrical measure is the symmetric uncertainty (Witten & Frank 2005), given by

U(X,Y) = 2R = 2\frac{I(X;Y)}{H(X)+H(Y)}

which represents a weighted average of the two uncertainty coefficients.[6]

If we consider mutual information as a special case of the total correlation or dual total correlation, the normalized version are respectively,

\frac{I(X;Y)}{\min\left[ H(X),H(Y)\right]} and \frac{I(X;Y)}{H(X,Y)} \; .

Finally there's a normalization [8] which derives from first thinking of mutual information as an analogue to covariance (thus Shannon entropy is analogous to variance). Then the normalized mutual information is calculated akin to the Pearson correlation coefficient,


\frac{I(X;Y)}{\sqrt{H(X)H(Y)}}\; .

Weighted variants[edit]

In the traditional formulation of the mutual information,

 I(X;Y) = \sum_{y \in Y} \sum_{x \in X} p(x,y) \log \frac{p(x,y)}{p(x)\,p(y)},

each event or object specified by (x,y) is weighted by the corresponding probability p(x,y). This assumes that all objects or events are equivalent apart from their probability of occurrence. However, in some applications it may be the case that certain objects or events are more significant than others, or that certain patterns of association are more semantically important than others.

For example, the deterministic mapping \{(1,1),(2,2),(3,3)\} may be viewed as stronger than the deterministic mapping \{(1,3),(2,1),(3,2)\}, although these relationships would yield the same mutual information. This is because the mutual information is not sensitive at all to any inherent ordering in the variable values (Cronbach 1954, Coombs & Dawes 1970, Lockhead 1970), and is therefore not sensitive at all to the form of the relational mapping between the associated variables. If it is desired that the former relation — showing agreement on all variable values — be judged stronger than the later relation, then it is possible to use the following weighted mutual information (Guiasu 1977)

 I(X;Y) = \sum_{y \in Y} \sum_{x \in X} w(x,y) p(x,y) \log \frac{p(x,y)}{p(x)\,p(y)},

which places a weight w(x,y) on the probability of each variable value co-occurrence, p(x,y). This allows that certain probabilities may carry more or less significance than others, thereby allowing the quantification of relevant holistic or prägnanz factors. In the above example, using larger relative weights for w(1,1), w(2,2), and w(3,3) would have the effect of assessing greater informativeness for the relation \{(1,1),(2,2),(3,3)\} than for the relation \{(1,3),(2,1),(3,2)\}, which may be desirable in some cases of pattern recognition, and the like. This weighted mutual information is a form of weighted KL-Divergence, which is known to take negative values for some inputs,[9] and there are examples where the weighted mutual information also takes negative values.[10]

Adjusted mutual information[edit]

A probability distribution can be viewed as a partition of a set. One may then ask: if a set were partitioned randomly, what would the distribution of probabilities be? What would the expectation value of the mutual information be? The adjusted mutual information or AMI subtracts the expectation value of the MI, so that the AMI is zero when two different distributions are random, and one when two distributions are identical. The AMI is defined in analogy to the adjusted Rand index of two different partitions of a set.

Absolute mutual information[edit]

Using the ideas of Kolmogorov complexity, one can consider the mutual information of two sequences independent of any probability distribution:


I_K(X;Y) = K(X) - K(X|Y).

To establish that this quantity is symmetric up to a logarithmic factor (I_K(X;Y) \approx I_K(Y;X)) requires the chain rule for Kolmogorov complexity (Li 1997). Approximations of this quantity via compression can be used to define a distance measure to perform a hierarchical clustering of sequences without having any domain knowledge of the sequences (Cilibrasi 2005).

Mutual information for discrete data[edit]

When X and Y are limited to be in a discrete number of states, observation data is summarized in a contingency table, with row variable X (or i) and column variable Y (or j). Mutual information is one of the measures of association or correlation between the row and column variables. Other measures of association include Pearson's chi-squared test statistics, G-test statistics, etc. In fact, mutual information is equal to G-test statistics divided by 2N where N is the sample size.

In the special case where the number of states for both row and column variables is 2 (i,j=1,2), the degrees of freedom of the Pearson's chi-squared test is 1. Out of the four terms in the summation:

 \sum_{i,j } p_{ij} \log \frac{p_{ij}}{p_i p_j }

only one is independent. It is the reason that mutual information function has an exact relationship with the correlation function  p_{X=1, Y=1}-p_{X=1}p_{Y=1} for binary sequences .[11]

Applications of mutual information[edit]

In many applications, one wants to maximize mutual information (thus increasing dependencies), which is often equivalent to minimizing conditional entropy. Examples include:

  • The mutual information is used to learn the structure of Bayesian networks/dynamic Bayesian networks, which explain the causal relationship between random variables, as exemplified by the GlobalMIT toolkit [2]: learning the globally optimal dynamic Bayesian network with the Mutual Information Test criterion.
  • Popular cost function in Decision tree learning.

See also[edit]

Notes[edit]

  1. ^ Alexander Kraskov, Harald Stögbauer, Ralph G. Andrzejak, and Peter Grassberger, "Hierarchical Clustering Based on Mutual Information", (2003) ArXiv q-bio/0311039
  2. ^ Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze (2008). An Introduction to Information Retrieval. Cambridge University Press. ISBN 0-521-86571-9. 
  3. ^ Haghighat, M. B. A., Aghagolzadeh, A., & Seyedarabi, H. (2011). A non-reference image fusion metric based on mutual information of image features. Computers & Electrical Engineering, 37(5), 744-756.
  4. ^ http://www.mathworks.com/matlabcentral/fileexchange/45926-feature-mutual-information-fmi-image-fusion-metric
  5. ^ Coombs, C. H., Dawes, R. M. & Tversky, A. (1970). Mathematical Psychology: An Elementary Introduction. Englewood Cliffs, New Jersey: Prentice-Hall. 
  6. ^ a b Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 14.7.3. Conditional Entropy and Mutual Information". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8 
  7. ^ White, Jim; Steingold, Sam; Fournelle, Connie. "Performance Metrics for Group-Detection Algorithms". Interface 2004. 
  8. ^ Strehl, Alexander; Ghosh, Joydeep (2002), "Cluster Ensembles - A Knowledge Reuse Framework for Combining Multiple Partitions", The Journal of Machine Learning Research 3 (Dec): 583–612 
  9. ^ Kvålseth, T. O. (1991). The relative useful information measure: some comments. Information sciences, 56(1), 35-38.
  10. ^ Pocock, A. (2012). Feature Selection Via Joint Likelihood (Thesis). 
  11. ^ Wentian Li (1990). "Mutual information functions versus correlation functions". J. Stat. Phys. 60 (5-6): 823–837. doi:10.1007/BF01025996. 
  12. ^ [1] Parsing a Natural Language Using Mutual Information Statistics by David M. Magerman and Mitchell P. Marcus
  13. ^ Hugh Everett Theory of the Universal Wavefunction, Thesis, Princeton University, (1956, 1973), pp 1–140 (page 30)
  14. ^ Hugh Everett, Relative State Formulation of Quantum Mechanics, Reviews of Modern Physics vol 29, (1957) pp 454–462.

References[edit]