캡 세트 문제의 새로운 하한선 제시한 딥마인드의 LLM
펀서치, 수학 함수 생성기 위에 판단·개선용 LLM을 쌓은 다층 구조 
인공지능의 가능성 넓혀, 수학자의 창의성 자극하는 '촉매제'

[해외DS]는 해외 유수의 데이터 사이언스 전문지들에서 전하는 업계 전문가들의 의견을 담았습니다. 저희 데이터 사이언스 경영 연구소 (GIAI R&D Korea)에서 영어 원문 공개 조건으로 콘텐츠 제휴가 진행 중입니다.

---

구글의 딥마인드는 대규모언어모델(LLM)을 사용해 인류의 가장 어려운 수학 문제 중 하나에 대한 새로운 해결책을 제시했다. 펀서치(Search for Mathematical Function, FunSearch)로 알려진 이 모델은 이른바 '캡 세트 문제'(Cap set Problem)에 대한 해결책을 발견한 것이다. 답이 있는 상태에서 수학 문제를 풀기 위해 LLM을 사용했던 이전의 실험들과는 확연히 대조적이다.

수십 년 동안 이어져 온 이 수수께끼는 점과 점 사이에 선을 그리면서 점 세 개가 직선을 이루지 않고 얼마나 많은 점을 연결할 수 있느냐를 묻는 극단적 조합론 문제다. 펀서치는 8차원에 걸쳐 512개의 점으로 구성된 솔루션을 만들어냈는데, 이는 지금까지 어떤 수학자가 해낸 것보다 큰 집합 규모다. 이 실험의 결과는 지난 14일 네이처(Nature) 저널에 게재됐다.

캡 세트 문제, "n개의 속성으로 식을 일반화하려면?"

캡 세트 문제는 1970년대에 유전학자 마샤 팔코가 개발한 게임에서 발전한 문제다. 앞서 언급한 대로 점을 연결하는 기하학적 문제기도 하지만 카드 조합 문제로도 풀어낼 수 있다. 기본적으로 덱(deck)에는 81장의 카드가 들어 있다. 각 카드에는 색상, 모양, 음영이 동일한 기호가 하나, 둘 또는 세 개씩 표시되며, 각 기호의 특징에 따라 세 가지 옵션이 존재한다. 이러한 가능성을 모두 합치면 3 × 3 × 3 × 3 = 81장의 덱이 만들어진다. 플레이어는 카드를 뒤집어 세 장의 카드에서 세트로 불리는 특별한 조합을 찾아내야 하는 방식이다.

수학자들은 뒤집힌 카드의 수가 21장 이상이면 플레이어가 세트를 찾을 수 있다는 것을 증명했다. 또한 5개 이상의 속성을 갖는 더 복잡한 버전의 게임에 대한 해결책도 찾아냈었다. 하지만 속성의 개수를 n개로 확장할 때 뒤집어야 하는 최소 카드 수는 알지 못했다. 즉 n개의 속성이 있고 n이 정수면 카드는 총 3ⁿ개지만, 해를 구하기 위해 공개해야 하는 최소 카드 수는 미스터리로 남아 있었다.

이산 기하학 관점으로 문제를 재정의하면 n 차원 공간에서 세 점의 특정 배열을 찾는 것과 같은 상황이다. 수학자들은 n이 주어졌을 때, 필요한 '테이블 위의 카드'의 수가 한 공식이 주는 수보다 크고 다른 공식이 주는 수보다 작아야 한다는 것을 발견함으로써 일반적인 해의 가능성에 대한 경계를 정할 수 있었다.

펀서치는 게임의 모든 요구 사항을 충족하는 카드 세트를 생성하여 새로운 하한(lower bound) n = 8을 찾아냈다. 딥마인드의 컴퓨터과학자 알프세인 파우지(Alfsein Fauzi)는 "더 이상 개선할 수 없다는 것을 증명한 것은 아니지만, 기존에 알려진 것보다 더 나은 결괏값을 얻었다"고 강조했다.

펀서치의 문제 해결 과정과 수학자와의 협업 방식

딥마인드 연구팀은 캡 세트 문제를 파이썬(프로그래밍 언어) 코드로 작성했는데 문제를 해결하는 방법을 명시하지 않은 상태로 펀서치에 입력했다. 펀서치는 두 가지 LLM으로 구성되어 있으며 문제가 담긴 코드는 먼저 구글의 건강관리 모델인 PaLM 2를 기반으로 만든 코디(codey)로 전송된다. 코디는 코드를 생성하여 해결책을 제안하는 역할을 수행한다. 그런 다음 제안된 해결책은 '평가자' 역할을 담당하는 LLM으로 전달되어 환각 증상이 의심되는 코드는 반려하고 정확성이 높은 코드는 저장하는 과정을 거친다. 또한 펀서치에는 가장 우수한 프로그램을 개발할 때까지 기존 코드를 지속적으로 업데이트하는 '자체 개선 루프'가 탑재돼 있다.

딥마인드의 컴퓨터과학자 베르나르디노 로메라-파레데스(Bernardino Romera-Paredes)는 "LLM이 생성하는 모든 프로그램이 유용한 것은 아니며, 종종 실행조차 할 수 없는 프로그램을 제안하는 경우도 있었다"고 전했다. 하지만 펀서치는 잘못된 프로그램을 빠르게 제거하고 올바른 프로그램을 찾아서 갱신하는 장점이 있다고 설명했다.

하지만 LLM은 여전히 결괏값을 설명하거나 이해하는 데 능숙하지 않다. 펀서치는 수학적 함수를 생성하고 검증할 수는 있지만, 그 이면의 논리나 직관은 제공하지 못한다. 다만 연구진은 수학자들이 펀서치가 발견한 코드를 살펴보고 수학적 인사이트를 추출한 후, 이를 펀서치에 대한 입력을 개선하는 데 사용하면 결과가 훨씬 더 개선됐다고 밝혔다. 아울러 공동 저자인 위스콘신대학교 매디슨 캠퍼스의 수학자 조던 엘렌버그(Jordan Ellenberg)는 "펀서치의 중요 특징 중 하나는 사람들이 LLM이 만든 프로그램을 통해 배울 수 있게 된 점이다"고 말했다. 그는 인간과 기계의 새로운 협업 방식을 모델링하는 것에 흥미를 느낀다고 덧붙였다. 이번 연구는 수학과 같은 순수학문의 발전을 돕는 용도로 LLM을 사용할 수 있다는 것에 큰 진전이 있는 연구 결과라고 사료된다.

---

AI Beats Humans on Unsolved Math Problem

Large language model does better than human mathematicians trying to solve combinatorics problems inspired by the card game Set

The card game Set has long inspired mathematicians to create interesting problems.

Now, a technique based on large language models (LLMs) is showing that artificial intelligence (AI) can help mathematicians to generate new solutions.

The AI system, called FunSearch, made progress on Set-inspired problems in combinatorics, a field of mathematics that studies how to count the possible arrangements of sets containing finitely many objects. But its inventors say that the method, described in Nature on 14 December¹, could be applied to a variety of questions in maths and computer science.

“This is the first time anyone has shown that an LLM-based system can go beyond what was known by mathematicians and computer scientists,” says Pushmeet Kohli, a computer scientist who heads the AI for Science team at Google Deepmind in London. “It’s not just novel, it’s more effective than anything else that exists today.”

This is in contrast to previous experiments, in which researchers have used LLMs to solve maths problems with known solutions, says Kohli.

MATHEMATICAL CHATBOT

FunSearch automatically creates requests for a specially trained LLM, asking it to write short computer programs that can generate solutions to a particular mathematical problem. The system then checks quickly to see whether those solutions are better than known ones. If not, it provides feedback to the LLM so that it can improve at the next round.

“The way we use the LLM is as a creativity engine,” says DeepMind computer scientist Bernardino Romera-Paredes. Not all programs that the LLM generates are useful, and some are so incorrect that they wouldn’t even be able to run, he says. But another program can quickly toss the incorrect ones away and test the output of the correct ones.

The team tested FunSearch on the ‘cap set problem’. This evolved out of the game Set, which was invented in the 1970s by geneticist Marsha Falco. The Set deck contains 81 cards. Each card displays one, two or three symbols that are identical in colour, shape and shading — and, for each of these features, there are three possible options. Together, these possibilities add up to 3 × 3 × 3 × 3 = 81. Players have to turn over the cards and spot special combinations of three cards called sets.

Mathematicians have shown that players are guaranteed to find a set if the number of upturned cards is at least 21. They have also found solutions for more-complex versions of the game, in which abstract versions of the cards have five or more properties. But some mysteries remain. For example, if there are n properties, where n is any whole number, then there are 3ⁿ possible cards — but the minimum number of cards that must be revealed to guarantee a solution is unknown.

This problem can be expressed in terms of discrete geometry. There, it is equivalent to finding certain arrangements of three points in an n-dimensional space. Mathematicians have been able to put bounds on the possible general solution — given n, they have found that the required number of ‘cards on the table’ must be greater than that given by a certain formula, but smaller than that given by another.

HUMAN–MACHINE COLLABORATION

FunSearch was able to improve on the lower bound for n = 8 by generating sets of cards that satisfy all the requirements of the game. “We don’t prove that we cannot improve over that, but we do get a construction that goes beyond what was known before,” says DeepMind computer scientist Alhussein Fawzi.

One important feature of FunSearch is that people can see the successful programs created by the LLM and learn from them, says co-author Jordan Ellenberg, a mathematician at the University of Wisconsin–Madison. This sets the technique apart from other applications, in which the AI is a black box.

“What’s most exciting to me is modelling new modes of human–machine collaboration,” Ellenberg adds. “I don’t look to use these as a replacement for human mathematicians, but as a force multiplier.”