Mutual Information

How much does knowing one thing tell you about another? Mutual information measures the reduction in surprise about Y once you have seen X, in bits. Unlike correlation it catches any dependence at all, linear or not — which makes it the natural thing to want, and notoriously hard to actually compute in high dimensions.

Estimating it from samples is the whole difficulty: the number of samples needed grows exponentially with the value being estimated, so any bound reported above a few bits should be read as a lower bound the estimator happened to reach rather than a measurement. InfoNCE is the estimator most of this graph relies on without saying so — every contrastive objective is a bound on mutual information, capped by log of the batch size.

I(X;Y) = H(X) − H(X|Y) = D sub _KL (p(x,y)‖p(x)p(y)), symmetric in its arguments and zero exactly when X and Y are independent. The InfoNCE bound is I ≥ log K − L for a batch of K, which is why contrastive learning wants large batches: the bound it optimises cannot exceed log K however good the representation is.