Graphs Constraints and Search for the Abstraction and Reasoning Corpus Yudong Xu1Elias B. Khalil1 2Scott Sanner1 1Department of Mechanical Industrial Engineering University of Toronto

2025-05-06 0 0 3.27MB 9 页 10玖币

侵权投诉

Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus

Yudong Xu,1Elias B. Khalil,1, 2 Scott Sanner1

1Department of Mechanical & Industrial Engineering, University of Toronto

2Scale AI Research Chair in Data-Driven Algorithms for Modern Supply Chains

wil.xu@mail.utoronto.ca, khalil@mie.utoronto.ca, ssanner@mie.utoronto.ca

Abstract

The Abstraction and Reasoning Corpus (ARC) aims at bench-

marking the performance of general artiﬁcial intelligence al-

gorithms. The ARC’s focus on broad generalization and few-

shot learning has made it difﬁcult to solve using pure machine

learning. A more promising approach has been to perform

program synthesis within an appropriately designed Domain

Speciﬁc Language (DSL). However, these too have seen lim-

ited success. We propose Abstract Reasoning with Graph Ab-

stractions (ARGA), a new object-centric framework that ﬁrst

represents images using graphs and then performs a search

for a correct program in a DSL that is based on the abstracted

graph space. The complexity of this combinatorial search is

tamed through the use of constraint acquisition, state hash-

ing, and Tabu search. An extensive set of experiments demon-

strates the promise of ARGA in tackling some of the compli-

cated object-centric tasks of the ARC rather efﬁciently, pro-

ducing programs that are correct and easy to understand.

In an attempt to better measure the gap between machine

and human learning, the Abstraction and Reasoning Corpus

(ARC) was created by Chollet in 2019. The dataset is a col-

lection of 1000 image-based reasoning tasks, where each

task asks for an output image given an input. To “learn” a

procedure that produces said output, each task comes with

2–5 input-output image pairs as training instances; these

training inputs are different from the actual test input, but

can be solved by the same (unknown) procedure. Some ex-

amples are shown in Figure 1. A competition with over

900 teams was hosted on Kaggle to solve the ARC (Kaggle

2020). Despite a massive effort, the solutions only achieved

20% accuracy on the hidden test set, at best. In fact, the

ﬁrst-place solution could not solve two of the three exam-

ples shown in Figure 1 despite their simplicity to a human.

Recognizing objects, actions performed on them, and re-

lationships between them makes up a large portion of hu-

man cognition core systems (Spelke and Kinzler 2007). The

ARC embodies this notion in its tasks. In fact, Acquaviva

et al. (2021) found that when humans attempt to solve ARC

tasks through language, half of the phrases they use relate

to object detection. Therefore, an object-centric approach to

solving the ARC is highly promising. Surprisingly, this key

insight is yet to be leveraged.

Figure 1: Sample ARC Tasks. Three tasks (each two con-

secutive columns) are shown. For a given task, each row

contains one example input-output pair. The top three rows

contain the “training” instances and the bottom row contains

the “test” instance. The goal is to use the training instances

to solve the test instance. The left task (“object recoloring”)

requires recoloring the size-6 grey objects to red and other

grey objects to blue. The middle task (“object movement”)

requires moving the red columns up until they hit the blue

object. The right task (“object augmentation”) requires ex-

tending the size-1 objects directly above, below or to the

sides of the green object towards it until they make contact.

ARGA: Abstract Reasoning with Graph

Abstractions

Toward this goal, we propose Abstract Reasoning with

Graph Abstractions (ARGA), an object-centric framework

for solving ARC tasks. Our design rationale is to build

a computationally efﬁcient, extensible, object-aware ARC

solver through careful integration of the following:

–Representation: Enabling object awareness requires a

move from treating the input as pixels towards a graph

of objects with spatial or other relations. We design a va-

riety of such graph abstractions to cater to the diversity

of the ARC and its different deﬁnitions of objects.

–Structure: Grounded in ﬁrst-order logic, our graph-

arXiv:2210.09880v2 [cs.AI] 2 Dec 2022

Figure 2: Illustration of ARGA’s constraint-guided search. Note that a reconstructed 2D image is used at each node for better

visualization. Nodes in the actual search tree consists a set of abstracted graphs.

based DSL makes it possible to deﬁne complex but in-

terpretable solution programs for tasks of the ARC. This

is in contrast to pure neural network-type approaches that

attempt to map input to output in an often black-box fash-

ion.

–Search: With the representation and DSL in place, we

opt for a complete tree search algorithm. Given a task,

the search seeks a program in the DSL that produces the

correct outputs for each of the task’s training examples.

Whenever a correct program for a task exists in our DSL,

the search can ﬁnd it given sufﬁcient time.

–Constraints: Leveraging the observation that (solved)

training examples not only tell us what a correct program

does but also what it should not do (e.g., in Fig. 1 (left),

objects should not move), we use constraint acquisition

to simplify our combinatorial search space. Constraints

are expressed in the very same graph DSL and may be

acquired by an arbitrary algorithm.

Fig. 2 illustrates the DSL, Search, and Constraints compo-

nents of ARGA; Fig. 4 illustrates the Representation. With

ARGA, we hope to provide AI researchers who are inter-

ested in the ARC and similar few-shot reasoning situations

with the ﬁrst such system upon which they can build and ex-

plore the capabilities of graph and search-based reasoning.

Our implementation is available on GitHub1.

Because object-oriented abstraction and reasoning are

major failure modes of state-of-the-art ARC solvers, we de-

ﬁne criteria to select a subset of object-oriented ARC tasks

as a testbed for the evaluation of our methods in compari-

son to other top solvers. The 160 tasks in question span a

wide range of challenging problems that can be categorized

as object recoloring, object movement, and object augmen-

tation. We show how ARGA’s design and performance are

favorable in the following ways:

–Extensibility and Modularity: Every component of

ARGA can be extended almost independently to target

additional ARC tasks or optimize performance: novel

graph abstractions can be added, additional object ﬁlters

1https://github.com/khalil-research/ARGA-AAAI23

and transformations can be appended to the DSL, new

search strategies can be tested, and faster constraint ac-

quisition algorithms may seamlessly replace ours.

–Computational Efﬁciency: Our DSL contains a num-

ber of object-based selection ﬁlters as well as transfor-

mations (e.g., recoloring, moving, etc.). Because these

can be composed together to form a candidate program

for an ARC task, the resulting search space is combina-

torially large. Nonetheless, through experiments on 160

object-based ARC tasks, we show that when ARGA ﬁnds

a solution, it does so by exploring a minute number of

possible solutions, effectively three orders of magnitude

fewer than the winner of the Kaggle competition.

–Effectiveness: Our current DSL includes only 4 base

ﬁlters and 11 transformations. Yet, we solve 57 of 160

tasks, only slightly behind the Kaggle winner’s 64 of 160.

The latter includes a much larger body of transformations

that were obtained by examining many more ARC tasks.

System overview

We propose a two-stage framework that takes an object-

centric approach to solving an ARC task. First, the graph ab-

straction stage inspired by work on Go (Graepel et al. 2001),

where the 2D grid images are mapped to (multiple) undi-

rected graph representations that capture information about

the objects in the images at a higher abstracted level. Sec-

ond, the solution synthesis stage, where a constraint-guided

search is used to formulate the series of operations to be ap-

plied to the abstracted graphs that will lead to a solution. The

space of possible operations is deﬁned by an ARGA-speciﬁc

relational Domain Speciﬁc Language (DSL).

Since the DSL deﬁnes operations on the abstracted

graphs, we will ﬁrst describe the graph abstraction stage and

formally deﬁne the structure of the abstracted graphs. Then,

the DSL will be deﬁned in detail. Finally, the solution syn-

thesis stage will be discussed.

Graph Abstraction

Graph abstraction allows us to search for a solution at a

macroscopic level. In other words, we are modifying groups

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Graphs,Constraints,andSearchfortheAbstractionandReasoningCorpusYudongXu,1EliasB.Khalil,1,2ScottSanner11DepartmentofMechanical&IndustrialEngineering,UniversityofToronto2ScaleAIResearchChairinData-DrivenAlgorithmsforModernSupplyChainswil.xu@mail.utoronto.ca,khalil@mie.utoronto.ca,ssanner@mie.utoronto....

展开>> 收起<<

Graphs Constraints and Search for the Abstraction and Reasoning Corpus Yudong Xu1Elias B. Khalil1 2Scott Sanner1 1Department of Mechanical Industrial Engineering University of Toronto.pdf

共9页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Graphs Constraints and Search for the Abstraction and Reasoning Corpus Yudong Xu1Elias B. Khalil1 2Scott Sanner1 1Department of Mechanical Industrial Engineering University of Toronto

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: