The Abstraction and Reasoning Corpus (ARC) comprising image-based logical reasoning tasks is intended to serve as a benchmark for measuring intelligence. Solving these tasks is very dificult for ofthe-shelf ML methods due to their diversity and low amount of training data. We here present our approach, which solves tasks via grammatical evolution on a domain-specific language for image transformations. With this approach, we successfully participated in an online challenge, scoring among the top 4% out of 900 participants.
The ARC challenge requires participants to develop a model that is able to solve tasks Di from the set D = fD1; : : : ; DM g. Each Di comprises an image-based Copyright © 2020 by the paper’s authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 1 https://www.kaggle.com/c/abstraction-and-reasoning-challenge/ 2 ls8-arc team on the oficial ARC challenge leaderboard.
(a) Training task 48 (b) Training task 100 (c) Training task 397 reasoning task with mi training pairs f(xk; yk)g and ni test pairs f(x^`; y^`)g, where mi > 0 is typically around 3 and ni > 0 is mostly 1. The images feature up to 10 discrete colors C = fc1; : : : ; c10g, and image sizes range between 1 and 30 pixels per dimension. The implied function f that maps inputs to the expected output images is vastly diferent for every task, often based on abstract features (e.g. connected shapes) or pattern continuation (see Figure 1). For each task Di, the method should derive f~i from f(xk; yk)g 2 Di which correctly maps all input images to the expected output: 8(x^`; y^`) 2 Di : f~i(x^`) = y^`.
The challenge participants have access to M = 400 training tasks, which show some logic concepts and come with labels y^`. The final scoring however is based on an undisclosed test set, whose task are only seen by the model. 3
For our approach, we assume that f can be broken down into a sequence of basic image transformations. We developed a custom domain-specific language (DSL) specifying such sequences, whose space of expressions is explored using an evolutionary algorithm (EA). We first explain our language in more detail and then show how we use an EA to create ARC task solvers from our DSL. Domain-Specific Language In a first step, we manually implemented solvers for approximately 20 random training tasks and identified reoccurring image operations, which became the basis of our DSL.
Let X = Su;v 1 Cu v denote the set of rectangular images with colors in C,
and X ordered lists of images, which we call layers. Our DSL is a context-free
grammar in Backus Naur Form (BNF) [
Our atomic functions comprise basic operations such as translation, rotation and cropping, as well as layer-specific operations like extracting a layer, sorting crop, rotate, …
T
X
X
L
sort, filter, … split_colors, duplicate, …
S
J union, top, … by diferent criteria, splitting images into layers, and merging them together. For additional flexibility, we also allow higher-order functions like map, which lifts the T -type to an L-type function by applying it to each layer. The grammar structure ensures that all possible expressions have an overall T -type logic, i.e. they transform a single input image into an output image. This allows to find solvers for some tasks, an example is given in Figure 3.
Grammatical Evolution We use Grammatical Evolution (GE) [
L(f jDi) = 1 mi
X dimg(f (xk); yk): mi k=1 Here we define dimg as (i) the proportion of correctly colored pixels (if images have equal size) or (ii) the Euclidean distance between the color histograms: dimg(x; y) =
(y)k2 1 + k (x) (Pi 1fxi6=yig=(uxvx) if ux = uy and vx = vy
else stripc1 split_colors sortArea;Desc top crop (1) (2) where u; v is the image width and height, 1fP g = 1 if P > else 0, and (x) = Pxi2x(1fxi=cg)c>2C as the (unnormalized) color histogram of x. f~ is an optimal solution if (and only if) all predictions are equal to the expected output, i.e. L(f jDi) = 0, thus we can also use Equation 1 as an early-stopping criterion. Following the evaluation procedure of the challenge, our accuracy is the proportion of correctly solved tasks: ACC = M 1 PiM=1 Q`n=i1 1ffi(x^`)=y^`g. Here, fi is the solution produced by our method after training on task Di. A grid search was performed to obtain good hyperparameters for population size, mutation rate and mutation strength. As GE is randomized, we ran the experiments with 40 diferent seeds and discuss the averaged results with standard deviation.
We first evaluate our method on the 400 training tasks of ARC, from which we solved 7:68( 0:61)%. The challenge leaderboard evaluation however is based on a secret data set of 100 tasks with slightly higher logic complexity. Here, we were able to correctly solve ACC = 3% of the tasks. Despite this seemingly low value, we scored among the top 30 of over 900 participants, which illustrates the challenge’s non-triviality. The small number of tasks makes it hard to assess the usefulness of atomic functions in the DSL. Moreover, there is no information about the overlap of required logic operations between training and test tasks.
Our results also made us question the efectiveness of GE considering the tremendous search space complexity. Small mutations to the current best individual, such as swapping out a single atomic function, can significantly change its behavior. As a result, the algorithm operates in a highly non-convex search space. We therefore compared our EA approach to simply generating random individuals from our DSL. This random search baseline solves an average of 6:17( 0:13)% of the training tasks, indicating that the EA is able to traverse the search space at least somewhat more eficiently. This is even more significant on the test tasks, where random-search is not able to solve even a single task. 5
We showed that our DSL+GE approach is viable for solving reasoning tasks. By designing a language for image-based logic and learning corresponding expressions from the training instances, we were able to score well in the ARC challenge. Ensuring a high expressiveness of the DSL, while at the same time limiting the complexity to allow tractable function evolution, appears to be the key problem. Finding the optimal set of functional atoms for the given domain may thus be subject to further research.
The ARC challenge’s dificulty illustrates the long way still to go until ML methods reach abstract reasoning capabilities comparable to the human mind’s. Acknowledgment This research has been funded by the Federal Ministry of Education and Research of Germany as part of the competence center for machine learning ML2R (01|18038A)