Mutual information
Information theory 

In probability theory and information theory, the mutual information (MI) of two random variables is a measure of the mutual dependence between the two variables. More specifically, it quantifies the "amount of information" (in units such as shannons, commonly called bits) obtained about one random variable through observing the other random variable. The concept of mutual information is intricately linked to that of entropy of a random variable, a fundamental notion in information theory that quantifies the expected "amount of information" held in a random variable.
Not limited to realvalued random variables like the correlation coefficient, MI is more general and determines how similar the joint distribution is to the products of factored marginal distribution . MI is the expected value of the pointwise mutual information (PMI).
Contents
Definition[edit]
Formally, the mutual information of two discrete random variables and can be defined as:^{[1]}^{:20}

where is the joint probability function of and , and and are the marginal probability distribution functions of and respectively.
In the case of continuous random variables, the summation is replaced by a definite double integral:^{[1]}^{:251}

where is now the joint probability density function of and , and and are the marginal probability density functions of and respectively.
If the log base 2 is used, the units of mutual information are bits.
Motivation[edit]
Intuitively, mutual information measures the information that and share: It measures how much knowing one of these variables reduces uncertainty about the other. For example, if and are independent, then knowing does not give any information about and vice versa, so their mutual information is zero. At the other extreme, if is a deterministic function of and is a deterministic function of then all information conveyed by is shared with : knowing determines the value of and vice versa. As a result, in this case the mutual information is the same as the uncertainty contained in (or ) alone, namely the entropy of (or ). Moreover, this mutual information is the same as the entropy of and as the entropy of . (A very special case of this is when and are the same random variable.)
Mutual information is a measure of the inherent dependence expressed in the joint distribution of and relative to the joint distribution of and under the assumption of independence. Mutual information therefore measures dependence in the following sense: if and only if and are independent random variables. This is easy to see in one direction: if and are independent, then , and therefore:
Moreover, mutual information is nonnegative (i.e. see below) and symmetric (i.e. see below).
Relation to other quantities[edit]
Nonnegativity[edit]
Using Jensen's inequality on the definition of mutual information we can show that is nonnegative, i.e.^{[1]}^{:28}
Symmetry[edit]
Relation to conditional and joint entropy[edit]
Mutual information can be equivalently expressed as
where and are the marginal entropies, and are the conditional entropies, and is the joint entropy of and . Note the analogy to the union, difference, and intersection of two sets, as illustrated in the Venn diagram. In terms of a communication channel in which the output is a noisy version of the input , these relations are summarised in the figure below.
Because is nonnegative, consequently, . Here we give the detailed deduction of :
The proofs of the other identities above are similar.
Intuitively, if entropy is regarded as a measure of uncertainty about a random variable, then is a measure of what does not say about . This is "the amount of uncertainty remaining about after is known", and thus the right side of the second of these equalities can be read as "the amount of uncertainty in , minus the amount of uncertainty in which remains after is known", which is equivalent to "the amount of uncertainty in which is removed by knowing ". 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 and therefore . Thus , and one can formulate the basic principle that a variable contains at least as much information about itself as any other variable can provide. This parallels a similar result about.
Relation to Kullback–Leibler divergence[edit]
Mutual information can also be expressed as a Kullback–Leibler divergence of the product of the marginal distributions, , of the two random variables and , from the random variables' joint distribution, :
Furthermore, let . Then
Note that here the Kullback–Leibler divergence involves integration with respect to the random variable only and the expression is now a random variable in . Thus mutual information can also be understood as the expectation of the Kullback–Leibler divergence of the univariate distribution of from the conditional distribution of given : the more different the distributions and are on average, the greater the information gain.
Bayesian estimation of mutual information[edit]
It is wellunderstood how to do Bayesian estimation of the mutual information of a joint distribution based on samples of that distribution. The first work to do this, which also showed how to do Bayesian estimation of many other informationtheoretic besides mutual information, was ^{[2]}. Subsequent researchers have rederived ^{[3]} and extended ^{[4]} this analysis. See ^{[5]} for a recent paper based on a prior specifically tailored to estimation of mutual information per se.
Independence assumptions[edit]
The KullbeckLeibler divergence formulation of the mutual information is predicated on that one is interested in comparing to the fully factorized outer product . In many problems, such as nonnegative matrix factorization, one is interested in less extreme factorizations; specifically, one wishes to compare to a lowrank matrix approximation in some unknown variable ; that is, to what degree one might have
Alternately, one might be interested in knowing how much more information carries over its factorization. In such a case, the excess information that the full distribution carries over the matrix factorization is given by the KullbeckLeibler divergence
The conventional definition of the mutual information is recovered in the extreme case that the process has only one value for .
Variations[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
satisfies the properties of a metric (triangle inequality, nonnegativity, indiscernability and symmetry). This distance metric is also known as the variation of information.
If are discrete random variables then all the entropy terms are nonnegative, so and one can define a normalized distance
The metric is a universal metric, in that if any other distance measure places and closeby, then the will also judge them close.^{[6]}^{[dubious – discuss]}
Plugging in the definitions shows that
In a settheoretic interpretation of information (see the figure for Conditional entropy), this is effectively the Jaccard distance between and .
Finally,
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.
which can be simplified as
Conditioning on a third random variable may either increase or decrease the mutual information, but it is always true that
for discrete, jointly distributed random variables . 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:
and for
where (as above) we define
(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.)
Applications[edit]
Applying information diagrams blindly to derive the above definition^{[citation needed]} has been criticised^{[who?]}, 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 odd number of variables
One highdimensional generalization scheme which maximizes the mutual information between the joint distribution and other target variables is found to be useful in feature selection.^{[7]}
Mutual information is also used in the area of signal processing as a measure of similarity between two signals. For example, FMI metric^{[8]} 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.^{[9]}
Directed information[edit]
Directed information, , measures the amount of information that flows from the process to , where denotes the vector and denotes . The term directed information was coined by James Massey and is defined as
 .
Note that if , the directed information becomes the mutual information. Directed information has many applications in problems where causality plays an important role, such as capacity of channel with feedback.^{[10]}^{[11]}
Normalized variants[edit]
Normalized variants of the mutual information are provided by the coefficients of constraint,^{[12]} uncertainty coefficient^{[13]} or proficiency:^{[14]}
The two coefficients are not necessarily equal. In some cases a symmetric measure may be desired, such as the following redundancy^{[citation needed]} measure:
which attains a minimum of zero when the variables are independent and a maximum value of
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
which represents the harmonic mean of the two uncertainty coefficients .^{[13]}
If we consider mutual information as a special case of the total correlation or dual total correlation, the normalized version are respectively,
 and
This normalized version also known as Information Quality Ratio (IQR) which quantifies the amount of information of a variable based on another variable against total uncertainty:^{[15]}
There's a normalization^{[16]} 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,
Weighted variants[edit]
In the traditional formulation of the mutual information,
each event or object specified by is weighted by the corresponding probability . 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 may be viewed as stronger than the deterministic mapping , 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 & Tversky 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).
which places a weight on the probability of each variable value cooccurrence, . 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 , , and would have the effect of assessing greater informativeness for the relation than for the relation , which may be desirable in some cases of pattern recognition, and the like. This weighted mutual information is a form of weighted KLDivergence, which is known to take negative values for some inputs,^{[17]} and there are examples where the weighted mutual information also takes negative values.^{[18]}
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:
To establish that this quantity is symmetric up to a logarithmic factor () requires the chain rule for Kolmogorov complexity (Li & Vitányi 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 & Vitányi 2005).
Linear correlation[edit]
Unlike correlation coefficients, such as the product moment correlation coefficient, mutual information contains information about all dependence—linear and nonlinear—and not just linear dependence as the correlation coefficient measures. However, in the narrow case that the joint distribution for and is a bivariate normal distribution (implying in particular that both marginal distributions are normally distributed), there is an exact relationship between and the correlation coefficient (Gel'fand & Yaglom 1957).
The equation above can be derived as follows for a bivariate Gaussian:
Therefore,
For discrete data[edit]
When and are limited to be in a discrete number of states, observation data is summarized in a contingency table, with row variable (or ) and column variable (or ). Mutual information is one of the measures of association or correlation between the row and column variables. Other measures of association include Pearson's chisquared test statistics, Gtest statistics, etc. In fact, mutual information is equal to Gtest statistics divided by , where is the sample size.
Applications[edit]
In many applications, one wants to maximize mutual information (thus increasing dependencies), which is often equivalent to minimizing conditional entropy. Examples include:
 In search engine technology, mutual information between phrases and contexts is used as a feature for kmeans clustering to discover semantic clusters (concepts).^{[19]}
 In telecommunications, the channel capacity is equal to the mutual information, maximized over all input distributions.
 Discriminative training procedures for hidden Markov models have been proposed based on the maximum mutual information (MMI) criterion.
 RNA secondary structure prediction from a multiple sequence alignment.
 Phylogenetic profiling prediction from pairwise present and disappearance of functionally link genes.
 Mutual information has been used as a criterion for feature selection and feature transformations in machine learning. It can be used to characterize both the relevance and redundancy of variables, such as the minimum redundancy feature selection.
 Mutual information is used in determining the similarity of two different clusterings of a dataset. As such, it provides some advantages over the traditional Rand index.
 Mutual information of words is often used as a significance function for the computation of collocations in corpus linguistics. This has the added complexity that no wordinstance is an instance to two different words; rather, one counts instances where 2 words occur adjacent or in close proximity; this slightly complicates the calculation, since the expected probability of one word occurring within words of another, goes up with .
 Mutual information is used in medical imaging for image registration. Given a reference image (for example, a brain scan), and a second image which needs to be put into the same coordinate system as the reference image, this image is deformed until the mutual information between it and the reference image is maximized.
 Detection of phase synchronization in time series analysis
 In the infomax method for neuralnet and other machine learning, including the infomaxbased Independent component analysis algorithm
 Average mutual information in delay embedding theorem is used for determining the embedding delay parameter.
 Mutual information between genes in expression microarray data is used by the ARACNE algorithm for reconstruction of gene networks.
 In statistical mechanics, Loschmidt's paradox may be expressed in terms of mutual information.^{[20]}^{[21]} Loschmidt noted that it must be impossible to determine a physical law which lacks time reversal symmetry (e.g. the second law of thermodynamics) only from physical laws which have this symmetry. He pointed out that the Htheorem of Boltzmann made the assumption that the velocities of particles in a gas were permanently uncorrelated, which removed the time symmetry inherent in the Htheorem. It can be shown that if a system is described by a probability density in phase space, then Liouville's theorem implies that the joint information (negative of the joint entropy) of the distribution remains constant in time. The joint information is equal to the mutual information plus the sum of all the marginal information (negative of the marginal entropies) for each particle coordinate. Boltzmann's assumption amounts to ignoring the mutual information in the calculation of entropy, which yields the thermodynamic entropy (divided by Boltzmann's constant).
 The mutual information is used to learn the structure of Bayesian networks/dynamic Bayesian networks, which is thought to explain the causal relationship between random variables, as exemplified by the GlobalMIT toolkit:^{[22]} learning the globally optimal dynamic Bayesian network with the Mutual Information Test criterion.
 Popular cost function in decision tree learning.
 The mutual information is used in Cosmology to test the influence of largescale environments on galaxy properties in the Galaxy Zoo.
 The mutual information was used in Solar Physics to derive the solar differential rotation profile, a traveltime deviation map for sunspots, and a time–distance diagram from quietSun measurements^{[23]}
See also[edit]
Notes[edit]
 ^ ^{a} ^{b} ^{c} Cover, T.M.; Thomas, J.A. (1991). Elements of Information Theory (Wiley ed.). ISBN 9780471241959.
 ^ Wolpert, D.H.; Wolf, D.R. (1995). "Estimating functions of probability distributions from a finite set of samples". Physical Review E.
 ^ Hutter, M. (2001). "Distribution of Mutual Information". Advances in Neural Information Processing Systems 2001.
 ^ Archer, E.; Park, I.M.; Pillow, J. (2013). "Bayesian and QuasiBayesian Estimators for Mutual Information from Discrete Data". Entropy.
 ^ Wolpert, D.H; DeDeo, S. (2013). "Estimating Functions of Distributions Defined over Spaces of Unknown Size". Entropy.
 ^ Kraskov, Alexander; Stögbauer, Harald; Andrzejak, Ralph G.; Grassberger, Peter (2003). "Hierarchical Clustering Based on Mutual Information". arXiv:qbio/0311039.
 ^ Christopher D. Manning; Prabhakar Raghavan; Hinrich Schütze (2008). An Introduction to Information Retrieval. Cambridge University Press. ISBN 0521865719.
 ^ Haghighat, M. B. A.; Aghagolzadeh, A.; Seyedarabi, H. (2011). "A nonreference image fusion metric based on mutual information of image features". Computers & Electrical Engineering. 37 (5): 744–756. doi:10.1016/j.compeleceng.2011.07.012.
 ^ "Feature Mutual Information (FMI) metric for nonreference image fusion  File Exchange  MATLAB Central". www.mathworks.com. Retrieved 4 April 2018.
 ^ Massey, James (1990). "Causality, Feedback And Directed Informatio" (ISITA).
 ^ Permuter, Haim Henry; Weissman, Tsachy; Goldsmith, Andrea J. (February 2009). "Finite State Channels With TimeInvariant Deterministic Feedback". IEEE Transactions on Information Theory. 55 (2): 644–662. arXiv:cs/0608070. doi:10.1109/TIT.2008.2009849.
 ^ Coombs, Dawes & Tversky 1970.
 ^ ^{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 9780521880688
 ^ White, Jim; Steingold, Sam; Fournelle, Connie. "Performance Metrics for GroupDetection Algorithms" (PDF).
 ^ Wijaya, Dedy Rahman; Sarno, Riyanarto; Zulaika, Enny. "Information Quality Ratio as a novel metric for mother wavelet selection". Chemometrics and Intelligent Laboratory Systems. 160: 59–71. doi:10.1016/j.chemolab.2016.11.012.
 ^ Strehl, Alexander; Ghosh, Joydeep (2002), "Cluster Ensembles – A Knowledge Reuse Framework for Combining Multiple Partitions" (PDF), The Journal of Machine Learning Research, 3 (Dec): 583–617
 ^ Kvålseth, T. O. (1991). "The relative useful information measure: some comments". Information sciences. 56 (1): 35–38. doi:10.1016/00200255(91)90022m.
 ^ Pocock, A. (2012). Feature Selection Via Joint Likelihood (PDF) (Thesis).
 ^ Parsing a Natural Language Using Mutual Information Statistics by David M. Magerman and Mitchell P. Marcus
 ^ Hugh Everett Theory of the Universal Wavefunction, Thesis, Princeton University, (1956, 1973), pp 1–140 (page 30)
 ^ Everett, Hugh (1957). "Relative State Formulation of Quantum Mechanics". Reviews of Modern Physics. 29: 454–462. Bibcode:1957RvMP...29..454E. doi:10.1103/revmodphys.29.454.
 ^ GlobalMIT at Google Code
 ^ Keys, Dustin; Kholikov, Shukur; Pevtsov, Alexei A. (February 2015). "Application of Mutual Information Methods in Time Distance Helioseismology". Solar Physics. 290 (3): 659–671. arXiv:1501.05597. Bibcode:2015SoPh..290..659K. doi:10.1007/s112070150650y.
References[edit]
 Cilibrasi, R.; Vitányi, Paul (2005). "Clustering by compression" (PDF). IEEE Transactions on Information Theory. 51 (4): 1523–1545. doi:10.1109/TIT.2005.844059.
 Cronbach, L. J. (1954). "On the nonrational application of information measures in psychology". In Quastler, Henry. Information Theory in Psychology: Problems and Methods. Glencoe, Illinois: Free Press. pp. 14–30.
 Coombs, C. H.; Dawes, R. M.; Tversky, A. (1970). Mathematical Psychology: An Elementary Introduction. Englewood Cliffs, New Jersey: PrenticeHall.
 Church, Kenneth Ward; Hanks, Patrick (1989). "Word association norms, mutual information, and lexicography". Proceedings of the 27th Annual Meeting of the Association for Computational Linguistics.
 Gel'fand, I.M.; Yaglom, A.M. (1957). "Calculation of amount of information about a random function contained in another such function". American Mathematical Society Translations: Series 2. 12: 199–246. English translation of original in Uspekhi Matematicheskikh Nauk 12 (1): 352.
 Guiasu, Silviu (1977). Information Theory with Applications. McGrawHill, New York. ISBN 9780070251090.
 Li, Ming; Vitányi, Paul (February 1997). An introduction to Kolmogorov complexity and its applications. New York: SpringerVerlag. ISBN 0387948686.
 Lockhead, G. R. (1970). "Identification and the form of multidimensional discrimination space". Journal of Experimental Psychology. 85 (1): 1–10. doi:10.1037/h0029508. PMID 5458322.
 David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0521642981 (available free online)
 Haghighat, M. B. A.; Aghagolzadeh, A.; Seyedarabi, H. (2011). "A nonreference image fusion metric based on mutual information of image features". Computers & Electrical Engineering. 37 (5): 744–756. doi:10.1016/j.compeleceng.2011.07.012.
 Athanasios Papoulis. Probability, Random Variables, and Stochastic Processes, second edition. New York: McGrawHill, 1984. (See Chapter 15.)
 Witten, Ian H. & Frank, Eibe (2005). Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann, Amsterdam. ISBN 9780123748560.
 Peng, H.C., Long, F., and Ding, C. (2005). "Feature selection based on mutual information: criteria of maxdependency, maxrelevance, and minredundancy". IEEE Transactions on Pattern Analysis and Machine Intelligence. 27 (8): 1226–1238. doi:10.1109/tpami.2005.159. PMID 16119262.CS1 maint: Multiple names: authors list (link)
 Andre S. Ribeiro; Stuart A. Kauffman; Jason LloydPrice; Bjorn Samuelsson & Joshua Socolar (2008). "Mutual Information in Random Boolean models of regulatory networks". Physical Review E. 77 (1). arXiv:0707.3642. Bibcode:2008PhRvE..77a1901R. doi:10.1103/physreve.77.011901.
 Wells, W.M. III; Viola, P.; Atsumi, H.; Nakajima, S.; Kikinis, R. (1996). "Multimodal volume registration by maximization of mutual information" (PDF). Medical Image Analysis. 1 (1): 35–51. doi:10.1016/S13618415(01)800049. PMID 9873920.
 Pandey, Biswajit; Sarkar, Suman (2017). "How much a galaxy knows about its largescale environment?: An information theoretic perspective". Monthly Notices of the Royal Astronomical Society Letters. 467: L6. arXiv:1611.00283. Bibcode:2017MNRAS.467L...6P. doi:10.1093/mnrasl/slw250.