AutoNumerics-Zero: Automated Discovery of State-of-the-Art Mathematical Functions

Motivation

• Known: 초월함수(지수, 로그, 삼각함수 등)는 하드웨어가 직접 계산할 수 없어 Taylor series, Chebyshev polynomials, Padé approximants, minimax optimization 등 수학자들이 개발한 방법으로 기본 연산({+, -, ×, ÷}) 조합을 통해 임의의 정확도로 근사해왔다. 최근에는 RL을 이용해 행렬곱셈(Fawzi et al., 2022)이나 정렬 알고리즘(Mankowitz et al., 2023) 같은 새로운 수학 알고리즘을 발견한 사례도 있다.
• Gap: 기존 근사법들은 임의 정확도(arbitrary accuracy) 달성을 목표로 설계되었으나, 실제 컴퓨터는 float32와 같은 유한 정밀도 타입만 사용하므로 그 이상의 정확도는 낭비된다. 유한하지만 높은 정확도만을 목표로 삼았을 때 더 효율적인(연산 수가 적은) 근사식을 발견할 수 있는지는 탐구되지 않았으며, 기존 접근법은 다항식 등 고정된 형태(form)에 얽매여 임의의 연산 조합이나 중간값 재사용을 통한 프로그램 구조를 탐색하지 못한다.
• Why: 과학 계산에서 편재하는 초월함수 계산의 효율을 높이면 계산 비용 절감 효과가 모든 향후 사용에 걸쳐 누적되며, 사전 수학 지식이나 학습 데이터에 의존하지 않는 zero-knowledge 탐색 방식은 기존 방법들의 편향에서 자유로워 새로운 수학적 발견(대형 언어모델과 상호보완적인 방법)으로 이어질 잠재력을 지닌다.
• Approach: 빈 프로그램에서 시작하여 무작위적이고 수학적 지식이 전혀 개입되지 않는 mutation만을 사용하는 진화적 symbolic regression 방법인 AutoNumerics-Zero를 제안하고, 정확도와 프로그램 길이(연산 수)를 목적함수로 최적화하여 여러 초월함수에 대해 기존 확립된 근사 기법들과 비교한다.

Achievement

Figure 4. Programs evolved from scratch (top row, orange) surpass

1. AutoNumerics-Zero 제안: 전통적 최적화 기법들을 결합하되 수학 지식을 전혀 사용하지 않는 zero-knowledge symbolic regression 방법을 개발했다.
2. 최고 수준 지수함수 근사 발견: 10개 연산으로 지수함수를 14 유효자리까지 근사하는 프로그램을 발견했으며, 이는 동일 연산 수의 기존 최고 근사법보다 6 자릿수 이상 정확도가 높다.
3. 엄밀한 검증: 발견된 근사에 대해 자동화된 방식으로 오차 상한을 수학적으로 증명하여 우수성을 입증했다.
4. 하드웨어 특화 확장: 특정 하드웨어 아키텍처(컴파일 경로)에 맞춰 최적화함으로써 기존 대비 3배 이상 빠른 근사를 발견하는 등 방법의 확장 가능성을 보였다.

How

Figure 2. Evolutionary search. This 4-stage cycle is iterated to

• 프로그램을 compute graph 형태로 표현하고, 빈 프로그램에서 시작해 4단계(선택-복제-변이-평가) 진화 사이클을 반복하는 population 기반 탐색을 수행한다.
• mutation은 기본 연산(+, -, ×, ÷) 및 상수 삽입 등에 대해 완전히 무작위로 적용되어, 어떤 변수를 조합할지 등에 수학적 사전지식이 개입하지 않도록 설계된다.
• 적합도(fitness)는 정확도와 프로그램 길이(연산 수)라는 미분 불가능한(non-differentiable) 목표를 동시에 고려한다.
• 유한 정밀도(예: float32) 기준의 높은-그러나 유한한 정확도 목표를 설정하여, 임의 정확도를 추구하는 전통적 방법과 차별화한다.
• 발견된 프로그램은 Chebyshev polynomials, Padé approximants, minimax optimization 등 각 타겟 함수에 적합한 강력한 baseline과 비교되며, 우위가 두드러진 경우 오차 상한을 자동화된 방식으로 수학적으로 증명한다.
• Section 4.6에서는 특정 하드웨어(컴파일 경로)에 특화하여 일반성 대신 효율을 극대화하는 실험도 수행한다.

Originality

• 임의 정확도가 아닌 유한 정밀도(예: float32) 목표에 최적화한다는 문제 설정 자체가 참신하며, 이를 통해 기존에 간과된 효율적 근사식 발견 가능성을 제시한다.
• 수학적 사전지식(전개 규칙, 미분 계산, 인간 설계 함수 코퍼스 사전학습 등)을 전혀 사용하지 않는 완전한 zero-knowledge 탐색으로, LLM 기반 접근과 상호보완적인 방법론을 제공한다.
• 함수를 수식(formula)이 아닌 프로그램(program)으로 표현하여 중간값 재사용을 통한 더 짧은 계산을 가능케 하는 표현 방식을 채택했다.
• 작은 입력 크기에서 탐색 후 해석적으로 일반화하는 기존 RL 기반 수학 발견 연구(Fawzi et al., 2022; Mankowitz et al., 2023)와 달리, 실제 사용되는 입력 크기(예: 32비트 부동소수점)에서 직접 탐색하여 해의 대규모 구조까지 탐색한다는 차별점이 있다.

Limitation & Further Study

• 저자들 스스로 밝히듯, 모든 타겟 함수에서 진화적 방법이 전통적 baseline을 능가한다고 주장하지 않으며, 함수별로 적합한 기법이 다를 수 있어 일반화 가능성에 한계가 있다.
• 진화적 탐색은 계산 비용이 크고 재현성 및 탐색 안정성(다양한 seed나 초기화에 따른 결과 편차)에 대한 논의가 충분히 제시되지 않을 가능성이 있다.
• 하드웨어 특화 최적화(Section 4.6)는 일반성을 희생하므로, 다른 하드웨어나 컴파일러 버전에 대한 이식성이 제한적일 수 있다.
• 후속 연구로 강화학습 기반 재구성, 더 다양한 연산 집합이나 타겟 함수로의 확장, 그리고 실제 물리 법칙 발견과 같은 더 광범위한 symbolic regression 응용으로의 확장이 제안된다.

Evaluation

총평: 사전 수학 지식 없이 진화적 탐색만으로 기존 최고 수준의 근사식을 능가하는 결과를 수학적으로 엄밀하게 입증한 흥미롭고 실용적인 연구로, 수치 계산 및 자동화된 수학적 발견 분야에 의미 있는 기여를 한다.