Het artikel behandelt de Fast Fourier Transform (FFT), een essentieel algoritme in de digitale signaalverwerking dat via de Cooley-Tukey-methode de complexiteit van Fourier-transformaties drastisch verlaagt naar $O(n \log n)$.
De auteur reageert op een recente publicatie van OpenAI waarin wordt beweerd dat er een snellere variant van de FFT is gevonden. Ben Recht betoogt echter dat dit een voorbeeld is van een galactisch algoritme: een algoritme dat theoretisch (asymptotisch) sneller is in de Big-O notatie, maar in de praktijk onbruikbaar is omdat de constante factor zo onvoorstelbaar groot is dat het nooit sneller zal draaien op fysiek mogelijke hardware.
Daarnaast bekritiseert de auteur het onrealistische rekenmodel van OpenAI, dat uitgaat van exacte complexe rekenkunde met willekeurige precisie. Het artikel eindigt met een bredere kritiek op de theoretische informatica, die volgens de auteur te ver is afgestapt van de praktische computerwetenschap, en waarschuwt dat AI deze trend van het produceren van nutteloze, puur theoretische papers kan versnellen.
Snellere Fourier-transformaties
In deze analyse kijken we naar een deel van de wiskunde-repository van OpenAI waarin wordt beweerd dat er snellere Fourier-transformaties kunnen worden berekend. De tekst is technischer dan gebruikelijk, maar bevat uitleg over signaalverwerking en computationele complexiteit voor wie een opfriscursus nodig heeft.
Wat is de Fast Fourier Transform (FFT)?
De Fast Fourier Transform (FFT) is een van de belangrijkste innovaties in digitale signaalverwerking. De FFT is een snelle methode om de frequentie-inhoud van signalen te extraheren, waardoor men snel frequenties over verschillende banden van het spectrum kan analyseren, filteren en manipuleren.
De Fourier-transformatie berekent de energie in elke frequentieband via een eenvoudig inproduct (dot product) [^1]. Stel dat $x$ de input is (een array van $n$ samples) en $f$ een frequentie. De hoeveelheid frequentie-inhoud in $x$ bij $f$ kan worden berekend met een specifieke formule.
Voor digitale signalen blijkt dat je slechts $n$ van deze inproducten hoeft te berekenen (één voor elk veelvoud van de frequentie $2\pi/n$) om alle frequentie-inhoud te begrijpen. Een naïvst benadering vereist $n$ vermenigvuldigingen en optellingen per frequentie. Hierdoor lijkt het berekenen van de volledige Fourier-transformatie $n^2$ rekenoperaties te vereisen.
Het Cooley-Tukey algoritme
De fast Fourier transform is een slimme recursieve procedure, bedacht door James Cooley en John Tukey in 1965 [^2]. Het hoofdidee is dat een Fourier-transformatie van lengte $n$ kan worden berekend door:
- De inputvector te husselen.
- Twee Fourier-transformaties van lengte $n/2$ te berekenen op de gehusselde componenten.
- De resultaten te combineren met behulp van atomaire rekenoperaties.
De husselacties en recombinaties kosten een lineair aantal rekenoperaties. Door deze procedure iteratief te herhalen ($\log2(n)$ keer), wordt de volledige discrete Fourier-transformatie berekend. Inclusief de administratie berekent de FFT een transformatie van lengte $n$ in minder dan $5 n \log2 n$ rekenoperaties.
Concreet versnellingseffect:
- Bij $n = 1.000$ is $n^2 = 1.000.000$, terwijl $5 \cdot n \log n$ ongeveer $50.000$ is (een 20-voudige versnelling).
- Bij $n = 1.000.000$ is de versnelling 10.000-voudig.
Deze versnellingen bepalen vaak of een transformatie überhaupt berekenbaar is binnen de beperkingen van een signaalverwerkingsapplicatie.
De claim van OpenAI
Sinds de uitvinding van de FFT zoeken onderzoekers naar nog snellere varianten. Men vraagt zich af hoe snel het theoretisch kan gaan. Omdat het $n$ stappen kost om de FFT simpelweg op te schrijven, lijkt $n$ operaties de ondergrens. De FFT is $5 \cdot \log_2(n)$ keer trager dan die limiet. Bij $n$ in de biljoenen is die factor ongeveer 200. Kan die prefactor worden verlaagd?
In een recente publicatie van OpenAI beweren zij een snellere Fourier-transformatie te hebben gevonden. In hun document "main.pdf" claimen ze een resultaat waarbij de $\log(n)$-term theoretisch iets kleiner is dan in de standaard FFT.
Ik heb dit document niet op de traditionele manier gelezen. In plaats daarvan heb ik het gevoed aan een chatbot-interface om de belangrijkste feiten te extraheren—in feite vroeg ik ChatGPT wat het van zijn eigen output vond. Dit is hoe wiskundig onderzoek tegenwoordig blijkbaar wordt gedaan.
Het probleem: Galactische Algoritmen
Wat ik vond was geen snellere FFT, maar een voorbeeld van hoe toegepaste wiskundige theorie kan degenereren wanneer formalisme volledig losgekoppeld raakt van de realiteit.
De misleiding van de Big-O notatie
De "Big-O" notatie wordt vaak misbruikt. Een algoritme heeft een looptijd $T(n) = O(F(n))$ als er een geheel getal $N$ en een constante $C$ bestaan zodanig dat de werkelijke stappen begrensd worden door $C \cdot F(n)$ voor alle $n > N$. Deze notatie richt zich op de asymptotische groei; alle constanten worden als equivalent beschouwd.
Dit staat logische luiheid toe. Als we een praktisch snellere FFT willen, zoeken we een algoritme dat minder dan $50n$ operaties vereist voor redelijke waarden van $n$. Maar $O(n)$ betekent niet noodzakelijkerwijs $50n$; het zou ook $10^{80}n$ kunnen betekenen. Een algoritme met zo'n onvoorstelbaar grote verborgen constante wordt een galactisch algoritme genoemd (naar Richard Lipton en Ken Regan).
Het FFT-algoritme van OpenAI is ontegenzeggelijk galactisch. De geschatte waarde voor $C$ was $10^{100}$ bij $N=10^{12}$. Zelfs bij $n=10^{100}$ zou de klassieke Cooley-Tukey-Gauss FFT nog steeds $10^{99}$ keer sneller zijn.
Hoewel het algoritme technisch gezien asymptotisch sneller is dan Cooley-Tukey, zou het pas sneller draaien bij een waarde van $n$ die fysiek onmogelijk is.
Onrealistische rekenmodellen
Lipton en Regan beweren dat galactische algoritmen nuttig zijn omdat ze onderzoek stimuleren naar praktische implementaties. Echter, het rekenmodel dat OpenAI gebruikt, vertoont geen enkele gelijkenis met een echte computer.
De tekst stelt: "Het model gebruikt exacte complexe rekenkunde." Dit veronderstelt dat men complexe getallen met willekeurige precisie kan opslaan en vermenigvuldigen. Het algoritme vereist vermenigvuldigingen van complexe getallen waarvan de grootte superpolynomiaal groeit met $n$. Als deze getallen als bits zouden worden opgeslagen, zou het geheugenbeslag effectief exponentieel zijn ten opzichte van de inputlengte. We hebben geen computers die dit in één operatie kunnen uitvoeren.
Theoretische context
Dat er een absurd rekenmodel nodig is om de FFT-snelheidslimiet te doorbreken, is niet verrassend:
- 1973: Jacques Morgenstern bewees dat een Fourier-transformatie niet sneller kan dan $\frac{1}{2} n \log n$ als de complexe coëfficiënten een begrensde grootte hebben.
- Veertig jaar later: Nir Ailon toonde aan dat een FFT niet sneller kan dan $n \log n$ zonder ernstige numerieke instabiliteit.
Het resultaat van OpenAI is dus minder een wiskundige doorbraak en meer een curiositeit waarbij computerwetenschappers slecht zijn in het formaliseren van hun ontwerpspecificaties.
De cultuur van de theoretische informatica
Veel andere "grote" resultaten in de repository van OpenAI kunnen op dezelfde manier worden bekritiseerd. Zo is er een galactisch algoritme om matrices te vermenigvuldigen in $O(n^{2.25})$ operaties, waarbij de constante $C$ niet eens geschat kan worden [^3].
Het feit dat dergelijke papers in prestigieuze conferenties (zoals STOC of FOCS) zouden kunnen worden gepubliceerd [^4], wijst op een cultuur die het uitvoeren van algoritmen op een computer actief ontmoedigt. Theoretische informatica is een vorm van wiskunde geworden die zich niet langer met computers bezighoudt.
AI is zeer effectief in het automatiseren van onze slechtste neigingen. Het versterkt onuitgesproken culturele praktijken waar niemand van houdt, maar waar niemand individueel van afwijkt. AI kan nu nutteloze theoretische papers schrijven. Misschien kunnen we, in de absurditeit van deze "trash dump" aan bewijzen, inzien dat het tijd is om iets anders te gaan doen.
***
[^1]: Tegenwoordig noemen jongeren dit "cosine similarity". [^2]: De Wikipedia-pagina vermeldt dat de eer naar Gauss in 1805 zou moeten gaan; correcte toeschrijving is een eeuwig probleem in de academische wereld. [^3]: Dit resultaat toont aan dat voor elke $\epsilon > 0$, er een constante $C$ is zodanig dat $T(n) \le n^{2.25 + \epsilon + C/\log(n)}$. Geen enkel OpenAI-model kan een kwantitatieve schatting van $C$ geven. [^4]: Een andere slechte traditie is dat de informatica haar meest prestigieuze podia kiest als hastily reviewed conferentieverslagen.
Snellere Fourier-transformaties
In deze analyse kijken we naar een deel van de wiskunde-repository van OpenAI waarin wordt beweerd dat er snellere Fourier-transformaties kunnen worden berekend. De tekst is technischer dan gebruikelijk, maar bevat uitleg over signaalverwerking en computationele complexiteit voor wie een opfriscursus nodig heeft.
Wat is de Fast Fourier Transform (FFT)?
De Fast Fourier Transform (FFT) is een van de belangrijkste innovaties in digitale signaalverwerking. De FFT is een snelle methode om de frequentie-inhoud van signalen te extraheren, waardoor men snel frequenties over verschillende banden van het spectrum kan analyseren, filteren en manipuleren.
De Fourier-transformatie berekent de energie in elke frequentieband via een eenvoudig inproduct (dot product) [^1]. Stel dat $x$ de input is (een array van $n$ samples) en $f$ een frequentie. De hoeveelheid frequentie-inhoud in $x$ bij $f$ kan worden berekend met een specifieke formule.
Voor digitale signalen blijkt dat je slechts $n$ van deze inproducten hoeft te berekenen (één voor elk veelvoud van de frequentie $2\pi/n$) om alle frequentie-inhoud te begrijpen. Een naïvst benadering vereist $n$ vermenigvuldigingen en optellingen per frequentie. Hierdoor lijkt het berekenen van de volledige Fourier-transformatie $n^2$ rekenoperaties te vereisen.
Het Cooley-Tukey algoritme
De fast Fourier transform is een slimme recursieve procedure, bedacht door James Cooley en John Tukey in 1965 [^2]. Het hoofdidee is dat een Fourier-transformatie van lengte $n$ kan worden berekend door:
- De inputvector te husselen.
- Twee Fourier-transformaties van lengte $n/2$ te berekenen op de gehusselde componenten.
- De resultaten te combineren met behulp van atomaire rekenoperaties.
De husselacties en recombinaties kosten een lineair aantal rekenoperaties. Door deze procedure iteratief te herhalen ($\log2(n)$ keer), wordt de volledige discrete Fourier-transformatie berekend. Inclusief de administratie berekent de FFT een transformatie van lengte $n$ in minder dan $5 n \log2 n$ rekenoperaties.
Concreet versnellingseffect:
- Bij $n = 1.000$ is $n^2 = 1.000.000$, terwijl $5 \cdot n \log n$ ongeveer $50.000$ is (een 20-voudige versnelling).
- Bij $n = 1.000.000$ is de versnelling 10.000-voudig.
Deze versnellingen bepalen vaak of een transformatie überhaupt berekenbaar is binnen de beperkingen van een signaalverwerkingsapplicatie.
De claim van OpenAI
Sinds de uitvinding van de FFT zoeken onderzoekers naar nog snellere varianten. Men vraagt zich af hoe snel het theoretisch kan gaan. Omdat het $n$ stappen kost om de FFT simpelweg op te schrijven, lijkt $n$ operaties de ondergrens. De FFT is $5 \cdot \log_2(n)$ keer trager dan die limiet. Bij $n$ in de biljoenen is die factor ongeveer 200. Kan die prefactor worden verlaagd?
In een recente publicatie van OpenAI beweren zij een snellere Fourier-transformatie te hebben gevonden. In hun document "main.pdf" claimen ze een resultaat waarbij de $\log(n)$-term theoretisch iets kleiner is dan in de standaard FFT.
Ik heb dit document niet op de traditionele manier gelezen. In plaats daarvan heb ik het gevoed aan een chatbot-interface om de belangrijkste feiten te extraheren—in feite vroeg ik ChatGPT wat het van zijn eigen output vond. Dit is hoe wiskundig onderzoek tegenwoordig blijkbaar wordt gedaan.
Het probleem: Galactische Algoritmen
Wat ik vond was geen snellere FFT, maar een voorbeeld van hoe toegepaste wiskundige theorie kan degenereren wanneer formalisme volledig losgekoppeld raakt van de realiteit.
De misleiding van de Big-O notatie
De "Big-O" notatie wordt vaak misbruikt. Een algoritme heeft een looptijd $T(n) = O(F(n))$ als er een geheel getal $N$ en een constante $C$ bestaan zodanig dat de werkelijke stappen begrensd worden door $C \cdot F(n)$ voor alle $n > N$. Deze notatie richt zich op de asymptotische groei; alle constanten worden als equivalent beschouwd.
Dit staat logische luiheid toe. Als we een praktisch snellere FFT willen, zoeken we een algoritme dat minder dan $50n$ operaties vereist voor redelijke waarden van $n$. Maar $O(n)$ betekent niet noodzakelijkerwijs $50n$; het zou ook $10^{80}n$ kunnen betekenen. Een algoritme met zo'n onvoorstelbaar grote verborgen constante wordt een galactisch algoritme genoemd (naar Richard Lipton en Ken Regan).
Het FFT-algoritme van OpenAI is ontegenzeggelijk galactisch. De geschatte waarde voor $C$ was $10^{100}$ bij $N=10^{12}$. Zelfs bij $n=10^{100}$ zou de klassieke Cooley-Tukey-Gauss FFT nog steeds $10^{99}$ keer sneller zijn.
Hoewel het algoritme technisch gezien asymptotisch sneller is dan Cooley-Tukey, zou het pas sneller draaien bij een waarde van $n$ die fysiek onmogelijk is.
Onrealistische rekenmodellen
Lipton en Regan beweren dat galactische algoritmen nuttig zijn omdat ze onderzoek stimuleren naar praktische implementaties. Echter, het rekenmodel dat OpenAI gebruikt, vertoont geen enkele gelijkenis met een echte computer.
De tekst stelt: "Het model gebruikt exacte complexe rekenkunde." Dit veronderstelt dat men complexe getallen met willekeurige precisie kan opslaan en vermenigvuldigen. Het algoritme vereist vermenigvuldigingen van complexe getallen waarvan de grootte superpolynomiaal groeit met $n$. Als deze getallen als bits zouden worden opgeslagen, zou het geheugenbeslag effectief exponentieel zijn ten opzichte van de inputlengte. We hebben geen computers die dit in één operatie kunnen uitvoeren.
Theoretische context
Dat er een absurd rekenmodel nodig is om de FFT-snelheidslimiet te doorbreken, is niet verrassend:
- 1973: Jacques Morgenstern bewees dat een Fourier-transformatie niet sneller kan dan $\frac{1}{2} n \log n$ als de complexe coëfficiënten een begrensde grootte hebben.
- Veertig jaar later: Nir Ailon toonde aan dat een FFT niet sneller kan dan $n \log n$ zonder ernstige numerieke instabiliteit.
Het resultaat van OpenAI is dus minder een wiskundige doorbraak en meer een curiositeit waarbij computerwetenschappers slecht zijn in het formaliseren van hun ontwerpspecificaties.
De cultuur van de theoretische informatica
Veel andere "grote" resultaten in de repository van OpenAI kunnen op dezelfde manier worden bekritiseerd. Zo is er een galactisch algoritme om matrices te vermenigvuldigen in $O(n^{2.25})$ operaties, waarbij de constante $C$ niet eens geschat kan worden [^3].
Het feit dat dergelijke papers in prestigieuze conferenties (zoals STOC of FOCS) zouden kunnen worden gepubliceerd [^4], wijst op een cultuur die het uitvoeren van algoritmen op een computer actief ontmoedigt. Theoretische informatica is een vorm van wiskunde geworden die zich niet langer met computers bezighoudt.
AI is zeer effectief in het automatiseren van onze slechtste neigingen. Het versterkt onuitgesproken culturele praktijken waar niemand van houdt, maar waar niemand individueel van afwijkt. AI kan nu nutteloze theoretische papers schrijven. Misschien kunnen we, in de absurditeit van deze "trash dump" aan bewijzen, inzien dat het tijd is om iets anders te gaan doen.
***
[^1]: Tegenwoordig noemen jongeren dit "cosine similarity". [^2]: De Wikipedia-pagina vermeldt dat de eer naar Gauss in 1805 zou moeten gaan; correcte toeschrijving is een eeuwig probleem in de academische wereld. [^3]: Dit resultaat toont aan dat voor elke $\epsilon > 0$, er een constante $C$ is zodanig dat $T(n) \le n^{2.25 + \epsilon + C/\log(n)}$. Geen enkel OpenAI-model kan een kwantitatieve schatting van $C$ geven. [^4]: Een andere slechte traditie is dat de informatica haar meest prestigieuze podia kiest als hastily reviewed conferentieverslagen.
Groetjes,