Підсилювання (машинне навчання)

Підси́лювання (англ. boosting) — це ансамблевий мета-алгоритм машинного навчання передусім для зменшення зсуву а також і дисперсії^[1] у керованім навчанні, та сімейство алгоритмів машинного навчання, які перетворюють слабких учнів на сильних.^[2] Підсилювання ґрунтується на питанні, поставленому Кірнсом^[en] і Веліентом (1988, 1989):^[3]^[4] Чи може набір слабких учнів (англ. weak learners) утворити єдиного сильного учня (англ. strong learner)? Слабкого учня визначають як класифікатор, який лише трохи корелює зі справжньою класифікацією (він може мітити зразки краще за випадкове вгадування). На противагу, сильний учень є класифікатором, який корелює зі справжньою класифікацією доволі добре.

Ствердна відповідь Роберта Шапіра на питання Кірнса та Веліента в праці 1990 року^[5] мала значні наслідки в машинному навчанні та статистиці, найголовніше, призвівши до розробки підсилювання.^[6]

Коли її вперше було представлено, задача підсилювання гіпотези (англ. hypothesis boosting problem) означала просто процес перетворення слабкого учня на сильного. «Неформально, задача [підсилювання гіпотези] ставить питання, чи ефективний алгоритм навчання […], який видає гіпотезу, чия ефективність лише трохи краща за випадкове вгадування [тобто, слабкий учень], означає існування ефективного алгоритму, який видає гіпотезу довільної точності [тобто, сильного учня].»^[3] Алгоритми, що швидко досягають підсилювання гіпотези, стали називати просто «підсилюванням». ARCing (англ. Adapt[at]ive Resampling and Combining, адаптивна перевібирка та об'єднування) Фройнда^[en] та Шапіро,^[7] як загальна методика, є більш-менш синонімічною підсилюванню.^[8]

Алгоритми підсилювання

Хоча підсилювання й не є обмеженим алгоритмічно, більшість алгоритмів підсилювання складаються з ітеративного навчання слабких класифікаторів стосовно розподілу та додавання їх до кінцевого сильного класифікатора. Коли вони додаються, вони, як правило, зважуються певним чином, зазвичай пов'язаним з точністю слабких учнів. Після додавання слабкого учня дані ваги змінюються: неправильно класифіковані приклади набирають ваги, а класифіковані правильно вагу втрачають (деякі алгоритми підсилювання насправді зменшують вагу повторювано неправильно класифікованих прикладів, наприклад, підсилювання більшістю [англ. boost by majority] та BrownBoost^[en]). Таким чином, майбутні слабкі учні більше зосереджуються на тих прикладах, які попередні слабкі учні класифікували неправильно.

Алгоритмів підсилювання існує багато. Первинні, запропоновані Робертом Шапіро (рекурсивне більшісно-вентильне формулювання, англ. a recursive majority gate formulation^[5]) та Йоавом Фройндом^[en] (підсилювання більшістю, англ. boost by majority^[9]), не були адаптивними й не могли повною мірою користуватися перевагами слабких учнів. Проте Шапіро та Фройнд потім розробили AdaBoost^[en], адаптивний алгоритм підсилювання, який виграв престижну премію Геделя.

Алгоритмами підсилювання (англ. boosting algorithms) можна з точністю називати лише ті алгоритми, які довідно є алгоритмами підсилювання в формулюванні ймовірно приблизно правильного навчання. Інші алгоритми, подібні за духом до алгоритмів підсилювання, іноді називають «алгоритмами підважування» (англ. leveraging algorithms), хоча їх іноді неправильно називають й алгоритмами підсилювання.^[9]

Основна відмінність між багатьма алгоритмами підсилювання полягає в їхніх методах зважування тренувальних точок даних та гіпотез. AdaBoost^[en] є дуже популярним і, мабуть, найважливішим історично, оскільки він був першим алгоритмом, який зміг адаптуватися до слабких учнів. Проте існує багато новіших алгоритмів, таких як LPBoost^[en], TotalBoost, BrownBoost^[en], Xgboost, MadaBoost, LogitBoost^[en] та інші. Багато алгоритмів підсилювання вписуються в систему AnyBoost,^[9] яка показує, що підсилювання виконує градієнтний спуск у просторі функцій за допомогою опуклої функції витрат.

Категоризація об'єктів

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

Задача категоризації об'єктів

Категоризація об'єктів є типовим завданням комп'ютерного зору, яке передбачає визначення того, чи містить зображення певну категорію об'єктів, чи ні. Ця ідея тісно пов'язана з розпізнаванням, ідентифікацією та виявленням. Категоризація об'єктів на основі зовнішнього вигляду зазвичай включає виділяння ознак, навчання класифікатора та застосування цього класифікатора до нових прикладів. Існує багато способів представляти категорію об'єктів, наприклад, з аналізу форми^[en], моделей торби слів, або локальних дескрипторів, таких як SIFT тощо. Прикладами керованих класифікаторів є наївний баєсів класифікатор, ОВМ, суміші ґаусіанів^[en], нейронна мережа тощо. Проте дослідження показали, що категорії об'єктів та їх розташування в зображеннях можливо також виявляти й некерованим чином.^[10]

Стан справ у категоризації об'єктів

Розпізнавання категорій об'єктів у зображеннях є складною проблемою в комп'ютерному зорі, особливо коли кількість категорій є великою. Це пов'язано з високою мінливістю всередині класів та потребою в узагальненні над різними варіаціями об'єктів у межах однієї категорії. Об'єкти в межах однієї категорії можуть виглядати вельми по-різному. Навіть той самий об'єкт може виглядати несхожо за різних точок огляду, масштабів^[en] та освітлення^[en]. Захаращене тло та часткове перекриття теж додають труднощів до розпізнавання.^[11] Люди здатні розпізнавати тисячі типів об'єктів, тоді як більшість наявних систем розпізнавання об'єктів тренуються розпізнавати лише декілька, наприклад, людське обличчя, автомобіль, прості об'єкти тощо.^[12] Були дуже активними дослідження порядкування більшою кількістю категорій та забезпечення інкрементного додавання нових категорій, і, хоча загальна задача залишається нерозв'язаною, було розроблено кілька багатокатегорійних систем виявлення об'єктів (для сотень та тисяч категорій^[13]). Одними зі способів є спільні ознаки (англ. feature sharing) та підсилювання.

Підсилювання для бінарної категоризації

AdaBoost можливо використовувати для виявлення облич як приклад бінарної категоризації. Двома категоріями є обличчя та тло. Загальний алгоритм виглядає наступним чином:

Сформувати великий набір простих ознак
Встановити початкові ваги для тренувальних зображень
Для Т раундів
1. Унормувати ваги
2. Для наявних ознак із набору, натренувати класифікатор із застосуванням єдиної ознаки та оцінити похибку тренування
3. Обрати класифікатор із найнижчою похибкою
4. Уточнити ваги тренувальних зображень: збільшити, якщо цим класифікатором класифіковано неправильно, і зменшити, якщо правильно
Сформувати остаточний сильний класифікатор як лінійну комбінацію цих T класифікаторів (коефіцієнт більший, якщо помилка тренування є невеликою)

Після підсилювання, класифікатор, побудований з 200 ознак, може забезпечити 95-відсотковий рівень виявлення за рівня хибного виявлення в $10^{-5}$ .^[14]

Ще одним застосуванням підсилювання для бінарної категоризації є система, яка виявляє пішоходів, використовуючи характери руху та вигляду.^[15] Ця робота є першою, яка об'єднала як інформацію про рух, так і інформацію про вигляд, як ознаки для виявлення людини, що йде. Вона використовує подібний підхід у системі виявляння об'єктів Віоли — Джонса.

Підсилювання для багатокласової категоризації

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

Основна послідовність алгоритму є подібною до бінарного випадку. Різниця полягає в тім, що міру похибки спільного навчання повинно бути визначено заздалегідь. Під час кожної ітерації алгоритм обирає класифікатор однієї ознаки (заохочуються ознаки, які можуть бути спільними з іншими категоріями). Це можливо здійснювати шляхом перетворення багатокласової класифікації на бінарну (набір категорій проти решти),^[16] або шляхом введення штрафної похибки з категорій, які не мають цієї ознаки класифікатора.^[17]

У праці «Sharing visual features for multiclass and multiview object detection», А. Торральба зі співавторами використали для підсилювання GentleBoost, та показали, що, коли тренувальні дані є обмеженими, навчання через спільні ознаки виконує роботу набагато краще, ніж без спільних ознак, за однакових раундів підсилювання. Також, для заданого рівня ефективності спостерігається, що загальна кількість необхідних ознак (а отже, і витрати часу виконання класифікатором) для детекторів зі спільними ознаками масштабується відносно кількості класів приблизно логарифмічно, тобто повільніше, ніж лінійне^[en] зростання у випадку без спільних ознак. Подібні результати показано й у праці «Incremental learning of object detectors using a visual shape alphabet», тільки автори використовували для підсилювання AdaBoost^[en].

Опуклі та неопуклі алгоритми підсилювання

Алгоритми підсилювання можуть ґрунтуватися на алгоритмах опуклої та неопуклої оптимізації. Опуклі алгоритми, такі як AdaBoost^[en] та LogitBoost^[en], може бути «переможено» випадковим шумом таким чином, що вони не зможуть навчатися простих та доступних для навчання комбінацій слабких гіпотез.^[18]^[19] На це обмеження було вказано Лонгом та Серведіо 2008 року. Проте, станом на 2009 рік, декілька авторів показали, що алгоритми підсилювання на основі неопуклої оптимізації, такі як BrownBoost^[en], можуть навчатися із зашумлених наборів даних, і можуть навчатися конкретно класифікатора, що лежить в основі набору даних Лонга — Серведіо.

Див. також

Втілення

Scikit-learn, відкрита бібліотека машинного навчання для python
Orange^[en], безкоштовний пакет програмного забезпечення добування даних, модуль Orange.sensemble [Архівовано 4 березня 2016 у Wayback Machine.]
Weka — це набір інструментів машинного навчання, який пропонує різноманітні втілення алгоритмів підсилювання, таких як AdaBoost та LogitBoost
Пакет R GBM [Архівовано 11 листопада 2018 у Wayback Machine.] (Generalized Boosted Regression Models) втілює розширення алгоритму AdaBoost Фройнда та Шапіро, та машини градієнтного підсилювання Фрідмана.
jboost [Архівовано 18 лютого 2019 у Wayback Machine.]: AdaBoost, LogitBoost, RobustBoost, Boostexter та чергувальні дерева рішень
Пакет R adabag [Архівовано 17 вересня 2018 у Wayback Machine.]: застосовує Multiclass AdaBoost.M1, AdaBoost-SAMME та Bagging
Пакет R xgboost [Архівовано 26 жовтня 2018 у Wayback Machine.]: втілення градієнтного підсилювання для лінійних моделей та моделей на основі дерев.

Примітки

Виноски

↑ Leo Breiman^[en] (1996). BIAS, VARIANCE, AND ARCING CLASSIFIERS (PDF). TECHNICAL REPORT. Архів оригіналу (PDF) за 19 січня 2015. Процитовано 19 січня 2015. У зниженні дисперсії Arcing [Підсилювання] є успішнішим за bagging {{cite web}}: Перевірте значення |last1= (довідка) (англ.)
↑ Zhou Zhi-Hua^[en] (2012). Ensemble Methods: Foundations and Algorithms. Chapman and Hall/CRC. с. 23. ISBN 978-1439830031. Термін підсилювання стосується сімейства алгоритмів, здатних перетворювати слабких учнів на сильних {{cite book}}: Перевірте значення |last= (довідка) (англ.)
↑ ^а ^б Michael Kearns(1988); Thoughts on Hypothesis Boosting [Архівовано 13 липня 2019 у Wayback Machine.], Unpublished manuscript (Machine Learning class project, December 1988) (англ.)
↑ Michael Kearns^[en]; Leslie Valiant (1989). Crytographic limitations on learning Boolean formulae and finite automata. Symposium on Theory of computing. ACM. 21: 433—444. doi:10.1145/73007.73049. Архів оригіналу за 1 квітня 2017. Процитовано 18 січня 2015. {{cite journal}}: Перевірте значення |last= (довідка) (англ.)
↑ ^а ^б Schapire, Robert E. (1990). The Strength of Weak Learnability (PDF). Machine Learning. Boston, MA: Kluwer Academic Publishers. 5 (2): 197—227. CiteSeerX 10.1.1.20.723. doi:10.1007/bf00116037. Архів оригіналу (PDF) за 10 жовтня 2012. Процитовано 7 травня 2018. (англ.)
↑ Leo Breiman^[en] (1998). Arcing classifier (with discussion and a rejoinder by the author). Ann. Stat. 26 (3): 801—849. doi:10.1214/aos/1024691079. Архів оригіналу за 2 червня 2018. Процитовано 17 листопада 2015. Шапіро (1990) довів, що підсилювання є можливим. (с. 823) {{cite journal}}: Перевірте значення |last= (довідка) (англ.)
↑ Yoav Freund and Robert E. Schapire (1997); A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting [Архівовано 24 березня 2018 у Wayback Machine.], Journal of Computer and System Sciences, 55(1):119-139 (англ.)
↑ Leo Breiman (1998); Arcing Classifier (with Discussion and a Rejoinder by the Author) [Архівовано 19 листопада 2018 у Wayback Machine.], Annals of Statistics, vol. 26, no. 3, pp. 801—849 (англ.): «Ідею слабкого навчання було представлено Кірнсом та Веліентом (1988, 1989), які залишили відкритим питання про те, чи є слабка й сильна навчаність еквівалентними. Це питання було названо задачею підсилювання , оскільки [розв'язок мусив] підсилювати низьку точність слабкого учня до високої точності сильного учня. Шапіро 1990 року довів, що підсилювання є можливим. Алгоритм підсилювання — це метод, який бере слабкого учня, і перетворює його на сильного. Фройнд та Шапіро 1997 року довели, що алгоритм, подібний до arc-fs, є підсилюванням.»
↑ ^а ^б ^в Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean (2000); Boosting Algorithms as Gradient Descent , in S. A. Solla, T. K. Leen, and K.-R. Muller, editors, Advances in Neural Information Processing Systems 12, pp. 512—518, MIT Press (англ.)
↑ Sivic, Russell, Efros, Freeman & Zisserman, «Discovering objects and their location in images», ICCV 2005 (англ.)
↑ A. Opelt, A. Pinz, et al., «Generic Object Recognition with Boosting», IEEE Transactions on PAMI 2006 (англ.)
↑ M. Marszalek, «Semantic Hierarchies for Visual Object Recognition», 2007 (англ.)
↑ Large Scale Visual Recognition Challenge. December 2017. Архів оригіналу за 2 листопада 2018. (англ.)
↑ P. Viola, M. Jones, «Robust Real-time Object Detection», 2001 (англ.)
↑ Viola, P.; Jones, M.; Snow, D. (2003). Detecting Pedestrians Using Patterns of Motion and Appearance (PDF). ICCV. Архів оригіналу (PDF) за 22 вересня 2017. Процитовано 7 травня 2018. (англ.)
↑ A. Torralba, K. P. Murphy, et al., «Sharing visual features for multiclass and multiview object detection», IEEE Transactions on PAMI 2006 (англ.)
↑ A. Opelt, et al., «Incremental learning of object detectors using a visual shape alphabet», CVPR 2006 (англ.)
↑ P. Long and R. Servedio. 25th International Conference on Machine Learning (ICML), 2008, pp. 608—615. (англ.)
↑ Long, Philip M.; Servedio, Rocco A. (March 2010). Random classification noise defeats all convex potential boosters (PDF). Machine Learning. Springer US. 78 (3): 287—304. doi:10.1007/s10994-009-5165-z. Архів оригіналу (PDF) за 6 липня 2017. Процитовано 17 листопада 2015. (англ.)

До уваги

Yoav Freund and Robert E. Schapire (1997); A Decision-Theoretic Generalization of On-line Learning and an Application to Boosting [Архівовано 12 жовтня 2008 у Wayback Machine.], Journal of Computer and System Sciences, 55(1):119-139 (англ.)
Robert E. Schapire and Yoram Singer (1999); Improved Boosting Algorithms Using Confidence-Rated Predictors [Архівовано 20 серпня 2008 у Wayback Machine.], Machine Learning, 37(3):297-336 (англ.)

Посилання

Robert E. Schapire (2003); The Boosting Approach to Machine Learning: An Overview [Архівовано 20 вересня 2020 у Wayback Machine.], MSRI (Mathematical Sciences Research Institute) Workshop on Nonlinear Estimation and Classification (англ.)
Zhou Zhi-Hua (2014) Boosting 25 years [Архівовано 20 серпня 2016 у Wayback Machine.], CCL 2014 Keynote. (англ.)
Zhou, Zhihua (2008). On the margin explanation of boosting algorithm (PDF). In: Proceedings of the 21st Annual Conference on Learning Theory (COLT'08): 479—490. Архів оригіналу (PDF) за 5 липня 2017. Процитовано 7 травня 2018. (англ.)
Zhou, Zhihua (2013). On the doubt about margin explanation of boosting (PDF). Artificial Intelligence. 203: 1—18. doi:10.1016/j.artint.2013.07.002. Архів оригіналу (PDF) за 5 липня 2017. Процитовано 7 травня 2018. (англ.)