دانلود مقاله نظریه ی یادگیری محاسباتی

در این بخش ویزگیهای نظری در مورد مشکلات متعدد یاد گیری ماشین حساب ارایه شده و انواع مهارت های متعدد الگوریتم های یاد گیری ماشین حساب مطرح شده است.این نظریه در صدد یافتن پاسخی مناسب به این سوالات است.تحت چه شرایطی یاد گیری موفقیت آمیز امکان پذیر است و تحت چه شرایطی غیر ممکن است.وتحت چه شرایطی الگوریتم خاص یاد گیری ,یاد گیری موفقیت آمیز را تضمین میکند.

مقدمه 1-7 هنگامی که یادگیری ماشین حساب مورد مطالعه قرار میگیرد،این طبیعی است که تعجب کنید ،چه قانون کلی میتواند بر یاد گیرنده های ماشین و غیر ماشین فایق آید.

آیا این امکان وجود دارد تا دسته ای از مشکلات یاد گیری جدایی ناپذیر را که شاید مشکل یا ساده باشد را بتوان جدا از الگوریتم یاد گیری شناسایی نمود.؟

آیا میتوان تعداد مثال های آموزشی لازم را برای اطمینان از یاد گیری موفقیت آمیز تعیین کرد؟چگونه این تعداد تحت تاثیر قرار میگیرند ، اگر یاد گیرنده اجازه داشته باشد تا سوالاتی را یرای معلم مطرح کند ودر مقابل نمونه اختیاری از مثال های آموزشی را مشاهده کند ؛آیا میتوان تعداد خطا هایی را که یاد گیرنده قبل از آموختن عملکرد مورد نظر ، انجام داده را مشخص کرد؟آیا میتوان پیچیدگی محاسباتی جدایی ناپذیر دسته ای از مشکلات یاد گیری را توصیف کرد؟

اگر چه جواب های کلی که به این سوالات داده میشود هنوز نامشخص اند اما بخش هایی از نظریه یاد گیری محاسباتی شکل گرفت.در این بخش نتایج قابل توجهی که از این نظریه به دست آمده ، ارا یه میشود و در بردارنده پاسخ سوالاتی است که در محدوده تنظیم مشکلات خاص ایجاد میشود.ما در این جا بر روی مسا له یادگیری استقرایی تاکید نمودیم که عملکرد مورد نظر آن مشخص نیست.

فقط میتوان الگوهای آموزشی بر طبق این عملکرد مورد نظر به دست آوردو فرضیه های انتخابی را با فاصله تعیین کرد.در طی این تنظیم نمودن ما سوالاتی را از این قبیل مطرح میکنیم.چند تا از الگوهای آموزشی برای یاد گیری موفقیت آمیز عملکرد مورد نطر کافی است؟چند خطا توسط یاد گیرنده قبل از موفق شدن رخ میدهد .طبق ان چه که ما مشاهده میکنیم این امکان وجود دارد تا محدودیت های کمی بر روی این ارزیابی تعیین کنیم که به خصوصیات مسایل یاد گیری بستگی دارد و از این قرار است : اندازه یا پیچیدگی فاصله فرضیه ای که توسط یاد گیرنده مطرح میشود.

دقت داشتن در مورد این که مفهوم مورد نظر باید تقریبی باشد.

این احتمال باشد که یاد گیرنده مبتواند فر ضیه موفقی را ارایه دهد.

روش الگوهای یادگبری برای یاد گیرنده مطرح باشد.

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

پیچیدگی محاسباتی :چه تلاش های محاسباتی برای یاد گیرنده لازم است تا به فرضیه موفقیت آمیز نزدیک شود(به احتمال زیاد)؟

محدوده خطا :چه تعداد از الگوهای آموزشی را یاد گیرنده قبل از نزدیک شدن به فرضیه موفق ؛ اشتبا ها طبقه بندی کرد ؟

توجه کنید که در اینجا یکسری طبقه بندی خاص وجود دارد که ما میتوانیم بر طبق آن سوالاتی از این را پی گیری کنیم.

به عنوان مثال در اینجا روشهای مختلفی وجود دارد که مشخص میکند چه روشی برای یاد گیرنده موفقیت آمیز است و شاید ما آن را برای موفق شدن مشخص کنیم.یاد گیرنده باید فرضیه ای را به دست آورد که با مفهوم مورد نظر یکسان باشد.به جای آن شاید ما فقظ به این نیاز داشته باشیم تا فرضیه ای ایجاد شود که با مفهوم مورد نظر بیشتر از زمان آن همسازی داشته باشد .یا این که یک فرضیه معمولی به دست آورد .ما باید تعیین کنیم چگونه یادگیرنده به الگوهای آموزشی دسترسی خواهد داشت؟ما میتوانیم مشخص کنیم که الگوهای آموزشی به کمک یک معلم مطرح میشود.یا از طریق آزمایش هایی که یاد گیرنده انجام میدهد؛ آنها را به دست می آورد یا فقط آن ها را به طور تصادفی بر حسب یکسری مراحل بیرونی و کنترل یاد گیرنده ایجاد کند.همان طور که پیش بینی میشد جواب سوالات بالا به طبقه بندی خاص یا مدل آموزشی که در ذهن داریم بستگی دارد .

ادامه این فصل به این ترتیب مرتب شده : بخش 2-7 درباره معرفی برنا مه ریزی احتمالی یاد گیری تقریبا صحیح است.

بخش 7-3 تحلیل پیچیدگی نمونه و پیچیدگی محاسبه ای در مورد مشکلات یادگیری متعدد در چهار چوب بر نامه ریزی یادگیری تقریبا صحیح است.

بخش4 -7 معرفی اهمیت ارز یابی پیچیدگی فاصله فرضیه ای است که ابعاد vc گویند و تحلیل مارا در مورد یاد گیری pac با مشکلات موجود در فاصله فرضیه بی انتها گسترش میدهد.

بخش5-7 معرفی مدل محدوده خطا است و محدوده ای از تعداد خطا هایی که توسط چندین الگوریتم یاد گیری ایجاد شده را ارایه میدهد که در بخش قبلی بحث شد.نهایتا ما الگوریتم weighted-majority را مطرح می کنیم که یک الگوریتم قابل اجرا برای ترکیب کردن پیش بینی های چندین الگوریتم یاد گیری رقابت کننده است.

همرا با آن محدوده خطای نظری برای این الگوریتم تعیین میشود.

یاد گیری احتمالی ، فرضیه های تقریبا صحیح در این بخش ما بر نا مه ریزی خاصی را برای مساله یاد گیری مد نظر قرار دادیم که آن را مدل یاد گیری احتمالی تقریبا صحیح (pac ) گویند.ما با مشخص کردن برنامه ریزی مساله ای که مدل یاد گیری pac را تعریف میکند شروع میکنیم.سپس این سوالات را مورد توجه قرار میدهیم.چه تعداد از الگوهای آموزشی و چه تعداد از محاسبات لازم است ؛ با این هدف که طبقه بندی های مختلف عملکرد های مورد نظر را در چهار چوب این مدل pac آموزش میدهد.به منظور ساده سازی ؛ما بحث درباره یادگیری مفاهیم با مقدار بولی بر طبق داده های آموزشی بدون اختلال را محدود میکنیم.به هر حال برخی از نتایج حاصله را میتوان با طرح های کلی تر یاد گیری عملکرد های مورد نظر با ارز یابی واقعی توسعه داد.(مثلا natarajan در سال 1991 را نگاه کنید)و بعضی ها را میتوان از طریق انواع مشخصی از داداه های ناقص توسعه داد .(مثلا بخش Vazirani 1994 - kearns - 1998 laridرا بررسی کنید) 1-2-7 دسته بندی مشکلات همان طور که در بخش های قبلی بیان شد ؛x به مجموعه ای از تمام نمونه های موجود در طی عملکرد های مورد نظر که تعریف شدند اشاره داردمثلا x میتواند مجموعه ای از تمام مردم را نشان دهد که هر یک را با خصوصیاتی شرح میدهند .سن (مثلا پیر یا جوان).

قد (مثلا کوتاه یا بلند).پس c به برخی از مجموعه های اهداف مورد نظر اشاره دارند که یاد گیرنده ما آن را فراتر از یاد گیری میگوید.

c هر یک از اهداف مورد نظر در c است که با برخی از زیر مجموعه های x تطبیق میکند یا برخی از عملکرد های ارز یابی شده بولی یکسان است.به این صورت بیان میشود c:xà{0,1} به عنوان مثال یک مفهوم مورد نظر c درc میتواند این معنی را برساند.

(افرادی که اسکی باز هستند ) اگر x یک مثال مثبت از c باشد ، سپس ما آن را به این صورت مینویسیم c(x)=1 اگر مثال منفی باشد به این صورت c(x)=0 است.

ما نمونه هایی را در نظر میگیریم که به طور اتفاقی از طریق x مطابق با توزیع احتمالی D ایجاد میشوند .

D میتواند توزیعی از نمونه های ایجاد شده باشد .با مشاهده افرادی که در بزرگترین فروشگاه ورزشی در سوییس اعتصاب کردند.به طور کلی D میتواند با هر نوعی توزیع شودو به طور کلی برای یاد گیرنده ناشناخته است.در کل ما نیاز داریم تا D در حالت ثابت قرار گیرد.

طوری که توزیع آن دایما بدون عوض کردن باشد.نمونه های آموزشی با رسم کردن مثال X به طور اتفاقی مطابق با D ایجاد میشود.

پسX به همراه مفهوم مورد نظر آن؛ C(X) برای یاد گیرنده ارایه میشود.

یاد گیرندهL برخی از فرضیه های موجود در مجموعه H را مورد توجه قرار میدهد و تلاش میکند تا مفهوم مورد نظر را یاد بگیرد.مثلا H میتواند مجموعه ای از تمام فرضیه هایی باشد که به وسیله ارتباط خصوصیاتی مثل قد و سن قابل توصیف است.

بعد از مشاهده مجموعه ای از مثال های آموزشی مفهوم مورد نظرC، L باید یک سری از فرضیه هایh را ازH به دست آورد.طوری که C را ارزیابی میکند.البته ما موفقیت L را با عملکرد h از طریق نمونه های جدید که به طور اتفاقی از طریق X بر طبق D رسم شده را مورد بررسی قرارر میدهیم.

توزیع احتمالی آن برای ایجاد داده های آموزشی به کار میرود.

در چهار چوب این برنامه ریزی ما مشخص کردیم کارکرد یاد گیرنده های مختلف L را با استفاده از فاصله های فرضیه ای مختلف H مورد توجه قرار دادیم.در این موقع مفاهیم مورد نظر مخصوص یادگیری بر حسب طبقه بندی های مختلف C رسم میشود.زیرا ما نبازمندیم که L برای یاد گیری هر مفهوم مورد نظرC بدون توجه به توزیع مثال های آموزشی به اندازه کافی کلی است.ما تحلیل های موارد بدتر را در طی تمام اهداف مورد نظر از طریقC و تمام توزیع های نمونه D مورد توجه قرار دادیم.

2-2-7 خطای یک فرضیه به این دلیل که چگونگی دقت یاد گیرنده در ارایه فرضیه های تقریبا درست h با مفهوم مورد نظر واقعی C را مورد توجه قرار دادیم.

پس اجازه بدهید تا ما خطای درست یک فرضیه h را با توجه به مفهوم مورد نظر C و توزیع نمونه D تعریف کنیم.

معمولا خطای درست h فقط میزان خطایی است که ما انتظار داریم تا هنگام به کار بردن h با نمونه های بعدی که مطابق با توزیع احتمالیD رسم شده ایجاد شود.در اینجا ما خطای درست h را با استفاده از C تعریف میکنیم و تا عملکرد مورد نظر بولی را نشان دهد.

تعریف خطای درست: به معنی (error D(h) خطای درست فرضیه h باتوجه به مفهوم مورد نظر C و توزیع D است که احتمال دارد h اشتباه طبقه بندی شده باشد.رسم کردن نمودار اتفاقی بر طبق D انجام میشود.

در اینجا علامت نشان میدهد که نتیجه احتمالی توزیع مثال D کنترل میشود.

تصویر 1-7 تعریفی از خطا را به صورت گرافیکی نشان میدهد.

** خطای فرضیه h با مراجعه به مفهوم هدفc .

خطای h با مراجعه به c است که که به احتمال قوی یک مثال رسم شده تصادفی در این ناحیه خواهد افتاد,.هر جا که h و ز مخالف یکدیگر طبقه بندی شوند.

+ نقطه مثبت و – نقطه منفی مثال های آموزشی را نشان میدهد.توجه داشته باشید که h یک خطای غیر صفر دارد و با مراجعه به c و و با وجود این قضیه کهh و c موافق هم هستند.** مفاهیم C وh با مجموعه ای از نمونه هاکه در چهار چوب X شرح داده شده آنها را مثبت گویند.خطای h با توجه به C نتیجه احتمالی یک نمونه رسم شده اتفاقی است ودر بخشی که با Cوh هماهنگی ندارند؛کاهش میابد.(یعنی اختلاف مجموعه آنها ) ما شرحی را انتخاب کردیم تا خطا را در طی توزیع کامل نمونه ها تعریف کنیم و نه فقط در خصوص الگوهای آموزشی زیر.

این یک خطای درست است که ما انتظار داریم با آن مواجه شویم زمانی که واقعا فرضیه نگه داری شده h بر نمونه های بر روی نمونه های بعدی که از طریق D رسم شده مورد استفاده قرار گیرد.

توجه کنید که خطا شدیدا به توزیع احتمالی و نامشخص D بستگی دارد.

مثلا اگر D یک توزیع احتمالی یکسان باشد ؛ همان احتمال را به هر نمونهX اختصاص میدهد.

سپس خطای فرضیه تصویر 1-7 میتواند بخشی از فضای نمونه کلی باشد و در بخشی که h قرار دارد کاهش میابد و مخالف C است.

به هر حال همان h,c دارای خطای بیشتری میباشند اگرD واقع شود .به احتمال خیلی زیاد نمونه های مربوط به h وC متقارن خواهند بود.

اگرD در حد نهایی با علامت صفر واقع شود نتیجه احتمالی نمونه ها به این صورت است که h(x)=c(x) سپس خطای H در تصویر 1-7 میتواند یک باشد.بر خلاف این واقعیت که h وC در مورد تعداد بسیاری از مثالها (با نتیجه احتمالی صفر ) توافق دارند.

نهایتا توجه داشته باشید که خطای h با توجه به C برای یاد گیرنده دقیقا قابل مشاهده نیست.

L میتواند فقط عملکرد h را در خصوص مثال های آموزشی مشاهده کند و آن باید فرضیه به دست آمده را فقط بر این اساس انتخاب کندما از اصطلاح خطای آموزشی استفاده میکنیم تا بخشی از مثال های آموزشی که توسط h اشتباه طبقه بندی شدند را در مقایسه با تعریف خطای درست که در بالا ارایه شده , نشان می دهیم.اکثر تحلیل های ما در مورد پیچیدگی یادگیری است.توجه عموم به این سوال است؛ چقدر احتمال دارد که مشاهده خطای آموزشی مربوط بهh , ارزیابی پیچیده ای از درستی خطا ی D(h) ارایه دهد؟

.

خطای آموزشی که در بالا تعریف شد همان خطای نمونه است برای وقتی که مجموعه ای از نمونه های S تعیین میشودکه نتیجه احتمالی خطای نمونه ارزیابی پیچیده ای از خطای درست را ایجاد میکند.طبق این فرضیه S نمونه داده ها است که جدا از h رسم میشود .به حر حال وقتی S مجموعه ای از داداه های آموزشی باشد ,یاد گیری فرضیهh شدیدا به S بستگی دارد .بنا بر این در این بخش ما تحیلی را ارایه دادیم که این مورد خاص و مهم را مورد توجه قرار میدهد.

3-2-7 قابلیت یاد گیری PAC هدف ما مشخص کردن طبقه بندی های مفاهیم مورد نظر است که بتوان با اطمینان آن را از طریق تعداد قابل قبولی از مثال های آموزشی که به طور اتفاقی رسم شوند با میزان محاسبه قابل قبولی فرا گرفت.انواع گزارشهایی که در مورد قابلیت یاد گیری میتوان حدس زد درست است ,کدامند؟

ما سعی میکنیم تا تعداد مثال های آموزشی مورد نیاز برای یاد گیری فرضیه h مشخص کنیم , طوری که error D(h)=0 است .متاسفانه آن مشخص میکند ,طبقه بندی را که مورد بررسی ما قرار گرفت ,بی نتیجه بود و دو دلیل داشت : اولا: در صورتی که ما نمونه های آموزشی را مطابق با هر مثال موجود در X ارایه دادیم (یک فرضیه واقعی نیست )در این جا چندین فرضیه ساز گار با مثال های آموزشی ارا یه میشود.

یاد گیرنده نمیتواند مطمئن باشد ,آن را که انتخاب کرد ه با مفهوم مورد نظر مطابقت میکند.

دوما:مثال های آموزشی ارایه شده بدون نظم وترتیب رسم میشوند که همیشه نتیجه احتمالی آن غیر از صفر است.مثالهای آموزشی که یاد گیرنده با آن مواجه میشود ممکن است گمراه کننده باشد.(به عنوان مثال ,اگر چه ما مکرر ا اسکی باز ها را در ارتفاعات مختلف میبینیم.در آن روز برای هر یک از آنها فرصت کمی وجود دارد تا همه مثال های آموزشی را که در ارتفاع دو متری روی میدهد را مشاهده کنید).

برای تطبیق دادن این دو مشکل ما خواسته هایمان را در مورد یاد گیرنده در دو روش کم میکنیم .اولا ما نیاز نداریم تا یاد گیرنده فرصیه ای بدون خطا به دست آورد,ما فقط نیاز داریم که خطای آن با محدود کردن و کاهش یافته و به اندازه دلخواه کوچک شود.دوما ما نیاز نداریم تا یاد گیرنده در هر مرحله از رسم بدون نظم مثال های آموزشی موفق شود.ما فقط نیاز داریم به این که عدم موفقیت نتیجه احتمالی آن را با یکسری محدودیت های لازم محدود کنیم تا به طور دلخواه آن را کوتاه کنیم.

به طور خلاصه ما فقط ملزم میکنیم که تا یاد گیرنده فرصیه احتمالی را یاد بگیرد که تقریبا صحیح است.از این رو به اصطلاح احتمال یاد گیری تقریبا صحیح یا به طور مختصر یاد گیری PAC میگوییم.

به یک سری از طبقه بندی های C که در طی یک سری از مجموعه مثال های X در طول n تعریف شده ,توجه کنیدو یک یاد گیرنده L از فاصله فرضیه H استفاده میکند.ما میگوییم که مفهوم طبقه بندی C توسط L با استفاده از H از طریق PAC قابل یاد گیری است.اگر برای هر مفهوم مورد نظرc درC , L نتیجه احتمالی -1 حاصل شود یک فرضیه h با error D(h) بعد از مشاهده تعداد قابل قبولی از مثال های آموزشی با مقدار قابل قبول محاسبات اجرا میشود.البته با دقت بیشتر.

تعریف: به مفهوم طبقه بندی C که با توجه به مجموعه مثال های X در طول n تعریف میشود, توجه کنید, یاد گیرنده L از فاصله فرضیه H استفاده میکند.

C قابلیت یادگیری PAC توسط L با استفاده از H است.

برای تمام C c توزیع های D در طیX انجام میشود.

به این صورت بیان میشود که 0 و به این صورت تعریف: به مفهوم طبقه بندی C که با توجه به مجموعه مثال های X در طول n تعریف میشود, توجه کنید, یاد گیرنده L از فاصله فرضیه H استفاده میکند.

به این صورت بیان میشود که 0 و به این صورت تعریف ما یاد گیرنده را به دو چیز ملزم میکند.اول اینکه L با هر احتمال زیاد ( -1 ) به طور آزادانه فرضیه ای را ارایه دهد که به طور اختیاری خطای کمتری ( ) دارند.دوم این که آن باید به طور مفید کار کند .

در زمانی که بیشتر به صورت چند جمله ای با 1/ و 1/ افزایش میابد .پس قدرت درخواست های ما در مورد فرصیه به دست آمده تعریف میشود و یا n و اندازه (C) پیچیدگی ذاتی فاصله نمونه تاکید شده X را و طبقه بندی مفهوم کلی C را تعریف میکند.در این جا n اندازه نمونه های X است.مثلا اگر نمونه های X با ویژگی های بولیK متقارن باشند پس n=k میشود.دومین پارامتر تعیین فاصله اندازه (C)طول Cرا در C کد گذاری میکند.فرض کنید برخی از آن ها برای C نمایش داده میشوند.مثلا اگر مفاهیم موجود در Cارتباط بالایی با ویژگی های بولی Kدارند ,.هر تعریفی از طریق شاخص های فهرست بندی مربوط به ویزگی های این ارتباط را شرح میدهد.پس اندازه (C)تعداد ویژگی های بولی است که در واقع برای شرحC به کار میرود.

تعریفی که ما از یادگیری PAC ارایه میدهیم ابتدا ظاهر میشود تا فقط با منابع محاسباتی مورد نیاز جهت یاد گیری مورد توجه قرار گیرد.در حالی که در این روش مسئله که بیشتر مورد توجه است, تعداد مثال های آموزشی مورد نیاز است .به هر حال این دو ارتباط خیلی نزدیکی دارند.اگر L بخواهد زمان پردازش هر مثال آموزشی رابه حداقل برساند پس برای Cروش PAC توسط یاد گیرنده قابل یاد گیری است و L باید از یک چند جمله ای تعداد مثال های اموزشی را فرا گیرد .در واقع روش معولی برای نشان دادن طبقاتی از مفاهیم مورد نظرC ,PAC قابل یاد گیری است.ابتدا نشان میددهد که هر مفهوم مورد نظر در Cرا میتوان از طریق یک چند جمله ای از تعداد مثال های آموزشی آموخت,سپس نشان داد که زمان پردازش هر مثال به صورت چند جمله ای محدود میشود .

قبل از عوض کردن ما باید خاطر نشان کنیم که یک فر ضیه ضمنی محدود کننده در تعریف ما در مورد قابلبت یادگیری pac ارایه شده .این تعریف به طور ضمنی فرض میشود که فاصله فرضیه یاد گیرنده در H شامل یک فرضیه با مقدار کم خطای دلخواه در مورد هر مفهوم مورد نظر در C است.این از طریق شرایط موجود در تعریف بالا ناشی میشود,که طبق آن یادگیرنده وقتی موفق میشود که محدوده خطای به طور اختیاری به صفر نز دیک شود.البته این مشکل است که اطمینان حاصل کرد که اگر فرد متوجه نباشد که Cدر پیشاپیش قرار گرفته ,آنگاه H را به عنوان مجموعه قوی تر از X به کار میبرد.چنان چه H بدون جهت گیری باشد نمیتواند از تعمیم دهی صحیح تعدادی از مثال های آموزشی قابل قبول پشتیبانی کند.با این وجود ,نتایج به دست آمده بر اسا س مدل یادگیری PAC است که دید گاه مفیدی با توجه به پیچیدگی مشکلات مختلف یاد گیری ارایه میدهد و با توجه به نسبت تعمیم دهی دقیق با مثال های آموزشی بیشتر ,اصلاح میشود.علاوه بر این در بخش 1-3-7 ما این فرضیه محدود کننده را ارتقا میدهیم تا در این مورد بررسی کنیم که یادگیرنده از قبل فرضیه ای درباره حالتی از مفهوم مورد نظر ایجاد نکرده.

3-7 پیچیدگی نمونه برای فاصله فرضیه محدود همان طور که قبلا ذکر شد , قابلیت یاد گیریPAC به طور عمده توسط تعدادی از مثال های آموزشی مورد نیاز یاد گیرنده تعیین شده است.افزایش تعداد مثال های آموزشی مورد نیاز همراه با اندازه مسئله را پیچیدگی نمونه مسئله یادگیری گویند که ویژگی های آن معمولا بیشترین توجه را به خود جلب میکند.به این دلیل که در بیشترین طبقه بندی های عملی بیشترین عاملی که موفقیت یادگیرنده را محدود میکند, محدود کردن قابلیت استفاده از داده های آموزشی است.

در این جا ما محدوده کلی در مورد پیچیدگی نمونه گروه وسیعی از یاد گیرنده ها, ارایه میدهیم که به آنها یادگیرنده های سازگار گویند.یک یاد گیرنده در صورتی سازگار است که فرضیه های به دست آمده آن در هر شکل ممکن با داده های آموزشی کاملا منطبق باشد.این کاملا منطقی است که بخواهید یک الگوریتم یاد گیری سازگار ارایه شود تا ما بتوانیم به طور نمونه فرصیه ای را ترجیح دهیم که متناسب با داده های آموزشی باشد.توجه داشته باشید که تعدادی از الگوریتم های یاد گیری در بخش های قبل مورد بررسی قرار گرفت که در بردارنده تمام الگوریتم های یاد گیری بود که در بخش 2 شرح داده شد و منطبق با یادگیرنده ها می باشند.

آیا میتوانیم محدوده ای از تعداد ی نمونه ها ی آموزشی مورد نیاز هر یاد گیرنده سازگار را به دست آوریم که مستقل از الگوریتم های خاصی باشد که برای به دست آوردن یک فرضیه سازگار به کار میروند؟جواب ,بله است.برای انحام این کار لازم است نوع فاصله را داشته باشیم.در این جا ما نوع فاصله تعریف میکنیم.

VS H,D مجموعه ای از تمام فرضیه های H h است که به طور صحیح مثال های آموزشی D را طبقه بندی میکند: هدف از این نوع فاصله در اینجا این است که خروجی های هر یاد گیرنده ساز گار فرضیه ای, متعلق به نوع فاصله است.بدون این که فاصله مثال X , فاصله فرصیه X یا داده های آموزشی D مد نظر باشد.

دلیل آن فقط این است که با تعریف نوع فاصله VS H,D هر فرضیه سازگار موجود در H را در بر میگیرد.بنابر این با محدود کردن تعداد مثالهای مورد نیاز هر یادگیرنده سازگار ,ما نیاز داریم فقط تعداد مثال های مورد نیاز را تعیین کنیم تا مطمئن شویم در نوع فاصله فرضیه های غیر قابل قبولی گنجانده نشود.تعریفی که ذیلا آمده بعد از HAUSSLR در سال 1998 این موضوع را با دقت بیشتری بیان میکند.

تعریف : به این موارد توجه کنید.یک فاصله فرضیه H ,مفهوم مورد نظرC ,و توزیع مثال و مجموعه ای از مثال های آموزشی D ازC فاصله نوع VS H,D گفته شده که کامل با توجه به C و D است.اگر هر فرضیه h در VS H,D خطایی کمتر از با توجه بهC و D داشته باشد از این قرار است : این تعریف در تصویر 2-7 شرح داده شده است.

*****تصویر 2-7 فاصله نگارشی VS H,D زیر مجموعه ای از فرضیه است که خطای آموزشی صفر را دارد.(علامت گذاری با r=0 در شکل).

البته errorD(h) (علامت گذاری شده با erroe در شکل) ممکن است غیر صفر باشد,حتی برای فرضیه ای که مرتکب خطای صفر شده.

فاصله نگارشی میگویدکه اصطلاحات موقعی همه فرضیه های h در VS H,D باقی میماند که errorD(h0 نوع فاصله -تهی فقط در مورد تمام فرضیه های منطبق با مثال های آموزشی مشاهده شده وجود دارد .(یعنی آنهایی که دارای خطای آموزشی صفر میباشند) و باید خطای درست آن کمتر از باشد.

البته از دیدگاه یاد گیرنده همه میتوانند فرضیه های متناسب با داده های آموزشی را بشناسند,تمام آنها به طور یکسان دارای خطای آموزشی صفر میباشند.فقط نظاره گری که میتواند مفهوم مورد نظر را تشخیص دهد میتواند با اطمینان تعیین کند که چه نوع فاصله کامل است.به طور شگفت انگیزی مبحث احتمالی, شرایط را طوری برای ما فراهم کرد تا نتیجه احتمالی نوع فاصله را که میتواند کامل باشد را بعد از اریه تعدادی از مثال های آموزشی مشخص کنیم حتی بدون این که شناختی باشد .مفهوم مورد نظر یا توزیع مثال های آموزشی رسم شده ,تعیین شد.

HAUSSLER در سال 1998 چنین محدوده ای را در شکلی از قضیه ای که در این جا ارایه شده ,بیان کرد.

قضیه 1-7 نوع فاصله با کامل شدن .اگر فاصله فرضیه H محدود باشد و D زنجیره ای از M>=1 باشد.مثال هایی که به طور اختیاری رسم شدند مستقل از یکسری مفاهیم مورد نظر C است پس برای هر 1 0 تعیین شده و نتیجه احتمالی نوع فاصله VS H,D جزو کامل شده به شمار نمی آید (با توجه به C )و کمتر یا مساوی با m e^ -H است.

اثبات : بگذارید h1.h----hk به عنوان تمام فرضیه های موجود درH باشد که خطای درست آن با توجه به C بزرگتر از است.مادر مورد تهی در نوع فاصله موفق نبودیم.اگر و اگر فقط حداقل یکی از این فرضیه های ایجاد شده با تمام m مستقل از مثال های آموزشی اختیاری هماهنگ باشد.نتیجه احتمالی هر یک فرضیه دارای خطای درست بیشتری از است که میتواند با یک مثال رسم شده اختیاری حداکثر در ) -1( سازگار باشد.

بنابر این چنین احتمالی وجود دارد که این فرضیه با m مثال هایی که به طور مستقل رسم شده حداقل در m^ ) -1( تطبیق میکند.ما فرصیه های k را با خطای بیشتر از داریم؛این احتمال وجود دارد که حداقل یکی از اینها با تمام مثال های آموزشی m نهایتا در m^ ) -1( k مطابقت داشته باشد.و از آنجا یی که H k پس حد اکثر میشود: m^ ) -1 ) H بالا خره ما از یک حالت کلی نابرابر استفاده می کنیم ا گر 10 پس e^ - ) -1( بنابراین : و این قضیه اثبات شد .

ما در مورد محدوده بالا این عنوان را تایید کردیم که طبق نتیجه احتمالی نوع جزو کامل به شمار نمی آید.و بر اساس تعداد مثال های آموزشیm خطای مجازو اندازه H میباشد .روش دیگری را که به کار ببرید, این احتمال وجود دارد که در این محدوده ها مثال های آموزشیm موفق نباشندتا تمام فرضیه های بد را حذف کند(یعنی فرضیه های با خطای درست بزرگتر از است).برای هر یادگیرنده سازگار از فاصله فرضیه H استفاده میشود.بگذارید ما از این نتیجه گیری برای تعیین تعداد مثال های آمورشی مورد نیاز استفاده کنیم تا این احتمال را که بیان میکند بعضی از مقادیر مطلوب که در این جا آمده نا موفق خواهد بود را کاهش دهیم.

1-7 m- ^ eH اصطلاحاتی که برای راه حل m به کار میرود را دوباره تنظیم میکنیم,و به این صورت بیان میکنیم: 2-7 به طور خلاصه نابرابری که در معادله (2-7) مشخص شده محدوده کلی از تعداد مثال های آموزشی را تامین میکند که برای هر یاد گیرنده سازگار کافی است تا با موفقیت تمام مفاهیم مورد نظر در H را با هر مفهوم مطلوبی از و فرا بگیرد.این تعداد مثال های آموزشی m کافی است تا اطمینان حاصل کنید هر فرضیه سازگاری که احتما لا دارای نتیجه احتمال ( 1-) است .تقریبا در چهار چوب خطای صحیح است).توجه کنیدm به طور خطی در 1/ و از نظر لگاریتمی در را افزایش میدهد.

هم چنین از نظر لگاریتمی در اندازه فاصله فرضیه H گسترش میابد.

توجه داشته باشید که محدوده بالا را میتوان به طور اساسی ارزیابی کرد.مثلا اگر چه احتمال عدم موفقیت با تهی شدن نوع فاصله وجود دارد ,باید در فاصله [1و0] قرار گیرد .محدوده آن از طریق قضیه ای که با H افزایش طولی دارد ,ایجاد میشود.در مورد فاصله های فرضیه ای بزر گ به اندازه کافی نمیتوان محدوده ای بزرگتر از قبلی به راحتی تعیین کرد.در نتیجه محدوده ای که به دست می آید در معادله 2-7 نابرابر است و اساسا میتوان تعداد مثال های آموزشی مورد نیاز را بررسی کرد .نقطه ضعف این محدوده در واقع به علت اصطلاح H است که از طریق اثبات این عنوان شکل گرفت.

وقتی نتیجه احتمالی به طور خلاصه بیان میکند که یک فرضیه با توجه به تمام فرضیه های دیگر میتواند قابل قبول باشد:در واقع یک محدوده فشرده تر در خیلی از موارد وجود دارد و با محدوده ای که فاصله های فرضیه ای بزرگتر را تا بی نهایت پوشش میدهد ,یکسان است.

این عنوان بخش 4-7 است.

1-3-7 یاد گیری ندانم گرایی و فرضیه های متناقض معادله2-7 از اهمیت خاصی بر خور دار است زیرا به ما میگوید که چه تعداد از مثال های آموزشی لازم است تا مطمئن شویم که هر فرضیه H خطای آموزشی نداردو خطای درست آن حداکثر است(با نتیجه احتمالی -1) و متاسفانه اگر H فاقد مفهوم مورد نظر C باشد پس فرضیه ای را با خطای صفر هرگز نمیتوان به دست آورد.در این مورد ما اکثرا از یاد گیرنده میخواهیم تا فرضیه ای را از H به دست آورد که در خصوص مثال های آموزشی کمترین خطا را داشته باشد.یک یاد گیرنده فرض نمی کند که مفهوم مورد نظر از طریق H قابل قبول است و به راحتی میتوان فرضیه ای را با کمترین خطای آموزشی پیدا کرد که بیشتر یادگیرنده ندانم گرا گویند.زیرا در مورد این که آیا HC است یا نه ,نظریه ای از قبل ندارد.

اگر چه معادله 2-7 بر اساس این فرضیه قرار گرفته که یاد گیرنده ,فرضیه با خطای صفر به دست آورد .

یک محدوده مشابه را میتوان برای این عنوان یافت که نشان میدهد یادگیرنده فرضیه هایی را مورد توجه قرار میدهد که خطای آموزشی دارند.به بیان دقیق تر , D را تعیین کنید تا مجموعه مشخصی از مثال های آموزشی را نشان دهد که برای یادگیرنده موجود است,در مقایسه با D که توزیع احتمالی را در خصوص مجموعه کاملی از مثال ها نشان میدهد.سپس errorD(h) را قرار دهید تا خطای آموزشی فرضیه hرا نشان دهد .به خصوص errorD(h) بخشی از مثال های آموزشی د ر D را تعریف میکند که توسط h اشتباه طبقه بندی شدند.

توجه کنید که errorD(h) درباره نمونه خاصی از داده های آموزشی D ممکن است که با خطای درست errorD(h) در مورد توزیع احتمالی D تفاوت داشته باشد.هم اکنون h(best) را تعیین کنید ,یک فرضیه ای از H را که کمترین خطای آموزشی را در طی مثال های آموزشی دارد, نشان دهد.چه تعداد از مثال های آموزشی لازم است که مطمئن شویم که به احتمال زیاد خطای درست errorD(h best) بیشتر از errorD(h best) + نمیباشد.به این سوال توجه کنید, در بخش قبلی فقط یک مورد خاصی از این سوال مطرح شد وقتی که errorD(h best) با صفرواقع شد.

این سوال را میتوان با استفاده از مباحث قیاسی در اثبات قضیه 1-7 جواب داد.در این جا کمک خواستن از محدوده های کلی hoeffding مفید است (گاهی آن را محدوده های افزودنی چرنوف میگویند) محدوده های هوفدینک انحراف بین نتیجه احتمالی درست برخی از وقایع را مشخص میکند.و مکررا در طی آزمایش های مستقل m مشاهده میشود.به بیان دقیق تر این محدوده ها برای آزمایش هایی به کار میروند که در بردارنده آزمایشهای bernaulli در باره m و به طور مجزا است.مثلا جدا از m در پرتاب کردن یک سکه و این احتمال که روی سر میچرخد.)این احتمال وجود دارد که روی سکه مطابق با نتیجه احتمالی فرضیه ای باشد که یک نمونه به دلخواه رسم شده را اشتباه طبقه بندی کرد.

m مستقل از پرتاب های سکه باm مستقل از نمونه های رسم شده مطابقت میکند.کثرت وقوع طرفین سکه در مثال های m با کثرت وقوع طبقه بندی اشتباه در طی مثال های m تطبیق میکند.محدوده های هوفدینگ بیان میکند که اگر خطای آموزشی errorD(h) درطی مجموعه D ارزیابی شود,در بر دارنده مثال های اتفاقی رسم شده m است.

سپس به این صورت بیان میشود: