Full search page →

Two useless clues can be useful together

AdvancedIT 08 · Networks, Information Inequalities and LearningInteractive plot

Description

Compute information about a noisy XOR label from each independent bit and from their pair.

Try this: Set label noise to zero. Why does each feature have zero information while their pair has one bit?

Predict first

Each of A and B alone carries zero information about the label. With no label noise, how much do the two together tell you?

Hints

The chapter section that uses this lab:

Explanation

Answer the prediction first, or open the explanation when you are ready.

Show the explanation

The label is A XOR B. Knowing one bit leaves the label a fair coin flip, but knowing both fixes it exactly: I(A,B;Y) = 1 − h₂(ε), which is 1 bit at ε = 0.

Lab · Two useless clues can be useful together

Predict first

Each of A and B alone carries zero information about the label. With no label noise, how much do the two together tell you?

I(A;Y)
0 bits
I(B;Y)
0 bits
I(A,B;Y)
0.531 bits
I(A;Y|B)
0.531 bits

Averaging either row or column gives 0.5: a single feature does not change the label distribution. Observing both can.

Try this: Set label noise to zero. Why does each feature have zero information while their pair has one bit?

A and B are independent fair bits, Y=A XOR B XOR E, E~Bernoulli(ε) independent. Thus I(A;Y)=I(B;Y)=0 and I(A,B;Y)=1−h₂(ε). This population identity does not establish a finite-sample generalization bound.

Method sources

Open in the Playground →