FunSearch(함수 공간 탐색의 약자)은 Google DeepMind가 개발한 인공지능 방법으로, 수학적 및 알고리즘적 문제를 해결하는 컴퓨터 프로그램을 발견하기 위해 설계되었다. 이 방법은 대규모 언어 모델과 자동 평가기, 진화적 탐색 절차를 결합하여 후보 프로그램을 생성하고 점수를 매긴 뒤, 우수한 성능의 프로그램을 사용해 새로운 후보를 생성한다. 이 시스템은 2023년에 발표되었으며, Nature 저널에 논문이 게재되었고, 극단 조합론 및 온라인 빈 포장 문제에 적용되었다.
FunSearch는 대규모 언어 모델이 발견 작업에 사용되는 방식을 전환한다. 직접 답변을 생성하는 대신, 문제를 컴퓨터 프로그램에 대한 탐색으로 구성하여 모델이 제안한 코드를 엄격히 테스트할 수 있게 한다. 이 접근 방식은 Generative AI에서 사용되는 모델과 같은 생성 능력을 활용하면서도 출력이 검증 가능하고 연구자가 해석할 수 있도록 보장한다.
방법
FunSearch는 후보 프로그램을 반복적으로 생성하고 평가하는 방식으로 작동한다. 사용자는 문제 사양, 평가 함수, 초기 프로그램 골격을 제공한다. 각 단계에서 시스템은 기존 프로그램을 데이터베이스에서 샘플링하며, 점수가 높은 프로그램을 우선시하고, 사전 학습된 대규모 언어 모델에 대한 프롬프트를 구성한다. 모델은 수정된 프로그램을 생성하고, 이는 실행되어 평가기에 의해 점수가 매겨진다. 유효한 프로그램은 데이터베이스에 다시 추가되어 탐색이 이전 성공을 기반으로 구축될 수 있게 한다.
탐색은 후보 프로그램 간의 다양성을 유지하기 위해 섬 기반 진화 방법을 사용하며, 지역 최적점으로 수렴할 위험을 줄인다. 원래 논문에서 언급된 주요 장점은 FunSearch가 최종 수치 답변이나 객체 목록만 제공하는 대신, 연구자가 검사하고 단순화하며 해석할 수 있는 프로그램을 출력한다는 점이다.
알고리즘 공식화
FunSearch는 고정된 골격에 내장된 함수와 같은 프로그램 조각 공간에 대한 탐색으로 설명할 수 있다. \(\mathcal{F}\)를 후보 함수 공간, \(S: \mathcal{F} \to \mathbb{R}\)를 고정된 솔버를 실행하여 얻은 평가 점수라고 하자. 초기 함수 \(f_0\)가 주어지면, FunSearch는 평가된 유효 함수의 데이터베이스 \(D\)를 유지한다. 이 시스템은 \(D\)에서 고득점 함수를 반복적으로 샘플링하고, 이를 사용해 대규모 언어 모델에 대한 프롬프트를 구성하며, 모델이 새 후보 함수 \(f'\)를 생성하도록 요청한다. 새 함수는 문제별 골격 내에서 실행되고 점수가 매겨진다. 유효하면 \(D\)에 추가되어 이후 프롬프트가 더 강력한 후보를 기반으로 구축될 수 있다.
이상적인 목표는 높은 평가 점수를 가진 후보 함수 \(f^* \in \arg\max_{f \in \mathcal{F}} S(f)\)를 찾는 것이지만, 실제로 FunSearch는 탐색 중 발견된 최상의 유효 함수를 반환한다. 원래 구현은 고득점 프로그램을 우선시하면서 다양성을 유지하기 위해 섬 기반 진화 프로세스를 사용한다.
응용
캡 집합 문제
FunSearch는 먼저 캡 집합 문제에서 시연되었으며, 이는 \(\mathbb{Z}_3^n\)에서 세 점이 일직선에 없는 가장 큰 부분 집합에 관한 가산 조합론 문제이다. 차원 8에서 FunSearch는 크기 512의 캡 집합을 발견하여 기존 구성보다 개선되었다. 논문은 또한 허용 집합과 관련된 구성을 발견하여 캡 집합 용량에 대한 더 나은 하한을 보고했다. Google DeepMind는 이 결과를 수학에서 검증 가능한 새로운 지식을 생성하는 대규모 언어 모델 사용의 예로 설명했다. Nature 뉴스 기사는 이 시스템이 카드 게임 Set과 관련된 조합론 문제에서 인간의 노력을 개선했다고 보도했다.
온라인 빈 포장
FunSearch는 또한 온라인 빈 포장 문제에 적용되었으며, 여기서 항목이 도착할 때 빈에 할당되어야 한다. 이 설정에서 FunSearch는 새 항목을 받을 빈을 결정하는 프로그램적 휴리스틱을 진화시켰다. 원래 논문은 발견된 휴리스틱이 시뮬레이션 데이터 및 OR-Library 벤치마크 인스턴스에서 일반적인 first-fit 및 best-fit 기준선보다 우수하다고 보고했다.
소프트웨어
Google DeepMind는 FunSearch 소프트웨어를 공개 GitHub 저장소에 공개하여 연구자가 결과를 재현하고 다른 문제에 방법을 적용할 수 있게 했다. 릴리스에는 진화적 탐색 코드, 평가기 인터페이스, 캡 집합 및 빈 포장 문제에 대한 예제가 포함된다. 이러한 공개 가용성은 Machine learning 및 Artificial intelligence 분야에서 추가 실험을 지원한다.
중요성
FunSearch는 대규모 언어 모델과 진화 계산의 통합으로 주목할 만하며, 이는 Deep learning의 더 넓은 분야에서 주목을 받고 있는 방향이다. 해석 가능한 프로그램을 생성함으로써, 문제를 해결할 뿐만 아니라 인간이 이해하고 구축할 수 있는 통찰력을 제공하는 AI 시스템으로의 경로를 제시한다. 이 방법은 Google DeepMind의 과학적 발견에 AI를 적용하려는 더 넓은 노력의 맥락에서 논의되었으며, Generative AI의 다른 이니셔티브와 함께 다루어졌다.
FunSearch는 특정 수학적 및 알고리즘적 작업에서 가능성을 보여주었지만, 일반적인 적용 가능성은 여전히 활발한 연구 영역이다. 사전 학습된 언어 모델에 대한 의존성과 잘 정의된 평가기의 필요성은 다른 영역에서의 사용을 제한할 수 있는 제약이다. 그럼에도 불구하고, 이 접근 방식은 프로그램 합성 및 최적화를 위한 언어 모델 사용에 대한 추가 작업에 영감을 주었으며, AI 연구의 진화하는 풍경에 기여하고 있다.