FunSearch: Making new discoveries in mathematical sciences using Large Language Models

FunSearch는 2023년 12월 말에 나온 Deepmind 논문으로 Nature에 실렸다고 한다.
Open problem에 대해서 기존에 인간이 풀었던 방식 이외로의 해결방식을 제시했다. 이십 년 전에 멈춰있던 해결법에서 더 나은 해결법을 제시했다는 점에서 이런 논문지에 실릴 수 있지 않았을까?

FunSearch이 Function space search의 약자로 LLM을 사용해서 문제를 새롭게 풀어낼 수 있는 방법을 제시한다. 이 논문에서는 LLM 자체보다는 Evaluation, Program database를 어떻게 사용할지에 초점을 맞추었다.

Specification

• 이 그림에서 Specification은 문제에 대한 설명, 정답이 어떠했으면 좋겠다는 설명이 들어갈 것이다.

Prompt

• 맨 처음 Prompt는 initial code로 넣어준다. (Skeleton code)

LLM

• PaLM2중 text-to-code foundation model인 Codey를 사용했다.
• 코드를 생성하기 때문에 hallucination을 피할 수 있었다.
• 코드를 생성했기 때문에 사람이 더 개선할 여지를 주기도 한다고 말한다. (협업방안이 되기도)

Evaluation

• Spec에서 제시된 평가방법대로 평가를 진행하게 된다.
• 여기에서 LLM이 제시해준 코드가 시간이나 메모리 문제 등으로 멈추는 경우는 program database로 넘기지 않는다.

Programs database

• 입력값으로 Evaluation에서 통과된 코드가 데이터베이스로 들어간다.
• 통과된 코드들 중 점수가 좋은 것과 좋지 않은 예시들을 Prompt에 포함해서 LLM으로 넘긴다.
• 반복해서 문제를 더 잘 풀어가도록 하는 유전 알고리즘을 통해서 이렇게 더 좋은 결과를 만들어내도록 했다.
• 프로그램 코드가 짧고 점수가 높은 경우를 하나씩 뽑아서 LLM instruction를 구성하여 LLM으로 해당 코드들을 참고해서 더 좋은 코드(더 좋은 문제풀이 방법)를 짜도록 한다.

결과적으로 이런 방법들을 통해서

특정한 정답을 가지고 있지 않는 문제(cat set problem)를 푸는 것을 넘어서 아래와 같이 그림에서 볼 수 있는 bin packing 문제도 풀었다.

섬 알고리즘

"Islands model" in the context of genetic algorithms refers to a specific variation of the genetic algorithm (GA) that involves multiple populations, often referred to as demes, evolving in parallel.

예제로 $2a^2+b = 57$ 만족하는 최적의 a, b를 구한다고 한다면

1. Random a, b를 몇 쌍 뽑아서 그 값과 57과의 차이를 fitness, $fitting = 1/fitness$ 값을 통해서 사용한 예제들 중 얼마나 적합한지를 확인할 수 있는 적합도($fitting/sum(fitting)$)를 구하게 된다.

2. Cross-over 위에서 구한 적합도를 기반으로 뽑아낸 쌍들 중 적합도를 기반으로 다시 쌍들의 구성을 변경하고(더 높은 점수를 가진 예제가 좀 더 많이 등장하게 된다.) 비트로 변환한 후 이 중 몇 개를 골라 shift 진행한다.
   (우성인 경우에 많이 등장할 것이고, cross-over할 때에도 영향을 더 많이 줄 것이다.)

3. Mutation 특정 확률을 기반으로 바꿀지말지를 결정하게 된다.(0과 1뿐이므로)
   하지만 항상 모든 유전자의 영향을 받을 수는 없기 때문에 약간의 변이가 생기게 된다는 것을 반영한다.

이렇게 계속해서 반복한다.
정지조건으로는 반복의 횟수를 정하거나, 적합도의 평균이 부모 세대보다 나아지지 않는 경우에 정지할 수 있다.

FunSearch의 섬 알고리즘

• FunSearch 에서 하나의 예제 (pair)를 하나의 클러스터라고 말하는데, 특정 갯수의 예제로 진행을 하면 해당 갯수의 클러스터가 하나의 섬에서 진화를 시작하게 된다.
• 논문에서는 열 개의 섬을 가지고 있는데, 문제들을 풀 때 열 개의 아일랜드에 먼저 통과한 예제들을 넣어주고 (아마도 두 개 이상이라면) 해당 예제들 중 두 개를 뽑아 (mutation) 더 좋은 문제풀이를 생성해내도록 한다.
• 열 개의 섬에서 문제를 풀게 되는데, 이 경우에 점수가 지지부진할 경우에 해당 섬을 리셋하게 된다(불이나서 섬에 있는 모든 생명체가 죽음). 이 경우에는 다른 섬에서 한 개의 클러스터만 이동해서 복제를 한다거나해서 그 섬에서 또 다른 진화과정이 진행된다.
• 이 연구에서 정지조건이 없다. (Endless하게 진행한다고 함)

이 연구가 곱씹어볼수록 놀라운 점은 LLM은 다 외워서하는 앵무새만은 아닐 수 있다는 지점을 보여주기도 한다는 것이다.