سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.
در این جلسه و جلسه بعدی در مورد یادگیری مبتنی بر نمونه صحبت می‌کنیم که کاملا متفاوت هستن از تمام مطالبی که تا اینجا دیدیم. این نوع از روش‌هارو با عنوان روش‌های غیر پارامتریک هم می‌شناسیم. در ابتدا دیدگاه حل مسئله به‌صورت غیر پارامتریک را خواهیم دید و سه مسئله متفاوت:
را بررسی خواهیم کرد.
ما همواره این گونه مسائل را به‌صورت پارامتریک حل می‌کردیم. یعنی توزیع پارامتری روی داده‌ها در نظر می‌گرفتیم و سعی می‌کردیم به کمک داده‌ها پارامترهای توزیع رو تخمین بزنیم. جنس توزیع رو ثابت در نظر می‌گرفتیم و هدفمون فقط تخمین پارامترها بود.
در دیدگاه غیر پارامتریک اصلا پارامتری در نظر نمی‌گیریم که به کمک داده‌های آموزش بدستش بیاریم و مستقیم از خود داده‌های آموزش استفاده خواهیم کرد.
از توزیعی که به روش غیر پارامتریک تخمین می‌زنیم جلوتر در مسئله دسته‌بندی می‌تونیم استفاده کنیم.
در این دیدگاه مستقیم باید داده‌ها را نگه داریم و همواره با خودشون کار داریم.
این دیدگاه شاید کمی شبیه به تخمین هیستوگرام باشه به جای تابع چگالی احتمال. فرض کنید تو شکل پایین محور افقی رو به تعدادی bin مساوی با عرض h تقسیم کردیم، حالا برای اینکه بفهمیم هر مستطیل چه طولی باید داشته باشه و محور عمودی به ازاش چه عددی بگیره، باید بیایم تعدادداده‌هایی که تو هر bin افتادن رو تقسیم بر تعداد کل نمونه‌ها کنیم تا به‌دست بیاد.
حالا چجوری باید این رو تبدیل به توزیع احتمال کنیم؟ فرض کنید اول یه داده رو پیدا می‌کنیم و می‌بینیم که کجا میفته (یعنی فاصله اون نقطه از مرکز bin اگر کوچیک‌تر از نصف فاصله bin که با h نشون دادیم بشه به این معنیه که اون نقطه در اون bin قرار گرفته)، حالا تا اینجا bin مرتبط با داده رو هم پیدا کردیم. در نهایت باید تقسیم بر h بشه.
حالا فرض کنید یه ناحیه R داریم، احتمال اینکه یه نمونه داخل ناحیه R بیفته برابر با انتگرال روی ناحیه R هست از تابع P(x) که تو خط اول اسلاید پایین هم نشون داده شده. از طرفی فرض کنید n سمپل داریم. احتمال اینکه k سمپل از n سمپل داخل ناحیه R بیفته با توزیع binominal به‌دست میاد. با توجه به خواصی که توزیع binominal داره، می‌تونیم به این نتیجه برسیم که k=nP. پس احتمال افتادن k نقطه از n نقطه، برابر میشه با k/p. در صورت زیاد شدن نمونه‌ها اگر مقدار k رو ثابت نگه داریم، حتما واریانس به سمت 0 شدن میره.
برای تخمین خود توزیع می‌تونیم از روابط زیر استفاده کنیم.
برای اینکه تخمین دقیقی داشته باشیم و در کل بتونیم برای تابع چگالی احتمال تخمین بهتری پیدا کنیم نیاز هست که یک سری شرط برقرار باشه که تو اسلاید پایین آورده شده.
ناحیه حول هر نقطه رو خودمون باید تنظیم کنیم. دو راه برای این کار داریم:
اول با توضیح راه حل دوم شروع می‌کنیم.
حول هر نقطه یک همسایگی ثابت در نظر می‌گیریم و می‌خواهیم ببینیم چند نقطه در اون همسایگی افتاده. تا اینجا تخمینی که برای n سمپل در نقطه x به‌دست آوردیم، برابر شد با kn تقسیم بر حجم ناحیه که تو این دیدگاه ثابت در نظر گرفته میشه. یک تابع پنجره داریم که به ازای عرض 1 حول نقطه 0 مقدارش 1 میشه و تو بقیه نقاط برابر با 0 هست. تو حالت d بعدی هم همینطور هست. یعنی دقیقا شبیه یک پنجره است. مقدار kn داره بهمون تعداد سمپل‌هایی رو نشون میده که داخل پنجره افتادن که طریقه محاسبه‌ش پایین آورده شده.
تو حالت کلی می‌تونیم تابع پنجره رو هرچیزی در نظر بگیریم با شرایطی که زیر گفته شده. مثلا می‌تونیم روی هر نقطه پنجره رو به صورت یک گاوسی در نظر بگیریم.
تو شکل زیر 13 تا سمپل داشتیم و روی هر کدوم یک گاوسی در نظر گرفتیم و باهم جمعشون کردیم. حالا می‌خوایم بررسی کنیم پارامتر پهنای پنجره چه اثری روی نتیجه داره؟ تو این مثال سیگما داره این پارامتر رو نشون میده.
تو حالت‌هایی که پهنای پنجره رو خیلی بزرگ در نظر گرفتیم و تابع زیادی هموار شده. یکمی جلوتر با جزییات بیشتری بررسی می‌کنیم.
چیزایی که تا اینجا دیدیم تو فضای یک بعدی بود. می‌تونیم همین کارو برای فضای دو بعدی هم انجام بدیم.
برای تحلیل جزئی تر پارامتر عرض پنجره فرض کنید تعداد کل نمونه‌هارو ثابت در نظر بگیریم. در این حالت عرض پنجره کوچیک منجر به واریانس خیلی زیادی میشه. واریانس اصلا چه معنی‌ای داشت؟ این بود که اگر داده آموزش رو تغییر بدیم، جواب‌ها خیلی متفاوت بشن. حالا چرا باعث میشه واریانس خیلی زیاد بشه؟ عکس زیر رو در نظر بگیرید. وقتی تو حالت دوم نمونه‌هارو تغییر دادیم باعث شده نسبت به حالت اول خیلی تغییر بکنه به این دلیل که عرض پنجره خیلی کوچیک بوده.
تو حالت دوم اگر عرض پنجره رو خیلی بزرگ در نظر بگیریم باعث میشه مقدار بایاس خیلی زیاد بشه و پیچیدگی مورد انتظار مارو پوشش نمیده.
پس به صورت کلی یک tradeoff داریم اینجا که با توجه به اون می‌تونیم تصمیم‌گیری کنیم.
یک مشکل اساسی وجود دارد و آن تعداد نقاطی است که در هر بعد باید تخمین بزنیم. فرض کنید در فضای یک بعدی نیاز به 10 نقطه در هر بازه برای تخمین داشته باشیم. وقتی فضا دو بعدی می‌شود تعداد نقاط 100 تا شده و وقتی به فضای سه بعدی می‌رویم تعداد نقاط به 1000 تا افزایش میابد. پس در فضای d بعدی تعداد نقاطی که در هر بازه نیاز به تخمین دارد تعدادش 10 به‌توان d خواهد بود. این مشکل قبلا هم وجود داشت اما در اینجا خیلی حاد تر رخ می‌دهد.
تا اینجا یکی از روش‌ها رو بررسی کردیم. اینجوری بود که رو هر نقطه یک پنجره در نظر می‌گرفت. همه رو باهم جمع می‌کرد. در نهایت تقسیم بر n و تقسیم بر حجم می‌کرد تا تابع چگالی احتما رو تخمین بزنه. از اینجا به بعد سراغ روش دوم می‌ریم.
روش دوم به این صورته که حجم همسایگی رو ثابت در نظر نگیریم و انقدر بزرگش کنیم که k تا نقطه تو اون همسایگی بیفته. سایز همسایگی اینجا بستگی داره به چگالی نقاط اطراف اون نقطه. اگر چگالی نقاط زیاد باشه همسایگی کم میشه و برعکس.
در این حالت باز یک سری شروط لازم و کافی داریم که تو اسلاید پایین آورده شده.
با یک مثال بقیه موارد رو بررسی خواهیم کرد. فرض کنید تابع واقعی چگالی احتمال رو با رنگ سبز تو نمودارهای زیر نمایش دادیم. یک سری سمپل بعنوان نمونه در نظر گرفتیم و می‌خوایم با روش knn تخمین چگالی رو انجام بدیم. اثر k اینجا یه‌جورایی شبیه به همون پارامتر عرض پنجره تو روش قبلیه.
تغییرات ناگهانی که به وجود میاد بخاطر چیه؟ به این دلیل هست که مثلا تو حالتی که k=5 در نظر گرفته شده، 5 تا نقطه همسایگی همه‌ش در حال تغییر هستن و این تغییر به صورت پیوسته رخ نمیده و فاصله‌ها متفاوته.
از مزایاش میشه به این اشاره کرد که هیچ فرضی روی توزیع نداریم و می‌تونیم هر توزیع پیچیده‌ای رو به کمکش مدل کنیم. از معایبش رشد تعداد نمونه‌هاست که با زیاد شدن ابعاد به صورت نمایی رشد میکنه. به پارامتر پهنای پنجره خیلی حساسه. برای به‌دست آوردن تخمین تو هر نقطه نیاز داریم که همه نمونه‌ها رو داشته باشیم و جاشون رو بدونیم. زمانی که تعداد داده‌ها زیاد باشه، زمان زیادی رو باید صرفش کنیم که خوب نیست.
یک سری داده آموزش در اختیار داریم و می‌خواهیم یک تابع تخمین بزنیم که از تمامی داده‌های آموزش هست. روشی که برای حل مسئله در نظر گرفتیم نگاه generative هست که در جلسات گذشته در موردش مفصل توضیح دادیم.
رابطه پایین که به رنگ قرمز نوشته شده داره چی رو نشون میده؟ داره میگه من میام یه همسایگی رو در نظر می‌گیرم، داده‌های مثبت و منفی رو توش می‌شمرم. اگه تعداد داده‌های مثبت بیشتر از منفی بود، کلاس C1 رو به اون‌جا اختصاص میدم. در غیر این صورت کلاس C2 بهش اختصاص داده میشه.
شکل پایین دو عرض مختلف پنجره رو نشون داده. در حالتی که عرض پنجره کوچیک‌تر در نظر گرفته شده داده‌ها خیلی خوب جدا شدن و خطای آموزش 0 هست. ولی خب به‌صورت خیلی پیچیده‌ای داده‌ها رو از هم جدا کرده.
حالا اگه از کرنل برای تخمین چگالی استفاده کنیم به روابط زیر می‌رسیم که با استفاده از قانون bayes و مواردی که تو جلسات قبل دیدیم، قابل حل هست.
روش دومی که می‌تونیم ازش برای حل مسئله و دسته‌بندی استفاده کنیم دیدگاه discriminative هست. این دیدگاه رو هم در جلسات قبلی در موردش توضیح دادیم. اینجوری بود که میومدیم مستقیم مقدار posterior رو روی هر کلاس حساب می‌کردیم، بعد داده رو به کلاسی که میزان posterior واسش حداکثر هست انتساب بدیم. به این روش اینجا کرنل گفته میشه (تشابه اسمی داره با روش کرنلی که بالاتر گفتیم).
حالا روش اینطوره که حول هر نقطه یک همسایگی در نظر می‌گیره و سعی میکنه اونقدر همسایگی رو بزرگ کنه که k تا نمونه تو اون همسایگی بیفته، بعد از روی برچسب همسایه‌ها برچسب اون داده رو مشخص میکنه.
این روش هیچ چیزی برای train نداره. هر نمونه‌ای میاد همون لحظه در موردش تصمیم‌گیری میشه. حالا ایرادش چیه؟ یک اینکه موقع تست لازمه به ازای هر تست فاصله رو حساب کنیم و زمان زیادی می‌خواد. دو هم اینکه مرزی بهمون میده ممکنه خیلی پیچیده باشه (یکم جلوتر توضیح داده شده که یعنی چی).
خلاصه روشی که دیدیم تا اینجا تو اسلاید پایین آورده شده.
تو تصویر زیر فرض کنید مقدار k رو 1 در نظر گرفتیم و می‌خوایم مرز رو توش بررسی کنیم. ناحیه نزدیک به هر نمونه هم مشخص شده. همونطور که تو تصویر هم مشخصه مرزی که به دست اومده خیلی پیچیده‌ست. از طرفی مقدار VC تو این مثال خیلی زیاده پس به این معنی هست که با نمونه‌های محدود به جواب درستی نمی‌رسیم.
برای روش کرنل 3 تا شکل مختلف تو تصویر پایین آورده شده با مقدار k متفاوت. لزوما با زیاد کردن k دسته‌بند خوبی نخواهیم داشت.
وقتی تعداد نمونه‌ها بی‌نهایت باشه، خطای 1NN از خطای bayes بیشتر میشه و از دو برابر خطای bayes کمتر.
به صورت کلی برای KNN خطایی که به‌دست میاد بهتره. اما در حالتی هست که تعداد نمونه‌ها خیلی زیاد باشه که گاهی اوقات عملا غیر ممکنه.
تو روش KNN از همسایگی استفاده کردیم. معیار همسایگی اینجا چیه اصلا؟ مثلا اینجا فاصله اقلیدسی در نظر گرفتیم اما می‌تونه چیزهای دیگه هم باشه. تعداد همسایه‌هارو چقدر در نظر بگیریم؟ با cross validation می‌تونیم تعیین کنیم. یه دیدگاه دیگه هم وجود داره با عنوان وزن‌دار کردن همسایه‌ها که جلوتر در موردش توضیح میدیم.
معیاری که برای فاصله در نظر گرفتیم اینجا فاصله اقلیدسی هست. می‌تونیم از معیارهای دیگه‌ای استفاده کنیم. مثلا وزن رو هم بهش اضافه کنیم. یا حالت دیگه‌ای وجود داره که می‌تونیم یک ماتریس رو ضرب کنیم در فاصله اقلیدسی.
بعنوان یک مثال مورد زیر رو بررسی کنیم.
فرض کنید به‌جای فاصله اقلیدسی، فاصله‌ای رو در نظر گرفتیم که در ترم دومش عدد 3 رو ضرب شده بعنوان یک وزن. باعث شده مرزهایی که به دست اومدن خیلی متفاوت بشن.
به این صورت در نظر بگیریم که اون نقاطی که در همسایگی میفتن، اگر نزدیک‌تر باشن اثر بیشتری داشته باشن تا نقاطی که دورتر هستن در همون همسایگی. گاهی تو این دیدگاه حتی گفته میشه که اصلا همسایگی در نظر گرفته نشه. چرا در این صورت هم باز استدلال درستی هست؟ چون نقاط نزدیک به نقطه مورد نظر اثر بیشتری دارند و نقاطی که دور هستند تاثیر زیادی نمی‌گذارند.
تابع وزن رو می‌تونیم موارد مختلفی در نظر بگیریم.
ساده‌ترین حالتی که میشه برای این حالت در نظر گرفت این هست که تعداد k تا از نزدیک‌ترین همسایه‌هارو در نظر بگیریم و روی مقدار y آن‌ها میانگین بگیریم. تو این حالت اگر مقدار k رو یک در نظر بگیریم تابعی که به دست میاد حالت پله‌ای پیدا میکنه.
برای حل مشکل پله‌ای شدن تابع می‌تونیم مقدار k رو بزرگ‌تر در نظر بگیریم. منتها مشکلی که تو این حالت به‌وجود میاد این هست که ابتدا و انتهای بازه‌هارو اشتباه دسته‌بندی میکنه.
اگه بخوایم توابع به‌دست اومده کمی هموارتر بشه چی کار می‌تونیم کنیم؟ می‌تونیم از وزن‌دار کردن کمک بگیریم. هرچی نقاط نزدیک‌تر اهمیتشون بیشتر و هرچی دورتر اهمیتشون کمتر.
نتیجه‌ای که با وزن‌دار کردن بهش می‌رسیم تو تصویر زیر آورده شده.
این روشی که برای رگرسیون ارائه شد خیلی روش مرسومی نیست. یک روش جایگزین براش وجود داره که در جلسه بعدی بررسی خواهیم کرد.
در مورد چگونگی محاسبه تابع چگالی احتمال با دیدگاه یادگیری مبتنی بر نمونه صحبت کردیم و دیدیم که چطور میشه این کار رو انجام داد. به این صورت بود که در هر نقطه یک پنجره در نظر بگیریم و در نهایت جمع کنیم و تقسیم بر تعداد کل داده‌های آموزش کنیم. در ادامه برای اینکه انتگرال تابع چگالی احتمال برابر با 1 بشه چیزی که به دست آوردیم رو تقسیم بر حجم می‌کردیم. مسئله کلسیفیکیشن و دسته‌بندی رو تو این حالت (یادگیری مبتنی بر نمونه) بررسی کردیم. کلیات رگرسیون در این حالت رو هم دیدیم که جزییاتش رو در جلسه بعدی بررسی خواهیم کرد.
اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.
