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

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

Тло ред.

У цьому розділі представлені деякі основні концепції машинного навчання, необхідні для опису методів ранньої зупинки.

Перенавчання ред.

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

Докладніше: Перенавчання

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

Регуляризація ред.

Докладніше: Регуляризація (математика)

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

Методи градієнтного спуску ред.

Докладніше: Градієнтний спуск

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

Ранні зупинки на основі аналітичних результатів ред.

Рання зупинка в статистичній теорії навчання ред.

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

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

,

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

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

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

Рання зупинка у процесі підсилення ред.

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

$L_{2}$ -посилення ред.

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

Рання зупинка на основі перевірки ред.

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

Розділити навчальні дані на навчальний набір і перевірочний набір, наприклад, у пропорції 2 до 1.

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

Зупиніть тренування, як тільки помилка на перевірочному наборі стане вище, ніж це було в останній раз.

Використовуйте ті ваги, які мережа мала на попередньому кроці, як результат циклу навчання.

— Лутц Пречелт, 'Рання зупинка – але коли?'

Більш складною за формою є використання перехресного затверджування — численні розбиття даних на навчальний набір і перевірочний набір — замість одного поділу на навчальний і перевірочний набір. Навіть ця проста процедура ускладнюється на практиці тим, що помилка перевірки може коливатися під час навчання, утворюючи декілька локальних мінімумів. Таке ускладнення призвело до створення багатьох ad hoc правил для вирішення питання про початок перенавчання^[8].

Див. також ред.

Перенавчання, рання зупинка є одним з методів, що використовуються для запобігання перенавчання
Похибка узагальнення
Регуляризація (математика)
Теорія статистичного навчання
Підсилювання (машинне навчання)
Перехресне затверджування, зокрема, за допомогою «набору перевірки»
Штучна нейронна мережа

Примітки ред.

↑ Girosi, Federico; Michael Jones; Tomaso Poggio (1 березня 1995). Regularization Theory and Neural Networks Architectures. Neural Computation. 7 (2): 219—269. CiteSeerX 10.1.1.48.9258. doi:10.1162/neco.1995.7.2.219. ISSN 0899-7667.
↑ ^а ^б Smale, Steve; Ding-Xuan Zhou (1 серпня 2007). Learning Theory Estimates via Integral Operators and Their Approximations. Constructive Approximation. 26 (2): 153—172. CiteSeerX 10.1.1.210.722. doi:10.1007/s00365-006-0659-y. ISSN 0176-4276.
↑ ^а ^б Yao, Yuan; Lorenzo Rosasco; Andrea Caponnetto (1 серпня 2007). On Early Stopping in Gradient Descent Learning. Constructive Approximation. 26 (2): 289—315. CiteSeerX 10.1.1.329.2482. doi:10.1007/s00365-006-0663-2. ISSN 0176-4276.
↑ Raskutti, G.; M.J. Wainwright; Bin Yu (2011). Early stopping for non-parametric regression: An optimal data-dependent stopping rule. 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). с. 1318—1325. doi:10.1109/Allerton.2011.6120320.
↑ 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 (1 червня 2003). 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.
↑ Tong Zhang; Bin Yu (1 серпня 2005). Boosting with Early Stopping: Convergence and Consistency. The Annals of Statistics. 33 (4): 1538—1579. arXiv:math/0508276. doi:10.1214/009053605000000255. ISSN 0090-5364. JSTOR 3448617.
↑ Prechelt, Lutz; Geneviève B. Orr (1 січня 2012). Early Stopping — But When?. У Grégoire Montavon, Klaus-Robert Müller (eds.) (ред.). Neural Networks: Tricks of the Trade. Lecture Notes in Computer Science. Springer Berlin Heidelberg. с. 53–67. doi:10.1007/978-3-642-35289-8_5. ISBN 978-3-642-35289-8.

[1] Girosi, Federico; Michael Jones; Tomaso Poggio (1 березня 1995). Regularization Theory and Neural Networks Architectures. Neural Computation. 7 (2): 219—269. CiteSeerX 10.1.1.48.9258. doi:10.1162/neco.1995.7.2.219. ISSN 0899-7667.

[smale_learning_2007-2] а ^б Smale, Steve; Ding-Xuan Zhou (1 серпня 2007). Learning Theory Estimates via Integral Operators and Their Approximations. Constructive Approximation. 26 (2): 153—172. CiteSeerX 10.1.1.210.722. doi:10.1007/s00365-006-0659-y. ISSN 0176-4276.

[yao_early_2007-3] а ^б Yao, Yuan; Lorenzo Rosasco; Andrea Caponnetto (1 серпня 2007). On Early Stopping in Gradient Descent Learning. Constructive Approximation. 26 (2): 289—315. CiteSeerX 10.1.1.329.2482. doi:10.1007/s00365-006-0663-2. ISSN 0176-4276.

[raskutti_early_2011-4] Raskutti, G.; M.J. Wainwright; Bin Yu (2011). Early stopping for non-parametric regression: An optimal data-dependent stopping rule. 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). с. 1318—1325. doi:10.1109/Allerton.2011.6120320.

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

[6] Bühlmann, Peter; Bin Yu (1 червня 2003). 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.

[7] Tong Zhang; Bin Yu (1 серпня 2005). Boosting with Early Stopping: Convergence and Consistency. The Annals of Statistics. 33 (4): 1538—1579. arXiv:math/0508276. doi:10.1214/009053605000000255. ISSN 0090-5364. JSTOR 3448617.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]