چند وقت پیش که دکتر شمسی عزیز الگوریتم گرادیان کاهشی تصادفی رو سر کلاس توضیح دادن، من یاد یه قسمت از برنامه کتاب‌باز افتادم. موضوع برنامه در مورد روابطمون با نزدیکانمون بود. یه جایی سروش صحت یه ورق ورداشت و چند تا نقطه روی کاغذ کشید بعد خودکار رو از دور به این نقاط نزدیک کرد و نشون داد که اول کار به همه نقاط نزدیک میشیم اما از یه جایی به بعد نزدیک شدن به بعضی نقاط باعث دور شدن از بقیه میشه. همینم شد که ایده این مقاله اومد تو ذهنم. این که چجوری رابطمون رو با بقیه بهینه کنیم؟ یا به صورت کلی‌تر چجوری بین اهدافمون تعادل برقرار کنیم؟ برای اینکه با ابزارهای بهینه‌سازی این سوال رو بررسی کنیم نیاز داریم که یکم با مسائل بهینه‌سازی آشنا بشیم. یه مسئله بهینه‌سازی به شکل زیر تعریف میشه :
رابطه بالا به زبان ساده میخواد از بین نقاطی که شرایط لازم و دارن اونی رو پیدا کنه که کمترین مقدار رو در تابع f میگیره. این کلی‌ترین تعریف مسئله بهینه‌سازی است و منطقا سخت‌ترین. یه دسته راحت‌تر از مسائل بهینه‌سازی هستند که قید ندارن و به صورت زیر تعریف میشن :
تو این مقاله ما با این مسائل سر و کار داریم. فقط توجه کنیم که تو تعریف بالا x با حرف درشت نوشته شده یعنی اینکه خودش یه بردار هست :
حالا که با تعریف مسئله آشنا شدیم میخوایم یک راه حل عددی برای حل مسئله بالا ارائه بدیم. منظور از روش عددی روشی هست که از یک حدس اولیه شروع میکنه و تو هر گام سعی میکنه به جواب اصلی نزدیکتر بشه. یکی از راه‌حل‌های معروف، روشِ گرادیانِ کاهشی هست. قبل از اینکه وارد روش گرادیان کاهشی بشیم بیاید یک مسئله رو به عنوان نمونه بگیریم و یه نگاهی به نمودارش بندازیم :
اگه تابع بالا رو تو فضای سه‌بعدی رسم کنیم به صورت زیر میشه:
به شکل بالا دقت کنید. صفحه کف، مقدار x و y رو نشون میده و ارتفاع، مقدار تابع در این نقطه یعنی f(x, y) رو نشون میده. میبینیم که تابع تو نقطه (0, 0) کمترین ارتفاع رو داره و در نتیجه نقطه بهینه ما، (0, 0) هست. صفحه کف جایی هست که ما باید داخلش جستجو کنیم. فرض کنید تو این صفحه استادید و به دنبال یک کلید می‌گردید. کلید در نقطه (0, 0) قرار داره. هر چقدر که این نقطه نزدیکتر باشید جریمه کمتری دارید و مقدار تابع تو اون نقطه کمتر هست. تو روش گرادیان کاهشی مثل سایر روشهای عددی یک نقطه اولیه در نظر میگیریم یعنی به تصادف یه جای صفحه کف قرار میگیریم و بعد سعی میکنیم تو هر مرحله یه ذره به جواب نزدیکتر شیم.
دوباره خودتون رو روی صفحه کف تصور کنید. می‌خواید دنبال کلید بگردید و یه تابعی هست که به شما میگه چقدر از کلید فاصله دارید. رو صفحه کف یه تعداد دایره رسم شده. روی یکی از اون دایره‌ها حرکت کنید. مقدار تابع چه تغییری میکنه؟ همون طور که متوجه شدید مقدار تابع هیچ تغییری نمیکنه. در واقع حرکت کردن رو دایره‌ها بیهوده است و باید به سمت دایرههای داخلی‌تر حرکت کنیم.
نمودار کانتور تو شکل بالا همین دایره‌ها رو مشخص میکنه. در واقع نمودار کانتور همه اطلاعاتی که میخوایم رو به ما میده و خوبیش هم اینه که تو صفحه دو بعدی قابل رسم هست.
حالا میریم سراغ این که چجوری از یک نقطه دلخواه به سمت کمینه حرکت کنیم.
شکل بالا رو نگاه کنید. نقطه سبز نقطه شروع ما رو نشون میده. چیزی که ما میخوایم اینه که به سمت دایرههای داخلی‌تر حرکت کنیم و تنها اطلاعاتی که داریم ضابطه تابع هست. چیزی که نیاز داریم یک جهت هست، یک جهت که به سمت دایرههای داخلی‌تر اشاره کنه. گرادیان این کار رو برامون انجام میده :
این فرم کلی گرادیان هست. وارد جزئیات محاسبه‌اش نمی‌شم چیزی که باید بهش توجه کنیم اینه که گرادیان تابع f تو یک نقطه یک بردار هست. تو شکل پایین قرینه گرادیان تو نقطه اول با یه بردار قرمز مشخص شده:
همونطور که میبینیم این جهت به دایرههای داخلی تر اشاره میکنه. حالا اگه تو این جهت یک قدم برداریم به نقطه دوم میرسیم. دوباره گرادیان تابع در نقطه جدید رو محاسبه میکنیم و قرینه اون رو به عنوان جهت کاهشی در نظر میگیرم و یک قدم دیگه بر میداریم. نمودار بعدی ۲۰ تا تکرار رو نشون میده. میبینیم که نقطه آخر خیلی به جواب اصلی نزدیک شده.
یه جایی که این روش گرادیان کاهشی خیلی به کار میره تو الگوریتم‌های یادگیری ماشین هست. مثلا مسئله رگرسیون رو در نظر بگیرید. m داده داریم که هر کدوم یه برچسبی دارن به عنوان مثال فرض کنید ۱۰۰ تا داده داریم که هر کدوم اطلاعات فردی یک دانش‌آموز رو مشخص میکنن و به هر کدوم از این داده‌ها یک برچسب زدیم که نمره درس ریاضیشون چنده. با استفاده از این ۱۰۰ تا داده یک مدل میسازیم که با استفاده از اطلاعات فردی یک دانش‌آموز نمره درس ریاضیش رو پیشبینی کنه. حالا برای اینکه مدل ما عملکرد خوبی داشته باشه یک تابع هزینه در نظر میگیریم که باید اون رو کمینه کنیم :
تو مثال ما yi نمره واقعی دانش‌آموز i ام رو مشخص میکنه و predictioni نمره‌ای که مدل برای دانش‌آموز i پیشبینی کرده. جریمه کلی‌ای که برای مدل در نظر میگیریم مجموع جریمه هر کدوم از نمونه‌ها هست. برای هر کدوم از الگوریتم‌های یادگیری ماشین تابع هزینه مشخص هست و میشه ازش گرادیان گرفت و روش گرادیان کاهشی رو براش اعمال کرد. شاید تا حالا اسم روش گرادیان کاهشی تصادفی به گوشتون خرده باشه. این هم یک الگوریتم بهینه‌سازی هست که از همون ابزار گرادیان استفاده میکنه و به علاوه دقت کمتری از روش گرادیان کاهشی داره. خب سوالی که پیش میاد اینه که اگه روش گرادیان کاهشی دقت بیشتری داره و میتونیم هم ازش استفاده کنیم چرا میریم سراغ نسخه تصادفیش؟ چون روش تصادفی هزینه کمتری داره.
روش گرادیان کاهشی تصادفی فقط برای توابعی به شکل زیر به کار میره :
نکته این تابع اینه که خودش مجموعه‌ای از توابع دیگه هست. اگه به تابع هزینه روشهای یادگیری ماشین نگاه کنید متوجه میشید که دقیقا چنین صورتی داره. کاری که تو الگوریتم گرادیان کاهشی انجام میدیم اینه که تو هر مرحله به جای اینکه گرادیان تابع f رو تو نقطه مورد نظر حساب کنیم، گرادیان یکی از fi ها رو تو اون نقطه محاسبه میکنیم. حالا این fi چجوری انتخاب میشه؟ به صورت تصادفی. سر همینم هست که اسمش شده گرادیان کاهشی تصادفی.
حالا بیاید یه نگاهی به چندتا تابع و مجموع اونها بندازیم. قبلا شکل یک تابع کروی رو دیدیم حالا با یک جابهجایی ساده چهارتا از این تابع‌ها ایجاد میکنیم که نقطه کمینه‌شون متفاوت هست.
نمودار کانتور اونها رو تو شکل زیر میبینیم:
نقاط کمینه رو با رنگ قرمز مشخص کردم. حالا سوالی که ایجاد میشه اینه که مجموع این توابع چه نسبتی با این تابع‌ها داره؟ شکل بعد این رو خیلی خوب نشون میده :
نمودار مجموع با رنگ طوسی نمایش داده شده. نمودار کانتور هم به صورت زیر هست:
شکل بالا دو تا نکته مهم داره. اول اینکه مجموع چندتا تابع کروی خودش یک تابع کروی هست. به طور کلی‌تر مجموع چندتا تابع محدب یک تابع محدب هست. تابع محدب فقط یدونه کمینه موضعی داره و درنتیجه اگه تو الگوریتمی که استفاده میکنیم یه نقطه پیدا کنیم که از نقاط اطرافش بهتره، خیالمون راحته که کمینه‌کننده کل تابع رو پیدا کردیم. نکته دوم رو میتونید تو نمودار کانتور ببینید. کمینه‌کننده تابع مجموع یه جایی بین کمینه‌کننده‌های توابع هست یعنی اگه کمینه‌کننده همه توابع رو داشته باشی میتونی یه بازه پیدا کنی که کمینه‌کننده تابع مجموع هم تو اون قرار داره. حالا شاید فکر کنید چون کمینه‌کننده توابعمون انقدر متقارن شدن این اتفاق افتاده. اما شکل بعد نشون میده که حتی اگه توابعمون به صورت تصادفی انتخاب شده باشن باز هم دو تا نکته‌ای که گفتیم برقرار هست :
به نمودار‌های کانتور توجه کنید:
میبینید که کمینه‌کننده‌یِ تابعِ مجموع بین کمینه‌کننده‌هایِ توابع قرار داره. حالا بریم سراغ ایده الگوریتم گرادیان کاهشی تصادفی. از این جا به بعد میخوایم با مجموع ۲۰ تا تابع کروی که به صورت تصادفی جابه‌جا شدن کار کنیم اما با توجه به اینکه اگه نمودار کانتور همه این توابع رو بکشیم دیگه چیزی ازش متوجه نمیشیم، فقط نمودار کانتور تابع مجموع رو بعلاوه نقطه کمینه‌کننده سایر توابع رسم میکنیم.
اگه گامهای الگوریتم گرادیان کاهشی رو روی نمودار بالا رسم کنیم به صورت زیر میشه:
اگه نمودار بالا رو با شکل الگوریتم گرادیان کاهشی مقایسه کنید میبینید که با نظم کمتری به سمت کمینه‌کننده کلی حرکت میکنیم دلیلش هم اینه که هر بار فقط یکی از کمینه‌کننده‌ها رو در نظر گرفتیم. دقیقا انگار الگوریتم تو هر مرحله یکی از نقطه‌های رنگی رو نشونه رفته و بهش نزدیک شده بدون اینکه به بقیه نقاط توجهی بکنه. اما این بی‌توجهی از یه جایی به بعد سردرگمش میکنه. بیاید یکم روی شکل قبل زوم کنیم:
میبینید از یه جا به بعد الگوریتم‌مون داره نوسان میکنه. در واقع از وقتی که وارد پوش محدب نقاط کمینه‌کننده میشیم دیگه الگوریتم خوب کار نمیکنه. دلیل این اتفاق اینه:
از یه جایی به بعد نزدیک شدن به یکسری نقاط باعث دور شدن از سایر نقاط میشه
چجوری به این نوسان غلبه کنیم؟ یک راه‌حل برای این ماجرا کاهشی کردن طول گام هست :
اگه روی شکل زوم کنیم کاهشی شدن طول گام‌ها بهتر مشخص میشه:
تو شکل بالا میبینید که وقتی تو هر قدم، طول گام رو کاهش میدیم الگوریتم‌مون کمتر نوسان میکنه. این کاهش دادن انقدر ادامه پیدا میکنه که آخر سر الگوریتم به قول معروف به گل میشینه. در واقع انقدر طول گام کوچیک میشه که عملا الگوریتم نمیتونه تکون بخوره. اما با این حال با مقایسه طول گام ثابت و کاهشی متوجه میشید که با طول گام کاهشی الگوریتم خیلی به جواب اصلی نزدیکتر شده. وقتی طول گام، کاهشی میشه کندتر حرکت میکنیم در نتیجه اگه تعداد گام رو افزایش بدیم نتیجه بهتری میگیریم :
میبینیم که چقدر به جواب اصلی نزدیک شدیم اما بیاید همین کار رو برای الگوریتم گرادیان کاهشی معمولی انجام بدیم:
میبینیم که از یه جایی به بعد الگوریتم سرگردان شده و هر بار از روی جواب اصلی می‌پره. توضیح الگوریتم گرادیان کاهشی تصادفی رو همینجا تموم میکنیم ولی اگه علاقه‌مند بودید توی این notebook میتونید کد همه شکل‌های بالا رو هم ببینید.
قبل از اینکه این بحث رو تموم کنم دلم میخواد چندتا سوال بپرسم. به نظرتون چرا وقتی طول گام را کاهشی میکنیم انقدر خوب به جواب اصلی همگرا میشیم؟ من نقاط کمینه‌کننده توابع کروی رو با استفاده از توزیع یکنواخت تولید کردم. به نظرتون اگه نقاط رو از توزیع دیگه‌ای هم تولید کنیم باز هم انقدر الگوریتم به کمینه‌کننده کلی نزدیک میشه؟ یه نکته دیگه اینکه وزن همه توابع کروی یکسان بود. اگه به شکل این توابع رجوع کنید میبینید همه این توابع یک شکل هستند و فقط جابه‌جا شدن. حالا اگه به بعضی از توابع یک ضریب بدیم چه بلایی سر تابع مجموع میاد؟ و تو این حالت الگوریتم چطوری رفتار میکنه؟
حالا بریم سراغ اینکه الگوریتم گرادیان کاهشی تصادفی کجای زندگی به دردمون میخوره. به نظر من تنها کاری که ما صبح تا شب انجام میدیم بهینه‌سازی هست. وقتی داریم درس میخونیم دنبال این هستیم که تابع موفقیت درسی‌مون رو بهینه کنیم. این تابع هزاران تا متغیر داره مثلا وقتی که باید به درس خوندن اختصاص بدیم یا ساعتی که باید درس بخونیم و ... . یه مسئله بهینه‌سازی دیگه که ما خیلی باهاش سر و کار داریم تابع روابطمون با بقیه آدمها هست. مثلا بهترین دوست یا شریک زندگیتون رو در نظر بگیرید. همش به این فکر میکنیم که چیکار کنیم تا خوشحالشون کنیم یا مثلا چطور رفتار کنیم تا از ما راضی باشن. اینجا هم متغیرهای خیلی زیادی داریم، وقتی که برای دوستامون خرج میکنیم، نحوه صحبت کردنمون و ... . اگه فکر کنید هزار تا تابع دیگه‌ام میاد تو ذهنتون که دنبال پیدا کردن نقطه بهینه‌شون هستید. حالا یه سوال مجموع این توابع چه تابعی رو به ما میدن؟
به نظر من مجموع این توابع سعادت ما رو اندازه میگیرن. به نظرتون ما چطوری دنبال نقطه بهینه تابع سعادت میگردیم؟ بیاید یه تابع خاص رو در نظر بیگیرم مثلا تابع معدل خوب. کاری که ما میکنیم اینه که دنبال یک جهت کاهشی میگردیم و بعد سعی میکنیم تو اون جهت حرکت کنیم مثلا میدونیم زمان بیشتر برای درس خوندن باعث بالا رفتن معدل میشه در نتیجه سعی میکنیم در این جهت یک گام برداریم و مثلا از فردا روزی دو ساعت درس بخونیم. همین قضیه برای یادگرفتن پیانو هم صادقه. یعنی میبینیم اگه بخوایم پیانو بزنیم باید براش وقت بزاریم و در نتیجه یک گام در این جهت حرکت میکنیم و از فردا روزی یک ساعت تمرین پیانو انجام میدیم. حالا این وسط بحث محدودیت منابع پیش میاد اگه برای ارتقای معدلمون همینطور تلاش کنیم و در جهتش گامهای بلند برداریم دیگه وقتی نمیمونه که پیانو تمرین کنیم. در نتیجه میرسیم به نکته کلیدی الگوریتم گرادیان کاهشی تصادفی :
از یه جایی به بعد نزدیک شدن به یکسری اهداف باعث دور شدن از سایر اهداف میشه
خب تکلیف چیه؟ به نظر من باید طول گاممون رو کاهشی کنیم. فرض کنید یه دوست خیلی خوب پیدا میکنیم و میخوایم رابطمون رو باهاش تقویت کنیم. باهاش وقت میگذرونیم و بیشتر آشنا میشیم. با سرعت خیلی خوبی بهش نزدیک میشیم و رابطمون بهتر میشه. اما از یه جایی به بعد اگه پامون رو نزاریم رو ترمز، میبینیم از کار و زندگی افتادیم و صبح تا شب داریم با دوستمون صحبت میکنیم. نزدیک شدن به نقطه بهینه‌کننده این تابع باعث میشه از نقطه بهینه‌کننده خیلی از توابع دیگمون دور بشیم مثلا یه کاهش معدل قابل توجه داشته باشیم. من خیلیا رو تو دانشگاه دیدم که وقتی وارد یه رابطه میشن معدل ترمیشون کاهش قابل ملاحظه‌ای پیدا میکنه.
یه مثال آشنای دیگه کنکور هست. سالی که وارد پیش‌دانشگاهی شدم با این استدلال که کنکور بحث مرگ و زندگی هست خیلی از فعالیت‌هام رو کنار گذاشتم. مثلا ورزش کردن یا وقت گذروندن با دوستام. تازه دو سال بعد از کنکور فهمیدم که این گامهای جهشی به سمت رتبه بهتر چه بلایی سرم آورده. وقتی یه اضطراب مزمن منو وادار کرد برم پیش روانپزشک. بعد از اون بود که با مشورت پزشکم فعالیت ورزشیم رو زیاد کردم. این روزا سعی میکنم هر روز حتی شده ده دقیقه کمی مطالعه آزاد داشته باشم. اگه ببینم چند روز گذشته و من با هیچ دوستی تماس نداشتم میفهمم یه جای کار میلنگه.
چند وقت پیش یه دوست جدید پیدا کردم که خیلی با هم جور بودیم و دقیقا با گامهای خیلی بلند به هم نزدیک شدیم. بعد یه مدت من متوجه شدم وقت خیلی کمی برای بقیه دوستام میزارم و خب پامو گذاشتم رو ترمز و یکم طول گام رو کاهش دادم. هنوزم این دوست عزیز تو دایره دوستای صمیمیم هست اما این باعث نشد که دوستیم با بقیه صدمه بخوره. وقتی دکتر شمسی ایده الگوریتم گرادیان کاهشی تصادفی رو مطرح کرد داستان برنامه کتاب‌باز رو براش تعریف کردم و گفتم خوبه به سروش صحت پیشنهاد بدیم برای اینکه تو روابطش موفق باشه، طول گامشو کاهشی کنه.
امیدوارم این مقاله کمکتون کنه تا تو برنامه‌ریزی‌هاتون تعادل بیشتری داشته باشید و سعادت بیشتری رو کسب کنید ❤️
