تعریف
اگر
را مجموعه ورودیهای ممکن و
را مجموعه خروجیهای ممکن در نظر بگیریم،
را به صورت ضرب دکارتی این دو مجموعه
تعریف میکنیم. برای مثال برای مسئله دستهبندی دوکلاسه ،
یک فضای برداری متناهی و
برابر با مجموعه
است.
را مجموعهای از توابع
که
است در نظر میگیریم. یک الگوریتم یادگیری
عبارتاست از تابعی از
به
. بهعبارت دیگر یک الگوریتم یادگیری تعداد محدودی از نمونههای یادگیری را دریافت میکند و یک تابع
را به عنوان خروجی برمیگرداند.
یک تابع هزینه
را در نظر میگیریم، برای مثال این تابع میتواند تابع هزینه خطای مربعات
باشد. برای یک توزیع احتمال
دادهشده روی
متوسط خطای تابع
، که یکی از اعضای کلاس فرضیه
است، به صورت زیر تعریف میشود.
دادههای آموزشی یک دنباله
تایی از زوج مرتبهای
به صورت
تشکیل میدهند، که تمامی آنها به صورت یکسان و مستقل از توزیع
نمونهبرداری شدهاند. یک الگوریتم یادگیری
به هر دنباله از دادههای آموزشی
یکی از اعضای کلاس فرضیه
را نسبت میدهد. کمینه خطای کلاس فرضیه
به صورت زیر تعریف میشود.
را خروجی الگوریتم بهازای دادههای آموزشی
در نظر میگیریم(
یک متغیر تصادفی است که به متغیر تصادفی
که از توزیع
نمونهبرداری شدهاست بستگی دارد). به الگوریتم
،
قاطع گفته میشود اگر
به صورت احتمالی به
میل کند. بهعبارت دیگر به ازای هر
و
عدد صحیح و مثبتی مانند
وجود داشتهباشد که بهازای هر
داشتهباشیم
بهازای هر الگوریتم یادگیری
و
داده شده، پیچیدگی نمونه،
را کمترین مقدار
تعریف میکنیم که رابطه بالا بهازای آن درست باشد. اگر الگوریتم
قاطع نباشد، آنگاه
، همچنین اگر الگوریتمی مانند
وجود داشته باشد که
عددی محدود باشد، میگوییم کلاس فرضیه
قابل یادگیری است.
یادگیری احتمالاً تقریباً صحیح و پیچیدگی نمونه
فضای فرضیه، فرضیههای سازگار، فرضیههای سازگار با خطای بالا
پیچیدگی نمونه نشاندهنده میزان قاطعیت یک الگوریتم است، یعنی به ازای میزان دقت دادهشده
و میزان اطمینان دادهشده
الگوریتم به حداقل
نمونه آموزشی نیاز دارد تا بتواند با احتمال حداقل
، خروجیای با خطایی کمتر از
تولید کند.
در مدل یادگیری احتمالاً تقریباً صحیح پیچیدگی نمونه باید تابعی چند جملهای از
و
باشد. به عبارت دیگر باید داشته باشیم:
کرانی برای پیچیدگی نمونه فضای فرضیه متناهی
اگر
یک مجموعه متناهی از فرضیهها باشد و مجموعه آموزشی
به صورت یکسان و مستقل از توزیع
نمونه برداری شده باشد آنگاه بهازای هر
و
اگر الگوریتم
یکی از فرضیههای سازگار
را به عنوان خروجی تولید کند(فرضیهای سازگار است که روی تمام نمونههای آموزشی با تابع هدف یکسان باشد) آنگاه
اثبات
میدانیم که فرضیه
سازگار است بنابراین
با توجه به نابرابری بول میدانیم که:
بنابراین: