Бустинг (машинско учење)

У машинском учењу, бустовање је ансамбл мета-алгоритама за смањење пристрасности, и варијансе у надгледаном учењу, и породице алгоритама за машинско учење који претварају слабе ученике у јаке. Бустовање је заснивано на питању које постављеном од стране Кеарнс и Валиант (1988, 1989): „Да ли може група слабих ученика да створи једног јаког ученика?“ Слаб ученик је дефинисан као класификатор који је у малој корелацији са правом класификацијом (може означити примере боље од случајног погодка). Супротно томе, јак ученик је класификатор који је произвољно добро повезан са правом класификацијом.

Роберт Шапиреов потврдан одговор из 1990. на питање постављено од стране Кеарнса и Валианта имао је значајне последице у машинском учењу и статистици, што је довело до развоја бустинга.

Алгоритми за појачавање

Пошто бустинг није алгоритамски ограничено,многи алгоритами за бустовање састоји се од итеративног учења слабих класификатора у односу на дистрибуцију и њиховог додавања јаком класификатору. Када се додају, они се пондеришу на начин који је повезан са прецизношћу слабих ученика. Пошто се дода слаб ученик, тежине података се поново прилагођавају, познато као "поновно пондерисање ". Погрешно класификовани улазни подаци добијају већу тежину, а примери који су правилно класификовани губе тежину. Тако да се будући слаби ученици више фокусирају на примере који су претходни слаби ученици погрешно класификовали, од претходних.

Илустрација која представља интуицију која стоји иза алгоритма за појачавање, који се састоји од паралелних ученика и пондерисаног скупа података.

Постоје многи алгоритами за појачавање. Оригинални алгоритам за појачање, које су предложили Роберт Шапире ( формулација рекурзивне већинске капије) и Иоав Фреунд (појачавање већином), нисе било прилагодљив и нису могли у целсти да искористе предности слабих ученика. Шапире и Фројнд су потом развили АдаБоост, адаптивни алгоритам за појачавање који је освојио Геделову награду .

Само алгоритми који су доказиви алгоритми за појачавање у вероватно приближно тачној формулацији учења се могу назвати алгоритмима за појачавање . Остали алгоритми који су по слични алгоритмима за појачавање се некада називају „алгоритми за повећање“, иако се некад називају и алгоритми за повећање, што је погрешно.

Главна разлика између алгоритама за бустинг је њихов метод пондерисања тачака података и хипотеза за обуку. АдаБоост је веома популаран,такође и историјски најзначајнији пошто је то први алгоритам који сто основа уводног покривања бустинга на универзитетским курсевима машинског учења. Неки од новијих алгоритама су ЛПБоост, ТоталБоост, БровнБоост, кгбоост, МадаБоост, ЛогитБоост и други. Многи алгоритми за појачавање улазе у АниБоост оквир, управо то показује да бустин врши спуштање градијента у функцијском простору користећи конвексну функцију трошкова .

Категоризација објеката у компјутерском виду

Дате слике садрже различите познате објекте у свету, од њих класификатор може да научи аутоматски да класификује објекте у будућим сликама. Једноставни класификатори који су изграђени на основу неке карактеристике слике објекта имају склоност да буду слаби у категоризацији. Коришћење бустинг методе за категоризацију објеката је начин да се уједине слаби класификатори, и на основу тогада се на посебан начин повећа укупна способност категоризације.

Проблем категоризације објеката

Категоризација објеката је класичан задатак компјутерског вида који се заснива на одређивању да ли слика садржи неку карактеристичну категорију објекта или не. Замисао категоризације објекта је уско повезана са распознавањем, идентификацијом и детекцијом. Категоризација објеката се заснова на изгледу, обично садржи екстракцију карактеристика, учење класификатора и примену класификатора на неке нове примере. Постоји више начина да се прикаже категорија објеката, нпр. из анализе облика, модела врећице речи или локалних дескриптора као што је СИФТ, и други. Неки од примера надгледаних класификатора су наивни Бајесови класификатори, машине за подршку векторима, мешавине Гаусових и неуронске мреже. Истраживање показује да се локације на сликама и категорија објеката на сликама могу открити и на ненадгледан начин .

Статус куо за категоризацију објеката

Препознавање категорија објеката на сликама је захтеван проблем у компјутерском виду, поготово када је број категорија доста велики. То је због велике варијабилности унутар класе и потребе за генерализацијом између варијација објеката унутар исте категорије. Објекти унутар једне категорије могу изгледати другачије. Исти објекат може изгледати другачије под другачијим гледиштима, размерама и осветљењем. Позадина и делимична оклузија између осталог отежавај препознавање. Људи могу да препознају хиљаде типова објеката, а већина постојећих система за препознавање објеката може да препознаје само неколико,  нпр. људска лица, аутомобили, једноставни објекти, итд. Истраживања су била веома активна у бављењу више категорија и омогућавању инкременталног додавања нових категорија, и иако општи проблем остаје нерешен. Једно од начина је дељење и унапређење функција.

Бустинг за бинарну категоризацију

АдаБоост може да се користити за препознавање лица као пример бинарне категоризације . Две категорије су лица у односу на позадину. Општи алгоритам је следећи:

1. Формирајте велики скуп простих карактеристика
2. Иницијализирајте тежине за слике тренинга
3. За Т рунде
   1. Нормализовати тежине
   2. За доступне функције из скупа, обучите класификатор користећи једну карактеристику и процените грешку у обучавању
   3. Изаберите класификатор грешком најмање тежине
   4. Ажурирајте тежине слика тренинга: повећајте ако су погрешно класификоване овим класификатором, смањите ако су исправно класификоване
4. Формирајте коначни јаки класификатор као линеарну комбинацију Т класификатора (коефицијент је већи ако је грешка у тренингу мала)

После бустовања, класификатор направљен од 200 карактеристика може дати стопу откривања од 95% под $10^{-5}$ лажно позитивна стопа .

Пример појачања за бинарну категоризацију је систем који детектује пешаке примењујући обрасце кретања и изгледа. Овај рад је први који комбинује и информације о кретању и информације о изгледу као карактеристике за откривање особе која хода. Примњујући сличан приступ Виола-Јонес оквиру за откривање објеката .

Појачавање за вишекласну категоризацију

У поређењу са бинарном категоризацијом, вишекласна категоризација тражи заједничке карактеристике које се могу делити у категоријама у исто време. Испоставило се да су генеричке карактеристике попут ивица. Током учења, детектори за сваку категорију могу се заједно обучавати. У поређењу са одвојеним тренингом, он боље генерализује, потребно је мање података о обуци и захтева мање функција да би се добио исти резултат.

Главни ток алгоритма је сличан бинарном случају. Оно што је различито је да се мера заједничке грешке у тренингу дефинише унапред. Током сваке итерације алгоритам бира класификатор једне карактеристике (подстицаће се карактеристике које се могу делити са више категорија). Ово се може урадити претварањем вишекласне класификације у бинарну (скуп категорија наспрам осталих), или увођењем казнене грешке из категорија које немају обележје класификатора.

У раду „Схаринг висуал феатурес фор мултицласс анд мултивиев објецт детецтион“, А. Торралба ет ал. користио ГентлеБоост за појачавање и показао да када су подаци о обуци ограничени, учење путем функција за дељење ради много боље него без дељења, с обзиром на исте рунде повећања. Такође, за дати ниво перформанси, укупан број потребних карактеристика (а самим тим и трошак времена рада класификатора) за детекторе дељења карактеристика, примећује се да приближно логаритамски скалира са бројем класа, тј. спорије од линеарног раста у случај недељења. Слични резултати су приказани у раду „Инкрементално учење детектора објеката коришћењем абецеде визуелног облика“, али су аутори користили АдаБоост за појачавање.

Конвексни против неконвексних алгоритама за појачавање

Алгоритми за појачавање могу бити засновани на конвексним или неконвексним оптимизацијским алгоритмима. Конвексни алгоритми, као што су АдаБоост и ЛогитБоост, могу бити „поражени“ насумичним шумом тако да не могу да науче основне комбинације слабих хипотеза које се могу научити. На ово ограничење указао је Лонг & Серведио 2008. године. Међутим, до 2009. године, више аутора је показало да алгоритми за појачавање засновани на неконвексној оптимизацији, као што је БровнБоост, могу да уче из скупова података са буком и могу посебно да науче основни класификатор скупа података Лонг–Серведио.

Види још

• AdaBoost
• Random forest
• Alternating decision tree
• Bootstrap aggregating (bagging)
• Cascading
• BrownBoost
• CoBoosting
• LPBoost
• Logistic regression
• Maximum entropy methods
• Neural networks
• Support vector machines
• Gradient boosting
• Margin classifiers
• Cross-validation
• Machine learning
• List of datasets for machine learning research

Имплементације

• Сцикит-леарн, библиотека отвореног кода за машинско учење за Питхон
• Оранге, бесплатни софтверски пакет за рударење података, модул Оранге.енсембле
• Века је скуп алата за машинско учење који нуди различите имплементације алгоритама за појачавање као што су АдаБоост и ЛогитБоост
• Р пакет ГБМ (Генерализед Боостед Регрессион Моделс) имплементира проширења за Фројндов и Шапиреов АдаБоост алгоритам и Фридманову машину за подизање градијента.
• јбоост ; АдаБоост, ЛогитБоост, РобустБоост, Боостектер и наизменична стабла одлучивања
• Р пакет адабаг : Примењује Мултицласс АдаБоост. М1, АдаБоост-САММЕ и Баггинг
• Р пакет кгбоост : Имплементација повећања градијента за линеарне и моделе засноване на стаблу.

 

 

Додатна литература

• Иоав Фреунд и Роберт Е. Сцхапире (1997); Теоријска генерализација он-лине учења и примена за унапређење Архивирано на сајту Wayback Machine (12. октобар 2008), Јоурнал оф Цомпутер анд Систем Сциенцес, 55(1):119-139
• Роберт Е. Шапире и Јорам Сингер (1999); Побољшани алгоритми за појачавање помоћу предиктора са оцењивањем поверења, Машинско учење, 37(3):297-336

Спољашње везе

• Роберт Е. Шапире (2003); Појачавајући приступ машинском учењу: Преглед, МСРИ (Институт за математичке науке) Радионица о нелинеарној процени и класификацији
• Зхоу Зхи-Хуа (2014) Боостинг 25 иеарс Архивирано на сајту Wayback Machine (20. август 2016), ЦЦЛ 2014 Кеиноте.
• 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. 
• Zhou, Zhihua (2013). „On the doubt about margin explanation of boosting.” (PDF). Artificial Intelligence. 203: 1—18. arXiv:1009.3613 . doi:10.1016/j.artint.2013.07.002.