Stochastic Gradient Descent

مشکل اصلی Batch Gradient Descent این است که در هر گام برای محاسبهٔ گرادیان از کل مجموعهٔ آموزشی استفاده می‌کند و روی داده‌های بسیار بزرگ کند می‌شود. در سوی دیگر، Stochastic Gradient Descent یا SGD در هر گام فقط یک نمونهٔ تصادفی را انتخاب و گرادیان را بر اساس همان نمونه محاسبه می‌کند. پردازش یک نمونه در هر تکرار بسیار سریع است و حتی اجازه می‌دهد مدل روی مجموعه‌داده‌هایی آموزش ببیند که در حافظه جا نمی‌شوند؛ زیرا در هر لحظه فقط یک نمونه لازم است.

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

در تابع هزینهٔ نامنظم، این تصادفی‌بودن گاهی مزیت است: می‌تواند الگوریتم را از Local Minimum بیرون بیندازد و احتمال یافتن Global Minimum را نسبت به Batch GD افزایش دهد. مسئله این است که همان تصادفی‌بودن مانع ساکن‌شدن دقیق روی کمینه می‌شود.

راه‌حل رایج کاهش تدریجی نرخ یادگیری است. در آغاز گام‌ها بزرگ‌اند تا پیشرفت سریع و خروج از کمینه‌های محلی ممکن شود، سپس گام‌ها کوچک و کوچک‌تر می‌شوند تا الگوریتم نزدیک کمینه آرام بگیرد. فرایندی که نرخ یادگیری را در طول زمان تعیین می‌کند Learning Schedule نام دارد و از نظر ایده شبیه Simulated Annealing در متالورژی است.

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

پیاده‌سازی سادهٔ SGD با یک Learning Schedule:

n_epochs = 50
t0, t1 = 5, 50 # learning schedule hyperparameters

def learning_schedule(t):
    return t0 / (t + t1)

np.random.seed(42)
theta = np.random.randn(2, 1) # random initialization

for epoch in range(n_epochs):
    for iteration in range(m):
        random_index = np.random.randint(m)
        xi = X_b[random_index : random_index + 1]
        yi = y[random_index : random_index + 1]
        gradients = 2 * xi.T @ (xi @ theta - yi) # for SGD, do not divide by m
        eta = learning_schedule(epoch * m + iteration)
        theta = theta - eta * gradients

هر مجموعهٔ m تکرار را یک Epoch در نظر می‌گیریم. برخلاف Batch GD که ۱۰۰۰ بار از کل داده عبور کرد، این نسخه فقط ۵۰ Epoch دارد و بااین‌حال جواب مناسبی می‌گیرد:

>>> theta
array([[4.21076011],
       [2.74856079]])

چون نمونه‌ها تصادفی انتخاب می‌شوند، ممکن است یک نمونه در یک Epoch چند بار انتخاب و نمونه‌ای دیگر اصلاً انتخاب نشود. راه دیگر این است که ابتدای هر Epoch مجموعه را - همراه برچسب‌ها - Shuffle کنید و سپس همهٔ نمونه‌ها را یک‌بار طی کنید. این روش پیچیده‌تر است و معمولاً نتیجهٔ محسوسی بهتر نمی‌دهد.

SGDRegressor در Scikit-Learn

برای رگرسیون خطی با SGD می‌توان از SGDRegressor استفاده کرد که به‌طور پیش‌فرض MSE را بهینه می‌کند. نمونهٔ زیر حداکثر ۱۰۰۰ Epoch اجرا می‌شود یا وقتی Loss طی ۱۰۰ Epoch کمتر از 10⁻⁵ تغییر کند متوقف می‌شود. نرخ اولیه ۰٫۰۱ است و Regularization غیرفعال شده است:

from sklearn.linear_model import SGDRegressor

sgd_reg = SGDRegressor(max_iter=1000, tol=1e-5, penalty=None, eta0=0.01,
                       n_iter_no_change=100, random_state=42)
sgd_reg.fit(X, y.ravel()) # y.ravel() because fit() expects 1D targets

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

>>> sgd_reg.intercept_, sgd_reg.coef_
(array([4.21278812]), array([2.77270267]))

Mini-Batch Gradient Descent

Mini-Batch GD میان دو روش قبلی قرار می‌گیرد. در هر گام نه از کل مجموعهٔ آموزشی استفاده می‌کند و نه فقط از یک نمونه؛ بلکه گرادیان روی مجموعهٔ تصادفی کوچکی از نمونه‌ها، یعنی Mini-Batch، محاسبه می‌شود.

مزیت مهم آن نسبت به SGD این است که عملیات ماتریسی روی سخت‌افزار مدرن - به‌ویژه GPU - بسیار بهینه‌اند و پردازش گروهی می‌تواند سریع‌تر شود. مسیر Mini-Batch نیز از SGD منظم‌تر است و با Batchهای نسبتاً بزرگ معمولاً نزدیک‌تر به کمینه حرکت می‌کند. در عوض در مسائل دارای Local Minimum ممکن است خروج از کمینه‌های محلی برای آن سخت‌تر از SGD باشد.

هر سه روش در نهایت نزدیک کمینه قرار می‌گیرند. Batch GD دقیقاً در کمینه متوقف می‌شود، درحالی‌که SGD و Mini-Batch اطراف آن حرکت می‌کنند؛ البته با Learning Schedule مناسب آن‌ها نیز می‌توانند بسیار نزدیک شوند. Batch GD هر گام را کند اجرا می‌کند، درحالی‌که دو روش دیگر گام‌های سریع‌تری دارند.

مقایسهٔ الگوریتم‌های رگرسیون خطی

پس از آموزش تقریباً تفاوتی در شکل مدل وجود ندارد؛ همهٔ این الگوریتم‌ها به مدل‌های مشابه می‌رسند و پیش‌بینی را به همان روش انجام می‌دهند.

Polynomial Regression

اگر داده پیچیده‌تر از یک خط مستقیم باشد چه؟ جالب است که هنوز می‌توان از مدل خطی برای برازش دادهٔ غیرخطی استفاده کرد: توان‌های ویژگی‌ها را به‌عنوان ویژگی‌های جدید اضافه می‌کنیم و سپس مدل خطی را روی مجموعهٔ توسعه‌یافته آموزش می‌دهیم. این روش Polynomial Regression نام دارد.

ابتدا دادهٔ غیرخطی بر اساس معادلهٔ درجهٔ دوم y = ax² + bx + c به‌همراه نویز تولید می‌کنیم:

np.random.seed(42)
m = 100
X = 6 * np.random.rand(m, 1) - 3
y = 0.5 * X ** 2 + X + 2 + np.random.randn(m, 1)

خط مستقیم برای این داده مناسب نیست. با PolynomialFeatures توان دوم ویژگی را به‌عنوان ویژگی تازه اضافه می‌کنیم:

>>> from sklearn.preprocessing import PolynomialFeatures
>>> poly_features = PolynomialFeatures(degree=2, include_bias=False)
>>> X_poly = poly_features.fit_transform(X)
>>> X[0]
array([-0.75275929])
>>> X_poly[0]
array([-0.75275929, 0.56664654])

X_poly هم x و هم x² را دارد. اکنون LinearRegression روی دادهٔ توسعه‌یافته:

>>> lin_reg = LinearRegression()
>>> lin_reg.fit(X_poly, y)
>>> lin_reg.intercept_, lin_reg.coef_
(array([1.78134581]), array([[0.93366893, 0.56456263]]))

مدل تقریباً رابطهٔ ŷ = 0.56x₁² + 0.93x₁ + 1.78 را یافته، درحالی‌که تابع اصلی y = 0.5x₁² + 1.0x₁ + 2.0 + Gaussian noise بوده است.

وقتی چند ویژگی وجود دارد، PolynomialFeatures فقط توان هر ویژگی را اضافه نمی‌کند، بلکه ترکیب‌های آن‌ها را نیز می‌سازد. مثلاً با دو ویژگی a و b و degree=3 علاوه بر a²، a³، b² و b³، عبارت‌های ab، a²b و ab² نیز ساخته می‌شوند. این توانایی به مدل خطی اجازه می‌دهد روابط میان ویژگی‌ها را ثبت کند.

Learning Curves

رگرسیون چندجمله‌ای با Degree بالا می‌تواند دادهٔ آموزشی را بسیار بهتر از مدل خطی ساده برازش کند، اما خطر Overfitting شدید دارد. شکل ۴-۱۴ مدل درجهٔ ۳۰۰ را با مدل خطی و مدل درجهٔ ۲ مقایسه می‌کند. مدل درجهٔ ۳۰۰ برای نزدیک‌شدن به تقریباً هر نمونه پیچ‌وخم زیادی ایجاد می‌کند.

مدل درجهٔ بالا شدیداً Overfit و مدل خطی Underfit است. در این مثال مدل درجهٔ دو بهترین تعمیم را دارد چون داده واقعاً از رابطهٔ درجهٔ دو ساخته شده است؛ اما در پروژهٔ واقعی تابع مولد داده را نمی‌دانیم. یک راه تشخیص استفاده از Cross-Validation است: عملکرد عالی روی آموزش و ضعیف روی اعتبارسنجی نشانهٔ Overfitting؛ عملکرد ضعیف روی هر دو نشانهٔ Underfitting.

راه دیگر «منحنی یادگیری» است؛ نمودار خطای آموزش و اعتبارسنجی نسبت به اندازهٔ داده یا تکرار آموزش. اگر مدل آموزش Incremental را پشتیبانی نکند، باید آن را چند بار روی زیرمجموعه‌های رو به رشد داده آموزش داد. Scikit-Learn تابع learning_curve() را برای این کار دارد:

from sklearn.model_selection import learning_curve

train_sizes, train_scores, valid_scores = learning_curve(
    LinearRegression(), X, y, train_sizes=np.linspace(0.01, 1.0, 40), cv=5,
    scoring="neg_root_mean_squared_error")
train_errors = -train_scores.mean(axis=1)
valid_errors = -valid_scores.mean(axis=1)

plt.plot(train_sizes, train_errors, "r-+", linewidth=2, label="train")
plt.plot(train_sizes, valid_errors, "b-", linewidth=3, label="valid")
[...] # beautify the figure: add labels, axis, grid, and legend
plt.show()

این مدل Underfit است. با یک یا دو نمونه مدل تقریباً می‌تواند آموزش را کامل برازش کند، پس خطای آموزشی از صفر آغاز می‌شود. با اضافه‌شدن نمونه‌ها، به‌دلیل نویز و غیرخطی‌بودن داده خطا بالا می‌رود و به Plateau می‌رسد. خطای اعتبارسنجی ابتدا بسیار بزرگ است چون مدل با دادهٔ کم تعمیم نمی‌دهد؛ سپس کاهش می‌یابد، اما چون خط مستقیم قادر به مدل‌کردن داده نیست در سطحی نسبتاً بالا و نزدیک خطای آموزش متوقف می‌شود.

اکنون منحنی مدل Polynomial درجهٔ ۱۰ را می‌بینیم:

from sklearn.pipeline import make_pipeline

polynomial_regression = make_pipeline(
    PolynomialFeatures(degree=10, include_bias=False),
    LinearRegression())
train_sizes, train_scores, valid_scores = learning_curve(
    polynomial_regression, X, y, train_sizes=np.linspace(0.01, 1.0, 40), cv=5,
    scoring="neg_root_mean_squared_error")
[...] # same as earlier

دو تفاوت مهم دیده می‌شود: خطای آموزش بسیار کمتر است و میان خطای آموزش و اعتبارسنجی فاصله‌ای وجود دارد. این فاصله نشانهٔ Overfitting است؛ مدل روی دادهٔ آموزشی بهتر از دادهٔ ندیده عمل می‌کند. با مجموعهٔ آموزشی بسیار بزرگ‌تر ممکن است دو منحنی به هم نزدیک‌تر شوند.

موازنهٔ Bias/Variance

یک نتیجهٔ مهم در آمار و یادگیری ماشین این است که خطای تعمیم را می‌توان به سه بخش مفهومی تقسیم کرد:

• Bias: خطای ناشی از فرض‌های نادرست، مثلاً فرض خطی‌بودن داده‌ای که واقعاً درجهٔ دو است. Bias بالا معمولاً به Underfitting منجر می‌شود.
• Variance: حساسیت زیاد مدل به تغییرهای کوچک دادهٔ آموزشی. مدل با Degrees of Freedom زیاد مانند Polynomial با Degree بالا معمولاً Variance زیاد دارد و Overfit می‌شود.
• Irreducible Error: خطایی که از نویز ذاتی داده می‌آید و فقط با تمیزکردن داده، اصلاح منبع داده، تعمیر Sensor یا حذف Outlierها قابل کاهش است.

افزایش پیچیدگی مدل معمولاً Variance را زیاد و Bias را کم می‌کند. کاهش پیچیدگی برعکس Bias را بالا و Variance را پایین می‌آورد؛ به همین دلیل این رابطه «Trade-Off» است.

مدل‌های خطی Regularized

یکی از راه‌های اصلی کاهش Overfitting، Regularize کردن مدل یا محدودکردن آن است. هرچه Degrees of Freedom کمتر باشد، Overfit شدن سخت‌تر است. برای Polynomial Regression ساده‌ترین راه کاهش Degree است؛ در مدل خطی معمولاً وزن‌ها را محدود می‌کنیم.

سه روش مهم عبارت‌اند از Ridge، Lasso و Elastic Net. در این مقاله Ridge آغاز می‌شود و دو روش دیگر در بخش بعد ادامه می‌یابند.

Ridge Regression

Ridge Regression که Tikhonov Regularization نیز نامیده می‌شود، نسخهٔ Regularized رگرسیون خطی است. جمله‌ای متناسب با مجموع مربع وزن‌ها به MSE اضافه می‌شود تا الگوریتم علاوه بر برازش داده، وزن‌های مدل را تا حد امکان کوچک نگه دارد. جملهٔ Regularization فقط هنگام آموزش به تابع هزینه اضافه می‌شود؛ پس از آموزش، عملکرد مدل باید با MSE یا RMSE معمولی ارزیابی شود.

فراپارامتر α شدت Regularization را کنترل می‌کند. اگر α صفر باشد Ridge همان Linear Regression است. اگر α بسیار بزرگ شود، همهٔ وزن‌ها به صفر نزدیک می‌شوند و مدل تقریباً خطی تخت نزدیک میانگین داده خواهد بود.

Bias یعنی θ₀ Regularize نمی‌شود، بنابراین جمع از i=1 شروع می‌شود. اگر w بردار وزن ویژگی‌ها باشد، جملهٔ Regularization برابر α ||w||₂² / m است. برای Batch GD کافی است مؤلفهٔ 2αw/m به بخش مربوط به وزن‌ها در بردار گرادیان اضافه شود و چیزی به گرادیان Bias افزوده نشود.

شکل ۴-۱۷ چند مدل Ridge را با αهای مختلف نشان می‌دهد. سمت چپ مدل‌های خطی و سمت راست PolynomialFeatures درجهٔ ۱۰ به‌همراه StandardScaler و Ridge است. با افزایش α، پیش‌بینی‌ها تخت‌تر و محافظه‌کارانه‌تر می‌شوند؛ Variance کاهش و Bias افزایش می‌یابد.

Ridge را می‌توان با راه‌حل بسته یا Gradient Descent آموزش داد. راه‌حل بسته:

A ماتریس همانی (n+1) × (n+1) است، با این تفاوت که خانهٔ بالا-چپ آن صفر است تا Bias Regularize نشود. Scikit-Learn می‌تواند این جواب را با فاکتورگیری Cholesky محاسبه کند:

>>> from sklearn.linear_model import Ridge
>>> ridge_reg = Ridge(alpha=0.1, solver="cholesky")
>>> ridge_reg.fit(X, y)
>>> ridge_reg.predict([[1.5]])
array([[1.55325833]])