Two Dimensions Govern Agnostic Multiclass Transductive Learning

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

بالنسبة للمشكلات البسيطة التي تحتوي فقط على إجابتين محتملتين، مثل "نعم" أو "لا"، عرف الباحثون منذ فترة طويلة أن هاتين الطريقتين في التعلم متماثلتان جوهرياً من حيث كمية البيانات المطلوبة للنجاح. ومع ذلك، عندما يمكن أن تكون الإجابات واحدة من احتمالات عديدة — مثل تحديد آلاف الأنواع المختلفة من الطيور أو تشخيص مئات الأمراض — تتغير القواعد. في هذه الحالات المعقدة، "متعددة الفئات" (multiclass)، تعتمد صعوبة التعلم على مقياسين رياضيين مختلفين للتعقيد. أحد المقاييس، والذي يُطلق عليه غالسب "بُعد دي إس" (DS dimension)، يتعلق بمدى قدرة المتعلم على التعامل مع المواقف التي يوجد فيها إجابة مثالية. والمقياس الآخر، وهو "بُعد ناتارجان" (Natarajan dimension)، يتعلق بمقدار عدم اليقين المتبقي عندما لا تتوفر إجابة مثالية. لسنوات، كان سؤالًا مفتوحًا ما إذا كانت قواعد "التعلم الاستدلالي" الصارمة ستجبر المتعلم على الحاجة إلى المزيد من البيانات مقارنة بقواعد "التعلم بضمان التوزيع المعتدل" (PAC)، خاصة عندما يكون عدد الإجابات المحتملة ضخماً أو حتى لانهائياً.

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

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

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

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

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

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

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

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