يكشف الذكاء الاصطناعي عن إمكانيات جديدة في ضرب المصفوفة

يحب علماء الرياضيات اللغز الجيد. حتى الأشياء المجردة مثل المصفوفات المضاعفة (جداول الأرقام ثنائية الأبعاد) يمكن أن تشعر وكأنها لعبة عندما تحاول إيجاد الطريقة الأكثر فاعلية للقيام بذلك. إنها تشبه إلى حدٍ ما محاولة حل مكعب روبيك في أقل عدد ممكن من الحركات - تحدي ، ولكن جذاب. فيما عدا ذلك بالنسبة لمكعب روبيك ، فإن عدد الحركات الممكنة في كل خطوة هو 18 ؛ لضرب المصفوفة ، حتى في الحالات البسيطة نسبيًا ، يمكن أن تقدم كل خطوة أكثر من 10¹² خيارات.

على مدار الخمسين عامًا الماضية ، تعامل الباحثون مع هذه المشكلة بعدة طرق ، وكلها تستند إلى عمليات البحث على الكمبيوتر بمساعدة الحدس البشري. في الشهر الماضي ، أظهر فريق في شركة الذكاء الاصطناعي DeepMind كيفية معالجة المشكلة من اتجاه جديد ، وتقديم التقارير في ورقة in الطبيعة أنهم نجحوا في تدريب شبكة عصبية لاكتشاف خوارزميات سريعة جديدة لمضاعفة المصفوفة. كان الأمر كما لو أن الذكاء الاصطناعي قد وجد استراتيجية غير معروفة لحل مكعب روبيك المعقد بشكل رهيب.

قال "إنها نتيجة رائعة للغاية" جوش ألمان، عالم كمبيوتر في جامعة كولومبيا. لكنه أكد هو وغيره من المتخصصين في ضرب المصفوفات أيضًا أن مساعدة الذكاء الاصطناعي هذه ستكمل الأساليب الحالية بدلاً من أن تحل محلها - على الأقل في المدى القريب. قال علمان: "إنه بمثابة إثبات لمفهوم لشيء يمكن أن يصبح اختراقًا". سوف تساعد النتيجة الباحثين ببساطة في سعيهم.

كما لو كان لإثبات هذه النقطة ، بعد ثلاثة أيام من الطبيعة ظهرت الورقة البحثية ، حيث أوضح زوجان من الباحثين النمساويين كيف يمكن للطرق الجديدة والقديمة أن تكمل بعضها البعض. استخدموا البحث التقليدي بمساعدة الكمبيوتر ل زيادة تحسين إحدى الخوارزميات التي اكتشفتها الشبكة العصبية.

تشير النتائج إلى أنه ، مثل عملية حل مكعب روبيك ، فإن الطريق إلى خوارزميات أفضل سيكون مليئًا بالتحولات والمنعطفات.

ضرب المصفوفات

يعد ضرب المصفوفة أحد أكثر العمليات جوهرية وانتشارًا في جميع الرياضيات. لمضاعفة زوج من nعلى حدةn المصفوفات ، مع كل منها n² العناصر ، يمكنك ضرب وإضافة هذه العناصر معًا في مجموعات معينة لتوليد المنتج ، وهو العنصر الثالث nعلى حدةn مصفوفة. الوصفة القياسية لضرب اثنين nعلى حدةn تتطلب المصفوفات n³ عمليات الضرب ، لذا تتطلب المصفوفة 2 × 2 ، على سبيل المثال ، ثمانية عمليات ضرب.

بالنسبة للمصفوفات الأكبر ، التي تحتوي على آلاف الصفوف والأعمدة ، تصبح هذه العملية مرهقة بسرعة. لكن في عام 1969 ، عالم الرياضيات فولكر ستراسن اكتشف إجراء لضرب زوج من المصفوفات 2 × 2 باستخدام سبع خطوات ضرب بدلاً من ثماني خطوات ، على حساب إدخال المزيد من خطوات الجمع.

تكون خوارزمية Strassen معقدة بلا داع إذا كنت تريد فقط ضرب زوج من المصفوفات 2 × 2. لكنه أدرك أنه سيعمل أيضًا مع مصفوفات أكبر. ذلك لأن عناصر المصفوفة يمكن أن تكون نفسها مصفوفات. على سبيل المثال ، يمكن إعادة تصور مصفوفة تحتوي على 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 فقط لمصفوفات كبيرة بشكل سخيف.

الحقل الفرعي الثاني يفكر على نطاق أصغر. بعد فترة وجيزة من عمل ستراسن ، عالم الكمبيوتر الإسرائيلي الأمريكي شموئيل فينوغراد أظهرت أن Strassen قد وصل إلى الحد النظري: لا يمكن ضرب مصفوفات 2 × 2 بأقل من سبع خطوات ضرب. ولكن بالنسبة لجميع أحجام المصفوفات الأخرى ، يظل الحد الأدنى لعدد الضربات المطلوبة سؤالًا مفتوحًا. ويمكن أن يكون للخوارزميات السريعة للمصفوفات الصغيرة تأثير كبير ، لأن التكرارات المتكررة لمثل هذه الخوارزمية قد تتغلب على خوارزمية Strassen عندما يتم مضاعفة المصفوفات ذات الحجم المعقول.

لسوء الحظ ، فإن العدد الهائل من الاحتمالات ضخم. حتى بالنسبة لمصفوفات 3 في 3 ، فإن "عدد الخوارزميات الممكنة يتجاوز عدد الذرات في الكون ،" الحسين فوزي، باحث DeepMind وأحد قادة العمل الجديد.

في مواجهة هذه القائمة المذهلة من الخيارات ، حقق الباحثون تقدمًا من خلال تحويل ضرب المصفوفة إلى ما يبدو وكأنه مشكلة رياضية مختلفة تمامًا - مشكلة يسهل على أجهزة الكمبيوتر التعامل معها. من الممكن تمثيل المهمة المجردة لضرب مصفوفتين كنوع معين من الكائن الرياضي: مصفوفة ثلاثية الأبعاد من الأرقام تسمى موتر. يمكن للباحثين بعد ذلك تقسيم هذا الموتر إلى مجموع المكونات الأولية ، تسمى موترات "الرتبة 1". كل من هؤلاء سيمثل خطوة مختلفة في خوارزمية ضرب المصفوفة المقابلة. هذا يعني أن العثور على خوارزمية ضرب فعالة يرقى إلى تقليل عدد المصطلحات في تحلل الموتر - فكلما قل عدد المصطلحات ، قل عدد الخطوات المتضمنة.

بهذه الطريقة اكتشف الباحثون الجديد خوارزميات التي تتضاعف nعلى حدةn المصفوفات التي تستخدم أقل من المعيار n³ خطوات الضرب للعديد من أحجام المصفوفات الصغيرة. لكن الخوارزميات التي تتفوق ليس فقط على المعيار ولكن أيضًا على خوارزمية Strassen للمصفوفات الصغيرة ظلت بعيدة المنال - حتى الآن.

لعبة على

تعامل فريق DeepMind مع المشكلة عن طريق تحويل تحلل الموتر إلى لعبة لاعب واحد. لقد بدأوا بخوارزمية التعلم العميق المنحدرة من AlphaGo - ذكاء اصطناعي DeepMind آخر كان في عام 2016 تعلمت أن تلعب لعبة اللوح Go بشكل جيد بما يكفي للتغلب على أفضل اللاعبين البشريين.

تم بناء جميع خوارزميات التعلم العميق حول الشبكات العصبية: شبكات من الخلايا العصبية الاصطناعية مصنفة في طبقات ، مع وصلات يمكن أن تختلف في القوة التي تمثل مدى تأثير كل خلية عصبية على تلك الموجودة في الطبقة التالية. يتم تعديل قوة هذه الاتصالات عبر العديد من التكرارات لإجراء التدريب ، حيث تتعلم الشبكة العصبية تحويل كل مدخلات تتلقاها إلى مخرجات تساعد الخوارزمية على تحقيق هدفها العام.

في خوارزمية DeepMind الجديدة ، المسماة AlphaTensor ، تمثل المدخلات خطوات على طول الطريق إلى مخطط ضرب مصفوفة صالح. المدخل الأول للشبكة العصبية هو موتر ضرب المصفوفة الأصلي ، وخرجه هو موتر الرتبة 1 الذي اختاره AlphaTensor لحركته الأولى. تطرح الخوارزمية موتر المرتبة الأولى من الإدخال الأولي ، مما ينتج عنه موتر محدث يتم تغذيته مرة أخرى في الشبكة كمدخل جديد. تتكرر العملية حتى يتم في النهاية تقليل كل عنصر في موتر البداية إلى الصفر ، مما يعني أنه لا يوجد المزيد من موترات الرتبة الأولى لإخراجها.

في تلك المرحلة ، اكتشفت الشبكة العصبية تحللًا موترًا صالحًا ، لأنه مضمون رياضيًا أن مجموع كل موتر الرتبة 1 يساوي تمامًا موتر البداية. والخطوات التي تم اتخاذها للوصول إلى هناك يمكن ترجمتها مرة أخرى إلى خطوات خوارزمية ضرب المصفوفة المقابلة.

ها هي اللعبة: يحلل AlphaTensor بشكل متكرر موترًا إلى مجموعة من مكونات المرتبة الأولى. في كل مرة ، يتم مكافأة AlphaTensor إذا وجد طريقة لتقليل عدد الخطوات. لكن الطرق المختصرة للنصر ليست بديهية على الإطلاق ، تمامًا كما يجب عليك أحيانًا التدافع على وجه مرتب تمامًا على مكعب روبيك قبل أن تتمكن من حل الأمر برمته.

أصبح لدى الفريق الآن خوارزمية يمكنها نظريًا حل مشكلتهم. كان عليهم فقط تدريبه أولاً.

مسارات جديدة

مثل جميع الشبكات العصبية ، يحتاج AlphaTensor إلى الكثير من البيانات للتدريب عليها ، لكن تحلل الموتر مشكلة صعبة للغاية. كانت هناك أمثلة قليلة على التحليلات الفعالة التي يمكن للباحثين تغذية الشبكة بها. بدلاً من ذلك ، ساعدوا الخوارزمية على البدء من خلال تدريبها على المشكلة العكسية الأسهل بكثير: إضافة مجموعة من موترات الرتبة الأولى التي تم إنشاؤها عشوائيًا.

قال "إنهم يستخدمون المشكلة السهلة لإنتاج المزيد من البيانات للمشكلة الصعبة" مايكل ليتمان، عالم كمبيوتر في جامعة براون. إن الجمع بين إجراء التدريب العكسي هذا والتعلم المعزز ، حيث قام AlphaTensor بإنشاء بيانات التدريب الخاصة به حيث كان يتخبط في البحث عن التحلل الفعال ، وعمل بشكل أفضل بكثير من أي من أسلوب التدريب بمفرده.

قام فريق DeepMind بتدريب AlphaTensor على تحليل الموترات التي تمثل مضاعفة المصفوفات حتى 12 × 12. سعت إلى خوارزميات سريعة لضرب مصفوفات الأرقام الحقيقية العادية وأيضًا الخوارزميات الخاصة بإعداد أكثر تقييدًا يُعرف باسم حساب modulo 2. (تستند هذه الرياضيات إلى رقمين فقط ، لذلك يمكن أن تكون عناصر المصفوفة 0 أو 1 فقط ، و 1 + 1 = 0). غالبًا ما يبدأ الباحثون بهذه المساحة الأكثر تقييدًا ولكن لا تزال واسعة ، على أمل أن الخوارزميات المكتشفة هنا يمكن تكييفها مع العمل على مصفوفات الأعداد الحقيقية.

بعد التدريب ، أعاد AlphaTensor اكتشاف خوارزمية Strassen في غضون دقائق. ثم اكتشف ما يصل إلى الآلاف من الخوارزميات السريعة الجديدة لكل حجم مصفوفة. كانت هذه مختلفة عن الخوارزميات الأكثر شهرة ولكن لها نفس عدد خطوات الضرب.

في حالات قليلة ، تفوق AlphaTensor على الأرقام القياسية الموجودة. حدثت اكتشافاته الأكثر إثارة للدهشة في حساب modulo 2 ، حيث وجد خوارزمية جديدة لضرب المصفوفات 4 × 4 في 47 خطوة من خطوات الضرب ، وهو تحسين على 49 خطوة مطلوبة لتكرارين من خوارزمية Strassen. كما تغلبت أيضًا على الخوارزمية الأكثر شهرة لمصفوفات 5 × 5 modulo 2 ، مما قلل عدد المضاعفات المطلوبة من الرقم القياسي السابق من 98 إلى 96. (لكن هذا الرقم القياسي الجديد لا يزال متأخرًا عن 91 خطوة التي ستكون مطلوبة للتغلب على خوارزمية Strassen باستخدام مصفوفات 5 × 5).

خلقت النتيجة الجديدة رفيعة المستوى الكثير من الإثارة ، بـ بعض الباحثين تكدس الثناء على التحسين القائم على الذكاء الاصطناعي في الوضع الراهن. ولكن لم يكن كل فرد في مجتمع ضرب المصفوفة معجبًا جدًا. قالت فاسيليفسكا ويليامز: "شعرت أن الأمر مبالغ فيه قليلاً". "إنها أداة أخرى. إنه ليس مثل ، "أوه ، أجهزة الكمبيوتر تغلب على البشر ،" هل تعلم؟ "

أكد الباحثون أيضًا أن التطبيقات الفورية لخوارزمية 4 × 4 المحطمة للأرقام القياسية ستكون محدودة: ليس فقط أنها صالحة فقط في الحساب 2 ، ولكن في الحياة الواقعية هناك اعتبارات مهمة إلى جانب السرعة.

اتفق فوزي على أن هذه مجرد البداية. قال "هناك مجال كبير للتحسين والبحث ، وهذا شيء جيد".

تطور نهائي

إن أعظم نقاط قوة AlphaTensor بالنسبة لطرق البحث الحاسوبية الراسخة هي أيضًا أكبر نقاط ضعفها: فهي ليست مقيدًا بالحدس البشري حول شكل الخوارزميات الجيدة ، لذلك لا يمكنها شرح خياراتها. هذا يجعل من الصعب على الباحثين التعلم من إنجازاته.

لكن هذا قد لا يكون عيبًا كبيرًا كما يبدو. بعد أيام قليلة من نتيجة AlphaTensor ، عالم الرياضيات مانويل كاورز وطالبه المتخرج جاكوب موسباور، كلاهما من جامعة يوهانس كيبلر لينز في النمسا ، عن خطوة أخرى إلى الأمام.

عندما صدرت ورقة DeepMind ، كان Kauers و Moosbauer في عملية البحث عن خوارزميات الضرب الجديدة باستخدام بحث تقليدي بمساعدة الكمبيوتر. ولكن على عكس معظم عمليات البحث هذه ، التي تبدأ من جديد بمبدأ إرشادي جديد ، فإن طريقتهم تعمل عن طريق التغيير والتبديل المتكرر لخوارزمية موجودة على أمل استخراج المزيد من مدخرات الضرب منها. أخذوا خوارزمية AlphaTensor لمصفوفات 5x5 modulo 2 كنقطة بداية ، فوجئوا عندما اكتشفوا أن طريقتهم قللت عدد خطوات الضرب من 96 إلى 95 بعد بضع ثوانٍ من الحساب.

ساعدهم AlphaTensor أيضًا في إجراء تحسين آخر بشكل غير مباشر. في السابق ، لم يكلف Kauers و Moosbauer عناء استكشاف مساحة مصفوفات 4 × 4 ، معتقدين أنه لن يكون من الممكن التغلب على تكرارين من خوارزمية Strassen. دفعتهم نتيجة AlphaTensor إلى إعادة النظر ، وبعد أسبوع من وقت الحساب بدءًا من نقطة الصفر ، كشفت طريقتهم عن خوارزمية أخرى من 47 خطوة لا علاقة لها بالخوارزمية التي اكتشفها AlphaTensor. قال Kauers: "إذا أخبرنا شخص ما أن هناك شيئًا لاكتشافه لـ 4 في 4 ، كان بإمكاننا فعل ذلك في وقت سابق". "ولكن حسنًا ، هذه هي الطريقة التي يعمل بها."

يتوقع Littman المزيد من هذه المفاجآت ، مشبهاً الوضع بالمرة الأولى التي ينهي فيها عداء ميلاً في أقل من أربع دقائق ، وهو إنجاز كان يعتبر على نطاق واسع مستحيلاً. قال: "كان الناس مثل ،" أوه ، انتظر ، يمكننا القيام بذلك ، والآن يمكن للكثير من الناس القيام بذلك ".

وبالنظر إلى المستقبل ، يأمل فوزي في تعميم AlphaTensor لمعالجة مجموعة أوسع من المهام الحسابية والحاسوبية ، تمامًا كما تفرّع سلفه AlphaGo في النهاية إلى ألعاب أخرى.

يرى Kauers أن هذا هو الاختبار الحقيقي الحقيقي لتطبيق التعلم الآلي لاكتشاف خوارزميات جديدة. ويشير إلى أن البحث عن خوارزميات ضرب المصفوفات السريعة هي مشكلة اندماجية تناسبها عمليات البحث الحاسوبية ، بمساعدة بشرية أو بدونها. ولكن ليس من السهل تحديد كل المسائل الرياضية. وقال إنه إذا تمكن التعلم الآلي من اكتشاف فكرة خوارزمية جديدة نوعًا ، "فسيغير ذلك قواعد اللعبة".