نظریه یادگیری محاسباتی
مدل یادگیری یک فرضیه تقریباً درست (PAC)

در این بخش، حالت خاصی را برای مسائل یادگیری در نظر می‌گیریم، این حال مدل یادگیری تقریباً درست (PAC) نامیده می‌شود. برای سادگی کار، یادگیری مفاهیم منطقی از داده‌های آموزشی بدون خطا را در نظر بگیرید. با این وجود بسیاری از نتایج حاصل را می‌توان به حالت کلی یادگیری توابع حقیقی مقادیر تابع هدف تعمیم داد. همچنین بسیاری دیگر از نتایج را می‌توان به یادگیری از انواع خاصی از داده‌های خطادار تعمیم داد.
فرض کنید  X مجموعه‌ای از تمامی نمونه‌های ممکن بر روی تابع هدف مفروض باشد. برای مثال، مجموعه تمامی افراد با ویژگی‌های سن (پیر و جوان) و قد (بلند و کوتاه) باشد.  C مجموعه مفاهیم هدفی است که ممکن است، یادگیر برای یادگیری آن‌ها برای یادگیری آنها، به کار برده باشد. هر مفهوم هدف  c در مجموعه  C متناسب با زیر مجموعه‌ای از  X است. به‌طور مشابه  c متناسب با تابع  c:X\rightarrow \{0,1\} می‌باشد. برای مثال، یک تابع هدف  c در  C، ممکن است مفهوم افراد اسکی باز باشد. اگر  x نمونه مثبتی از  c باشد، داریم:
c(x)=0
در این حالت فرض می‌کنیم که نمونه‌ها به صورت تصادفی و با توزیع احتمال  D انتخاب می‌شوند. برای مثال،  D ممکن است، توزیع احتمال نمونه افرادی باشد که از یک باشگاه ورزشی بیرون می‌آیند (توزیع احتمالی بر روی تمامی افراد). در کل  D ممکن است، هر توزیع احتمالی باشد و درحالت کلی این توزیع برای یادگیر ناشناخته است. تمامی اطلاعات موجود در  D این است که توزیع احتمالی ثابت است، بدین معنا که این توزیع احتمال با زمان تغییر نمی‌کند. نمونه‌های آموزشی با این توزیع احتمال انتخاب شده و به همراه مقدار تابع هدفشان ( c(x)) به یادگیر داده می‌شوند.
یادگیر  L مجموعه‌ای از فرضیه‌های ممکن مانند  H را در یادگیری مفهوم هدف در نظر می‌گیرد. برای مثال،  H ممکن است، مجموعه تمامی فرضیه‌های قابل بیان به صورت عطف سن و قد باشد. بعد از مشاهده یک سری از نمونه‌های آموزشی، برای تابع هدف  c، باید فرضیه‌ای مانند  h از  H که تخمین آن از  c است، به عنوان فرضیه‌ تخمینی خروجی دهد. موفقیت  L را کارایی این فرضیه  h بر روی نمونه‌های جدیدی که به صورت تصادفی از  X و باتوزیع  D انتخاب می‌شوند، می‌سنجیم. در چنین حالتی، علاقه ما به کارایی یادگیرهای مختلف  L با فضای فرضیه‌های مختلف  H در یادگیری مجموعه توابع هدف مختلف درون  C است. زیرا ما می‌خواهیم یادگیر  L به اندازه کافی جامع باشد تا بتواند هر تابع هدف درون  C را مستقل از اینکه توزیع  D چیست، یاد بگیرد. در بعضی مواقع نیز علاقه داریم که بدترین حالت توابع هدف درون  C را برای تمامی توزیع‌های  D بررسی کنیم.
چون علاقه ما به نزدیکی فرضیه خروجی  h به تابع هدف حقیقی  c است، پس کار را با تعریف خطای واقعی یک فرضیه  h بر روی  c و توزیع احتمال  D شروع می‌کنیم. خطای واقعی  h، حطای  h در دسته‌بندی نمونه‌های جدید با توزیع  D است.
تعریف :‌ خطای واقعی( error_{D}(h)) فرضیه  h برای تابع هدف  c و توزیع احتمال نمونه  D این است که نمونه انتخابی بر اساس توزیع  D اشتباه دسته‌بندی شود. (در رابطه زیر،  Pr_{x\in D} نشان دهنده احتمال عبارت با فرض اینکه  x از توزیع  D پیروی می‌کند، می‌باشد.
error_{D}(h)\equiv Pr_{x\in D}[c(x)\not =h(x)]
توجه کنید که خطا را طوری تعریف کرده ایم که که خطای تمامی نمونه‌های ممکن را اندازه بگیرد و فقط محدود به نمونه‌های آموزشی نباشد. بنابراین انتظار داریم که زمانی که از فرضیه به‌دست آمده بر روی نمونه‌های تصادفی جدید استفاده می‌کنیم، چنین خطایی داشته باشد. همچنین توجه کنید که این خطا به شدت به توزیع احتمال  D وابسته است. برای مثال، اگر  D توزیعی یکنواخت باشد که به تمامی نمونه‌های  X احتمالی یکسان نسبت می‌دهد، خطای فرضیه آمده در شکل روبرو نسبت به نمونه‌های درون نواحی هلالی به تمامی نمونه‌ها خواهد بود. در نتیجه اگر  D احتمال بیشتری به نمونه‌های نواحی هلالی نسبت دهد، خطا بیشتر خواهد شد. در بدترین حالت نیز، D، احتمال صفر به نمونه‌های خارج نواحی هلالی و احتمال ۱ به نمونه‌های درون نواحی هلالی نسبت می‌دهد و خطا ۱ خواهد بود، با وجود اینکه  c و  h واقعا اشتراک دارند. توجه داشته باشید که خطای  h برای  c به‌طور مستقیم، برای یادگیر غیرقابل مشاهده است.  L فقط کارایی  h را بر روی نمونه‌های آموزشی، در دسترس دارد و باید انتخاب خود در مورد فرضیه را بر اساس همین معیار انجام دهد. ما از عبارات خطای آموزشی (در مقابل خطای واقعی) برای نمایش نسبت نمونه‌های آموزشی با دسته‌بندی اشتباه توسط  h به کل نمونه‌های آموزشی استفاده می‌کنیم. قسمت بزرگی از بررسی ماشین از پیچیدگی یادگیری بر محور این سؤال متمرکز می‌شود که چگونه احتمال دارد که خطای آموزشی مشاهده شده، معیاری غلط‌انداز از  error_{D}(h) باشد؟ است.