Local Regularization Does Not Characterize Multiclass PAC Learnability

ملخص تقني: التنظيم المحلي لا يحدد قابلية التعلم في فئة متعددة الأصناف ضمن إطار PAC

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

اقترح أسيلس وآخرون (Asilis et al.) التنظيم المحلي (local regularization) كتعميم محتمل لـ ERM في حالة الأصناف المتعددة. يقوم المنظم المحلي بتعيين درجة $\psi(h, x)$ ثابتة لكل فرضية $h$ عند كل نقطة اختبار $x$، بشكل مستقل عن عينة التدريب. وتتنبأ المتعلمة المستحثة بواسطة مثل هذا المنظم بـ "تسمية" (label) الفرضية ذات الحد الأدنى من الدرجة من بين تلك المتسقة مع العينة المرصودة. وبينما أثبت جعفر، وأسيلس، ودغمي سابقاً أن التنظيم المحلي يفشل في توصيف التعلم في النموذج الاستدلالي (transductive model) (حيث يتم اختبار نقطة محددة محجوزة)، ظل التساؤل قائماً حول ما إذا كان هذا المبدأ يحدد قابلية التعلم ضمن إطار PAC، حيث قد تحمل النقطة المحجوزة كتلة سكانية ضئيلة، وقد يؤدي تكرار أخذ العينات نظرياً إلى الكشف عنها.

المنهجية والبناء
يبني البحث مثالاً مضاداً باستخدام فئة فرضيات قابلة للعد تعتمد على البطولات (tournaments) (رسوم بيانية كاملة موجهة).

• فئة الفرضيات ($H$): بالنسبة لعدد صحيح $q \ge 3$، تتوافق الفرضيات مع حواف الرسم البياني الكامل $K_q$. وتتنبأ الفرضية $h_{q,e}$ بـ "الرأس" (الرأس المستهدف) للحافة $e$ ضمن نموذج البطولة $\tau$.
• فضاء الحالات: الحالات هي أزواج $(q, \tau)$، حيث $\tau$ هي بطولة على $q$ من الرؤوس.
• التوزيعات الصعبة: يعرّف المؤلفون عائلة من "التوزيعات الصعبة" $D_{e,v}$ للحافة المستهدفة $e=\{u,v\}$ والطرف النهائي $v$. هذه التوزيعات تكون منتظمة فوق البطولات التي تكون فيها الحافة $e$ موجهة نحو $v$. وبناءً على ذلك، تكون جميع التسميات المرصودة في عينة التدريب متطابقة: $(q, v)$.
• آلية الفشل:
  1. التصفية (Filtering): تقوم عينة التدريب (جميع التسميات متساوية مع $v$) بتصفية "فضاء النسخة" (version space)، مما يبقي فقط على الفرضيات المقابلة للحواف المتصلة بـ $v$ والموجهة نحو $v$ في البطولات التي تم أخذ العينات منها.
  2. الترتيب الثابت (Fixed Ranking): يفرض المنظم المحلي $\psi$ ترتيباً كلياً صارماً على الحواف المتصلة بـ $v$ عند نقطة الاختبار قبل ملاحظة العينة.
  3. الانقلابات الدورية (Cyclic Inversions): ينشأ جوهر الصعوبة من المثلثات الدورية (cyclic triangles) في البطولة. حتى لو قامت العينة بإزالة العديد من المنافسين، فإن الترتيب الثابت للحواف المتبقية يمكن أن "ينقلب" بالنسبة للهدف الحقيقي بسبب الهيكل الدوري. وتحديداً، إذا نجت حافة خارجة (التي لا ينبغي أن تكون هي الهدف) من عملية التصفية وبدت في ترتيب المنظم الثابت قبل حافة الدخول المستهدفة الحقيقية، فإن المتعلمة ترتكب خطأً.

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

1. وجود مثال مضاد: يثبت البحث وجود فئة فرضيات متعددة الأصناف قابلة للعد $H$ قابلة للتعلم بنظام PAC ولكنها ليست قابلة للتعلم بواسطة أي منظم محلي.

   • قابلية التعلم: الفئة قابلة للتعلم بنظام PAC بتعقيد عينة قدره $O(\frac{1}{\varepsilon} \log \frac{1}{\delta})$. وتنجح متعلمة صريحة بمجرد ظهور تسميتي الطرفين في العينة.
   • حد الأبعاد: تمتلك هذه الفئة بُعد "دانيلي-شاليف-شارويت" (DS dimension) لا يتجاوز 2. ويتم إثبات ذلك من خلال إظهار أن صورة كل فرضية تحتوي على تسميتين على الأكثر، مما يمنع تشكيل مكعب زائف ثلاثي الأبعاد.

2. مبرهنة الاستحالة: لأي منظم محلي $\psi$، يوجد متعلم مستحث $A_\psi$ يفشل في تعلم $H$ بنظام PAC.

   • نمط الفشل: لأي منظم ثابت، يظهر المؤلفون أنه لأحجام عينات كبيرة $n$، توجد توزيعات واقعية حيث يتجاوز احتمال الخطأ قيمة ثابتة $\delta_0 = \frac{1}{192e}$.
   • الحدود الكمية: يتم حصر احتمال الخطأ بعيداً عن الصفر ($\varepsilon_0 = \frac{1}{96e}$) لأن العدد المتوقع لـ "الانقلابات" (الحواف الخارجة المصنفة قبل الحواف الداخلة) في هيكل البطولة يظل كبيراً. يعتمد الإثبات على حقيقة أن البطولة العشوائية تحتوي على $\Theta(q^3)$ من المثلثات الدورية، مما يضمن أن أي ترتيب صارم للحواف سيؤدي إلى نسبة ثابتة من أخطاء التنبؤ في حوادث الهدف.

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

• التمييز عن النتائج الاستدلالية: على عكس الحد الأدنى الاستدلالي (transductive lower bound) من قبل جعفر وآخرين، والذي يعتمد على نقطة واحدة محجوزة ذات كتلة سكانية قد تكون ضئيلة، يقوم هذا البناء بتوزيع الخطأ عبر مجموعة من البطولات. يستمر الفشل حتى مع نمو أحجام العينات بشكل تعسفي، مما يمنع المتعلمة من "تعلم" الهيكل الخفي من خلال تكرار أخذ العينات.
• محدودية الدرجات الثابتة: تسلط النتيجة الضوء على الجمود الجوهري في التنظيم المحلي: بما أن ترتيب الفرضيات عند نقطة الاختبار ثابت قبل ملاحظة العينة، فلا يمكن للمتعلمة إعادة ترتيب المنافسين الناجين بناءً على الهيكل المحدد لبيانات التدريب. في إعداد البطولة، يؤدي عدم القدرة على إعادة الترتيب هذا إلى خطأ ثابت في السكان رغم أن الفئة تمتلك بُعد DS منخفض (DS-dim $\le 2$) وقابلة للتعلم بكفاءة بوسائل أخرى.
• النطاق: ينطبق هذا النتيجة تحديداً على المنظمات حيث تكون الدرجات ثابتة بشكل مستقل عن العينة. ولا يتناول هذا الأمر أطر العمل غير الخاضعة للإشراف (unsupervised frameworks) حيث قد تعتمد قاعدة التنظيم على العينة غير الموسومة.

باختصار، يقدم البحث إجابة سلبية حاسمة على السؤال حول ما إذا كان التنظيم المحلي يحدد قابلية التعلم في حالة الأصناف المتعددة، موضحاً أنه حتى للفئات ذات البعد التوليفي المنخفض (DS-dim $\le 2$) والتعقيد الأمثل للعينة، يمكن للمنظمات ذات الدرجات الثابتة أن تفشل في التعلم.