Contrastive Identification and Generation in the Limit

ملخص تقني: التحديد والإنشاء التبايني في الحد

تعريف المشكلة
يقدم هذا العمل استقصاءً نظرياً للتعلم المتعلق بـ التحديد والإنشاء التبايني في الحد (limit). يعالج المؤلفون فجوة في نماذج التعلم التقليدية في الحد (Gold, 1967; Angluin, 1980) والنماذج التوليدية الحالية (Klein-berg and Mullainathan, 2024)، والتي تعتمد على تدفقات من الأمثلة الإيجابية (النص - Text) أو البيانات المصنفة بالكامل (المخبر - Informant). في العديد من السيناريوهات الطبيعية — مثل اختبارات A/B، والتجارب المقارنة، والتعليقات التوضيحية للتشابه وعدم التشابه — تظهر البيانات كـ أزواج غير مرتبة $\{x, y\}$، حيث يعرف المتعلم أن الأمثلة تختلف تحت الفرضية المستهدفة $h$ (أي $h(x) \neq h(y)$)، لكنه لا يعرف أي عنصر هو الإيجابي ($h(x)=1$) وأي عنصر هو السلبي ($h(x)=0$).

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

1. تحديد (Identify) الفرضية المستهدفة $h$ من فئة معروفة $\mathcal{H}$ (الاستقرار على الفرضية الصحيحة).
2. إنشاء (Generate) أمثلة إيجابية جديدة لـ $h$ (إخراج العناصر الموجودة في $\text{supp}(h)$ التي لم تظهر بعد في التدفق).

المنهجية والإطار التقني
المساهمة التقنية المركزية هي تقديم الرسم البياني للتقاطع المشترك (common crossing graph)، ويرمز له بـ $\Gamma(h, g) = \Delta(h) \cap \Delta(g)$، حيث $\Delta(h)$ هي مجموعة كافة الأزواج التي تعبر القطع المعرف بواسطة $h$. يرمز هذا الرسم البياني للغموض الزوجي بين الفرضيات؛ حيث توجد حافة في $\Gamma(h, g)$ إذا كان الزوج يشكل ملاحظة صالحة لكل من $h$ و $g$.

يطبق المؤلفون هذا الكائن الهندسي على ثلاثة مستويات:

• الأزواج: لتحليل القابلية للاستبعاد (eliminability) بين فرضيتين.
• العائلات المحدودة: لتحليل عوائق الإنشاء الناتجة عن العروض المشتركة.
• مجموعات العيب اللانهائية (Infinite Defect Sets): لتحليل المتانة ضد الفساد العدائي.

يستخدم العمل ترجمة نظرية الرسم البياني، مما يقلل الغموض التبايني الزوجي إلى مسألة تغطية: تكون الفرضية $g$ غير قابلة للاستبعاد من $h$ إذا وفقط إذا كان دعم $h$ مغطى بالعقد المتصلة بالحواف في $\Gamma(h, g)$.

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

1. التوصيف الدقيق للتحديد التبايني (CtrId)
يقدم العمل شرطاً ضرورياً وكافياً لتكون الفئة $\mathcal{H}$ قابلة للتحديد من البيانات التباينية. تنتمي الفئة إلى CtrId إذا وفقط إذا كانت:

• قابلة للتحديد النصي (تحقق شرط "Tell-Tale" الخاص بـ Angluin).
• شرط التغطية المتداخلة (Overlapping-Cover Condition): يجب أن يشكل كل زوج من الفرضيات غير القابلة للمقارنة "تغطية متداخلة". وهذا يعني أن دعمهما يجب أن يتقاطع ($\text{supp}(h) \cap \text{supp}(g) \neq \emptyset$) وأن اتحادهما يجب أن يغطي كامل فضاء الأمثلة ($\text{supp}(h) \cup \text{supp}(g) = X$).
• الاستنتاج: تُدخل البيانات التباينية عائقاً جديداً: إذا كانت الفرضيات غير قابلة للمقارنة، أو منفصلة، أو متداخلة ولكنها لا تغطي الفضاء، فلا يمكن التمييز بينها.

2. الإنشاء التبايني وبُعد الإغلاق
يقدم المؤلفون بُعد الإغلاق التبايني ($C^\Delta$)، وهو بُعد توافقي مشابه لبُعد الإغلاق للبيانات الإيجابية (Raman et al., 2025).

• التعريف: $C^\Delta(\mathcal{H})$ هو الحد الأعلى لحجم مجموعات الحواف "المجوفة" المحدودة (مجموعات الأزواج التي لا تفرض عناصر إيجابية جديدة خارج العقد المرصودة).
• النتيجة: تقبل الفئة مولداً تباينياً موحداً إذا وفقط إذا كان $C^\Delta(\mathcal{H}) < \infty$. والتعقيد العيني (sample complexity) المحكم هو $C^\Delta(\mathcal{H}) + 1$.
• الإنشاء غير الموحد: تكون الفئة قابلة للإنشاء غير الموحد إذا أمكن تفكيكها إلى سلسلة من الفئات الفرعية ذات أبعاد إغلاق تبايني محدودة.
• العوائق: يحدد العمل "عوائق العائلة المحدودة"، حيث تسمح مجموعة من الفرضيات بعرض تبايني مشترك مع تقاطع محدود للدعم، مما يمنع إنشاء عناصر جديدة.

3. التسلسل الهرمي الماسي (The Diamond Hierarchy)
في الفئات القابلة للعد ذات الدعم غير المحدود بانتظام (UUS)، تشكل عائلات التعلم الأربع تسلسلاً هرمياً ماسياً صارماً وليس سلسلة خطية:

• الاحتواء الصارم: $\text{CtrId} \subsetneq \text{CtrGen}$ و $\text{CtrId} \subsetneq \text{TxtId}$. وكل من $\text{CtrGen}$ و $\text{TxtId}$ محتواة بشكل صارم في $\text{TxtGen}$.
• عدم القابلية للمقارنة: $\text{CtrGen}$ و $\text{TxtId}$ غير قابلتين للمقارنة متبادلاً.
  • $\text{TxtId} \not\subseteq \text{CtrGen}$: الفئات ذات الدعم المنفصل قابلة للتحديد نصياً ولكنها محجوبة عن الإنشاء التبايني بسبب عوائق التقاطعات المحدودة.
  • $\text{CtrGen} \not\subseteq \text{TxtId}$: الفئات ذات "الدعم المثقوب" (إزالة عنصر من مجموعة لانهائية) قابلة للإنشاء تباينياً عبر النوى النهائية ولكنها تفتقر إلى مجموعات "Tell-Tale" المحدودة المطلوبة للتحديد النصي.

4. انعكاس المتانة تحت الفساد العدائي
يثبت العمل انعكاساً حاداً للعلاقة بين أنماط التحديد تحت الفساد العدائي المحدود:

• هشاشة النص: يمكن لمثال إيجابي واحد فاسد أن يجعل الفئة غير قابلة للتحديد في الإعداد النصي.
• المتانة التباينية: يعرّف المؤلفون عدد العيب $\kappa(h \to g)$، الذي يحصي الحد الأدنى من الانتهاكات المفروضة لفرضية $g$ في أي عرض صالح لـ $h$. إذا كان $\kappa(h \to g) = \infty$، فلا يمكن لأي فساد محدود أن يحجب الانتهاكات.
• فئة أحادية العنصر (Co-Singleton Class): الفئة التي تصنف كل الأمثلة كإيجابية باستثناء "ثقب" واحد هي قابلة للتحديد تحت أي ميزانية فساد محدودة في الإعداد التبايني (باستخدام خوارزمية "عد الغياب")، ولكنها غير قابلة للتحديد حتى مع فساد واحد في الإعداد النصي.
• النتيجة: لكل $k \ge 1$، التحديد التبايني الفاسد بمقدار $k$ والتحديد النصي الفاسد بمقدار $k$ غير قابلين للمقارنة متبادلاً.

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

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