Mutual information 427282 225348602 2008-07-13T05:53:21Z SmackBot 433328 Date the maintenance tags or general fixes In [[probability theory]] and [[information theory]], the '''mutual information''', or '''transinformation''', of two [[random variable]]s is a quantity that measures the mutual dependence of the two variables. The most common [[unit of measurement]] of mutual information is the [[bit]], when logarithms to the base 2 are used. == Definition of mutual information == Formally, the mutual information of two discrete random variables ''X'' and ''Y'' can be defined as: :<math> I(X;Y) = \sum_{y \in Y} \sum_{x \in X} p(x,y) \log{ \left( \frac{p(x,y)}{p_1(x)\,p_2(y)} \right) }, \,\! </math> where ''p''(''x'',''y'') is the [[joint distribution|joint probability distribution function]] of ''X'' and ''Y'', and <math>p_1(x)</math> and <math>p_2(y)</math> are the [[marginal probability]] distribution functions of ''X'' and ''Y'' respectively. In the [[continuum|continuous]] case, we replace summation by a definite [[double integral]]: :<math> I(X;Y) = \int_Y \int_X p(x,y) \log{ \left( \frac{p(x,y)}{p_1(x)\,p_2(y)} \right) } \; dx \,dy, </math> where ''p''(''x'',''y'') is now the joint probability ''density'' function of ''X'' and ''Y'', and <math>p_1(x)</math> and <math>p_2(y)</math> are the marginal probability density functions of ''X'' and ''Y'' respectively. These definitions are ambiguous because the base of the log function is not specified. To disambiguate, the function ''I'' could be parameterized as ''I''(''X'',''Y'',''b'') where ''b'' is the base. Alternatively, since the most common unit of measurement of mutual information is the bit, a base of 2 could be specified. Intuitively, mutual information measures the information that ''X'' and ''Y'' share: it measures how much knowing one of these variables reduces our 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'' and ''Y'' are identical then all information conveyed by ''X'' is shared with ''Y'': knowing ''X'' determines the value of ''Y'' and vice versa. As a result, the mutual information is the same as the uncertainty contained in ''Y'' (or ''X'') alone, namely the [[information entropy|entropy]] of ''Y'' (or ''X'': clearly if ''X'' and ''Y'' are identical they have equal entropy). Mutual information quantifies the distance between the [[joint distribution]] of ''X'' and ''Y'' and what the joint distribution would be if ''X'' and ''Y'' were independent. Mutual information is a measure of 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'') &times; ''p''(''y''), and therefore: :<math> \log{ \left( \frac{p(x,y)}{p(x)\,p(y)} \right) } = \log 1 = 0. \,\! </math> Moreover, mutual information is nonnegative (i.e. ''I''(''X'';''Y'')&nbsp;≥&nbsp;0; see below) and [[symmetry|symmetric]] (i.e. ''I''(''X'';''Y'') = ''I''(''Y'';''X'')). ==Relation to other quantities== Mutual information can be equivalently expressed as :<math> \begin{align} I(X;Y) & {} = H(X) - H(X|Y) \\ & {} = H(Y) - H(Y|X) \\ & {} = H(X) + H(Y) - H(X,Y) \end{align} </math> where ''H''(''X'') and ''H''(''Y'') are the marginal [[information entropy|entropies]], ''H''(''X''|''Y'') and ''H''(''Y''|''X'') are the [[conditional entropy|conditional entropies]], and ''H''(''X'',''Y'') is the [[joint entropy]] of ''X'' and ''Y''. Since ''H''(''X'') ≥ ''H''(''X''|''Y''), this characterization is consistent with the nonnegativity property stated above. Intuitively, if entropy ''H''(''X'') is regarded as a measure of uncertainty about a random variable, then ''H''(''X''|''Y'') is a measure of what ''Y'' does <em>not</em> say about ''X''. This is "the amount of uncertainty remaining about ''X'' after ''Y'' is known", and thus the right side of the first of these equalities can be read as "the amount of uncertainty in ''X'', minus the amount of uncertainty in ''X'' which remains after ''Y'' is known", which is equivalent to "the amount of uncertainty in ''X'' which is removed by knowing ''Y''". 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 more information about itself than any other variable can provide. Mutual information can also be expressed as a [[Kullback-Leibler divergence]], of the product ''p''(''x'') &times; ''p''(''y'') of the [[marginal distribution]]s of the two random variables ''X'' and ''Y'', from ''p''(''x'',''y'') the random variables' [[joint distribution]]: :<math> I(X;Y) = D_{\mathrm{KL}}(p(x,y)\|p(x)p(y)). </math> Furthermore, let ''p''(''x''|''y'') = ''p''(''x'', ''y'') / ''p''(''y''). Then :<math> \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} </math> Thus mutual information can thus also be understood as the [[expected value|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''), the greater the [[Kullback-Leibler divergence|information gain]]. == Variations of the mutual information == Several variations on the mutual information have been proposed to suit various needs. Among these are normalized variants and generalizations to more than two variables. === Conditional mutual information === Sometimes it is useful to express the mutual information of two random variables conditioned on a third. :<math>I(X;Y|Z) = \mathbb E_Z I\big((X|Z);(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)},</math> which can be simplified as :<math>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)}.</math> Conditioning on a third random variable may either increase or decrease the mutual information, but it is always true that :<math>I(X;Y|Z) \ge 0</math> 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 === 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 diagram]]s, as explained in the article ''[[Information theory and measure theory]]'', then the only definition of multivariate mutual information that makes sense is as follows: :<math>I(X_1) = H(X_1),</math> <math>I(X_1|X_2) = H(X_1|X_2)</math> and for <math>n > 1,</math> :<math>I(X_1;\,...\,;X_n) = I(X_1;\,...\,;X_{n-1}) - I(X_1;\,...\,;X_{n-1}|X_n),</math> where (as above) we define :<math>I(X_1;\,...\,;X_{n-1}|X_n) = \mathbb E_{X_n} I\big((X_1|X_n);\,...\,;(X_{n-1}|X_n)\big).</math> (This definition is identical to that of [[interaction information]] except for a change in sign with an odd number of random variables.) ====Applications==== Some have criticized the blind application of information diagrams used to derive the above definition, 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 <math>n \ge 3.</math> One high-dimensional generalization scheme that maximizes the mutual information between the joint distribution and other target variables is found be useful in [[feature selection]]. === Normalized variants === Normalized variants of the mutual information are provided by the ''coefficients of constraint'' (Coombs, Dawes & Tversky 1970) or ''uncertainty coefficient'' (Press & Flannery 1988) :<math> C_{XY}=\frac{I(X;Y)}{H(Y)} ~~~~\mbox{and}~~~~ C_{YX}=\frac{I(X;Y)}{H(X)} </math> The two coefficients are not necessarily equal. A more useful and symmetric scaled information measure is the ''redundancy''{{Fact|date=July 2008}} :<math>R= \frac{I(X;Y)}{H(X)+H(Y)}</math> which attains a minimum of zero when the variables are independent and a maximum value of :<math>R_{\max }=\frac{\min (H(X),H(Y))}{H(X)+H(Y)} </math> 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 :<math>U(X,Y) = 2R = 2 \frac{I(X;Y)}{H(X)+H(Y)}</math> which represents a weighted average of the two uncertainty coefficients (Press & Flannery 1988). Other normalized versions are provided by the following expressions (Yao 2003, Strehl & Ghosh 2002). :<math> \frac{I(X;Y)}{\mbox{min}(H(X),H(Y))}, ~~~~~~~ \frac{I(X;Y)}{H(X,Y)}, ~~~~~~~ \frac{I(X;Y)}{\sqrt{H(X)H(Y)}} </math> === Weighted variants === In the traditional formulation of the mutual information, :<math> I(X;Y) = \sum_{y \in Y} \sum_{x \in X} p(x,y) \log \frac{p(x,y)}{p(x)\,p(y)}, </math> each ''event'' or ''object'' specified by <math>(x,y)</math> is weighted by the corresponding probability <math>p(x,y)</math>. 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 <math>\{(1,1),(2,2),(3,3)\}</math> may be viewed as stronger (by some standard) than the deterministic mapping <math>\{(1,3),(2,1),(3,2)\}</math>, 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) :<math> 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)}, </math> which places a weight <math>w(x,y)</math> on the probability of each variable value co-occurrence, <math>p(x,y)</math>. 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 <math>w(1,1)</math>, <math>w(2,2)</math>, and <math>w(3,3)</math> would have the effect of assessing greater ''informativeness'' for the relation <math>\{(1,1),(2,2),(3,3)\}</math> than for the relation <math>\{(1,3),(2,1),(3,2)\}</math>, which may be desirable in some cases of pattern recognition, and the like. There has been little mathematical work done on the weighted mutual information and its properties, however. === Absolute mutual information ===<!-- This section is linked from [[Kolmogorov complexity]] --> Using the ideas of [[Kolmogorov complexity]], one can consider the mutual information of two sequences independent of any probability distribution: :<math> I_K(X;Y) = K(X) - K(X|Y). </math> To establish that this quantity is symmetric up to a logarithmic factor (<math>I_K(X;Y) \approx I_K(Y;X)</math>) requires the [[chain rule for Kolmogorov complexity]] {{Harvard citation|Li|1997}}. Approximations of this quantity via [[Data compression|compression]] can be used to define a [[Metric (mathematics)|distance measure]] to perform a [[hierarchical clustering]] of sequences without having any [[domain knowledge]] of the sequences {{Harvard citation|Cilibrasi|2005}}. ==Applications of mutual information== In many applications, one wants to maximize mutual information (thus increasing dependencies), which is often equivalent to minimizing [[conditional entropy]]. Examples include: * The [[channel capacity]] is equal to the mutual information, maximized over all input distributions. * [[Discriminative training]] procedures for [[hidden Markov model]]s have been proposed based on the [[maximum mutual information]] (MMI) criterion. * [[RNA structure|RNA secondary structure]] prediction from a [[multiple sequence alignment]]. * 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 often used as a significance function for the computation of [[collocation]]s in [[corpus linguistics]]. * 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]] [[Independent component analysis]] algorithm * Average mutual information in [[delay embedding theorem]] is used for determining the ''embedding delay'' parameter. * Mutual information between [[genes]] in [[microarray|expression microarray]] data is used by the [[ARACNE]] algorithm for reconstruction of [[gene regulatory network|gene networks]]. == See also == * [[Pointwise mutual information]] == References == * {{cite journal | last = Cilibrasi | first = R. | coauthors = Paul Vit&aacute;nyi | title = Clustering by compression | journal = IEEE Transactions on Information Theory | volume = 51 | issue = 4 | pages = 1523–1545 | date = 2005 | url = http://www.cwi.nl/~paulv/papers/cluster.pdf | format = [[PDF]] | doi = 10.1109/TIT.2005.844059 }} * Coombs, C. H., Dawes, R. M. & Tversky, A. (1970), ''Mathematical Psychology: An Elementary Introduction'', Prentice-Hall, Englewood Cliffs, NJ. * Cronbach L. J. (1954). On the non-rational application of information measures in psychology, in H Quastler, ed., ''Information Theory in Psychology: Problems and Methods'', Free Press, Glencoe, Illinois, pp. 14—30. * Kenneth Ward Church and Patrick Hanks. Word association norms, mutual information, and lexicography, ''Proceedings of the 27th Annual Meeting of the Association for Computational Linguistics'', 1989. * Guiasu, Silviu (1977), ''Information Theory with Applications'', McGraw-Hill, New York. * {{cite book | last = Li | first = Ming | coauthors = Paul Vit&aacute;nyi | title = An introduction to Kolmogorov complexity and its applications | location = New York | publisher = [[Springer-Verlag]] | date = 1997 | month = February | id = ISBN 0387948686 }} * Lockhead G. R. (1970). Identification and the form of multidimensional discrimination space, ''Journal of Experimental Psychology'' '''85'''(1), 1-10. * [[Athanasios Papoulis]]. ''Probability, Random Variables, and Stochastic Processes'', second edition. New York: McGraw-Hill, 1984. ''(See Chapter 15.)'' * Press, W. H., Flannery, B. P., Teukolsky, S. A. & Vetterling, W. T. (1988), ''Numerical Recipes in C: The Art of Scientific Computing'', Cambridge University Press, Cambridge, p. 634 * {{cite journal | last = [[Alexander Strehl|Strehl]] | first = Alexander | coauthors = Joydeep Ghosh | title = Cluster ensembles -- a knowledge reuse framework for combining multiple partitions | journal = Journal of Machine Learning Research | volume = 3 | pages = 583–617 | date = 2002 | url = http://strehl.com/download/strehl-jmlr02.pdf | format = [[PDF]] | doi = 10.1162/153244303321897735 }} * Witten, Ian H. & Frank, Eibe (2005), ''Data Mining: Practical Machine Learning Tools and Techniques'', Morgan Kaufmann, Amsterdam. * Yao, Y. Y. (2003) Information-theoretic measures for knowledge discovery and data mining, in ''Entropy Measures, Maximum Entropy Principle and Emerging Applications'' , Karmeshu (ed.), Springer, pp. 115-136. * Peng, H.C., Long, F., and Ding, C., "Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27, No. 8, pp.1226-1238, 2005. [http://research.janelia.org/peng/proj/mRMR/index.htm Program] * Andre S. Ribeiro, Stuart A. Kauffman, Jason Lloyd-Price, Bjorn Samuelsson, and Joshua Socolar, (2008) "Mutual Information in Random Boolean models of regulatory networks", Physical Review E, Vol.77, No.1. arXiv:0707.3642. [[Category:Information theory]] [[de:Transinformation]] [[es:Información mutua]] [[fr:Information mutuelle]] [[ja:相互情報量]] [[pl:Informacja wzajemna]]