I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it.

In a scenario very similar to popular binary classification machine learning contests, competitors are required to submit their answers to the test set containing N data points. The accuracy of the submission will be announced. The competitors can then submit a new answer, and the new accuracy will always be published, no matter improved or not.

If the competitor has no information about the test set at all, what is the optimal way (in the sense that the least submissions are needed) to crack the challenge?

  • 1
    $\begingroup$ Information-theoretically, you need at least $N/\log_2(N+1)$ tests, and you can certainly do it with $N+1$. The lower bound is probably closer to the truth. $\endgroup$ – Yuval Filmus Sep 26 '17 at 10:12

Your problem is tackled in Vaishampayan, Query Matrices for Retrieving Binary Vectors Based on the Hamming Distance Oracle. Vaishampayan relates this problem to one considered in Lev and Yuster, On the size of dissociated bases, and the upshot (if I understand things correctly) is that a random test set of size $O(N/\log N)$ (for an appropriate hidden constant) would do if you don't care about carrying the decoding procedure efficiently. Vaishampayan describes a more structured solution using $o(N)$ tests which can be implemented efficiently.


Here is another interesting scheme, which might be better if your initial classifier has high accuracy. Suppose your classifier has a 99% accuracy, i.e., an 1% error rate. Divide the test set into $N/100$ blocks of 100 data points. We will work on one block at a time, for each block recovering the correct classification of all 100 data points in that block.

Note that we expect about 37% of the blocks to be have no errors (all 100 data points are classified correctly by your classifier), 37% to have one error, and 26% to have two or more errors. We can figure out how many errors are present in a block by making a single query: flip the prediction for all 100 data points in the block (leaving the other $N-100$ predictions unchanged), submit it, and see how much the accuracy decreases. If the number of correct predictions decreases by 100, then the original predictions were all correct; if it decreases by 98, then there was 1 error in the original predictions; otherwise there were 2 or more errors.

Also, you can find the locations of the errors. For instance, if there is a single error, you can find the location of the error by doing binary search: split the block in half, and test whether the error is in the first half or second half by testing the number of errors in the first half. Recurse. This will find the location of a single error using $\lg 100$ submissions on average. In general, if there are $k$ errors in the block, you can find the location of them using at most $k \lg 100$ submissions.

Once you have finished this procedure for a block, you know the correct classification of all points within the block.

Since the number of errors in each block has a Poisson distribution, the average number of errors is 1. Therefore, on average we will do $1 + \lg 100 \approx 7.6$ submissions per block. After $(N/100) \times (1 + \lg 100) \approx 0.076 N$ submissions, you learn the correct classification for all points in the test set. You can of course generalize; if the error rate is $1/m$, then you can use blocks of size $m$, and you'll need about $(N/m) (1 + \lg m)$ submissions to reverse engineer the test set.

This shows that the higher the initial accuracy of your classifier, the fewer number of submissions needed to reverse engineer the correct classification of all data points in the test set.

As a heuristic, you can also recover the correct classification for some number of data points (by processing some of the blocks as above), then add those to your training set, and make new predictions on the remaining data points in the test set. If you are lucky, perhaps your classification accuracy on the remainder will improve (thanks to the additional training data), and perhaps even fewer submissions will be needed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.