نگاهی به ریاضیاتی که OpenAI ادعا می کند تبدیل های فوریه را سریعتر محاسبه می کند

سلام، خوانندگان آرگمین! پست امروز به بخشی از مخزن ریاضی OpenAI نگاه می کند که ادعا می کند تبدیل فوریه سریعتر را محاسبه می کند. فنی‌تر از حد معمول است، اما من سعی کردم برای افرادی که نیاز به یک دوره آموزشی تکمیلی در مورد پردازش سیگنال یا پیچیدگی محاسباتی دارند، مطالب آموزشی اضافه کنم.

تبدیل فوریه سریع یکی از مهم ترین نوآوری ها در پردازش سیگنال دیجیتال و یکی از الگوریتم های مورد علاقه من است. FFT راهی سریع برای استخراج محتوای فرکانس سیگنال ها است که به شما امکان می دهد فرکانس ها را در باندهای مختلف طیف به سرعت تجزیه و تحلیل، فیلتر و دستکاری کنید.

تبدیل فوریه انرژی را در هر باند فرکانسی از طریق یک محصول نقطه‌ای ساده محاسبه می‌کند. 1 اجازه دهید x ورودی شما، طول n آرایه از نمونه ها، و f فرکانس را نشان دهد. سپس مقدار فرکانس x در f را می توان با فرمول محاسبه کرد:

برای سیگنال های دیجیتال، کمی ریاضی نشان می دهد که شما فقط باید n از این محصولات نقطه ای را محاسبه کنید، یکی در هر مضربی از فرکانس 2𝜋/n، تا همه محتوای فرکانس را درک کنید. ساده لوحانه، این نیاز به n ضرب و جمع برای هر فرکانس دارد. بنابراین، محاسبه کل تبدیل فوریه به n 2 عملیات حسابی نیاز دارد.

تبدیل فوریه سریع یک روش بازگشتی هوشمندانه است که توسط جیمز کولی و جان توکی در سال 1965 ابداع شد. 2 ایده اصلی این است که یک تبدیل فوریه طول-n را می توان با به هم زدن بردار ورودی، محاسبه دو تبدیل فوریه به طول n/2 بر روی مولفه های به هم ریخته، و سپس با استفاده از عملیات اتمی یک خروجی محاسبه کرد. درهم آمیختگی ها و نوترکیبی ها تعداد خطی عملیات حسابی را انجام می دهند. تکرار این رویه به صورت مکرر، یعنی log 2 (n) بار، تبدیل فوریه گسسته کامل را محاسبه می کند.

با حسابداری، FFT یک تبدیل فوریه طول-n را در کمتر از 5 n log2 n عملیات حسابی محاسبه می کند.

برای بتن ریزی این شتاب، وقتی n 1000 باشد، n^2 برابر با 1000000 و 5*n log n حدود 50000 است که یک افزایش سرعت 20 برابری است. وقتی n 1,000,000 باشد، افزایش سرعت 10000 برابر می شود. این افزایش‌ها می‌توانند تفاوت بین یک تبدیل قابل محاسبه یا عدم توجه به محدودیت‌های یک برنامه پردازش سیگنال باشند.

از زمان اختراع FFT، مردم به دنبال تبدیل فوریه حتی سریعتر بودند. یک سوال این است که چقدر سریع می توانید پیش بروید. به نظر می رسد که برای محاسبه FFT احتمالا به حداقل n عملیات نیاز دارید، زیرا فقط نوشتن آن n مرحله طول می کشد. FFT 5*log 2 (n) برابر کمتر از حد معقول سرعت است و این فاکتور 5*log 2 (n) می تواند بزرگ باشد. وقتی n یک تریلیون باشد 200 است. آیا می توانید کاری هوشمندانه برای کاهش آن پیش فاکتور 200 انجام دهید؟

خوب، ببینید، در زباله ی عظیمی که OpenAI هفته گذشته دنیای ریاضیات را درگیر کرد، آنها ادعا می کنند که تبدیل فوریه سریع تری دارند. ادعای اصلی آنها با نام تبعیض آمیز "main.pdf" این است

کنجکاو شدم که اینجا چه خبر است. اصطلاح log(n) در تئوری، کمی کوچکتر از FFT استاندارد بود.

آیا من این مقاله را خواندم؟ البته نه. هیچ کس در OpenAI نیز این مقاله را نخواند، پس چرا من باید این مقاله را بخوانم؟ من کاری را انجام دادم که هر ریاضی دان دیگری در جهان با ریاضیات شیب هوش مصنوعی انجام می دهد: آن را دوباره به دستگاه اسلوپ برگرداندم و یک جلسه بازیابی اطلاعات را با رابط چت بات برای استخراج حقایق برجسته اجرا کردم. از نظر انسان‌شناسی: از ChatGPT پرسیدم که درباره خروجی خود چه فکر می‌کند. ما اکنون تحقیقات ریاضی را اینگونه انجام می دهیم. چه دنیایی

متأسفانه، من تبدیل فوریه سریعتر پیدا نکردم. درعوض، زمانی که فرمالیسم چنان از واقعیت جدا می‌شود، پوسیدگی را یافتم که در درون نظریه ریاضی کاربردی ایجاد می‌شود که «شکوفایی» چیزی نیست جز مصنوع ریاضیدانان که نمی‌توانند به درستی قواعد بازی‌هایشان را به زبان طبیعی مشخص کنند.

اول، نماد "big-O" به قدری مورد سوء استفاده قرار گرفته است که بی معنی شده است. بیایید این تعریف را مرور کنیم، که من را به عنوان یک دانشجو تحت تاثیر قرار داد. یک الگوریتم زمان اجرای T(n) = O(F(n)) دارد اگر یک عدد صحیح N و یک ثابت C وجود داشته باشد به طوری که

یعنی تعداد مراحلی که الگوریتم عملا انجام می‌دهد، تا زمانی که n بزرگ باشد، با یک عدد ثابت ضربدر برخی از تابع مناسب F(n) محدود می‌شود. F(n) معمولا چیزی آشنا و قابل تفسیر است، مانند یک تابع چند جمله ای یا نمایی. این نماد می گوید که ما فقط به این اهمیت می دهیم که وقتی اندازه محاسبات بزرگ باشد چه اتفاقی می افتد. ما به نرخ رشد مجانبی زمان محاسبه اهمیت می دهیم. همه ثابت ها معادل هستند.

نماد Big-O برای میانبرها در حسابداری الگوریتمی مفید است، اما تنبلی منطقی قابل توجهی را نیز امکان پذیر می کند. اگر FFT عملا سریع‌تر می‌خواهیم، ​​الگوریتمی می‌خواهیم که برای n با اندازه معقول به کمتر از 50n عملیات نیاز دارد. اما O(n) به معنای 50 n نیست. می تواند به معنای 10 80 n باشد. این یک الگوریتم "زمان خطی" در نظر گرفته می شود. الگوریتمی که به n + 10 80 نیاز دارد نیز یک الگوریتم زمان خطی در رژیم big-O در نظر گرفته می شود. الگوریتمی که فقط زمانی که n بزرگتر از 10 80 باشد ضمانت زمان خطی داشته باشد نیز زمان خطی در نظر گرفته می شود.

10 80 تقریبا برابر با تعداد اتم های جهان شناخته شده است. به همین دلیل است که ریچارد لیپتون و کن ریگان الگوریتم هایی با ثابت های پنهان غیرقابل درک بزرگ را الگوریتم های کهکشانی می نامند.

الگوریتم OpenAI FFT قطعا کهکشانی است. مقادیر تخمینی برای C 10100 بود که N=1012 بود. بنابراین حتی زمانی که n=10 100 باشد، FFT محترم Cooley-Tukey-Gauss 1099 برابر سریعتر خواهد بود.

پس چرا این نتیجه جدید FFT جالب است؟ خوب، توجه داشته باشید که در نمادگذاری big-O، از نظر تکنیکی مجانبی سریعتر از الگوریتم کولی-توکی است زیرا

یعنی حتما اما با توجه به ثابت‌ها، الگوریتم تنها زمانی سریع‌تر اجرا می‌شود که n غیرممکن باشد. تقریبا، شما نیاز دارید

لیپتون و ریگان استدلال می کنند که الگوریتم های کهکشانی مفید هستند زیرا آنها تحقیقات را تحریک می کنند. هنگامی که نشان دادید زمان اجرا به طور مجانبی امکان پذیر است، می توانید زمان خود را صرف یافتن الگوریتمی کنید که عملا به این زمان اجرا قابل اثبات برسد. شاید بتوانید عامل هوش مصنوعی خود را به دنبال آن بفرستید. شما انجام می دهید. شاید بتوانید یک الگوریتم عملی به دست آورید، اما من هیچ نمونه قانونی را نمی دانم که در آن این اتفاق افتاده است. من به خصوص در اینجا تردید دارم، زیرا مدل «محاسبات» OpenAI که از OpenAI استفاده می‌کند هیچ شباهتی به یک رایانه واقعی ندارد.

"این مدل از محاسبات پیچیده دقیق استفاده می کند." این بدان معناست که فرض می‌کند می‌توانید اعداد مختلط را با دقت دلخواه ذخیره و ضرب کنید. در واقع، الگوریتم از شما می‌خواهد اعداد مختلط را که بزرگی آنها به صورت ابرچندجمله‌ای با n افزایش می‌یابد ضرب کنید. اگر این اعداد را به صورت بیت ذخیره کنید، نیاز به حافظه عملا در طول ورودی نمایی خواهد بود. فرض بر این است که شما می توانید چنین اعداد مختلط دلخواه خود را در یک عملیات واحد ضرب کنید. ما کامپیوتری نداریم که بتواند این کار را انجام دهد.

بنابراین حتی اگر این قضیه در main.pdf "درست" باشد (هیچ کس نمی داند، و من اهمیتی نمی دهم)، در واقع مشکلی را که ما در جستجوی یک FFT سریعتر برای حل آن هستیم، حل نمی کند.

برای افرادی که با تحلیل های نظری FFT آشنا هستند، اینکه برای شکستن محدودیت سرعت FFT به یک مدل محاسباتی پوچ نیاز دارید، تعجب آور نیست. در سال 1973، ژاک مورگنسترن ثابت کرد که نمی‌توانید تبدیل فوریه را سریع‌تر از ½ n log n دریافت کنید، اگر بخواهید ضرایب پیچیده مورد استفاده در محاسبات دارای قدر محدود باشند. این باید پایان داستان بود! اما اینطور نبود. مردم گفتند مدل ضریب محدود مورگنسترن بسیار محدود کننده است.

چهل سال بعد، Nir Ailon نشان داد که نمی‌توانید FFT را سریع‌تر از n log n بدون ناپایداری‌های عددی شدید محاسبه کنید. حدس می‌زنم این نیز برای برخی افراد بسیار محدودکننده بود.

بنابراین، این نتیجه OpenAI جدید کمتر یک پیشرفت ریاضی است و بیشتر عجیب است که دانشمندان کامپیوتر در رسمی کردن مشخصات طراحی خود بد هستند. تعریف «تئوری» رایانه با رایانه هایی که ما واقعا می سازیم بسیار فاصله دارد. تبدیل فوریه «سریع‌تر» صرفا نمونه‌ای است که در آن نظریه چنان از سؤال اصلی دور می‌شود که «مشکل باز» چیزی بیش از یک معمای وضعیت تحصیلی نمی‌شود. راه حل مانند چیزی است که وقتی جریان های ربات محاسباتی را روی مشکلات غیرممکن تنظیم می کنید و آنها را درگیر هک غیرقانونی می بینید اتفاق می افتد.

بسیاری از نتایج "بزرگ" دیگر در این slopository OpenAI را می توان به همین روش مورد نقد قرار داد. برای مثال، یکی از آن نتایج یک الگوریتم کهکشانی برای ضرب دو ماتریس در عملیات O(n^2.25) بود. ساختار استفاده شده در مقاله به شما اجازه نمی دهد حتی ثابتی را که درون O بزرگ پنهان شده است تخمین بزنید.

با این حال، اگر به طور قابل ملاحظه ای بهتر نوشته می شد، این مقالات آن را به معتبرترین مکان های انتشار برای نظریه علوم کامپیوتر تبدیل می کردند (به عنوان مثال، مقالات کنفرانس داوری از STOC یا FOCS). 4 مقاله ضرب ماتریسی احتمالا جوایزی را کسب می کرد. اما هیچ کدام از اینها ربطی به کامپیوتر ندارند!

این به این دلیل است که نظریه علوم کامپیوتر دارای فرهنگی است که به طور فعال الگوریتم‌ها را بر روی رایانه اجرا نمی‌کند. نوشتن مقالاتی در کنفرانس های تئوری که ادعا می کنند الگوریتمی وجود دارد بدون نوشتن آن قابل قبول است. تئوری علوم کامپیوتر به شکلی از ریاضیات تبدیل شده است که به کامپیوترها ربطی ندارد، و پاداش کمی برای تاثیر خارج از آن رشته های ریاضی ارائه می دهد. من این را برای دوستی توضیح دادم که به من گفت که «نظریه» معنای فرارشته‌ای «پنهان شدن در ابهام ساخته خود» دارد.

هوش مصنوعی واقعا در خودکارسازی بدترین تمایلات ما خوب است. این شیوه‌های فرهنگی ناگفته را تقویت می‌کند که هیچ‌کس دوست ندارد، اما هیچ فردی نمی‌تواند به طور منطقی از آنها منحرف شود. از سنت‌های مکانیزه‌ای که نسبت به کنش جمعی سرپیچی می‌کنند، بهره‌برداری می‌کند. در این راستا، هوش مصنوعی اکنون می تواند مقالات تئوری بی فایده بنویسد. اما شاید در پوچ بودن سطل زباله OpenAI ناخوشایند از شواهد، همه ما می‌توانیم به دنبال آن باشیم و با هم متوجه شویم که باید کار دیگری را انجام دهیم.

صفحه ویکی پدیا می گوید که باید آن را به گاوس در سال 1805 نسبت داد! تخصیص صحیح اعتبار یک مشکل همیشگی در دانشگاه است.

آن یکی نشان می دهد که برای هر اپسیلون بزرگتر از 0، یک C ثابت وجود دارد به طوری که T(n) <= n^(2.25 +epsilon + C/log(n)). مهم نیست که کدام پرسش‌ها را امتحان می‌کنم، نمی‌توانم یک مدل OpenAI برای ارائه تخمین کمی از C دریافت کنم.

یکی دیگر از سنت‌های بد، انتخاب معتبرترین مکان‌های علم کامپیوتر به‌عنوان جلسات بررسی عجولانه کنفرانس است.