The Two Features That Look Like Noise

Let $X$ be uniform on $\{-2, -1, 1, 2\}$ and let $Y = |X|$. Knowing $X$ tells you $Y$ with certainty. The correlation between them is

$$\rho(X, Y) = 0.0000000000,$$

exactly, by symmetry. Correlation measures one thing: how much of $Y$ moves linearly with $X$. Here none of it does, and all of it is determined.

Mutual information is not fooled:

$$H(X) = 2 \text{ bits}, \qquad H(Y) = 1 \text{ bit}, \qquad I(X;Y) = 1 \text{ bit}.$$

Knowing $X$ removes all of $Y$'s uncertainty. This part of the story is familiar, and the usual conclusion is "use mutual information instead of correlation". The second construction is the one that should worry you, because mutual information does not save you from it either.

A. Three variables, no pair informative

Let $A$ and $B$ be independent fair bits and let $C = A \oplus B$, the exclusive or. Every pairwise mutual information:

$$I(A;B) = I(A;C) = I(B;C) = 0.0000000000 \text{ bits}.$$

Any two of the three are independent. Look at $A$ alone and $C$ looks like a coin flip. Look at $B$ alone and $C$ looks like a coin flip. Yet

$$I(A, B \,;\, C) = 1 \text{ bit},$$

which is all of $C$. The pair determines the target completely and neither member of the pair carries a single bit about it.

Open the figure's second tab, the pair that hides together, for this XOR pair: each input alone carries 0 bits about the target, and the pair carries 1.

B. What this does to feature selection

The standard first step on a wide dataset is univariate screening: score each feature against the target, keep the top ones, model those. Correlation, mutual information, a single-feature AUC, a chi-squared test - it does not matter which, they all agree here.

On the XOR data, every screening method scores $A$ and $B$ at exactly zero and drops both. A screen that kept the top 10% of a thousand features would drop them; a screen that kept the top 90% would drop them. They are not near the threshold, they are at the floor.

And the failure is not a rare corner. Any feature that acts through an interaction looks like this to some degree:

• a drug that helps one genotype and harms another, with no main effect
• a control that matters only above a temperature
• a difference between two measurements when neither measurement alone is informative
• any target that depends on a parity, a ratio, or a match between two fields

C. What to do instead

• Screen with a model that can see pairs. A shallow gradient-boosted tree on all features, scored by permutation importance, finds $A$ and $B$ immediately, because a depth-two tree can represent XOR and a single split cannot.
• Screen in blocks rather than singly, when the features have known structure: the two ends of a measurement, the before and after, the pair of fields that are compared downstream.
• Construct the interaction if you suspect one. A difference, a ratio or a product computed before screening turns a pairwise effect into a univariate one, and is checkable in a line.
• Treat "no feature was predictive" as a hypothesis, not a finding. The XOR table is what that conclusion looks like when it is wrong.

The general statement is worth keeping in the exact form the numbers give it. Independence of every pair does not imply independence of the set: the joint distribution of $(A, B, C)$ is not the product of its margins even though every two-way margin factorises. Every screening procedure that scores features one at a time is assuming the opposite.