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

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

مقدمه 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 را در خصوص مثال های آموزشی مشاهده کند و آن باید فرضیه به دست آمده را فقط بر این اساس