Why this Paper?
아무래도 이번에도 역시 공동과제를 위해 읽는 논문이며 ARC가 또 관련이 되어 있다. 확실히 ARC가 어렵다보니 다들 각자의 연구 방법으로 해결하고자 하는 것 같다.
Introduction
현재 AI 모델들은 소수의 데이터만으로는 제대로 된 추론을 수행하지 못한다. 이는 Abstraction and Reasoning Corpus(ARC)를 통해 확인할 수 있다. 각 퍼즐은 2~5개의 학습 예제만을 포함하고 있어, 대형 언어 모델(LLMs)에게도 어려운 문제를 만든다. 현재 AI와 인간의 성능 격차는 30.5%와 80%이다. 이런 차이는 AI 시스템이 인간 수준의 작업을 수행하기 위한 "핵심 기술"을 아직 갖추지 못했음을 나타낸다.
현재 다양한 모델이 ARC에서 테스트 되었다. LLMs는 올바른 관계를 설명할 수는 있지만 정확한 변환을 수행하지 못하는 경우가 많고 딥러닝 모델은 올바른 변환을 학습하는 데 실패하는 경향이 있다. 마지막으로 프로그램 유도 방식 & DSL 검색 방식은 개별 함수들을 효율적으로 좋바하여 정답을 도출하는 능력이 부족하다.
LLM은 모델이 커질수록 ARC 성능이 향상됨을 보이지만 훈련 비용이 높아 연구 그룹이 쉽게 접근하기 어렵다. 딥러닝 방식은 전반적으로 내부 표현의 노이즈로 인해 정확한 정답을 도출하는 데 어려움을 겪는다. 따라서 이 노이즈를 필터링 하는 과정이 필요하다. 더 구조화된 학습 방식과 저수준 언어를 적용한다면 해결이 가능할지도 모른다.
Learning Classifier Systems(LCS)는 진화적 규칙 기반 학습의 한 형태이며 데이터셋 분류와 같은 작업에 최적화되는 방식이다. LCS는 고차원 데이터에 적용할 수 없기 때문에 이미지 데이터에 많이 활용되지 않았다. 그러나 ARC 데이터는 입력 이미지가 최대 30 x 30 픽셀이기 때문에 ARC 문제에 LCS를 적용할 가능성이 있다.
이 연구의 목표는 LCS를 ARC 퍼즐의 해결책으로 활용할 수 있는지 여부를 확인하고 ARC 훈련 데이터셋에서 테스트하는 것이다. 배경에서는 ARC 및 LCS 연구를 설명하고 방법 및 결과에서는 LCS Solver를 평가하고 논의에서는 기존 ARC 해결 방법과 비교한 뒤, 개선 방안을 제안할 것이다.
Background
현재(논문이 작성된 시기)까지는 ARC 데이터셋에 LCS가 적용된 사례는 없다. 그러나 다양한 시도가 이루어졌고 그들 중 일부는 LCS와 유사한 특징을 공유한다.
Abstraction and Reasoning Corpus
ARC는 2019년에 도입된 AI 벤치마크 데이터셋이다. 현재의 대형 언어 모델(LLMs)도 해결하기 어려운 난제이며 총 900개의 퍼즐로 구성이 되어 있다. 그러나 입력-출력 예제가 매우 적어서 Few-Shot Learning 환경이라고도 부른다. 예제 퍼즐은 그림 1에서 확인할 수 있다. 훈련 셋, 평가 셋, 테스트 셋으로 구성이 되어있지만 그중에서 테스트 셋은 완전히 비공개로 되어있는 상태이다. 이런 테스트 셋에 대한 도전은 공식적인 대회를 통해 제출해야만 가능하다.
퍼즐을 올바르게 해결하기 위해서는 각 테스트 입력에 대해 3번의 병렬 시도 내에서 정확한 출력을 생성해야 한다. 이 예제들은 인간이 특정한 핵심 지식(prior knowledge)를 보유하고 있다면 3번의 시도 안에 정답을 명확하게 도출하도록 설계되어 있다. 즉, 인간과 유사한 추론 과정을 AI가 수행해야 한다. 필요한 사전 지식은 정해져 있지는 않지만 Chollet(개발자)는 인간의 핵심 지식 4가지를 표1에서 설명한다.
이 벤치마크는 Chollet이 정의한 일반 지능(다양한 작업에서 얼마나 효율적으로 새로운 기술을 습득할 수 있는지 측정하는 지표)을 평가하기 위해 설계되었다. 이 개념은 비공개 테스트 셋의 작업으로 확장된다. 즉, 이전 경험 없이도 새로운 작업을 수행할 수 있는 AI의 능력을 측정하는 방식이다. 이런 일반화된 추론 능력을 AI가 가진다면 다양한 응용 분야에서 활용될 가능성이 있다.
계속된 연구에 따르면 ARC의 전체 퍼즐중 80~88%가 인간이 해결 가능한 것으로 나타났지만 AI 모델이 ARC를 해결한 최고 성능은 30~50% 수준에 불과하다. 즉 인간과 AI 간의 성능차이가 아직 크고 ARC 데이터셋의 난이도가 높다는 것이 계속 입증되고 있다.
ARC에서 AI가 어려움을 겪는 원인은 다양하지만 우리는 뉴럴 네트워크 기반 해결법과 기호(symbolic) 기반 해결법이 직면한 문제점에 초점을 맞춘다. 뉴럴 네트워크 기반 모델은 잘못된 연관을 학습하거나 랜덤 픽셀을 해석하는 오류가 발생하며 기호 기반 모델은 객체의 위치가 어긋나거나 개념적 요소를 놓치는 문제가 발생한다. 흥미롭게도 이러한 오류들은 인간이 ARC 퍼즐을 해결할 때 나타나는 실수들과 유사하다.
현재까지 ARC 테스트 셋에서 최고 성능을 기록한 해결법은 30.5%의 정확도를 달성했다. 이 모델은 공개된 ARC 대회에 나온 것으로, 이전 Kaggle ARC 대회에서 높은 성능을 기록한 해결책들의 앙상블(Ensemble) 모델이다. 앙상블을 구성한은 모델 중 최고 성능을 보인 것은 21%의 정확도를 기록하고 있고 DSL 기반의 검색(search)방식을 이용하지만 개발자 스스로도 이 방법의 한계를 인정하고 있다. 즉, 일반화된 인공지능으로 발전할 가능성이 거의 없다는 것이다.
이외에도 DSL 기반의 해결법들은 여러 가지가 있지만 성공 여부는 다소 엇갈린다. 일반적으로 이런 해결법을은 함수 라이브러리와 검색 알고리즘으로 구성된다. 이중 일부 방법은 기존 함수 라이브러리의 구조를 개선하거나 새로운 함수 솔루션을 추가하는 방식으로 해결법을 확장하기도 한다. 대표적인 예시로 Witt el al. 의 연구에서는 비스산 모양이나 색상이 가진 객체를 찾고 각 객체별로 변형을 적용하는 방식을 사용했다.
또 다른 DSL 기반 접근법으로 Dreamcoder가 있다. 그러나 ARC 문제에 적용했을 때 성공적이지 않았다. 하지만 Dreamcoder는 자체 DSL을 확장할 수 있는 메커니즘을 가졌다. 뉴럴 네트워크를 이용하여 퍼즐을 해결하고 공통으로 사용되는 요소를 DSL에 추가하여 문제 해결에 활용한다. 그러나 ARC 실험에서는 초기 DSL이 단순할 경우 효과적인 방법을 찾지 못했다.
최근에는 LLM이 ARC 연구를 다시 활성화했다. 성공적인 결과를 기록한 사례도 등장했고 훈련 데이터 기준으로 10~50%의 정확도를 기록했다. 그러나 가장 효과적인 LLM 모델들은 온라인에서만 사용할 수 있어 테스트 셋에는 제출이 불가능하다. LLM은 광범위한 지식을 통합하는 데 매우 효과적이며,이는 DSL 솔루션이 직접 프로그래밍해야 하는 영역이다.
뉴럴 네트워크 기반 해결법의 경우 퍼즐당 훈련 데이터가 너무 적기 때문에 이를 보완하기 위해 인공 데이터셋을 활용한다. 현재까지 ARC를 테스트하는 뉴럴 네트워크는 CNN, 오토인코더, 예제 퍼즐의 컨텍스트를 추가적으로 학습하는 모델 등 다양하다. 한 가지 방법은 데이터 증강(Data Augmentation)을 수행하는 것이지만 최고 성능이 겨우 2%에 불과했다.
Learning Classifier Systems
LCS는 니치 기반(Niche-Based) 진화적 머신러닝 모델의 한 종류이다. 이들은 유전 알고리즘(Genetic Algorithm)을 이용하여 규칙의 집합을 생성하고 최적화한다. 이러한 특성 덕분에 LCS는 이질적인 데이터셋에 특히 효과적이다. 그러나 이미지 데이터에 적용된 사례는 제한적이며 대부분의 연구는 분류(Classification) 문제에 초점을 맞추고 있다. 기존 연구들에서는 이진 및 다중 클래스 분류 문제를 주로 해결하였다.
그러나 LCS는 입력 차원(Input Dimensions)이 너무 클 경우 학습 성능이 급격히 저하되는 문제점이 있다. 그렇기에 픽셀 값을 직접 입력으로 넣는 것은 비효율적이며, 이를 해결하기 위해 이미지의 내용을 요약할 수 있는 다양한 특징과 통계를 활용한다. 덕분에 회전, 밝기, 질감 변화에 더해 강건한 학습을 가능하게 할 수 있다.
또 다른 접근 방식은 넓은 범위의 픽셀 그룹이나 전체 이미지에서 파생된 특징을 분석하는 방법이다. lqbal et al. 의 연구에서는 이미지 전반에 걸쳐 적용되는 9가지 특징에 대해 선형 가중치를 학습하였고 siddique et al. 의 연구에서는 좌-우 뇌 반구 분할과 유사한 구조의 측면화 학습 모델을 사용하여 LCS를 딥러닝 모델의 출력값을 처리하는 데 활용했다.
현재까지 LCS 기반의 ARC 해결법으로 연구된 바가 없다. 그러나 저수준의 정보와 고수준의 정보를 동시에 분석하는 방식은 ARC의 문제 해결 방식과 유사하다. LCS는 매우 이질적인 문제를 해결하는 데 강점이 있으며 비교적 작은 데이터셋에서도 효과적으로 학습이 가능하다. 이런 특성은 ARC 문제를 해결하는 데 적합할 가능성이 있다.
Method
우리는 ARC 훈련 데이터셋의 대부분에서 2가지 LCS 모델을 테스트하고 여러번 반복 학습하며 비교했다. 각 모델은 전체 그리드를 보지 않고 그리드의 작은 부분만을 관찰하며 이를 기반으로 해당 위치의 출력 픽셀을 예측한다. 그리고 관찰하는 부분의 크기(Portion size), 학습 반복 횟수(Learning Iterations) 두 가지 변수를 다르게 설정하여 실험을 진행했다.
Dataset
ARC 훈련 데이터셋(Training Set)을 사용한다. 이 데이터셋은 공식 퍼즐 중 가장 간단한 셋이며 다른 연구에서도 많이 사용된다. 빈칸 채우기, 패턴 반사 등의 간단한 규칙부터 여러 단계를 거치는 복잡한 프로세스까지 포함된다. 우리는 400개의 퍼즐과 419개의 테스트 그리드로 구성된 훈련 셋만을 사용하였다.
LCS
연구에서는 scikit-XCS(XCS 알고리즘을 단일 단계 분류 문제에 맞게 재구현)과 scikit-eLCS(UCS의 기본버전을 구현)을 사용하였다. 이 모델들은 0~9의 정수로 이루어진 컬러 그리드 셀을 처리하며 Don't Care 연산자를 활용하여 특정 입력을 무시하는 방식으로 작동한다. 모델에 사용된 하이퍼파라미터는 표 2에서 확인할 수 있다.
입력 커널의 크기는 3 x 3, 5 x 5, 7 x 7을 사용했으며 학습 반복 횟수는 8000회, 16000회, 32000회, 64000회로 설정하여 수렴 속도를 분석했다. 각 퍼즐의 예제 그리드만 사용하여 퍼즐마다 하나의 모델을 학습한다. 그리고 학습된 모델은 각 퍼즐의 첫 번째 테스트 그리드에 대해 실행된다.
Algorithm
우리가 구현한 해결법은 Kernel LCS는 각 ARC 그리드를 슬라이딩 윈도우 방식으로 처리하며 학습 알고리즘으로 LCS를 사용하여 출력 그리드를 생성한다. 알고리즘 1은 슬라이딩 윈도우 방식으로 데이터를 생성하는 방법을 보여준다.
- 우선 각 입력 그리드에서 $n \times n$ 커널을 사용하여 데이터를 구성한다.
- 각 데이터 항목은 평탄화된 $n \times n$ 커널 그리드, 출력 픽셀(해당 커널의 중앙 픽셀에 대응되는 값)으로 구성된다.
- 커널이 입력 그리드를 슬라이딩하면서 각 $n \times n$ 영역을 1차원 배열로 변환하여 저장하고 중앙 픽셀의 출력값을 함께 기록한다.
- 입력 그리드는 패딩(0으로 채우기)를 추가하여 커널이 가장자리까지 도달할 수 있도록 처리한다.
ARC의 그리드 크기는 퍼즐마다 다르고, 같은 퍼즐 내에서도 입력-출력 쌍별로 다를 수 있다. LCS 규칙은 고정된 입력 크기를 요구하기 때문에 커널 기반 설계를 적용하여 입력-출력 크기 차이를 우회하고 퍼즐 크기 변동성 문제를 해결했다.
ARC 문제에서 최대 그리드 크기를 입력으로 사용할 경우 최대 900개의 입력 차원이 발생한다. 그러나 이는 대량의 입력을 처리할 수 있도록 설계되지 않은 모델에는 적합하지 않다. 그래서 우리는 입력과 출력의 크기가 동일한 퍼즐(262/400)만 실험에 사용했다.
그래도 다른 연구들과의 비교를 하기 위해 전체 400개 퍼즐을 기준으로 성능을 보고했다. ARC 문제를 해결하기 위한 전체 아키텍처 개요는 그림2에 나와 있으며, 각 LCS 모델은 각 테스트 그리드/퍼즐에 대해 하나의 정답만 출력한다.
Analysis
기본적으로 ARC 벤치마크에서는 3번의 병렬 시도 내에서 완전히 정답인 테스트 그리드의 개수만을 성능 평가 기준으로 삼는다. 이 방식은 부분적으로 정답인 경우의 진행 상황을 반영하지 못하는 문제가 있다. 픽셀의 정확도를 측정하면 부분 정답을 평가할 수 있지만 ARC 데이터셋에서는 신중하게 적용해야 한다. 왜냐하면 많은 퍼즐이 '0'이 배경색으로 사용되므로 모델이 단순히 픽셀을 0으로 예측하면 픽셀 정확도를 부풀릴 수 있기 때문이다.
따라서 입력 그리드와 출력 그리드 사이에서 변경된 픽셀만을 기준으로 정확도를 평가하는 방식을 제안한다. 또한 우리는 거의 정답(Close Solutions)인 퍼즐의 개수도 보고한다. 즉, 변경된 픽셀 중 최소 하나 이상을 정확하게 예측한 경우를 측정한다. 이 방식은 모델이 향후 개선되었을 때 어느 정도 성능을 보일 수 있는지 가늠하는 지표가 된다. 그렇다고 모든 퍼즐에 대해 평가하지는 않고 적어도 해결할 가능성이 있는 퍼즐에서의 성능을 평가한다.
Results
표 3에는 kernel LCS가 ARC 데이터셋에서 기록한 결과가 나와 있다. 가장 성능이 우수했던 시스템은 eLCS로 3 x 3 커널과 5 x 5 커널에서 400개의 퍼즐 중 19개를 정답으로 해결하는 데 성공했다. 모든 테스트에서 가장 우수한 성능을 보였기 때문에 앞으로 내용은 eLCS에 집중하여 분석할 예정이다. 3가지 해결법에서 총 25개의 퍼즐이 정답으로 해결되었다.
3 x 3 커널에서 5 x 5 커널로 증가시 성능은 하락되었으나 "거의 정답"인 퍼즐의 개수가 증가하는 경향을 보였다. 입력 크기를 늘리면 더 많은 정보를 학습할 수 있지만, 복잡도가 증가하면서 완벽한 정답을 도출하는 것은 어려워지는 것으로 보인다. 그리고 대부분의 경우 학습 반복 횟수를 늘리면 성능이 향상됨을 확인했다.
그림 3에서 확인할 수 있는 해결된 퍼즐을 통해, LCS가 기본적인 픽셀 변환 규칙을 학습할 수 있음을 확인할 수 있다. 대부분의 퍼즐은 단순한 규칙을 따른다. 예를 들어 :
- 퍼즐 "3618c87e"는 입력값의 최상단 위치에 회색 픽셀이 있으면 해당 위치에 파란 픽셀을 배치하는 규칙
- 퍼즐 "bb43febb"는 회색 박스의 경계와 내부를 구별해야 하는 규칙
그림 4에서는 5 x 5 커널의 장점이 나타난다. 5 x 5 커널에서는 해결이 가능했지만 3 x 3에서는 해결할 수 없었던 퍼즐이 존재했다. 예를 들어 :
- 퍼즐 "ce22a75a" 는 입력 위치에 회색 픽셀이 있으면 파란색 출력하는 규칙, 3 x 3이 실패
- 퍼즐 "c0f76784"는 5 x 5 커널이 추가적인 정보를 제공하면서 해결
그림 5에서는 LCS의 실패 사례가 나타난다. 대부분의 퍼즐에서 LCS는 3 x 3 커널의 한계를 넘어서 일반화하지 못하는 결과를 나타났다. 그러나 예외적으로 퍼즐 "0d3d703e"에서는 모델이 단 1개의 픽셀 차이로 오답을 냈다. 아마 조금 더 나은 표현 학습을 했다면 정답을 맞출 가능성이 높았을 것이다.
Discussion
문제를 해결하는 데 필요한 정보다 커널 창(kernel window)에 존재하는 경우 LCS는 필요한 모든 규칙을 학습이 가능하다. 그러나 커널 크기를 증가시킨다고 항상 더 많은 퍼즐을 해결할 수 있는 것은 아니다. 이론적으로는 가능하지만 실제로는 5 x 5커널을 넘어가면 해결된 퍼즐의 수가 감소하는 경향을 보였다. 이는 입력 차원이 많아지면서 LCS가 효과적으로 관리하기 어려워지기 때문으로 추측된다.
규칙이 지나치게 구체화되면서, 단순한 저차원 입력(3 x 3커널과 같은) 에서는 몇 단계만으로 일반화가 가능했던 문제들이 고차원 입력에서는 더 많은 학습 단계를 요구하기 때문이다. 이를 해결하기 위해서는 초기에는 저차원 입력으로 학습하고 만약 학습된 규칙들이 서로 충돌할 경우 입력 크기를 확장하는 방식이 제안될 수 있다.
한 가지 예외는 퍼즐 c0f76784(그림 4 참고)인데 이 퍼즐에서는 훈련 데이터 내에서 일관된 모양과 색상이 존재하기 때문에 더 큰 커널에서도 학습이 잘 이뤄진 것으로 추측된다. 반면 퍼즐 ce22a75a는 3 x 3 커널로 해결할 수 있어야 하지만 반복적으로 실패하는 문제를 보였다. 단순히 학습 반복 횟수를 늘리는 것만으로는 충분하지 않고 추가적인 개선 방법이 필요할 수 있다.
또한 일부 문제를 해결하기 위해서는 시스템이 "객체"의 개념을 이해할 수 있어야 한다. 예를 들어 그림 5의 퍼즐 05f2a901에서는 테스트 예제의 객체와 훈련 예제의 객체가 완전히 다르다. 즉, 단순하게 규칙 기반으로는 해결할 수 없고 추상화를 가능하게 하는 추가 구조가 필요하다. 이 경우 LCS는 객체를 삭제하는 것은 학습했지만 다시 생성하는 것은 학습하지 못했다. 입력과 출력에서 색상이 다를 경우(그림 5 왼쪽 상단 퍼즐 참고), 입력과 출력의 크기가 다를 경우 해결하지 못하는 한계를 보였다.
Conclusion
우리는 LCS가 ARC 문제 해결에 기여할 수 있음을 입증하기 위해 간단한 해결법(solver)를 구현하고 테스트했다. 이번 연구에서 제안한 커널 LCS 방법은 적절한 정보가 주어지면 LCS가 ARC 퍼즐을 해결할 수 있음을 보여주었다. 이를 위해서는 학습자가 너무 많은 입력 차원을 갖지 않도록 설계해야 한다.
LCS 접근법은 구체적인 규칙을 학습할 수 있고 잘못된 패턴을 학습하는 문제를 방지할 수 있다는 점에서 장점이 있다. LCS 자체의 개선도 가능하며 추상화 과정을 자동화하는 다른 방법과 결합하여 더욱 확장될 가능성이 존재한다.
우리는 ARC에서 LCS를 활용하는 연구가 유망한 결과를 가졍로 가능성이 크다고 결론지었다. 또한 LCS 기반 연구가 더 활발히 진행될 수 있도록 관심을 유도하는 것이 중요하다.
https://dl.acm.org/doi/10.1145/3638530.3664157
Learning Classifier Systems as a Solver for the Abstraction and Reasoning Corpus | Proceedings of the Genetic and Evolutionary C
Publication History Published: 01 August 2024
dl.acm.org