🤖 machine learning

Indexing: the Beginning and the End

تقدم هذه الورقة مفهوم التعقيد السببي لتوضيح أن بنيات التعلم العميق المقنعة مثل الشبكات العصبية المتكررة (RNNs) ومحولات الانتباه الخطي (linear-attention transformers) محدودة جوهرياً في حل عملية الفهرسة الأولية عندما يظهر الفهرس في نهاية المدخلات، في حين يمكن لمحولات الـ softmax والمحولات غير المقنعة ذات الانتباه الخطي حلها بكفاءة، وهو فصل نظري تؤكده التجارب التجريبية.

المؤلفون الأصليون: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

نُشر 2026-07-27

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

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

هذه الورقة البحثية، التي تحمل عنوان "الفهرسة: البداية والنهاية"، تأخذ لغزاً محدداً وبسيطاً جداً يسمى "الفهرسة" (Indexing) وتستخدمه لاختبار عقول هذه الأنواع المختلفة من بنيات الرخوتات. اللغز سهل بشكل مخادع: تخيل أن لديك قائمة من $n$ من البتات (سلسلة من 0 و1) ورقم $i$ يخبرك أي بت يجب أن تختار. الهدف ببساطة هو إخراج قيمة ذلك البت المحدد. الأمر يشبه أن تُعطى صفاً من 64 مفتاح إضاءة ورقمًا، وليكن "17"، ثم يُطلب منك: "هل المفتاح 17 يعمل أم لا؟"

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

وهنا تكمن المفاجأة: تثبت الورقة أنه بالنسبة لأنواع معينة من الروبوتات (تحديداً تلك التي تعالج المعلومات بطريقة "سببية" أو "مقنعة"، مما يعني أنها يمكنها فقط النظر إلى ما جاء قبلها وليس ما يأتي بعدها)، فإن حل هذا اللغز مستحيل رياضياً إذا كانت قائمة البتات طويلة وظهر رقم الفهرس في النهاية تماماً. الأمر كما لو أنك قدمت لروبوت طابوراً طويلاً من الناس، وطلبت منه تذكر وجه كل شخص، ثم همست في نهايته: "أخبرني باسم الشخص رقم 42". توضح الورقة أن روبوتات مثل RNNs، وMamba، والمحولات ذات الانتباه الخطي المقنع (masked linear-attention transformers) لديها "عنق زجاجة في الذاكرة". فهي لا تستطيع ضغط كل تلك المعلومات في حزمة صغيرة بما يكفي لتذكر البت المحدد عندما يصل الفهرس أخيراً. وقد أثبت المؤلفون ذلك باستخدام رياضيات صارمة تظل صحيحة حتى لو كانت الروبوتات تمتلك دقة لانهائية (بمعنى أنها لا ترتبك بسبب أخطاء التقريب).

ومع ذلك، تتغير القصة إذا قلبت السيناريو. إذا ظهر رقم الفهرس في بداية القائمة (مما يخبر الروبوت "تذكر الشخص 42" قبل أن تعرض عليهم طابور الناس)، تصبح الـ RNNs هي الأبطال الخارقين. يمكنها حل هذا في خطوة واحدة، بينما تحتاج الروبوتات الأخرى (بما في ذلك المحولات الشهيرة Transformers) إلى خطوتين على الأقل لمعرفة الأمر.

لم يكتفِ المؤلفون بالرياضيات فقط؛ بل أجروا تجارب على نماذج حقيقية. قاموا بتدريب هذه الروبوتات على قوائم تصل إلى 64 بتًا. وكانت النتائج مطابقة تماماً لنظريتهم. الروبوتات التي قالت الرياضيات إنها ستفشل (النماذج السببية التي تحاول إيجاد البت في نهاية قائمة طويلة) استسلمت باستمرار كلما طالت القوائم. وفي الوقت نفسه، الروبوتات التي قالت الرياضيات إنها ستنجح تعلمت المهمة بسهولة.

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

ملخص تقني: الفهرسة: البداية والنهاية

بيان المشكلة

تبحث هذه الورقة في القدرة التعبيرية واختناقات المعلومات في بنيات التعلم العميق الحديثة — وتحديداً الشبكات العصبية المتكررة (RNNs)، ومحولات Softmax Transformers، ومحولات الانتباه الخطي (Linear-Attention Transformers)، ونماذج حالة الفضاء (SSMs) — من خلال منظور بدائية الفهرسة (indexing primitive).

تُعرَّف مهمة الفهرسة كما يلي: بالنظر إلى تسلسل من $n$ بتات $\sigma_1, \dots, \sigma_n \in \{0, 1\}$ وفهرس $i \in \{1, \dots, n\}$ ، يجب على النموذج إخراج قيمة البت رقم $i$ ، أي $\sigma_i$ . يحلل المؤلفون نوعين محددين من هذه المهمة لاستقصاء القيود الهيكلية المختلفة:

الفهرسة من جهة اليمين (RHI): يظهر الفهرس $i$ في نهاية تسلسل المدخلات (بعد البتات). يجب على النموذج استرجاع $\sigma_i$ بناءً على المعلومات التي تمت معالجتها من الـ $n$ بت السابقة.
الف فهرسة من جهة اليسار (LHI): يظهر الفهرس $i$ في بداية تسلسل المدخلات (قبل البتات). يجب على النموذج نقل معلومات الفهرس عبر التسلسل لاسترجاع $\sigma_i$ في النهاية.

تركز الدراسة على البنيات "الصغيرة"، والمعرّفة بأنها تمتلك عدد بارامترات $o(1)$ (عدد ثابت من البارامترات بالنسبة لطول التسلسل $n$ ) وإمكانية استخدام حسابات حقيقية ذات دقة لانهائية.

المنهجية

يستخدم المؤلفون إطاراً نظرياً يعتمد على التعقيد السببي (causal complexity) وأبعاد VC (VC dimension) لاستخلاص حدود دنيا غير مشروطة.

التعقيد السببي

بالنسبة للبنيات السببية (المقنعة/masked)، حيث تعتمد المخرجات عند الموضع $k$ فقط على المدخلات من $1 $إلى$ k $، يقدم المؤلفون مفهوم **التعقيد السببي**. يقيس هذا المفهوم الحد الأدنى للبعد$ s $الذي يمكن ضغط تاريخ المدخلات ($ x_1, \dots, x_{k-1} $) إليه (عبر دالة "بصمة") بحيث يمكن حساب المخرج رقم$ k $من هذا التمثيل المضغوط والمدخل الحالي$ x_k$ باستخدام تعقيد حسابي منخفض.

رؤية جوهرية: إذا كانت البنية ذات تعقيد سببي منخفض (تحديداً $o(1)$ )، فإنها لا تستطيع ضغط التاريخ الضروري لحل المهام التي تتطلب استرجاع معلومات ماضية محددة عندما لا تكون تلك المعلومات متاحة فوراً.

الأدوات النظرية

أبعاد VC: قام المؤلفون بتكييف التقنية من Kozachinskiy et al. (2025) لإظهار أنه إذا حل النموذج مهمة الفهرسة، فإن فئة المفاهيم المرتبطة به يجب أن تمتلك بُعد VC لا يقل عن $n$ .
التعقيد الحسابي: استخدموا التعقيد الحسابي للدوال التي تحسبها الطبقات (بما في ذلك الدوال الأسية، والعمليات الحسابية، والجمل الشرطية) لتقييد أبعاد VC.
الحدود غير المشروطة: على عكس الأعمال السابقة التي اعتمدت على افتراضات الدقة المحدودة، فإن هذه النتائج صالحة حتى للنماذج التي تستخدم أرقاماً حقيقية ذات دقة لانهائية.

التحقق التجريبي

تم التحقق من النتائج النظرية من خلال تجارب على مهام الفهرسة الثنائية لأطوال تسلسلات $n \in \{8, 16, 32, 64\}$ . يقارن المؤلفون بين:

النسخ الكاملة والمسببة (causal) من نماذج Softmax وLinear-Attention Transformers.
الشبكات العصبية المتكررة (تحديداً GRUs).
نماذج حالة الفضاء (SSMs) (تحديداً Mamba).
تم تدريب جميع النماذج من الصفر مع ثبات المعلمات الفائقة (hyperparameters) لمراقبة ديناميكيات التعلم مع زيادة $n$ .

المساهمات والنتائج الرئيسية

1. الفهرسة من جهة اليمين (الفهرس في النهاية)

في هذا السيناريو، يعالج النموذج جميع الـ $n$ بت قبل رؤية الفهرس. لحل المهمة، يجب على النموذج ضغط سلسلة الـ $n$ بت كاملة في حالة (state) صغيرة بما يكفي ليتم معالجتها بواسطة رمز الفهرس.

استحالة الحل للبنيات ذات التعقيد السببي المنخفض: يثبت المؤلفون أنه لا يمكن لأي عدد ثابت ( $O(1)$ $O (1)$ ) من الطبقات ذات التعقيد السببي $o(1)$ $o (1)$ أن يحل مهمة RHI.
- البنيات المتأثرة: الشبكات العصبية المتكررة الصغيرة، ونماذج SSM (مثل Mamba)، ونماذج Linear-Attention Transformers المقنعة (masked) جميعها تمتلك تعقيداً سببياً $o(1)$ . وبناءً عليه، لا يمكنها حل RHI في عدد ثابت من الطبقات، حتى مع الدقة اللانهائية.
- التأكيد التجريبي: تفشل النماذج في هذه الفئة (طبقة واحدة ومتعددة الطبقات من causal linear-attention، وGRUs، وMamba) باستمرار في تعلم RHI مع نمو $n$ ، حيث تصل نسبة النجاح إلى 0% عند $n=64$ .
إمكانية الحل للبنيات ذات التعقيد السببي العالي:
- محولات Softmax: يمكن لطبقة واحدة بـ $O(1)$ من البارامترات حل RHI. ويُعزى ذلك إلى تعقيدها السببي العالي (عبر آلية softmax التي تسمح بالانتباه العالمي/global attention).
- Full Linear-Attention: يمكن لطبقتين بـ $O(1)$ من البارامترات حل RHI.
- التأكيد التجريبي: تتعلم هذه التكوينات المهمة بسهولة، مع معدلات نجاح عالية حتى عند $n=64$ .

2. الفهرسة من جهة اليسار (الفهرس في البداية)

في هذا السيناريو، يتم معالجة الفهرس أولاً ويجب نقله عبر التسلسل وصولاً إلى موضع البت ذي الصلة.

هيمنة الشبكات العصبية المتكررة (RNNs): يمكن للشبكات العصبية المتكررة الصغيرة حل LHI في طبقة واحدة بـ $O(1)$ من البارامترات. فهي تحافظ طبيعياً على حالة مخفية (hidden state) يمكنها حمل الفهرس $i$ وتحديث إحداثي معين عند مواجهة البت رقم $i$ .
محدودية البنيات الأخرى:
- نماذج SSM وLinear-Attention: لا تستطيع نماذج 1-layer SSM ولا نماذج 1-layer Linear-Attention (سواء كانت مقنعة أو كاملة) حل LHI بـ $o(1)$ من البارامترات. إن خطية تحديثات SSM تمنعها من "كتابة" قيمة البت بشكل انتقائي في موضع محدد بناءً على الفهرس دون خلط المعلومات بطريقة تمنع الاسترجاع.
- محولات Softmax: تفشل محولات 1-layer Softmax أيضاً في حل LHI بـ $o(1)$ من البارامترات.
الحل عبر العمق: يمكن لجميع البنيات (بما في ذلك SSMs، وLinear-Attention، وSoftmax Transformers) حل LHI إذا مُنحت طبقتين بـ $O(1)$ من البارامترات. الطبقة الأولى تقوم بنشر الفهرس، والثانية تقوم باسترجاع البت.
التأكيد التجريبي: تنجح نماذج 1-layer GRUs في جميع الأطوال. بينما تفشل نماذج 1-layer Mamba وLinear-Attention عند $n \ge 16$ . أما النسخ ذات الطبقتين من جميع البنيات فتنجح.

جدول ملخص للحد الأدنى من الطبقات المطلوبة

البنية	الفهرسة من جهة اليسار (LHI)	الفهرسة من جهة اليمين (RHI)
Full Softmax	2	1
Causal Softmax	2	1
Full Linear-Attention	2	2
Causal Linear-Attention	2	$\omega(1)$ (مستحيل)
SSM (مثل Mamba)	2	$\omega(1)$ (مستحيل)
RNN	1	$\omega(1)$ (مستحيل)

(ملاحظة: $\omega(1)$ تشير إلى أن عدد الطبقات المطلوبة ليس محدوداً بثابت؛ أي أنه ينمو مع $n$ .)

الأهمية والادعاءات

تدعي الورقة أنها تقدم أول حدود دنيا متعددة الطبقات وذات دقة لانهائية لفئة من البنيات ذات التعقيد السببي المنخفض، بما في ذلك SSMs، وRNNs، ومحولات Linear-Attention المقنعة.

الفصل بين البنيات: تكشف بدائية الفهرسة عن فصل جوهري بين البنيات. فبينما يمكن لنماذج Softmax Transformers ونماذج Full Linear-Attention حل RHI بكفاءة، فإن النسخ المقنعة ونماذج SSM لا تستطيع ذلك، مما يسلط الضوء على الدور المحدد لآليات الانتباه العالمي في التغلب على اختناقات المعلومات.
دور الخطية: تشير النتائج إلى أن قواعد التحديث الخطية لـ SSMs، والتي غالباً ما يُشاد بكفاءتها، تصبح عبئاً في مهام LHI حيث تتطلب الكتابة الانتقائية غير الخطية في خطوة واحدة.
التوافق بين النظرية والتطبيق: تُظهر التجارب أن نتائج الاستحالة النظرية (الحدود الدنيا التقاربية) تظهر نوعياً في إعدادات التدريب المحدودة. التكوينات التي تمتلك حلولاً نظرية تتعلم المهمة بقوة، بينما تلك التي تفتقر إليها تعاني مع زيادة طول التسلسل، حتى لو نجحت عند قيم $n$ الصغيرة.
التواضع: يذكر المؤلفون صراحة أن فشل التدريب ليس دليلاً على الاستحالة، كما أن النجاح عند قيم $n$ الصغيرة لا ينفي الحدود الدنيا التقاربية. ومع ذلك، فإن الارتباط القوي بين حدودهم النظرية والأداء التجريبي يشير إلى أن التعقيد السببي هو متنبئ قوي لقابلية التعلم لمهام الاسترجاع.

يوسع هذا العمل تحليل القدرة التعبيرية لمحولات (Transformer) — الذي ركز سابقاً على تركيب الدوال ورؤوس الاستقراء (induction heads) — ليشمل البدائل الحديثة والفعالة، موفراً تبريراً رياضياً صارماً لقيودها في سيناريوهات استرجاع المعلومات المحددة.