هوش مصنوعی احتمالات جدیدی را در ضرب ماتریس نشان می دهد

ریاضیدانان عاشق یک پازل خوب هستند. حتی چیزی به انتزاعی مانند ضرب ماتریس ها (جدول دو بعدی اعداد) می تواند شبیه یک بازی باشد وقتی سعی می کنید کارآمدترین راه را برای انجام آن پیدا کنید. این کمی شبیه تلاش برای حل مکعب روبیک در کمترین حرکت ممکن است - چالش برانگیز، اما جذاب. با این تفاوت که برای یک مکعب روبیک، تعداد حرکات ممکن در هر مرحله 18 است. برای ضرب ماتریس، حتی در موارد نسبتاً ساده، هر مرحله می تواند بیش از 10 را نشان دهد¹² گزینه.

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

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

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

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

ضرب ماتریس ها

ضرب ماتریس یکی از اساسی ترین و فراگیرترین عملیات در تمام ریاضیات است. برای ضرب یک جفت از n-توسط-n ماتریس ها، هر کدام با n² عناصر، شما این عناصر را ضرب کرده و در ترکیبات خاصی با هم جمع می کنید تا محصول، یک سوم تولید شود n-توسط-n ماتریس دستور استاندارد ضرب دو n-توسط-n ماتریس ها نیاز دارد n³ عملیات ضرب، بنابراین یک ماتریس 2 در 2، برای مثال، به هشت ضرب نیاز دارد.

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

اگر بخواهید یک جفت ماتریس 2 در 2 را ضرب کنید، الگوریتم Strassen بیهوده پیچیده است. اما او متوجه شد که این کار برای ماتریس های بزرگتر نیز کار می کند. به این دلیل که عناصر یک ماتریس می توانند خود ماتریس باشند. به عنوان مثال، یک ماتریس با 20,000 سطر و 20,000 ستون را می توان به عنوان یک ماتریس 2 در 2 تصور کرد که چهار عنصر آن هر کدام 10,000 در 10,000 ماتریس هستند. سپس هر یک از این ماتریس ها را می توان به چهار بلوک 5,000 در 5,000 و غیره تقسیم کرد. استراسن می تواند روش خود را برای ضرب ماتریس های 2 در 2 در هر سطح از این سلسله مراتب تودرتو به کار گیرد. با افزایش اندازه ماتریس، پس انداز حاصل از ضرب های کمتر افزایش می یابد.

کشف Strassen منجر به جستجوی الگوریتم‌های کارآمد برای ضرب ماتریس شد، که از آن زمان الهام‌بخش دو حوزه فرعی مجزا بوده است. یکی روی یک سوال اصلی تمرکز می کند: اگر تصور کنید دو را ضرب کنید n-توسط-n ماتریس و اجازه دهید n به سمت بی نهایت اجرا می شود، چگونه تعداد مراحل ضرب در سریع ترین مقیاس الگوریتم ممکن با n؟ این رکورد فعلی برای بهترین مقیاس بندی، n^2.3728596، متعلق به المان و ویرجینیا واسیلوسکا ویلیامز، دانشمند کامپیوتر در موسسه فناوری ماساچوست. (اخیراً منتشر نشده پیش چاپ با استفاده از یک تکنیک جدید، یک پیشرفت کوچک گزارش شده است.) اما این الگوریتم‌ها صرفاً جنبه نظری دارند و بر روش‌هایی مانند Strassen فقط برای ماتریس‌های بی‌عیب و بزرگ پیروز می‌شوند.

حوزه دوم در مقیاس کوچکتر فکر می کند. اندکی پس از کار استراسن، دانشمند کامپیوتر اسرائیلی آمریکایی اشموئل وینوگراد نشان داد که استراسن به یک حد تئوریک رسیده است: نمی توان ماتریس های 2 در 2 را با کمتر از هفت مرحله ضرب ضرب کرد. اما برای تمام اندازه‌های ماتریس دیگر، حداقل تعداد ضرب‌های مورد نیاز یک سوال باز باقی می‌ماند. و الگوریتم‌های سریع برای ماتریس‌های کوچک می‌توانند تأثیر بزرگی داشته باشند، زیرا تکرارهای مکرر چنین الگوریتمی ممکن است زمانی که ماتریس‌هایی با اندازه معقول در حال ضرب شدن هستند، الگوریتم Strassen را شکست دهد.

متأسفانه، تعداد زیادی از امکانات بسیار زیاد است. حتی برای ماتریس های 3 در 3، "تعداد الگوریتم های ممکن از تعداد اتم های جهان بیشتر است." الحسین فوزی، محقق DeepMind و یکی از رهبران کار جدید.

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

به این ترتیب، محققان جدید کشف کرده اند الگوریتم که ضرب می شوند n-توسط-n ماتریس هایی که کمتر از استاندارد استفاده می کنند n³ مراحل ضرب برای بسیاری از اندازه های ماتریس کوچک. اما الگوریتم‌هایی که نه تنها از استاندارد، بلکه از الگوریتم استراسن برای ماتریس‌های کوچک بهتر عمل می‌کنند، تا کنون دور از دسترس باقی مانده‌اند.

بازی در

تیم DeepMind با تبدیل تجزیه تانسور به یک بازی تک نفره به مشکل نزدیک شد. آنها با یک الگوریتم یادگیری عمیق شروع کردند که از AlphaGo نشات گرفته بود - هوش مصنوعی دیگری DeepMind که در سال 2016 بازی رومیزی Go را یاد گرفت به اندازه کافی خوب برای شکست دادن بازیکنان برتر انسانی.

همه الگوریتم‌های یادگیری عمیق حول شبکه‌های عصبی ساخته شده‌اند: شبکه‌هایی از نورون‌های مصنوعی که در لایه‌هایی طبقه‌بندی شده‌اند، با اتصالاتی که می‌توانند از نظر قدرت متفاوت باشند که نشان‌دهنده میزان تأثیر هر نورون بر روی لایه‌های بعدی است. قدرت این اتصالات در بسیاری از تکرارهای یک روش آموزشی بهینه سازی می شود، که در طی آن شبکه عصبی یاد می گیرد هر ورودی دریافتی خود را به خروجی تبدیل کند که به الگوریتم کمک می کند تا هدف کلی خود را انجام دهد.

در الگوریتم جدید DeepMind که AlphaTensor نام دارد، ورودی‌ها مراحلی را در مسیر رسیدن به یک طرح ضرب ماتریس معتبر نشان می‌دهند. اولین ورودی شبکه عصبی تانسور ضرب ماتریس اصلی است و خروجی آن تانسور رتبه-1 است که AlphaTensor برای اولین حرکت خود انتخاب کرده است. الگوریتم این تانسور رتبه-1 را از ورودی اولیه کم می کند و یک تانسور به روز شده را به دست می دهد که به عنوان ورودی جدید به شبکه بازگردانده می شود. این فرآیند تا زمانی تکرار می شود که در نهایت هر عنصر در تانسور شروع به صفر کاهش یابد، به این معنی که دیگر تانسورهای رتبه 1 برای حذف وجود ندارد.

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

بازی به این صورت است: AlphaTensor بارها و بارها یک تانسور را به مجموعه ای از اجزای رتبه-1 تجزیه می کند. هر بار، اگر AlphaTensor راهی برای کاهش تعداد مراحل پیدا کند، پاداش دریافت می کند. اما میانبرهای پیروزی اصلاً شهودی نیستند، همانطور که گاهی اوقات باید قبل از اینکه بتوانید کل موضوع را حل کنید، یک چهره کاملاً مرتب روی مکعب روبیک به هم بزنید.

تیم اکنون الگوریتمی داشت که از نظر تئوری می توانست مشکل آنها را حل کند. آنها فقط باید ابتدا آن را آموزش می دادند.

مسیرهای جدید

مانند همه شبکه‌های عصبی، AlphaTensor به داده‌های زیادی برای آموزش نیاز دارد، اما تجزیه تانسور مشکل بسیار سختی است. نمونه‌های کمی از تجزیه‌های کارآمد وجود داشت که محققان بتوانند شبکه را تغذیه کنند. در عوض، آنها به الگوریتم کمک کردند تا با آموزش آن بر روی مسئله معکوس بسیار ساده تر، شروع به کار کند: جمع کردن دسته ای از تانسورهای رتبه-1 به طور تصادفی.

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

تیم DeepMind AlphaTensor را برای تجزیه تانسورهایی که نشان دهنده ضرب ماتریس ها تا 12 در 12 هستند آموزش دادند. به دنبال الگوریتم‌های سریعی برای ضرب ماتریس‌های اعداد واقعی معمولی و همچنین الگوریتم‌هایی خاص برای تنظیمات محدودتر به نام محاسبات مدول ۲ بود. (این ریاضی فقط بر اساس دو عدد است، بنابراین عناصر ماتریس فقط می توانند 2 یا 0 باشند، و 1 + 1 = 1.) محققان اغلب با این فضای محدودتر اما همچنان گسترده شروع می کنند، به این امید که الگوریتم های کشف شده در اینجا بتوانند با آنها سازگار شوند. روی ماتریس اعداد حقیقی کار کنید

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

در چند مورد، AlphaTensor حتی رکوردهای موجود را شکست داد. شگفت‌انگیزترین اکتشافات آن در محاسبات مدول 2 اتفاق افتاد، جایی که الگوریتم جدیدی برای ضرب ماتریس‌های 4 در 4 در 47 مرحله ضرب یافت، که نسبت به 49 مرحله مورد نیاز برای دو تکرار الگوریتم استراسن بهبود یافته است. همچنین بهترین الگوریتم برای ماتریس های مدول 5 5 در 2 را شکست و تعداد ضرب های مورد نیاز را از رکورد قبلی 98 به 96 کاهش داد. الگوریتم استراسن با استفاده از ماتریس های 91 در 5.)

نتیجه پرمخاطب جدید هیجان زیادی ایجاد کرد، با برخی از محققان ستایش فراوان از بهبود مبتنی بر هوش مصنوعی در وضعیت موجود. اما همه افراد در جامعه ضرب ماتریس تا این حد تحت تأثیر قرار نگرفتند. واسیلوسکا ویلیامز گفت: «احساس می‌کردم که این موضوع کمی بیش از حد تبلیغاتی است. «این یک ابزار دیگر است. این مثل این نیست که "اوه، کامپیوترها انسان ها را شکست دادند، می دانید؟"

محققان همچنین تاکید کردند که کاربردهای فوری الگوریتم رکوردشکنی 4 در 4 محدود خواهد بود: نه تنها در محاسبات مدول 2 معتبر است، بلکه در زندگی واقعی علاوه بر سرعت، ملاحظات مهمی نیز وجود دارد.

فوزی پذیرفت که واقعاً این تازه شروع است. او گفت: "جای زیادی برای پیشرفت و تحقیق وجود دارد و این چیز خوبی است."

یک پیچ نهایی

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

اما این ممکن است آنقدرها که به نظر می رسد یک ایراد بزرگ نباشد. چند روز پس از نتیجه AlphaTensor، ریاضیدان مانوئل کائورز و دانشجوی فوق لیسانسش یاکوب موسباور، هر دو از دانشگاه یوهانس کپلر لینز در اتریش، گام دیگری به جلو را گزارش کردند.

هنگامی که مقاله DeepMind منتشر شد، Kauers و Moosbauer در حال جستجو برای الگوریتم‌های ضرب جدید با استفاده از یک جستجوی معمولی به کمک رایانه بودند. اما بر خلاف بسیاری از این جستجوها، که از نو با یک اصل راهنمای جدید شروع می‌شوند، روش آن‌ها با تغییر مکرر الگوریتم موجود به امید کاهش صرفه‌جویی در ضرب بیشتر از آن کار می‌کند. با در نظر گرفتن الگوریتم AlphaTensor برای ماتریس های 5 در 5 مدول 2 به عنوان نقطه شروع، آنها با شگفتی متوجه شدند که روش آنها پس از چند ثانیه محاسبه تعداد مراحل ضرب را از 96 به 95 کاهش می دهد.

AlphaTensor همچنین به آنها کمک کرد تا بهبود دیگری را به طور غیرمستقیم انجام دهند. پیش از این، کائورز و موسباور به کاوش فضای ماتریس‌های 4 در 4 خود زحمت نمی‌دادند و معتقد بودند که نمی‌توان دو تکرار الگوریتم استراسن را شکست داد. نتیجه AlphaTensor آنها را بر آن داشت که تجدید نظر کنند و پس از یک هفته زمان محاسباتی که از ابتدا شروع شد، روش آنها یک الگوریتم 47 مرحله‌ای دیگر را نشان داد که با الگوریتمی که AlphaTensor کشف کرده بود نامرتبط بود. Kauers گفت: "اگر کسی به ما می گفت که چیزی برای کشف 4 در 4 وجود دارد، ما می توانستیم این کار را زودتر انجام دهیم." "اما خوب، خوب، این روش کار می کند."

لیتمن انتظار چنین غافلگیری های بیشتری را دارد و این وضعیت را به اولین باری که یک دونده یک مایل را در کمتر از چهار دقیقه به پایان رساند، تشبیه می کند، شاهکاری که به طور گسترده غیرممکن تلقی می شد. او گفت: "مردم می گفتند، "اوه، صبر کنید، ما می توانیم این کار را انجام دهیم" و اکنون بسیاری از مردم می توانند این کار را انجام دهند.

فوزی امیدوار است که AlphaTensor را برای انجام طیف گسترده‌تری از وظایف ریاضی و محاسباتی تعمیم دهد، درست همانطور که جدش AlphaGo در نهایت به بازی‌های دیگر منشعب شد.

Kauers این را به عنوان آزمون تورنسل واقعی برای کاربرد یادگیری ماشینی برای کشف الگوریتم های جدید می داند. او اشاره می کند که جستجو برای الگوریتم های ضرب سریع ماتریس یک مسئله ترکیبی است که جستجوهای رایانه ای، با یا بدون کمک انسان، به خوبی برای آن مناسب است. اما تعیین همه مسائل ریاضی به این راحتی نیست. او گفت: اگر یادگیری ماشین بتواند یک ایده الگوریتمی کیفی جدید را کشف کند، "این یک تغییر دهنده بازی خواهد بود."