چکیده :
نظریه یاد گیری محاسبه ای
در این بخش ویزگیهای نظری در مورد مشکلات متعدد یاد گیری ماشین حساب ارایه شده و انواع مهارت های متعدد الگوریتم های یاد گیری ماشین حساب مطرح شده است.این نظریه در صدد یافتن پاسخی مناسب به این سوالات است.تحت چه شرایطی یاد گیری موفقیت آمیز امکان پذیر است و تحت چه شرایطی غیر ممکن است.وتحت چه شرایطی الگوریتم خاص یاد گیری ,یاد گیری موفقیت آمیز را تضمین میکند.
مقدمه 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 کنترل میشود.
** خطای فرضیه 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 انجام میشود. به این صورت بیان میشود که <1/2 >0 و به این صورت <1/2 0< است. یاد گیرنده L با نتیجه احتمالی حداقل یک فرضیه H h را به دست میآورد که به صورت errorD(h) است.و این در زمانی است که چند جمله ای در n , 1/ و 1/و اندازه (C) تعیین میشود.
تعریف ما یاد گیرنده را به دو چیز ملزم میکند.اول اینکه 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 به طور عمده توسط تعدادی از مثال های آموزشی مورد نیاز یاد گیرنده تعیین شده است.افزایش تعداد مثال های آموزشی مورد نیاز همراه با اندازه مسئله را پیچیدگی نمونه مسئله یادگیری گویند که ویژگی های آن معمولا بیشترین توجه را به خود جلب میکند.به این دلیل که در بیشترین طبقه بندی های عملی بیشترین عاملی که موفقیت یادگیرنده را محدود میکند, محدود کردن قابلیت استفاده از داده های آموزشی است.
و...
NikoFile
