Lisitsa, Alexei and Vernitski, Alexei (2024) On strong anti-learning of parity. In: OL2A 2023: International Conference on Optimization, Learning Algorithms and Applications 2023, 2023-09-27 - 2023-09-29, Ponta Delgada, Portugal. (In Press)
Lisitsa, Alexei and Vernitski, Alexei (2024) On strong anti-learning of parity. In: OL2A 2023: International Conference on Optimization, Learning Algorithms and Applications 2023, 2023-09-27 - 2023-09-29, Ponta Delgada, Portugal. (In Press)
Lisitsa, Alexei and Vernitski, Alexei (2024) On strong anti-learning of parity. In: OL2A 2023: International Conference on Optimization, Learning Algorithms and Applications 2023, 2023-09-27 - 2023-09-29, Ponta Delgada, Portugal. (In Press)
Abstract
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).
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Divisions: | Faculty of Science and Health Faculty of Science and Health > Mathematics, Statistics and Actuarial Science, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 26 Jul 2023 09:09 |
Last Modified: | 16 May 2024 21:56 |
URI: | http://repository.essex.ac.uk/id/eprint/36054 |