Question
A research team tests a binary classifier on the same four hidden validation examples again and again. Their identifiers are public, but their labels \(y_1,\ldots,y_4\) are secret. Each label is an independent fair coin flip unrelated to its identifier. For every submitted vector of four binary predictions, the validation service replies with the exact number of correct predictions, an integer from 0 to 4. The service permits five score queries and does not disclose raw labels.
A researcher first submits four zeros. For query i=1,2,3,4, they may use all previous scores when choosing the next four predictions. Devise a procedure that learns every hidden label within the remaining four queries. Quantify how much label information the transcript reveals, then compare the final memorizing classifier's apparent error on these four examples with its expected error on fresh, unrelated identifiers whose labels are still fair coins.
Get hint
Hint 1
Compare the score of the all-zero predictions with a score obtained by changing only one new position from zero to one.
Check your answer
Solution
Write \(S(v)=\sum_{j=1}^{4}1\{v_j=y_j\}\) for the exact returned score of prediction vector \(v\). First query \(v=(0,0,0,0)\), giving \(s_0=S(0,0,0,0)\). This baseline is the number of zero labels.
Recover labels sequentially. Suppose \(y_1,\ldots,y_{i-1}\) are already known. Submit the adaptive vector \(v^{(i)}=(y_1,\ldots,y_{i-1},1,0,\ldots,0)\), where position \(i\) is 1 and all later positions are 0, and observe score \(s_i\). The hypothetical prediction vector with the same recovered first i−1 labels but with position i still zero would score exactly \(s_0+\sum_{j<i}y_j\): changing a previously recovered position from the baseline 0 to its correct label adds one point only when that label is 1.
Thus the new score difference is
\(d_i=s_i-[s_0+\sum_{j<i}y_j]=+1\text{ if }y_i=1,\text{ and }-1\text{ if }y_i=0.\)
So \(y_i=(d_i+1)/2\). Apply this for \(i=1,2,3,4\). The method uses one baseline and four further queries, each informed by the earlier answers; it identifies every one of the \(2^{4}=16\) possible label vectors. Since the four labels are independent fair bits, their entropy is \(H(Y)=4\) bits. Because the transcript is a deterministic function of Y and uniquely determines Y, the mutual information is \(I(Y;\mathrm{transcript})=H(Y)=4\) bits. The exact scores have revealed the entire hidden target vector despite never displaying individual labels.
Now submit the classifier that remembers the four identifier–label pairs. Its validation error on the reused holdout is \(0/4=0\). For a genuinely fresh identifier, its label remains an independent \(\operatorname{Bernoulli}(1/2)\) random variable, so any prediction based only on previous labels and identifiers errs with probability \(1/2\). The expected fresh-sample error is 50%, not zero. A memorizing model can therefore have perfect apparent validation performance with no generalizable signal. Reusing a supposedly secret holdout with informative score feedback is not an independent final test.
Assumptions
There are exactly four fixed holdout identifiers and independent \(\operatorname{Bernoulli}(1/2)\) labels unrelated to any predictive features.
All score queries reuse precisely these four examples; scores are exact integer counts without added noise or rounding.
A researcher may choose queries adaptively and may submit a final memorizing predictor after the five score queries.
Fresh test identifiers carry new independent fair-coin labels, so past memorization supplies no new predictive information.
Final Answer
Five exact score queries recover all four labels (4 bits of information); memorized holdout error is \(0/4\), but expected error on fresh independent labels is \(1/2\) per example.