논문/논문 정리

[논문 정리] Program Synthesis using Inductive Logic Programming for the Abstraction and Reasoning Corpus

bengal3636 2025. 4. 2. 16:38

Introduction

머신러닝과 딥러닝의 발전으로 AI의 성능은 사람의 성능을 능가했다. 그러나 특정 task에만 집중되어 있는 task-specific이기 때문에 다른 task에 적용할 경우 실패하는 경향이 있다.

 

LLMs의 경우 기계와 사람 지능간의 차이를 좁혔지만 여전히 굉장히 많은 양의 데이터를 필요로 하고 추론 능력이 부족하다는 단점이 존재한다.

 

ARC 챌린지는 Francois Chollet가 범용 인공지능을 측정하기 위해 만든 벤치마크이다. 2019년에 나왔지만 아직까지도 어려운 챌린지이며 LLMs도 풀지 못했다. 400개의 다른 특징을 요구하는 테스트 셋이 있고 심지어는 공개되지 않은 private한 200개의 테스트 셋도 추가로 존재한다.

 

Objectness는 인간의 핵심 사전 지식 중 하나이다. 객체 중심 추상화는 인간에게 매우 중요한 객체 인식을 가능하게 하며 이는 당연히 ARC 과제를 해결할 때 핵심이 된다.

 

Inductive Logic Programming(ILP)는 머신러닝 방법 중에 하나이지만 아직까지 ARC 챌린지에는 적용되지 않았다. 이는 Program synthesis(프로그램 합성) 기법 중 하나이며 few training examples에서 학습이 가능하다고 알려져 있다.

 

우리는 ILP를 이용한 프로그램 합성 시스템을 만들어 Logic의 관계를 찾도록 학습시켰다. 그리고 무작위로 5개의 샘플을 뽑아 우리의 시스템에 적용시켜 보았다.

그림 1. ARC 훈련 데이터셋의 예시

Object centric Abstractions and Representations

객체 중심 추상화는 객체 사이의 관계들에 집중하는 것을 도와준다. 그러나 객체 측면에서 동일한 이미지를 해석하는 방법은 여러 가지가 있을 수 있으므로 겹치는 해석들을 모두 유지한다.

Objects and Relations between Objects

우리는 객체들과 그 관계로 이루어진 간단한 DSL을 구성했다.

객체 : Point, Line, Rectangle

관계 : LineFromPoint, Translate, Copy, PointStraightPathTo

표 1(객체)과 표 2(관계)

 

Multiple Representations

객체 중심 방법을 이용하면 여러 개의 오브젝트들과 배경 색깔로 구성할 수 있다. 목표 이미지를 만들 때도 배경을 먼저 칠하고 그 뒤에 객체들을 그리는 방식을 이용하면 편리하다.

 

이미지는 하나의 사각형으로 인식할 수도 있지만 4개의 점과 선으로 인식도 가능하다. 어떤 논리가 적용될지 모르고 어떤 관계가 적용될지 모르기 때문에 유효한 출력 그리드를 생성할 때까지 객체와 관계의 여러 가지 혼합 표현을 이용하여 작업을 진행한다. 만약 완성되었을 경우, 그대로 사용해도 되고 길이가 제일 짧은 것을 사용해도 된다.

ILP

ILP는 논리 기반 머신러닝이다. 목표는 주어진 학습 데이터와 지식을 일반화하는 가설을 유도하는 것이다. 우리가 사용하는 DSL은 객체와 관계로 이루어져 있다.

 

다른 형태의 ML과 목표는 비슷하지만 차이점이 존재한다. ML은 데이터를 표현하기 위해 벡터/텐서를 사용하지만 ILP는 논리 프로그램을 사용하며 ML이 함수를 학습하는 반면에 ILP는 관계를 학습한다.

 

ILP의 문제점은 거대한 가상 공간을 찾는 효율성이다. top-down과 bottom-up 방법이 있는데 우리는 top-down 방식을 이번 시스템에 사용한다.

 

거대한 프로그램을 ILP로 학습하는 것은 가상 공간이 너무 크기 때문에 어려운 일이다. 이것을 해결하기 위해 여러 방식들이 시도되고 있다.

Divide-and-conquer

divide-and-conquer 방식은 예제를 하위 집합으로 나누고 각 하위 집합에 대한 프로그램을 검색한다. 우리는 이 방식을 사용하지만 예제에 적용하지는 않고 예제 안에 있는 객체에 적용했다.

Program Synthesis using ILP

ILP는 일반적으로 개념 학습 용도로 사용되지만 논리 프로그램 구축이 가능하기 때문에 프로그램 합성도 수행이 가능하다. 이를 확장하여 논리 프로그램과 결합해 순차적으로 객체를 생성하는 더 큰 프로그램을 구축하여 목표를 만든다.

 

PointStraightPathTo를 제외한 모든 관계는 첫 번째 객체가 주어지면 객체를 생성할 수 있다. 즉, 관계를 이용하여 객체를 생성한다. 각 관계는 ILP에 의해 학습된 논리 프로그램에 의해 구체적으로 정의되며, 이 프로그램은 관계의 조건과 결과를 기술하여 명확한 객체 생성을 가능하게 한다.

 

아래는 예시이다.

그림 3. Line_from_point를 수직으로 적용한 예시

 

이 논리프로그램은 2개의 선을 모호하지 않게 생성이 가능하고, 점들이 그리드의 가장자리에 있어 한 방향의 선으로만 커질 수 있으므로 방향 변수는 필요하지 않다.

 

프로그램이 더 짧다면 더 많은 선을 생성할수 있었을 것이다. 아래는 그 예시이다.

그림 4. 수직 방향의 조건을 삭제한 예시

 

이렇게 ILP를 통해 논리 프로그램을 얻음으로써 우리는 객체를 생성하는 프로그램을 구성한다.

System Overview

Objects and Relations Retrieval

시스템은 먼저 각 ARC 과제의 입력 및 출력 Grid로부터 DSL에 정의된 객체(Object)들을 추출한다. 위에서 말했던 대로 동일한 이미지를 해석하는 방법은 여러 가지가 있을 수 있으므로 겹치는 해석들을 모두 유지한다. 우리가 정의한 DSL을 이용하여 객체들 사이의 관계를 탐색한다: 

  • 입력-입력 관계 : 입력 Grid 내 객체 간 관계
  • 출력-출력 관계 : 출력 Grid 내 객체 간 관계
  • 입력-출력 관계 : 입력과 출력 객체 사이의 관계

ILP calls

우리는 전에서 찾은 관계를 정의하는 논리 프로그램을 생성하기 위해 ILP를 호출한다. 이 과정은 탐색 공간을 줄여주는 역할도 한다. 우리는 입력의 정보를 이용하여 출력을 만들기 위해 입력-출력 관계를 활용한다. 출력 객체가 생성되면, 출력-출력 관계는 기존 출력 객체로부터 다른 출력 객체를 만드는 역할을 한다.

 

각 ILP 호출 후 출력 그리드가 업데이트되면서 생성된 객체와 관계는 새로운 입력 정보처럼 간주된다. 다음 ILP 호출 시에는 앞의 정보를 포함하여 확장된 정보를 기반으로 새로운 출력을 생성하며 점점 목표에 가까워지도록 유도한다.

 

Candidate Generation

Horn Clause의 Body에 들어갈 수 있는 후보 항목들은 전에 추출한 객체와 관계뿐만 아니라 논리 연산자도 포함된다:

Equal(X,...), GreaterThan(X, ...), LowerThan(X,...), Member(X,...), aX + b

 

우리는 타입을 명확하게 가진 객체와 관계를 사용하기 때문에 그 타입에 관련된 후보들만 생성하면 된다. 예를 들어 LineFromPoint의 관계를 정의하는 논리 프로그램을 만든다고 하자. 첫 번째 변수인 Point를 구성하기 위해  point 또는 point의 속성과 연관된 후보를 생성할 것이다. 그 다음으로는 길이, 방향, 진행방향과 같은 속성 변수를 처리하게 된다.

 

Positive and Negative examples

ILP 시스템은 논리 프로그램을 학습하기 위해  positive example과 negative example이 필요하지만 ARC에는 positive example들로만 이루어져 있다. 그래서 우리는 negative example을 만들 방법을 찾았다. 논리 프로그램이 생성한 객체 중 훈련 데이터에 실제로 존재하는 객체는 positive example, 존재하지 않는 객체는 negative example로 간주한다.

 

예를 들어 그림 3번이 정답이라고 할 때 그림 4번의 두 개의 수직선은 positive example이 되고 나머지는 negative example이 된다. 

 

Unification between Training examples

ILP 호출은 각 관계와 과제의 모든 훈련 예제에서 이뤄진다. 이때 ILP 시스템은 2개 이상의 훈련 예제에서 공통으로 작동하는 추상적이고 일반화된 프로그램을 생성하도록 제한된다.

 

훈련 예제는 2개가 넘는 경우도 많을텐데 왜 최소 2개만 커버할까?

=> 전부 커버할 경우 오히려 일반화가 실패했던 경우가 있기 때문

그림 5. 2개의 수직 방향과 2개의 수평 방향 예제를 포함한 ARC 문제

 

그림 5에서는 점에서 시작해 반대편 경계까지 선을 그리고, 그 선을 선 방향의 수직 방향으로 반복적으로 이동시켜서 그리드를 채우는 방식의 과제가 제시된다. 4개의 예제를 전부 만족시키는 솔루션을 찾는 것이 2개의 예제의 경우보다 더 복잡한 프로그램을 요구한다.

세로 방향 2개의 예시(왼쪽) 가로 방향 2개의 예시(오른쪽)

 

왼쪽은 앞의 2개(세로 방향)의 예시를 이용한 논리 프로그램이다. 이 경우에는 성공했지만

오른쪽은 뒤의 2개(가로 방향)의 예시를 이용한 논리 프로그램이다. 이 경우에는 실패했다.

 

그러나 테스트가 더 길고 훈련 예제보다 많은 이동을 요구할 경우 프로그램이 제대로 작동하지 않을 것이다. 이것을 해결하기 위해서는 조건이 있는 반복, 재귀 등을 사용해야 하지만 이는 향후 연구의 범위이다.

Rules, Grid states and Search

ILP 호출은 빈 그리드에서 시작한다. 첫 번째 ILP 호출은 객체를 생성하는 관계를 정의하는 규칙을 하나 만들며 이를 통해 그리드 상태를 업데이트 한다. 모든 훈련 예제와 테스트 예제에 대해 수행되며, 이후의 호출은 업데이트된 그리드를 바탕으로 이어진다.

 

우리의 목표는 빈 그리드에서 출력 그리드를 만들 수 있는 시퀀스를 찾는 것이다. 만약 동시에 두 개 이상의 예제에서 일반화된 논리 구조를 갖고 테스트 예제에서 유효한 출력(정답이 아닐지라도)을 만들면 최종 프로그램으로 간주한다.

 

단, 모순되는 명령을 포함하는 프로그램은 중간에 폐기된다.

Deductive Search

그림 7의 경우 거꾸로 접근하는 것이 더 편해보이지만, 그렇게 할 경우 테스트에 대한 출력을 생성할 수 없다. 그렇기에 우리는 연역적(deductive) 탐색을 사용한다.

 

같은 논리 프로그램이라도 적용 순서에 따라 그리드에서 커버하는 면적이 달라질 수 있으며, 이러한 절차적 특성은 여러 프로그램을 연속적으로 적용할 때 더욱 중요해진다.

 

따라서 테스트 예제를 풀 때는, 전체 논리 프로그램을 가장 많은 면적을 덮도록 적용하는 방향으로 연역적 탐색을 수행한다. 왜냐하면 최종 프로그램은 훈련 예제의 출력 그리드를 모두 덮을 수 있어야 하며, 이와 같은 방식으로 적용하면 테스트 출력 역시 전부 커버할 수 있을 가능성이 높기 때문이다.

 

https://arxiv.org/abs/2405.06399

 

Program Synthesis using Inductive Logic Programming for the Abstraction and Reasoning Corpus

The Abstraction and Reasoning Corpus (ARC) is a general artificial intelligence benchmark that is currently unsolvable by any Machine Learning method, including Large Language Models (LLMs). It demands strong generalization and reasoning capabilities which

arxiv.org