السَّمْت

AI for Science2022متقدم13 دقيقة قراءة

اكتشاف خوارزميات أسرع لضرب المصفوفات بالتعلّم المعزَّز

Discovering Faster Matrix Multiplication Algorithms with Reinforcement Learning

Fawzi, A. · Balog, M. · Huang, A. · Hubert, T. · Romera-Paredes, B. · Barekatain, M. · Novikov, A. · Ruiz, F. J. R. · Schrittwieser, J. · Swirszcz, G. · Silver, D. · Hassabis, D. · Kohli, P. — Nature

المشكلة

ضرب المصفوفات من أكثر العمليات أساسيةً في الحوسبة — يُشغّل الشبكات العصبية ورسوميات الحاسوب والمحاكاة العلمية وضغط البيانات. البدائية لضرب مصفوفتين بأبعاد n×n تحتاج n³ عملية ضرب عددي. في عام 1969 فاجأ شتراسن مجتمع الرياضيات حين أثبت أن مصفوفتين 2×2 يمكن ضربهما بسبع عمليات ضرب فقط بدل ثمانٍ، مما يعطي خوارزمية أسرع مقاربيّاً. لكن طوال خمسين عاماً بعد شتراسن ظلّ إيجاد خوارزميات أفضل لمصفوفات أكبر مشكلة مفتوحة. فضاء البحث هائل الحجم — لضرب مصفوفتين 4×4 توجد خوارزميات محتملة أكثر من عدد الذرّات في الكون — والحدس البشري وحده بلغ حدوده.

الإسهام

يُعيد AlphaTensor صياغة البحث عن خوارزميات ضرب المصفوفات على شكل لعبة لاعب واحد تُسمّى TensorGame: الحالة ثلاثية الأبعاد (مُوتِّر)، وكل حركة تختار جداء خارجي من الأولى وتطرحه من المُوتِّر. الهدف تصفير المُوتِّر بأقل عدد من الحركات — فكل حركة تمثّل عملية ضرب واحدة في الخوارزمية النهائية. يُبنى النظام على AlphaZero مع بنية محوِّل مخصّصة وبحث شجرة مونت كارلو. ينطلق AlphaTensor من الصفر فيُعيد اكتشاف خوارزمية شتراسن، ثم يتجاوزها: لمصفوفات 4×4 على حقل منتهٍ يجد خوارزمية من 47 عملية ضرب بدل 49 لشتراسن — وهو التحسين الأول منذ خمسين عاماً. يكتشف أيضاً آلاف الخوارزميات غير المتكافئة ويُحسِّنها لعتاد محدّد، محققاً تسريعاً بنسبة 10–20% على GPU وTPU.

الأثر

أثبت AlphaTensor أن التعلّم المعزَّز قادر على تجاوز عقود من الخبرة البشرية في اكتشاف الخوارزميات لمسألة رياضية أساسية. أرسى نموذجاً جديداً: تحويل المسائل الرياضية المفتوحة إلى ألعاب يستطيع وكيل ذكاء اصطناعي تعلّمها. ألهم العمل أنظمة لاحقة مثل AlphaEvolve وغيره من أنظمة الذكاء الاصطناعي للرياضيات، وأثبت أن إطار AlphaZero يمتدّ إلى ما هو أبعد من ألعاب اللوح نحو الاكتشاف العلمي. عمليّاً، الخوارزميات المُحسَّنة للعتاد التي اكتشفها AlphaTensor تُسرِّع أي نظام يعتمد على ضرب المصفوفات — من تدريب الشبكات العصبية إلى توليد الرسوميات.

تخيّل أنك تحتاج إلى شحن حاوية عبر المحيط. المسار «المعتاد» يمرّ بمئة محطة. عالم لوجستي بارع اسمه شتراسن اكتشف مساراً بتسع وأربعين محطة فقط — لكن على مدى خمسين عاماً لم يستطع أحد إيجاد مسار أقصر.

تصوّر الآن أنك تُعطي مستكشفاً افتراضياً خريطة فارغة وتقول له: «اعثر على أي مسار يُوصل الشحنة بشكل صحيح. كلما قلّت المحطات زادت مكافأتك.» المستكشف لا يعرف شيئاً عن الشحن أو الجغرافيا — يبدأ بتجريب مسارات عشوائية ويتعلّم من كل محاولة.

بعد ملايين المحاولات، يكتشف هذا المستكشف — AlphaTensor — مسارات بسبع وأربعين محطة فقط. ليس مساراً واحداً، بل آلاف الاختصارات الصالحة التي لم يجدها أي رسّام خرائط بشري. وحين تطلب منه تحسين المسار لنوع معيّن من السفن (GPU أو TPU)، يجد مسارات أسرع بنسبة 10–20% على تلك السفينة بالذات.

لماذا يُعدّ ضرب المصفوفات نبض الحوسبة الحديثة

في كل مرة تسأل مساعداً صوتياً أو تُطبّق فلتراً على صورة أو تُشغّل شبكة عصبية، يضرب الحاسوب مصفوفات. ضرب المصفوفات بالنسبة للحوسبة كالجمع بالنسبة للحساب — عملية بدائية يُبنى عليها كل شيء آخر. تسريعها ولو بنسبة بسيطة يتراكم أثره عبر مليارات العمليات اليومية حول العالم.

الخوارزمية المدرسية لضرب مصفوفتين بأبعاد n×n تُنفّذ n³ عملية ضرب عددي: لمصفوفتين 2×2 يعني ذلك 2³ = 8 عمليات ضرب. كل عملية ضرب عددي هي الخطوة المُكلفة — عمليات الجمع رخيصة نسبياً. لذلك يصبح السؤال الجوهري: هل يمكن ضرب المصفوفات بعدد أقل من عمليات الضرب؟

افتح في المختبر
قارن بين كيفية تنفيذ الخوارزمية المعيارية وخوارزمية شتراسن وAlphaTensor لضرب مصفوفتين 2×2. لاحظ كيف يمزج شتراسن عناصر المصفوفة بذكاء ليوفّر عملية ضرب واحدة.
تستيقظ التجربة عند وصولك…

اختراق شتراسن — وخمسون عاماً من الصمت

في عام 1969 أثبت فولكر شتراسن أن ضرب مصفوفتين 2×2 يمكن أن يتمّ بسبع عمليات ضرب بدل ثمانٍ. الحيلة: بدل أن تحسب كل عنصر في المصفوفة الناتجة بشكل مستقل، تمزج صفوف وأعمدة المصفوفتين في مجاميع ذكية، ثم تضرب تلك المجاميع، وأخيراً تُعيد تركيب النتائج للحصول على الإجابة النهائية. أنت تستبدل عملية ضرب واحدة بعدة عمليات جمع إضافية — صفقة رابحة لأن الضرب هو المُكلف.

لنتيجة شتراسن أثر عميق: بتطبيق حيلة الـ 2×2 بشكل تعاوُدي على مصفوفات أكبر (قسّم كل مصفوفة n×n إلى أربع كتل n/2 × n/2)، تنخفض التعقيدية المقاربية من O(n³) إلى O(n^2.807). للمصفوفات الكبيرة هذا تسريع هائل. لكن لحالات أساسية أكبر — 3×3 و4×4 و5×5 — لم يكن أحد يعرف العدد الأمثل من عمليات الضرب. فضاء البحث ينمو بسرعة خيالية بحيث يستحيل الاستقصاء الشامل.

T(n)=7⋅T ⁣(n2)+O(n2)  ⟹  T(n)=O ⁣(nlog⁡27)≈O(n2.807)T(n) = 7 \cdot T\!\left(\frac{n}{2}\right) + O(n^2) \implies T(n) = O\!\left(n^{\log_2 7}\right) \approx O(n^{2.807})
علاقة شتراسن التعاوُدية — تكلفة التفكيك التعاوُدي 2×2 — بتطبيق حيلة السبع عمليات ضرب لكتل 2×2 بشكل تعاوُدي، تنخفض التكلفة الإجمالية لضرب مصفوفتين n×n من n³ إلى n^2.807 تقريباً. المفتاح: سبعة استدعاءات تعاوُدية بدلاً من ثمانية.

الفكرة المحورية: ضرب المصفوفات هو تفكيك مُوتِّر

هنا نصل إلى الرابط الرياضي الأنيق الذي جعل AlphaTensor ممكناً. أيّ خوارزمية لضرب مصفوفة بأبعاد m×k في مصفوفة بأبعاد k×n يمكن ترميزها كعملية تفكيك لمُوتِّر ثلاثي الأبعاد بأبعاد (mk) × (kn) × (mn). تخيّل هذا المُوتِّر كمكعّب من الأرقام يُرمِّز أيّ عناصر من المصفوفتين يجب مزجها لإنتاج كل عنصر في المصفوفة الناتجة.

كل «خطوة» في الخوارزمية — أي عملية ضرب عددي واحدة — تُقابل حدّاً واحداً من الرتبة الأولى في التفكيك: ثلاثة متجهات u وv وw يُشكّل جداؤها الخارجي u ⊗ v ⊗ w طبقةً واحدة من المُوتِّر. العدد الإجمالي لهذه الحدود يُسمّى رتبة التفكيك ويساوي عدد عمليات الضرب العددي التي تستخدمها الخوارزمية.

الخوارزمية المعيارية لمصفوفتين 2×2 رتبتها 8. خوارزمية شتراسن رتبتها 7. إيجاد خوارزمية أسرع يعني إيجاد تفكيك أدنى رتبة للمُوتِّر نفسه — وهي مسألة كلاسيكية في نظرية التعقيد الجبري استعصت على الجهود البشرية لعقود.

T=∑r=1Ru(r)⊗v(r)⊗w(r)\mathcal{T} = \sum_{r=1}^{R} \mathbf{u}^{(r)} \otimes \mathbf{v}^{(r)} \otimes \mathbf{w}^{(r)}
تفكيك المُوتِّر — كل حدّ من الرتبة الأولى يمثّل عملية ضرب واحدة — مُوتِّر ضرب المصفوفات 𝒯 يُفكَّك إلى R جداء خارجي من الرتبة الأولى. R هو العدد الإجمالي لعمليات الضرب العددي. إيجاد أصغر R يُكافئ إيجاد أكفأ خوارزمية ممكنة.
افتح في المختبر
شاهد كيف يُقشَّر المُوتِّر ثلاثي الأبعاد طبقةً بطبقة. كل جداء خارجي من الرتبة الأولى (u ⊗ v ⊗ w) يطرح «شريحة» واحدة من المُوتِّر. حين يصل المُوتِّر إلى الصفر تحصل على خوارزمية صالحة.
تستيقظ التجربة عند وصولك…

لعبة المُوتِّر: تحويل الرياضيات إلى لعبة يلعبها الذكاء الاصطناعي

القرار التصميمي الجوهري في هذه الورقة هو إعادة صياغة تفكيك المُوتِّر كلعبة لاعب واحد. آلية اللعبة كالتالي:

الحالة: مُوتِّر ثلاثي الأبعاد S_t، يُهيَّأ بمُوتِّر ضرب المصفوفات 𝒯. الفعل: في كل خطوة t يختار اللاعب ثلاثة متجهات u وv وw ويطرح جداءها الخارجي من الحالة الحالية لتصبح الحالة الجديدة: S ناقص u ⊗ v ⊗ w. الهدف: اختزال S_t إلى مُوتِّر أصفار. : مكافأة سالبة عند كل خطوة (لتشجيع تقليل الخطوات)، مع عقوبة سالبة كبيرة إذا لم يُصفَّر المُوتِّر خلال الحد الأقصى من الخطوات.

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

افتح في المختبر
جرّب لعبة المُوتِّر المُبسَّطة! اختر متجهات لتصفير مُوتِّر صغير. حركات أقل = خوارزمية أكفأ.
تستيقظ التجربة عند وصولك…

كيف يفكّر AlphaTensor: البنية والتدريب

يُبنى AlphaTensor على AlphaZero لكنه يُدخل ابتكارات جوهرية للتعامل مع التحديات الفريدة للعبة المُوتِّر. في لعبة غو رقعة اللعب شبكة ثنائية الأبعاد بها 361 حركة ممكنة، أما في لعبة المُوتِّر فالحالة مُوتِّر ثلاثي الأبعاد وفضاء الأفعال يتجاوز 10³³ — أكبر من فضاء غو بثلاثين رتبة من حيث الحجم.

الشبكة العصبية عبارة عن محوِّل بمرمِّز وفاكّ ترميز. المرمِّز يستقبل ثلاثة مدخلات: حالة المُوتِّر الحالية (مُسقَطة على المحاور الثلاثة لالتقاط بنيتها ثلاثية الأبعاد)، والأفعال الأخيرة المتّخذة (للسياق الزمني)، وتضمين عددي للوقت. يعالج المُوتِّر عبر طبقات انتباه تتعامل مع جميع التبديلات الدورية الثلاثة للمحاور بالتساوي — وهو تحيّز استقرائي مفتاحي يحترم التناظر الرياضي لتفكيك المُوتِّر.

فاكّ الترميز يُخرج شيئين: — توزيع احتمالي على الأفعال المرشّحة (أي u وv وw ينبغي اختيارها لاحقاً) — وقيمة — تقدير لعدد الخطوات المتبقية من الحالة الحالية. بما أن تعداد جميع الأفعال الممكنة مستحيل عملياً، يستخدم AlphaTensor نهج AlphaZero المُعيَّن بالعينات: الشبكة تقترح مجموعة صغيرة من الأفعال الواعدة، ثم يستكشف بحث شجرة مونت كارلو من بينها.

افتح في المختبر
استكشف بنية AlphaTensor. انقر على كل مكوّن لمعرفة دوره — من مرمِّز المُوتِّر إلى مخطّط بحث الشجرة.
تستيقظ التجربة عند وصولك…

يجمع التدريب بين مصدرين. الأول: عروض تركيبية — تفكيكات مُوتِّر مولَّدة عشوائياً توفّر منهجاً تمهيدياً للبدء. ليست حلولاً مثالية — مجرد حلول صالحة تُعلّم الشبكة البنية الأساسية للمسألة. الثاني: ألعاب اللعب الذاتي — يلعب الوكيل لعبة المُوتِّر مستخدماً بحث شجرة مونت كارلو، والمسارات الناتجة تُضاف إلى ذاكرة إعادة التشغيل. تُدرَّب الشبكة على التنبؤ بالسياسة (أي حركة اختارها بحث الشجرة) والقيمة (كم خطوة تبقّت) من كل حالة.

من التقنيات الجوهرية التوسيع بتغيير الأساس: المُوتِّر نفسه يمكن التعبير عنه في أنظمة إحداثيات متكافئة عديدة. بتحويل المُوتِّر عشوائياً قبل كل لعبة، يرى AlphaTensor أوجهاً متنوعة للمسألة ذاتها، فيكتسب وعياً بالتناظرات دون ترميزها صراحةً. يلعب الوكيل جميع الأوجه بالتوازي ويكفيه حلّ أيٍّ منها — إذا وجد تفكيكاً في أيّ أساس فهو صالح رياضياً في جميع الأسس.

النتائج: تجاوُز خمسين عاماً من الاكتشاف البشري

دُرِّب AlphaTensor على أحجام مصفوفات تتراوح من 2×2 حتى 5×5، وكانت اكتشافاته مُبهرة.

انطلاقاً من الصفر بلا أي معرفة مسبقة، يُعيد الوكيل أولاً اكتشاف الخوارزميات المعيارية، ثم حلّ شتراسن ذا السبع عمليات لمصفوفتي 2×2، ثم يتخطّاه. لمصفوفات 4×4 على الحقل المنتهي Z/2Z (الحساب المعياري بالقسمة على 2)، اكتشف AlphaTensor خوارزمية من 47 عملية ضرب — متغلّباً على تطبيق شتراسن التعاوُدي ذي الـ 49 لأول مرة منذ 1969.

في الحالة العملية المهمة لضرب مصفوفة 4×5 في مصفوفة 5×5، حيث تستخدم الخوارزمية المعيارية 100 عملية ضرب والخوارزميات البشرية وصلت إلى 80، وجد AlphaTensor خوارزميات بـ 76 عملية فقط. من بين أكثر من 70 حجم مصفوفة اختُبِر، حسّن AlphaTensor أفضل خوارزمية معروفة في حالات كثيرة وطابقها في البقية.

والأكثر إدهاشاً ربما: اكتشف AlphaTensor أكثر من 14,000 خوارزمية غير متكافئة لمسألة واحدة (ضرب مصفوفتين 4×4). هذا التنوّع كشف أن فضاء الخوارزميات الكفؤة أغنى بكثير مما كان الرياضيّون يتصوّرون.

افتح في المختبر
استكشف اكتشافات AlphaTensor عبر أحجام مصفوفات مختلفة. قارن عدد عمليات الضرب في الخوارزمية المعيارية وخوارزمية شتراسن وAlphaTensor.
تستيقظ التجربة عند وصولك…

أبعد من النظرية: التحسين للعتاد الحقيقي

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

يستغلّ AlphaTensor تنوّع الخوارزميات المُكتشَفة بإضافة مرحلة تحسين ثانية. بعد إيجاد عدة خوارزميات متكافئة رياضياً (بنفس الرتبة)، يقيس أداء كل منها على منصة عتاد مستهدَفة — مثل GPU من نوع NVIDIA V100 أو TPU v2 من Google — ويُعيد زمن التنفيذ كإشارة مكافأة إضافية.

النتيجة: خوارزميات مُفصَّلة للعتاد تعمل أسرع بنسبة 10–20% من التطبيقات المستخدمة شائعاً على نفس العتاد. هذا يُظهر ميزة جوهرية لاكتشاف الخوارزميات بالذكاء الاصطناعي: القدرة على التحسين لأهداف عملية غير رياضية بحتة تهمّ في الواقع التطبيقي.

شبه كود: حلقة تدريب AlphaTensorpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

# حلقة تدريب AlphaTensor (مُبسَّطة)
# 1. التهيئة: تحميل مُوتِّر ضرب المصفوفات T
T = build_matmul_tensor(m, k, n)
# 2. توليد عروض تركيبية
demos = generate_random_decompositions(T, num_demos=10000)
# 3. حلقة التدريب
for episode in range(num_episodes):
    # التوسيع بتغيير الأساس
    T_aug = random_change_of_basis(T)
    # لعب لعبة المُوتِّر مع بحث الشجرة
    trajectory = mcts_play(network, T_aug, max_steps=R_max)
    # المكافأة: عدد الخطوات بالسالب (أقل = أفضل)
    reward = -len(trajectory)
    # الإضافة إلى ذاكرة إعادة التشغيل
    buffer.add(trajectory, reward)
    # تدريب الشبكة على الذاكرة + العروض
    network.train(buffer, demos)
    # تتبّع أفضل تفكيك وُجِد
    if len(trajectory) < best_rank:
        best_rank = len(trajectory)
        best_algorithm = trajectory

الصورة الأشمل: من الألعاب إلى الاكتشاف العلمي

AlphaTensor جزء من مسار أوسع في DeepMind: توسيع إطار AlphaZero من ألعاب اللوح إلى مسائل العالم الحقيقي. AlphaZero أتقن الشطرنج وغو والشوغي. MuZero تعلّم التخطيط دون أن يعرف حتى قواعد اللعبة. AlphaTensor يُظهر الخطوة التالية — تطبيق نفس المبادئ على مسألة مفتوحة في الرياضيات البحتة.

النهج قابل للتعميم. أي مسألة يمكن صياغتها كـ «اتّخذ سلسلة أفعال للوصول إلى حالة هدف قابلة للتحقق» هي مرشّحة لهذا الإطار. التطبيقات المحتملة تشمل اكتشاف خوارزميات أسرع لعمليات حسابية أساسية أخرى (الفرز وتحويل فورييه السريع والالتفاف)، وتحسين تصميم الدارات، وإيجاد مسارات تركيب كيميائي جديدة، وغير ذلك.

تربط الورقة أيضاً بـ AlphaFold 2 — مثال آخر على تطبيق DeepMind الذكاءَ الاصطناعي لحلّ مسألة علمية أساسية استعصت على عقود من الجهد البشري. هذه الأعمال مجتمعةً تشير إلى نموذج جديد لا يكون فيه الذكاء الاصطناعي مجرد أداة لأتمتة المهام المعروفة، بل شريكاً في الاكتشاف العلمي ذاته.

الخط الزمني: الطريق إلى AlphaTensor وما بعده

  1. 1969

    خوارزمية شتراسن

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

  2. 2016

    AlphaGo يهزم لي سيدول

    نظام AlphaGo من DeepMind يهزم بطل العالم في غو، مُثبتاً أن التعلّم المعزَّز العميق مع بحث شجرة مونت كارلو قادر على إتقان ألعاب استراتيجية معقدة.

  3. 2017

    AlphaZero — خوارزمية واحدة لجميع الألعاب

    AlphaZero يُتقن الشطرنج وغو والشوغي من اللعب الذاتي وحده دون أي بيانات بشرية. يُثبت أن التعلّم من صفحة بيضاء قادر على تجاوز الخبرة البشرية.

  4. 2019

    MuZero — التخطيط بلا قواعد

    MuZero يتعلّم التخطيط في بيئات لا يعرف قواعدها، فيبني نموذجاً داخلياً للديناميكيات. يوسّع AlphaZero إلى ألعاب أتاري.

  5. 2022

    AlphaTensor — من الألعاب إلى الرياضيات

    أول توسيع لـ AlphaZero إلى مسألة رياضية مفتوحة. يكتشف خوارزميات أسرع لضرب المصفوفات مُتغلّباً على رقم شتراسن الذي صمد خمسين عاماً.

  6. 2025

    AlphaEvolve — تطوير الخوارزميات بواسطة Gemini

    نظام AlphaEvolve من DeepMind يستخدم نماذج اللغة الكبيرة لتصميم خوارزميات متقدمة للرياضيات والحوسبة، موسِّعاً نموذج الذكاء الاصطناعي لاكتشاف الخوارزميات.

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

المرجعFawzi, Balog, Huang, Hubert, Romera-Paredes, Barekatain, Novikov, Ruiz, Schrittwieser, Swirszcz, Silver, Hassabis, Kohli. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 2022.

مصطلحات هذه الورقة