توقف زودهنگام

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

پیش‌زمینه[ویرایش]

بعضی مباحث یادگیری ماشین که دانستن آنها برای درک توقف زودهنگام مفید است:

بیش برازش[ویرایش]

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

منظم‌سازی[ویرایش]

در چارچوب یادگیری ماشین، منظم‌سازی یعنی تغییر الگوریتم یادگیری به طوری که از بیش‌برازش جلوگیری شود. معمولا با اعمال یک شرط هموار سازی چنین کاری رخ می‌دهد.^[۱] این هموارسازی می‌تواند به صورت صریح با محدود کردن تعداد پارامترهای مدل، یا به صورت ضمنی با تغییر تابع هزینه صورت بگیرد (همچون رگرسیون ریج).

روش‌های گرادیان کاهشی[ویرایش]

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

توقف زودهنگام مبتنی بر روش‌های تحلیلی[ویرایش]

توقف زود‌هنگام در تئوری یادگیری آماری[ویرایش]

توقف زودهنگام می‌تواند برای منظم‌سازی مسائل رگرسیون بدون پارامتر کارگشا باشد. برای فضای ورودی $X$ و خروجی $Y$ ، و نمونه‌هایی که از یک توزیع نامعلوم بر $X\times Y$ به دست آمده‌اند، هدف چنین مسائلی تقریب یک تابع رگریسون به صورت زیر است:

$f_{\rho }(x)=\int _{Y}y\,d\rho (y\mid x),\,x\in X$

که در آن $\rho (y\mid x)$ بیانگر احتمال شرطی $y$ به شرط $x$ می‌باشد.^[۲]

توقف زودهنگام در بوستینگ[ویرایش]

بوستینگ به خانواده‌ای از الگوریتم‌ها گفته می‌شود که در آن تعدادی یادگیرنده ضعیف (مدل‌هایی که همبستگی کمی با هدف مسئله دارند) با یکدیگر ترکیب شده تا یک یادگیرنده قوی ایجاد کنند. نشان داده شده است که منظم‌سازی از طریق توقف زودرس، موجب می‌شود حاصل حدی الگوریتم برای تعداد بی‌نهایت داده به مقدار واقعی تابع هدف میل کند.^[۳]^[۴]^[۵]

توقف زودهنگام مبتنی بر اعتبارسنجی[ویرایش]

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

البته انواع پیچیده‌تری مبتنی بر اعتبارسنجی متقابل نیز وجود دارند. از آنجا که ممکن است چندین کمینه محلی طی فرآیند یادگیری تولید شود، به طور قطعی نمی‌توان گفت بیش‌برازش از کجا شروع شده‌است و معمولا این مورد به طور تجربی مشخص می‌شود.^[۶]

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

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

↑ Girosi, F.; Jones, Michael J.; Poggio, T. (1995). "Regularization Theory and Neural Networks Architectures". Neural Computation (به انگلیسی).
↑ Smale, Steve; Zhou, Ding-Xuan (2007-08-01). "Learning Theory Estimates via Integral Operators and Their Approximations". Constructive Approximation (به انگلیسی). 26 (2): 153–172. doi:10.1007/s00365-006-0659-y. ISSN 1432-0940.
↑ Wenxin Jiang (February 2004). "Process consistency for AdaBoost". The Annals of Statistics. 32 (1): 13–29. doi:10.1214/aos/1079120128. ISSN 0090-5364.
↑ Bühlmann, Peter; Bin Yu (2003-06-01). "Boosting with the L₂ Loss: Regression and Classification". Journal of the American Statistical Association. 98 (462): 324–339. doi:10.1198/016214503000125. ISSN 0162-1459. JSTOR 30045243. S2CID 123059267.
↑ Tong Zhang; Bin Yu (2005-08-01). "Boosting with Early Stopping: Convergence and Consistency". The Annals of Statistics. 33 (4): 1538–1579. arXiv:math/0508276. Bibcode:2005math......8276Z. doi:10.1214/009053605000000255. ISSN 0090-5364. JSTOR 3448617. S2CID 13158356.
↑ Prechelt, Lutz; Geneviève B. Orr (2012-01-01). "Early Stopping — But When?". In Grégoire Montavon; Klaus-Robert Müller (eds.). Neural Networks: Tricks of the Trade. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 53–67. doi:10.1007/978-3-642-35289-8_5. ISBN 978-3-642-35289-8.

[1] Girosi, F.; Jones, Michael J.; Poggio, T. (1995). "Regularization Theory and Neural Networks Architectures". Neural Computation (به انگلیسی).

[2] Smale, Steve; Zhou, Ding-Xuan (2007-08-01). "Learning Theory Estimates via Integral Operators and Their Approximations". Constructive Approximation (به انگلیسی). 26 (2): 153–172. doi:10.1007/s00365-006-0659-y. ISSN 1432-0940.

[3] Wenxin Jiang (February 2004). "Process consistency for AdaBoost". The Annals of Statistics. 32 (1): 13–29. doi:10.1214/aos/1079120128. ISSN 0090-5364.

[4] Bühlmann, Peter; Bin Yu (2003-06-01). "Boosting with the L₂ Loss: Regression and Classification". Journal of the American Statistical Association. 98 (462): 324–339. doi:10.1198/016214503000125. ISSN 0162-1459. JSTOR 30045243. S2CID 123059267.

[5] Tong Zhang; Bin Yu (2005-08-01). "Boosting with Early Stopping: Convergence and Consistency". The Annals of Statistics. 33 (4): 1538–1579. arXiv:math/0508276. Bibcode:2005math......8276Z. doi:10.1214/009053605000000255. ISSN 0090-5364. JSTOR 3448617. S2CID 13158356.

[prechelt_early_2012-6] Prechelt, Lutz; Geneviève B. Orr (2012-01-01). "Early Stopping — But When?". In Grégoire Montavon; Klaus-Robert Müller (eds.). Neural Networks: Tricks of the Trade. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 53–67. doi:10.1007/978-3-642-35289-8_5. ISBN 978-3-642-35289-8.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]