Towards a framework for algorithm learning : cross-domain induction and the principled limits of algorithmic abstraction

Abstract

Computation graphs over homogeneous algebras allow for the learning of algorithms from data that sequentially reflect individual computation steps- so-called memory traces - to be framed as a classical machine learning problem, specifically as a classification task. However, previous work revealed two central limitations: (1) Changes in the input data distribution lead to a significant drop in model accuracy, limiting transferability. (2) The concept of abstraction in the context of computation graphs over homogeneous algebras remained vague and lacked formal definition. We evaluate the effectiveness of domain generalization methods in handling shifts in input distributions. Based on a systematic literature review, we select two established approaches and compare their performance with our domain-specific method, DIBE. We conduct a case study using classical comparison-based sorting algorithms and empirically demonstrate that some of these methods improve model robustness to domain shifts. Furthermore, we extend the theory of computation graphs over homogeneous algebras by introducing the notion of a quotient algebra. Quotient algebras are used to formally define two forms of abstraction: structural abstraction, as the compression of linear computation sequences independent of the underlying carrier set, and modular abstraction, as black-box operations. Finally, we prove that modular abstraction constitutes an undecidable decision problem, indicating that this type of abstraction is partially inaccessible to algorithmic approaches.