پرش به محتوا

یادگیری احتمالا تقریبا صحیح

از ویکی‌پدیا، دانشنامهٔ آزاد

در نظریه یادگیری محاسباتی، یادگیری احتمالاً تقریباً صحیح (یادگیری PAC) چارچوبی است برای تحلیل ریاضی یادگیری ماشین که در سال ۱۹۸۴ توسط لسلی والینت پیشنهاد شد.[۱]

در این چارچوب یادگیرنده نمونه‌هایی را دریافت کرده و باید از کلاس مشخصی از توابع ممکن یک تابع تعمیم (به نام فرضیه) انتخاب نماید. هدف این است که با احتمال بالا ("احتمالاً") تابع انتخاب شده خطای تعمیم پایینی دارد (تقریباً صحیح). یادگیرنده باید قادر به یادگیری مفهوم با هر ضریب تقریب، احتمال موفقیت، یا توزیع نمونه‌ها باشد.

این مدل بعدها به منظور استفاده در محیط‌ها و داده‌های دارای نویز نیز توسعه داده شد (نمونه misclassified).

یک نوآوری مهم چارچوب PAC وارد کردن مفاهیم محاسباتی نظریه پیچیدگی در یادگیری ماشین است. به ویژه، انتظار می‌رود که یادگیرنده توابع بهینه (زمان و فضای مورد نیاز محدود به یک چند جملهای (زمان و فضای چند جمله‌ای) از اندازه نمونه هستند) و یادگیرنده خود را باید یک روند بهینه را پیاده‌سازی نماید.

هم‌ارزی

[ویرایش]

تحت برخی شرایط این سه شرط هم ارز هستند:

  1. کلاس مفهوم C، یک PAC یادگرفتنی است.
  2. بعد VC کلاس C محدود است.
  3. C یک کلاس Glivenko-Cantelli است.

جستارهای وابسته

[ویرایش]

منابع

[ویرایش]
  1. L. Valiant.

جستارهای وابسته

[ویرایش]