Conditional entropy

Conditional entropy is a quantity in information theory that measures the average uncertainty remaining about a random variable after another variable is observed. Written $H(X\mid Y)$, it averages the Shannon entropy of the conditional distributions of $X$ over possible observations of $Y$. It describes uncertainty under a specified probabilistic model, rather than uncertainty about any particular observed outcome. (math.mit.edu)

Definition and interpretation

For discrete variables $X$ and $Y$, let $p(x,y)$ denote their joint probability distribution and $p(x\mid y)$ their conditional probability. Conditional entropy is defined by

Equivalently,

Terms with zero joint probability contribute zero. Observations having $p(y)=0$ are omitted because their conditional distributions do not affect the average. (math.mit.edu)

The logarithm’s base determines the unit: base two gives bits, while the natural logarithm gives nats. In expected-value notation,

Thus it is the average conditional self-information of $X$. Unlike $H(X\mid Y=y)$, which concerns one observation, $H(X\mid Y)$ averages over the entire probability distribution of observations. A discrete $X$ can also be conditioned on a continuous $Y$, using an expectation rather than a discrete sum over $y$. (people.lids.mit.edu)

Fundamental identities and inequalities

The entropy chain rule expresses joint uncertainty as uncertainty about one variable plus the uncertainty remaining about the other:

For a finite sequence, its extension is

where the first term is $H(X_1)$. These identities follow by factoring joint probabilities into conditional probabilities. When entropies are finite, the first identity also gives $H(X\mid Y)=H(X,Y)-H(Y)$. Direct definitions remain important when subtraction would produce the undefined expression $\infty-\infty$. (people.csail.mit.edu)

For finite-valued variables,

The upper equality holds precisely when $X$ and $Y$ exhibit statistical independence. The lower equality holds precisely when $X$ is a deterministic function of $Y$, except on events of probability zero. Conditional entropy is generally asymmetric: knowing $Y$ may determine $X$, without knowing $X$ determining $Y$. (ocw.mit.edu)

Additional conditioning cannot increase average discrete entropy:

The difference is conditional mutual information, $I(X;Z\mid Y)$, which is nonnegative. For finite-valued variables, equality holds exactly when $X$ and $Z$ have conditional independence given $Y$. Likewise, mutual information satisfies

quantifying how much observing $Y$ reduces uncertainty about $X$ on average. (ocw.mit.edu)

Examples and the role of averaging

Consider a fair binary variable $X$, and let $Y$ equal $X$ with probability $1-\varepsilon$, otherwise taking the opposite value, independently of $X$. Applying the definition gives

At $\varepsilon=0$, the observation identifies $X$. At $\varepsilon=\tfrac12$, it provides no information, leaving one bit of uncertainty. At $\varepsilon=1$, it again identifies $X$, because the observed value is always inverted. These are direct consequences of the conditional distributions. (math.mit.edu)

“Conditioning reduces entropy” is an average statement, not a guarantee for every observation. For example, let $U$ and $Y$ be independent fair binary variables, and set $X=U\lor Y$. Then $H(X)=h_2(1/4)$, approximately $0.811$ bits. Observing $Y=0$ leaves $X=U$, raising uncertainty to one bit; observing $Y=1$ determines $X$. Their average is nevertheless $H(X\mid Y)=0.5$ bits, below the unconditional entropy. (ocw.mit.edu)

Coding and statistical learning

In lossless data compression with side information, conditional entropy determines an asymptotic coding threshold. For independent, identically distributed finite-alphabet pairs $(X_i,Y_i)$, rates above $H(X\mid Y)$ permit reconstruction of $X$-blocks with error probability tending to zero when the decoder knows the corresponding $Y$-blocks. The Slepian–Wolf theorem establishes that this threshold remains achievable even when the encoder does not know those observations. (people.lids.mit.edu)

Conditional entropy also describes uncertainty in dependent sequences. For a stationary finite-alphabet stochastic process, the uncertainty about the next symbol conditioned on increasingly long histories converges to the entropy rate. In a stationary first-order Markov chain, this rate is $H(X_{t+1}\mid X_t)$. (stanforddatacompressionclass.github.io)

In machine learning, $H(Y\mid X)$ measures uncertainty about a label $Y$ given features $X$. It is distinct from the conditional cross-entropy of a model $q(y\mid x)$. Their difference is the expected Kullback–Leibler divergence between the true conditional distribution and the model. Consequently, under unrestricted prediction, conditional entropy is the minimum achievable population logarithmic loss, rather than necessarily the loss attained by a trained model. (s3-us-west-2.amazonaws.com)

Continuous variables

For continuous variables admitting a joint probability density function, conditional differential entropy is

When the relevant quantities are finite, $h(X\mid Y)=h(X,Y)-h(Y)$. Unlike discrete conditional entropy, it can be negative and changes when the scale of $X$ changes. It is therefore not directly interpretable as a nonnegative number of bits required for exact representation of a continuous observation. Mutual information remains nonnegative and equals $h(X)-h(X\mid Y)$ when that difference is well defined. (s3-us-west-2.amazonaws.com)

References

1. 600: Lecture 33 — Entropymath.mit.edu
2. Information Theory — Polyanskiy and Wupeople.lids.mit.edu
3. 441S16: Course Notesocw.mit.edu
4. ST06 — Lecture 3people.csail.mit.edu
5. Non IID Sources and Entropy Ratestanforddatacompressionclass.github.io
6. 11. Information Theory — Dive into Deep Learnings3-us-west-2.amazonaws.com