Kutatás
Gyorsabb FFT az OpenAI-tól? Egy elemzés szerint csak papíron működik
Az OpenAI által közzétett matematikai anyagban egy, a gyors Fourier-transzformációnál elméletben gyorsabb algoritmus is szerepel. Az argmin.net blog szerzője szerint azonban ez az eredmény csak elképzelhetetlenül nagy bemeneteknél és nem létező számítógépeken lenne előnyös.
Miért nagy szó az FFT?
A Fourier-transzformáció egy jelet, például hangot vagy képet, frekvenciaösszetevőire bont. A modern jelfeldolgozás, a tömörítés és a tudományos számítások jelentős része erre épül. A gyors változatot, az FFT-t James Cooley és John Tukey dolgozta ki 1965-ben. Ez egy n hosszú transzformációt kevesebb mint 5 n log2 n aritmetikai művelettel számol ki, szemben a naiv módszer n² műveletével. Nagy adatsoroknál ez óriási különbség, ezért tartják az FFT-t a számítástechnika egyik legfontosabb algoritmusának. Ha valaki ezt érdemben megverné, annak komoly gyakorlati következményei lennének.
A blogbejegyzés szerint ugyanakkor erről szó sincs. Az elméleti informatikában az algoritmusok gyorsaságát gyakran aszimptotikusan, úgynevezett big-O jelöléssel írják le: ez azt mutatja meg, hogyan nő a futásidő, ha a bemenet a végtelenhez tart, de elrejti a konstans szorzókat. Egy aszimptotikusan jobb algoritmus is lehet a gyakorlatban reménytelenül lassabb, ha a rejtett konstans hatalmas.
Egy googolnyi adatnál is lassabb lenne
A szerző becslése szerint az OpenAI módszerében ez a konstans nagyjából 10^100 is lehet (egy N=10^12 paraméterértéknél). Ez annyit jelent, hogy még egy 10^100 elemű, vagyis a megfigyelhető univerzum atomjainak számát is messze meghaladó adatsornál is a klasszikus Cooley–Tukey FFT lenne nagyjából 10^99-szer gyorsabb. Az ilyen, csak csillagászati méreteknél előnyös eljárásokat nevezik a szakmában galaktikus algoritmusnak.
A másik kifogás a számítási modellre vonatkozik. Az elemzés szerint a módszer egzakt, tetszőleges pontosságú komplex aritmetikát feltételez, és egyetlen lépésben szoroz össze szuperpolinomiálisan növekvő nagyságú komplex számokat. Valódi számítógépen ez nem valósítható meg, hiszen a hardver véges pontossággal dolgozik. A szerző korábbi eredményekre is hivatkozik: Morgenstern 1973-ban bizonyította, hogy korlátos együtthatókkal nem lehet ½ n log n-nél gyorsabb Fourier-transzformációt végezni, Nir Ailon pedig később kimutatta, hogy n log n-nél gyorsabb eljárás csak súlyos numerikus instabilitás árán lehetséges. Az OpenAI anyagában a blog szerint egy O(n^2.25) idejű mátrixszorzási algoritmus is szerepel, ennek rejtett konstansát viszont nem lehet megbecsülni.
Óvatosan a kritikával is
A bejegyzés tágabb üzenete, hogy az aszimptotikus eredmények könnyen elszakadhatnak a valódi számítógépektől, és a mesterséges intelligencia akár tömegesen is gyárthat ilyen, gyakorlatban kevéssé hasznos elméleti cikkeket. Érdemes azonban az elemzést is fenntartással kezelni. Véleménycikkről van szó, amelynek szerzője saját bevallása szerint nem olvasta el a dolgozatot, hanem ChatGPT-vel foglaltatta össze, így a konstansbecslések megbízhatósága kérdéses. A szerző neve a szövegben nem szerepel, a blog alapján valószínűleg Ben Recht.
Sok kérdés nyitott marad. Az OpenAI eredeti állítását nem ellenőriztük elsődleges forrásból, és a blog szerint az FFT-ről szóló rész egy „main.pdf” nevű dokumentumban található, ennek pontos helyét azonban nem tudtuk megerősíteni. Nem ismert az sem, hivatalosan hogyan kommentálta a cég az anyagot. Végül az sem tisztázott, helyes-e egyáltalán a bizonyítás: a blog szerint ezt jelenleg senki sem tudja biztosan, így az állítás valódi súlyáról csak a szakértői átvizsgálás után lehet majd megalapozottan beszélni.