Википедија

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

После бустовања, класификатор направљен од 200 карактеристика може дати стопу откривања од 95% под   лажно позитивна стопа . [13]

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

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

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

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

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

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

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

Види још уреди

Имплементације уреди

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

Напомене уреди

 

Референце уреди

 

  1. ^ Leo Breiman (1996). „BIAS, VARIANCE, AND ARCING CLASSIFIERS” (PDF). TECHNICAL REPORT. Архивирано из оригинала (PDF) 2015-01-19. г. Приступљено 19. 1. 2015. „Arcing [Boosting] is more successful than bagging in variance reduction” 
  2. ^ Zhou Zhi-Hua (2012). Ensemble Methods: Foundations and Algorithms. Chapman and Hall/CRC. стр. 23. ISBN 978-1439830031. „The term boosting refers to a family of algorithms that are able to convert weak learners to strong learners” 
  3. ^ Michael Kearns(1988); Thoughts on Hypothesis Boosting, Unpublished manuscript (Machine Learning class project, December 1988)
  4. ^ Michael Kearns; Leslie Valiant (1989). Crytographic [sic] limitations on learning Boolean formulae and finite automata. Symposium on Theory of Computing. 21. ACM. стр. 433—444. ISBN 978-0897913072. doi:10.1145/73007.73049. 
  5. ^ Schapire, Robert E. (1990). „The Strength of Weak Learnability” (PDF). Machine Learning. 5 (2): 197—227. CiteSeerX 10.1.1.20.723  . doi:10.1007/bf00116037. Архивирано из оригинала (PDF) 2012-10-10. г. Приступљено 2012-08-23. 
  6. ^ Leo Breiman (1998). „Arcing classifier (with discussion and a rejoinder by the author)”. Ann. Stat. 26 (3): 801—849. doi:10.1214/aos/1024691079  . „Schapire (1990) proved that boosting is possible. (Page 823)” 
  7. ^ Schapire, Robert E. (1990). „The Strength of Weak Learnability” (PDF). Machine Learning. 5 (2): 197—227. CiteSeerX 10.1.1.20.723  . doi:10.1007/bf00116037. Архивирано из оригинала (PDF) 2012-10-10. г. Приступљено 2012-08-23. 
  8. ^ а б в 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
  9. ^ Emer, Eric. „Boosting (AdaBoost algorithm)” (PDF). MIT. Архивирано из оригинала (PDF) 15. 02. 2020. г. Приступљено 2018-10-10. 
  10. ^ Sivic, Russell, Efros, Freeman & Zisserman, "Discovering objects and their location in images", ICCV 2005
  11. ^ A. Opelt, A. Pinz, et al., "Generic Object Recognition with Boosting", IEEE Transactions on PAMI 2006
  12. ^ M. Marszalek, "Semantic Hierarchies for Visual Object Recognition", 2007
  13. ^ P. Viola, M. Jones, "Robust Real-time Object Detection", 2001
  14. ^ A. Torralba, K. P. Murphy, et al., "Sharing visual features for multiclass and multiview object detection", IEEE Transactions on PAMI 2006
  15. ^ A. Opelt, et al., "Incremental learning of object detectors using a visual shape alphabet", CVPR 2006
  16. ^ P. Long and R. Servedio. 25th International Conference on Machine Learning (ICML), 2008, pp. 608--615.
  17. ^ Long, Philip M.; Servedio, Rocco A. (март 2010). „Random classification noise defeats all convex potential boosters” (PDF). Machine Learning. 78 (3): 287—304. doi:10.1007/s10994-009-5165-z  . Приступљено 2015-11-17. 

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

Спољашње везе уреди


Грешка код цитирања: Постоје ознаке <ref> за групу с именом „note“, али нема одговарајуће ознаке <references group="note"/>

Преузето из „https://sr.wikipedia.org/w/index.php?title=Бустинг_(машинско_учење)&oldid=26833593”