گرادیان کاهشی تصادفی
گرادیان کاهشی تصادفی (به انگلیسی: Stochastic Gradient Descent) (اغلب به اختصار SGD خوانده میشود) روشی مبتنی بر تکرار برای بهینهسازی یک تابع مشتقپذیر به نام تابع هدف (تابع هزینه) است که یک تقریب تصادفی از روش گرادیان کاهشی میباشد. در حقیقت گرادیان کاهشی تصادفی الگوریتمی در اختیار ما قرار میدهد که طی چند حلقهٔ تکرار مقدار کمینه یک تابع و مقادیری را که با ازای آنها تابع کمینه مقدار خود را میگیرد، بدست بیاوریم. به تازگی مقالهای ابداع این روش را به هربرت رابینز و ساتِن مونرو (به انگلیسی: Herbert Robins and Sutton Monro) برای انتشار مقالهای در باب گرادیان کاهشی تصادفی در سال ۱۹۵۱ نسبت دادهاست. تفاوت گرادیان کاهشی تصادفی با گرادیان کاهشی استاندارد در این است که برخلاف گرادیان کاهشی استاندارد که برای بهینهسازی تابع هدف از تمام دادههای آموزشی استفاده میکند، گرادیان کاهشی تصادفی از گروهی از دادههای آموزشی که بهطور تصادفی انتخاب میشود برای بهینهسازی استفاده میکند. این روش در مسائل آماری و یادگیری ماشین کاربرد فراوانی دارد.
پیشینه
در برآوردهای آماری و یادگیری ماشین معمولاً مسائلی بهوجود میآید که در آنها نیاز است تابعی مانند
یا به عبارت دیگر:
که
برای حل چنین مسئلهای از گرادیان کاهشی استاندارد یا در مواردی از گرادیان کاهشی تصادفی استفاده میشود. در آمار کلاسیک زمینههایی مثل کمترین مربعات یا برآورد درستنمایی بیشینه، مسائلی مشابه در باب کمینهسازی مجموع جملات مطرح میشود. همچنین مسئلهٔ مینیممسازی جمع جملات در اصل کمینهسازی خطر تجربی (Empirical risk minimization) نیز مطرح میشود.
در بسیاری از موارد تابع هدف تابعی ساده میشود که اعمال روش گرادیان کاهشی روی آن پیچیده و زمانبر نیست در این موارد از روش گرادیان کاهشی استاندارد استفاده میشود، مانند خانوادهٔ توابع نمایی یک پارامتره که در ارزیابی توابع اقتصادی استفاده میشود. اما از آنجا که در روش گرادیان کاهشی استاندارد یا تصادفی به محاسبهٔ گرادیان تابع هدف در هر حلقه نیاز است، در بعضی از موارد که پارامترهای تابع هدف زیاد اند یا مجموعهٔ دادههای آموزشی بسیار بزرگ است محاسبهٔ انجام شده در هر حلقه میتواند بسیار زمانبر و پیچیده باشد به همین دلیل در این موارد از گرادیان کاهشی تصادفی استفاده میشود که در هر حلقه این عملیات را تنها برای بخشی از مجموعهٔ دادههای آموزشی که در اختیار داریم، انجام میدهد. در روش گرادیان کاهشی تصادفی در هر حلقه عملیات موردنظر بر روی تنها یک عضو مجموعهٔ دادههای آموزشی که در هر حلقه یهصورت تصادفی انتخاب میشود انجام نمیشود و در عوض بر روی زیرمجموعهای از آن انجام میشود؛ این امر دو دلیل دارد:
- پراکندگی مقدار بدست آمده برای پارامتر را در هر حلقه کم میکند و همگرایی پایدارتر پیش میرود.
- بهرهگیری از عملیات ماتریسی که پیادهسازی بسیار سریعی دارد.
کاربردها
گرادیان کاهشی تصادفی یک الگوریتم محبوب و متداول برای یادگیری طیف گستردهای از مدلها در یادگیری ماشین است، از جمله ماشینهای بردار پشتیبانی، رگرسیون لجستیک و مدلهای گرافیکی. الگوریتم بازگشت به عقب که عملاً الگوریتم استاندارد برای یادگیری شبکههای عصبی مصنوعی است در واقع روشی برای پیدا کردن گرادیان شبکه برای استفاده در گرادیان کاهشی تصادفی است. گرادیان کاهشی تصادفی در جامعه ژئوفیزیک نیز کاربردهایی دارد مانند مسئله وارونگی کامل شکلموج (FWI).
روش پیادهسازی
در پیادهسازی کلی گرادیان کاهشی تصادفی ابتدا بردار پارامترها که برداری است که شامل تمام پارامترهای تابع هزینه است را
که در آن
در پیادهسازی دیگر در هر حلقه عضوی تصادفی از مجموعهٔ دادهها انتخاب نمیشود بلکه در هر حلقه کل مجموعه دادهها یک بار بهصورت تصادفی بازچینی میشود سپس به عملیات بهروزرسانی به ترتیب به ازای
بهومقدار اولیه بده تا زمانی که کمینه بدست بیاید تکرار کن دادههای آموزشی را به صورت تصادفی بازچینی کن برایاز ۱ تا n تکرار کن:
همانطور که پیشتر اشاره شد معمولاً عملیات بهروز رسانی برای
مثال
فرض کنید در یک مسئلهٔ یادگیری ماشین میخواهیم از روش کمترین مربعات استفاده کنیم به طوری که مجموعهای از دادههای آموزشی به شکل
بسط
تا به حال چندین روش نوین برای کاهش سریعتر گرادیان کاهشی ابداع شده که ذیلاً بعضی مورد بررسی قرار گرفتهاند.
تکانه (Momentum)
این روش برای اولین بار توسط روملهارت، هیلتون و ویلیامز معرفی شد. در این روش میزان تغییر پارامتر
که با ترکیب این دو به عبارت پایین میرسیم:
روش momentum باعث میشود که مسیر پارامتر
میانگین (Averaging)
در این روش در هر مرحله پارامترهای
گرادیان تطبیقی (AdaGrad)
روش آداگراد یا گرادیان تطبیقی برای اولین بار در سال ۲۰۱۱ معرفی و منتشر شد. این روش برای هر بُعدِ پارامتر یک نرخ یادگیری جداگانهای در نظر میگیرد؛ نرخ یادگیری همان
نرخ یادگیری برای ابعاد مختلف پارامتر از قطر اصلی ضرب خارجی
حال میتوان پارامتر را به صورت پایین بهروز کرد:
این معادله برای بعد
از آنجا که در نرخ یادگیری
RMSProp
در این روش همانند گرادیان تطبیقی برای هر بُعدِ پارامتر نرخ یادگیری جداگانهای در نظر گرفته میشود. ایده اصلی این است که نرخ یادگیری را برای یک بُعد بر میانگین گرادیانهای آن بُعد تقسیم کنیم؛ بنابراین، ابتدا میانگین را به این شکل محاسبه میکنیم:
در این معادله
این روش نتایج بسیار خوبی برای مسائل مختلف بهینهسازی دادهاست.
Adam
این روش مشابه روش RMSProp است با این تفاوت که هم از میانگین گرادیان و هم از گشتاورهای دوم آن به شکل پایین استفاده میشود.
در اینجا
جستارهای وابسته
منابع
- ↑
- ↑ Mei, Song; Montanari, Andrea; Nguyen, Phan-Minh (2018-08-14). "A mean field view of the landscape of two-layer neural networks". Proceedings of the National Academy of Sciences. 115 (33): E7665–E7671. doi:10.1073/pnas.1806579115. ISSN 0027-8424. PMID 30054315.
- ↑ "Unsupervised Feature Learning and Deep Learning Tutorial". deeplearning.stanford.edu (به انگلیسی). Archived from the original on 20 اكتبر 2018. Retrieved 2018-10-29.
- ↑ Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning (2008). Efficient, Feature-based, Conditional Random Field Parsing بایگانیشده در ۱۴ اوت ۲۰۱۸ توسط Wayback Machine. Proc. Annual Meeting of the ACL.
- ↑ LeCun, Yann A., et al. "Efficient backprop." Neural networks: Tricks of the trade. Springer Berlin Heidelberg, 2012. 9-48
- ↑ Díaz, Esteban and Guitton, Antoine. "Fast full waveform inversion with random shot decimation". SEG Technical Program Expanded Abstracts, 2011. 2804-2808
- ↑ S، Suryansh (۲۰۱۸-۰۳-۱۲). «Gradient Descent: All You Need to Know». Hacker Noon. بایگانیشده از اصلی در ۱ مه ۲۰۲۰. دریافتشده در ۲۰۱۸-۱۰-۲۹.
- ↑ Miller، Lachlan (۲۰۱۸-۰۱-۱۰). «Machine Learning week 1: Cost Function, Gradient Descent and Univariate Linear Regression». Medium. دریافتشده در ۲۰۱۸-۱۰-۲۹.
- ↑ Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. (8 October 1986). "Learning representations by back-propagating errors". Nature. 323 (6088): 533–536. Bibcode:1986Natur.323..533R. doi:10.1038/323533a0.
- ↑ Polyak, Boris T.; Juditsky, Anatoli B. (1992). "Acceleration of stochastic approximation by averaging" (PDF). SIAM J. Control Optim. 30 (4): 838–855. doi:10.1137/0330046. Archived from the original (PDF) on 12 January 2016. Retrieved 20 May 2019.
- ↑ Duchi, John; Hazan, Elad; Singer, Yoram (2011). "Adaptive subgradient methods for online learning and stochastic optimization" (PDF). Journal of Machine Learning Research. 12: 2121–2159. Archived from the original (PDF) on 28 May 2019. Retrieved 20 May 2019.
- ↑ Tieleman, Tijmen and Hinton, Geoffrey (2012). Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning
- ↑ Diederik, Kingma; Ba, Jimmy (2014). "Adam: A method for stochastic optimization". arXiv:1412.6980 [cs.LG].
- ↑ Zeiler, Matthew D. (2012). "ADADELTA: An adaptive learning rate method". arXiv:1212.5701 [cs.LG].
- ↑ Perla, Joseph (2014). "Notes on AdaGrad" (PDF). Archived from the original (PDF) on 2015-03-30.
- ↑ Zeiler, Matthew D. (2012). "ADADELTA: An adaptive learning rate method". arXiv:1212.5701 [cs.LG].
- ↑ Gupta, Maya R.; Bengio, Samy; Weston, Jason (2014). "Training highly multiclass classifiers" (PDF). JMLR. 15 (1): 1461–1492. Archived from the original (PDF) on 25 اكتبر 2018. Retrieved 21 May 2019.
- ↑ Hinton, Geoffrey. "Overview of mini-batch gradient descent" (PDF). pp. 27–29. Archived from the original (PDF) on 23 November 2016. Retrieved 27 September 2016.