Stochastic Gradient Descent Convergence

بررسی همگرایی Stochastic Gradient Descent

یادآوری: برای Batch Gradient Descent تابع هزینه را برحسب تعداد دفعات تکرار رسم می‌کردیم و مطمئن می‌شدیم که در هر تکرار \(J_{train}(\theta)\) کاهش پیدا می‌کند. برای Stochastic Gradient Descent در خلال یادگیری، درست قبل از آپدیت \(\theta\) با استفاده از \((x^{(i)},y^{(i)})\) تابع هزینه را محاسبه می‌کنیم. سپس به عنوان مثال در هر 1000 تکرار میانگین تابع هزینه را روی آخرین 1000 نمونه بررسی شده توسط الگوریتم رسم و همگرایی آن را بررسی می‌کنیم. هرچند نمودار رسم شده ممکن است نویزی باشد، چون 1000 نمونه یک بار رسم می‌شود، ولی اگر به شکل زیر باشد، می‌توان گفت که عملکرد خوبی داشته است.

نمودار قرمز رنگ با \(\alpha\) کمتری رسم شده و مشاهده می‌شود که هر چند نرخ همگرایی آن آهسته‌تر است ولی جواب بهتری را محاسبه می‌کند. البته گاهی اوقات این اختلاف قابل صرفنظر است.

اگر به جای میانگین روی 1000 نمونه روی 5000 نمونه (نمودار قرمز رنگ) میانگین بگیریم و آن را رسم کنیم ممکن است که نمودار صاف‌تری (smoother) داشته باشیم. ولی یکی از معایب آن، این است که در مشاهده عملکرد الگوریتم تاخیر به وجود می‌آید.

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

آخرین موردی که ممکن است مشاهده کنید نموداری شبیه زیر است که نشان می‌دهد الگوریتم همگرا نمی‌شود و احتمالاً نیاز دارید \(\alpha\) را کاهش دهید.

معمولاً در Stochastic Gradient Descent نرخ \(\alpha\) را ثابت نگه می‌داریم. ولی اگر خیلی آهسته با زمان نرخ \(\alpha\)) را کاهش دهیم، احتمال دارد به جای نوسان در نزدیکی کمینه سراسری به آن همگرا شود. مثلاً می‌توان \(\alpha\) را به صورت زیر کاهش داد:

$$ \alpha = \frac{const 1}{iteration Number + const 2} $$

یکی از دلایلی که از این مورد اجتناب می‌کنیم این است که باید \(const1\) و \(const2\) را زیاد تغییر دهیم تا به اعداد مناسبی برسیم و این کار اضافه به صرفه نیست. مخصوصاً که جواب‌های به دست آمده در حول و حوش نقطه کمینه سراسری هم معمولاً راضی کننده هستند.