Average Attention Transformers and Arithmetic Circuits

ملخص تقني: محولات الانتباه المتوسط (Average Attention Transformers) والدوائر الحسابية

بيان المشكلة
ركزت التحليلات النظرية الحالية لقدرة المحولات (Transformers) التعبيرية بشكل أساسي على مسائل القرار فوق أبجديات منتهية، حيث قارنت المحولات بفئات الدوائر البوليانية (مثل $AC^0$ و $TC^0$) أو الصيغ المنطقية. هذه النتات تقتصر على التعرف على اللغات. تعالج هذه الورقة فجوة في فهم القدرة الحسابية للمحولات كدوال "من تسلسل إلى تسلسل" (sequence-to-sequence) تعمل على متجهات من الأعداد الحقيقية أو النسبية. يهدف المؤلفون إلى توصيف القدرة التعبيرية لمشفرات المحولات (Transformer encoders) من خلال مقارنتها مباشرة بالدوائر الحسابية، التي تحسب الدوال فوق الحلقات شبه المجموعية (semirings) باستخدام عمليات مثل الجمع، والضرب، ودالة الإشارة (sign function).

المنهجية
قام المؤلفون بتكييف نموذج محول معمّم (بناءً على Hao et al., 2022) ليعمل فوق حلقات شبه مجموعية تعسفية. تشمل الخيارات المنهجية الرئيسية ما يلي:

1. تعريف النموذج: عرّفوا "محولات دوائر الانتباه المتوسط" (average attention circuit transformers)، حيث تُستبدل الشبكات الأمامية التقليدية (feed-forward networks) بدوائر حسابية، وتستخدم آلية الانتباه "انتباهًا صلبًا متوسطًا" (average hard attention) - أي الانتباه إلى جميع المتجهات ذات درجات الانتباه القصوى.
2. عائلات الدوائر: حللوا ثلاث فئات من عائلات الدوائر الحسابية ذات العمق الثابت والحجم متعدد الحدود:
   • $FNC^0_R$: ذات مدخلات محدودة (Bounded fan-in).
   • $FSAC^0_R$: ذات مدخلات شبه غير محدودة (Semi-unbounded fan-in) (جمع غير محدود، ضرب ثنائي).
   • $FAC^0_R$: ذات مدخلات غير محدودة (Unbounded fan-in) (جمع وضرب غير محدودين).
     تم توسيع هذه الفئات باستخدام دالة sign للتعامل مع العمليات غير المستمرة.
3. بناء المحاكاة:
   • الدوائر إلى المحولات: لمحاكاة دائرة ما، يقوم المؤلفون بتشفير البنية الرسومية للدائرة (البوابات والحواف) في تسلسل من المتجهات. يمثل كل متجه حافة أو بوابة، ويحتوي على مؤشرات للمتطلبات السابقة/اللاحقة، وأنواع البوابات، والقيم.
   • آليات الانتباه: صمموا دوال انتباه محددة ($f^{att}_E$ و $f^{att}_V$) تسمح للمتجهات بالانتباه إلى مقدماتها بناءً على مطابقة المؤشرات.
   • التجميع والتنشيط: استخدموا تجميع الانتباه الصلب المتوسط لتجميع القيم من المقدمات. ومن الأهمية بمكان، قاموا ببناء دوال تنشيط تختار العملية المناسبة (الجمع، أو الضرب، أو الهوية) بناءً على نوع البوابة المشفر في المتجه.
   • التعامل مع القياس (Scaling): نظرًا لأن الانتباه المتوسط يقلص النتائج بمقدار $1/k$ (حيث $k$ هو عدد المتجهات التي تم الانتباه إليها)، تتضمن عملية البناء آليات لعد المقدمات وإعادة قياس المخرجات لاستعادة القيمة الحسابية الصحيحة.

النتائج الرئيسية
تثبت الورقة وجود تطابق دقيق بين القدرة الحسابية لهذه المحولات الحسابية المحددة وفئات الدوائر الحسابية:

1. الحد الأعلى (Upper Bound): لأي حلقة شبه مجموعية $R$، فإن الدوال التي تحسبها محولات دوائر الانتباه المتوسط تقع ضمن الفئة $FSAC^0_R[\text{sign}]$. وهذا ينطبق حتى على المحولات القياسية ذات الانتباه المتوسط التقليدي، بشرط تقييد دوال التنشيط الخاصة بها لتكون من نفس فئة الدائرة.
2. الحد الأدنى (المحاكاة) (Lower Bound/Simulation): إذا كانت الحلقة شبه المجموعية $R$ هي امتداد لـ $\mathbb{Q}$ مرتب بـ $\mathbb{Z}$، فإنه لأي عائلة دوائر في $FSAC^0_R[\text{sign}]$ بعمق $K$، يوجد محول بـ $2K$ طبقة يمكنه محاكاة العائلة بأكملها.
   • تعمل المحاكاة مع الدوائر ذات المدخلات غير المحدودة باستخدام الانتباه المتوسط.
   • بالنسبة للدوائر ذات المدخلات شبه غير المحدودة، يمكن تكييف البناء لاستخدام انتباه حاصل الضرب النقطي القياسي.
   • بالنسبة للدوائر ذات المدخلات المحدودة، يمكن تقييد البناء أكثر باستخدام الانتباه الصلب الأيسر أو الأيمن.
3. نظريات محددة:
   • النظرية 4.5: يمكن لمحول ببعد 7 و $2K$ طبقة أن يحاكي أي دائرة $R$ غير محدودة المدخلات بعمق $\le K$ (حيث $R$ هو امتداد لـ $\mathbb{Q}$ مرتب بـ $\mathbb{Z}$).
   • النظرية 4.11: يمكن لمحول ببعد 9 و $2K$ طبقة أن يحاكي أي دائرة $FSAC^0_R[\text{sign}]$.

الأهمية والادعاءات
يزعم المؤلفون أن نتائجهم توفر منظورًا جديدًا للقدرة التعبيرية للمحولات من خلال الربط بين مجالات نظرية تعلم الآلة والحساب الجبري.

• التكافؤ النظري: أثبتوا أن محولات الانتباه المتوسط مكافئة حسابيًا لفئة الدوائر الحسابية ذات العمق الثابت مع الجمع غير المحدود، والضرب الثنائي، وبوابات الإشارة ($FSAC^0_R[\text{sign}]$).
• القيود: تشير الورقة صراحة إلى أن هذا التكافؤ يعتمد على استخدام المحول لدوائر حسابية (أو دوال مكافئة) كدوال تنشيط. لا تستطيع المحولات القياسية ذات الشبكات الأمامية (feed-forward networks) محاكاة هذه الدوائر لأن الشبكات الأمامية لا يمكنها بطبيعتها إجراء عملية ضرب مدخلين عشوائيين كما هو مطلوب للمحاكاة.
• عدم الانتظام (Non-Uniformity): أوضح المؤلفون أنه بينما يمكن للمحولات محاكاة عائلات دوائر محددة، فإن هذا لا يعني أن كل دالة في $FSAC^0_R[\text{sign}]$ يتم حسابها بواسطة محول واحد، حيث أن عائلات الدوائر هي نموذج حسابي غير منتظم.
• الإمكانات المستقبلية: تقترح الورقة أن التقدم النظري في الحساب الجبري قد يفيد نظرية تعلم الآلة والعكس، وأن النتائج النظرية قد تلهم التطورات العملية، رغم عدم اقتراح تطبيقات محددة.

هذا العمل مقدم كنسخة أولية (مايو 2026) من معهد علوم الحاسوب النظرية في جامعة لايبنيز هانوفر.