التعلم PAC مقابل.التعلم على التوزيع الموحد

Question

فئة الوظيفة $\mathcal{F}$ يمكن تعلم PAC في حالة وجود خوارزمية $أ$ مثل هذا ل أي توزيع $د$, ، أي وظيفة غير معروفة $و$ وأي $\ إبسيلون، \ دلتا $ ويعتقد أن هناك $م$ بحيث على مدخلات $م$ عينات معرف $(x, f(x))$ أين $x\sim D$, $أ$ العائدات، مع احتمال أكبر من $1-\دلتا$, ، وهي وظيفة $\ إبسيلون$-قريب من $و$ (بالنسبة إلى $د$).الفصل $\mathcal{F}$ يكون PAC قابلاً للتعلم بكفاءة إذا كان PAC قابلاً للتعلم، و $أ$ يعمل في الوقت المناسب $ ext{بولي}(1/\epsilon, 1/\delta, n)$ (أين $|x| = n$) ووصف $و$.

هل هناك حالة حيث فئة $\mathcal{F}$ هل PAC ليس قابلاً للتعلم بكفاءة، ومع ذلك يمكن تعلمه بكفاءة على التوزيع الموحد؟

Answer 1

هل هناك حالة حيث فئة $\mathcal{F}$ هل PAC ليس قابلاً للتعلم بكفاءة، ومع ذلك يمكن تعلمه بكفاءة على التوزيع الموحد؟

وقد سئل هذا على TCS.SE.يبدو أن الإجابة المختصرة هي نعم - يعطي آرون روث مثالاً للعرض-$ك$ أدوات العطف ل $k \gg \log n$.وفي التعليقات، نقل عن أفريم بلوم الإجابة على هذا السؤال $2$-مصطلح DNF.

لا أفهم الأمثلة الموجودة هناك تمامًا - يجب أن يستغرق الأمر المزيد من العمل لاستخلاص النتيجة حقًا (سأقوم بتحديث هذه الإجابة إذا وجدت دليلاً قائمًا بذاته).لكن المشكلة العامة هنا في التوزيع الموحد هي أنه إذا كان الهدف يعمل $و$ هو "متناثر"، مما يعني أنه يُصنف على الأكثر كـ $\دلتا$ جزء من توزيع المدخلات مع $1$, ، فمن السهل التعلم بمجرد التخمين $0$.

---

إلى جانب تعلم PAC الفعال (متعدد الحدود)، هناك أمثلة أخرى حيث يبدو أن التوزيع الموحد يساعد.على سبيل المثال، المشكلة الصعبة الكلاسيكية لتعلم PAC هي DNF، وهي مشكلة يُعتقد أنها غير قابلة للتعلم من PAC، وهي صعبة جدًا.من ناحية أخرى، فإن DNF على التوزيع الموحد يكاد يكون PAC قابلاً للتعلم:لدينا qausiخوارزمية زمنية متعددة الحدود لذلك.يرى هذه الملاحظات و هذه الملاحظات.

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

يصر التعلم العام لـ PAC على أن تعمل خوارزمية واحدة في وقت واحد لجميع التوزيعات.في الواقع، يجد مجتمع التعلم الآلي المهتم بتطبيقات العالم الحقيقي أن الإعداد الموحد مشكوك فيه:ولكن في إطار أكثر عمومية، لا يستطيع أحد إثبات أي شيء حقًا.