پیاده سازی الگوریتم گرادیان کاهشی در پایتون — راهنمای گام به گام | تم آف

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

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

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

فیلم آموزش ریاضی برای یادگیری ماشین + پیاده سازی در پایتون در تم آف

کلیک کنید

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

اگر تابع $$ F (overrightarrow {x}) $$ را در نظر بگیریم که با گرفتن بردار $$overrightarrow {x}$$ در خروجی عدد $$y$$ را برگرداند، می‌توان با شروع از $$x_0$$ به صورت زیر حرکت کرد و مقدار تابع را کمینه کرد:

$$ large overrightarrow {x_{n+1}}= overrightarrow {x_n}-eta triangledown F ( overrightarrow {x_n}) $$

به این ترتیب، می‌توانیم جواب‌های بعدی را محاسبه کنیم.

توجه داشته باشید که مقدار گرادیان در «نرخ یادگیری» (Learning Rate) ضرب می‌شود و سپس از مقدار $$overrightarrow {x_n}$$ کم می‌شود. دلیل این اتفاق به ذات الگوریتم گرادیان کاهش برمی‌گردد. این الگوریتم تنها از مشتق اول تابع هدف استفاده می‌کند و تغییراتی که $$overrightarrow {x_n}$$ تنها برگرفته از شیب تابع است و نمی‌تواند انحناهای مربوط به مشتقات درجات بالاتر را وارد رفتار خود کند. به همین دلیل، تغییراتی که در $$overrightarrow {x_n}$$ ایجاد می‌کند تنها در بازه کوچکی از دقت بالایی برخوردار است. همین موضوع باعث می‌شود تا گام تغییرات را عدد کوچکی (از 0٫001 تا 0٫1) ضرب کنیم تا الگوریتم واگرا نشود.

فیلم آموزش یادگیری ماشین و پیاده سازی در پایتون Python – بخش یکم در تم آف

کلیک کنید

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

$$ large F'(x)= frac {F (x + h)-F(x-h)}{2 h} $$

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

پیاده سازی گرادیان کاهشی در پایتون

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

فیلم آموزش یادگیری ماشین با پایتون – ماشین لرنینگ با Python در تم آف

کلیک کنید

ابتدا کتابخانه‌های مورد نیاز را فراخوانی می‌کنیم:

import numpy as np
import matplotlib.pyplot as plt

این کتابخانه‌ها به ترتیب برای کار با آرایه‌ها و رسم نمودار مورد استفاده قرار خواهند گرفت.

حال تابع هدف را تعریف می‌کنیم:

$$ large f ( x ) = x ^ 2 $$

که خواهیم داشت:

# Function to Minimize
def f(x:float):
    return x**2

حال محل شروع الگوریتم را تعیین می‌کنیم:

x0 = 3 # Initial Solution

اکنون نرخ یادگیری و تعداد مراحل کار الگوریتم را تعریف می‌کنیم:

lr = 1e-2 # Learning Rate
nIteration = 10 # Iteration Count

به این ترتیب، موارد مورد نیاز برای اجرای الگوریتم ایجاد شدند.

فیلم آموزش ریاضی برای یادگیری ماشین + پیاده سازی در پایتون در تم آف

کلیک کنید

حال حلقه اصلی برای کار الگوریتم را ایجاد می‌کنیم:

x = x0

# Algorithm Main Loop
for i in range(nIteration):
    x = x - lr * (2 * x)

توجه داشته باشید که مشتق تابع $$ f (x ) = x ^ 2 $$ به‌‌صورت $$ f’ (x) = 2 x $$ خواهد بود.

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

x = x0

# Algorithm Main Loop
print(f'x{0}: {round(x, 4)} -- y{0}: {round(f(x), 4)}')
for i in range(nIteration):
    x -= lr * (2 * x)
    print(f'x{i + 1}: {round(x, 4)} -- y{i + 1}: {round(f(x), 4)}')

با اجرای کد خواهیم داشت:

x0:  3      -- y0:  9
x1:  2.94   -- y1:  8.6436
x2:  2.8812 -- y2:  8.3013
x3:  2.8236 -- y3:  7.9726
x4:  2.7671 -- y4:  7.6569
x5:  2.7118 -- y5:  7.3537
x6:  2.6575 -- y6:  7.0625
x7:  2.6044 -- y7:  6.7828
x8:  2.5523 -- y8:  6.5142
x9:  2.5012 -- y9:  6.2562
x10: 2.4512 -- y10: 6.0085

مشاهده می‌کنیم که الگوریتم به‌خوبی مقدار تابع را کاهش می‌دهد. به‌دلیل کم بودن مقدار نرخ یادگیری، الگوریتم گام‌های کوچک، اما مطمئن‌تری برمی‌دارد. با افزایش نرخ یادگیری به 0٫1 خواهیم داشت:

x0:  3      -- y0:  9
x1:  2.4    -- y1:  5.76
x2:  1.92   -- y2:  3.6864
x3:  1.536  -- y3:  2.3593
x4:  1.2288 -- y4:  1.5099
x5:  0.983  -- y5:  0.9664
x6:  0.7864 -- y6:  0.6185
x7:  0.6291 -- y7:  0.3958
x8:  0.5033 -- y8:  0.2533
x9:  0.4027 -- y9:  0.1621
x10: 0.3221 -- y10: 0.1038

به این ترتیب، سرعت کمینه‌سازی بالاتر می‌رود و الگوریتم در تعداد مراحل ثابت، به میزان بیشتر بهبود ایجاد می‌کند.

حال تابع مشتق عددی را تعریف می‌کنیم:

# Numerical Derivative
def Derivative(Function, x:float, h:float=1e-6):
    d = (Function(x + h) - Function(x - h)) / (2 * h)
    return d

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

فیلم آموزش ریاضی برای یادگیری ماشین + پیاده سازی در پایتون در تم آف

کلیک کنید

حال تابع را در حلقه نوشته شده جایگذاری می‌کنیم:

    x -= lr * Derivative(f, x)

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

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

برای این کار، ابتدا یک لیست خالی برای اضافه کردن مقدار x و y در هر مرحله ایجاد می‌کنیم:

xSolution = []
ySolution = []

x = x0

xSolution.append(x)
ySolution.append(f(x))

# Algorithm Main Loop
for i in range(nIteration):
    x -= lr * Derivative(f, x)
    xSolution.append(x)
    ySolution.append(f(x))

به این ترتیب مقدار x و y در طول کار الگوریتم ذخیره می‌شود.

حال نیاز داریم تا نمودار تابع هدف را نیز رسم کنیم. برای این کار می‌توانیم از numpy به شکل زیر استفاده کنیم:

Xs = np.linspace(-3, +3, num=51)
Ys = np.vectorize(f)(Xs)

حال برای رسم نمودار خواهیم داشت:

plt.plot(Xs, Ys, lw=1, c='teal', label='Function Label')
plt.plot(xSolution, ySolution, lw=0.8, marker='o', ms=3, c='crimson', label='Points Over Iterations')
plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.show()

پس از اجرا، به نمودار زیر می‌رسیم.

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

فیلم آموزش ریاضی برای یادگیری ماشین + پیاده سازی در پایتون در تم آف

کلیک کنید

حال اگر مقدار نرخ یادگیری با به 0٫9 افزایش دهیم، به نمودار زیر می‌رسیم.

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

اگر از نقطه $$x_0=1$$ شروع کنیم و نرخ یادگیری برابر با 1٫05 باشد، شکل زیر را خواهیم داشت.

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

فیلم آموزش ریاضی برای یادگیری ماشین + پیاده سازی در پایتون در تم آف

کلیک کنید

بنابراین، می‌توان نتیجه گرفت که با تغییر نرخ یادگیری، یکی از چهار حالت زیر رخ خواهد داد:

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

توابعی با بیش از یک ورودی

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

فیلم آموزش ریاضی برای یادگیری ماشین + پیاده سازی در پایتون در تم آف

کلیک کنید

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

$$ large f ( x _ 1 , x _ 2 ) = ( 1 – x _1 )^2+100(x_2-x_1^2)^2 $$

این تابع در محل $$ x = (1 , 1 )$$ به کمینه می‌رسد.

برای این منظور، ابتدا تابع تعریف‌شده را اصلاح می‌کنیم:

# Function to Minimize
def f(x:np.ndarray):
    return (1-x[0])**2 + 100 * (x[1] - x[0]**2)**2

توجه داشته باشید که چون بیش از یک پارامتر وجود دارد، باید از آرایه‌ها استفاده کنیم.

حال تابع مشتق را اصلاح می‌کنیم:

# Gradient
def Gradient(Function, x:np.ndarray, h:float=1e-6):
    nX = x.size
    g = np.zeros(nX)
    fx = Function(x)
    for i in range(nX):
        temp = x.copy()
        temp[i] += h
        ftemp = Function(temp)
        g[i] = (ftemp - fx) / h
    return g

در این تابع به ترتیب عملیات زیر رخ می‌دهد:

فیلم آموزش ریاضی برای یادگیری ماشین + پیاده سازی در پایتون

کلیک کنید

1. ابتدا ورودی‌ها از جمله هدف، محل مشتق‌گیری و مقدار گام دریافت می‌شود.
2. تعداد پارامترها تعیین می‌شود.
3. یک آرایه خالی برای ذخیره مشتق تابع نسبت به هر پارامتر ایجاد می‌شود.
4. مقدار تابع در محل مشتق‌گیری محاسبه و ذخیره می‌شود.
5. داخل حلقه به‌ازای هر پارامتر:
   a. یک نسخه کپی از x ایجاد می‌شود.
   b. پارامتر انتخاب شده در حلقه به‌اندازه گام افزایش می‌یابد.
   c. مقدار تابع در موقعیت فعلی محاسبه می‌شود.
   d. مقدار مشتق حساب شده و به آرایه گرادیان اضافه می‌شود.
6. آرایه گرادیان خروجی داده می‌شود.

حال محل شروع، نرخ یادگیری و تعداد مراحل را تعریف می‌کنیم:

x0 = np.array([0.1, 0.1]) # Initial Solution
lr = 2e-3 # Learning Rate
nIteration = 90 # Iteration Count

و برای تعریف حلقه اصلی برنامه خواهیم داشت:

x = x0
print(f'y{0}: {round(f(x), 4)}')
# Algorithm Main Loop
for i in range(nIteration):
    x -= lr * Gradient(f, x)
    print(f'y{i+1}: {round(f(x), 4)}')

که با اجرا به ترتیب مقادیر زیر به‌دست می‌آید:

y0: 1.62
y1: 1.0582
y2: 0.8613
y3: 0.7907
y4: 0.7632
y5: 0.7502
y6: 0.7422
y7: 0.7359
y8: 0.7302
y9: 0.7248

حال می‌توانیم برنامه خود با اندکی ارتقا داده و الگوریتم گرادیان کاهشی را به شکل یک تابع تعریف کنیم:

# Gradient Descent Algorithm
def GDA(Function, x0:np.ndarray, nIteration:int, lr:float=1e-3):
    x = x0
    for _ in range(nIteration):
        x -= lr * Gradient(Function, x)
    return x

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

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

کلیک کنید

جمع‌بندی

در این آموزش از مجله تم آف، با الگوریتم گرادیان کاهشی آشنا شدیم. همچنین، روش گام به گام پیاده سازی الگوریتم گرادیان کاهشی در پایتون را بیان کردیم.