سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.
مثل الگوریتم پرسپترون دنبال یه خط (یا ابرصفحه) می‌گردیم که بتونیم داده‌هارو جدا کنیم ولی نگاهمون متفاوته نسبت به چیزی که در جلسه گذشته تو الگوریتم پرسپترون دیدیم.
نحوه کار این الگوریتم به این صورته که سعی میکنه اول برداری رو پیدا کنه در فضا که اگر همه داده‌ها بهش مپ شدن خوب بتونه اونارو از هم جدا کنه. تو تصویر پایین یه سری داده مثبت و یه سری داده منفی داریم که به بردار سیاه رنگ مپ شدن. برداری خوبه که بعد مپ شدن داده‌ها بهش تفکیک داده‌ها بهتر انجام بشه.
از این الگوریتم برای کم کردن بُعد هم استفاده میشه. انگار با این کار میاد یه ویژگی جدید اضافه میکنه به ویژگی‌های قبلی‌ای که داشتیم.
فرض کنید یک سری داده داریم با دو تا ویژگی X1 و X2. حالا میایم داده‌هارو روی محور افقی مپ می‌کنیم. همونطور که از تصویر زیر هم مشخصه، مپ شده داده‌ها به خوبی از هم جدا نشدن.
حالا بیایم داده‌هارو روی محور عمودی مپ کنیم. باز هم داده‌ها به خوبی جدا نمیشدن. پس باید یه بردار جدید به جز محور عمودی و افقی پیدا کنیم.
مثلا بردار زیر رو رسم می‌کنیم و همونطور که تو تصویر هم مشخصه به خوبی تونسته داده‌های مپ شده رو از هم جدا کنه.
در هر بُعدی ما صرفا به دنبال یک بردار هستیم که با W مشخص میشه. می‌تونیم W رو بردار نرمال ابرصفحه جدا کننده دسته‌ها در نظر بگیریم.
حالا بریم سراغ نوشتن روابط ریاضی و فرمول‌هایی که لازمه. فرضمون اینکه مسئله دو کلاسه هست و می‌خوایم داده‌هارو به دو کلاس مختلف تقسیم کنیم. از قبل می‌دونیم که تصویر یک بردار روی بردار دیگه برابره با حاصل ضرب داخلی اون دو بردار. اینجا حاصل تصویر X روی بردار W رو به صورت WTX نشون میدیم.
خب الان ما دنبال یه بردار هستیم که اگر داده‌ها روی اون مپ بشن به خوبی از هم جدا بشن. اولین و ساده‌ترین معیاری که می‌تونیم در نظر بگیریم برای اینکه بهترین بردار رو پیدا کنیم اینکه بیایم میانگین داده‌های مپ شده مثبت و میانگین داده‌های مپ شده منفی رو حساب کنیم بعد ببینیم که آیا فاصله میانگین‌ها از هم خوب هست یا نه. به عبارت دیگه میایم داده‌هارو مپ می‌کنیم اول. بعد میانگین داده‌های مپ شده رو حساب می‌کنیم. اگر میانگینی که به دست میاریم خیلی از هم دور باشن می‌تونیم ادعا کنیم که برداری که پیدا کردیم خوبه.
حالا همه چیزایی که تا اینجا گفتیم رو با زبان ریاضی بنویسیم. میانگین دسته اول رو با u1 نشون دادیم و میانگین دسته دوم رو با u2. از اونجایی که دنبال میانگین مپ شده داده‌ها هستیم پس هر کدوم از میانگین‌هارو در WT (ترانهاده بردار W) ضرب کردیم. از طرفی دیگه اندازه بردار W رو 1 در نظر گرفتیم. چرا؟ چون هرچقدر طول بردار W بزرگ‌تر باشه یه جورایی عددی که برای میانگین هم به دست میاد بیشتر میشه. برای اینکه جلوی این رو بگیریم، اندازه W رو به 1 محدود می‌کنیم. در نهایت قراره دو میانگین مپ شده رو مقایسه کنیم و هرچقدر فاصله دو میانگین بیشتر باشه برامون بهتره.
حالا اگه این مسئله بهینه‌سازی رو با تکنیک ضریب لاگرانژ (که اینجا توضیح داده نمیشه) حل کنیم، جوابی که به دست میاد برای W متناسب میشه با u1-u2. یعنی چی؟ یعنی بردار W رو برداری در نظر بگیر که دو میانگین رو بهم وصل میکنه. چرا؟ چون در این حالت دو میانگین مپ شده بیشترین فاصله از هم رو خواهند داشت.
این معیاری که در نظر گرفتیم معیار خوبی نیست. چرا؟ چون واریانس رو توش لحاظ نکردیم. یعنی چی؟ یعنی چون واریانس کم نیست باعث شده که داده‌ها تو هم قاطی بشن. (تو تصویر بالا هم مشخصه) ما می‌خوایم میانگین مپ شده داده‌ها از هم دور باشه همچنین داد‌ها فشرده هم باشن که تو هم دیگه قاطی نشن، به عبارت دیگه یعنی واریانسشون کم باشه. برداری که تو شکل پایین نمایش داده شده یه مقدار کمی واریانس داره، به همین دلیل هم داده‌ها کمی فشرده‌تر شدن و تو هم دیگه قاطی نشدن.
حالا چیزی رو که تا اینجا گفتیم به صورت ریاضی بنویسیم. میانگین رو با u مشخص کردیم و واریانس رو با s.
حالا ببینیم چجوری مقادیر واریانس رو اینجا حساب کرده. واریانس بعد از مپ کردن داده‌هارو صرفا اومده WT رو توش ضرب کرده و به دست آورده.
چیزی که اینجا بهش واریانس میگیم در واقع واریانس نیست. جلوتر می‌بینیم که اسمش scatter matrix عه. ولی خب چرا؟ دلیلش چی بوده که اومده تقسیم بر تعداد کل داده‌هارو در نظر نگرفته؟ بخاطر این بوده که وقتی ما تو یه دسته تعداد داده‌هامون بیشتر میشه، یه جورایی فاصلمون از مرز بیشتر بشه، به این دلیل که چون تعداد داده‌ها تو اون دسته بیشتره، مطمئن‌تریم که درست‌تر دسته‌بندی انجام میشه. به عبارت دیگه کلاسی که داده بیشتری داره، بیشتر حواسمون باشه که غلط دسته‌بندی نکنیم.
تو روش LDA اومدیم تابع هزینه رو به صورت کسری نشون دادیم، می‌تونست نحوه‌های دیگه‌ای هم برای نمایش وجود داشته باشه. می‌خوایم فاصله میانگین‌هارو حداکثر کنیم و مقدار واریانس‌هارو حداقل. پس میانگین رو گذاشتیم تو صورت کسر و واریانس رو گذاشتیم تو مخرج کسر. حالا می‌خوایم محاسبات رو انجام بدیم و جواب مسئله بهینه‌سازی رو پیدا کنیم.
حالا چجوری محاسبات ریاضی رو انجام داده؟ اول صورت رو محاسبه کرده. صورت باید دوبار تو خودش ضرب بشه. ضرب دوم رو فقط جابجا کرده. چرا؟ برای اینکه بتونه راحت‌تر مشتق بگیره می‌خواد فرم نوشتن رو یکمی عوض کنه. اون دو تا پرانتز وسط رو که حاوی u1-u2 هست بعدا اسمشو عوض میکنه و یه ماتریس SB می‌گیره.محاسبات مخرج هم شبیه صورت انجام داده و صرفا فرم نوشتن رو تغییر داده.
بعد از انجام محاسبات به فرم زیر رسیدیم. الان از چیزی که به دست آوردیم خیلی راحت‌تر می‌تونیم مشتق بگیریم. حالا می‌خوایم تو مرحله بعدی چیزی که به دست آوردیم رو بهینه کنیم. یعنی نسبت به W ازش مشتق بگیریم و برابر با صفر قرار بدیم.
مراحل مشتق گرفتن هم تو تصویر زیر مشخصه. مشتق کسر چجوری حساب می‌شد؟ به صورت زیر:
(مشتق صورت × مخرج - مشتق مخرج × صورت) / مربع مخرج
برای جواب آخر اومده ضرایب رو که عدد ثابت بودن یه لاندا فرض کرده و با استفاده از اون جواب آخر رو نوشته. حالا جوابی که به دست اومده به صورت بسته نیست. در ادامه می‌خوایم برای W به یه جواب برسیم.
حالا می‌خوایم مسئله زیر رو به روش یکم ساده‌تر حلش کنیم به جای اینکه از حل بردار ویژه تو ماتریس‌ها استفاده کنیم.
چجوری حل کرده؟ SBW شده یه ضریبی از (u1-u2). حالا فقط اومده W رو تنها کرده و بقیه محاسبات رو انجام داده.
حالا SW-1 داره چیو نشون میده؟ یه جورایی پراکندگی داده‌ها در هر کلاس رو داره مشخص میکنه. در جلسات آینده جزییاتش رو خواهیم دید تو مباحث PCA.
پس الان جواب چیو داره مشخص میکنه؟ میگه همون فاصله زیاد بین میانگین‌هارو حفظ می‌کنم، از طرفی یه واریانسی رو هم در نظر می‌گیرم که داده‌های کلاسای مختلف تو هم دیگه نرن.
حالا بریم یه دور خلاصه کل روش LDA رو ببینیم. دسته‌بندی رو چطور می‌خوایم انجام بدیم؟
تا اینجا یه بردار تو فضا به‌دست آوردیم که داده‌هارو روش تصویر کنیم ولی هنوز دسته‌بندی رو انجام ندادیم. یعنی چی؟ یعنی یه مقداری رو مشخص کنیم که بهمون بگه اگه از اون مقدار عددی که به دست آوردیم بیشتر شد مثلا داده متعلق به دسته قرمزه، اگه کمتر شد متعلق به دسته آبیه. (این مورد رو یکم جلوتر توضیح میدیم.)
تا اینجا مثالایی که دیدیم همشون دو کلاسه بوده. حالا می‌خوایم ببینیم اگه مسئله چند کلاسه باشه چجوری باید حلش کنیم. دو راه حل کلی وجود داره:
در ادامه اول رویکرد دوم رو بررسی می‌کنیم بعد می‌ریم سراغ رویکرد اول.
برای راه‌حل دوم دو دیدگاه مختلف وجود داره:
میاد مسئله چند کلاسه رو دو دسته‌ای میکنه. دسته‌ای که می‌خواد بررسی کنه رو یکی از دسته‌ها در نظر می‌گیره، بقیه دسته‌هارو هرچند تا که باشن دسته دوم در نظر می‌گیره.
حالا اگه یه داده جدید بیاد چجوری تصمیم‌گیری کنیم که متعلق به کدوم دسته می‌تونه باشه؟ گاهی ممکنه نقطه جدید بدون هیچ ابهامی تو یک دسته قرار بگیره. مثل تصویر زیر. نقطه نارنجی جدید اومده ولی خب کاملا مشخصه که به کدوم دسته متعلقه.
ولی گاهی اوقات اینقدر راحت نیست و نقطه جدید ممکنه جایی باشه که نتونیم به سادگی تشخیص بدیم که متعلق به کدوم دسته‌س. اگه ابهام پیش بیاد در مورد یه نقطه میاد فاصله اون نقطه با مرزهارو در نظر می‌گیره، هرچقدر بیشتر باشه فاصله، به همون دسته اختصاص میده. الان تو تصویر زیر نقطه نارنجی رو نمی‌تونیم تشخیص بدیم که متعلق به دسته قرمزهاست یا سبزها. چه کنیم؟ چون فاصله نقطه نارنجی از مرز جدا کننده دسته سبز (خط قهوه تیره) بیشتره پس می‌تونیم بگیم متعلق به دسته سبزه.
این دیدگاه یه ایرادی داره. ممکنه داده‌های یک دسته رو نتونیم با خط جدا کنیم. مثلا داده‌ها زیر رو در نظر بگیرید. به صورت خطی از هم دارن جدا میشن ولی نمی‌تونیم با خط یکی رو در مقابل بقیه قرار بدیم. مثلا نمی‌تونیم با یک خط داده‌های سبز رو از آبی جدا کنیم. این ایراد تو دیدگاه بعدی حل میشه.
اینطوره که تو هر مرحله دو تا از دسته‌هارو فقط در نظر می‌گیریم و سعی می‌کنیم از هم جداشون کنیم. مثلا اول مثلث و دایره رو سعی می‌کنیم جدا کنیم. بعد مثلث و ضربدر رو جدا می‌کنیم. انگار سه تا مسئله جداسازی دو کلاسه داریم که باید جدا جدا حلش کنیم.
اگر تعداد کلاس هامون C باشه تعداد خطوطی که به دست میاد ترکیب (C, 2) میشه. یعنی به ازای هر دو دسته یه مرز باید پیدا بشه.
تابع f_ij(x) رو به این صورت تعریف می‌کنیم که: برای مرزی که دسته i ام رو از دسته j ام جدا می‌کند مقدار به دست آمده ترانهاده W_ij در X را مشخص می‌کند.
حالا یه داده جدید میاد چجوری تشخیص بدیم که متعلق به کدوم دسته‌س؟ یه راه اینکه بیایم تابع f_ij رو برای همه دسته‌ها حساب کنیم و ببینیم مقدارش چجوری میشه. مثلا برای دسته اول با بقیه دسته‌ها مثل زیر میشه:
بیایم تعداد توابعی رو که مثبت میشن بشمریم. هر کدوم که تعداد توابع مثبتش بیشتر بشه، یعنی انگار داده x متعلق به اون دسته س. حالا یه ابهامی پیش میاد. اگه مثلا تعداد مثبت‌ها درسته اول و دسته دوم یکسان بشه چجوری بفهمیم داده x متعلق به دسته اوله یا دسته دوم؟ تو این حالت میایم مقدار تابع زیر رو در نظر می‌گیریم بعد از رو عددی که این بهمون میده می‌تونیم مقایسه رو انجام بدیم و تصمیم بگیریم.
این روشا به صورت تئوری خیلی درست نیستن. چون اومدیم چند تا جوابی که مستقل از هم دارن به دست میان رو باهم مقایسه می‌کنیم. ولی در عمل خیلی کاربردی ان و خب ازشون استفاده می‌کنیم.
بریم در ادامه دو تا مثال ببینیم.
الان تو شکل سمت چپ، ما اومدیم هر دسته رو با یک خط از بقیه دسته‌ها جدا کردیم. اون ناحیه وسط که با قرمزمشخص شده ناحیه ابهامه. اگر داده‌ای اون وسط بیاد نمی‌دونیم باید به کدوم دسته بدیمش.
تو شکل سمت راست، اومدیم هر دو تا کلاس رو با یه خط از بقیه جدا کردیم. باز هم اون ناحیه قرمز ناحه ابهامه برامون. اگر داده‌ای اون وسط بیاد نمی‌دونیم باید به کدوم دسته بدیمش.
از نظر محاسباتی کدوم یکی از این دو روش بهتره؟ بستگی به مسئله داره. تو روش اول تعداد مسئله دسته‌بندی C تاست تو حالت دوم ترکیب (2, C) هست. مثلا اگه راه‌حل خطی باشه، روش اول بهتره، اگه پیچیده‌تر باشه، ممکنه روش دوم بهتر باشه که بتونیم جواب رو بشکنیم و با محاسبات کمتر به جواب برسیم.
خب، تا اینجا رویکرد دوم رو برای حل مسائل چند کلاسه دیدیم که خودش دو تا راه حل مختلف داشت. حالا بریم سراغ رویکرد اول که اینجوری بود که بیایم برای هر دسته یه تابع در بیاریم و با استفاده از مقایسه توابع تشخیص بدیم نمونه جدید متعلق به کدوم دسته‌س. فرق این دیدگاه با قبلی تو اینکه همه این توابع باهم train میشن.
با یک مثال جلوتر بیشتر توضیح میدیم. برای هر دسته یه تابعی رو در نظر می‌گیریم و چون مرزهارو جوری تعیین کردیم که مقادیر توابع باهم یکسان بشه دیگه منطقه ابهام وجود نداره اینجا. مثلا تابع دسته اول f1 باشه و تابع دسته دوم f2. مرز بین f1 و f2 از طریق f1 = f2 به دست میاد. پس دیگه ناحیه ابهام نداریم.
مثالی که در نظر داریم حل مسئله چند کلاسه با الگوریتم پرسپترون هست. می‌خوایم به ازای هر دسته یک بردار در نظر بگیریم. فرض کنید C تا دسته داریم پس باید C تا بردار در نظر بگیریم از 1 تا C. حالا یه داده جدید میاد. داده جدید رو تو تک تک وزن‌ها از 1 تا C ضرب می‌کنیم. حاصل هر کدوم بیشتر بشه، داده جدید رو به اون دسته اختصاص میدیم. جزییات الگوریتم پرسپترون رو در جلسه گذشته مفصل بررسی کردیم.
نکته‌ای که این دیدگاه با دیدگاه قبلی داره اینکه به صورت همزمان داره داده جدید رو از کلاسی که بهش متعلق نیست دور میکنه و به کلاسی که بهش متعلق هست نزدیک میکنه. بر خلاف دیدگاه قبلی که میومد جدا جدا حساب می‌کرد هر دفعه، این داره همزمان learn میکنه.
اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.
