جزوه دوره یادگیری ماشین دکتر مهدیه سلیمانی - جلسه نوزدهم - انتخاب ويژگی و روش PCA

سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.

محتوای این جلسه

در ابتدا ادامه بحث انتخاب ویژگی رو که از جلسه گذشته باقی‌مونده ادامه می‌دیم و سپس در مورد روش PCA صحبت خواهیم کرد.

مروری بر جلسه گذشته

در جلسه گذشته بحث انتخاب ویژگی رو شروع کردیم که به نوعی هدفش کاهش ابعاد هست. به این دلیل که خیلی اوقات نیاز داریم که ابعاد فضا رو کاهش بدیم، بعد داده‌هارو train کنیم. معیار Mutual Information رو دیدیم که نشون میداد چقدر ویژگی‌ها بهم وابسته هستند و هرچقدر این وابستگی بیشتر بود برامون مطلوب‌تر بود. یعنی به‌جای اینکه بیایم ویژگی‌هارو تکی تکی با target بسنجیم، مجموعه‌ای در نظر گرفتیم و با target مقایسه کردیم. در نهایت به یک مسئله جستجو رسیدیم.

الگوریتم کلی تمام چیزهایی که در موردش صحبت کردیم اینجا آورده شده. در هر مرحله اول یک سری ساب‌ست جنریت می‌کنیم، بعد ساب‌ست‌هارو ارزیابی می‎‌کنیم (یعنی چک می‌کنیم که ببینیم چقدر خوب هستن) و در نهایت یک شرط برای خروج داریم.

الگوریتم رو کی باید متوقف کنیم؟

• به یک تعداد فیچر خاص برسیم.
• یک تعداد ایتریشن خاص رو رد کنیم.
• به یک نقطه‌ای برسیم که کمینه محلی باشه.

مقایسه روش‌های فیلتر و Wrapper

روش‌های فیلتر به دسته‌بند دسترسی مستقیم ندارند. یک ساب‌ست انتخاب می‌کنن و اون رو به دسته‌بند میدن. ولی روش‌های wrapper اینطورن که هر دور برای اینکه ساب‌ست رو ارزیابی کنن، به خود دسته‌بند هم نیاز دارن و به صورت مستقیم باهاش در ارتباط هستن.

آیا به جز معیار Mutual Information که محاسبات سنگین داره، معیارهای دیگه‌ای برای بررسی خوب بودن ویژگی‌های یک subset وجود داره؟

یکی از معیارها می‌تونه استفاده از فاصله باشه. یعنی به این صورت که داده‌های دسته‌های مختلف فاصله‌شون از هم زیاد بشه و داده‌های درون یک دسته فاصله‌شون از هم کم بشه.

برای جستجو روش‌های مختلفی وجود داره که به صورت کلی به چند موردش تو اسلاید زیر اشاره شده:

به صورت کلی اگر با روش‌های complete سرچ کنیم محاسبات سنگینی خواهیم داشت. روش‌های هیوریستیک معمولا بهینه سراسری رو از دست میدن. روش‌های غیر قطعی به تیون شدن پارامترها بستگی دارن و اینکه چند دور الگوریتم رو ادامه بدیم.

تا اینجا، در مورد روش‌های انتخاب ویژگی صحبت کردیم و دو روش مختلف فیلتر و wrapper رو معرفی کردیم. همچنین تا حدی سرچ در ساب‌ست‌ها رو دیدیم.

در ادامه روش PCA رو بررسی خواهیم کرد.

روش PCA

تو این روش برخلاف روش قبلی که در جلسه گذشته دیدیم و از بین ویژگی‌ها تعدادی رو انتخاب می‌کردیم، می‌خواهیم ویژگی‌هارو به یک فضای جدید ببریم. اصطلاحا به این کار Feature Extraction گفته میشه. در واقع با یک تبدیل خطی این کار رو انجام خواهیم داد.

چرا همچین روش‌هایی برامون مهم هستن؟ به صورت کلی خیلی محتمل هست که در داده‌هایی که داریم فیچرهایی داشته باشیم که باهم خیلی کورلیشن داشته باشن. در این حالت می‌تونیم به‌جای اینکه هر دو ویژگی رو نگه داریم، فقط یکیش رو نگه داریم و فضا رو کاهش بدیم.

صورت مسئله: از فضای ویژگی اصلی که d بعدی هستن، می‌خواهیم داده‌ها رو به فضای d' بعدی ببریم. در روش PCA تبدیل بین رو حتما پیدا می‌کنیم. یک سری روش‌های دیگه وجود دارن که نقاط تبدیل یافته رو پیدا می‌کنن ولی نمی‌تون تبدیل رو پیدا کنن. همچنین روش PCA به صورت unsupervised هست و از برچسب‌ها استفاده‌ای نمی‌کنه.

کاهش ابعاد برامون فواید زیادی داره:

• اول اینکه داده‌ها با ابعاد بالا رو نمی‌تونیم به صورت بصری ببینیم که توزیعشون به چه صورت هست. پس وقتی ابعادشون رو به دو یا سه می‌رسونیم می‌تونیم دید بهتری نسبت به داده پیدا کنیم.
• کاربرد دیگه‌ش می‌تونه کامپرس کردن داده‌ها باشه. یعنی هم تبدیل مستقیم رو داریم هم تبدیل معکوس رو.
• می‌تونیم ازش بعنوان pre-process هم استفاده کنیم. باعث میشه جلوی overfitting گرفته بشه.
• می‌تونیم از این روش‌ها برای کاهش نویز استفاده کنیم.

تبدیل خطی

انگار یک ماتریس داریم که در ورودی‌هامون ضرب میشه و در نتیجه از روی ترکیبات خطی ورودی‌ها می‌تونیم یک سری ورودی جدید بسازیم.

هر بعد بردار جدیدی که ساخته میشه انگار ضرب داخلی یکی از ستون‌های ماتریس A در بردار ورودی است.

پس می‌خوایم از تبدیل خطی استفاده کنیم برای کاهش ابعاد. روش‌های دیگه‌ای هم وجود داره، اما در اینجا همشون رو نمی‌بینیم.

ایده Principal Component Analysis (PCA)

به هر کدوم از ستون‌های ماتریس A یک مولفه اصلی یا principle component گفته میشه. در ادامه خواهیم دید که چرا بهشون این اسم رو دادیم.

ایده کلی این روش به این صورت هست که در قدم اول میاد میانگین داده‌ها رو از تمامی داده‌ها کم میکنه. یعنی چی؟ یعنی میانگین جدید داده‌ها رو صفر می‌کنه. در قدم بعدی میاد اولین PC (اولین ستون ماتریس A) رو راستایی در نظر می‌گیره که اگه داده‌ها بهش map بشن، بیشترین واریانس رو خواهند داشت. دومین PC رو عمود بر اولین PC به صورتی در نظر می‌گیره که دوباره بیشترین میزان واریانس رو روش داشته باشه. همینطور الی آخر تمام PC ها رو به صورتی در نظر می‌گیره که همشون بر هم عمود باشن و بیشترین میزان واریانس رو داشته باشن.

برای درک بهتر تصویر زیر رو در نظر بگیرید. اگر تصویر داده‌هارو روی محور عمودی در نظر بگیریم، به نسبت تصویرشون روی محور افقی واریانس بیشتر دارن (یعنی انگار دقت بیشتری در نظر گرفتیم) در روش PCA همواره دنبال بردارهایی هستیم که این ویژگی رو داشته باشن و بیشترین میزان واریانس رو زمانی که دیتارو روشون تصویر می‌کنیم بهمون بدن.

اگر مقادیر ویژه ماتریس کواریانس یک توزیع گاوسی رو حساب کنیم و اون‌هارو از بزرگ به کوچیک مرتب کنیم، اون مقدار ویژه‌ای که بیشترین مقدار رو داره باعث میشه که واریانس داده‌ها نسبت به بردار ویژه‌ای که میسازه از بقیه بزرگ‌تر باشه. الان تو تصویر زیر مثلا می‌تونیم بردار v2 رو حذف کنیم و فقط بردار v1 رو نگه داریم. چون واریانس داده‌ها روش خیلی بیشتره نسبت به بردار v2.

گام‌های دقیق PCA

ماتریس X ماتریس داده‌هاست. در گام اول میانگین داده‌هارو محاسبه میکنه. سپس میانگین رو از ماتریس X کم می‌کنه. در گام بعدی ماتریس کواریانس داده‌هارو حساب می‌کنه. در مرحله بعدی بردارهای ویژه ماتریس کواریانس رو محاسبه می‌کنیم و بعد به ترتیب مقادیر از بزرگ به کوچیک مرتب می‌کنیم. ماتریس کواریانس d × d بعدی بود پس حداکثر d تا مقدار ویژه خواهد داشت. از این تعداد مثلا می‌خواهیم d' تاشو برداریم. حالا ماتریس تبدیل A رو (که بالاتر در موردش حرف زدیم) چجوری باید بسازیم؟ مقادیر ویژه‌ای که در نظر گرفتیم رو تو ستون‌های ماتریس A می‌ذاریم. تو مرحله آخر فقط کافیه ضرب ماتریس داده‌ها (که میانگین رو ازش کم کرده بودیم) و ماتریس A رو انجام بدیم.

حالا هر کدوم از این گام‌ها رو به صورت دقیق‌تر بررسی کنیم ببینیم چی شد. میانگین رو حساب کردیم. بعد ماتریس کواریانس رو باید تخمین بزنیم. اگر می‌خواستیم با روش likelihood تخمین بزنیم به صورت زیر میشد.

به صورتی دیگه اگر بیایم ماتریس X رو در ترانهاده‌ش ضرب کنیم و بر تعداد N (کل نمونه‌ها) تقسیم کنیم، در واقع به همون ماتریس کواریانس می‌رسیم. (از اینجا به بعد هر وقت ماتریس X رو داشتیم منظور ماتریس داده‌هاست که مقدار میانگین ازش کم شده)

حالا می‌خوایم در مورد این صحبت کنیم که چرا برداری که ماکسیمم واریانس رو داره برامون اهمیت داره و بعد اینو ببینیم که چرا این بردارها معادل با همون بردارهای ویژه هستن.

الان تو دو تصویر زیر، بردار دوم ترجیح بیشتری برامون داره، به این دلیل که واریانس داده‌ها روش خیلی بیشتر هست.

تعبیر دیگه‌ای میشه در نظر گرفت. به این صورت که به جای اینکه بگیم خطی خوبه که واریانس زیاد داشته باشه، خطی رو در نظر بگیریم که وقتی می‌خوایم نقاط رو روش تصویر کنیم فاصله کلی‌شون کم باشه. دیدگاه دوم هم تو تصاویر بالا واضح هست.

با استفاده از قضیه فیثاغورس میشه نشون داد که این دو دیدگاه باهم معادل هستن. خط سبز رنگ فاصله نقطه از مبدا هست و همواره ثابت هست. حالا برای اینکه این فاصله ثابت بمونه در صورتی که اندازه خط قرمز رو کم کنیم، اندازه خط آبی زیاد میشه. خط قرمز فاصله نقطه از خط رو نشون میده و خط آبی تصویر نقطه روی خط رو. (چیزی که دنبالش هستیم اینکه یا فاصله نقطه از خط کم بشه (خط قرمز)، یا تصویر شده نقطه روی خط فاصله بیشتری نسبت به راس پیدا کنه (خط آبی))

این رو هم در نظر داشته باشید که میانگین رو از داده‌مون کم کردیم و با نقاط جدید این کار رو می‌کنیم.

حالا چرا راستاهایی که بردار ویژه‌های ماتریس کواریانس هستند، بردارهایی با حداکثر مقدار واریانس هستند؟

تبدیلی که داشتیم به این صورت بود که ترانهاده ماتریس A رو در بردار x ضرب می‌کردیم و بردار x' رو به‌دست می‌آوردیم. حالا می‌خوایم ماتریس کواریانس رو در فضای جدید تشکیل بدیم و ببینیم که به چه صورتی میشه. یعنی می‌خوایم برای x' ماتریس کواریانس رو محاسبه کنیم. این ماتریس رو با R نمایش میدیم. حالا می‌خوایم ماتریس کواریانس در فضای اصلی رو بر حسب بردارهای ویژه بنویسیم. ماتریس A یک ماتریسی هست که ستون‌هاش مقادیر ویژه هستن و همه برهم عمود هستن. یعنی اگر حاصل‌ضرب A در ترانهاده A رو حساب کنیم به ماتریس همانی می‌رسیم.

اگر چرخش رو در فضا به صورتی انجام بدیم که بردارهای پایه‌مون بشن بردارهای ویژه ماتریس، تو اون فضا ماتریس کواریانس به صورت قطری میشه. یعنی ابعاد نسبت به هم عمود هستند. یعنی کورلیشن این بردارها 0 میشه.

حالا چرا برداری که واریانس داده‌ها روش زیاد هست متناظر میشه با بردار ویژه ماتریس کواریانس؟

ما از بین بردارهای مختلف دنبال برداری هستیم که اگر در x ضرب شد باعث بشه حاصل واریانس زیادی داشته باشه. فرض کنید این بردار رو با a نشون بدیم. واریانس x' هم که تبدیل یافته نقاط هستن رو به دست میاریم. حالا هدفمون اینکه مقدار این واریانس رو ماکسیمم کنیم. به عبارتی دیگه دنبال بردار a هستیم به صورتی که باعث بشه مقدار واریانس داده‌ها براش maximum بشه. این مسئله رو حالا چجوری میشه حل کرد؟ با تکنیک تابع لاگرانژ می‌تونیم حلش کنیم. حاصل این برابر میشه با راستایی که برابر با راستای بردارهای مقادیر ویژه باشه. یعنی اگه بردارهای ویژه رو در نظر بگیریم می‌تونیم بگیم که مقدار واریانس براش ماکسیمم میشه.

تا اینجا کاهش ابعاد رخ نداده اصلا. حالا می‌خوایم در مورد این صحبت کنیم که چجوری ابعاد رو کم کنیم و مهم‌ترین بعدهارو برداریم؟ بالاتر هم گفتیم بردارهای ویژه‌ای که مقادیر ویژه بزرگ‌تری دارن برامون اهمیت بیشتری دارن. حالا می‌خوایم از بین d تا بردار d' تا رو به همین صورت انتخاب کنیم. تبدیل خطی‌ای که خواهیم داشت از روی همین مقادیر ویژه و بردارهای ویژه به دست خواهد اومد. حالا یک x hat داریم که از روی مپ شده نقاط داره ساخته میشه. چی مد نظرمون هست؟ این که مقادیر تبدیل یافته و مقادیر اصلی تا حد ممکن بهم مقادیرشون نزدیک باشه. کل روابطی که پایین نوشته شده می‌خواد این رو نشون بده که در صورتی که بخوایم کمترین میزان خطارو داشته باشیم، باید مقادیر ویژه‌هایی با کمترین مقدار رو دور بریزیم. به عبارتی دیگه یعنی زمانی این خطا برامون کمینه میشه که مقادیر ویژه با کمترین مقدار توش بیان. یعنی مقادیر ویژه با بیشترین مقدار برامون بمونه و ازشون استفاده کنیم تا فضای جدید رو بسازیم.

مثال

فرض کنید یک سری تصویر از صورت اشخاص داریم. تعداد ابعاد میشه تعداد پیکسل‌های سطرها در ستون‌ها.

حالا می‌خوایم روی این فضا PCA بزنیم. اول میانگین چهره‌ها رو حساب کنیم. بعد از تمام عکس‌ها کم کنیم. اگه این تصاویر 100 × 100 باشند، فضایی که داریم 10،000 بعدی خواهد بود. حالا تو این فضا ماتریس کواریانس رو تشکیل میدیم، بردار ویژه‌های ماتریس کواریانس رو هم محاسبه می‌کنیم. هر بردار ویژه تو این فضا 10 هزار بعدی خواهد شد. چون فضا هم 10 هزار بعدی هست، هر بردار ویژه برابر با یک تصویر خواهد شد و می‌تونیم با همین تصاویر نشون بدیم. اصطلاحا اینجا بهشون eigenface گفته میشه.

الان تو تصویر پایین اومده 256 تا eigenface رو ترکیب خطیشو در نظر گرفته و در نهایت با تصویر میانگین جمع کرده و با این کار اومده تصویر اصلی اولیه رو با دقت خیلی خوبی بازسازی کرده. از فضای 112 × 92 ایی به فضای 256 بعدی رسیده ولی با این حال با دقت خوبی تصویرش رو ساخته.

تو تصویر پایین هم به ازای تعداد ابعاد مختلف خروجی رو مشخص کرده:

بخشی از مباحث این جلسه باقی‌موند که در جلسه بعدی ارائه خواهد شد.

جمع‌بندی مطالب گفته شده

با روش PCA آشنا شدیم که برای کاهش ابعاد فضا ازش استفاده میشه و به صورت خطی و unsupervised هست. روش کلی به این صورت بود که اول میانگین داده‌هارو حساب می‌کردیم، بعد از کل داده‌ها کمش می‌کردیم. بعد ماتریس کواریانس رو محاسبه می‌کردیم و بعد مقادیر ویژه رو براش به‌دست میاوردیم. سپس به کمک این مقادیر ویژه به یک فضای جدیدی رو با ابعاد کمتر می‌ساختیم. به این صورت بود که با بردارهای ویژه یک ماتریس می‌ساختیم و بعد در داده‌ها که مقدار میانگین ازشون کم شده بود ضرب می‌کردیم.

اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.

اسلایدهای این جلسه (بخش انتخاب ویژگی)

اسلایدهای این جلسه (بخش روش PCA)

ویدیو این جلسه

جزوه جلسه قبلی (جلسه هجدهم)

جزوه جلسه بعدی (جلسه بیستم)