سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.
تو این جلسه با دسته‌بند SVM آشنا میشیم. این دسته‌بند محبوب‌ترین دسته‌بند هست. اول با مفهوم margin آشنا میشیم و میگیم که SVM دنبال این هست که مقدار margin رو حداکثر کنه. بعد انواع SVM و کرنل رو خواهیم دید.
اگر یک سری داده داشته باشیم که با خط قابل جدا شدن باشن، می‌دونیم که احتمالا خط‌های زیادی وجود داره که بتونیم این داده‌هارو از هم جدا کنیم و لزوما فقط یک خط نیست. حالا کدوم یکی از این خط‌ها از بقیه بهتره؟ شاید خطی مناسب‌تر باشه که با داده‌ها فاصله بیشتری داره و اون‌هارو از هم جدا میکنه و این خط شاید باعث تعمیم‌پذیری بیشتری هم بشه.
برای درک بهتر مفهوم margin تصویر زیر رو در نظر بگیرید. سه خط مختلف رو در نظر گرفتیم. فرض کنید مثلا در یکی از عکس‌ها فرضا اولین عکس از سمت چپ، خط داده شده رو در همون راستای خودش جابجا کنیم (شیب خط ثابت بمونه صرفا مقدار W0 رو جابجا کنیم) margin به این معنی هست که ما تا کجا میتونیم اون خط رو جابجا کنیم تا داده‌ها درست دسته‌بندی بشن.
الان تو عکس اول از سمت چپ، میزان margin خیلی کمه. تو عکس وسط میزان margin یکم بیشتر شده و تو عکس آخر از سمت راست هم میزان margin در بیشترین حالت هست.
چرا خط با margin بیشتر رو به خط با margin کمتر ترجیح می‌دیم؟ یه جورایی تعمیم‌پذیری بیشتر میشه. چرا؟ چون باعث میشه بهتر دسته‌ها از هم جدا بشن.
در ادامه اول در مورد داده‌هایی که به‌صورت خطی از هم جدا میشن بحث می‌کنیم، بعد داده‌هایی که خطی قابل جدا شدن نیستن رو هم بررسی خواهیم کرد.
به صورت کلی SVM نبال پیدا کردن خطی با بیشترین میزان margin هست.
قبل از اینکه وارد مسئله بهینه‌سازی SVM بشیم، بریم سراغ یک سری تعاریف و مقدمات اولیه.
فاصله یک نقطه از صفحه به صورت زیر به‌دست میاد. نقطه رو تو معادله صفحه جایگذاری کنیم، ازش قدر مطلق بگیریم و تقسیم بر اندازه بردار نرمال صفحه کنیم.
ممکنه به جای w0 تو بعضی کتاب‌ها یا منابع از حرف b استفاده بشه.
فرضمون تو این مسئله اینکه داده‌ها به‌صورت خطی تفکیک‌پذیر هستن.
گفتیم نزدیک‌ترین نقطه به صفحه یا خط رو Xn در نظر می‌گیریم و مقادیر W و w0 رو جوری ست کردیم که اگر Xn رو تو معادله ابرصفحه جایگذاری کنیم، جواب نهایی مقدارش 1 میشد. چون Xn رو نزدیک‌ترین نقطه به خط یا صفحه در نظر گرتیم پس بقیه نقاط دورتر قرار می‌گیرن.
حالا بالاتر دیدیم که فاصله اقلیدسی چجوری به‌دست میاد. همچنین مقدار WTXn + x0 برابر با 1 بود که اگر تو فرمول بالاتر جایگزین کنیم جواب میشه:
1/||W||
حالا اگر کل margin رو در نظر بگیریم، میشه:
2/||W||
فرض کنید نقطه قرمز نزدیک‌ترین نقطه به خط سیاه باشه و فاصله‌ش 1 هست. چون margin وجود داره، پس کلا میشه 2.
حالا شرطی که گذاشتیم چی داره میگه؟ میگه به ازای همه نمونه‌های آموزش اگر بیایم فاصله از خط یا صفحه رو حساب کنیم بعد مینیمم بگیریم مقدارش میشه 1. دقیقا همون فرضی که اول کار در نظر گرفتیم که نزدیک ترین نقطه به خط یا صفحه مقدارش 1 میشه.
از نظر بهینه‌سازی این جزو مسئله‌های سخت هست و ما نمی‌تونیم حل کنیم. پس باید بیایم کاری کنیم که شرطمون به صورت یک‌سری روابط خطی در بیاد. پس نیاز داریم روابطی که تا اینجا بهش رسیدیم رو معادلش رو بنویسیم.
قدر مطلق معادله خط یا صفحه برابر میشه با حاصلضرب y در معادله. چرا؟ چون مقدار y یا مثبت هست یا منفی. وقتی قدر مطلق رو برداریم انگار داریم علامتش رو برمی‌گردونیم سرجاش.
حالا می‌خوایم شرطمون رو باز نویسی کنیم. اینجوری در نظر می‌گیریم که تک تک نقاط باید فاصله‌شون از صفحه بزرگتر یا مساوی 1 باشه. (چون نزدیک‌ترین نقطه به صفحه یا خط فاصله‌ش 1 بود، پس هیچ نقطه دیگه‌ای وجود نداره که فاصله‌ش از 1 کمتر بشه)
ممکنه سوال پیش بیاد که چرا وقتی صورت مسئله رو بازنویسی کردیم برای ||W|| توان 2 ظاهر شد. ماکسیمم کردن مقدار 2 بر روی ||W|| فرقی با ماکسیمم کردن 2 بر روی ||W|| به توان 2 نداره. (یعنی ما وقتی داریم یه عبارتی رو ماکسیمم می‌کنیم، میتونیم توان دومش رو به‌جای خودش ماکسیمم کنیم) وقتی که همه موارد رو بازنویسی کردیم، ماکسیمم کردن 2 بر روی ||W|| به توان 2 معادل شد با مینمم کردن 1/2 در ||W|| به‌توان 2. این مسئله بهینه‌سازی برامون قابل حله.
حالا اگه مسئله رو بخوایم با جزییات بیشتری نشون بدیم و بررسی کنیم به روابط زیر می‌رسیم.
برای حل مسئله بهینه‌سازی که تا اینجا بهش رسیدیم باید از روش Quadratic Programming استفاده کنیم.
در واقع برای حل این مسائل یک‌سری ابزار وجود داره که خیلی راحت مارو به جواب می‌رسونه.
تو مسئله‌ای که داریم، ماتریس Q برابر با ماتریس همانی میشه، مقدار C هم برابر با 0 است. یک سری قید و شرط هم که میتونیم خودمون اضافه کنیم. همه این‌ها رو به ابزار می‌دیم و مسئله رو برامون حل میکنه.
هرچند ما این مسئله بهینه‌سازی رو مستقیم برای SVM حل نمی‌کنیم. در واقع یه دوگان تعریف می‌کنیم که خیلی ساده‌تره و سعی می‌کنیم اون رو حل کنیم.
قبل از اینکه مسئله دوگان SVM رو ببینیم، اول بررسی کنیم که چطور میشه یک مسئله بهینه‌سازی محدودیت‌دار رو حل کرد.
فرض کنید یه تابع به نام f داریم و دنبال مینمم اون تابع هستیم و یک سری شرط تساوی و نامساوی هم وجود داره. از نظر بهینه‌سازی کاری که برای حل این مسئله می‌کنیم استفاده از تکنیک ضریب لاگرانژه. یه تابع تشکیل می‌دیم که علاوه بر اینکه تابع x هست، تابعی از ضرایبی هست که برای هر کدوم از توابعی که تو شرط‌ها ظاهر شدن هم هست.
اصطلاحا به alpha و lambda ضرایب لاگرانژ گفته میشه و هردوشون از جنس بردار هستن. برای اینکه عملکرد بهتر این تابع و این ضرایب رو بهتر بفهمیم، فرض کنید تابعی که تا اینجا تشکیل دادیم رو می‌خوایم ماکسیمم کنیم به ازای همه مقادیر alpha و lambda، فقط برای alpha شرط بزرگتر مساوی 0 هم در نظر می‌گیریم. به زودی می‌فهمیم چرا همچین شرطی رو لحاظ کردیم براش.
میخواهیم نواحی مختلف فضای x رو دسته‌بندی کنیم و برحسب اون بگیم که مقدار lambda چی میشه. تو دو حالتی که شرط‌ها برقرار نمیشن، مقدار تابع لاگرانژ بی‌نهایت شده. زمانی هم که شرط‌ها برقرار میشن مقدار تابع لاگرانژ برابر شده با مقدار f(x).
قبلا دنبال این بودیم که تابع f رو روی بخشی از فضا حداقل کنیم که شرط‌هایی که گذاشتیم برقرار باشه. به‌جاش می‌خوایم بگیم max لاگرانژ رو حداقل کن ولی روی کل فضا دیگه شرطی نداریم. چرا شرطی نداریم تو این فضا؟ چون بررسی کردیم حالت‌هایی رو که خارج از محدوده شرط‌هامون بود و دیدیم مقدار لاگرانژ بی‌نهایت میشه پس مهم نیست برامون. چرا؟ چون دنبال مینمم کردن ماکسیمم تابع لاگرانژ هستیم. یعنی انگار داریم مقدار تابع f رو تو حالتی که همون شرط‌های اولیه رو داریم حساب می‌کنیم.
پس در نهایت به‌جای اینکه مینمم خود تابع f رو پیدا کنیم، دنبال مینمم تابع لاگرانژ می‌گردیم.
حالا نکته‌ای که وجود داره اینکه میتونیم جای min و max رو عوض کنیم و برای چیزی که بالا دیدیم دوگان بسازیم که دقیقا معادلش هست.
حالا برگردیم سر مسئله اصلیمون. تو این مسئله فقط یک سری شرط نامساوی داریم. برای اینکه این شرط رو شبیه شرط بالا کنیم (یعنی شرطی باشه که مقدارش منفی بشه) کافیه که فقط یه جابجایی انجام بدیم. حالا الان دقیقا شد شبیه مسئله‌ای که بالاتر بررسی کردیم و راه حلش رو دیدیم. عبارتی که بعنوان ضریب برای alpha آورده شده همون تابع g هست که تو اسلایدهای بالا هم وجود داره. در نهایت هم جای min و max رو عوض کردیم.
حالا بریم که مسئله رو حل کنیم. اول مینمم باید حساب کنیم. چجوری؟ مشتق بگیریم برابر با 0 بذاریم اگه به روابط بسته رسیدیم تمومه. جوابی که برای بردار W رسیدیم اینطوره که میگه تک تک نمونه‌های آموزش رو در y مربوط به خودش و در یک ضریب دیگه ضرب کن بعد همه رو باهم جمع کن.
حالا می‌خوایم تو تابع لاگرانژ چیزایی که بالا حساب کردیم رو جایگذاری کنیم. تو قدم اول اومده alpha(n) رو ضرب کرده در 1.
بعد از ضرب مقدار 1 رو از رابطه لاگرانژ برداشته و مقدار (n)alpha رو پایین نوشته. مقدار W0 رو هم میتونیم حذف کنیم.
بعد از حذف کردن W0 روابط زیر رو داریم. دو تا جمله‌ای که داریم از جنس هم دیگه هستن فقط ضرایبشون فرق داره. یکی ضریبش 1/2 عه اون یکی هم alpha(n) هست.
حالا در نهایت به رابطه زیر می‌رسیم.
تا اینجا فرم رابطه دوگان رو برای SVM به‌دست آوردیم. از اونجایی که یک مسئله QP هست حلش با ابزار خیلی ساده اتفاق میفته. اما اصلا چرا دوگان حساب کردیم؟ چون شهود بیشتری رو میتونیم تو این رابطه ببینیم که جلوتر بررسی می‌کنیم.
عبارت بالا رو میتونیم به شکل پایین بازنویسی کنیم. دنبال پیدا کردن ماکسیمم f بودیم که معادله با پیدا کردن مینیمم منفی f. از طرفی دیگه حاصلضرب y در x رو میتونیم به صورت ماتریس بنویسیم. عبارت اول رابطه بالا چطور؟ به این معنیه که انگار مقدار alpha(n) رو با 1 ضرب داخلی کنیم.
حالا فرض کنید این مسئله رو حل کردیم. خط رو از کجا در بیاریم؟
اول اینکه مقدار alpha با حل به کمک روش QP به دست میاد. از طریق مقدار alpha هم میتونیم مقدار W رو حساب کنیم. مقدار W0 رو چجوری پیدا کنیم؟ جلوتر می‌بینیم.
فرض کنید می‌خوایم f رو حداقل کنیم و یک سری شرط‌هایی براش در نظر گرفتیم. تابع لاگرانژی هم که براش تشکیل می‌دیم مثل رابطه وسط میشه. حالا می‌خوایم شرط‌های لازم برای جواب‌های مسئله رو پیدا کنیم که تو سمت راست اومده.
این‌ها یک سری شرط هستن که می‌خوایم ازشون استفاده کنیم تا بتونیم جواب بهینه رو پیدا کنیم. به این شروط اصطلاحا شروط KKT گفته میهشه.
حالا بریم تو مسئله‌ای که داشتیم شرایط KKT رو بنویسیم. در ادامه جزییات و شهودش رو بررسی خواهیم کرد.
حالت اول که تو اسلاید پایین اومده به این معنی هست که داده‌هامون روی margin نیفتاده. یا سمت بالای margin هست یا سمت پایینش و ازش دوره. حالت دوم به این معنی هست که داده حتما روی margin قرار گرفته باشه.
اگر alpha از 0 بزرگتر بشه به این معنیه که داده روی margin افتاده حتما.
به نقاطی که مقدار alpha توشون از 0 بیشتر میشه support vector میگیم. چرا؟ چون از اون‌ها استفاده می‌کنیم تا مرز رو مشخص کنیم.
حالا با استفاده از support vector میخواهیم مقدار W0 رو محاسبه کنیم.
یکی از مقادیر alpha که مقدارش بیشتر از 0 هست رو برمی‌داریم (support vector) از طرفی دیگه می‌دونیم اگر نقطه‌ای روی margin باشه رابطه زیر براش برقراره. پس به سادگی مقدار W0 رو میتونیم حساب کنیم.
حالا می‌خوایم مرز یا همون قانون تصمیم‌گیری رو پیدا کنیم. یعنی چی؟ یعنی اگه داده‌ای مثبت هست بیفته طرف مثبت، اگه منفی هست بیفته طرف منفی.
هر داده‌ای که تو رابطه دسته‌بند ظاهر شده (یعنی هر جا که x داریم) به صورت ضرب داخلی دو نقطه هست. این کمک میکنه که بعدا تو بحث کرنل بتونیم دسته‌بندهای پیچیده‌تری بسازیم به‌جای ضرب داخلی.
تا اینجا مسئله بهینه‌سازی‌ای که حساب کردیم به فرم زیر در اومد.
همونطور که قبلا تو مسئله رگرسیون خطی و غیرخطی دیدیم، برای پیداکردن مرز مناسب اول فضارو عوض می‌کردیم خط رو رد می‌کردیم بعدش برمی‌گردوندیم به حالت اولیه. حالا مشابه اون مفهوم رو اینجا هم می‌خوایم استفاده کنیم. فرض کنید داده‌هامون جوری باشن که با یک دایره قابل جدا شدن باشن. یعنی داده‌هارو به دو دسته داخل دایره و خارج دایره تقسیم کنیم. حالا اگه تبدیل روی داده‌ها انجام بدیم، به جای خود x مقدار phi(x) رو خواهیم داشت. پارامترها ثابت می‌مونن و تغییری نمی‌کنن. یعنی چی؟ یعنی اینکه تغییر ابعاد و فضا هیچ ربطی به تعداد و مقدار پارامترها نداره. تنها مشکلی که وجود داره و موضوع رو پیچیده میکنه پیچیدگی محاسبه ضرب داخلیه. ولی بعدها می‌بینیم که این پیچیدگی رو هم میشه با روش‌هایی کمتر کرد حتی تو ابعاد خیلی بالا.
جلسه بعدی قبل اینکه بحث کرنل رو شروع کنیم، اول در مورد داده‌هایی که به‌صورت خطی قابل جدا شدن نیستن صحبت می‌کنیم. حتی ممکنه داده‌ها به صورت خطی قابل جدا شدن باشن اما نویز وجود داشته باشه تو داده‌ها. پس باید روش‌هایی براش داشته باشیم که در این حالت‌ها هم باز بتونیم میزان margin رو حداکثر کنیم. الان تو شکل پایین سمت چپ، ترجیح می‌دیم اون داده آبی غلط دسته‌بندی بشه، اما میزان margin بیشتر بشه.
چیزی که تا اینجا بررسی کردیم Hard Margin بود. از اینجا به بعد راجع به Soft Margin صحبت می‌کنیم. مقدماتشو اینجا می‌بینیم و جزییاتش رو در جلسه بعدی بررسی خواهیم کرد. به صورت کلی اینطوره که میایم شرط‌هایی که تعریف کردیم رو یکمی منعطف‌تر می‌کنیم. انگار به‌جای اینکه بگیم که داده‌ها دقیقا بالا و پایین خط قرار بگیرن، اشکالی نداره که یه سری از داده‌ها اشتباهی دسته‌بندی بشن. تو جلسه بعدی اول صورت مسئله رو به صورت دقیق مطرح می‌کنیم بعد هم دوگانش رو به‌دست میاریم و بقیه مراحلی که اینجا طی کردیم رو تو soft margin هم خواهیم دید.
فرمول ماکسیمم کردن margin رو تو SVM دیدیم. بعد منجر شد به یک مسئله QP. بعد اومدیم به‌جای خود مسئله دوگانش رو در نظر گرفتیم که معادل بود با حل کردن مسئله بهینه‌سازی ضرایب لاگرانژ. مسئله بهینه‌سازی ضرایب لاگرانژ رو با جزییات بیشتری بررسی کردیم که منجر شد برسیم به معرفی شرایط KKT. بعد مفهوم support vector رو مطرح کردیم و مقدار W0 رو به کمک اون حساب کردیم.
اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.
