نظرية ما يمكن تعلُّمه

قبل ورقة فاليانت، لو سألت «هل تستطيع الآلة تعلُّم المسألة الفلانية؟» لما وجدت إجابة دقيقة. ببساطة، لم يكن هناك تعريف متّفق عليه لمعنى «التعلُّم» من منظور حوسبي.

التشبيه هنا مفيد: قبل آلات تورينغ لم تكن هناك طريقة رياضية لنقول «هذه المسألة قابلة للحساب» أو «مستحيلة الحساب». نموذج تورينغ أعطانا تلك اللغة. فاليانت قدّم الشيء نفسه لمسائل التعلُّم.

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

يقوم نموذج PAC على أربعة مكوّنات أساسية:

فضاء المدخلات — مجموعة كل المدخلات الممكنة. في صياغة فاليانت الأصلية، هي متجهات بولية $x \in \{0, 1\}^n$. تخيّل أن كل خانة تمثّل سمة: «له فرو»، «له أجنحة»، «يستطيع السباحة».

فئة المفاهيم — عائلة $\mathcal{C}$ من الدوال البولية، كل واحدة منها تأخذ مدخلاً وتُعطي قيمة 1. إحدى هذه الدوال $c \in \mathcal{C}$ هي المفهوم الهدف المجهول الذي نريد تعلّمه. مثلاً، قد تكون $\mathcal{C}$ عبارة عن «كل العطوف المنطقية على $n$ متغيّر».

التوزيع — توزيع احتمالي ثابت لكنه مجهول $\mathcal{D}$ على فضاء المدخلات. الأمثلة تُسحب منه بشكل مستقل ومتماثل التوزيع، وخطأ المتعلم يُقاس وفقه أيضاً. النقطة الجوهرية أن الإطار حُرّ التوزيع: على المتعلم أن ينجح مهما كان التوزيع.

الفرضية — الدالة $h$ التي يُخرجها المتعلم. والمطلوب أن يكون $\Pr_{x \sim \mathcal{D}}[h(x) \neq c(x)] \leq \varepsilon$.

الآن وقد اتّضحت المكوّنات، لنرَ ما يشترطه نموذج PAC بدقة. المتعلم يجب أن ينجح أياً كان المفهوم الهدف من $\mathcal{C}$، وأياً كان التوزيع الذي يولّد الأمثلة. يتلقّى أمثلة مُصنَّفة $(x, c(x))$ ويُخرج فرضية $h$ تحقّق الشرط التالي:

باحتمال $1 - \delta$ على الأقل — بالنسبة للسحب العشوائي للأمثلة — يكون خطأ الفرضية محدوداً بـ$\Pr_{x \sim \mathcal{D}}[h(x) \neq c(x)] \leq \varepsilon$.

والشرط الإضافي: يجب أن يتمّ ذلك بعدد أمثلة وزمن حساب كلاهما متعدد الحدود في $1/\varepsilon$ و$1/\delta$ وحجم المدخل $n$. حين تتوفر خوارزمية تحقّق ذلك، نقول إن $\mathcal{C}$ قابلة للتعلم وفق PAC.

السؤال الأول الذي يتبادر إلى الذهن: كم مثالاً $m$ يكفي؟ أثبت فاليانت أنه لفئة مفاهيم منتهية $\mathcal{C}$، الجواب هو:

إذا سحبت $m \geq \frac{1}{\varepsilon}\bigl(\ln|\mathcal{C}| + \ln\frac{1}{\delta}\bigr)$ مثالاً على الأقل، فأيّ فرضية تتّسق مع كل الأمثلة ستكون صحيحة وفق PAC.

الفكرة وراء ذلك هي الاستبعاد التدريجي. كل مثال عشوائي يحمل فرصة لا تقل عن $ε$ لكشف أي فرضية «سيئة» — أي فرضية خطؤها أكبر من $ε$. بعد $m$ مثال، احتمال أن تنجو فرضية سيئة بعينها من الكشف ينخفض إلى $(1-ε)^m \leq e^{-εm}$ على الأكثر. وبتطبيق حد الاتحاد على كل مفاهيم $|\mathcal{C}|$ الممكنة، يصبح احتمال بقاء أيّ فرضية سيئة أقل من $|\mathcal{C}| \cdot e^{-εm}$. نجعل هذا ≤ $δ$ ونحلّ بالنسبة لـ$m$ فنحصل على الحدّ المذكور.

أعمق ما في برهان فاليانت هو أن الأمثلة العشوائية أقوى مما نتوقّع. لا تحتاج إلى أمثلة مختارة بعناية أو استعلامات مُصمَّمة بدهاء — عيّنات عشوائية عادية من أي توزيع يقدّمه الواقع تكفي.

تخيّل أن لديك غرفة فيها مئة مشتبه به، وكل مثال عشوائي هو شاهد يدخل الغرفة ويقول: «هذا ليس الجاني». كل مشتبه به تتناقض تنبؤاته مع شهادة الشاهد يخرج من الغرفة فوراً. بعد عدد كافٍ من الشهود، لا يبقى إلا من يتّسق سلوكه بدرجة عالية مع الجاني الحقيقي. هؤلاء الباقون قد لا يطابقون المفهوم الهدف تماماً، لكنهم صحيحون تقريباً — يختلفون عنه في نسبة $\varepsilon$ فقط من الحالات.

فاليانت لم يكتفِ بوضع الإطار النظري، بل استخدمه ليُثبت نتائج عملية. أظهر أن عدة فئات من الدوال البولية يمكن تعلّمها بكفاءة وفق PAC:

صيغ k-CNF — الصيغة العطفية السويّة التي تحتوي كل عبارة فيها على $k$ حرف منطقي كحدٍّ أقصى. الخوارزمية هنا أنيقة في بساطتها: ابدأ بأعمّ فرضية ممكنة، ثم احذف كل عبارة تتناقض مع مثال إيجابي. ما يبقى هو فرضية صالحة.

صيغ k-DNF — الصيغة الفصلية السويّة التي يحتوي كل حدٍّ فيها على $k$ حرف منطقي كحدٍّ أقصى. قابلة للتعلم وفق PAC أيضاً، لكن بخوارزمية مختلفة.

تعبيرات $\mu$ — صيغ بولية لا يظهر فيها أي متغير أكثر من مرة واحدة. تعقيدها المحدود يجعل تعلّمها ممكناً بكفاءة.

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

من أبرز ما يميّز نموذج PAC إصراره على الكفاءة الحوسبية. لا يكفي أن نُثبت إمكانية التعلم بعدد منتهٍ من الأمثلة — بل يجب أن تعمل الخوارزمية في زمن متعدد الحدود أيضاً.

هنا يظهر انقسام مثير للاهتمام: بعض فئات المفاهيم قابلة للتعلم نظرياً من حيث عدد الأمثلة — أي أن حدّ تعقيد العيّنات منتهٍ — لكنها مستعصية حوسبياً. معالجة تلك الأمثلة تتطلب زمناً ينمو أُسِّياً مع $n$.

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

من أجرأ القرارات التصميمية في نموذج PAC شرط أن يكون الإطار حُرّ التوزيع. يعني هذا أن على المتعلم أن ينجح مهما كان التوزيع $\mathcal{D}$ — لا يحق له افتراض أن البيانات منتظمة، أو غاوسية، أو تتبع نمطاً بعينه.

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

فكّر فيه كضمان الحالة الأسوأ: كما تسأل نظرية التعقيد «هل تعمل هذه الخوارزمية على كل مدخل ممكن؟»، يسأل نموذج PAC «هل ينجح هذا المتعلم على كل توزيع ممكن؟»

حدّ فاليانت لعدد الأمثلة يعتمد على $\ln|\mathcal{C}|$، أي لوغاريتم حجم فئة المفاهيم. هذا يعمل جيداً حين تكون الفئة منتهية، لكن ماذا عن فئات لانهائية مثل «كل المصنّفات الخطية في $\mathbb{R}^n$»؟

الإجابة جاءت من ربط نموذج PAC بـبُعد VC — وهو مقياس يعكس «التعقيد الفعلي» لفئة الفرضيات بغض النظر عن حجمها. في عام 1989، أثبت بلومر وإيرنفوخت وهاوسلر ووارموث النظرية الأساسية: فئة المفاهيم قابلة للتعلم وفق PAC إذا وفقط إذا كان بُعد VC الخاص بها منتهياً.

هذه النتيجة وحّدت الإطار الحوسبي الذي وضعه فاليانت مع نظرية التعلم الإحصائي في توصيف واحد لقابلية التعلم، ولا يزال هذا التوصيف محورياً في المجال حتى اليوم.

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