Towards a Framework for Learning of Algorithms: The Case of Learned Comparison Sorts

Towards a Framework for Learning of Algorithms: The Case of Learned Comparison Sorts

Philipp Kunz, Ilche Georgievski, Marco Aiello

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 4353-4360. https://doi.org/10.24963/ijcai.2024/481

Designing algorithms is cumbersome and error-prone. This, among other things, has increasingly led to efforts to extend or even replace designing algorithms with machine learning models. While previous research has demonstrated that some machine learning models possess Turing-completeness, the findings are largely theoretical, and solutions for specific algorithmic tasks remain unclear. With this in mind, we investigate the feasibility of learning representations of classical algorithms from data on their execution, enabling their application to different inputs. We propose a novel and general framework for algorithm learning consisting of a model of computation that facilitates algorithm analysis across various levels of abstraction. We formalize the problem of learning an algorithm using an algebraic approach for graph traversal. We apply this framework to comparison sorts and evaluate the inferred machine learning models' performance, demonstrating the applicability of the approach in terms of accuracy and sensitivity.
Keywords:
Machine Learning: ML: Applications
Machine Learning: ML: Classification
Machine Learning: ML: Supervised Learning