فهم التعلّم PAC
يبدأ الإطار بالاعتراف بما لا يمكن الوعد به. فالعيّنة المنتهية قد تُضلّل دائماً، ومن ثمّ فطلب الفرضية الصحيحة تماماً بيقين يمنع التعلّم منعاً. ويطلب PAC بدل ذلك فرضيةً خطؤها الحقيقي لا يتجاوز إبسيلون، ويقبل احتمال إخفاق قدره دلتا - فقد لا تكون العيّنة ممثّلة، ولا طريقة تمنع ذلك. وتكون الفئة قابلة للتعلّم متى أمكن كتابة عدد العيّنات اللازم لبلوغ الهدفين بدلالة إبسيلون ودلتا وحدهما.
وللفئة المنتهية تكون الحجّة عدّاً. فمتباينة هوفدينغ تحدّ احتمال أن تُظهر فرضية واحدة ثابتة خطأ تدريب بعيداً عن خطئها الحقيقي؛ وحدّ الاتّحاد يضرب ذلك في عدد الفرضيات ليغطّيها جميعاً دفعةً واحدة. وبحلّ المعادلة لحجم العيّنة نحصل على n من رتبة (log|H| + log(1/دلتا)) على إبسيلون تربيع. واللوغاريتم هو القصّة كلّها: فئة من اثنتين تحتاج 220 عيّنة عند إبسيلون 0.1 وثقة 95%، وفئة تتجاوز المليون تحتاج 878.
والانتظام ليس تفصيلاً تقنياً. فالمتعلّم يفحص العيّنة ثمّ يختار، فالفرضية التي يردّها دالّةٌ في البيانات نفسها وليست مثبَّتة سلفاً. وحدٌّ لا يصحّ إلّا لفرضية محدّدة مسبقاً لن يقول شيئاً عن الفرضية المنتَجة فعلاً. ودفع log|H| يشتري قولاً عن كلّ الأعضاء في آنٍ واحد، وهو يغطّي الفائزة بالضرورة.
وما يقع بدون ذلك قابل للقياس. فعلى بيانات يكون فيها خطأ كلّ فرضية الحقيقي 0.5 بالضبط، تُظهر فرضية واحدة ثابتة خطأ تدريب يبعد 0.0002 عن الحقيقة، بينما تقع أفضل ألف على بعد 0.1149 تحتها. وليست أيٌّ من تلك الألف أفضل من غيرها؛ فالفجوة كلّها كلفة الانتقاء، ولهذا لا يكون درجة التدريب تقديراً للأداء المقبل.
كيفية الحساب
P( err(ĥ) ≤ min_h err(h) + ε ) ≥ 1 − δ, n ≥ (ln|H| + ln(2/δ)) / (2ε²)
حيث
- ε
- التسامح: كم فوق أفضل خطأ ممكن يُقبل أن نكون
- δ
- احتمال الإخفاق: كم مرّة يُسمح لعيّنة غير ممثّلة بأن تُبطل الضمانة
- ĥ
- الفرضية التي تردّها الخوارزمية بعد رؤية العيّنة
- ln|H|
- ثمن البحث؛ وللفئات اللانهائية يحلّ البُعد VC محلّه
مثال على التعلّم PAC
عند إبسيلون 0.1 ودلتا 0.05، تكون العيّنات المطلوبة 220 لفئة من 2، و300 لعشر، و530 لألف، و878 لـ1,048,576. أي إنّ نصف مليون ضعف من الفرضيات يكلّف 658 عيّنة إضافية، لأنّ المطلب ينمو مع عدد خانات حجم الفئة.
وأثر الانتقاء الذي يحمي منه الحدّ، على ضجيج محض يكون فيه خطأ كلّ فرضية الحقيقي 0.5: أفضل واحدة تقع 0.0002 تحت الحقيقة على عيّنتها، وأفضل عشر 0.0549 تحتها، وأفضل مئة 0.0887 تحتها، وأفضل ألف 0.1149 تحتها.
وللفئات اللانهائية تجري الحجّة نفسها بالبُعد VC مكان log|H|، إذ تحدّ لِمّة ساور السلوكيات المتمايزة على n نقطة بكثير حدود - فعند البُعد 2 وn = 20 يكون العدد 211 بدل 1,048,576.
الأسئلة الشائعة
هل حدود PAC نافعة عملياً؟
نادراً بوصفها أرقاماً. فهي أسوأ-حالة على كلّ توزيع وتطلب عادةً بيانات أكثر بكثير ممّا ينجح واقعاً. وقيمتها بنيوية: تقول أيّ مقدار يحكم التعميم، وهذا هو الذي ينتقل.
ما معنى «خالٍ من افتراض التوزيع» هنا؟
يصحّ الحدّ أيّاً كان التوزيع المولّد للبيانات، ولهذا يكون أسوأ-حالة وفضفاضاً. لكنّه يشترط أن يأتي التدريب والاختبار من التوزيع نفسه - وهو افتراض حقيقي، وأوّل ما ينهار عملياً.
هل يقول التعلّم PAC كيف نجد الفرضية؟
ليس بذاته. فتعقيد العيّنة شأن معلوماتي لا حسابي؛ وقد تكون فئةٌ قابلة للتعلّم ببيانات معتدلة بينما يظلّ البحث عن فرضية جيّدة عصيّاً.
الخلاصة
يستحقّ PAC أن يُتعلَّم لهيئته لا لأرقامه. فهو يقول إنّ التعميم يُشترى بتقييد البحث، ويسعّر ذلك القيد لوغاريتماً، ويوضح أنّ درجة التدريب تقرير عن بحثٍ لا تقدير للخطأ المقبل.