OpenAI FFT algoritmi: muhim yutuqmi yoki yomon foydalanish?

Salom, iportal-ai o'quvchilari! Bugun biz OpenAI tomonidan taqdim etilgan tez Fourier transformasi (FFT) algoritmi haqida gaplashamiz. Bu mavzu juda texnik bo'lib, lekin biz sizga signal ishlash va hisoblash murakkabligini qayta o'rganish uchun bir nechta darslik materiallarini qo'shdik.

Fourier transformasi va uning ahamiyati

Tez Fourier transformasi (FFT) raqamli signal ishlashning eng muhim innovatsiyalaridan biridir. FFT signalning chastota tarkibini tezda aniqlash imkonini beradi, bu esa signalni tahlil qilish, filtrlash va chastota bandlarini boshqarish imkonini beradi.

Fourier transformasi signalning har bir chastota bandidagi energiyani aniqlash uchun oddiy dot productdan foydalanadi. Agar x sizning kirish signalingiz bo'lsa, n uzunlikdagi namunalardan iborat bo'lsa va f chastota bo'lsa, x signalining f chastotadagi chastota tarkibi quyidagi formuladan aniqlanadi:

Digital signal uchun, bir oz matematik hisoblash shuni ko'rsatadiki, siz faqat n ta dot productni hisoblashingiz kerak, har bir chastota 2𝜋/n ko'paytmasida, barcha chastota tarkibini tushunish uchun. Naiv usulda, bu har bir chastota uchun n ta ko'paytirish va qo'shishni talab qiladi. Shu sababli, butun Fourier transformasini hisoblash n^2 arifmetik operatsiyalarni talab qiladi.

Tez Fourier transformasi (FFT)

Tez Fourier transformasi (FFT) 1965-yilda James Cooley va John Tukey tomonidan ixtiro qilingan ajoyib takroriy usuldir. Asosiy gʻoya shundaki, uzunlik-n Fourier transformasi kirish vektorini aralashtirib, aralashtirilgan komponentlarga ikkita uzunlik-n/2 Fourier transformasini hisoblab, keyin esa atomik arifmetik operatsiyalarni ishlatib natijalarni qayta birlashtirish orqali hisoblash mumkin. Aralashtirishlar va qayta birlashtirishlar linearning arifmetik operatsiyalarni talab qiladi. Bu usulni takrorlash, ya'ni log2(n) marta, butun diskret Fourier transformasini hisoblash imkonini beradi. Hisoblash bilan, FFT uzunlik-n Fourier transformasini 5n log2(n) dan kam arifmetik operatsiyalar bilan hisoblaydi.

Bu tezlashtirishni aniqlashtirish uchun, agar n 1000 bo'lsa, n^2 1,000,000 va 5 * n log n taxminan 50,000 ga teng, bu 20 marta tezlashtirishdir. Agar n 1,000,000 bo'lsa, tezlashtirish 10,000 marta bo'ladi. Bu tezlashtirishlar signal ishlash ilovasi cheklovlari bilan bog'liq holda transformani hisoblash mumkin yoki mumkin emasligini belgilaydi.

OpenAI FFT algoritmi

FFT ixtiro qilinganidan beri, odamlar hatto tezroq Fourier transformalarni qidirishgan. Bir savol shundaki, qanchalik tez bo'lish mumkin. Tezroq FFT algoritmi uchun kamida n operatsiyalar talab qilinishi mumkin, chunki uni yozish uchun n bosqich talab qilinadi. FFT 5*log2(n) marta bu muqobil tezlik cheklovidan sekinroq, va bu 5*log2(n) koeffitsiyenti katta bo'lishi mumkin. U 200 ga teng bo'lsa, n trillion bo'lsa.

Endi, shunday qilib, OpenAI o'tgan hafta matematika dunyosi uchun katta maqolalar yukladi, ular tezroq Fourier transformasi borligini da'vo qilishdi. Ularning "main.pdf" deb nomlangan asosiy da'vosi shundaki:

Men bu maqolani qiziqish bilan o'qidim. Log(n) atamasi nazariy jihatdan standart FFT dan biroz kichikroq edi.

Men bu maqolani o'qidimmi? Albatta, yo'q. OpenAIda hech kim bu maqolani o'qimagan, shuning uchun men ham o'qimayman? Men butun dunyo bo'ylab har bir matematikning AI slop matematikasiga nima qilishini qildim: men uni slop mashinasiga qaytardim va chatbot interfeysi orqali ma'lumot olish sessiyasini o'tkazdim. Antropomorfik jihatdan: men ChatGPT dan o'z chiqishlari haqida nima o'ylayotganini so'radim. Shunday qilib, biz hozirgi kunda matematika tadqiqotlarini olib boramiz. Qanday dunyo!

Afsuski, men tezroq Fourier transformasini topmadim. Buning o'rniga, men formalizm realdan juda uzoqlashganda, "yutuq" faqat matematiklar o'z o'yinlari qoidalarini tabiiy tilda to'g'ri belgilay olmasligi natijasida paydo bo'lgan chivinni topdim.

Birinchidan, "big-O" notatsiyasi juda ko'p ishlatilganligi sababli, ma'nosi yo'qolgan. Keling, uni qayta ko'rib chiqamiz, bu meni talabalarimda hayratga solgan. Algoritmning ish vaqtini T(n) = O(F(n)) deb belgilash mumkin, agar mavjud bo'lsa N butun soni va C doimiysi shundayki:

Ya'ni, algoritmning haqiqiy qanchalik qadamni olishi, doimiy sonning ba'zi qulay funksiyaga ko'paytmasidan katta bo'lmasligi kerak, agar n katta bo'lsa. F(n) odatda tanish va tushunarli narsadir, masalan, polinom yoki eksponensial funksiyalar. Bu notatsiya faqat katta hisoblash hajmi bo'lganida nima sodir bo'lishini aytadi. Biz hisoblash vaqtining asimptotik o'sish tezligini qiziqtiramiz. Barcha doimiy sonlar teng hisoblanadi.

Big-O notatsiyasi algoritmik hisobda qisqa yo'llarni berish uchun foydali, lekin u juda katta logik tanaffusga imkon beradi. Agar biz amaliy jihatdan tezroq FFT xohlasak, biz 50n dan kamroq operatsiyalar talab qiladigan algoritmni xohlaymiz. Lekin O(n) 50n degani emas. U 1080n bo'lishi mumkin. Bu "linear vaqt" algoritmi deb hisoblanadi. N+1080 operatsiyalar talab qiladigan algoritm ham big-O rejimida "linear vaqt" algoritmi hisoblanadi. N 1080 dan katta bo'lsa, faqat linear vaqt kafolatlarini beradigan algoritm ham linear vaqt deb hisoblanadi. 1080 taxminan ma'lum bo'lgan barcha atomlar soniga teng. Shu sababli Richard Lipton va Ken Regan galaktik algoritmlar deb ataydilar.

OpenAI FFT algoritmi aniq galaktikdir. N=10^12 bo'lganida C qiymatlari 10^100 edi. Shu sababli, hatto n=10^100 bo'lsa ham, qadimiy Cooley-Tukey-Gauss FFT 10^99 marta tezroq bo'ladi.

Shunday qilib, bu yangi FFT natijasi nima uchun qiziq? Ha, big-O notatsiyasida, u texnik jihatdan Cooley-Tukey algoritmidan asimptotik jihatdan tezroqdir, chunki:

Ya'ni, ha, lekin doimiy sonlarga ko'ra, algoritm faqat n juda katta bo'lganida tezroq ishlaydi. Taxminan, sizga kerak:

Lipton va Regan galaktik algoritmlar ilmiy tadqiqotlarni rag'batlantiradi, degan fikrni bildiradilar. Bir marta sizning ish vaqtingiz asimptotik jihatdan mumkinligini ko'rsatganingizdan so'ng, siz bu isbotlangan ish vaqtini amaliy jihatdan erishadigan algoritmni topishga vaqt sarflashingiz mumkin. Belki siz AI agentlari qo'rqog'ini bu ishga yuborasiz. Siz qiling. Belki siz amaliy algoritmni chiqarsiz, lekin men bilmayman.

Asl manba: argmin.net