Skip to content
بازگشت به نتایج جست‌وجو

کاهش گرادیان تصادفی (SGD)

معرفی‌شده توسط
Robbins, H. & Monro, S.
سال
1951
نوع
First-order iterative optimization algorithm

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

اندازه قلم

چه کاری انجام می‌دهد؟

کاهش گرادیان تصادفی (SGD) یک الگوریتم بهینه‌سازی تکراری مرتبه اول است که ریشه در چارچوب تقریب تصادفی معرفی شده توسط رابینز و مونرو در سال ۱۹۵۱ دارد. این الگوریتم با به‌روزرسانی پارامترهای مدل با استفاده از گرادیان محاسبه شده بر روی یک نمونه آموزشی تصادفی انتخاب شده (یا یک دسته کوچک) در هر مرحله، یک تابع هدف را کمینه می‌کند. این الگوریتم موتور بهینه‌سازی اصلی در پشت یادگیری ماشین مدرن و یادگیری عمیق است و امکان آموزش مدل‌ها را بر روی مجموعه داده‌هایی که برای جا گرفتن در حافظه بسیار بزرگ هستند، فراهم می‌کند.

شهود پشت روش

کاهش گرادیان معمولی، گرادیان دقیق تابع زیان را بر روی تمام نمونه‌های آموزشی قبل از انجام یک به‌روزرسانی پارامتر محاسبه می‌کند — این روش صحیح است اما برای مجموعه داده‌های بزرگ به طور غیرقابل تحملی کند است. SGD دقت را با سرعت معامله می‌کند: یک نمونه (یا یک دسته کوچک) را به طور تصادفی انتخاب می‌کند، تخمینی نویزی از گرادیان را محاسبه می‌کند و بلافاصله پارامترها را به‌روزرسانی می‌کند. این نویز صرفاً یک مزاحمت نیست؛ بلکه به عنوان یک تنظیم ضمنی عمل می‌کند و به بهینه‌ساز کمک می‌کند تا از حداقل‌های محلی کم‌عمق و نقاط زینی فرار کند. در طول تکرارهای متعدد، گام‌های نویزی میانگین‌گیری می‌شوند و پارامترها به سمت حداقل تابع زیان همگرا می‌شوند، بسیار شبیه به راه رفتن یک مست که همچنان به مقصد می‌رسد.

تاریخ

بنیان نظری SGD توسط هربرت رابینز و ساتون مونرو در مقاله سال ۱۹۵۱ آنها با عنوان 'A Stochastic Approximation Method' پایه‌گذاری شد، که اثبات کرد به‌روزرسانی‌های تکراری نویزی با اندازه گام کاهشی به ریشه یک تابع رگرسیون همگرا می‌شوند. ارتباط با بهینه‌سازی مبتنی بر گرادیان توسط کیفر و ولفوویتز (۱۹۵۲) و بعدها توسط قانون LMS ویدرو و هاف (۱۹۶۰) برای فیلترینگ تطبیقی به صراحت بیان شد. SGD در یادگیری ماشین از طریق کارهای لِکون و همکارانش در اواخر دهه ۱۹۸۰ و ۱۹۹۰ برای آموزش شبکه‌های عصبی از طریق پس‌انتشار (backpropagation) رواج یافت. انتشار آزمایش‌های مقیاس بزرگ توسط بوتو و همکارانش در دهه ۲۰۰۰ برتری SGD را نسبت به روش‌های دسته‌ای بر روی مجموعه داده‌های صنعتی نشان داد. فرمولاسیون مدرن SGD دسته‌ای کوچک با رنسانس یادگیری عمیق در حدود سال ۲۰۱۲ (AlexNet) جهانی شد و این الگوریتم همچنان بهینه‌ساز غالب در این حوزه است، با انواع آن مانند Adam (Kingma & Ba, 2014) که مستقیماً بر اساس قاعده به‌روزرسانی آن ساخته شده‌اند.

چه زمانی استفاده شود

SGD روش انتخابی است هر زمان که مجموعه آموزشی به اندازه‌ای بزرگ باشد که محاسبه گرادیان کامل در هر به‌روزرسانی پرهزینه باشد، که تقریباً تمام آموزش شبکه‌های عصبی مدرن و برازش مدل‌های خطی در مقیاس بزرگ را شامل می‌شود. این روش برای هر تابع زیان مشتق‌پذیر قابل اعمال است. مفروضات کلیدی: تابع زیان نسبت به پارامترها مشتق‌پذیر (یا زیرمشتق‌پذیر) است، نقاط داده به طور مستقل نمونه‌برداری می‌شوند و برآوردگر گرادیان بدون اریب است. برای اهداف قویاً محدب، SGD همگرایی O(1/T) را به دست می‌آورد؛ برای اهداف عمومی غیرمحدب (مانند شبکه‌های عمیق) در عمل نقاط ایستا را پیدا می‌کند، اگرچه تضمین بهینگی سراسری وجود ندارد. SGD دسته‌ای کوچک (اندازه دسته ۳۲-۵۱۲) معمولاً به SGD تک نمونه‌ای خالص ترجیح داده می‌شود زیرا برآوردهای گرادیان با واریانس کمتر ارائه می‌دهد و از موازی‌سازی در سخت‌افزارهای مدرن بهره می‌برد. هنگامی که مجموعه داده به اندازه‌ای کوچک است که کاهش گرادیان دسته‌ای کامل امکان‌پذیر باشد و هدف به خوبی شرطی شده باشد، روش‌های مرتبه دوم مانند L-BFGS ممکن است سریعتر همگرا شوند.

محدودیت‌ها و ملاحظات

  • برآوردهای گرادیان نویزی هستند که باعث می‌شود تابع زیان به جای کاهش یکنواخت، نوسان کند و تشخیص همگرایی را دشوارتر می‌کند.
  • به شدت به نرخ یادگیری حساس است: اگر خیلی بزرگ باشد باعث واگرایی می‌شود؛ اگر خیلی کوچک باشد آموزش را به طور غیرقابل تحملی کند می‌کند.
  • همگرایی به حداقل سراسری برای اهداف غیرمحدب مانند شبکه‌های عصبی عمیق تضمین نمی‌شود.
  • به‌روزرسانی‌های همسان‌گرد (Isotropic) به تمام ابعاد پارامتر به طور مساوی رفتار می‌کنند و آن را برای سطوح زیان با انحناهای بسیار متفاوت در امتداد محورهای مختلف نامناسب می‌سازد — که انگیزه‌ای برای انواع نرخ تطبیقی است.
  • نیاز به تنظیم دقیق برنامه نرخ یادگیری دارد؛ برنامه‌های ضعیف عملکرد نهایی را به طور قابل توجهی کاهش می‌دهند.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • به مجموعه داده‌های دلخواه بزرگ مقیاس می‌شود زیرا هر به‌روزرسانی فقط به یک نمونه یا یک دسته کوچک نیاز دارد و حافظه و محاسبات در هر مرحله ثابت می‌ماند.
  • نویز داخلی، تنظیم ضمنی را فراهم می‌کند و به فرار از حداقل‌های محلی کم‌عمق و نقاط زینی در مناظر غیرمحدب کمک می‌کند.
  • بسیار عمومی: قابل اعمال به هر تابع زیان مشتق‌پذیر، از جمله آنتروپی متقاطع، میانگین خطای مربعات، زیان لولایی و اهداف سفارشی.
  • بنیان تقریباً تمام بهینه‌سازهای مدرن (Adam, RMSProp, AdaGrad, Nesterov momentum) را تشکیل می‌دهد — درک SGD پیش‌نیاز درک آن‌هاست.
  • پیاده‌سازی و موازی‌سازی آسان بر روی GPUها با استفاده از دسته‌های کوچک.

کاربردها

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

چگونه کار می‌کند

چگونه کار می‌کند

1

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

فرمول
L(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(f(x_i; \theta),\, y_i)
2

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

فرمول
\hat{g}_t = \nabla_\theta \ell(f(x_{i_t}; \theta_t),\, y_{i_t})
3

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

فرمول
\theta_{t+1} = \theta_t - \eta_t \, \hat{g}_t
4

شرایط رابینز-مونرو (مجموع نرخ‌ها واگرا می‌شود، مجموع مربع نرخ‌ها همگرا می‌شود) همگرایی را برای اهداف محدب تضمین می‌کند. در عمل، برنامه‌های رایج شامل کاهش پله‌ای، میرایی کسینوسی و راه‌اندازی مجدد گرم هستند؛ این شرایط مبنای نظری را برای چرایی ضرورت یک برنامه کاهشی فراهم می‌کنند.

فرمول
\sum_{t=1}^{\infty} \eta_t = \infty, \quad \sum_{t=1}^{\infty} \eta_t^2 < \infty

دام‌های رایج

  • استفاده از نرخ یادگیری ثابت در طول آموزش بدون هیچ برنامه کاهشی، که باعث می‌شود بهینه‌ساز به جای تثبیت شدن در حداقل، در اطراف آن نوسان کند.
  • انتخاب اندازه دسته بدون در نظر گرفتن اثر تنظیم ضمنی: دسته‌های بسیار بزرگ نویز را کاهش می‌دهند و می‌توانند به تعمیم‌پذیری در مقایسه با دسته‌های کوچکتر در همان تعداد دوره‌ها آسیب برسانند.
  • فراموش کردن مخلوط کردن داده‌های آموزشی قبل از هر دوره، که می‌تواند سوگیری سیستماتیک را هنگام مرتب‌سازی داده‌ها بر اساس کلاس یا زمان معرفی کند.
  • تنظیم نرخ یادگیری فقط بر اساس زیان اعتبارسنجی یک بار به جای نظارت بر منحنی‌های آموزش، از دست دادن نشانه‌های واگرایی یا فلات زودرس.
  • رفتار با SGD به عنوان یک بهینه‌ساز جعبه سیاه بدون درک خواص همگرایی آن، سپس کورکورانه به Adam روی آوردن زمانی که همگرایی کند به نظر می‌رسد بدون تشخیص علت ریشه‌ای.

پرسش‌های متداول

تفاوت بین SGD، SGD دسته‌ای کوچک و کاهش گرادیان دسته‌ای کامل چیست؟

کاهش گرادیان دسته‌ای کامل، گرادیان دقیق را بر روی تمام n نمونه آموزشی در هر به‌روزرسانی محاسبه می‌کند — دقیق اما با هزینه O(n) در هر مرحله. SGD خالص از دقیقاً یک نمونه انتخاب شده تصادفی در هر به‌روزرسانی استفاده می‌کند — هزینه O(1) اما بسیار نویزی. SGD دسته‌ای کوچک از یک زیرمجموعه تصادفی کوچک (معمولاً ۳۲-۵۱۲ نمونه) استفاده می‌کند — یک مصالحه عملی که نویز را کاهش می‌دهد در حالی که هزینه را قابل مدیریت نگه می‌دارد و از موازی‌سازی GPU بهره می‌برد. در استفاده مدرن، 'SGD' تقریباً همیشه به معنای SGD دسته‌ای کوچک است.

چگونه باید نرخ یادگیری را تنظیم کنم؟

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

چرا SGD گاهی اوقات بهتر از Adam تعمیم می‌یابد؟

بهینه‌سازهای با نرخ تطبیقی مانند Adam اغلب سریعتر همگرا می‌شوند اما می‌توانند بیشتر بیش‌برازش (overfit) کنند، به ویژه در وظایف طبقه‌بندی تصویر. نویز بالاتر در SGD — به ویژه در اندازه‌های دسته کوچک — به عنوان تنظیم ضمنی عمل می‌کند و به مدل کمک می‌کند تا حداقل‌های مسطح‌تری را پیدا کند که بهتر تعمیم می‌یابند. چندین مطالعه تجربی (مانند ویلسون و همکاران، ۲۰۱۷) این پدیده را مستند کرده‌اند، به همین دلیل است که SGD با تکانه همچنان برای آموزش مدل‌های بینایی کامپیوتر مانند ResNet ترجیح داده می‌شود.

آیا SGD تضمین می‌کند که حداقل سراسری را پیدا کند؟

فقط برای اهداف قویاً محدب، تحت شرایط اندازه گام رابینز-مونرو. برای اهداف غیرمحدب (تقریباً تمام شبکه‌های عمیق)، SGD به یک نقطه ایستا (که در آن گرادیان صفر است) همگرا می‌شود، که در عمل تمایل دارد یک حداقل محلی خوب باشد تا یک نقطه زینی یا حداقل سراسری. به طور تجربی، راه‌حل‌های یافت شده اغلب برای عملکرد پیشرفته کافی هستند.

روش‌های مرتبط

منابع

  1. Robbins, H. & Monro, S. (1951). A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3), 400–407.

    باز کردن مرجع DOI
    کپی شد.
  2. Goodfellow, I., Bengio, Y. & Courville, A. (2016). Deep Learning (Ch. 8). MIT Press.

    شابک: 978-0-262-03561-3
    کپی شد.