سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.
اول ادامه بحث یادگیری مبتنی بر نمونه رو داریم بعدش هم در مورد یادگیری جمعی (Bagging و Boosting) صحبت می‌کنیم.
پایه روش‌های غیر پارامتریک به این صورت بود که حول هر نقطه x یک همسایگی در نظر می‌گرفتیم بعد اگه احتمال افتادن یک نقطه در این همسایگی رو P در نظر بگیریم p(x) برابر می‌شد با:
p(x) = (k / n) / V
P = p(x) × V
همینطور دیدیم که توزیع اینکه k نمونه از n نمونه داخل محدوده مورد نظرمون بیفته یک توزیع binominal میشه. بعلاوه، تو روش‌های غیر پارامتریک هر دو دیدگاه generative و discriminative تقریبا یکی هستن و هر دو هم خیلی پیچیده‌ن. برای همین دیگه خیلی روش مانور نمیدن.
در آخر جلسه گذشته مبحث به اینجا رسید که می‌خواستیم از روش‌های غیر پارامتریک برای مسئله رگرسیون استفاده کنیم. اولین ایده ساده‌ای که داشتیم این بود که به ازای هر نقطه k تا نزدیک‌ترین همسایه رو براش پیدا کنیم، مقدار y رو اونجا برای اون نقاط ببینیم و در نهایت ازشون میانگین بگیریم. منطقا وقتی مقدار k زیادتر میشه نویزی که حول نقاط وجود داره تاثیرش کمتر میشه.
می‌تونستیم این روش رو به صورت وزن‌دار هم انجام بدیم. نقاط هرچی نزدیک‌تر، وزنشون بیشتر.
ولی همچنان با این روش هم مشکل نقاط ابتدا و انتهای بازه وجود داره.
در ادامه روش‌های دیگه‌ای رو برای مسئله رگرسیون KNN بررسی می‌کنیم.
اگر روند رشد یا نزول رو در داده‌ها درست مشخص مشخص کنیم، می‌تونیم در مورد داده‌های اول و آخر بازه هم تصمیم‌گیری درستی داشته باشیم. قراره برای هر داده مثل x یک مسئله رگرسیون خطی حل کنیم. برای هر نقطه همسایه‌هاشو در نظر می‌گیریم. یعنی می‌خوایم به ازای همسایه‌ها یک خط پیدا کنیم که به خوبی نقاط همسایه رو پوشش بده. انگار به صورت محلی می‌خوایم رگرسیون خطی انجام بدیم. محلی بودنش به این دلیله که صرفا داره روی همسایه‌های هر نقطه اعمال میشه. اگر این کار رو انجام بدیم انگار به ازای هر نقطه از فضا داریم یک مسئله رگرسیون خطی حل می‌کنیم. برای تخمین مقدار y در هر نقطه، باید نزدیک‌ترین نقاط رو بهش پیدا کنیم مسئله رگرسیون رو براش حل کنیم و بردار w رو براش حساب کنیم بعد با رابطه y = wx مقدار y رو تخمین بزنیم.
از طرفی نموداری هم که بهش خواهیم رسید یک نمودار خطی میشه. یعنی یک سری خط هستن که پیوسته پشت سر هم با شیب‌های مختلف قرار گرفتن.
حالا اگه همین مسئله رو به‌صورت وزن‌دار در نظر بگیریم، خروجی نهایی دیگه به این صورت خط شکسته نمیشه. چون اومدیم بر اساس دوری یا نزدیکی نقاط یک وزنی رو حساب کردیم. تابع کرنلی که پایین اومده، دوری و نزدیکی نقاط رو مشخص میکنه. در واقع همون وزن هست. (شباهت رو مشخص میکنه، هرچقدر شبیه‌تر نزدیک‌تر و وزن بیشتر)
همونطور که تو نمودارهای زیر هم مشخصه، دیگه مشکل اول و آخر بازه رو تو این روش نداریم.
نکته مثبت این روش اینکه برای هر مدل تابعی این روش جواب میده. نکته منفی‌ای که داره اینکه محاسبات خیلی زیاد میشه. به ازای هر نقطه باید بریم رگرسیون حساب کنیم. از طرفی دیگه مشکل overfitting خواهیم. داشت اگر تعداد نمونه‌ها کم باشه، باید سمپل‌های آموزش خیلی زیاد باشه تا جواب خوبی بگیریم.
جواب‌هایی که این روش بهمون میده لزوما خطی نیستن می‌تونن غیر خطی هم باشن.
آیا یک روشی مثل SVM که قبلا بررسیش کردیم، می‌تونه غیر پارامتریک باشه؟ خیر چون فاز لرنینگ داریم و بعد آموزش، پارامترها پیدا میشن.
عملا این روش‌ها هیچ فاز لرنینگ و یادگیری‌ای ندارن. یعنی فقط نمونه‌های آموزش رو در جایی نگه می‌دارن. کل کاری که انجام میدن بعد از اومدن داده جدید هست. پارامتری برای یادگیری ندارن و فقط از روی نمونه‌ها به‌دست میان. همچنین خیلی کند هستن.
از اولین جلسه تا به اینجا در مورد دستهبندهای مختلف صحبت کردیم. روش‌های SVM و کرنل و درخت تصمیم رو دیدیم. در نهایت هم به یادگیری مبتنی بر نمونه رسیدیم. این جلسه می‌خواهیم در مورد ترکیب دسته‌بندها و رگرسورها صحبت کنیم که بهشون Ensemble Learning (یادگیری جمعی) گفته میشه.
فرض کنید یک سری داده داریم و براشون دستهبندهای مختلف رو به‌دست آوردیم. حالا می‌خوایم از ترکیب این دسته‌بندها به یک جواب نهایی برسیم. تو حالتی که جنس دستهبندهای پایه یکی باشه بهش Ensemble گفته میشه و تو حالتی که جنسشون یکی نباشه Multiple Classifier بهش میگیم.
روش‌های Ensemble خودشون به دو دسته تقسیم میشن که بهشون Bagging و Boosting میگیم.
چرا اصلا سراغ این روش میایم؟
فرض کنید یک سری دسته‌بند ساده داشته باشیم. خواص این دستهبندهای ساده چی بود؟ بایاس زیاد و واریانس کم داشتن. یعنی تعمیم‌پذیری خوبی داشتن ولی دقت خوبی رو بهمون نمیدادن. واریانس کم داشتن نکته مثبتشون بود ولی از طرفی دقت کم یکی از نکات منفی‌شون بود.
برعکس، دستهبندهای پیچیده، واریانس زیاد و بایاس کم داشتن. یعنی رو داده آموزش بهمون دقت خوبی میدادن ولی تعمیم‌پذیری لزوما خوبی ممکن بود نداشته باشن.
حالا امروز می‌خواهیم دو تا دیدگاه مختلف رو ببینیم که اومده یه جورایی این دو تا دسته‌بند رو باهم ترکیب کرده و مشکلاتشون رو تا حدی حل کرده.
تو دیدگاه Bagging دنبال این هستیم که به صورت کلی واریانس رو کم کنیم. چطوری؟ اگر دستهبندهای پیچیده با واریانس بالا رو در نظر بگیریم، با استفاده از تکنیکی که جلوتر می‌بینیم، میایم داده آموزش رو به چند تا قسمت کوچیک‌تر می‌شکنیم، بعد جدا جدا اون‌هارو train می‌کنیم با روش‌های مختلف و در نهایت با میانگین‌گیری به دنبال کم کردن واریانس هستیم.
تو دیدگاه Boosting به دنبال این هستیم که بایاس بالای روش‌های ساده رو کم کنیم.
حالا فرض کنید درخت تصمیم رو بعنوان یک دسته‌بند پیچیده با واریانس بالا، بعنوان یک دسته‌بند پایه در نظر گرفتیم. داده آموزش مشخصی هم داریم. حالا چجوری می‌خوایم با یک داده آموزش و یک دسته‌بند، به دستهبندهای متفاوت برسیم که در نهایت از همشون میانگین بگیریم و استفاده کنیم و یک دسته‌بند کلی داشته باشیم؟ داده آموزشی که اینجا داریم یکمی متفاوت‌تر میشه. یعنی چی؟ بررسی می‌کنیم جلوتر.
اسم دیدگاه Bagging از مفهوم Bootstrap Aggregation در آمار گرفته شده. ببینیم اصلا یعنی چی این. فرض کنید یک دیتاست با N سمپل مختلف داریم، با جایگذاری میایم n تا سمپل مختلف ازش بر می‌داریم. منطقا یک سری نمونه‌ها ممکنه چند بار تکرار بشن و یک سری دیگه اصلا ظاهر نشن. انگار یه تاس رو چند بار بندازیم، یک سری اعداد اصلا نیان و یک سری از اعداد چندبار تکرار بشن. حالا فرض کنید این کار رو برای چند دسته مختلف انجام بدیم. دسته اول یک بار n داده رندوم. دسته دوم n داده رندوم دیگه و همینطور الی آخر. چون این داده‌ها تصادفی انتخاب میشن، داده‌های هر دسته با دسته دیگه متفاوته. حالا روی هر دسته یک بار درخت تصمیم رو اجرا می‌کنیم. حالا یک نمونه جدید میاد. چیکار باید کنیم؟ اگر مسئله کلسیفیکیشن باشه بین دسته‌ها رای می‌گیریم. اگر رگرسیون باشه بینشون میانگین می‌گیریم. این معادل با همون روش Bagging هست.
مسئله Bagging برخلاف ظاهر ساده‌ای که داره تئوری‌ش خیلی پیچیده‌ست.
تمام چیزایی که بالاتر توضیح دادیم تو اسلاید پایین در قالب ریاضی در اومده. چرا در نهایت داریم از تابع علامت استفاده می‌کنیم؟ برای رای‌گیری. خروجی یا مثبت 1 یا منفی 1 میشه.
یکی از دسته‌بندی‌هایی که Bagging روش خیلی خوب جواب میده درخت تصمیم هست. درخت تصمیم خیلی قابل تفسیره. به صورت یک جعبه بسته نیست و عملکردش کاملا مشخصه. البته جواب Bagging وقتی خیلی خوب میشه که هر کدوم از این دسته‌بندها باهم متفاوت باشن و دقت خوبی هم داشته باشن.
حالا چجوری این دسته‌بندهارو از هم متفاوت کنیم؟
یکی از کارهایی که میشه انجام داد همون انتخاب تصادفی سمپل‌هاست. یکی دیگه از کارها استفاده از ایده Random Forest هست. یعنی چجوری؟ یعنی اینجوری که بیایم ویژگی‌ها رو برای درخت‌هامون محدودتر کنیم. قرار بود تو Bagging از چند تا درخت تصمیم مختلف استفاده کنیم، به‌جای اینکه تمام attributeها رو به همه درخت‌ها بدیم، به هر درخت یک سری از attributeها رو بدیم که با اون یکی فرق کنه. چرا؟ چون اگه ویژگی همه درخت‌ها یکسان باشه با احتمال خوبی ویژگی‌های انتخاب شده برای هر درخت باهم یکی میشه، حتی ترتیبشون و این باعث میشه در نهایت درخت‌ها خیلی بهم شبیه بشن.
حالا این کار (محدود کردن ویژگی‌ها) ممکنه باعث بشه دقت کمتر بشه، چه کنیم؟ هدف از اینکه یک درخت ویژگی‌های خوبی رو انتخاب کنه این بود که باعث بشه عمقش کمتر شه. حالا اگه ما اجازه بدیم با ویژگی‌های محدودتر عمق بیشتری داشته باشه، دقت خیلی تحت تاثیر قرار نگیره و به حد خوبی باقی بمونه.
تا اینجا Bagging رو دیدیم. به این صورت بود که می‌خواستیم واریانس روش‌های پیچیده رو به کمکش کم کنیم و در نهایت از کلاس‌های ساخته شده میانگین بگیریم یا رای‌گیری کنیم. حالا ایده Boosting میگه که من میام دستهبندهای ضعیف رو بهبود میدم و ازشون دستهبندهای قوی‌تری می‌سازم.
دسته‌بند ضعیفی که تو این دیدگاه بعنوان مثال ازش استفاده خواهیم کرد Decision Stump هست. این دسته‌بند یک درخت تصمیم با یک نود هست. یعنی فقط ریشه داره. یعنی فقط یک ویژگی رو انتخاب میکنه و بر اساس اون میاد تصمیم می‌گیره حالا.
حالا فرض کنید یک مسئله دسته‌بندی داریم (نه رگرشن) و خروجی هر دسته بند مثبت یا منفی 1 هست. می‌خوایم یک دسته‌بندی کلی از روی تعدادی دستهبندهای پایه بسازیم که جنسشون یکیه. هر کدوم از این دسته‌بندها یک وزن خاصی دارن (برخلاف Bagging که وزن‌ها یکسان بود). حالا می‌خوایم مقادیر آلفا و تتا رو (که تو اسلاید پایین هم اومده) پیدا کنیم.
با روش Decision Stump شروع کنیم. از کل بردار X یکی از ویژگی‌هارو انتخاب میکنه و براش یک threshold در نظر می‌گیره. هدف اینکه بیایم یک سری از این دسته‌بندهارو باهم ترکیب کنیم و به یک دسته‌بند قوی برسیم.
معروف‌ترین الگوریتمی که برای Boosting وجود داره، اسمش AdaBoost هست. حالا چیکار میکنه؟ اول میاد یک دسته‌بند اولیه با یک وزن برامون می‌سازه. بعد میره سراغ بعدی‌ها و ویژگی‌های دیگه‌ای رو بهش اضافه میکنه. با این هدف که تو هر مرحله خطاهای مرحله قبلی پوشش داده بشه. حالا چجوری؟ هر دور برای هر نقطه یک وزن در نظر گرفته میشه. هرچی نقطه سخت‌تر باشه (یعنی نقاطی باشن که نتونسته باشه براشون دسته‌بندی انجام بده و دسته‌بندی برای اون نقاط سخت‌تر باشه) وزن بیشتری می‌گیره و این باعث میشه که اون نقطه بیشتر تو تابع هزینه ظاهر بشه.
حالا بریم با یک مثال ببینیم کلا چه اتفاقی میفته. فرض کنید دسته‌بند پایه‌مون Decision Stump هست و دیتاستی که داریم تو تصویر پایین آورده شده.
میاد اولین ویژگی رو انتخاب میکنه. سمت راست thresholdای رو که در نظر می‌گیره منفی و سمت چپش رو مثبت در نظر می‌گیره. اونایی که اشتباه دسته‌بندی میشن رو دورشون یک دایره می‌کشه. تو مرحله بعدی اون نمونه‌هایی که اشتباه دسته‌بندی میشن رو وزنشونو زیاد میکنه و انگار دیتاست دوم رو می‌سازه که عین همون اولیه‌ست ولی اون نقاطی که اشتباه دسته‌بندی شدن وزنشون بیشتر شده. تو مرحله اول همه نمونه‌ها رو داریم و وزن همشون هم یکسانه.
تو مرحله بعدی به شکل زیر میاد دسته‌بندی رو انجام میده و دوباره مراحل قبلی رو تکرار میکنه و دیتاست سوم رو می‌سازه.
کل سه مرحله تو تصویر زیر کنار هم اومدن.
حالا چجوری از روی این مراحل دسته‌بند نهایی رو بسازیم؟ از مقادیر آلفا استفاده میکنه و دسته‌بند رو به کمک اون می‌سازه.
حالا بریم سراغ الگوریتمش و ببینیم که به چه صورته. ممکنه در نگاه اول پیچیده باشه ولی در کل ساده است. راند هر مرحله با اندیس مشخص میشه و شماره داده به صورت بالانویس. در کل M تا کامپوننت اضافه می‌کنیم. هر دور یکی. در هر مرحله برای اضافه کردن هر کامپوننت چند تا کار انجام میده:
نوتیشن مواردی که تو الگوریتم بالا ازش استفاده شده اینجا بهش اشاره شده:
تو شروع الگوریتم وزنی که در نظر می‌گیریم همشون باهم برابر هستن و در نهایت موقع آپدیت کردن وزن‌ها، با توجه به اینکه داده‌ها اشتباه دسته بندی شدن یا درست، وزن رو زیاد می‌کنیم یا ثابت در نظر می‌گیریم.
حالا بریم سراغ تابع ضرر و ببینیم که چطور محاسبه میشه و چجوری باید بهینه‌ش کرد. فرض کنید دسته‌بند کلی‌ای که به‌دست میاد رو با H نشون بدیم. تابع ضرری که در گرفتیم به صورت نمایی هست. جاهایی که H مثبت بشه مقدار loss کم میشه و جاهایی که منفی بشه مقدارش زیاد میشه.
تابع loss ای که به صورت نمایی هست با رنگ قرمز تو نمودار پایین مشخص شده. در واقع بر خلاف loss function ساده‌ای که به ازای نمونه‌های غلطِ دسته‌بندی شده، صرفا یک واحد جریمه می‌کرد، این تابع میاد به ازای نمونه‌های غلط پنالتی خیلی بیشتری رو در نظر می‌گیره.
حالا تو اسلاید پایین روابط ریاضی مرتبط با loss function نوشته شده. برای H یک ضریب 1/2 در نظر گرفته شده که هیچ تاثیری در معادلات نداره فقط خواسته با این فرم بنویستش.
حالا می‌خوایم رابطه‌ای که تا اینجا برای loss function به‌دست آوردیم، شبیه همون رابطه‌ای بنویسیم که بالاتر تو الگوریتم دیدیم برای تابع هزینه. اول کار اومدیم رابطه بالا رو به صورت جمع دو جمله شکستیم. یک دسته اون نمونه‌هایی که دسته‌بند آخر داره درست دسته‌بندی‌شون میکنه (جمله اول) و یک دسته هم نمونه‌هایی که دسته‌بند آخر داره غلط دسته‌بندی‌شون میکنه (جمله دوم).
حالا تو مرحله بعدی هدفمون اینکه جمله اول رو از بین ببریم. برای این کار میایم عبارت زیر رو به E اضافه و کم می‌کنیم:
بعد از این کار به رابطه آخری که تو اسلاید بالا آورده شده می‌رسیم. حالا می‌خوایم رابطه‌ای که به‌دست اومده رو نسبت به h کمینه کنیم. چیزی که بهش می‌رسیم معادل با همون رابطه‌ای هست که تو الگوریتم بعنوان تابع هزینه دیدیم. یعنی دسته‌بندی رو انتخاب کن که جمع وزن‌دار خطاها توش حداقل بشه.
حالا بخش دوم الگوریتم و alpha رابطه‌ش از کجا میاد؟ (همون رابطه ارور وزن‌دار که تو مرحله دوم بود و مرحله سوم) میایم نسبت به آلفا از تابع هزینه‌ای که به‌دست اومد مشتق می‌گیریم و برابر با 0 قرار میدیم و بعد ازش لگاریتم می‌گیریم.
ادامه این مبحث موند که در جلسه بعدی بررسی خواهد شد.
روش Bagging و Boosting رو دیدیم که اولی سعی می‌کرد از کنار هم گذاشتن دستهبندهای پیچیده به یک دسته‌بند خوب برسه و دومی سعی بر این داشت که دستهبندهای ساده رو در کنار هم بهبود بده تا بهتر عمل کنن.
اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.
اسلایدهای این جلسه (بخش یادگیری مبتنی بر نمونه)
