Stochastic Gradient Descent

رگرسیون خطی با استفاده از Gradient Descent

$$ h_{\theta}(x) = \sum^{n}_{j=0} \theta_j x_j$$

$$ J_{train}(\theta) = \frac{1}{2m} \sum^{m}_{i=1}\left(h_{\theta}(x^{(i)} - y^{(i)}\right)^2$$

$$\begin{eqnarray} Repeat \quad &\{& \nonumber \\ &\quad& \theta_j := \theta_j - \alpha \frac{1}{m} \sum^{m}_{i=1} \left(h_{\theta}(x^{(i)} - y^{(i)}\right)x^{(i)}_j \nonumber \\ &\quad&(\text{for every} \quad j = 0, 1, ..., n) \nonumber \\ \quad &\}& \end{eqnarray}$$

مشکل با الگوریتم بالا زمانی پیش می‌آید که m بسیار بالا باشد. الگوریتم فوق را Batch Gradient Descent نیز می‌نامند. کلمه Batch به این اشاره دارد که همه نمونه‌ها را همزمان نگاه می‌کند.

الگوریتم بسیار کاراتری برای داده‌های بزرگ وجود دارد که آن را Stocastic Gradient Descent می‌نامند:

$$ cost(\theta, (x^{(i)},y^{(i)})) = \frac{1}{2}\left(h_{\theta}(x^{(i)}) - y^{(i)}\right)^2$$ $$J_{train}(\theta) = \frac{1}{m} \sum^{m}_{i=1} cost(\theta, (x^{(i)},y^{(i)}))$$

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

.مجموعه داده‌ها را به صورت تصادفی هم می‌زند
$$\begin{eqnarray} Repeat \quad &\{& \nonumber \\ &\quad& \text{for} \quad i=1,2,...,m \quad \{ \nonumber \\ &\quad& \quad \theta_j := \theta_j - \alpha \left(h_{\theta}(x^{(i)} - y^{(i)}\right)x^{(i)}_j \nonumber \\ &\quad& \quad (\text{for every} \quad j = 0, 1, ..., n) \nonumber \\ &\quad&\}\nonumber \\ \quad \quad &\}& \end{eqnarray}$$

در حقیقت در هر مرحله تنها یک نمونه از داده‌ها را برای تعیین پارامترهای $\theta$ انتخاب می‌کند. به این معنی که ابتدا $(x^{(1)},y^{(1)})$ را انتخاب و بر اساس آن پارامترها را تعیین و در مرحله بعد $(x^{(2)},y^{(2)})$ را انتخاب و بر اساس آن پارامترها را بهبود می‌بخشد. این کار را تا آخرین داده تکرار می‌کند. پس به جای اینکه در هر مرحله کل داده‌ها را استفاده کنیم، تنها از یک داده استفاده می‌کنیم و عملکرد بهتر این الگوریتم در کار با داده‌های بسیار زیاد به همین دلیل است.

البته باید به این نکته توجه داشت که هرچند این الگوریتم هم نظیر الگوریتم Batch Gradient Descent از نقطه شروع، در یک مسیر کلی به سمت نقطه کمینه سراسری حرکت می‌کند، ولی تفاوت آن با Batch Gradient Descent در این است که به جای انتخاب یک مسیر نسبتاً کوتاه و سر راست، چون در هر بار تکرار از یک داده استفاده می‌کند و در هر تکرار ممکن است جهت مسیر انتخاب شده به سمت کمینه سراسری تغییر کند، در نهایت ممکن است در محدوده‌ای نزدیک به کمینه سراسری نوسان کند. البته این مسئله مشکلی خاصی ایجاد نمی‌کند و معمولاً پاسخ‌های آن خوب است. بنابراین هرچند مسیر Batch Gradient Descent کوتاه‌تر و سر راست‌تر است، اما در عوض هر تکرار Stocastic Gradient Descent بسیار سریع‌تر انجام می‌شود و نکته آخر اینکه در حلقه تکرار برای m از یک تا مثلاً 100 میلیون، معمولاً با 10 تکرار و کمتر (بسته به حجم داده‌ها) به یک تابع فرضیه مناسب می‌رسیم و نیازی نیست که این حلقه 100 میلیون بار تکرار شود.

<< مبحث قبلی مبحث بعدی >>