On Strong Anti-learning of Parity

On some data, machine learning displays anti-learning; that is, while the classifier demonstrates excellent performance on the training set, it performs much worse than the random classifier on the test set. In this paper we study what we call strong anti-learning, that is, the most surprising scenario, in which the more examples you place in the training set, the worse the accuracy becomes, until it becomes \(0\%\) on the test set. We produce a framework in which strong anti-learning can be reproduced and studied theoretically. We deduce a formula estimating anti-learning when decision trees (one of the most important tools of machine learning) solve the parity bit problem (one of the most famously tricky problems of machine learning). Our estimation formula (deduced under certain mathematical assumptions) agrees very well with experimental results (produced on random data without these assumptions).