التعلم الصحيح تقريبًا

في نظرية التعلم الحسابي ، يُعد التعلم الصحيح تقريبًا ( PAC ) إطارًا للتحليل الرياضي للتعلم الآلي . وقد اقترحه ليزلي فاليانت في عام 1984. ^{[ 1 ]}

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

تم توسيع النموذج لاحقًا لمعالجة الضوضاء (العينات المصنفة بشكل خاطئ).

من أهم ابتكارات إطار عمل PAC إدخال مفاهيم نظرية التعقيد الحسابي في مجال تعلم الآلة. فعلى وجه الخصوص، يُتوقع من المتعلم إيجاد دوال فعالة (متطلبات الوقت والمساحة محدودة بدالة متعددة الحدود لحجم المثال)، كما يجب على المتعلم نفسه تنفيذ إجراء فعال (يتطلب عدد أمثلة محدود بدالة متعددة الحدود لحجم المفهوم، مع تعديلها بحدود التقريب والاحتمالية ) .

من أجل تقديم تعريف لشيء قابل للتعلم بواسطة PAC، علينا أولاً تقديم بعض المصطلحات. ^{[ 2 ]}

سنستخدم مثالين للتعريفات التالية. المثال الأول هو مشكلة التعرف على الأحرف عند إعطاء مصفوفة من${\displaystyle n}$بتات تُشفّر صورة ثنائية القيمة. المثال الآخر هو مشكلة إيجاد فاصل زمني يُصنّف النقاط داخله بشكل صحيح على أنها موجبة، والنقاط خارجه على أنها سالبة.

يترك${\displaystyle X}$يمكن أن تكون مجموعة تسمى فضاء الحالات أو ترميز جميع العينات. في مشكلة التعرف على الأحرف، يكون فضاء الحالات هو${\displaystyle X=\{0,1\}^{n}}$في مسألة الفترات، فضاء الحالات،${\displaystyle X}$، هي مجموعة جميع الفترات المحدودة في${\displaystyle \mathbb {R} }$، أين${\displaystyle \mathbb {R} }$يرمز إلى مجموعة جميع الأعداد الحقيقية .

المفهوم هو مجموعة فرعية${\displaystyle c\subset X}$أحد المفاهيم هو مجموعة جميع أنماط البتات في${\displaystyle X=\{0,1\}^{n}}$التي تشفر صورة الحرف "P". ومن المفاهيم المذكورة في المثال الثاني مجموعة الفترات المفتوحة.${\displaystyle \{(a,b)\mid 0\leq a\leq \pi /2,\pi \leq b\leq {\sqrt {13}}\}}$، كل منها يحتوي على النقاط الإيجابية فقط. فئة مفاهيمية${\displaystyle C}$هي مجموعة من المفاهيم على مدى${\displaystyle X}$. يمكن أن تكون هذه مجموعة جميع المجموعات الفرعية لمصفوفة البتات التي تم هيكلتها 4-متصلة (عرض الخط هو 1).

يترك${\displaystyle \operatorname {EX} (c,D)}$أن يكون إجراءً يقدم مثالاً،${\displaystyle x}$باستخدام توزيع احتمالي${\displaystyle D}$ويعطي التسمية الصحيحة${\displaystyle c(x)}$، أي 1 إذا${\displaystyle x\in c}$وصفر فيما عدا ذلك.

الآن، بالنظر إلى${\displaystyle 0<\epsilon ,\delta <1}$، افترض وجود خوارزمية${\displaystyle A}$ومتعددة الحدود${\displaystyle p}$في${\displaystyle 1/\epsilon ,1/\delta }$(وغيرها من المعايير ذات الصلة بالفئة)${\displaystyle C}$) بحيث، بالنظر إلى عينة بحجم${\displaystyle p}$تم رسمها وفقًا لـ${\displaystyle \operatorname {EX} (c,D)}$إذن، باحتمالية لا تقل عن${\displaystyle 1-\delta }$،${\displaystyle A}$يُخرج فرضية${\displaystyle h\in C}$التي يكون متوسط ​​خطأها أقل من أو يساوي${\displaystyle \epsilon }$على${\displaystyle X}$بنفس التوزيع${\displaystyle D}$علاوة على ذلك، إذا كان البيان أعلاه ينطبق على الخوارزمية${\displaystyle A}$ينطبق هذا على كل مفهوم${\displaystyle c\in C}$ولكل توزيع${\displaystyle D}$زيادة${\displaystyle X}$ولجميع${\displaystyle 0<\epsilon ,\delta <1}$ ثم${\displaystyle C}$يمكن تعلم PAC (بكفاءة) (أو يمكن تعلم PAC بدون توزيع ). يمكننا أيضًا القول أن${\displaystyle A}$هي خوارزمية تعلم PAC لـ${\displaystyle C}$.

في ظل بعض شروط الانتظام، تكون هذه الشروط متكافئة: ^{[ 3 ]}

1. يمكن تعلم فئة المفاهيم C باستخدام PAC.
2. بُعد VC للمركبة C محدود.
3. C هي فئة Glivenko-Cantelli موحدة .
4. C قابل للانضغاط بالمعنى الذي وضعه ليتلستون ووارموث

• استخراج البيانات
• التسامح مع الأخطاء (التعلم الآلي)
• التعلم وفقًا لمنهج أوكام
• تعقيد العينة

• م. كيرنز، يو. فازيراني. مقدمة في نظرية التعلم الحسابي . مطبعة معهد ماساتشوستس للتكنولوجيا، 1994. كتاب مدرسي.
• م. مهري، أ. رستمي زاده، وأ. تالوالكار. أسس التعلم الآلي . مطبعة معهد ماساتشوستس للتكنولوجيا، 2018. يتضمن الفصل الثاني شرحًا مفصلًا لمفهوم قابلية التعلم PAC. متاح للقراءة مجانًا من الناشر.
• د. هاوسلر. نظرة عامة على إطار التعلم الصحيح تقريبًا (PAC) . مقدمة للموضوع.
• إل. فاليانت. على الأرجح صحيح تقريبًا. الكتب الأساسية، 2013. حيث يجادل فاليانت بأن التعلم القائم على التقريب الصحيح يصف كيف تتطور الكائنات الحية وتتعلم.
• ليتلستون، ن.؛ وارموث، م.ك. (10 يونيو 1986). "العلاقة بين ضغط البيانات وسهولة التعلم" (ملف PDF) . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 9 أغسطس 2017.
• موران، شاي؛ يهودايوف، أمير (2015). "مخططات ضغط العينات لفئات VC". arXiv : 1503.06960 [ cs.LG ].

• شرح تفاعلي لتعلم برنامج PAC