Efficient learning through programmatic representations
Improving transformation search in BEN
D. Condratov (TU Delft - Electrical Engineering, Mathematics and Computer Science)
D.Z. Zak – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
S. Dumančić – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
A. van Deursen – Graduation committee member (TU Delft - Electrical Engineering, Mathematics and Computer Science)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The Abstraction and Reasoning Corpus (ARC) challenges systems to recognise patterns from just a few input-output examples, which proves to be a setting where most current approaches struggle. Program synthesis systems like BEN tackle this by decomposing the images into objects rather than pixels and then searching for transformation programs that explain the examples. However, its reliance on exhaustive enumeration makes the transformation search computationally expensive and difficult to scale.
This project aims to improve the transformation search and, in doing so, asks whether correspondence-tailored grammar pruning can reduce the search space and improve the efficiency of BEN’s conquer step. BEN is reimplemented in Julia using the Herb.jl library. On top of that, a pruning strategy that exploits structural similarities between matched input-output object pairs is added. Both the baseline and the improved version are evaluated on the 400-task ARC training set.
The pruning reduces the average number of candidate programs evaluated by 77%, but it has a seemingly slight negative impact on the tasks that get solved. The number of correctly solved tasks decreases from 31 to 30. These results show that simple structural observations about the matched object pairs substantially reduce the search space. More informed search looks like a promising direction for improving program synthesis systems on ARC.