🤖 machine learning

Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization

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

المؤلفون الأصليون: Artur Back de Luca, Kimon Fountoulakis

نُشر 2026-05-25

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

CC BY 4.0

المؤلفون الأصليون: Artur Back de Luca, Kimon Fountoulakis

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

تخيل أنك معلم يحاول التحقق مما إذا كان الطالب قد تعلم حقًا قاعدة رياضية معينة، مثل "كيفية جمع رقمين". لديك قائمة من الأمثلة (أزواج المدخلات والمخرجات) وتريد أن تتأكد بنسبة 100% من أن الطالب لا يخمن أو يتبع خدعة ما.

هذه الورقة البحثية تطرح سؤالاً جوهرياً: كم عدد الأمثلة التي تحتاج لإظهارها للطالب لتثبت أنه يعرف القاعدة بالضبط، وليس مجرد قاعدة مشابهة جداً لها؟

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

إليك تفصيل لنتائجهم باستخدام تشبيهات بسيطة:

1. مشكلة "المحتال"

تخيل أن لديك طالباً مثالياً يعرف قاعدة جمع الأرقام. تريد إثبات أنه الوحيد الذي يعرفها.

السيناريو السهل: إذا كان هذا الطالب هو الوحيد في الغرفة، فقد تحتاج فقط إلى إظهار 5 أو 10 أمثلة له لتثبت أنه يعرف القاعدة.
السيناريو الصعب: الآن، تخيل أنك دعوت 1,000 من "المحتالين" إلى الغرفة. هؤلاء المحتالون مثاليون تقريباً؛ فهم يعطون الإجابة الصحيحة في 99.9% من الحالات. الحالة الوحيدة التي يخطئون فيها هي على مجموعة محددة وخفية من الأرقام (مثل الأرقام التي تبدأ بالرقم '7').

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

2. تشبيه "الإبرة في كومة القش"

لإثبات أن الطالب هو "الحقيقي" وليس محتالاً، عليك العثور على الرقم المحدد الذي يختلفون عنده.

إذا كان لديك 1,000 محتال، وكل واحد منهم يخفي خطأه في زاوية صغيرة ومختلفة من كون الأرقام، فعليك فحص كل زاوية لتتأكد.
تثبت الورقة أنه إذا أضفت بوابة واحدة إضافية إلى دائرة (أو "رأس انتباه" إضافي إلى نموذج Transformer)، فإن عدد هذه الزوايا الخفية ينفجر.
النتيجة: لضبط جميع المحتالين، قد تحتاج إلى فحص مليارات الأمثلة. إذا فحصت بضعة آلاف فقط (عدد "متعدد الحدود" - polynomial)، فمن المرجح أن تفوتك هؤلاء المحتالين، وسيجتاز الطالب الاختبار رغم أنه في الواقع مخطئ.

3. الشخصيتان الرئيسيتان

اختبر المؤلفان هذا على نوعين من "الطلاب":

الدوائر (Circuits): فكر فيها كآلات منطقية بسيطة وصارمة (مثل الآلة الحاسبة). وجدوا أن إضافة مفتاح واحد إضافي فقط إلى دائرة بعمق 2 أو أكثر يجعل من الصعب أسياً عملية التصديق على الإجابة.
نماذج الـ Transformers: وهي نماذج الذكاء الاصطناعي القوية التي تقف وراء أدوات الدردشة الآلية. أظهر المؤلفون أن إضافة رأس انتباه واحد إضافي (تعديل معماري طفيف) وبعض الأرقام الإضافية إلى ذاكرة النموذج يجعل من المستحيل التصديق على الإجابة بعدد معقول من الأمثلة.

4. فخ "الكمال شبه التام"

قد تفكر: "حسناً، ولكن ماذا لو تقبلنا ببساطة أن الطالب يرتكب بعض الأخطاء؟ ماذا لو قلنا: 'إذا حصل على 99% صح، فهذا جيد بما يكفي'؟"
تقول الورقة: كن حذراً.

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

5. التجربة في العالم الحقيقي

لإثبات أن هذا ليس مجرد نظرية رياضية، قاموا ببناء هذه النماذج بالفعل:

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

الخلاصة

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

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

ملخص تقني: شهادة الأمثلة صعبة للدوائر والمحولات في ظل الإفراط في التخصيص الأدنى

بيان المشكلة

مع تزايد نشر الشبكات العصبية المتطورة في مهام الاستدلال والخوارزميات، يصبح ضمان صحتها الدقيقة أمراً بالغ الأهمية. غالباً ما تحجب الدقة العالية في المتوسط حالات النجاح (average-case accuracy) السلوكيات غير المتسقة، مما يجعل من الصعب اكتشاف الإخفاقات التي تنحرف عن منطق الاستدلال المنشود. تتناول هذه الورقة مشكلة الشهادة الدقيقة (exact certification): وهي تحديد الحد الأدنى لعدد الأمثلة المسمات (مدخل-مخرج) اللازمة لتحديد فرضية مستهدفة $f^*$ بشكل فريد ضمن فئة فرضيات $\mathcal{H}$ ، بحيث لا توجد فرضية أخرى في $\mathcal{H}$ تتفق مع $f^*$ على كامل النطاق.

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

المنهجية

تستخدم الورقة إطاراً نظرياً متجذراً في تعقيد التدريس (teaching complexity) وتعقيد الدوائر (circuit complexity)، مكملاً بالتحقق التجريبي على مهام الجمع الثنائي.

الإطار النظري

تعريف حجم الشهادة: يعرّف المؤلفون حجم الشهادة، $\text{cert}(f^*, \mathcal{H})$ ، كأصغر حجم لعينة مسمات $S$ بحيث تحتوي فضاء النسخة $V_S^{\mathcal{H}}$ (مجموعة الفرضيات في $\mathcal{H}$ المتسقة مع $S$ ) على $f^*$ فقط.
مبدأ عدم الاتفاق المنفصل (Disjoint-Disagreement Principle): تعتمد استراتيجية الإثبات الجوهرية على بناء مجموعة من فرضيات "المخادع" (deceiver hypotheses). بالنسبة لفرضية مستهدفة $f^*$ $f^{*}$ ، يبني المؤلفون عائلة من الفرضيات $\{g_\pi\}$ ${g_{π}}$ تتفق مع $f^*$ $f^{*}$ في كل مكان باستثناء "كتل محفزة" (trigger blocks) $B_\pi$ $B_{π}$ محددة ومنفصلة زوجياً.
- إذا كانت فئة الفرضيات تحتوي على مثل هذه العائلة من المخادعين حيث تكون مجموعات عدم الاتفاق (disagreement sets) منفصلة، فإن أي شهادة دقيقة يجب أن تحتوي على مثال واحد على الأقل من كل مجموعة عدم اتفاق.
- وبناءً على ذلك، يتم تحديد الحد الأدنى لحجم الشهادة بعدد هذه الكتل المنفصلة.
تحليل الإفراط في التخصيص (Overparametrization Analysis): يحلل المؤلفون كيف أن إضافة سعة ضئيلة (مثل بوابة إضافية واحدة في الدوائر، أو رأس انتباه إضافي وعرض تمثيل ثابت في المحولات/Transformers) تسمح ببناء هذه العائلات الأسية من المخادعين لكل هدف في الفئة الأصلية الأصغر.

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

يكمل المؤلفون النظرية بتجربتين على التعرف على الجمع الثنائي:

الدوائر المصممة: يقومون بتطبيق بناء المخادع النظري لدوائر العتبة ( $TC_0$ ) التي تتعرف على الجمع. يقومون بتوليد مجموعة من $2^n$ من الدوائر غير الصحيحة، كل منها يختلف عن الهدف في كتلة مدخلات متميزة، ويقيسون عددها الذي ينجو من أخذ العينات المنتظم لمرشحات الشهادة.
المحولات المدربة: يقومون بتدريب محولات (Transformers) تعمل بنظام المشفر فقط (encoder-only) على الجمع بـ 10 بت. بعد اختيار النماذج التي تجتاز فحوصات التحقق الصارمة (دقة 99.9%)، يقيمونها على مجموعة اختبار كبيرة غير مدرجة في التدريب. يحللون "نجاة" هذه النماذج غير الكاملة (المخادعين) عند تعرضها لمرشحات شهادة مأخوذة بالعينات المنتظمة، واختبار ما إذا كان يمكن اكتشاف الأخطاء المتبقية باستخدام عينات ذات حجم حدودي (polynomial-sized).

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

1. الصعوبة الأسية الناتجة عن الإفراط في التخصيص الأدنى

المساهمة النظرية الرئيسية هي إثبات أن الشهادة حساسة للغاية لحجم فئة الفرضيات.

دوائر العتبة ( $TC_0$ ): بالنسبة لدوائر بعمق $d \ge 2$ ، فإن إضافة بوابة عتبة إضافية واحدة (زيادة ميزانية البوابات من $s$ إلى $s+1$ ) تجبر حجم الشهادة لكل هدف في الفئة الأصلية $TC_{d,s}$ على أن يصبح أسياً في بُعد المدخلات $n$ . وتحديداً، $\text{cert}(f^*, TC_{d,s+1}) \ge 2^{\Omega(n)}$ .
المحولات (Transformers): بالنسبة للمحولات ذات الدقة اللوغاريتمية مع الانتباه المتوسط الصلب (AHAT)، فإن إضافة رأس انتباه واحد في الطبقة النهائية وستة إحداثيات مساعدة للتمثيل/البقايا يخلق فئة موسعة تصبح فيها الشهادة صعبة بشكل أسي. حتى لو كان للهدف $f^*$ حجم شهادة حدودي في البنية الأصغر، فإنه يتطلب عدداً أسياً من الأمثلة للشهادة ضد البنية الأكبر قليلاً.
عدم الفراغ (Non-Vacuity): يثبت المؤلفون أن هذه الحدود الدنيا ليست فارغة. فهم يظهرون أن الفئات الأصغر ( $TC_{d,s}$ والمحولات القياسية) تحتوي على أهداف ذات أحجام شهادة حدودية (تحديداً $O(\log |\mathcal{H}|)$ )، ومع ذلك تصبح هذه الأهداف نفسها صعبة الشهادة بشكل أسي بمجرد توسيع الفئة بشكل أدنى.

2. صعوبة الشهادة التقريبية

توسع الورقة هذه النتائج لتشمل الشهادة التقريبية:

تحمل الخطأ المطلق: إذا كانت الشهادة تسمح بعدد حدودي فقط من الأخطاء ( $R = \text{poly}(n)$ )، فإن حجم الشهادة يظل أسياً ( $2^{\Omega(n)}$ ).
تحمل الخطأ النسبي: إذا كانت الشهادة تسمح بخطأ نسبي ثابت ( $\epsilon$ )، يمكن أن يكون حجم الشهادة صغيراً (حدودي في $1/\epsilon$ ). ومع ذلك، يأتي هذا على حساب السماح بعدد أخطاء مطلقة هائل. يوضح المؤلفون أن ضمانات الخطأ النسبي الثابت يمكن أن تخفي أخطاءً أسية، بينما لا تزال ضمانات الخطأ المطلق الحدودية تتطلب شهادات أسية.

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

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

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

تدعي الورقة تقديم شكل كمي لصعوبة الشهادة للتعلم الدقيق. وتكمن أهميتها في التأكيدات التالية:

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

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