قوّة التعلّم الضعيف

عام 1984 قدّم ليزلي فاليانت إطار التعلّم PAC — وهو اختصار لـ Probably Approximately Correct. الفكرة بسيطة: فئة من المفاهيم تكون قابلة للتعلّم القوي إذا وُجدت خوارزمية تستطيع، بثقة عالية، إيجاد فرضية خطؤها صغير بالقدر الذي تريده. وتكون قابلة للتعلّم الضعيف إذا كان المطلوب أهون من ذلك بكثير: يكفي أن تتغلّب على التخمين العشوائي بهامش ضئيل — أي أن يكون خطؤها أقل من $1/2 - \gamma$ لقيمة $\gamma > 0$ صغيرة جداً.

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

الاختراق الذي حققه شابير كان إثبات أن الإجابة نعم، بشرط واحد: أن تُغيّر التوزيع بين كل تشغيلة وأخرى — أي أن تُرشِّح الأمثلة بحيث تُجبر المتعلّم الضعيف على التركيز في كل مرة على الأخطاء التي وقعت فيها الفرضيات السابقة.

الفكرة الجوهرية أنيقة بقدر ما هي بسيطة. لنبدأ بـمتعلّم ضعيف $A$ لا يتجاوز خطؤه $\alpha < 1/2$ على أي توزيع. ما يفعله شابير هو بناء خوارزمية جديدة $A'$ تستدعي $A$ ثلاث مرات، كل مرة على توزيع مختلف، ثم تدمج النتائج:

الجولة الأولى — التقط ما تستطيع. شغِّل $A$ على التوزيع الأصلي $D_1 = D$ لتحصل على الفرضية $h_1$. هذه الفرضية تكتشف الأنماط التي يقدر عليها المتعلّم، لكنها ما زالت تُخطئ في نسبة $\alpha$ من البيانات.

الجولة الثانية — ألغِ ما تعلّمتَه. أنشئ توزيعاً جديداً $D_2$ يكون فيه احتمال ظهور مثال أصابت فيه $h_1$ مساوياً تماماً لاحتمال ظهور مثال أخطأت فيه — توزيع مناصفة 50/50. على هذا التوزيع تفقد $h_1$ أي ميزة وتصبح كأنها تُخمّن عشوائياً. شغِّل $A$ على $D_2$ لتحصل على $h_2$، وهي فرضية مُضطرة لاكتشاف أنماط جديدة في المنطقة الصعبة.

الجولة الثالثة — ركِّز على الخلاف. ابنِ $D_3$ بالاحتفاظ فقط بالأمثلة التي اختلفت فيها $h_1$ عن $h_2$. هذه هي النقاط غير المحسومة — الحالات التي نحتاج فيها لمن يكسر التعادل. شغِّل $A$ على $D_3$ لتحصل على $h_3$.

الفرضية النهائية: عند تصنيف مثال $v$، إذا اتفقت $h_1$ و$h_2$ — أي $h_1(v) = h_2(v)$ — فخُذ إجابتهما. وإذا اختلفتا، اعتمد على $h_3(v)$ بوصفها الحَكَم. بعبارة أخرى: النتيجة هي تصويت الأغلبية بين $h_1$ و$h_2$ و$h_3$.

النتيجة المركزية تقول إن خطأ الفرضية المركّبة $h$ لا يتجاوز $g(\alpha) = 3\alpha^2 - 2\alpha^3$. لنفهم لماذا هذا مهم، لنأخذ أرقاماً ملموسة: إذا كان خطأ المتعلّم الضعيف $\alpha = 0.4$ — أي دقته 60% فقط — فإن جولة تعزيز واحدة تُنزل الخطأ إلى $g(0.4) = 3(0.16) - 2(0.064) = 0.352$. للوهلة الأولى لا يبدو الفرق مبهراً، لكن القوة الحقيقية تظهر في التكرار.

بما أن $g(\alpha) < \alpha$ لكل $\alpha \in (0, 1/2)$، نستطيع تطبيق البناء تعاودياً: في كل مرة يمرّ الخطأ عبر الدالة $g$ فيتقلّص أكثر. بعد $k$ مستوى من التعاود يصبح الخطأ $g^k(\alpha)$، وهو يتقارب نحو الصفر بسرعة مُضاعَفة أُسّياً — أي أسرع بكثير مما قد نتوقّع.

قبل عمل شابير، الفكرة التي تتبادر للذهن مباشرةً هي: شغِّل المتعلّم الضعيف $T$ مرة بشكل مستقل على التوزيع نفسه، واجمع الفرضيات $h_1, \dots, h_T$، ثم تنبّأ بتصويت الأغلبية. لو كانت أخطاء الفرضيات مستقلة عن بعضها، لعمل هذا الأسلوب ببراعة — حدّ تشيرنوف يضمن تقارباً أُسّياً سريعاً.

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

هنا تأتي بصيرة شابير: غيِّر التوزيع بين الجولات بحيث تُجبَر كل فرضية على تعلّم شيء جديد. التوزيعات المُرشَّحة $D_2$ و$D_3$ تُبطل مزايا الفرضيات السابقة، فتضمن أن كل متعلّم لاحق يلتقط معلومات تُكمّل ما التقطه من سبقه.

بناء الفرضيات الثلاث الذي وصفناه هو خطوة واحدة فقط. للوصول إلى دقة عالية كما نشاء، يُطبّقه شابير بشكل تعاودي عبر إجراء سمّاه Learn.

يعمل هذا الإجراء كالتالي: يأخذ هدفاً لـالخطأ $\varepsilon$ ويبدأ من الأعلى نزولاً. إذا كان الهدف $\varepsilon \geq 1/2 - 1/p(n,s)$ — أي في متناول المتعلّم الضعيف — فإنه يستدعيه مباشرةً. أما إذا كان الهدف أصعب، فيحسب $\alpha = g^{-1}(\varepsilon)$ ويستدعي نفسه ثلاث مرات بهدف خطأ $\alpha$ ليحصل على ثلاث فرضيات فرعية، ثم يدمجها بـتصويت الأغلبية فيحصل على فرضية خطؤها لا يتجاوز $g(\alpha) = \varepsilon$.

العمق الكلي لهذا التعاود هو $O(\log p(n,s) + \log\log(1/\varepsilon))$ — لوغاريتمي مُزدوج فحسب بالنسبة للدقة المطلوبة. معنى ذلك عملياً أن خفض الخطأ إلى $10^{-100}$ لا يحتاج إلا عدداً متواضعاً من طبقات التعاود.

لفهم لماذا يتقلّص الخطأ، نُعرِّف أربعة احتمالات على التوزيع $D$ للمثال $v$:

• $w = \Pr[h_2(v) \neq h_1(v) = c(v)]$ — $h_1$ أصابت و$h_2$ أخطأت
• $x = \Pr[h_1(v) = h_2(v) = c(v)]$ — كلتاهما أصابتا
• $y = \Pr[h_1(v) \neq h_2(v) = c(v)]$ — $h_1$ أخطأت و$h_2$ أصابت
• $z = \Pr[h_1(v) = h_2(v) \neq c(v)]$ — كلتاهما أخطأتا

الفرضية النهائية $h$ لا تُخطئ إلا في حالتين: أن يُخطئ كلٌّ من $h_1$ و$h_2$ معاً (الحالة $z$)، أو أن يختلفا ويُخطئ $h_3$ في الحكم بينهما. من هنا يكون الخطأ محدوداً بـ$z + \alpha_3(w + y)$. وباستخدام القيود التي يفرضها بناء $D_2$ وكون كل $\alpha_i \leq \alpha$، نصل إلى أن الخطأ الكلي لا يتجاوز $3\alpha^2 - 2\alpha^3$.

إلى جانب المبرهنة الرئيسية، استخلص شابير نتائج مفاجئة حول تعقيد أي فئة مفاهيم قابلة للتعلّم:

• ضغط الفرضية. أي متعلّم قوي يمكن تحويله إلى متعلّم تكون فرضيته بحجم متعدد حدود في $\log(1/\varepsilon)$ بدلاً من $1/\varepsilon$. عملياً، عيّنة بحجم $m$ يمكن تلخيصها في قاعدة حجمها لا يتجاوز متعدد حدود لوغاريتمياً في $m$.

• كفاءة الذاكرة. توجد خوارزمية تعلّم لأي فئة قابلة للتعلّم لا تحتاج من الذاكرة إلا مقداراً متعدد حدود لوغاريتمياً في $1/\varepsilon$ — أقل بكثير من تخزين العيّنة كاملة.

• التعلّم الفوري. لأي فئة قابلة للتعلّم، توجد خوارزمية فورية لا يزيد عدد أخطائها المتوقع على أول $m$ محاولة إلا كمتعدد حدود في $\log m$.

• نتائج الاستحالة. أي فئة مفاهيم لا يمكن حسابها بدوائر متعددة الحدود في الحجم تكون غير قابلة للتعلّم — وهذه أول نتيجة استحالة مستقلة عن طريقة التمثيل ولا تعتمد على فرضيات تشفيرية.

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

عام 1995 طوّر يوآف فرويند خوارزمية تعزيز أكفأ. ثم في 1997 قدّم فرويند وشابير معاً AdaBoost، وهي التي نقلت التعزيز من عالم النظرية إلى التطبيق الفعلي. بدلاً من ثلاث جولات لكل مستوى تعاودي، يعمل AdaBoost بحلقة تكرارية واحدة من $T$ جولة متتابعة: في كل جولة يُعاد ترجيح مجموعة التدريب بأكملها، فالأمثلة التي يُخطئ فيها التجميع الحالي تحصل على أوزان أعلى، مما يُجبر المتعلّم الضعيف التالي على التركيز عليها. التنبؤ النهائي هو تصويت موزون لجميع الفرضيات الـ$T$، حيث تحصل الفرضيات الأدق على وزن تصويتي أكبر.

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