🤖 machine learning

Universal Multiclass Transductive Online Learning

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

المؤلفون الأصليون: Steve Hanneke, Hongao Wang

نُشر 2026-06-01

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

CC BY 4.0

المؤلفون الأصليون: Steve Hanneke, Hongao Wang

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

تخيل أنك تلعب لعبة تخمين عالية المخاطر ضد خصم ماكر. إليك الإعداد:

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

تبحث هذه الورقة البحثية، بعنوان "التعلم عبر الإنترنت الاستدلالي متعدد الفئات الشامل" (Universal Multiclass Transductive Online Learning)، في مدى جودة أدائك في هذه اللعبة عندما لا تكون الإجابات الممكنة مجرد "نعم" أو "لا"، بل يمكن أن تكون أي رقم في قائمة لانهائية (مثل 1، 2، 3... وصولاً إلى ما لا نهاية).

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

1. النتائج الثلاث الممكنة (التثليث)

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

🟢 الأخضر (أخطاء ثابتة): إذا كان كتاب القواعد بسيطاً بما يكفي، فسترتكب خطأً بضع مرات فقط في البداية، ثم ستصيب في كل شيء للأبد بعد ذلك. لا يهم كم تستمر اللعبة؛ إجمالي أخطائك يظل منخفضاً ومستقراً.
🟡 الأصفر (أخطاء لوغاريتمية): إذا كان كتاب القواعد أكثر تعقيداً قليلاً، فسترتكب المزيد من الأخطاء، لكنها تنمو ببطء شديد. تخيل أن اللعبة استمرت 1,000 جولة؛ قد ترتكب 10 أخطاء. إذا استمرت مليون جولة؛ قد ترتكب 20 خطأً. الأخطاء تنمو، لكنها تنمو ببطء شدو لدرجة أنها لا تُذكر مقارنة بالوقت الإجمالي.
🔴 الأحمر (غير قابل للتعلم): إذا كان كتاب القواعد فوضوياً للغاية، يمكن للخصم أن يجبرك على ارتكاب خطأ في كل جولة تقريباً. مهما كنت ذكياً، لا يمكنك تعلم النمط. أخطاؤك ستنمو بنفس سرعة اللعبة نفسها.

2. "الخريطة" الجديدة (شجرة LCLL)

لمعرفة أي من الألوان الثلاثة ينطبق على كتاب قواعد معين، اخترع المؤلفون طريقة جديدة لرسم خريطة للاحتمالات. يسمونها شجرة المستوى المقيد-ليتليستون-ليتليستون (LCLL).

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

3. لماذا فشلت الخرائط السابقة

حاول المؤلفون استخدام خرائط أقدم (مثل شجرة VCL أو شجرة DSL) التي نجحت في ألعاب "نعم/لا" البسيطة. ووجدوا أنها فشلت عندما يمكن أن تكون الإجابات أرقاماً لانهائية.

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

4. استراتيجية "اللعبة"

لإثبات نظريتهم، صمم المؤلفون نوعاً جديداً من الألعاب (لعبة Gale-Stewart).

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

5. ماذا لو كانت الإجابات فوضوية؟ (الحالة اللاحتمية/Agnostic)

تسأل الورقة أيضاً: "ماذا لو لم يتبع الخصم كتاب قواعد مثالي، بل قدم إجابات عشوائية فقط؟"

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

ملخص

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

ملخص تقني: التعلم عبر الإنترنت عبر الإنترنت (Transductive) متعدد الفئات والشامل (Universal)

بيان المشكلة
يتقصى هذا البحث مشكلة التصنيف عبر الإنترنت (Transductive) الشامل متعدد الفئات مع فضاء تسميات (Labels) لا نهائي تعداداً. في هذا الإطار، يشارك المتعلم في لعبة متسلسلة ضد خصم (Adversary). قبل بدء اللعبة، يختار الخصم تسلسلاً من الحالات $X = \{X_t\}_{t \in \mathbb{N}}$ ويكشف التسلسل بأكمله للمتعلم مسبقاً. في كل جولة $t$ ، يتنبأ المتعلم بتسمية $\hat{Y}_t$ بناءً على تسلسل الحالات المعروف و تاريخ التسميات الحقيقية $Y_{<t}$ . بعد ذلك، يكشف الخصم عن التسمية الحقيقية $Y_t$ . يُقاس أداء المتعلم بعدد الأخطاء (في الحالة الواقعية/Realizable) أو الندم (Regret) (في الحالة غير الواقعية/Agnostic).

الهدف الجوهري هو توصيف القابلية للتعلم الشامل (Universal Learnability) لفئة المفاهيم $\mathcal{H}$ . وبخلاف المعدلات الموحدة (Uniform rates) التي توفر حدوداً مستقلة عن تسلسل البيانات المحدد، تتطلب القابلية للتعلم الشامل أن يكون لكل تسلسل واقعي خوارزمية يكون فيها عدد الأخطاء نمواً دون خطي (Sublinear) (أو يحقق حدوداً محددة) بالنسبة للأفق الزمني $T$ . يعالج البحث تحديداً الفجوة في الأدبيات الحالية، والتي ركزت بشكل أساسي على التصنيف الثنائي أو المعدلات الموحدة، من خلال توسيع هذه المفاهيم لتشمل إعدادات متعددة الفئات مع تسميات غير محدودة.

المنهجية والمفاهيم الأساسية
يستخدم المؤلفون نظرية الألعاب التوافقية والتحليل الهيكلي لفئات المفاهيم لاستخلاص شروط القابلية للتعلم.

الهياكل التوافقية:
- شجرة ليتلستون (Littlestone Tree): هيكل قياسي للتعلم عبر الإنترنت حيث العقد هي حالات والحواف هي تسميات.
- شجرة ليتلستون مقيدة بالمستوى (Level-Constrained Littlestone - LCL): تنويع حيث تشترك جميع العقد عند نفس العمق في نفس الحالة.
- شجرة (LCL-Littlestone - LCLL): هيكل جديد تم تقديمه في هذا العمل. يوسع شجرة ليتلستون لإعدادات متعددة الفئات مع تسميات غير محدودة. في شجرة LCLL، ترتبط العقدة عند العمق $k$ بتسلسل من $k+1$ من الحالات، وتمثل الحواف تسلسلات من التسميات المقابلة لمسارات في شجرة LCL بعمق $k+1$ .
- خاصية اللامبالاة (Indifferent Property): خاصية حاسمة مقتبسة من أعمال التصنيف الثنائي (Bousquet et al., 2023). تكون الشجرة "لامبالية" إذا كان لجميع أحفاد العقدة $u$ (حيث تظهر $u$ قبل $v$ في ترتيب البحث بالعرض BFS) اتفاق على تسمية $v$ . تسمح هذه الخاصية للخصم باستخدام استراتيجية السير العشوائي (Random walk) لفرض الأخطاء حتى عندما يعرف المتعلم تسلسل الحالات.
النهج القائم على نظرية الألعاب (ألعاب جال-ستيوارت - Gale-Stewart Games):
صمم المؤلفون لعبة جال-ستيوارت مبتكرة لتوصيف القابلية للتعلم. بخلاف الألعاب السابقة حيث يقترح الخصم تسلسلاً من الحالات، يقترح الخصم هنا "شجرة مقيدة بالمستوى" (تسلسل من الحالات ومجموعة من تسلسلات التسميات الممكنة). يحاول المتعلم (اللاعب B) اختيار مسار متسق مع فئة المفاهيم.
- المساهمة التقنية الرئيسية هي تصميم هذه اللعبة لالتقاط خاصية اللامبالاة. يوضح المؤلفون أن التوسعات القياسية لأشجار التصنيف الثنائي (مثل أشجار DSL أو LCL) تفشل في توصيف القابلية للتعلم في إعدادات التسميات غير المحدودة متعددة الفئات لأن خاصية "اللامبالاة" لا تتحقق تلقائياً للأشجار اللانهائية في هذا السياق.
- يستخدمون مبرهنة الحتمية البورية (Borel Determinacy Theorem) لإثبات أنه إذا كانت فئة المفاهيم تفتقر إلى شجرة LCLL لامبالية لانهائية، فإن المتعلم (اللاعب B) لديه استراتيجية فوز.
تصميم الخوارزمية:
- الحالة الواقعية (Realizable Setting): تقترح الخوارزميات تتبع تقدم لعبة جال-ستيوارت. إذا تقدمت اللعبة (مما يشير إلى وجود تسلسل فرعي مشتت/Shattered)، تقوم الخوارزمية بتحديث حالتها. إذا توقفت اللعبة، تنتقل الخوارزمية إلى استراتيجية الأغلبية الموزونة (باستخدام دالة وزن بناءً على التسلسلات المشتتة) لتعلم فئة المفهوم الجزئية المتبقية.
- الحالة غير الواقعية (Agnostic Setting): يوسع المؤلفون الخوارزمية الواقعية باستخدام إطار عمل "التعلم مع الخبراء". يقومون ببناء مجموعة معدودة من الخبراء بناءً على سلوك الخوارزمية الواقعية على التسلسلات المتخيلة وفهارس الأخطاء، باستخدام خوارزمية Squint (Koolen & van Erven, 2015) مع أوزان أولية غير موحدة لتقليل الندم.

النتائج الرئيسية

الثلاثية (Trichotomy) للحالة الواقعية:
يحدد البحث ثلاثية لمعدلات الخطأ المثلى للتعلم عبر الإنترنت الشامل عبر الإنترنت (Transductive) متعدد الفئات وغير المحدود:
- أخطاء ثابتة ( $O(1)$ ): يمكن تحقيقها إذا وفقط إذا كانت $\mathcal{H}$ لا تمتلك شجرة ليتلستون لامبالية لانهائية.
- أخطاء لوغاريتمية ( $\Theta(\log T)$ ): يمكن تحقيقها إذا وفقط إذا كانت $\mathcal{H}$ تمتلك شجرة ليتلستون لامبالية لانهائية ولكن لا تمتلك شجرة LCLL لامبالية لانهائية.
- أخطاء خطية ( $\Omega(T)$ ): إذا كانت $\mathcal{H}$ تمتلك شجرة LCLL لامبالية لانهائية، فلا يمكن لأي خوارزمية ضمان أخطاء دون خطية.
الحالة غير الواقعية (Agnostic Setting):
- تكون فئة المفاهيم $\mathcal{H}$ قابلة للتعلم عبر الإنترنت (Transductive) شامل عبر الإنترنت (Universal) غير واقعي إذا وفقط إذا كانت لا تمتلك شجرة LCLL لامبالية لانهائية.
- بالنسبة لهذه الفئات، يقدم المؤلفون خوارزمية تحقق حداً للندم قدره $\tilde{O}(\sqrt{T})$ (مع إخفاء العوامل اللوغاريتمية المتعددة).
- تم إثبات حد أدنى يوضح أنه لأي فئة تحتوي على مفهومين متميزين على الأقل، لا يمكن أن يكون الندم $o(\sqrt{T})$ .
توسيع العملية العشوائية (Stochastic Process):
تم توسيع النتائج إلى الإعداد الذي يعرف فيه المتعلم فقط العملية العشوائية التي تولد تسلسل الحالات (بدلاً من التسلسل نفسه). وقد تبين أن شرط "جميع العمليات التي تسمح بالتعلم عبر الإنترنت الشامل" يكافئ غياب شجرة LCLL لامبالية لانهائية.

الأهمية والادعاءات
يدعي البحث تقديم مساهمات هامة لنظرية التعلم عبر الإنترنت:

حل حالة تعدد الفئات غير المحدودة: يوفر أول توصيف كامل للتعلم عبر الإنترنت (Transductive) الشامل متعدد الفئات مع فضاءات تسميات لانهائية تعداداً، مما يحل الفجوة التي تركتها الدراسات السابقة التي ركزت على التصنيف الثنائي أو التسميات المحدودة.
توصيف توافقي جديد: تقديم شجرة (Level-Constrained-Littlestone-Littlestone - LCLL) وخاصية اللامبالاة كالتوصيف الصحيح لهذا الإعداد. يشير المؤلفون صراحةً إلى أن المرشحات السابقة (أشجار DSL، أو أشجار LCL، أو أشجار ليتلستون القياسية) غير كافية، كما هو موضح في الأمثلة المضادة حيث تمتلك فئة ما شجرة LCLL لانهائية وتظل قابلة للتعلم، أو تمتلك شجرة ليتلستون لانهائية ولكنها تفتقر إلى خاصية اللامبالاة المطلوبة للحد الأدنى.
تصميم لعبة مبتكر: يسلط البحث الضوء على تصميم لعبة جال-ستيوارت محددة حيث يقترح الخصم تسلسلات التسميات لفترات من الحالات، بدلاً من مجرد الحالات. يُقدم هذا التصميم كمساهمة مفاهيمية ضرورية لالتقاط خاصية اللامبالاة في الإعدادات غير المحدودة، حيث تفشل هياكل الألعاب القياسية.
التعلم الشامل المتفائل (Optimistic Universal Learning): يربط العمل بين القابلية للتعلم عبر الإنترنت (Transductive) وبين المسألة الأوسع لـ "التعلم عبر الإنترنت الشامل المتفائل" (التعلم كلما كان التعلم ممكناً). ويوضح أن معرفة تسلسل الحالات (Transductive) أو العملية العشوائية (Optimistic) يؤديان إلى نفس شروط القابلية للتعلم المحددة بواسطة هيكل شجرة LCLL.

يظل المؤلفون متواضعين فيما يتعلق بالحالة غير الواقعية (Agnostic)، حيث يقرون بوجود فجوة لوغاريتمية متعددة بين الحد الأعلى ( $\tilde{O}(\sqrt{T})$ ) والحد الأدنى ( $\Omega(\sqrt{T})$ )، ويتركون تضييق هذه الفجوة كمسألة مفتوحة. كما يحددون توصيف التعلم عبر الإنترنت الشامل للعمليات ذات التسميات غير المحدودة كمسألة مفتوحة أيضاً.