OpenAI의 수학 라이브러리에서 주장하는 고속 푸리에 변환 (FFT) 분석

안녕하세요, argmin 독자 여러분! 오늘 게시물은 OpenAI의 수학 저장소 중 빠르다고 주장되는 푸리에 변환(Fourier transforms)을 계산하는 부분에 대해 다룹니다. 평소보다 기술적인 내용이지만, 신호 처리 또는 계산 복잡도에 대한 복습이 필요한 분들을 위해 튜토리얼 자료를 추가하려고 노력했습니다.

The Fast Fourier Transform (FFT)은 디지털 신호 처리(digital signal processing)에서 가장 중요한 혁신 중 하나이자 제가 가장 좋아하는 알고리즘 중 하나입니다. FFT는 신호의 주파수 성분(frequency content)을 추출하는 빠르고 효율적인 방법으로, 스펙트럼의 다양한 대역에 걸쳐 주파수를 빠르게 분석하고, 필터링하며, 조작할 수 있게 해줍니다.

The 푸리에 변환은 간단한 내적(dot product)을 통해 각 주파수 대역의 에너지를 계산합니다. $x$를 샘플 길이 $n$인 입력 배열로, $f$를 주파수라고 할 때, $x$에서 $f$에서의 주파수 성분 양은 다음 공식으로 계산될 수 있습니다:

[공식 생략]

디지털 신호의 경우, 모든 주파수 성분을 이해하기 위해서는 각 주파수의 배수인 $2 ext{𝜋}/n$ 지점에서 이 내적을 단지 $n$번만 계산하면 됩니다. 순진하게(naively) 접근할 경우, 이는 각 주파수에 대해 $n$번의 곱셈과 덧셈을 필요로 합니다. 따라서 전체 푸리에 변환을 계산하는 것은 $n^2$개의 산술 연산을 요구하는 것으로 보입니다.

고속 푸리에 변환(fast Fourier transform)은 James Cooley와 John Tukey가 1965년에 고안한 영리한 재귀적 절차입니다. 주요 아이디어는 길이-$n$의 푸리에 변환을 입력 벡터를 재배열하고, 재배열된 구성 요소에 대해 길이 $n/2$의 푸리에 변환 두 개를 계산한 다음, 원자적인 산술 연산을 사용하여 출력들을 다시 결합함으로써 계산할 수 있다는 것입니다. 이러한 재배열과 재결합 과정은 선형(linear) 수의 산술 연산을 필요로 합니다. 이 절차를 반복적으로, 즉 $ ext{log}_2(n)$번 수행하면 전체 이산 푸리에 변환(discrete Fourier transform)을 계산합니다. 정리하자면, FFT는 $5 n ext{log}_2 n$개 미만의 산술 연산으로 길이-$n$의 푸리에 변환을 계산합니다.

이 가속 효과를 구체적으로 살펴보면, n이 1,000일 때 n²은 1,000,000이고 5 * n log n은 약 50,000입니다. 이는 20배의 속도 향상을 의미합니다. n이 1,000,000일 때는 속도 향상이 10,000배에 달합니다. 이러한 속도 향상은 신호 처리 애플리케이션의 제약 조건 하에서 변환(transform)을 계산할 수 있는지 여부를 결정하는 차이가 될 수 있습니다.

FFT가 발명된 이래로 사람들은 더 빠른 푸리에 변환(Fourier transforms)을 찾아왔습니다. 하나의 질문은 얼마나 빠르게 갈 수 있느냐는 것입니다. FFT를 작성하는 것만으로도 n 단계가 필요하기 때문에, 적어도 n개의 연산이 필요할 것 같습니다. FFT는 그 합리적인 속도 제한보다 5log2(n)배 느린데, 이 5log2(n) 인자는 클 수 있습니다. n이 일조(trillion)일 때 200입니다. 이 200이라는 전인자(prefactor)를 줄이기 위해 영리한 방법을 찾을 수 있을까요?

글쎄요, 놀랍게도 지난주 OpenAI가 수학계에 쏟아낸 방대한 논문 더미에서 그들은 더 빠른 푸리에 변환을 주장하고 있습니다. 그들의 차별적으로 명명된 “main.pdf”에서 나온 주요 주장은 다음과 같습니다.

(중략)

저는 여기서 무슨 일이 벌어지고 있는지 궁금했습니다. 이론적으로 log(n) 항은 표준 FFT보다 아주 조금 더 작았습니다.

제가 이 논문을 읽었나요? 물론 아닙니다. OpenAI의 누구도 이 논문을 읽지 않았으니, 제가 왜 읽어야 할까요? 저는 전 세계 모든 수학자들이 AI가 만들어낸 수학적 쓰레기(slop mathematics)를 다루는 방식대로 했습니다. 즉, 그것을 다시 쓰레기 기계에 넣고 챗봇 인터페이스로 정보 검색 세션을 실행하여 핵심 사실들을 추출했습니다. 의인화하자면: 저는 ChatGPT에게 자신의 출력물에 대해 어떻게 생각하는지 물어봤습니다. 이것이 바로 우리가 지금 수학 연구를 하는 방식입니다. 정말 대단한 세상입니다.

불행하게도, 저는 더 빠른 푸리에 변환을 찾지 못했습니다. 대신, 형식주의(formalism)가 현실과 너무 동떨어져서

우선, “빅-오(big-O)” 표기법은 너무 남용되어 의미가 없어졌습니다. 학부 시절 저에게 깊은 인상을 주었던 정의를 복습해 보겠습니다. 알고리즘의 실행 시간이 $T(n) = O(F(n))$이라는 것은 정수 $N$과 상수 $C$가 존재하여 다음을 만족한다는 것입니다.

즉, 알고리즘이 실제로 수행하는 단계 수는 $n$이 충분히 클 때 상수가 어떤 편리한 함수 $F(n)$의 배수로 위쪽 경계(upper bounded)를 갖는다는 의미입니다. $F(n)$은 보통 다항식이나 지수 함수처럼 익숙하고 해석 가능한 무언가입니다. 이 표기법은 우리가 계산 크기가 클 때 무슨 일이 일어나는지에만 관심이 있다는 것을 말해줍니다. 우리는 계산 시간의 점근적(asymptotic) 성장률에 관심을 갖습니다. 모든 상수는 동등합니다.

빅-오 표기법은 알고리즘 계정(algorithmic accounting)에서 지름길을 찾는 데 유용하지만, 놀라운 논리적 게으름(logical laziness)도 허용합니다. 만약 우리가 실질적으로 더 빠른 FFT를 원한다면, 합리적인 크기의 $n$에 대해 $50n$번 미만의 연산을 요구하는 알고리즘을 원할 것입니다. 하지만 $O(n)$이 $50n$을 의미하지는 않습니다. $10^{80}n$을 의미할 수도 있습니다. 이것은 “선형 시간(linear time)” 알고리즘으로 간주될 것입니다. $n + 10^{80}$을 요구하는 알고리즘 역시 빅-오 체제에서는 선형 시간 알고리즘으로 간주됩니다. $n$이 $10^{80}$보다 클 때만 선형 시간 보장을 갖는 알고리즘도 마찬가지입니다. $10^{80}$은 알려진 우주의 원자 수와 거의 같습니다. 이것이 리처드 립턴(Richard Lipton)과 켄 리건(Ken Regan)이 감히 상상할 수 없을 만큼 큰 숨겨진 상수(hidden constants)를 가진 알고리즘을 *은하계 알고리즘(galactic algorithms)*이라고 부르는 이유입니다.

OpenAI의 FFT 알고리즘은 확실히 은하계적입니다. $N=10^{12}$일 때 추정된 값 $C$는 $10^{100}$이었습니다. 따라서 $n=10^{100}$일 때조차도, 존경받는 Cooley-Tukey-Gauss FFT보다 1099배 더 빠를 것입니다.

그렇다면 이 새로운 FFT 결과가 왜 흥미로운 것일까요? 빅-오 표기법에서 기술적으로 Cooley-Tukey 알고리즘보다 점근적으로(asymptotically) 더 빠르다는 점에 주목하세요. 왜냐하면

제 말은, 물론입니다. 하지만 상수를 고려할 때, 이 알고리즘이 더 빠르게 실행되는 경우는 $n$이 불가능할 정도로 클 때뿐입니다. 대략적으로, 당신은 필요합니다

저 숫자가 도대체 무슨 의미인지.

Lipton과 Regan은 전역 알고리즘(galactic algorithms)이 연구를 촉진시키기 때문에 유용하다고 주장합니다. 실행 시간이 점근적으로 가능하다는 것을 보여주면, 그 시간을 가지고 실제로 이 증명 가능한 실행 시간을 달성하는 알고리즘을 찾는 데 집중할 수 있다는 것입니다. 어쩌면 여러분의 AI 에이전트 군집(swarms)을 그것 뒤에 보내볼 수도 있습니다. 각자 할 일을 하세요. 실용적인 알고리즘을 도출해낼 수도 있겠지만, 이런 일이 실제로 일어난 합당한 사례는 제가 아는 바가 없습니다. 저는 특히 의구심스럽습니다. 왜냐하면 OpenAI가 사용하는 “계산(computation)” 모델은 실제 컴퓨터와는 전혀 유사하지 않기 때문입니다.

“이 모델은 정확한 복소수 산술을 사용합니다.” 이는 임의 정밀도에서 복소수를 저장하고 곱할 수 있다고 가정한다는 의미입니다. 실제로 이 알고리즘은 크기가 $n$에 대해 *초다항식적(superpolynomially)*으로 증가하는 복소수를 곱해야 합니다. 만약 이러한 숫자를 비트(bits)로 저장한다면, 메모리 요구 사항은 입력 길이에 대해 사실상 지수적(exponential)이 될 것입니다. 이 모델은 그러한 임의로 큰 복소수들을 단일 연산으로 곱할 수 있다고 가정합니다. 우리는 그렇게 할 수 있는 컴퓨터를 가지고 있지 않습니다. 따라서 main.pdf에 있는 이 정리가 “참”이라고 하더라도 (아무도 모르고, 저도 신경 안 쓰지만), 그것은 우리가 더 빠른 FFT를 찾을 때 해결하고자 했던 문제를 실제로 해결하는 것은 아닙니다.

FFT의 이론적 분석에 익숙한 사람들에게는, FFT 속도 한계를 돌파하기 위해 터무니없는 계산 모델이 필요하다는 사실은 놀랍지 않을 것입니다. 1973년, Jacques Morgenstern은 계산에 사용되는 복소 계수들이 유계 크기를 가져야 한다면 $rac{1}{2} n ext{ log } n$보다 빠르게 푸리에 변환을 얻을 수 없다는 것을 증명했습니다. 이것으로 이야기가 끝났어야 했습니다! 하지만 그렇지 않았습니다. 사람들은 Morgenstern의 제한된 계수 모델이 너무 제약적이라고 말했습니다. 40년 후, Nir Ailon은 심각한 수치 불안정성(numerical instabilities) 없이 FFT를 $n ext{ log } n$보다 빠르게 계산할 수 없다는 것을 보여주었습니다. 이것 역시 어떤 사람들에게는 너무 제약적이었던 것 같습니다.

따라서 이 새로운 OpenAI의 결과는 수학적 돌파구라기보다는 컴퓨터 과학자들이 설계 사양을 형식화하는 데 서툰 것에서 비롯된 기이한 현상에 가깝다. 컴퓨터에 대한 ‘이론적인’ 정의는 우리가 실제로 구축하는 컴퓨터와 매우 동떨어져 있다. 이 ‘더 빠른’ 푸리에 변환(Fourier transform)은 이론이 원래의 질문과 너무 멀리 떨어져서 ‘미해결 문제(open problem)’가 단순한 학술적 지위 퍼즐에 불과하게 된 예시일 뿐이다. 그 해결책은 마치 계산용 봇 스트림을 불가능한 문제에 설정했을 때, 그것들이 불법 해킹에 몰두하는 것과 같다.

이 OpenAI의 쓰레기장(slopository)에 있는 다른 ‘거대한’ 결과들 중 상당수도 같은 방식으로 비판할 수 있다. 예를 들어, 그 결과 중 하나는 두 행렬을 $O(n^{2.25})$ 연산으로 곱하는 은하계 알고리즘이었다. 논문에서 사용된 구성 방식으로는 빅 오 표기법($O$) 안에 숨겨진 상수조차 추정할 수 없다. 그것은 무한대와 다름없으며, 오직 천상의 음악(divine music of the spheres) 같은 신성한 방식으로만 계산 가능하다.

그럼에도 불구하고, 만약 이 논문들이 훨씬 더 잘 쓰여졌다면, 컴퓨터 과학 이론 분야의 가장 권위 있는 출판 장소(즉, STOC나 FOCS와 같은 심사 과정을 거친 학회 발표 자료집)에 실렸을 것이다. 행렬 곱셈 논문은 아마도 상을 받았을 것이다. 하지만 이 둘 중 어느 것도 컴퓨터와는 아무 관련이 없다!

이는 컴퓨터 과학 이론이 알고리즘을 실제로 컴퓨터에서 실행하는 것을 적극적으로 억제하는 문화를 가지고 있기 때문이다. 존재하지만 절대로 그것을 글로 쓰지 않은 알고리즘이 존재한다고 주장하는 논문을 이론 학회에 발표하는 것은 용인된다. 컴퓨터 과학 이론은 이제 컴퓨터와 관련되지 않는 일종의 수학이 되었으며, 그러한 순수 수학적 추구 외의 분야에서 영향력을 발휘할 경우 거의 보상을 받지 못한다. 나는 이 점을 “이론(theory)”이라는 단어가 스스로 만들어낸 ‘폐쇄적인 곳에 숨어 지내는’ 다학제적 의미를 가진다고 말하는 친구에게 설명한 적이 있다.

AI는 우리의 최악의 경향을 자동화하는 데 정말 능합니다. 아무도 좋아하지 않지만 개인이 합리적으로 벗어날 수 없는 암묵적인 문화적 관행을 증폭시킵니다. 집단 행동에 저항하는 기계화된 전통을 악용합니다. 이런 맥락에서, AI는 이제 쓸모없는 이론 논문을 작성할 수 있습니다. 하지만 어쩌면 불쾌한 OpenAI의 쓰레기장 같은 증명들 속의 부조리함 속에서, 우리 모두가 고개를 들고 함께 무언가 다른 것을 고려해야 한다는 사실을 깨달을 수도 있을 것입니다.

위키피디아 페이지에 따르면 이것은 1805년 가우스(Gauss)에게 공로를 돌려야 한다고 합니다! 적절한 공로 인정은 학계에서 영원한 문제입니다.

저것 하나만 봐도, 모든 $ ext{epsilon} > 0$ 에 대해 $T(n) ext{ } ext{<= } n^{(2.25 + ext{epsilon} + C/ ext{log}(n))}$ 을 만족하는 상수 $C$가 존재한다는 것을 알 수 있습니다. 제가 어떤 질문을 하든, OpenAI 모델이 $C$에 대한 정량적 추정치를 제공하게 할 수가 없습니다. 뭐 어때요!