سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.
در ابتدا ادامه روش‌های یادگیری جمعی رو خواهیم دید و بعد راجع به انتخاب ویژگی صحبت خواهیم کرد.
در مورد یادگیری جمعی صحبت کردیم. ایده کلی به این صورت بود که به جای اینکه فقط یک دسته‌بند داشته باشیم تعدادی دسته‌بند همزمان داشته باشیم که باهم یادگیری رو انجام بدن. دو دیدگاه مختلف Bagging و Boosting داشتیم.
دیدگاه Bagging اینطور بود که سعی میکرد دسته‌بندهای پیچیده رو از یک جنس باهم ترکیب کنه. مثلا چند تا درخت تصمیم رو باهم ترکیب میکرد و دیتارو به صورت رندوم به هر کدوم از این دسته‌بندها اختصاص میداد و در نهایت بینشون رای‌گیری میکرد. نتیجه Bagging این بود که واریانس رو کم میکرد و باعث میشد تعمیم‌پذیری بهتری داشته باشیم.
دیدگاه Boosting به این صورت بود که میومد با دسته‌بندهای ضعیف و ساده‌تر شروع میکرد و هدفش این بود که اونارو تقویت کنه. یکی از الگوریتم‌هایی هم که ازش دیدیم AdaBoost بود. ایده کلی‌ش این بود که میگفت تو هر مرحله میام خطای دسته‌بندهای قبلی رو سعی می‌کنم بهبود بدم و همینطور الی آخر.
در جلسه قبل همچنین جزییات مرحله به مرحله الگوریتم AdaBoost رو بررسی کردیم. آخرین چیزی که ازش موند بررسی روابط مربوط به وزن‌ها بود که تو این جلسه از همونجا مطلب رو ادامه میدیم.
در این الگوریتم رابطه‌ای برای آپدیت کردن وزن‌ها داشتیم که به صورت زیر به‌دست میومد. هدف اینکه ببینیم این رابطه از کجا اومده.
اول اینکه تو جلسات قبلی و روابط قبلی دیدیم که مفهوم وزن از رابطه زیر اومد. یعنی اومدیم اون ضریب رو بعنوان وزن در نظر گرفتیم.
حالا در قدم بعدی فرض کنید میایم H رو باز می‌کنیم و بر اساس تعریفی که از H کرده بودیم فرمول وزن رو دوباره می‌نویسیم.
از ترکیب این دو رابطه می‌تونیم به تعریف زیر برای وزن برسیم:
به این صورته که هر دور از یک توزیع نقاط رو در میاره بعد سعی میکنه که h رو به صورتی پیدا کنه که حداقل خطای آموزش رو داره. استپ‌های الگوریتم شبیه همون حالت قبلی هست فقط در هر مرحله توزیع (D) رو داره آپدیت میکنه. انگار اینطوره که تو هر مرحله داریم توزیع رو تغییر میدیم و آپدیت می‌کنیم که در نهایت باعث بشه کمترین میزان خطارو داشته باشیم.
دسته‌بندی در این مثال روی نویز داده‌ها کمی بیشتر حساس است.در هر تصویر آخرین دسته‌بندی که به‌دست اومده با رنگ سبز نشون داده شده. تو مرحله آخر آخرین دسته‌بندی که به دست اومده با خط‌چین سیاه مشخص شده. یه مشکلی که اینجا هست اینکه داده‌ای که داشتیم نویزی بوده، هر دفعه این نویزها وزن بهشون اضافه شده و همین باعث شده تعداد دسته‌بندها زیاد بشه و سعی کنه تمام این نویزهارو پوشش بده و نهایتا دچار overfitting شده.
دسته‌بند پایه‌ای که برای AdaBoost در نظر گرفته میشه می‌تونه هرچیزی باشه. یک درخت با عمق خیلی محدود یا حتی یک شبکه عصبی. نکته‌ای که وجود داره اینکه چطور اون دسته‌بند پایه رو تو مرحله learn کنیم. چون داده‌ها اینجا هر کدومشون یک وزنی دارن که تو حالت عادی این دسته‌بندها این وزن رو ندارن. یکی از راه‌ها برای دخیل کردن این وزن می‌تونه این باشه که بیایم مثلا موقع استفاده از درخت تصمیم برای محاسبه Information Gain وزن رو دخیل کنیم. یکی دیگه از راه‌ها هم نمونه‌برداری هست. اینجوره که هر داده‌ای وزن بیشتری داره نمونه بیشتری ازش برمی‌داریم.
تابع هزینه به صورت کلی در هر مرحله کم و کمتر میشه با توجه به اینکه دنبال پیدا کردن H و alpha بهینه هستیم. در ادامه می‌خوایم ببینیم با زیاد شدن تعداد راندها برای e و خطای آموزش چه اتفاقی میفته.
نمودار زیر، داره نمودار تابع هزینه رو که دنبال کم کردنش بودیم نشون میده بهمون.
در مورد خطای داده آموزش، به صورت کلی با زیاد شدن m کم میشه ولی ممکنه جاهایی باشه که هر از گاهی زیاد بشه. مثلا به خاطر وجود نویزها ممکنه این اتفاق بیفته.
همچنین یک حد بالا برای خطای آموزش وجود داره که فقط در اسلاید پایین بهش اشاره میشه.
خطای اپسیلون (e) در هر مرحله به صورت کلی داره افزایش پیدا میکنه. چرا؟ داده‌هایی که اشتباه دسته‌بندی شدن خیلی وزنشون زیاد شده برای همین هم در کل مقدار اپسیلون زیاد شده. حالا وقتی e زیاد میشه باعث میشه مقدار alpha کم و کمتر بشه.
تو این الگوریتم با زیاد شدن تعداد مراحل، در اکثر مواقع overfitting رخ نخواهد داد. اگر نگران overfitting هم بودیم می‌تونیم با تکنیک cross validation مشخص کنیم که این الگوریتم از یه جایی دیگه بیشتر جلوتر نره و متوقف بشه.
در نمودار زیر اتفاق جالبی افتاده. از یک جایی به بعد خطای آموزش 0 شده ولی با این حال در هر مرحله داره خطا روی داده تست هم کم میشه. ما همیشه فکر می‌کنیم با 0 شدن خطای آموزش ممکنه دچار overfitting بشیم و خطای تست بره بالا ولی اینجا داره میره پایین. چرا؟ اگه نمودار تابع هزینه رو به یاد بیارید به صورت نمایی داشت کم میشد. یعنی برای داده‌هایی هم که به صورت درست دسته‌بندی شده بودن انگار یه میزان خطایی رو در نظر گرفته بود. این باعث میشه که داده‌های درست دسته‌بندی شده به مرور از مرز دور و دورتر بشن. به عبارتی دیگه، یعنی margin براشون در نظر بگیره. این قضیه باعث میشه که اتفاق زیر بیفته.
یه جمع‌بندی کلی کنیم ویژگی‌های مهمی رو که تا اینجا دیدیم. همون‌طور که بالاتر هم گفتیم، overfitting در Boosting به صورت کلی خیلی کم اتفاق میفته. از طرفی دیگه حتی با صفر شدن خطای آموزش همچنان خطای تست می‌تونست کم و کمتر بشه.
یک حدی برای خطا اوایل در نظر گرفته بودن که خیلی حد بالای خوبی نبود. T تعداد راندهای الگوریتم رو نشون میده. d مقدار VC دسته‌بند پایه رو نشون میده (هرچی VC بیشتر فاصله بین نمونه‌ها در دسته‌بندها بیشتر) و تعداد نمونه‌ها که در مخرج آورده شده (هرچی تعداد نمونه‌ها بیشتر بشه باعث میشه نمونه‌های دو کلاس بیشتر بهم نزدیک بشن برای همین تو مخرج آورده شده).
حالا چرا باند خوبی نیست این چیزی که به‌دست اومده؟ چون T ظاهر شده توش و به صورت کلی و با زیاد کردن تعداد راندها فاصله نمونه‌ها در کلاس‌ها از هم زیاد نمیشه.
بعدها حد بالای دیگه‌ای براش به دست آوردن که بهتر بود و ایرادات حد بالای قبلی رو نداشت و به موضوع margin که بالاتر در موردش توضیح دادیم اشاره شده بود.
اول اینکه اومدن مقدار H رو تقسیم بر جمع مقادیر آلفاها کردن. این کار تاثیری در دسته‌بندی نخواهد داشت. بعد اومدین تعریفی رو برای margin به صورت زیر ارائه دادن.
به صورت کلی محدوده H بین -1 تا +1 هست. چرا؟ به این دلیل که مقادیر h می‌تونن +1 یا -1 بشن. وقتی همشون +1 بشن، مقدار H هم +1 میشه و اگر همشون -1 بشن مقدار H برابر با -1 میشه (چون تقسیم میشه). در حالتی هم که این مقادیر تعدادشون مشخص نباشه که چند تا -1 و +1 هستن مقدار H بین این دو تا عدد میشه.
از طرفی مقدار y هم یا +1 هست یا -1. حالا به صورت کلی ضرب y در H بهمون چی رو نشون میده؟ اگه داده به کلاس مثبت باشه و مقدار H توش زیاد بشه به این معنیه که margin بیشتری داره و برعکس.
تو مثال زیر اومده مقدار مارجین رو به ازای سمپل‌های مختلف کشیده. به این صورت که چه تعداد از سمپل‌ها، مارجین کمتر از یه مقداری رو دارن. حالا margin منفی چی رو نشون میده؟ اینکه جقدر اشتباه دسته‌بندی شده. به ترتیب با زیاد کردن تعداد iteration ها تعداد margin های منفی کم و کمتر میشه. این به این معنیه که با زیاد شدن تعداد راندها داده‌ها دارن بهتر دسته‌بندی میشن و همچنین margin توشون افزایش پیدا میکنه.
حد بالای دومی که به‌دست اومد در اسلاید زیر آورده شده. تنها نکته‌ای که وجود داره اینکه دیگه تعداد راندها تو این فرمول وجود نداره و از بین رفته.
بحث مرتبط با دسته‌بندهای جمعی و الگوریتم AdaBoost اینجا به پایان میرسه و وارد بحث انتخاب ویژگی میشیم.
تا به حال برای بحث هندل کردن overfitting روش‌های مختلفی رو دیدیم. یکی دیگه از این روش‌ها برای این کار، کاهش فضای ابعاد ورودی هست.
یک دسته از راه‌هایی که برای کاهش overfitting تا اینجا داشتیم راه‌های تئوری بودن. یک دسته راه‌های دیگه به صورت غیر تئوری بودن. آخرین چیزی که می‌خوایم در موردش بحث کنیم، کاهش فضای ورودی هست.
برای کاهش ابعاد فضای ورودی دو راه مختلف داریم:
پس مسئله به این صورت شد که اگر یک داده داریم و جدول‌ها نشون دهنده تعداد فیچرها هستن، فقط تعدادی از ستون‌ها رو در نظر می‌گیریم و با بقیه فیچرها کاری نداریم.
چرا این روش مفیده؟ پیچیدگی فضا رو کم میکنه به صورت کلی بعد فضا کم میشه. از طرفی دیگه بحث تعمیم‌پذیری با کم کردن تعداد ویژگی‌ها می‌تونه کنترل بشه. مورد دیگه هم اینکه سرعت افزایش پیدا میکنه و فضا با تعداد ابعاد کمتر خیلی بیشتر قابل درک هست تا یک فضای پیچیده با تعداد قابل توجهی بعد.
مثال SVM رو در نظر بگیریم که نویز یا فیچرهای غیر مرتبط چه تاثیری می‌تونه روش داشته باشه. فرض کنید تو حالت اول (شکل سمت چپ) داده‌ها رو با از طریق یک ویژگی با اون مرز قرمز رنگ از هم جدا کردیم. حالا یک ویژگی رندوم که هیچ رابطه‌ای با نمونه‌ها نداره اضافه می‌کنیم و تبدیل میشه به نمودار سمت راست. همون‌طور که مشخصه، اضافه کردن این فیچر باعث شد که دسته‌بند و مرز به طور کلی تغییر کنه و بهم بریزه. پس حذف کردن این ویژگی می‌تونه به بهبود دسته‌بندی کمک کنه.
حالا چه معیاری برای انتخاب ویژگی‌ها وجود داره؟ به چه صورت قراره این کار رو انجام بدیم؟ در ادامه یک سری از این معیارهارو بررسی خواهیم کرد.
این معیار نشون میده که یک ویژگی به صورت تکی، چقدر برای دسته‌بندی مناسب هست. آیا صرفا با همین معیار می‌تونیم ویژگی‌های خوب رو برداریم؟ اصلا چه ایرادی داره این کار؟ چون به صورت تکی داره در نظر گرفته میشه خیلی جالب نیست.
این معیار به این صورته که رابطه تک تک فیچرهارو با target بررسی میکنه. مقدار correlation یک عدد همواره بین +1 تا -1 هست. اگر 0 بشه به این معنی هست که هیچ رابطه خطی‌ای بین داده‌ها وجود نداره. اگر مقدارش +1 بشه یعنی به صورت خطی با شیب مثبت داده‌ها با هم ارتباط دارن و اگر -1 بشه یعنی این ارتباط و شیب خط به صورت منفی هست.
این معیار زمانی که بین ویژگی‌ها با target رابطه غیر خطی وجود داره (مثلا یک سهمی) اصلا به خوبی جواب نمیده و نمی‌تونه این رابطه رو برامون مشخص کنه. پس باعث میشه یک سری فیچرهای خوب غیر خطی رو از دست بدیم و به همین دلیل خیلی نمی‌تونه خوب باشه.
این معیار نشون میده که چقدر X و Y از هم مستقل نیستن (در واقع، نسبت بهم وابسته هستند). هر چقدر اینا نسبت بهم بیشتر استقلال نداشته باشن (وابستگی بیشتری داشته باشن) X اطلاعات بیشتری از Y در اختیار ما قرار میده. تو رابطه زیر وقتی حالتی پیش میاد که X و Y نسبت بهم مستقل میشن، مقدارش 0 میشه و وقتی که استقلال ندارن نسبت بهم (بهم وابسته هستن) مقادیر بزرگ و بزرگ‌تر میشه براشون. مشکل correlation هم اینجا حل میشه و روباط غیر خطی هم قابل تشخیص خواهند بود.
یک مثال از این معیار رو بررسی کنیم. دو ویژگی X1 , X2 رو در نظر بگیرید. هیستوگرام هر کدوم از این ویژگی‌ها بر اساس Y تو نمودارهای پایین رسم شده. کدوم یکی از فیچرها بهتره؟ X2. چرا؟ چون مقدار Mutual Information توش بیشتر میشه.
تو اسلاید زیر دلیل اینکه چرا X1 نمی‌تونه فیچر خوبی باشه رو آورده.
اولین دلیل به این برمی‌گرده که اگر فرضا دو تا ویژگی داشته باشیم که یکیشون یک رابطه خطی با target داشته باشه و یک ویژگی دیگه مثلا ضریبی از ویژگی اول باشه (یعنی این ویژگی دوم هم همون رابطه خطی رو با target با یک ضریب متفاوت داره) به هیچ عنوان قابل تشخیص نیست. یعنی ویژگی‌هایی که از روی هم دیگه به دست میان و با هم یه جورایی correlation دارن تو این حالت قابل تشخیص نیستن. چون داریم تکی تکی هر ویژگی رو با target می‌سنجیم. یه جورایی داره ویژگی اضافه هم انتخاب میشه در حالی که دلمون نمی‌خواد این اتفاق بیفته.
دومین دلیل به این برمی‌گرده که ممکنه هر کدوم از ویژگی‌ها به صورت تکی خیلی تاثیری نداشته باشن، ولی وقتی در کنار هم دیگه قرار می‌گیرن ممکنه تاثیرشون خیلی بیشتر بشه.
مثال زیر رو در نظر بگیرید. وقتی صرفا داده‌هارو روی نمودار X1 یا نمودار X2 به صورت تکی در نظر می‌گیریم اصلا قابل جدا شدن نیستن. ولی وقتی هر دو ویژگی رو باهم داریم به خوبی با یک خط از هم جدا میشن (سمت چپ). نمودار سمت راست هم داره همین موضوع رو نشون میده.
حالا چجوری این ویژگی‌های خوب رو باید در بیاریم؟ خیلی پیچیده‌س اگر قرار باشه دو به دو یا چند به چند ویژگی‌هارو باهم در نظر بگیریم. ولی یک سری معیار چند متغیره وجود داره که بهمون این فیچرهای کاندید رو میده.
فرض کنید به طریقی فیچرهای کاندید رو داریم و می‌خوایم بینشون انتخاب کنیم و بهترین‌هاشو نگه داریم. به معیارهایی مثل Mutual Information که بالاتر دیدیم، Multi-variate filter هم گفته میشه. یک روش اینکه از این معیارها استفاده کنیم.
روش دوم اینکه هیچ معیاری نداشته باشیم. مستقیما مجموعه کاندیداها رو چک کنیم و ببینیم که کدوم فیچرها خوبن (با train کردن با اون ویژگی‌ها). به این روش‌ها به اصطلاح Wrapper گفته میشه. حالا اشکال این روش‌های wrapper چی می‌تونه باشه؟ از نظر زمانی خیلی وقت‌گیره که بخوایم به ازای فیچرهای مختلف هر دفعه train کنیم و بررسی کنیم چقدر ویژگی‌ها خوب بوده یا بد بوده.
تا اینجا دو روش مختلف برای ارزیابی خوب بودن فیچرهای کاندید دیدیم.
حالا اگه 4 تا ویژگی داشته باشیم و بخوایم بین این فیچرها انتخاب کنیم، فضایی که داریم به صورت زیر در میاد. می‌خوایم این مسئله رو بعنوان یک مسئله جستجو در نظر بگیریم و سعی کنیم بهترین جستجو رو انجام بدیم. یک سری از این روش‌ها به صورت کاملا حریصانه هستن. یک سری دیگه از روش‌ها کمتر حریصانه هستن.
بقیه این موضوع رو در جلسه بعدی دنبال خواهیم کرد.
تو بحث اول دو دیدگاه Bagging و Boosting رو دیدیم. برای Boosting الگوریتم AdaBoost رو معرفی کردیم. دیدیم که معادل میشه با بهینه کردن یک تابع هزینه. در عین حال که یک دسته‌بند پیچیده رو داشت یاد می‌گرفت اما تا حد خوبی نسبت به overfitting مقاوم بود.
در بخش انتخاب ویژگی حالت‌ها و معیارهای مختلف رو بررسی کردیم. در نهایت به این نتیجه رسیدیم که با دو روش مختلف یا به صورت Multi-variant filter و استفاده از جستجو، یا به روش wrapper و ارزیابی فیچرها به این نتیجه برسیم که کدوم ویژگی‌هارو در نظر بگیریم.
اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.
اسلایدهای این جلسه (بخش یادگیری جمعی)
