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

به‌نام خدا، سلام… در این پست می‌خواهم درباره الگوریتم گرادیان کاهشی (Gradient Descent) صحبت کنم. باتوجه به اهمیت زیاد این الگوریتم، در جلسه سوم از آموزش یادگیری ماشین رایگان می‌خواهم به تشریح گرادیان کاهشی بپردازم. این الگوریتم در جلسات بعدی بسیار کاربرد دارد. با هوسم همراه باشید…

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

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

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

الگوریتم گرادیان کاهشی، یک الگوریتم بهینه‌سازی تکراری مرتبه-اول هست که مینیموم محلی در یک تابع مشتق‌پذیر را پیدا می‌کند.

سخت بود؟ پر از کلمات عجیب و غریب؟ اجازه دهید ساده‌اش کنم:

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

یک‌سری از کلمات را حذف کردم. البته، این کلمات مهم بودند. بعدا درباره کلمات حذف‌شده توضیح می‌دهم. حتما می‌دانید که مینیموم محلی چیست؛ اما محض یادآوری به تصویر زیر نگاه کنید.

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

الگوریتم گرادیان کاهشی

می‌خواهم گرادیان کاهشی را طی یک مثال به شما توضیح بدهم. مثال زیر را درنظر بگیرید؛ بیایید با گرادیان کاهشی، مینیموم محلی آن را بیابیم.

قبل از اینکه توضیحات اصلی را شروع کنیم، بیایید چند نکته مقدماتی و لازم به شما بگویم.

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

نکته یادتان باشد که یک تابع محدب (Convex) همواره یک اکسترمم دارد. اما یک تابع غیرمحدب (Non Convex) بیش از یک اکسترمم دارد. تفاوت یک تابع محدب و غیرمحدب چیست؟ معیار بررسی محدب/غیرمحدب بودن یک تابع، دو نقطه مانند A و B است! به شکل زیر نگاه کنید:

• تابع محدب: هر دو نقطه‌ای روی منحنی انتخاب کنیم، به هیچ وجه خط واصل این دو نقطه، تابع را قطع نمی‌کند.
• تابع غیرمحدب: دو نقطه‌ای وجود دارد که خط واصل آنها، تابع را قطع خواهد کرد. به دو علامت ضربدر در شکل سمت راست نگاه کنید که تابع را قطع کرده است.

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

نکته تابع درجه دوم همواره همواره همواره یک تابع محدب هست. چون یک اکسترمم دارد و بنابراین قطعا محدب است و تمام.

بسیارخب، بعد از چند نکته، برویم مینیموم محلی تابع y=0.1x² را با گرادیان کاهشی بدست بیاوریم. گرادیان کاهشی شامل چند مرحله ساده هست که در ادامه توضیح می‌دهم.

مرحله 1: انتخاب یک مقدار رندوم برای x

در اولین مرحله، به صورت رندوم یک مقدار برای x انتخاب می‌شود. به عنوان مثال، در شکل زیر نقطه x=2 به عنوان نقطه اولیه انتخاب شده است.

مرحله 2: محاسبه مقدار مشتق در این نقطه

حال باید محاسبه کنیم که مقدار مشتق تابع y=0.1x² در این نقطه چقدر است. چرا باید مقدار مشتق را حساب کنیم؟ ساده است، ما می‌دانیم که اکسترمم‌ها در نقاطی اتفاق می افتد که مقدار مشتق برابر با صفر هست. بنابراین، اینجا مقدار مشتق را حساب می‌کنیم تا ببینیم صفر هست یا نه. اتفاقا کلمه گرادیان در الگوریتم گرادیان کاهشی هم به همین مشتق اشاره دارد. خب، مشاهده می‌کنید که صفر نیست:

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

شیب می‌تواند ما را به محل مینیموم نزدیک کند. چگونه؟ در مرحله سوم می‌بینید…

مرحله 3: بدست آوردن نقطه جدید با مشتق

اگر به شما بگویم که یک گام به سمت نقطه مینیموم بردارید، به سمت راست میروید یا چپ؟ قطعا چپ، یعنی همیشه به دنبال سراشیبی هستید. پس شیب می‌تواند به ما کمک کند؛ در اینجا شیب مثبت است و فلش زرد در شکل زیر هم شیب مثبت را نشان می‌دهد. اگر در جهت شیب (فلش زرد) حرکت کنیم، قطعا فی ضلالٍ مبین! درعوض کافی است، در جهت منفی شیب (فلش قرمز) حرکت کنیم، دراین‌صورت به هدف نزدیک می‌شویم.

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

بیایید نقطه جدید را در شکل هم ببینیم:

پس:

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

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

و حالا تکرار مرحله 2 و 3

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

• مرحله 1: یک نقطه رندوم انتخاب کن.
• مرحله 2: مقدار مشتق در این نقطه را حساب کن.
• مرحله 3: از رابطه (*) x_new=x – df/dx برای محاسبه مقدار جدید استفاده کن.
• برگرد به مرحله 2

این فرآیند آنقدر تکرار می‌شود تا ما به نقطه مینیموم محلی برسیم. بیایید انیمیشن حرکت گوی به سمت نقطه مینیموم را ببینیم.

ببینید چطور گام به گام حرکت می‌کند و به سمت مینیموم محلی می‌رود.

ممکن است این سوال برای شما ایجاد شود که چرا رفته رفته آن فلش کوچک و کوچکتر شد؟ چون شیب رفته رفته کمتر شد. یعنی مشتق کوچکتر شد و بنابراین هربار مقدار کمتری هم به x اضافه شد.

اما یک چالش در گرادیان کاهشی

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

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

طول گام در گرادیان کاهشی

به رابطه زیر دقت کنید؛ یک پارامتر η اضافه کرده‌ام که به آن طول گام گفته می‌شود. معمولا مقدار آن بین 0 و 1 است. این پارامتر، می‌تواند از قدرت مشتق بکاهد و جلوی آن حرکت نامنظم را بگیرد:

رابطه بالا، فرمول کامل گرادیان کاهشی است. حال، بیایید با طول گام 0.1 دوباره مینیموم تابع را بدست آوریم:

چه می‌کند این طول گام! حالا در انیمیشن‌های زیر، طول گام را با مقادیر مختلف ببینید:

درمورد انیمیشن‌های بالا صحبت بسیار است. می‌خواهم آنها را کمی تحلیل کنم:

• همه نمودارهای بالا با 25 گام کشیده شده است. یعنی 25 بار فرآیند گرادیان کاهشی را طبق رابطه (*) انجام داده‌ام.
• در طول گام 0.2 و 0.4 اوضاع خوب است. به‌خوبی به سمت مینیموم محلی سرازیر می‌شویم. قبل از 25 گام به مینیموم می‌رسند. البته، 0.4 زودتر می‌رسد. یعنی، نسبت به 0.2 طول گام مناسب‌تری است.
• در طول گام 0.6 سریع پیش رفتیم. اما درنهایت، بین دو نقطه نوسان کردیم و به مینیموم محلی نرسیدیم. ای کاش می‌توانستیم طول گام را آن نزدیکی‌های مینیموم کوچکتر کنیم. آن وقت مشکل حل می‌شد.
• در طول گام 0.8 اوضاع بد هست. به‌نظر می‌رسد نوسان شدیدی داریم و احتمال کمی دارد که به مینیموم محلی برسیم.
• نتایج بالا، نشان می‌دهد که برای این تابع طول گام 0.4 خوب است.

بسیارخب، بیایید چند نکته درمورد طول گام بگویم.

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

نکته معمولا در یادگیری ماشین به پارامتر η نرخ یادگیری گفته می‌شود.

گرادیان کاهشی در ابعاد بالاتر

همه مثال‌هایی که برای شما زدم، در فضای دوبعدی بود. تنها یک متغیر مستقل (x) داشتیم که می‌خواستیم مقداری برایش بدست آوریم که تابع f مینیموم شود. اما در یادگیری ماشین آنقدر ابعادمان زیاد است که نمی‌توانیم به تصویر بکشیم. یعنی، یک عالمه متغیر مستقل داریم. همچنین، یک عالمه نقطه مینیموم محلی داریم. درضمن، هر نقطه مینیموم محلی برایمان مطلوب نیست. بلکه به دنبال نقطه‌ای هستیم که مینیموم تر است! به تصویر زیر نگاه کنید؛ فضا سه بعدی است و دو متغیر مستقل [x₁, x₂]=x داریم.

دقت کنید؛ مثلا می‌خواهیم از نقطه A شروع کنیم و از چاله Local Minima نجات پیدا کنیم. سپس، Saddle Point را هم به سلامت رد کنیم. درنهایت بیفتیم در چاه Global Minima. کار سختی است! 😅 خب بیایید کمی سخت‌ترش کنیم. نظرتان درباره شکل پایینی چیست؟!

تازه همه اینها در سه بعد است که می‌توانیم به تصویر بکشیم. معمولا، در یادگیری ماشین ما با ابرفضا (Hyper-space) یا فضاهای بیش از سه بعد سروکار داریم.

نکته گرادیان افزایشی (Gradient Ascent) هم داریم که در آن به سمت بالا (در جهت شیب) حرکت کنیم تا به ماکزیموم محلی برسیم. معمولا، در یادگیری ماشین از گرادیان کاهشی استفاده می‌شود.

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

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

در بلوک دیاگرام بالا، چرا از ∂ برای نشان دادن مشتق استفاده کردم؟ چون دیدید که تابع ممکن است چندین متغیر مستقل داشته باشد که طبیعتا باید از همه متغیرهای مستقل مشتق بگیریم. یعنی x در تصویر بالا، یک برداری از متغیرهای مستقل به‌صورت [x₁, x₂, …, x_n]=x است. به همین خاطر است که بجای کلمه مشتق از کلمه گرادیان استفاده می‌شود.

در پایان بیایید یک بار دیگر آن تعریف سخت را مرور کنیم:

الگوریتم گرادیان کاهشی، یک الگوریتم بهینه‌سازی تکراری مرتبه-اول هست که مینیموم محلی در یک تابع مشتق‌پذیر را پیدا می‌کند.

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

• بهینه‌سازی: دیدیم که یک الگوریتم بهینه سازی است که به دنبال یافتن مینیموم محلی است.
• تکراری: دیدیم که یک فرآیند سه مرحله‌ای آنقدر تکرار می‌شود تا به مینیموم محلی برسیم.
• مرتبه-اول: در گرادیان کاهشی از مشتق اول استفاده می‌شود. مرتبه-اول هم به همین نکته اشاره دارد.
• تابع مشتق‌پذیر: تابع باید مشتق‌پذیر باشد که بتوانیم مشتق بگیریم!

خب خسته نباشید؛ این جلسه هم تمام شد، اما حرف ناگفته بسیار است. بهینه سازی در یادگیری ماشین بسیار پراهمیت هست. در جلسات بعدی یادگیری ماشین خواهید دید. همه آنچه که در اینجا گفتم، تنها شروعی ساده در بحث بهینه سازی در یادگیری ماشین است. مثلا، الگوریتم های SGD و ADAM و Mini-batch SGD بسیار مهم هستند. اما برای شروع کافی است. در جلسه بعدی می‌خواهم درباره رگرسیون خطی صحبت کنم. اتفاقا کاربرد گرادیان کاهشی در رگرسیون خطی را خواهید دید. خب، حالا شما بگویید، این جلسه چطور بود؟ برای ما کامنت کنید و با هوسم همراه باشید…