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

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

کاهش گرادیان (انگلیسی: Gradient descent) الگوریتم بهینه‌سازی مرتبهٔ اول از نوع الگوریتم‌های تکرار شونده است. برای یافتن کمینهٔ محلی یک تابع با استفاده از این الگوریتم، گام‌هایی متناسب با منفی گرادیان (یا گرادیان تخمینی) تابع در محل فعلی برداشته خواهد شد. اگر در استفاده از این الگوریتم، گام‌هایی متناسب با جهت مثبت گرادیان برداشته شود، به بیشینهٔ محلی تابع نزدیک می‌شویم که به این فرایند افزایش گرادیان گفته می‌شود. اگر تابع محدب یا مقعر باشه به بیشینه جهانی می‌رسیم.[۱] بسیاری از مسائل یادگیری ماشینی محدب هستند و ازینرو گرادیان کاهشی جواب بهینه را در این مسائیل تولید می‌کند.[۱]

توضیح الگوریتم[ویرایش]

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

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

برای توابع محدب هر بار مقدار تابع یا کمتر می‌شود یا ثابت می‌ماند به این معنی که

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

مثال[ویرایش]

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

گرادیان این تابعِ دومتغیّریه این بردار است:

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

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

Banana-SteepDesc.gif

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  1. ۱٫۰ ۱٫۱ Kim, Donghwan; Fessler, Jeffrey (2015-10-17). "Optimized first-order methods for smooth convex minimization". Mathematical Programming (in English). 159 (1-2): 81–107. ISSN 0025-5610. PMID 27765996. 

پیوند به بیرون[ویرایش]