논문/논문 정리

[논문 정리] Solving Abstract Reasoning Tasks with Grammatical Evolution

bengal3636 2025. 2. 13. 16:05

Why This Paper?

이번 논문은 유비 추론 문제에 진화 알고리즘을 적용한 연구이다. 앞에서 본 것들과 비슷하게 ARC를 해결하는 방법을 가지고 있다.

Introduction

AI 연구가 빠르게 발전하고 있지만 AI의 지능을 엄격하게 정의하고 측정하는 문제는 여전히 난제로 남아 있다. 이러한 문제를 해결하기 위해 Abstraction and Reasoning Corpus(ARC)가 발표되었으며, 이에 대한 Kaggle 챌린지도 함께 진행되었다. ARC는 수백 개의 이미지 기반 논리 문제를 포함하고 있으며(그림 1 참고) 인간의 도움 없이 AI가 논리적 추론을 수행하는 것을 목표로 한다.

 

이를 해결하기 위해서는 극소수의 예제에서 과제의 논리를 학습해야 하며, 이는 인간에게는 쉽지만 기계에게는 어려운 과제로 남아 있다.본 연구에서는 도메인 특화 언어(Domain-Specific Language, DSL)을 기반으로 한 접근 방식을 제안하며 이 DSL 표현은 문법적 진화(Grammatical Evolution, GE)를 통해 생성된다. 이 방법을 통해 우리는 ARC 챌린지에서 900개 이상의 팀 중 28위를 기록하는 성과를 거두었다.

Problem Statement

ARC 챌린지는 참가자들이 모델을 개발하여 특정 작업 $D_i$를 해결하도록 요구한다. $D_i$는 전체 작업 집합 $\mathcal{D} = \{D_1,\dots,D_M\}$ 중 하나에 해당된다. 각 $D_i$는 이미지 추론 작업으로 구성되며 $m_i$개의 학습용 이미지 쌍 $\{(x^k,y^k)\}$과 $n_i$개의 테스트용 이미지 쌍 $\{(x^l,y^l)\}$이 포함된다. 일반적으로 학습용은 3개 정도, 테스트용은 1개 정도이다.

 

그림 1. 대표적인 ARC 작업 예시 (a) 단일 색상으로 된 가장 작은 직사각형 잘라내기 (b) 빨간색 픽셀에 의해 지정된 방향으로 선을 그림 (c) 패턴을 매칭한 후 필요에 따라 크기를 확대하거나 색상을 변경함

 

이미지는 최대 10가지 색상을 가지며, 각 차원의 크기는 1~30 픽셀 범위 내에서 변동한다. 입력 이미지에서 출력 이미지로 매핑하는 함수 $f$는 작업마다 다르며, 추상적인 특징을 기반으로 하는 경우가 많다.(그림 1 참고). 각 작업 $D_i$에 대해 모델은 $f_i : (x^k, y^k) \in D_i$를 찾아야 한다. 즉, 모든 입력 이미지가 예상 출력으로 올바르게 매핑되도록 해야 한다 : $ \forall (x^l, y^l) \in D_i : f_i(x^l) = y^l$. 참가자들은 총 $M = 400$ 개의 훈련 작업에 접근할 수 있다. 그러나 최종 점수는 공개되지 않은 테스트 셋에서 평가된다.

Reasoning Approach

우리는 함수 $f$가 일련의 기본 이미지 변환(Basic Image Transformations)의 순서로 분해될 수 있다고 가정한다. 이를 위해 변환 시퀀스를 정의하는 맞춤형 도메인 특화 언어(DSL)을 개발했다. 이 DSL을 이용하여 표현 공간을 탐색하는 진화 알고리즘(EA, Evolutionary Algorithm)을 적용했다. 먼저 이 언어의 세부 사항을 설명한 후, 진화 알고리즘을 활용하여 DSL에서 ARC 문제를 해결하는 방법을 소개한다.

 

도메인 특화 언어(Domain-Specific Language, DSL) 첫 번째로 우리는 20개의 랜덤한 ARC 훈련 작업을 수동으로 해결하는 solver를 구현해다. 거기서 반복적으로 등장하는 이미지 변환 연산을 식별하고 이를 기반으로 DSL을 구축했다.

 

$\mathcal{X} = \bigcup_{w,h \geq 1}C^{w \times h}$은 색상 집합 $C$에서 정의된 직사각형 이미지를 나타내며, $\mathcal{X}^*$는 이미지의 정렬된 리스트로, 우리는 이를 레이어(Layers)라고 부른다. 우리의 DSL은 바커스-나우르 표기법(Backus Naur Form, BNF)으로 정의된 문맥 자유 문법(Context-Free Grammar, CFG)이다. 이때, 비종결(non-terminal) 심볼들은 특정 기능을 수행하는 함수 집합을 의미하며 아래와 같이 분류된다.

  1. 이미지를 변환하는 연산 ($T = \mathcal{X}^{\mathcal{X}}$)
  2. 이미지를 여러 레이어로 분해하는 연산 ($S = (\mathcal{X}^*)^{\mathcal{X}}$)
  3. 여러 레이어를 하나의 이미지로 결합하는 연산 ($J = \mathcal{X}^{\mathcal{X}^*}$)
  4. 특정 레이어를 조작하는 연산 ($L = (\mathcal{X}^*)^{\mathcal{X}^*}$)

그림 2는 DSL 함수 유형을 시각적으로 표현한 그림을 제공한다.

 

그림 2. DSL의 함수 유형, 각 유형별로 예제 함수가 포함되어 있다

 

우리의 기본(Atomic) 함수들은 여러가지 이미지 조작 기능을 포함한다. 이동(Translation), 회전(Rotation), 잘라내기(Cropping), 레이어 추출(Extracting a Layer), 레이어 정렬(Sorting by Criteria), 이미지를 여러 레이어로 분리(Splitting into Layers), 레이어 병합(Merging Layers Together). 추가적인 유연성을 위해 map과 같은 고차 함수(Higher-Order Function)도 허용한다(map 연산자는 T타입 함수를 L타입 함수로 변환한다). 우리의 DSL 문법 구조는 모든 표현식을 최종적으로 T타입 로직을 가지도록 보장한다. 즉, 하나의 입력 이미지를 받아 변환된 출력 이미지로 매핑하는 방식으로 동작한다. 우리는 이 방식으로 일부 ARC 문제를 해결하는 solver를 찾을 수 있었으며 그림 3에 예제가 나와 있다.

 

문법적 진화(Grammatical Evolution, GE) 우리는 문법적 진화(GE)를 이용하여 DSL 표현을 생성하고 최종적으로 ARC문제를 해결할 solver를 찾는다. 표현식을 생성하는 과정에서 표준 모듈로 기반 매핑(Modulo-Based Mapping) 기법을 사용하여 DSL 구문 트리로 변환된 코돈(Codon) 시퀀스를 매핑하여 이미지 변환함수 $\widetilde{f}$를 획득한다. 이후 균등 변이(Uniform Mutation) 및 1-포인트교차(1-Point Crossover)를 적용하여 새로운 개체를 생성한다. 다음 세대의 부모는 토너먼트 선택 방식을 사용하여 부모 개체와 자식 개체 간 성능을 비교하여 선택한다. 이때 손실 함수는 모든 학습 샘플에 대해 예측 결과 $f(x)$와 실제 정답 $y$ 사이의 거리로 정의된다.

$$\mathcal{L}(f|D_i) = \frac{1}{m_i}\sum_{k=1}^{m_i}d_\text{img}(f(x^k),y^k)$$

여기서 이미지의 거리 $d_\text{img}(f(x^k),y^k)$는 아래처럼 계산된다.

$$d_\text{img}(x,y) = \begin{cases}
\sum_i 1_{\{x_i \neq y_i\}} / (u_xv_x) & \text{ if }\; u_x=u_y \;\text{and}\; v_x = v_y \\
1 + ||\phi (x) - \phi (y)||_2 & \text{ else }
\end{cases}$$

  • $u_x, v_x$ : 이미지 $x$의 너비(width)와 높이(height)
  • $1_{\{x_i \neq y_i\}}$ : 픽셀 $x_i$와 $y_i$가 다를 경우 1, 같을 경우 0을 반환하는 지표
  • $\phi (x)$ : 이미지 $x$의 색상 히스토그램

$f$가 최적의 솔루션이라면 모든 예측 값이 기대 정답과 정확히 일치해야 한다. 즉 $\mathcal{L}(f|D_i) = 0$이면 ARC 문제를 완벽하게 해결한 것이며 , 이를 조기 종료 기준으로 사용할 수 있다.

Experimental Results

챌린지의 평가 절차에 따라 정확도(ACC)는 올바르게 해결된 작업의 비율로 정의된다: $ACC = M^{-1}\sum_{i =1}^{M} \prod^{n_i}_{l=1} 1_{\{f_i(\hat{x}^l) = \hat{y}^l\}}$. 여기서 $f_i$는 훈련 후에 우리가 도출한 솔루션이며 $D_i$는 주어진 ARC 작업이다. 또한 그리드 검색을 수행하여 인구 크기, 돌연변이율, 변이 강도 등에 대한 최적의 하이퍼파라미터를 찾았다. GE 방식은 무작위성이 있기 때문에 40개의 서로 다른 시드를 이용하여 평균 결과를 표준 편차와 함께 측정했다.

 

ARC의 400개의 훈련 데이터에서 테스트한 결과 평균 정확도는 7.68%($\pm$0.61%)로 측정되었다. 테스트 셋에서 진행한 결과에서는 3%의 정확도가 측정되었다. 이는 낮은 수치이지만 900개 이상의 팀 중 상위 30위 내에 들었기 때문에 이 챌린지가 쉽지 않음을 나타낸다.

 

우리는 GE를 무작위 탐색과 비교해서 평가를 추가로 진행했다. 무작위 탐색의 경우 훈련 데이터셋의 6.17%의 정확도를 보였으며 GE 방식이 최소환 무작위 탐색보다는 효율적으로 수행한다는 점을 증명하였다. 이 차이는 복잡한 작업(complex task)에서 더욱 두드러지는 결과가 나타났다.

Conclusion

우리는 DSL + GE 방식이 논리 추론 문제를 해결하는 데 유효함을 증명했다. DSL의 표현력을 높이는 동시에 함수의 진화를 계산적으로 복잡도를 제한하는 것이 핵심적인 문제로 보인다. 향후 연구에서는 최적의 함수 원자(atomic functions) 집합을 찾는 것이 고려될 수 있다.

 

또한 ARC 챌린지의 높은 난이도는 ML 방법이 인간의 사고 수준과 비슷한 수준의 추론 능력을 갖추기까지 여전히 갈 길이 멀다는 점을 시사한다.

느낀점

앞서 읽었던 논문들은 ARC 문제를 높은 비율로 해결했기 때문에, 이 논문도 비슷한 성과를 거뒀을 것이라고 예상했다. 하지만 정확도가 10%도 되지 않는다는 점에서 놀랐다. 아무래도 이 논문이 2020년에 발표된 연구이기 때문에, 당시 기준에서는 이 정도 성과도 상당히 우수한 결과였을 것이라 생각된다. 동시에, ARC 문제가 얼마나 어려운지 이제서야 실감이 나기 시작했다. 만약 ARC를 거의 완벽하게 해결할 수 있는 AI가 등장한다면, 그보다 더 어려운, 즉 더 복잡한 추론 능력을 요구하는 새로운 벤치마크가 등장할 것 같다. AI가 발전할수록 "지능"을 평가하는 기준도 계속해서 높아지는 과정이 반복되지 않을까 하는 생각이 든다.

 

https://ceur-ws.org/Vol-2738/LWDA2020_paper_8.pdf