Рання зупинка

На зображенні показано проблему перенавчання в машинному навчанні. Червоні точки являють собою дані для навчальних наборів. Зелена лінія відображає справжній функціональний зв'язок, а синя лінія показує функцію, яка була вивчена. Така ситуація називається перенавчанням.

Алгоритми машинного навчання тренують модель на скінченному наборі навчальних даних. Під час навчання модель оцінюється щодо того, наскільки добре вона прогнозує спостереження, на тих даних, які є в навчальному наборі. Загалом, мета машинного навчання полягає в тому, щоб створити модель, яка узагальнює, тобто робить прогнози на спостереженнях, які раніше не траплялись. Перенавчання відбувається тоді, коли модель добре вписується в дані тренувального набору, одночасно з тим має велику помилку узагальнення.

Регуляризація, в контексті машинного навчання, відноситься до процесу зміни алгоритму навчання з метою запобігання перенавчання. Це, як правило, передбачає накладання певного обмеження гладкості на вивчену модель[1]. Ця гладкість може бути затребувана явно, коли фіксується кількість параметрів у моделі, або через зміну функції втрат, як у регуляризації Тихонова. Регуляція Тихонова, разом з регресією головних компонент і багатьма іншими схемами регуляризації, відноситься до спектральної регуляризації, регуляризації, яка характеризується застосуванням фільтра. До цього класу методів належить і рання зупинка.

Методи градієнтного спуску — ітераційні методи оптимізації першого порядку. Кожна ітерація оновлює приблизне рішення задачі оптимізації, роблячи крок у від'ємному напрямку градієнта цільової функції. Вибираючи відповідний розмір кроку, такий метод може збігатись до локального мінімуму цільової функції. Градієнтний спуск використовується в машинному навчанні через визначення функції втрат, яка відображає помилку на навчальному наборі, а потім відбувається мінімізація функції.

Рання зупинка може бути використана для регуляризації непараметричних задач регресії, які виникають в машинному навчанні. Для заданого простору вхідних даних ${\displaystyle X}$, простору виводу ${\displaystyle Y}$ і зразків, які взяті з невідомої ймовірнісної міри ${\displaystyle \rho }$ на ${\displaystyle Z=X\times Y}$, метою таких задач є наближення функцією регресії ${\displaystyle f_{\rho }}$, яка задається як

${\displaystyle f_{\rho }(x)=\int _{Y}yd\rho (y|x),x\in X}$,

де ${\displaystyle \rho (y|x)}$ є умовним розподілом на ${\displaystyle x}$ індукованим ${\displaystyle \rho }$[2].

Один загальний вибір для апроксимації функції регресії полягає у використанні функцій з відтворювального ядра Гільбертового простору[2]. Ці простори можуть мати нескінченну кількість вимірів, які містять рішення, що відповідають перенавчанню на навчальних наборах довільного розміру. Таким чином, регуляризація особливо важлива для цих методів. Один із способів регулювання непараметричних задач регресії полягає в застосуванні правила ранньої зупинки до ітераційної процедури, такої як спуск градієнта.

Правила ранньої зупинки, запропоновані для цих задач, ґрунтуються на аналізі верхніх меж похибки узагальнення як функції числа ітерації. Вони дають приписи щодо кількості ітерацій для запуску, які можна обчислити до початку процесу розв'язання[3][4].

Підсилення відноситься до сімейства алгоритмів, в яких множина слабких учнів (учні, які лише злегка корелюють зі справжнім процесом) об'єднуються для отримання сильного учня. Було показано, що для декількох алгоритмів підсилення (включаючи AdaBoost) регуляризація за допомогою ранньої зупинки може забезпечити гарантії узгодженості, тобто, результат отриманий при підсиленні наближається до справжнього рішення, оскільки кількість зразків прямує до нескінченності[5][6][7].

Методи підсилення мають тісні зв'язки з методами градієнтного спуску, описаними вище, і можуть розглядатися як метод підсилення, заснований на ${\displaystyle L_{2}}$ втратах: L₂Boost[3].