سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.
گفتیم می‌خوایم داده‌های مثبت و منفی رو طوری با یک خط از هم جدا کنیم که margin زیادی داشته باشیم. مسئله بهینه‌سازی رو هم به شکل زیر برای SVM در آوردیم. بعد از تکنینک ضریب لاگرانژ استفاده کردیم و برای این مسئله یک دوگان تعریف کردیم.
مسئله دوگان به شکل زیر در اومد. در نهایت دیدیم که پارامترهامون هیچ ربطی به داده‌هامون و ابعادش نداره و میتونیم فضا رو عوض کنیم.
مسئله دوگان رو ابزار برامون می‌تونه حل کنه. منتها مشکلی که هست اینکه حتی اگه این مسئله جواب نداشته باشه، ابزار بهمون یه جوابی برمی‌گردونه و نمیگه که مسئله جواب نداره. جوابی که بهمون میده احتمالا یک جواب پرتی خواهد بود. حالا در چه حالتی این مسئله جواب نداره؟ حالتی که داده‌ها خطی تفکیک‌پذیر نباشن. حالا از کجا بفهمیم جواب ابزار جواب مسئله هست یا نیست؟ میتونیم بردار alpha ای که به عنوان جواب بهمون میده رو تو رابطه‌ای که داریم جایگزین کنیم و مقدار y ای که به‌دست میاد رو با y واقعی مقایسه کنیم. اگر نزدیک بهم شدن می‌فهمیم که جوابی که بهمون داده درست هست و داده‌ها خطی تفکیک‌پذیر بودن.
حالا اگه داده‌ها خطی تفکیک‌پذیر نباشن چه کنیم؟ یا داده‌ها خطی تفکیک‌پذیر باشن ولی نویز وجود داشته باشه چی؟ مفهومی بعنوان soft margin رو داریم.
چیزی که تا اینجا و جلسه قبلی دیدیم hard margin بود و اینطور بود که اجازه نمی‌داد هیچ داده‌ای وارد محدوده margin بشه ولی توی soft margin ما این اجازه رو میدیم که داده‌ها بتونن وارد محدوده margin یا حاشیه بشن.
حالا برای اینکه بفهمیم چطور داریم کار می‌کنیم و برای ارزیابی باید بیایم یک تابع هزینه یا خطا تعریف کنیم تا بسنجیم که به ازای داده‌هایی که وارد فضای حاشیه شدن چقدر خطا رخ داده. نماد ξ بهمون نشون میده که هر داده چقدر از margin عبور کرده و به خط نزدیک شده. مسئله بهینه‌سازی‌ای که اینجا داریم هدفش کم کردن میزان این ξ هاست به ازای همه نمونه‌ها.
مسئله بهینه‌سازی ای که اینجا داریم خیلی شبیه مسئله تو hard margin هست فقط یک جمله بهش اضافه شده و نشون میده که چقدر margin نقض شده. یک سری شرط هم داریم. اگر کی‌سی (ξ) بین 0 و 1 باشه و یا بزرگتر از 1 باشه به چه معنی‌ای هست؟ اگر بین 0 و 1 باشه یعنی درست دسته‌بندی میشه ولی داخل margin هست. اگر بزرگتر از 1 باشه یعنی دسته‌بندی درست انجام نمیشه. هر چقدر مقدار کی‌سی بیشتر باشه، بیشتر جریمه میشه.
هدفمون اینکه میزان کی‌سی margin رو کم کنیم و از طرفی میزان margin رو بیشتر کنیم. از نظر بهینه‌سازی مسئله‌مون از جنس QP میشه که میتونیم مستقیم حلش کنیم ولی ما میایم دوگانش رو در نظر می‌گیریم.
پارامتر C اگه بزرگ بشه چیو نشون میده؟ یعنی می‌خوایم کمتر داده‌ها برن تو حاشیه. وقتی مقدارش بی‌نهایت بشه، به این معنیه که انگار مسئله‌مون hard margin هست. تو حالتی که C مقدارش 0 هست، داده‌ها میتونن هرجوری که می‌خوان پراکنده بشن و اصلا به درد نمی‌خوره.
حالا اصلا مقدار C رو چجوری تنظیم کنیم؟ از تکنیک cross validation استفاده کنیم. یک سری مقدار برای C در نظر بگیریم، بعد ببینیم با کدوم مقدار نتیجه بهتر میشه همون رو در نظر بگیریم.
حالا بریم جزییات مسئله بهینه‌سازی رو بیشتر بررسی کنیم. با جابجایی رابطه بالا به رابطه پایین میتونیم برسیم.
حالا اگر نمودار loss function رو رسم کنیم، به نمودار پایین می‌رسیم. اونایی که درست دسته‌بندی شدن که هیچی. اونایی که تو ناحیه margin قرار می‌گیرن تو قسمت مثبت نمودار هستن. اونایی هم که غلط دسته‌بندی میشن سمت چپ نمودار قرار گرفتن.
تا اینجا مسئله بهینه‌سازی رو دیدیم. از اینجا به بعد بریم دوگان این مسئله رو بررسی کنیم. در جلسه قبلی تبدیل مسئله به دوگانش رو به کمک تابع لاگرانژ با جزییات بررسی کردیم. به همون ترتیب دوگان این مسئله رو می‌نویسیم.
حالا قصد داریم برحسب سه پارامتر اصلی مسئله W, W0 و کی‌سی رابطه رو کمینه کنیم و بر اساس alpha و بتا هم که ضرایب اصلی تابع لاگرانژ هستند، مسئله رو ماکسیمم کنیم. (یعنی مشتق بگیریم برابر با 0 بذاریم)
مسئله بهینه‌سازی عین حالت قبلی میشه که تو جلسه قبلی دیدیم. تنها تفاوت شرطی هست که روی alpha داریم. تو مسئله قبلی alpha بزرگتر یا مساوی صفر بود.
حالا بریم شرایط و حالت‌های مختلف رو یه بررسی بکنیم و ببینیم که چطور میشه و چه شهودی دارن. اگه آلفا بین 0 و C باشه داده دقیقا روی margin میفته. اگه آلفا دقیقا برابر با C بشه، داده‌هایی رو نشون میده که دقیقا داخل margin افتادن. (برای جزییات این بخش و اینکه چطور از طریق این محاسبات به این شهود میرسه به زمان 32:15 تا 40:15 از ویدیو این جلسه مراجعه کنید)
تا اینجا SVM رو دیدیم، حالت‌های hard و soft رو هم با جزییات بررسی کردیم.
حالا اگه بخوایم حالتی رو بررسی کنیم که داده‌ها به کمک خط جدا نشن چیکار کنیم؟ از این بخش به بعد این مبحث رو بررسی خواهیم کرد. تو شکل پایین دو حالت مختلف از داده‌هارو که با یک خط قابل جدا شدن نیستن رو نشون داده. حالت اول رو میتونیم با soft margin حل کنیم. حالت دوم رو نمی‌تونیم و باید انتقال انجام بدیم و بریم تو فضای جدید و دنبال مرز خطی باشیم.
داده‌هارو بردیم به یک فضای جدید که بتونیم با یک خط از هم جداشون کنیم.
چرا اصلا تو SVM به جای خود مسئله بهینه‌سازی با دوگانش کار می‌کنیم؟ اگر فضارو تغییر بدیم، phi(x) داره در WT ضرب میشه. یعنی چی؟ تعداد پارامترها داره با ابعاد فضای جدید افزایش پیدا می‌کنه.
اما اگر دوگان رو در نظر بگیریم چی؟ در این حالت وقتی فضارو عوض می‌کنیم، تغییری در تعداد پارامترها نخواهیم داشت. تنها مشکلی که اینجا داریم پیچیدگی ضرب داخلی هست که ممکنه زمانبر باشه.
بعد از اینکه بردار W رو حساب کردیم مرزمون چه شکلی میشه؟ فرمول اول داره مرز رو نشون میده. از قبل هم می‌دونیم که بردار W به چه صورتی هست. مقدار W0 رو هم به کمک یک support vector میتونیم حساب کنیم.
حالا اگر مقداری که برای W به دست آوردیم رو تو رابطه بالا بذاریم، هرچیزی که ظاهر میشه حتما شکل ضرب داخلی داره.
در واقع خود داده‌ها در فضای جدید رو نمی‌خوایم، ضرب داخلیشون هم برامون کفایت می‌کنه. آیا راهی وجود داره که به جای اینکه خود داده رو در فضای جدید حساب کنیم مستقیما ضرب داخلی‌شو حساب کنیم صرفا؟ این دقیقا ایده کرنل هست.
می‌خوایم مرز خطی در داده‌ها با ابعاد بالا پیدا کنیم بدون اینکه داده‌هارو به اون فضا مپ کنیم. یعنی تمام ضرب داخلی‌هارو که دیدیم بدون بردن داده‌ها به فضای جدید انجام بدیم.
فرض کنید ضرب داخلی داده‌ها در فضای جدید رو با K نشون میدیم. ضرب داخلی دو نقطه یه جورایی یه تابع هست از اون دو نقطه. انگار K یک تابعی هست که خروجیش میشه ضرب داخلی دو نقطه ورودی.
حالا فرض کنید یک فضای دوبعدی داریم و مقدار phi که به صورت زیر تعریف شده. اینجا فعلا phi رو خودمون حساب کردیم و از روشی که گفتیم استفاده نکردیم. ضرب داخلیشون میشه نظیر به نظیر درایه‌ها و در نهایت جمعشون.
حالا می‌خوایم همین مثال بالا رو بدون اینکه داده‌ها رو ببریم به فضای جدید حل کنیم. فرض کنید تابع کرنل رو تعریف کرده باشیم مجذور 1 بعلاوه ضرب داخلی نقاط در فضای اصلی. می‌خوایم نشون بدیم که این رابطه معادل هست با ضرب داخلی نقاط تبدیل یافته.
اگه این فرمول رو باز کنیم می‌بینیم دقیقا مثل حالت قبلی میشه جواب فقط با این تفاوت که ضریب 2 ظاهر شده تو یک سری از عبارت‌ها. حالا اگه این جواب ضرب داخلی رو بخوایم تبدیل کنیم به دو تا مجموعه نقطه، مقدار رادیکال 2 ظاهر میشه تو یه سری جملات که برای پوشش دادن همون مقدار 2 در جواب هست. آیا رادیکال 2ها برامون مهمن؟ نه مهم نیستن میتونیم صرف نظر کنیم.
حالا بریم این رابطه رو که توان دوم هست برای حالت d بعدی بنویسیم.
حالا حالت چندجمله‌ای با توان بالا رو در نظر بگیرید. برای محاسبه کرنل بین دو نقطه چقدر عملیات نیاز داریم؟ از اردر d هست. چرا؟ اگر توان رو با هزینه 1 حساب کنیم، هزینه جمع کردنمون میشه d.
حالا حالتی رو در نظر بگیرید که داده‌هامون d بعدیه و مرتبه کرنل 2 هست. اگه از روش تبدیل داده‌ها به فضای جدید و بعد ضرب داخلیشون در هم استفاده کنیم اردر محاسبات تو این حالت میشه d به توان 2 که همون m هست. اگه از کرنل استفاده کنیم پیچیدگی‌ش همون از اردر d خواهد بود.
چیزی که تا اینجا بررسی کردیم کرنل چند جمله‌ای بود. الان می‌خوایم یک کرنل جدید معرفی کنیم که انگار فضارو بردیم تو فضای بی‌نهایت بعدی و بعد ضرب داخلی رو اونجا می‌خوایم محاسبه کنیم.
داره میگه اگه دو تا نقطه داریم، من میام فاصله اقلیدسی این دو تا نقطه رو حساب می‌کنم، به توان دو می‌رسونم، تقسیم بر گاما می‌کنم و تو رابطه پایین قرارش میدم.
یک حالت ساده رو در نظر بگیریم. فرض کنیم داده‌ها یک‌بعدی هستن و مقدار گاما 1 هست. می‌خوایم ببینیم انتقال داده‌ها به چه فضایی معادل با این هست که از این کرنل استفاده کنیم. به عبارتی دیگه این کرنل ضرب داخلی نقاط در چه فضایی میشه.
اگه رابطه‌ای که داشتیم رو باز کنیم به چند تا جمله می‌رسیم که یکیشون برابره با exp(2xx'). حالا بسط تیلور این جمله رو می‌نویسیم که برابر میشه با حاصل جمع یک سری جملات.
حالا چیزی که بالا بهش رسیدیم حاصل ضرب داخلی phi(x) و phi(x') هست. خود phi(x) چی میشه؟
یعنی انگار داریم داده‌ها رو به فضای بی‌نهایت بعدی می‌بریم.
فرم‌های دیگه‌ای برای کرنل هم وجود داره که تو تصویر زیر اومده:
حالا ما از کجا مطمئن بشیم اون تابعی که برای کرنل در نظر می‌گیریم برابر میشه با ضرب داخلی نقاط در یک فضای دیگه؟ یک سری شرایط لازم و کافی باید وجود داشته باشه که با چک کردن اون‌ها میتونیم مطمئن بشیم. جلوتر می‌بینیم.
حالا برگردیم به همون رابطه‌ای که برای SVM در آوردیم. وقتی نقاط رو به فضای جدید می‌بردیم یه قسمتی بود که ضرب داخلی نقاط در فضای جدید رو نشون می‌داد بهمون. الان دیگه لازم نیست نقاط رو حتما ببریم تو فضای جدید و بعد ضرب داخلیشون رو حساب کنیم. مستقیما میتونیم از تابع کرنل استفاده کنیم.
معادله مرز و بقیه روابط رو هم میتونیم خیلی راحت با کرنل جایگزین کنیم.
یک مثال ببینیم. می‌خواهیم از کرنل گاوسی برای حل مسئله‌ای که داریم استفاده کنیم. مرزی که اینجا برامون مشخص کرده مثل این میمونه که انگار روی هر داده یک گاوسی قرار دادیم بعد به هرکدوم یک ضریب آلفا اختصاص دادیم و در مقدار برچسبشون (y) ضرب میشن.
مقدار پارامتر کرنل رو در سه حالت مختلف و مرزی که به ازاش رسم کرده نشون داده. وقتی مقدار پارامتر خیلی کوچیک شده مثل این میمونه که هر داده خودش معادل با یک support vector شده و این باعث overfitting میشه.
راجع به ادامه SVM و مباحث soft margin حرف زدیم. مفهوم کرنل رو معرفی کردیم و یکی دو نوع مختلفش رو بررسی کردیم.
اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.
