Conditional mutual information


Conditional mutual information

In probability theory, and in particular, information theory, the conditional mutual information is, in its most basic form, the expected value of the mutual information of two random variables given the value of a third.

Contents

Definition

For discrete random variables X, Y, and Z, we define

I(X;Y|Z) = \mathbb E_Z \big(I(X;Y)|Z\big)
    = \sum_{z\in Z} p_Z(z) \sum_{y\in Y} \sum_{x\in X}
      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)},

where the marginal, joint, and/or conditional probability mass functions are denoted by p with the appropriate subscript. This 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)}.

Alternatively, we may write[1]

I(X;Y | Z) = H(X,Z) + H(Y,Z) − H(X,Y,Z) − H(Z)

Conditional mutual information can also be rewritten to show its relationship to mutual information

I(X;Y | Z) = H(X | Z) − H(X | Y,Z) = I(X;Y) − H(Z) + H(Z | X) + H(Z | Y) − H(Z | X,Y)

Conditioning on a third random variable may either increase or decrease the mutual information: that is, the difference I(X;Y | Z) − I(X;Y), called the interaction information, may be positive, negative, or zero, 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, in particular, those known as Shannon-type inequalities.

Like mutual information, conditional mutual information can be expressed as a Kullback-Leibler divergence:

 I(X;Y|Z) = D_{\mathrm{KL}}[ p(X,Y,Z) \| p(X|Z)p(Y|Z)p(Z) ].

Or as an expected value of simpler Kullback-Leibler divergences:

 I(X;Y|Z) = \sum_{z \in Z} p( Z=z ) D_{\mathrm{KL}}[ p(X,Y|z) \| p(X|z)p(Y|z) ],
 I(X;Y|Z) = \sum_{y \in Y} p( Y=y ) D_{\mathrm{KL}}[ p(X,Z|y) \| p(X|Z)p(Z|y) ].

More general definition

A more general definition of conditional mutual information, applicable to random variables with continuous or other arbitrary distributions, will depend on the concept of regular conditional probability. (See also.[2][3])

Let (\Omega, \mathcal F, \mathfrak P) be a probability space, and let the random variables X, Y, and Z each be defined as a Borel-measurable function from Ω to some state space endowed with a topological structure.

Consider the Borel measure (on the σ-algebra generated by the open sets) in the state space of each random variable defined by assigning each Borel set the \mathfrak P-measure of its preimage in \mathcal F. This is called the pushforward measure X _* \mathfrak P = \mathfrak P\big(X^{-1}(\cdot)\big). The support of a random variable is defined to be the topological support of this measure, i.e. \mathrm{supp}\,X = \mathrm{supp}\,X _* \mathfrak P.

Now we can formally define the conditional probability measure given the value of one (or, via the product topology, more) of the random variables. Let M be a measurable subset of Ω, (i.e. M \in \mathcal F,) and let x \in \mathrm{supp}\,X. Then, using the disintegration theorem:

\mathfrak P(M | X=x) = \lim_{U \ni x}
  \frac {\mathfrak P(M \cap \{X \in U\})}
        {\mathfrak P(\{X \in U\})}
  \qquad \textrm{and} \qquad \mathfrak P(M|X) = \int_M d\mathfrak P\big(\omega|X=X(\omega)\big),

where the limit is taken over the open neighborhoods U of x, as they are allowed to become arbitrarily smaller with respect to set inclusion.

Finally we can define the conditional mutual information via Lebesgue integration:

I(X;Y|Z) = \int_\Omega \log
  \frac {d \mathfrak P(\omega|X,Z)\, d\mathfrak P(\omega|Y,Z)}
        {d \mathfrak P(\omega|Z)\, d\mathfrak P(\omega|X,Y,Z)}
  d \mathfrak P(\omega),

where the integrand is the logarithm of a Radon–Nikodym derivative involving some of the conditional probability measures we have just defined.

Note on notation

In an expression such as I(A;B | C), A, B, and C need not necessarily be restricted to representing individual random variables, but could also represent the joint distribution of any collection of random variables defined on the same probability space. As is common in probability theory, we may use the comma to denote such a joint distribution, e.g. I(A0,A1;B1,B2,B3 | C0,C1). Hence the use of the semicolon (or occasionally a colon or even a wedge \wedge) to separate the principal arguments of the mutual information symbol. (No such distinction is necessary in the symbol for joint entropy, since the joint entropy of any number of random variables is the same as the entropy of their joint distribution.)

Multivariate mutual information

The conditional mutual information can be used to inductively define a multivariate mutual information in a set- or measure-theoretic sense in the context of information diagrams. In this sense we define the multivariate mutual information as follows:

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

where

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

This definition is identical to that of interaction information except for a change in sign in the case of an odd number of random variables. A complication is that this multivariate mutual information (as well as the interaction information) can be positive, negative, or zero, which makes this quantity difficult to interpret intuitively. In fact, for n random variables, there are 2n − 1 degrees of freedom for how they might be correlated in an information-theoretic sense, corresponding to each non-empty subset of these variables. These degrees of freedom are bounded by various Shannon- and non-Shannon-type inequalities in information theory.

References

  1. ^ K. Makarychev et al. A new class of non-Shannon-type inequalities for entropies. Communications in Information and Systems, Vol. 2, No. 2, pp. 147–166, December 2002 PDF
  2. ^ Regular Conditional Probability on PlanetMath
  3. ^ D. Leao Jr. et al. Regular conditional probability, disintegration of probability and Radon spaces. Proyecciones. Vol. 23, No. 1, pp. 15–29, May 2004, Universidad Católica del Norte, Antofagasta, Chile PDF

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Mutual information — 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 (sometimes known by the archaic term… …   Wikipedia

  • Multivariate mutual information — In information theory there have been various attempts over the years to extend the definition of mutual information to more than two random variables. These attempts have met with a great deal of confusion and a realization that interactions… …   Wikipedia

  • Information theory — Not to be confused with Information science. Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental… …   Wikipedia

  • Information theory and measure theory — Measures in information theory = Many of the formulas in information theory have separate versions for continuous and discrete cases, i.e. integrals for the continuous case and sums for the discrete case. These versions can often be generalized… …   Wikipedia

  • Conditional entropy — 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 information theory, the conditional entropy (or equivocation) quantifies the remaining entropy (i.e.… …   Wikipedia

  • Information bottleneck method — The information bottleneck method is a technique introduced by Tishby et al [1] for finding the best tradeoff between accuracy and complexity (compression) when summarizing (e.g. clustering) a random variable X, given a joint probability… …   Wikipedia

  • Information diagram — An information diagram is a type of Venn diagram used in information theory to illustrate relationships among Shannon s basic measures of information: entropy, joint entropy, conditional entropy and mutual information. [Fazlollah Reza. An… …   Wikipedia

  • Conditional budgeting — is a budgeting approach designed for companies with fluctuating income, high fixed costs, or income depending on sunk costs, as well as NPOs and NGOs. The approach builds on the strengths of proven budgeting approaches, leverages the respective… …   Wikipedia

  • Information Processing Language — (IPL) is a programming language developed by Allen Newell, Cliff Shaw, and Herbert Simon at RAND Corporation and the Carnegie Institute of Technology from about 1956. Newell had the role of language specifier application programmer, Shaw was the… …   Wikipedia

  • Inequalities in information theory — Inequalities are very important in the study of information theory. There are a number of different contexts in which these inequalities appear.hannon type inequalitiesConsider a finite collection of finitely (or at most countably) supported… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.