پیچیدگی نمونه
پیچیدگی نمونه یک الگوریتم یادگیری ماشین، برابر است با تعداد نمونه‌های یادگیری که برای موفقیت الگوریتم لازم است. به صورت دقیق‌تر، پیچیدگی نمونه برابر است با حداقل تعداد نمونه‌های لازم، تا تابع خروجی الگوریتم با احتمالی نزدیک به «یک» در فاصله‌ای نزدیک به «صفر» از تابع هدف قرار گیرد. پیچیدگی نمونه به دو صورت در نظر گرفته می‌شود: طبق قضیه می‌دانیم که در حالت کلی، پیچیدگی نمونه نوع قوی بی‌نهایت است. به عبارت دیگر هیچ الگوریتم یادگیری‌ای وجود ندارد که بتواند با تعداد محدودی نمونه هر تابع هدفی را یاد بگیرد. به‌هرحال اگر خود را به توابع خاصی مانند توابع خطی یا توابع دودویی محدود کنیم؛ پیچیدگی نمونه محدود است و به مربوط می‌شود.
اگر formula_1 را مجموعه ورودی‌های ممکن و formula_2 را مجموعه خروجی‌های ممکن در نظر بگیریم، formula_3 را به صورت ضرب دکارتی این دو مجموعه formula_4 تعریف می‌کنیم. برای مثال برای مسئله ، formula_1 یک فضای برداری متناهی و formula_2 برابر با مجموعه formula_7 است.
formula_8 را مجموعه‌ای از توابع formula_9 که formula_10 است در نظر می‌گیریم. یک الگوریتم یادگیری formula_11 عبارت‌است از تابعی از formula_12 به formula_8. به‌عبارت دیگر یک الگوریتم یادگیری تعداد محدودی از نمونه‌های یادگیری را دریافت می‌کند و یک تابع formula_10 را به عنوان خروجی برمی‌گرداند. یک formula_15 را در نظر می‌گیریم، برای مثال این تابع می‌تواند تابع هزینه خطای مربعات formula_16 باشد. برای یک توزیع احتمال formula_17 داده‌شده روی formula_4 متوسط خطای تابع formula_9، که یکی از اعضای کلاس فرضیه formula_8 است، به صورت زیر تعریف می‌شود. formula_21
داده‌های آموزشی یک دنباله formula_22 تایی از زوج مرتب‌های formula_23 به صورت formula_24 تشکیل می‌دهند، که تمامی آن‌ها به صورت یکسان و مستقل از توزیع formula_17 نمونه‌برداری شده‌اند. یک الگوریتم یادگیری formula_11 به هر دنباله از داده‌های آموزشی formula_27 یکی از اعضای کلاس فرضیه formula_8 را نسبت می‌دهد. کمینه خطای کلاس فرضیه formula_8 به صورت زیر تعریف می‌شود.
formula_30
formula_31 را خروجی الگوریتم به‌ازای داده‎های آموزشی formula_27 در نظر می‌گیریم(formula_33 یک متغیر تصادفی است که به متغیر تصادفی formula_27 که از توزیع formula_35 نمونه‌برداری شده‌است بستگی دارد). به الگوریتم formula_11،
formula_43
به‌ازای هر الگوریتم یادگیری formula_11 و formula_45 داده شده، پیچیدگی نمونه، formula_46 را کمترین مقدار formula_41 تعریف می‌کنیم که رابطه بالا به‌ازای آن درست باشد. اگر الگوریتم formula_11 نباشد، آن‌گاه formula_49، هم‌چنین اگر الگوریتمی مانند formula_11 وجود داشته باشد که formula_46 عددی محدود باشد، می‌گوییم کلاس فرضیه formula_8 قابل یادگیری است.
پیچیدگی نمونه نشان‌دهنده میزان قاطعیت یک الگوریتم است، یعنی به ازای میزان دقت داده‌شده formula_53 و میزان اطمینان داده‌شده formula_54 الگوریتم به حداقل formula_55 نمونه آموزشی نیاز دارد تا بتواند با احتمال حداقل formula_56، خروجی‌ای با خطایی کمتر از formula_53 تولید کند. در مدل پیچیدگی نمونه باید تابعی چند جمله‌ای از formula_58 و formula_59 باشد. به عبارت دیگر باید داشته باشیم:
formula_60 اگر formula_8 یک مجموعه متناهی از فرضیه‌ها باشد و مجموعه آموزشی formula_62 به صورت یکسان و مستقل از توزیع formula_17 نمونه برداری شده باشد آنگاه به‌ازای هر formula_64 و formula_65 اگر الگوریتم formula_11 یکی از فرضیه‌های سازگار formula_67 را به عنوان خروجی تولید کند(فرضیه‌ای سازگار است که روی تمام نمونه‌های آموزشی با تابع هدف یکسان باشد) آنگاه
formula_68
formula_69
formula_70 می‌دانیم که فرضیه formula_71 سازگار است بنابراین formula_72
formula_73
formula_74
با توجه به می‌دانیم که:
formula_75
بنابراین:
formula_76
formula_77
formula_78