Parity, Sensitivity, and Transformers

بناءً على النص المقدم، إليك ملخص تقني مفصل لورقة البحث "التكافؤ، الحساسية، والمحولات" (Parity, Sensitivity, and Transformers).

بيان المشكلة

تتناول الورقة البحثية السؤال الجوهري المتعلق بمدى قدرة التعبير (expressivity) لهياكل المحولات (Transformer architectures)، وتحديداً فيما يتعلق بمهمة PARITY (التكافؤ). مهمة PARITY هي دالة بولية (Boolean function) تُخرج القيمة 1 إذا كان عدد الواحدات في تسلسل مدخل ثنائي فردياً، و0 خلاف ذلك. وهي مشكلة نموذجية في علوم الحاسوب النظرية معروفة بحساسيتها العالية (حيث يؤدي تغيير أي بت واحد إلى تغيير المخرجات).

بينما أثبتت الأبحاث السابقة أن المحولات ذات آليات الانتباه "الصلبة" (hard attention) -وتحديداً الانتباه الصلب الفريد (UHAT)- لا يمكنها حساب PARITY في عمق ثابت، إلا أن قدرات المحولات ذات الانتباه "الناعم" (soft attention/softmax) لا تزال أقل وضوحاً. تعتمد البناءات الحالية لمحولات الانتباه الناعم القادرة على حساب PARITY على افتراضات "غير عملية"، مثل:

• الترميزات الموضعية (Positional encodings) التي تعتمد على الطول الإجمالي للمدخلات ($n$).
• آليات الانتباه الصلبة.
• تطبيع الطبقة (Layer normalization) مع معامل تنظيم $\epsilon = 0$.
• عدم التوافق مع القناع السببي (Causal masking).

علاوة على ذلك، ظل التساؤل مفتوحاً حول ما إذا كان بإمكان محول مكون من طبقة واحدة حساب PARITY.

المنهجية

يستخدم المؤلفون نهجين منهجيين متميزين لمعالجة الحد الأدنى (lower bound) والحد الأعلى (upper bound/construction) لقدرة التعبير للمحولات تجاه مهمة PARITY.

1. الحد الأدنى عبر الحساسية المتوسطة (Average Sensitivity)
لإثبات أن محولاً من طبقة واحدة لا يمكنه حساب PARITY، يستخدم المؤلفون مفهوم الحساسية المتوسطة.

• التعريف: الحساسية المتوسطة لدالة $f$ هي القيمة المتوقعة لمواقع بتات المدخلات بحيث يؤدي تغيير البت إلى تغيير مخرجات الدالة. بالنسبة لـ PARITY، هذه القيمة هي بالضبط $n$ (نمو خطي).
• المنطق: ينمذج المؤلفون حساب المحول ذي الطبقة الواحدة كدالة يمكن التعبير عنها في المنطق من الدرجة الأولى للأعداد الحقيقية $(\mathbb{R}, <, +, \cdot)$. ومن خلال تطبيق نظرية تارسكي-سيدنبرغ (Tarski-Seidenberg theorem) (حذف المكممات)، يثبتون أن أي دالة يحسبها محول ذو طبقة واحدة يمكن تمثيلها كمزيج بولي لعدد ثابت من دوال عتبة كثيرات الحدود (PTFs) من درجة منخفضة.
• التقييد: بالاستناد إلى نتيجة لـ "كين" (Kane)، يثبتون أن الحساسية المتوسطة لـ PTFs ذات الدرجة المنخفضة تنمو بمعدل $O(\sqrt{n} \cdot (\log n)^{O(1)})$. وبما أن الحساسية المتوسطة لـ PARITY تنمو خطياً ($n$)، فإن المحول ذي الطبقة الواحدة لا يمكنه حسابها.

2. الحد الأعلى عبر بناء جديد (New Construction)
لإثبات أن PARITY يمكن حسابها بواسطة محول دون افتراضات غير عملية، يقترح المؤلفون بناءً جديداً مكوناً من أربع طبقات.

• الآلية: يستخدم البناء انتباه الـ softmax وترميزات موضعية مستقلة عن الطول ومحدودة حدودياً. كما يتجنب تطبيع الطبقة ويعمل تحت كل من الانتباه الكامل والقناع السببي.
• الاستراتيجية الخوارزمية:
  1. الطبقة 1: تحسب مجموعاً مرجحاً لبتات المدخلات لاستخراج قيمة $\gamma$ مرتبطة بعدد الواحدات ($\Sigma$).
  2. الطبقة 2: تستخدم الترميزات الموضعية ($i \mapsto (\ln i, i^{10})$) والقيمة $\gamma$ لحساب متوسط مرجح $\Gamma$. هذه القيمة تقرب دالة $f(\rho)$ التي تشفر معلومات حول $\Sigma$.
  3. الطبقة 3: تبني أوزان الانتباه $L_{i,n}$ التي تتركز بشدة على الموضع $i = \Sigma$. ويتحقق ذلك باستخدام القيمة $\Gamma$ (المحسوبة في الطبقة 2) لتقريب شكل تربيعي محدد يصل لذروته عند $i = \Sigma$. يثبت المؤلفون أنه بالنسبة للموضع الصحيح، يكون وزن الانتباه أكبر بكثير (بهامش قدره $\Omega(n^6)$) من أي موضع آخر.
  4. الطبقة 4: تحسب مجموعاً مرجحاً لـ $(-1)^i$ باستخدام أوزان الانتباه المركزة. النتيجة هي قيمة $z$ قريبة من $(-1)^\Sigma$، مما يسمح للطبقة النهائية بالتمييز بين التكافؤ الزوجي والفردي.
• التعامل مع المدخلات الكبيرة: للتعامل مع الحالات التي يكون فيها عدد الواحدات ($\Sigma$) كبيراً، يقوم البناء بتقسيم المدخلات إلى $M$ من السلاسل الفرعية (حيث $M$ هو ثابت زوجي)، وحساب تكافؤ كل منها بالتوازي، ثم تجميع النتائج.

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

1. حل مسألة الطبقة الواحدة المفتوحة: تجيب الورقة بشكل حاسم على السؤال المفتوح حول ما إذا كان بإمكان محول من طبقة واحدة حساب PARITY. النتيجة هي سلبية. يثبت المؤلفون أن الحساسية المتوسطة لأي دالة يمكن حسابها بواسطة محول من طبقة واحدة محدودة بـ $O(\sqrt{n} \cdot (\log n)^{O(1)})$، وهو ما لا يكفي للحساسية الخطية لـ PARITY.
2. بناء محسّن لـ PARITY: يقدم المؤلفون بناءً جديداً للمحول مكوناً من أربع طبقات يحسب PARITY. يحسن هذا البناء الأعمال السابقة (مثل Chiang و Cholak, 2022؛ Yang et al., 2025) من خلال إزالة العديد من الافتراضات المقيدة:
   • يستخدم الانتباه الناعم (softmax) بدلاً من الانتباه الصلب.
   • يستخدم ترميزات موضعية مستقلة عن الطول.
   • لا يتطلب تطبيع الطبقة (أو تحديداً لا يعتمد على $\epsilon=0$).
   • متوافق مع القناع السببي (causal masking).
   • الترميزات الموضعية محدودة حدودياً، مما يجعلها قابلة للتطبيق لأطوال المدخلات العملية.
3. متطلبات العمق: توضح الورقة أنه بينما لا تكفي طبقة واحدة، فإن أربع طبقات كافية في ظل تصميمات معمارية واقعية. وهذا يحدد بدقة متطلبات العمق لحساب الدوال ذات الحساسية العالية.

الأهمية

تطور هذه الورقة الفهم النظري لهياكل المحولات من خلال توصيف متطلبات العمق بدقة لمهمة PARITY. ومن خلال ربط قدرة التعبير للمحولات بالحساسية المتوسطة للدوال البولية، يقدم المؤلفون حداً أدنى صارماً يستبعد نماذج الطبقة الواحدة. وفي الوقت نفسه، من خلال تقديم بناء من أربع طبقات يلتزم بالممارسات المعمارية القياسية (الانتباه الناعم، القناع السببي، الترميزات المحدودة)، تثبت الورقة أن PARITY قابلة للحساب بواسطة المحولات دون اللجوء إلى نواتج اصطناعية نظرية.

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