یادگیری احتمالا تقریبا صحیح
در نظریه یادگیری محاسباتی، یادگیری احتمالاً تقریباً صحیح (یادگیری PAC) چارچوبی است برای تحلیل ریاضی یادگیری ماشین که در سال ۱۹۸۴ توسط لسلی والینت پیشنهاد شد.[1]
در این چارچوب یادگیرنده نمونه‌هایی را دریافت کرده و باید از کلاس مشخصی از توابع ممکن یک تابع تعمیم (به نام فرضیه) انتخاب نماید. هدف این است که با احتمال بالا ("احتمالاً") تابع انتخاب شده خطای تعمیم پایینی دارد (تقریباً صحیح). یادگیرنده باید قادر به یادگیری مفهوم با هر ضریب تقریب، احتمال موفقیت، یا توزیع نمونه‌ها باشد.
این مدل بعدها به منظور استفاده در محیط‌ها و داده‌های دارای نویز نیز توسعه داده شد (نمونه misclassified).
یک نوآوری مهم چارچوب PAC وارد کردن مفاهیم محاسباتی نظریه پیچیدگی در یادگیری ماشین است. به ویژه، انتظار می‌رود که یادگیرنده توابع بهینه (زمان و فضای مورد نیاز محدود به یک چند جملهای (زمان و فضای چند جملهای) از اندازه نمونه هستند) و یادگیرنده خود را باید یک روند بهینه را پیاده‌سازی نماید.
هم‌ارزی
تحت برخی شرایط این سه شرط هم ارز هستند:
- کلاس مفهوم C، یک PAC یادگرفتنی است.
- بعد VC کلاس C محدود است.
- C یک کلاس Glivenko-Cantelli است.
جستارهای وابسته
- یادگیری ماشین
- داده کاوی
- خطا تحمل (PAC یادگیری)
منابع
- L. Valiant.
جستارهای وابسته
- M. Kearns, U. Vazirani. An Introduction to Computational یادگیری تئوری. MIT Press, 1994. یک کتاب درسی است.
- D. Haussler. بررسی اجمالی از احتمالاً حدود صحیح (PAC) یادگیری چارچوب است. یک مقدمه به این موضوع است.
- L. Valiant. Probably Approximately Correct اساسی، کتاب، ۲۰۱۳. که در آن Valiant استدلال می‌کند که PAC یادگیری توضیح می‌دهد که چگونه موجودات تکامل و یادگیری است.