Deep Mind AlphaTensor الگوریتم های جدیدی را کشف خواهد کرد

Deep Mind AlphaZero را به ریاضیات تعمیم داده است تا امکانات جدیدی را برای الگوریتم های تحقیقاتی باز کند.

AlphaTensor بر پایه AlphaZero ساخته شده است، عاملی که عملکرد فوق بشری را در بازی های روی تخته مانند شطرنج، Go و شوگی نشان داده است، و این کار سفر AlphaZero را از بازی کردن تا مقابله با مسائل حل نشده ریاضی برای اولین بار نشان می دهد.

مصریان باستان الگوریتمی برای ضرب دو عدد بدون نیاز به جدول ضرب ایجاد کردند و ریاضیدان یونانی اقلیدس الگوریتمی را برای محاسبه بزرگترین مقسوم علیه رایج توصیف کرد که امروزه نیز مورد استفاده قرار می گیرد.

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

آنها در Nature منتشر کردند. AlphaTensor اولین سیستم هوش مصنوعی (AI) برای کشف الگوریتم‌های جدید، کارآمد و قابل اثبات صحیح برای کارهای اساسی مانند ضرب ماتریس است. این یک سوال باز 50 ساله در ریاضیات را در مورد یافتن سریعترین راه برای ضرب دو ماتریس روشن می کند.

AlphaTensor که از ابتدا آموزش دیده است، الگوریتم های ضرب ماتریس را کشف می کند که کارآمدتر از الگوریتم های طراحی شده توسط انسان و کامپیوتر موجود هستند. علی‌رغم بهبود الگوریتم‌های شناخته‌شده، آنها خاطرنشان می‌کنند که محدودیت AlphaTensor نیاز به از پیش تعریف مجموعه‌ای از ورودی‌های فاکتور بالقوه F است که فضای جستجو را گسسته می‌کند اما احتمالاً می‌تواند منجر به از دست دادن الگوریتم‌های کارآمد شود. یک جهت جالب برای تحقیقات آینده، تطبیق AlphaTensor برای جستجوی F است. یکی از نقاط قوت AlphaTensor انعطاف پذیری آن برای پشتیبانی از پاداش های پیچیده تصادفی و غیرقابل تمایز (از رتبه تانسور تا کارایی عملی در سخت افزار خاص)، علاوه بر یافتن الگوریتم ها است. برای عملیات سفارشی در طیف گسترده ای از فضاها (مانند فیلدهای محدود). آنها بر این باورند که این امر کاربردهای AlphaTensor را به سمت طراحی الگوریتم‌هایی سوق می‌دهد که معیارهایی را که در اینجا در نظر نگرفتیم، مانند پایداری عددی یا مصرف انرژی، بهینه‌سازی می‌کنند.

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

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

این بازی فوق‌العاده چالش برانگیز است - تعداد الگوریتم‌های ممکن برای در نظر گرفتن بسیار بیشتر از تعداد اتم‌های جهان است، حتی برای موارد کوچک ضرب ماتریس. در مقایسه با بازی Go، که برای دهه‌ها چالشی برای هوش مصنوعی باقی ماند، تعداد حرکات ممکن در هر مرحله از بازی آنها 30 مرتبه بزرگتر است (برای یکی از تنظیماتی که در نظر می‌گیرند بالای 10^33).

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

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

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

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

در حالی که آنها در اینجا بر روی مشکل خاص ضرب ماتریس تمرکز کردند، ما امیدواریم که مقاله ما الهام بخش دیگران در استفاده از هوش مصنوعی برای هدایت کشف الگوریتمی برای سایر وظایف محاسباتی اساسی باشد. تحقیقات آنها همچنین نشان می دهد که AlphaZero یک الگوریتم قدرتمند است که می تواند فراتر از دامنه بازی های سنتی گسترش یابد تا به حل مسائل باز در ریاضیات کمک کند. با تکیه بر تحقیقات ما، آنها امیدوارند که کارهای بیشتری را انجام دهند - استفاده از هوش مصنوعی برای کمک به جامعه برای حل برخی از مهم ترین چالش ها در ریاضیات و در سراسر علوم.

طبیعت - کشف الگوریتم‌های ضرب ماتریس سریع‌تر با یادگیری تقویتی

چکیده
بهبود کارایی الگوریتم‌ها برای محاسبات اساسی می‌تواند تأثیر گسترده‌ای داشته باشد، زیرا می‌تواند بر سرعت کلی حجم زیادی از محاسبات تأثیر بگذارد. ضرب ماتریس یکی از این وظایف ابتدایی است که در بسیاری از سیستم ها رخ می دهد - از شبکه های عصبی گرفته تا روال های محاسباتی علمی. کشف خودکار الگوریتم‌ها با استفاده از یادگیری ماشین، چشم‌انداز فراتر از شهود انسانی و عملکرد بهتر از بهترین الگوریتم‌های طراحی‌شده توسط انسان را ارائه می‌دهد. با این حال، خودکار کردن روش کشف الگوریتم پیچیده است، زیرا فضای الگوریتم‌های ممکن بسیار زیاد است. در اینجا ما یک رویکرد یادگیری تقویتی عمیق مبتنی بر AlphaZero1 را برای کشف الگوریتم‌های کارآمد و قابل اثبات صحیح برای ضرب ماتریس‌های دلخواه گزارش می‌کنیم. عامل ما، AlphaTensor، برای انجام یک بازی تک نفره آموزش دیده است که هدف آن یافتن تجزیه تانسور در یک فضای عامل محدود است. AlphaTensor الگوریتم هایی را کشف کرد که برای بسیاری از اندازه های ماتریس از پیچیدگی های پیشرفته بهتر عمل می کنند. خصوصاً مورد مربوط به ماتریس‌های 4×4 در یک میدان محدود است، که در آن الگوریتم AlphaTensor برای اولین بار از زمان کشف آن در 50 سال پیش، الگوریتم دو سطحی Strassen را بهبود می‌بخشد. ما بیشتر انعطاف‌پذیری AlphaTensor را از طریق موارد استفاده مختلف نشان می‌دهیم: الگوریتم‌هایی با پیچیدگی پیشرفته برای ضرب ماتریس ساخت‌یافته و بهبود کارایی عملی با بهینه‌سازی ضرب ماتریس برای زمان اجرا بر روی سخت‌افزار خاص. نتایج ما توانایی AlphaTensor را برای تسریع فرآیند کشف الگوریتمی در طیف وسیعی از مسائل و بهینه‌سازی برای معیارهای مختلف برجسته می‌کند.