سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.
همونطور که در جلسه گذشته دیدیم، می‌تونستیم به‌جای بردن داده‌ها به فضای جدید و محاسبه ضرب داخلی‌شون، بدون بردن داده‌ها به فضای جدید مستقیما ضرب داخلی‌شون رو پیدا کنیم و این باعث میشد که از نظر پیچیدگی کارمون خیلی ساده‌تر بشه. همچنین دیدیم که انواع مختلف کرنل وجود داره. حالا بریم در ادامه یه مثال دیگه ببینیم.
داده‌هامون دو کلاسه هستن و مرز بین داده‌ها با رابطه زیر تعیین میشه. مرزی که به دست اومده یه جورایی پیچیده‌ست و از جمع یک‌سری گاوسی به دست اومده.
می‌خواهیم پارامتر C و پارامتر alpha رو تو این مثال بررسی کنیم. همونطور که قبلا هم دیده بودیم در مسئله soft margin وقتی مقدار پارامتر C رو خیلی زیاد (مثلا بی‌نهایت) در نظر می‌گرفتیم به این معنی بود که در مورد همه داده‌ها margin رعایت بشه که دقیقا معادل با مسئله hard margin SVM بود. یه جورایی hard margin SVM ای که در فضای کرنل عمل میکنه. تو این حالت یک سری support vector داریم که با دایره روی مرز marginها مشخص شدن.
حالا با همون مقدار alpha اگه مقدار C رو از بی‌نهایت کمتر کنیم باعث میشه که کم کم به مسئله soft margin تبدیل بشه و بهمون اجازه بده که کم کم مرز رو رد کنیم.
حالا هرچقدر مقدار C رو کمتر کنیم، می‌بینیم که تعداد بیشتری از داده‌ها support vector میشن.
حالا مقدار پارامتر کرنل که همون alpha هست رو تغییر بدیم ببینیم چه تغییراتی میکنه. تو اولین حالت با توجه به مقدار پارامتر C یک مسئله hard margin داریم.
هرچقدر مقدار آلفا کمتر بشه انتظار داریم overfitting بیشتر بشه و مرز جدا کننده پیچیده‌تری داشته باشیم.
در نهایت وقتی مقدار آلفا به 0.1 می‌رسه، مرز در پیچیده‌ترین حالت به سر می‌بره. در تمامی عکس‌ها داده‌هایی که با دایره مشخص شده support vector هستن. خط‌چین margin رو مشخص میکنه و اون فضایی که تیره و روشن شده داره مرز رو مشخص میکنه.
آیا لازمه soft margin و kernel در کنار هم استفاده بشن؟ خیلی وقت‌ها در عمل از این دو در کنار هم استفاده می‌کنیم. ترکیبات مختلف alpha و C رو کنار هم می‌ذاریم و در نهایت با چک کردن ارور بهترین نتیجه رو انتخاب می‌کنیم.
در ادامه راجع به این صحبت می‌کنیم که این امکان وجود داره که الگوریتم‌های دیگه رو هم می‌تونیم بر اساس کرنل بنویسیم.
هرجایی ضرب داخلی داده‌هارو داشته باشیم می‌تونیم از کرنل استفاده کنیم.
حالا در حالت کلی چطور باید مطمئن بشیم کرنلی که طراحی کردیم درست هست؟ جلوتر بررسی می‌کنیم.
به کمک یک قضیه می‌تونیم متوجه بشیم که آیا کرنلی که طراحی کردیم کرنل خوبی هست یا نه.
قضیه این رو میگه که اگر به ازای هر N نقطه یک ماتریس بسازیم (بهش ماتریس کرنل یا Gram گفته میشه) و درایه ij آن حاصل ضرب داخلی نقطه i و j آن را مشخص می‌کند در واقع کرنل بین دو نقطه i و j هست. اگه همچنین ماتریسی به ازای هر N نقطه بسازیم، چه زمانی میگیم کرنلی که در نظر گرفتیم معادل میشه با ضرب داخلی دو نقطه در یک فضایی؟
اولین ویژگی خیلی مهم اینکه اون تابعی که بعنوان کرنل در نظر می‌گیریم اینکه متقارن باشه. دومین ویژگی اینکه Positive Semi-Definite باشه. وقتی ماتریسی مثل A رو بتونیم به صورت ضرب BBT بنویسیم میگیم همچین خاصیتی رو داره.
یک سری خواص دیگه هم وجود داره برای کرنل که تعدادی‌شو بهش اشاره می‌کنیم:
حالا بریم ببینیم که آیا میشه برای حالت‌های ساده کرنل تعریف کرد؟
مثال اولی که بررسی می‌کنیم در این مورد، راجع به دسته‌بند‌های احتمالاتی هست. اینجوری بود که وقتی مسئله رو دو کلاسه در نظر می‌گرفتیم هر کلاس رو می‌تونستیم با یک گاوسی مدل کنیم. حالا فرض کنید برای دسته‌بندی اینجوری در نظر بگیریم که هر نقطه رو فاصله‌ش رو از میانگین هر کدوم از این توزیع‌ها در نظر بگیریم به هر کدوم نزدیک‌تر بود، به همون کلاس اختصاصش بدیم.
حالا چجوری این مسئله رو بر اساس کرنل بنویسیم؟ برای اینکه بر اساس کرنل بنویسیم همه چیز باید بر اساس ضرب داخلی باشه. فرض کنید به‌جای فاصله اقلیدسی، فاصله به توان 2 رو در نظر بگیریم و اون‌هارو مقایسه کنیم. در ادامه بهتره که مقادیر میانگین رو هم باز کنیم و از روی خود سمپل‌ها بنویسیم. به جای ضرب داخلی نمونه‌ها کرنل رو جایگزین می‌کنیم. مرز رو می‌تونیم از حالت خطی به حالت‌های پیچیده تبدیل کنیم به کمک کرنل.
یه جورایی هر الگوریتمی که بر اساس فاصله نقاط عمل کنه رو می‌تونیم به سادگی براش کرنل بنویسیم. چرا؟ چون می‌تونیم به راحتی نشون بدیم که فاصله اقلیدسی دو نقطه در فضای جدید بر اساس ضرب داخلی نوشته میشه.
حالا می‌تونیم مسئله رگرسیون رو هم بر اساس کرنل بنویسیم. تو مثال بعدی این رو بررسی می‌کنیم. تو مسئله رگرسیون یه تابع هزینه داشتیم که می‌خواستیم مقدارش رو حداقل کنیم. مشکلی که اینجا داریم اینکه ما ضرب داخلی داده‌هارو لازم داریم برای اینکه بتونیم بر اساس کرنل بنویسیم و اینجا نداریمش به جاش ضرب داخلی داده‌ها در W رو داریم.
حالا ما تابع هزینه زیر رو داریم. باید ازش مشتق بگیریم و برابر با 0 قرار بدیم. وقتی این کارو رو می‌کنیم بعد از تنها کردن W می‌تونیم اون رو بر اساس یه ضریبی از X بنویسیم. برامون مهم نیست که اون ضریب چیه. به صورت کلی، هرجا که یک تابع خطی داریم و می‌تونیم W رو بر اساس جمع وزن‌دار نقاط بنویسیم می‌تونیم براش کرنل رو حساب کنیم.
حالا داده‌هارو بردیم به یک فضای جدید و می‌خوایم از تابع هزینه مشتق بگیریم و بر اساس کرنل بنویسیم. فقط کافیه به جای W مقدار جدیدی که تو فضای جدید رو براش محاسبه کردیم جایگذاری کنیم.
برای داده جدیدی هم که بیاد می‌تونیم به روش زیر تصمیم‌گیری بکنیم. یعنی بدون اینکه داده رو به فضای جدید ببریم با استفاده از تابع کرنل می‌تونیم در موردش اظهار نظر بکنیم.
کرنل برای داده‌هایی که جنسشون طوری نیست که بتونیم با یه وکتور نشون بدیم هم کاربردی هست. مثلا گراف‌ها و دنباله‌ها از جنس وکتور نیستن. حالا می‌تونیم به جای اینکه برای داده‌ها مستقیما ویژگی تعریف کنیم، از کرنل بعنوان تابع شباهت استفاده کنیم. چرا از کرنل بعنوان معیار شباهت استفاده می‌کنیم؟ به این دلیل که برای محاسبه کرنل داریم از ضرب داخلی استفاده می‌کنیم و ضرب داخلی هم با کسینوس رابطه داره. پس یه جورایی داره بهمون شباهت رو میگه.
از اولین جلسه تا به اینجا مسائلی که باهاشون سر و کار داشتیم به این صورت بوده که یک سری پارامتر داشتن و ما به دنبال پیدا کردن اون پارامترها به بهترین نحو بودیم. یک سری الگوریتم دیگه وجود دارن که اصلا چنین پارامترهایی رو ندارن و خیلی ساده‌تر هم حل میشن. درخت تصمیم یکی از این دسته‌بندهاست.
اساس کار درخت تصمیم تقسیم‌بندی فضاست. یعنی میخواد ببینه به هر قسمت از فضا چه برچسبی رو اختصاص بده به داده‌ها. برخلاف سادگی‌ش دقت خیلی خوبی داره. برای شهود بهتر از این دسته‌بند با یک مثال شروع می‌کنیم.
فرض کنید برای داده‌مون یک سری ویژگی در نظر گرفتیم. اکثرا این ویژگی‌ها به صورت گسسته تعریف میشن اما در آخر این بحث خواهیم دید که چطور ویژگی‌های پیوسته رو هم به گسسته تبدیل کنیم. تو این مثال 4 تا ویژگی مختلف تعریف کردیم. مثلا سنش بالای 40 هست یا نه. درد قفسه سینه داره یا نه. سیگار میکشه یا نه. تست ورزشش مثبت شده یا نه. چیزی هم که میخواد حدس بزنه اینکه آیا اون فرد بیماری قلبی داره یا نه. هر نود یکی از ویژگی‌هارو نشون میده. هر یال مشخص‌کننده یکی از مقادیری هست اون نود می‌تونه بگیره. چون اینجا دو حالت داشتیم (بله/خیر) پس دو تا یال شد. در هر مسیر هم انگار که داریم شرایط رو باهم دیگه AND می‌کنیم و جلو میریم. این مثل تقسیم‌بندی فضا و در نظر گرفتن یک برچسب به‌ازای اون فضا میمونه. تقسیم‌بندی فضا هم یا بر اساس یک ویژگی انجام میشه یا بر اساس AND چند ویژگی. همونطور که در درخت هم مشخصه، دسته مثبت داره از مسیرهای مختلف و مستقل از هم مشخص میشه و فقط یک مسیر خاص نیست.
از این دسته‌بند بیشتر برای کلاس‌بندی استفاده میشه. اما میشه برای مسائل رگرسیون‌طور هم ازش کمک گرفت.
یه مثال دیگه ببینیم. در مورد برگزار شدن یا نشدن بازی تنیس هست که بر اساس شرایط جوی مشخص میشه. حالا فرض کنید بر اساس دیتایی که از قبل داریم همچین درختی رو ساختیم. حالا اصلا چجوری باید درخت رو بسازیم؟ از کجا تشخیص دادیم که ویژگی outlook رو بعنوان اولین ویژگی در نظر بگیریم؟
باید به طریقی ویژگی‌هارو اولویت‌بندی کنیم. درخت تصمیم تو این مورد خیلی حریصانه و گریدی عمل میکنه. میاد میبینه به ازای هر ویژگی چقدر اون ویژگی خوبه که بعنوان root در نظر گرفته بشه. بعد که ریشه رو فیکس کرد در مورد بقیه نودها تصمیم‌گیری میکنه. مسئله‌مون اینجا میشه پیدا کردن یک درخت که درخت خوبی هست.
برای درخت تصمیم الگوریتم‌های مختلفی برای learning وجود داره که در ادامه بررسی‌شون خواهیم کرد.
حالا چجوری ویژگی بهتر رو انتخاب کنیم؟ فرض کنید یک معیاری انتخاب کردیم بر اساس اون می‌خوایم بهترین درخت رو پیدا کنیم. جلوتر این معیار رو دقیق بررسی خواهیم کرد. حالا فرض کنید این معیار اینجوری کار میکنه که روی یک ویژگی و یک مجموعه نمونه اعمال میشه و در جواب بهمون یک عدد میده. رو تمام ویژگی‌ها این معیار رو حساب می‌کنیم. اونی که این عدد توش از همه بیشتر بشه رو بعنوان ریشه در نظر می‌گیریم و همین کار رو برای بقیه نودها تکرار می‌کنیم.
شبه کد راه‌حلی که بالا ارائه دادیم اینجا اومده. این الگوریتم رو تا چه زمانی به‌صورت بازگشتی اجرا میکنه؟ تا زمانی که نمونه‌هایی که به یک نود اختصاص داده شدن همشون مثبت یا همشون منفی باشن. (وقتی همه نمونه‌ها مختص یک کلاس باشن دیگه هیچ نیازی نیست که ادامه بده و همون نود رو بعنوان برگ در نظر میگیره.) حالت دیگه هم این هست که تمامی ویژگی‌هامون تموم بشه و برسیم به یک مجموعه سمپلی که توش هم نمونه مثبت داریم هم منفی.
شرط تموم شدن الگوریتم تو اسلاید پایین مجددا بهش اشاره شده:
این هم جزییات الگوریتم ID3 هست:
تا اینجا با کلیات درخت تصمیم آشنا شدیم. جلسه بعدی در مورد معیار انتخاب ریشه با جزییات صحبت خواهیم کرد. این جلسه فقط یک سری مقدمات راجع بهش خواهیم دید.
معیاری مد نظر ما هست که وقتی بر اساس اون درخت رو تشکیل می‌دیم وقتی نمونه‌هارو بر اساسش تقسیم بندی می‌کنیم نمونه‌ها برچسبشون از یک جنس باشن. مثلا همشون مثبت باشن یا همشون منفی باشن. به عبارتی دیگه خالص بودن برچسب زیر درخت برامون مهمه.
معیاری به نام آنتروپی داریم که می‌تونیم ازش استفاده بکنیم. فرض کنید توزیع برنولی رو داریم. یه سکه رو در نظر بگیرید که مثلا با احتمال pi شیر میاد و با احتمال 1 منهای pi خط میاد. اگه بخوایم براش آنتروپی رو حساب کنیم به این صورت در میاد:
فرمول کلی معیار آنتروپی هم اینجا آورده شده:
حالا خاصیتی که معیار آنتروپی داره اینکه وقتی مقدار احتمال نیم بشه این معیار حداکثر مقدارشو داره و وقتی برابر با 0 یا 1 هست مقدارش برابر با 0 میشه. پس یعنی انگار وقتی نمی‌دونیم که احتمال کدوم یکی از دو رخداد بیشتره، معیار آنتروپی مقدارش خیلی زیاده در مقایسه با وقتی که می‌دونیم کدوم یکی از دو رخداد میخواد رخ بده.
بحث کرنل رو ادامه دادیم و دیدیم که میشه همه مسائل رو یه جورایی با کرنل بازنویسی کرد. با کلیات درخت تصمیم آشنا شدیم و دیدیم که به صورت کلی چجوری کار میکنه.
اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.
