در مورد پیچیدگی نمونه توضیح بده.
پیچیدگی نمونه یک الگوریتم یادگیری ماشین، برابر است با تعداد نمونه‌های یادگیری که برای موفقیت الگوریتم لازم است. به صورت دقیق‌تر، پیچیدگی نمونه برابر است با حداقل تعداد نمونه‌های لازم، تا تابع خروجی الگوریتم با احتمالی نزدیک به «یک» در فاصله‌ای نزدیک به «صفر» از تابع هدف قرار گیرد.پیچیدگی نمونه به دو صورت در نظر گرفته می‌شود:طبق قضیه می‌دانیم که در حالت کلی، پیچیدگی نمونه نوع قوی بی‌نهایت است. به عبارت دیگر هیچ الگوریتم یادگیری‌ای وجود ندارد که بتواند با تعداد محدودی نمونه هر تابع هدفی را یاد بگیرد.به‌هرحال اگر خود را به توابع خاصی مانند توابع خطی یا توابع دودویی محدود کنیم؛ پیچیدگی نمونه محدود است و به مربوط می‌شود.تعریف.اگر 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_30formula_31 را خروجی الگوریتم به‌ازای داده‎های آموزشی formula_27 در نظر می‌گیریم(formula_33 یک متغیر تصادفی است که به متغیر تصادفی formula_27 که از توزیع formula_35 نمونه‌برداری شده‌است بستگی دارد). به الگوریتم formula_11، گفته می‌شود اگر formula_37 به صورت احتمالی به formula_38 میل کند. به‌عبارت دیگر به ازای هر formula_39 و formula_40 عدد صحیح و مثبتی مانند formula_41 وجود داشته‌باشد که به‌ازای هر formula_42 داشته‌باشیم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_69formula_70می‌دانیم که فرضیه formula_71 سازگار است بنابراین formula_72formula_73formula_74با توجه به می‌دانیم که:formula_75بنابراین:formula_76formula_77formula_78