جزوه دوره یادگیری ماشین دکتر مهدیه سلیمانی - جلسه سوم - رگرسیون خطی و گرادیان کاهشی

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

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

• دیدگاه Bayesian و Fully Bayesian (که از جلسه گذشته باقی‌مونده)
• رگرسیون خطی
• گرادیان کاهشی

دیدگاه Bayesian و Fully Bayesian

تو این دیدگاه برخلاف دیدگاه map و ml که میومدیم یه مقدار فیکس برای پارامتر در نظر می‌گرفتیم، نمی‌خوایم مقدار پارامتر رو یه مقدار فیکس در نظر بگیریم. مثلا دیدگاه ml اینجوری بود که میومدیم مقدار تابع likelihood رو حداکثر می‌کردیم و تو دیدگاه دوم که map بود، می‌خواستیم ببینیم بعد دیدن داده‌ها به کدوم مقدار پارامتر بیشتر معتقدیم و همون رو می‌خواستیم برگردونیم.

از اونجایی که دیتایی که داریم محدوده و هیچوقت بی‌نهایت نمیشه، پس همیشه اون توزیعی که به دست میاد یه واریانسی داره. حالا برای اینکه بتونیم از اطلاعات کل توزیع استفاده کنیم میریم سراغ دیدگاه Fully Bayesian.

حالا جزییات این دیدگاه به چه صورته؟

نمیایم مقدار پارمتر رو فیکس در نظر بگیریم. فرض می‌کنیم بعد دیدن داده‌ها مقدار p(theta | D) مثل شکل زیر شده باشه:

حالا ما به هر کدوم از این مقادیر پارامتر به یه اندازه‌ای اعتقاد داریم. برای اینکه همه مقادیر پارامتر رو در مدل نهایی دخیل کنیم، میایم میگیم مثلا اگر توزیع اصلیمون p(x | theta) یه توزیع گاوسی بوده، این توزیع رو میانگینشو جاهای مختلف فضا در نظر بگیر، بعد در نهایت همه رو بذار کنار هم اما هر کدوم رو با یه وزنی بهش اهمیت بده. (هر کدوم از این توزیع‌هایی که پایین اومده رو با یه وزنی قراره بذاریم کنار هم، بعد از همشون به یه توزیع واحد برسیم.)

حالا وزن رو چجوری به دست بیاریم؟

تو این انتگرال، اون قسمتی که دورش خط کشیدیم داره وزن رو بهمون نشون میده. اصلا (theta | D)p چی بود؟ همون توزیعی بود که بعد دیدن داده‌ها بهش رسیدیم و بالا هم عکسش هست. (یعنی بعد دیدن داده‌ها به اون پارامتری که داریم چقدر معتقدیم) و سمت چپش هم داره توزیع با اون مقدار پارامتر رو نشون میده.

یعنی به جای اینکه فقط یه توزیع در بیاریم با یه مقدار پارامتر مشخص که فیکس کردیم (مثل map یا ml) میایم همه این توزیعارو کنار هم میذاریم و یه توزیع کلی در میاریم.

حالا باید چیکار کنیم؟

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

این دیدگاهی که میاد همه پارمترهارو دخیل میکنه و یه مقدار واسش فیکس نمیکنه رو میگیم Fully Bayesian، دیدگاه map رو که میاد یه مقدار فیکس میکنه برای پارامترا میگیم Bayesian.

چه موقع جوابی که دیدگاه Fully Bayesian داره با جواب map یکی میشه؟

زمانی این اتفاق میفته که واریانس خیلی خیلی کم بشه.

از اونجایی که مقدار این توزیع به جز یه نقطه تو بقیه نقاط صفره (یعنی وزنمون فقط در یک نقطه غیر صفره) وقتی در توزیع‌های دیگه ضرب میشه باعث میشه که فقط یه توزیع از بین همه توزیع‌ها باقی بمونه. که جواب نهایی با همون جواب map یکسان میشه.

مثال از Bayesian

همون مثال توزیع برنولی رو که تو جلسه گذشته هم بررسی کردیم، در نظر بگیریم.

• جنس prior رو شبیه توزیع بتا در نظر می‌گیریم.
• طبق محاسباتی هم که داشتیم دیدیم که posterior هم از جنس بتا شد فقط پارامتراش متفاوت بود.

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

حالا جواب انتگرال به شیوه زیر محاسبه میشه:

حالا چرا میاد از expectation برای حل انتگرال استفاده میکنه؟

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

حالا میاد جوابی که به دست آورده رو تو حالتی که x=1 هست محاسبه می‌کنه. تو توزیع برنولی اگه x برابر با 1 باشه جوابش میشه تتا:

بعد، تو توزیع بتای جدیدی که به دست آوردیم، مقادیر آلفا 0 و آلفا 1 مثل زیر به دست اومده:

درنهایت، با توجه به فرمول expectation توزیع بتا میاد با این مقادیر جدید، expectation رو براش حساب می‌کنه:

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

جمع‌بندی و خلاصه سه دیدگاه

اگه تو دیدگاه map توزیعی که به دست میاریم، تو یه نقطه به شدت پیک بزنه، مقدارش با جواب Bayesian یکی میشه.

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

معمولا بخاطر انتگرال‌گیری و سختی حدس زدن مقدارش از Bayesian استفاده نمیشه.

رگراسیون خطی

با یک مثال به توضیح این موضوع می‌پردازیم.

ویژگی‌های خونه رو بعنوان ورودی داریم و می‌خوایم قیمت خونه رو بعنوان خروجی تخمین بزنیم.

چون یه سری نمونه رو برای train در اختیار داریم و قراره برای نمونه‌های جدید تخمین بزنیم، مسئله میشه یادگیری با ناظر.

برای حل مسئله لرنینگ چه گام‌هایی داریم؟

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

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

مرحله آخر هم ارزیابی تابعی هست که به دست آوردیم.

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

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

حالا، بریم سراغ مدل‌های خطی برای فضای فرضیه. شاید به نظر برسه مدل‌های خطی خیلی محدود کننده باشن ولی این فرضی که ما میذاریم و مدل خطی تعریف می‌کنیم رو می‌تونیم تعمیم بدیم به مدل‌های غیر خطی.

برای سادگی کار، فرض کنید مسئله‌مون تک متغیره است (یعنی یه ویژگی ورودی داریم) و قراره خروجی رو تخمین بزنیم.

اگه مسئله چند متغیره باشه، مقادیر مختلف برای w رو در قالب یه بردار نمایش میدیم و به صورت بردار در نظر می‌گیریم.

خب حالا تا اینجا، فضای فرضیه رو انتخاب کردیم.

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

حالا مسئله بهینه‌سازی جنسش چی باید باشه؟ همین چیزی که دنبالش هستیم. یعنی کاری کنیم تابع f به اون هدف ناشناختمون نزدیک بشه. می‌خوایم مجموعه پارامترهایی رو انتخاب کنیم که تقریب خوبی برای تارگت به دست بیاریم.

دو مرحله باید طی کنیم:

• در نظر گرفتن یه معیار برای خطا که بفهمیم چقدر فاصله داریم با هدف
• معیار خطایی که به دست آوردیم رو از طریق مسئله بهینه‌سازی حداقلش رو پیدا کنیم

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

مجموعه train رو بگیریم و پارامترای یه تابع پارامتری رو گزارش کنیم. این تابع پارامتری چیه؟ همون تابعی که می‌خوایم بعنوان تابع تخمین در نظر بگیریم.

دو مرحله ای که داشتیم:

• یه راه برای اینکه ببینیم چقدر تابع f تقریب خوبی برای تارگت هست
• از بین wهای مختلف کدوم مقدار وزن باعث میشه تا مقدار بهتری برای تارگتمون بدست بیاد

حالا بریم سراغ تعریف معیار خطا

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

یه راه برای اینکار، اینکه بیایم مقدار این تابع رو در تک تک نقاط train حساب کنیم و ببینیم که چقدر فاصله داره با همون نمونه‌های واقعی آموزش.

یه معیار خطای مشهور، خطای مربعی هست که از همون اینجا استفاده کردیم. حالا برای اینکه برای همگی نقاط حساب کنه اومده این خطارو تو همه نمونه‌ها نگاه کرده و در نهایت تابع هزینه (cost function) رو از جمع همشون تعریف کرده.

تا اینجا یه تابع هزینه ساده در نظر گرفتیم که شد مجذور خطا تو تمامی نقاط.

حالا تا الان فضای فرضیه رو انتخاب کردیم و همچنین انتخاب کردیم که دنبال حداقل کردن چه هستیم. قدم بعدی اینکه وزنی رو پیدا کنیم که کمترین هزینه رو داشته باشه. به همین دلیل میایم تابع ضرر یا loss function رو تعریف می‌کنیم. (که یه جورایی همون بازنویسی شده تابع هزینه‌ای هست که بالا تعریف کردیم.)

خیلی از الگوریتم‌ها یه تابع هزینه (cost) دارن که میشه مجموع ضررها (loss)

از این به بعد وقتی بگیم loss function منظورمون خطایی هست که بعنوان مزر بین چیزی که تخمین زدیم و چیزی که تارگت ما بوده در نظر گرفتیم.

حالا از جمع loss functionها روی نمونه‌ها، cost function به دست اومد که می‌خوایم اونو بهینه کنیم:

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

حالا می‌خوایم وزنی رو پیدا کنیم که این تابع هزینه رو برامون کمترین حالت ممکن کنه.

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

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

حالا این ضربدر قرمز رو تو شکل سمت راست جابجا کنیم خروجی‌ش رو تو شکل سمت چپ میتونیم ببینیم که چطور میشه. (یعنی به ازای تابع هزینه‌های مختلف، می‌تونیم ببینیم که تابعی که از روی پارامترهای w0 و w1 ساخته میشه به چه شکلی در میاد)

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

حالا در ادامه، می‌خوایم تابع هزینه‌ای که به دست آوردیم رو حداقل کنیم. (بهترین تابع هدف رو انتخاب کنیم.)

برای این‌کار، می‌تونیم از تابع هزینه نسبت به w مشتق بگیریم و برابر با 0 قرار بدیم.

از اونجایی که بردار w دوتا مقدار مختلف داره، پس یه بار نسبت به w0 مشتق می‌گیریم برابر 0 میذاریم، یک بار هم نسبت به w1.

در نهایت یه دستگاه معادله به‌دست میاد که می‌تونیم حلش کنیم و جواب‌ها رو به دست بیاریم.

حالا بریم سراغ حالت کلی ببینیم وقتی dتا ورودی داریم، جوابمون چه شکلی میشه. (تو این مثال که دیدیم، ورودی‌مون تک متغیره بود.)

دنبال مینیمم کردن تابع هزینه هستیم (مقداری برای w پیدا کنیم تا تابع هزینه کمینه بشه)

از لحاظ شهودی:

• وقتی یه ورودی داریم، دنبال پیدا کردن یک خط هستیم
• وقتی دو تا ورودی داریم، دنبال پیدا کردن یک صفحه هستیم
• وقتی d تا ورودی داریم، دنبال پیدا کردن یک ابر صفحه هستیم

که تابع هزینه رو برامون کمینه کنه.

حالا الان تو شکل پایین حالتی رو نشون داده که دو تا ورودی داریم و دنبال یک صفحه هستیم به طوری که تابع هزینه رو برامون کمینه:

حالا بریم سراغ حل کردن همون مسئله پیدا کردن کمترین تابع هزینه با d تا ورودی:

تو روابط پایین سعی کرده همون روابط رو به شکل ماتریسی و برداری بنویسه.

از اونجایی که اندازه ماتریس از فرمول زیر به دست میومد:

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

فرق این مشتق‌گیری با مشتق گرفتن تو حالت عادی اینکه چون x ماتریسه، بجای اینکه خودش بیاد ضرب بشه در ماتریس دوم، ترانهاده‌ش رو اومده ضرب کرده. (برای جزییات بیشتر راجع به مشتق‌گیری در ماتریس‌ها بخونید.)

در نهایت برای به دست آوردن w اومده از سمت چپ هر دو طرف معادله رو در وارون X^TX ضرب کرده.

تو جبر خطی به ماتریس +X که تو عکس پایین اومده، میگیم شبه معکوس. دلیلش چیه؟

چون ممکنه ماتریس X معکوس نداشته باشه و مربعی نباشه پس از روش یه ماتریس مربعی ساختیم و ازش وارون گرفتیم. اگه از سمت راست یه ماتریس X ضرب کنیم باعث میشه X در شبه معکوسش بشه ماتریس همانی (I).

مسئله‌ای که دنبالش بودیم اینجا حل شد و جوابش به صورت بسته به دست اومد. حالا یه سوالی پیش میاد، چرا می‌تونیم ادعا کنیم که در اکثر مواقع این ماتریسی که باهاش روبرو هستیم وارون داره؟

اکثرا تو مسائلی که باهاش روبرو هستیم تعداد ویژگی‌ها (d) محدوده و تعداد نمونه‌ها (N) خیلی زیاده. خیلی نادره که ماتریس فول رنک نشه برای همینم مشکلی پیش نمیاد برای وارون ماتریس (تقریبا اصلا پیش نمیاد که تعداد نمونه‌هامون از تعداد فیچرها کمتر بشه)

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

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

آشنایی با تکنیک‌های دیگر بهینه‌سازی

تابع هزینه (cost function - J) اینو برای ما مشخص میکنه که هر کدوم از بردارهای پارامتر برامون چقدر هزینه داره. یعنی باعث میشه تخمین بدی داشته باشیم.

یه راه برای بهینه‌سازی استفاده از روش‌های تکراریه (Iterative)

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

یه روش معروف برای اینجام این کار گرادیان کاهشی است.

در ادامه می‌خوایم ببینیم که چجوری به کمک روش گرادیان کاهشی بیایم و تابع هزینه رو کمینه کنیم.

گرادیان کاهشی

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

قبل اینکه بحث روش گرادیان کاهشی رو ادامه بدیم، اول بفهمیم حرف بالا یعنی چی و چرا بعد ادامه الگوریتم رو بررسی خواهیم کرد.

چرا حرکت در خلاف جهت گرادیان باعث میشه بیشترین میزان کاهش رو در تابع داشته باشیم؟

اینکه یکم بالاتر گفتیم "بیشترین کاهش رو در مقدار تابع داشته باشیم" یعنی کاری کنیم تا مثلا در مثال زیر به نقطه مینمم تابع برسیم. چرا به نقطه مینمم برسیم؟ چون تو اون نقطه پارامترهای ما مقداری رو خواهند داشت که به ازای اون‌ها مقدار تابعِ هزینه کمترین مقدار ممکن میشه. برای همین دنبال نقطه مینمم هستیم. مثلا تو نمودار زیر محور عمودی داره تابع هزینه رو نشون میده و محور افقی داره مقدار پارامترها رو نشون میده. ما دنبال این هستیم که نقطه مینمم تابع زیر رو پیدا کنیم. نقطه مینمم‌ش میشه جایی که با دایره نارنجی تو شکل پایین مشخص شده.

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

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

حالا اگه من در جهت شیب خط که همون جهت خط سبز رنگه و معادل هست با همون مشتق که یه جورایی میشه همون گرادیان، حرکت کنم، به عبارتی دیگه، یعنی در جهت گرادیان حرکت کنم که میشه جهت همون فلش قرمز رنگ که تو تصویر پایین مشخص شده، دارم از نقطه مینمم دور میشم! هدف اینکه در نهایت به نقطه مینمم برسم، یعنی در جهت فلش زرد رنگ حرکت کنم. حالا چجوری باید حرکت کنم که بهش برسم؟ باید در جهتی برم که بیشترین میزان کاهش رو دارم و تو این مثال یعنی در خلاف جهت گرادیان حرکت کنم! خلاف یه چیزی رو در ریاضیات با منفی اون چیز نشون میدیم. یعنی اگه جهت گرادیان رو با نماد ∇ نشون بدیم، خلاف جهت گرادیان میشه ∇- که جلوتر در الگوریتم گرادیان کاهشی خواهیم دید.

اطلاعات اضافه ولی جالب در مورد نماد گرادیان!

گرادیان رو در ریاضیات با نماد دلتای برعکس نشون میدیم و بهش دِل میگیم. یعنی اینجوری ∇. حالا خود دلتا چیه؟ خود دلتا که نمادش اینجوریه ∆ بهمون اختلاف یک چیز رو نشون میده. مثلا اگه من بخوام اختلاف زمان رو در دو لحظه مختلف حساب کنم، می‌تونم بگم تغییرات زمان (t∆) برابر هست با زمان در لحظه دوم (t2) منهای زمان در لحظه اول (t1) یعنی اینجوری t = t2 - t1∆.

حالا چرا گرادیان نمادش دلتای برعکسه؟ شاید چون ما تو گرادیان تغییرات رو نسبت به یک متغیر در نظر نمی‌گیریم، بلکه نسبت به چند متغیر در نظر می‌گیریم، برای همین از همون دلتا که داشت تغییرات یک چیز رو نشون میداد، ولی به‌صورت برعکس استفاده شده!

چیزی که برای جهت شیب مثبت ارائه شد، برای جهت شیب منفی هم برقراره که دیگه اون رو خودتون تحلیل کنید. امیدوارم الان متوجه شده باشید که چرا حرکت در خلاف جهت گرادیان باعث میشه بیشترین میزان کاهش رو در تابع داشته باشیم و مثلا تو مثال بالا به نقطه بهینه برسیم.

حالا، اگه مثالمون به‌جای دره، قله داشت و به جای نقطه کمینه، دنبال نقطه بیشینه بودیم، آیا همچنان حرکت در خلاف جهت گرادیان اوکی بود؟ منطقاً نه. چون تو این حالت دنبال بیشترین میزان کاهش نیستیم، بلکه دنبال بیشترین میزان افزایش هستیم و باید در جهت گرادیان حرکت کنیم.

حالا، اگر مثالمون به جای یک نقطه کمینه دارای چند تا نقطه کمینه بود اون وقت چی میشد؟ در ادامه همین مطلب توضیح دادیم.

ادامه الگوریتم...

حالا همونطور که یکم قبل‌تر گفتیم می‌خوایم تو هر مرحله مقدار بهتری برای w پیدا کنیم تا مقدار تابع هزینه کم و کمتر بشه و هر دفعه مقدار w رو با مقادیری که مارو به هدفمون نزدیکتر می‌کنه آپدیت می‌کنیم.

حالا مقدار w رو چجوری آپدیت کنیم؟ از الگوریتم گرادیان کاهشی استفاده کنیم! چجوری؟ بالاتر به این نکته اشاره کردیم که بیشترین میزان کاهش برای یه نقطه در فضا در راستای خلاف جهت گرادیانه. پس بیایم از همین ایده استفاده کنیم و سعی کنیم مقدار w رو هر دفعه آپدیت کنیم. (فرضمون هم اینکه تابع هزینه مشتق‌پذیره)

ضریب اتا داره میگه تو هر مرحله تغییرات چقدر باشه. در واقع پارامتریه که داره نرخ یادگیری رو مشخص می‌کنه. اگر این ضریب رو تا حد خوبی کوچیک در نظر بگیریم می‌تونیم مطمئن بشیم که مقدار تابع هزینه در زمان t+1 از زمان t قطعا کوچکتر و یا مساویه.

چند تا ورژن مختلف برای گرادیان کاهشی داریم که تو برخی‌شون این امکان وجود داره که ضریب اتا تو هر دور تغییر کنه و همواره یه مقدار ثابت نباشه.

مشکل گرادیان کاهشی برای بهینه‌سازی چیه؟

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

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

پس چی شد؟ در گرادیان کاهشی وابسته به نقطه شروع هستیم و با توجه به نقطه شروع ممکنه مسیری رو بریم که باعث بشه تو کمینه محلی گیر کنیم.

اما...

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

بریم سراغ ادامه حل مسئله‌ای که داشتیم، می‌خواستیم تابع هزینه رو به کمک گرادیان کاهشی کمینه کنیم.

تعبیر شهودی خط آخر این اسلاید برای آپدیت کردن وزن، به این صورته که مثلا اگه جواب داخل پرانتز مثبت بشه (یعنی چیزی که تخمین زدیم از مقدار واقعی کمتر شده باشه) انگار اومده بردار W در زمان t رو با ضریبی مثبت از بردار X جمع میزنه. (در واقع بردار X در یک عدد مثبت ضرب شده که همون حاصل پرانتز بوده). حالا چرا جمع میکنه؟ انگار داره سعی میکنه بردار W و بردار X رو بهم نزدیک‌تر کنه. چرا نزدیک‌تر کنه؟ چون باعث میشه تو دور بعدی حاصل ضربِ داخلی بردار X و W (داخل پرانتز) یک عدد بزرگ‌تر بشه نسبت به حالت قبلی و چون عدد بزرگتری شده نسبت به حالت قبل، پس انگار تفاضلش از y مقدارش کمتر شده پس یعنی چیزی که تخمین زده به y نزدیک‌تر شده.

برای حالتی که داخل پرانتز مقدارش منفی هم میشه همچین تعبیر مشابهی داره.

برای درک بهتر این مثال رو در نظر بگیرید. مثلا مقدار y برابر با 10 باشه. حالا تو مرحله اول مقدار ضرب داخلی WX مثلا بشه 6. تو مرحله بعدی این مقدار ضرب داخلی WX بیشتر بشه یکم نسبت به حالت قبل و مثلا برابر شه با 7. حالا قبول دارید که حاصل تفریق 7-10 کوچیکتر از 6-10 هست دیگه؟ پس یعنی انگار تو مرحله دوم چیزی که تخمین زدیم یه قدم بیشتر به y نزدیک‌تر شده.

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

حالا چیزی که تا اینجا دیدیم روش گرادیان کاهشی به شیوه batch بود. می‌تونیم با یکم تغییر، حالت stochastic رو هم از رو همین به‌دست بیاریم. تو شیوه batch اینطوره که تو هر دور که میخوایم بردار W رو آپدیت کنیم، باید همه داده‌هارو یه دور ببینیم (بخاطر اون سیگما که میاد تو هر دور یه بار جمع حساب می‌کنه) تا بتونیم بردار وزن رو آپدیت کنیم.

پارامتر اتا (نرخ یادگیری)

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

حالا بریم تو چند شکل ببینیم که الگوریتم گرادیان کاهشی چجوری کار می‌کنه و تو هرقدم چجوری میره جلو.

دیدیم که در نهایت به بهترین خطی که می‌تونست وجود داشته باشه رسیدیم. (همون چیزی که دنبالش بودیم از اول)

نسخه stochastic گرادیان کاهشی

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

به جای اینکه تو هر دور با سیگما کار کنیم، هر دور با خود همون یه داده کار می‌کنیم. البته لازم هم نیست که با یک بار دیدن داده‌ها به جواب برسیم. ممکنه لازم باشه چندین دور داده‌هارو ببینیم تا به جواب برسیم. (ترتیب دیدن نقاط هم تو جوابمون ممکنه تاثیرگذار باشه)

فرمول کاملش تو عکس زیر اومده. به این رابطه جدیدی که برای آپدیت کردن وزن‌ها به دست اومد اصطلاحا LMS گفته میشه.

حالا اصلا مزیت این روش نسبت به روش قبلی چیه؟

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

ارزیابی مدل و تعمیم‌پذیری

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

حالا در ادامه اول با دو تا مفهوم مختلف آشنا میشیم بعدشم یه مثال می‌بینیم.

مفهوم Empirical Training Loss

میانگین مجذورات خطا در نمونه‌های آموزش رو بهمون نشون میده.

مفهوم Expected Test Loss

بیایم از مجذورات خطا expectation بگیریم. یعنی اگر توزیع رو بشناسیم و بدونیم که نمونه‌هامون (مقادیر x و y) از چه توزیعی میان مقدار expectation رو براش حساب کنیم. در واقع ما باید دنبال یک‌سری پارامتر باشیم که مقدار f(x; theta) رو برامون حداقل کنه. چرا؟ چون می‌خوایم روی داده‌های جدید خوب عمل کنیم و پیش‌بینی خوبی رو نمونه‌های جدید داشته باشیم که از قبل نداشتیم و منطقا مقدار y نمونه‌های جدید رو هم در اختیار نداریم.

حالا ما دنبال یه سری روش هستیم که به کمکش مشخص کنیم که وقتی که مقدار Empirical Loss کم هست، حدس بزنیم که آیا مقدار Expected Loss هم کم هست یا نه.

چجوری این کار رو انجام بدیم؟

یک راه برای جواب دادن به این سوال اینکه از همون اول کاری بیایم یک سری نمونه آموزش رو بعنوان test کنار بذاریم و کلا تو مدل ازشون استفاده نکنیم بعد اینجا ازشون استفاده کنیم. (بعدا راجع به جزییاتش مفصل توضیح میدیم.)

در ادامه اول بریم یه مثال ببینیم و به کمک اون یک سری موارد دیگه رو بررسی کنیم.

تعداد نمونه‌های train چقدر تاثیرگذار هستن؟

به کمک یک مثال که با رگراسیون خطی حل شده می‌خوایم این مورد رو بررسی کنیم. اول از همه، 10 تا نمونه داشتیم. بعد تعداد نمونه‌هارو به 20 تا افزایش دادیم و بعد تعداد نمونه‌هارو به 50 تا رسوندیم. تو هر مرحله سعی کردیم خطی رو از نمونه‌ها عبور بدیم که کمترین میزان مجذورات خطارو داشته باشه.

در نهایت هر سه تا خط و همچنین خط اصلی که جوابمون بوده رو تو یک نمودار رسم کردیم. همونطور که تو عکس هم واضحه، جواب اصلی خیلی نزدیک به حالیته که 50 تا نمونه داشتیم.

حالا یه نمودار دیگه داریم که داره میانگین مجذورات خطا رو بر اساس تعداد نمونه‌های آموزش مشخص می‌کنه. همونطور که مشخصه میزان MSE تا یه حدی که نمونه‌هارو افزایش دادیم کاهش پیدا کرده ولی از یه جایی به بعد دیگه ثابت مونده و دیگه تغییری نکرده (با وجود اینکه تعداد نمونه‌های آموزش زیاد شدن).

حالا دلیلش چیه؟ چرا این خطا 0 نمیشه؟

بخاطر اینکه بهترین خطی هم که پیدا بشه بازم یه نویزی داره و اینجوری نیست که بهترین خط از رو همه‌ی نمونه‌ها بگذره پس باعث میشه که مقدار MSE هیچوقت 0 نشه.

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

انواع خطا در مسئله رگراسیون خطی

این مبحث و مسائل مربوط به آن به صورت کامل در این جلسه ارائه نشدند و بخشی از آن به جلسه بعدی موکول شد. جزوه آن به صورت یکجا با مطالب جلسه بعدی ارائه خواهد شد.

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

• دو دیدگاه Bayesian و Fully Bayesian رو بررسی کردیم.
• با رگراسیون خطی که به صورت بسته جوابی که می‌خواستیم رو بهمون می‌داد آشنا شدیم.
• با روش گرادیان کاهشی به صورت batch آشنا شدیم.
• روش گرادیان کاهشی به صورت stochastic رو دیدیم.
• به صورت کلی در مورد مفاهیم ارزیابی مدل بحث کردیم.

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

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

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

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

جزوه جلسه بعدی (جلسه چهارم)