AlgoVerse

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

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

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

ادامه‌ی توضیح ↓
ورودی:
P 4×2 · rate=50 · steps=25خروجی PDF

چهار نقطه نزدیک y = 2x + 1؛ با نرخ ۰٫۰۵ و ۲۵ گام، w و b به ۲ و ۱ نزدیک می‌شوند و خطا مدام کم می‌شود.

  1. def gradient_descent(P, rate, steps):
  2. # Fit a line y = w·x + b to the points P by least squares. rate is the learning rate in thousandths.
  3. eta = rate / 1000
  4. n = len(P)
  5. w = 0.0
  6. b = 0.0
  7. rows = [[0, w, b, round(loss(P, w, b), 4)]] # for the picture: step, w, b, loss
  8. for t in range(1, steps + 1):
  9. # The gradient of the mean squared error with respect to w and b.
  10. gw = 0.0
  11. gb = 0.0
  12. for x, y in P:
  13. err = w * x + b - y
  14. gw = gw + 2 * err * x / n
  15. gb = gb + 2 * err / n
  16. w = round(w - eta * gw, 4)
  17. b = round(b - eta * gb, 4)
  18. current = round(loss(P, w, b), 4)
  19. rows.append([t, w, b, current])
  20. if current > rows[0][3]:
  21. return None
  22. return [w, b]
  25. def loss(P, w, b):
  26. total = 0.0
  27. for x, y in P:
  28. total = total + (w * x + b - y) ** 2
  29. return total / len(P)

ناوردا: با نرخ یادگیری به اندازه‌ی کافی کوچک، خطا (loss) در هر گام کم می‌شود.

شروع اجرا

w—
b—
current—

جدول هنوز خالی است.

متغیرهای محلی

rate50
steps25

نارنجی = در همین گام عوض شد

P list

[0, 1][1, 3][2, 5][3, 7]

Call stack

  1. gradient_descent()خط 1
گام ۱ از ۹۲۱
خط سیاه = step · خط نارنجی = گام کلیدیstep: 0/25 · done: 0/1
    توضیح

    ایده

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

    θ ← θ − η · ∇L(θ)

    η نرخ یادگیری (اندازه‌ی گام) است.

    برازش خط

    برای نقطه‌های (x_i, y_i) خط y = w·x + b را می‌خواهیم که میانگین مربع خطا کمینه شود:

    L(w, b) = (1/n) Σ (w·x_i + b − y_i)²
∂L/∂w = (2/n) Σ (w·x_i + b − y_i) · x_i
∂L/∂b = (2/n) Σ (w·x_i + b − y_i)

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

    نرخ یادگیری

    • خیلی کوچک: همگرایی آهسته.
    • خیلی بزرگ: هر گام از کمینه رد می‌شود و خطا بزرگ‌تر می‌شود (واگرایی).

    ورودی

    هر سطر P یک نقطه است؛ rate نرخ یادگیری به هزارم (۵۰ یعنی ۰٫۰۵) و steps تعداد گام‌ها.