Tehostaa

Boosting on koostumuksen koneoppimisen meta-algoritmi ,  jota käytetään  pääasiassa vähentämään harhaa (estimaatiovirhe) sekä varianssia [1] ohjatussa oppimisessa . Määritelty myös koneoppimisalgoritmien perheeksi, joka muuntaa heikot oppimisalgoritmit vahvoiksi [2] .

Boostointi perustuu Kearnsin ja Valiantin (1988, 1989) [3] [4] esittämään kysymykseen : "Voiko joukko heikkoja oppimisalgoritmeja tuottaa vahvan oppimisalgoritmin?". Heikko oppimisalgoritmi määritellään luokittelijaksi , joka korreloi heikosti oikean luokituksen kanssa (voi merkitä esimerkit paremmin kuin satunnainen arvaus). Toisin kuin heikko algoritmi, vahva oppimisalgoritmi on luokitin, joka korreloi hyvin oikean luokituksen kanssa.

Robert Shapiren myönteinen vastaus vuoden 1990 artikkelissa [5] Kearnsin ja Valiantin kysymykseen oli erittäin tärkeä koneoppimisteorian ja tilastojen kannalta , ja se johti useiden tehostamisalgoritmien luomiseen [6] .

Tehostava hypoteesi viittasi prosessiin virittää heikko oppimisalgoritmi vahvan oppimisen saavuttamiseksi. Epävirallisesti kysytään, tarkoittaako tehokkaan oppimisalgoritmin olemassaolo, jonka tulos on hypoteesi, jonka suorituskyky on vain hieman parempi kuin satunnainen arvaus (eli heikko oppiminen), tehokkaan algoritmin olemassaoloa, joka tuottaa mielivaltaisen tarkkuuden (eli vahvan) hypoteesin. oppiminen) [3] . Algoritmit, jotka päätyvät tällaiseen hypoteesiin, tunnetaan nopeasti yksinkertaisesti "tehostavina". Freundin ja Shapiren "kaari"-algoritmi (Adaptive Resampling and Combining) [7] yleisenä tekniikkana on enemmän tai vähemmän synonyymi tehostukselle [8]

Tehostusalgoritmit

Vaikka tehostaminen ei ole algoritmisesti rajoitettua, useimmat tehostusalgoritmit koostuvat heikkojen luokittimien iteratiivisesta harjoittelusta niiden kokoamiseksi vahvaksi luokittelijaksi. Kun niitä lisätään, niille annetaan yleensä jollain tavalla painoja, jotka yleensä liittyvät harjoitustarkkuuteen. Kun heikko luokitin on lisätty, painot lasketaan uudelleen, mikä tunnetaan nimellä "painon uudelleenlaskenta" . Väärin luokitellut syötteet saavat enemmän painoa, kun taas oikein luokitellut tapaukset laihtuvat [nb 1] . Näin ollen myöhempi heikko oppiminen keskittyy enemmän esimerkkeihin, joissa aikaisemmat heikot oppimiset on luokiteltu väärin.

Tehostusalgoritmeja on monia. Robert Shapiren ( rekursiivinen enemmistöportin  muotoilu ) [5] ja Yoav Freundin (dominanssin vahvistaminen) [9] ehdottamat alkuperäiset algoritmit eivät olleet mukautuvia eivätkä kyenneet antamaan täyttä hyötyä heikosta oppimisesta. Shapire ja Freund kehittivät sitten AdaBoostin (Adaptive Boosting), adaptiivisen tehostusalgoritmin, joka voitti arvostetun Gödel-palkinnon .

Vain sellaisia ​​algoritmeja, joiden voidaan todistaa olevan tehostamisalgoritmeja suunnilleen oikean oppimisen muotoilussa, voidaan kutsua tarkasti tehostamisalgoritmeiksi . Muita algoritmeja, jotka ovat hengeltään samanlaisia ​​kuin tehostusalgoritmeja, kutsutaan joskus vipuvaikutusalgoritmeiksi , vaikka niitä kutsutaan joskus väärin myös tehostamisalgoritmeiksi [ 9] . 

Suurin ero monien tehostusalgoritmien välillä on opetusdatapisteiden painojen [ ja hypoteeseissa . AdaBoost-algoritmi on erittäin suosittu ja historiallisesti merkittävin, koska se oli ensimmäinen algoritmi, joka pystyi sopeutumaan heikkoon oppimiseen. Algoritmia käytetään usein perusjohdantona algoritmien tehostamiseen yliopistojen koneoppimiskursseilla [10] . On olemassa monia äskettäin kehitettyjä algoritmeja, kuten LPBoost [ , TotalBoost, BrownBoost , xgboost , MadaBoost, LogitBoost ym.[ ominaisuusavaruuteen [ käyttäen konveksia häviöfunktiota [ .

Ominaisuuksien luokittelu tietokonenäössä

Kun otetaan huomioon kuvat, jotka sisältävät erilaisia ​​maailmassa tunnettuja esineitä, niiden perusteella voidaan kouluttaa luokitin, joka luokittelee objektit automaattisesti tulevissa tuntemattomissa kuvissa. Yksinkertaiset luokittimet, jotka on rakennettu joidenkin objektikuvan ominaisuuksien perusteella , osoittautuvat yleensä luokittelussa tehottomiksi. Tehostusmenetelmien käyttäminen objektien luokittelussa on tapa yhdistää heikkoja luokittajia tietyllä tavalla yleisen luokittelukyvyn parantamiseksi.

Objektien luokittelutehtävä

Ominaisuuden luokittelu on tyypillinen tietokonenäön tehtävä , jossa määritetään, sisältääkö kuva tietyn luokan esineitä vai ei. Idea liittyy läheisesti tunnistamiseen, tunnistamiseen ja havaitsemiseen. Objektin tunnistuksen mukainen luokittelu sisältää tyypillisesti piirteiden poimimisen , luokittelijan koulutuksen ja luokittelijan soveltamisen uusiin tietoihin. On olemassa monia tapoja esittää objektiluokkaa, kuten jäsentämällä muotoa , käyttämällä sanapussimallia , käyttämällä paikallisia kuvaajia, kuten SIFT , ja niin edelleen. Esimerkkejä valvotuista luokittelijoista ovat naiivit bayes - luokittelijat ,tukivektorikoneet , Gaussin sekoitus hermoverkot . Tutkimukset ovat kuitenkin osoittaneet, että objektiluokat ja niiden sijainti kuvissa voidaan havaita myös ohjaamattoman oppimisen avulla [11] .

Objektien luokittelun tilanne

Objektiluokkien tunnistaminen kuvista on tietokonenäön kannalta vaikea tehtävä , varsinkin jos luokkien määrä on suuri. Tämä on seurausta luokkien suuresta sisäisestä vaihtelevuudesta ja tarpeesta yleistää erilaisia ​​käsitteitä luokan sisällä. Saman luokan esineet voivat näyttää täysin erilaisilta. Jopa sama kohde voi näyttää erilaiselta eri näkökulmista, mittakaavasta tai valaistuksesta . Taustakohina ja osittaiset päällekkäisyydet lisäävät myös tunnistuksen monimutkaisuutta [12] . Ihmiset pystyvät tunnistamaan tuhansia esinetyyppejä, kun taas useimmat olemassa olevat esineiden tunnistusjärjestelmät on koulutettu tunnistamaan vain muutama, kuten ihmisten kasvot , autot , yksinkertaiset esineet jne. [13] . Kategorioiden määrän lisäämistä ja uusien luokkien lisäämismahdollisuutta koskevaa tutkimusta tehdään aktiivisesti, ja vaikka yleistä ongelmaa ei ole vielä ratkaistu, ilmaisimia on kehitetty useille kategorioille (jopa satoja ja tuhansia [14] ) . Tämä saavutetaan erityisesti jakamalla ominaisuuksia ja tehostamalla.

Tehostus binääriluokitukseen

AdaBoost-pakettia voidaan käyttää kasvojentunnistukseen esimerkkinä binääriluokittelusta . Kaksi luokkaa ovat kasvot ja tausta. Yleinen algoritmi näyttää tältä:

1. Muodostamme suuren joukon ominaisuuksia
2. Kuvien harjoitussarjan painojen alustaminen
3. T-ajojen tekeminen
   1. Normalisoi painot
   2. Sarjan käytettävissä oleville ominaisuuksille harjoittelemme luokittelijaa jollakin ominaisuuksista ja laskemme harjoitusvirheen
   3. Luokittelijan valinta pienimmällä virheellä
   4. Päivitä harjoituskuvan painot: lisää, jos luokitellut väärin, ja vähennä, jos ne ovat oikein
4. Lopullisen vahvan luokittelijan muodostamme T-luokittajien lineaarisena yhdistelmänä (kerroin on suurempi, jos harjoitusvirhe on pienempi)

Tehostuksen jälkeen 200 ominaisuudesta rakennettu luokitin voi saavuttaa 95 % onnistuneista tunnistusvirheistä [ 15] .

Toinen binääriluokituksen tehostuksen sovellus on järjestelmä, joka tunnistaa jalankulkijat liikekuvioiden ja ulkonäön perusteella [16] . Tämä teos yhdistää liikeinformaation ja ulkonäön ominaisuuksina liikkuvan ihmisen havaitsemiseen ensimmäistä kertaa. Käytämme samanlaista lähestymistapaa kuin Viola-Jonesin objektintunnistusmalli .

Moniluokkaluokituksen tehostaminen

Verrattuna binääriluokitukseen moniluokkainen luokittelu yhteisiä piirteitä, jotka voidaan jakaa luokkien välillä samanaikaisesti. Ne osoittautuvat yleisemmiksi, kuten " raja " -ominaisuus . Harjoittelun aikana kunkin luokan luokittelijat voidaan kouluttaa yhdessä. Erilliseen harjoitteluun verrattuna tällaisella harjoittelulla on parempi yleistys , se vaatii vähemmän harjoitustietoja ja vähemmän ominaisuuksia tarvitaan halutun tuloksen saavuttamiseksi.

Algoritmin perustoiminto on samanlainen kuin binääritapauksessa. Erona on, että yhteisharjoitteluvirheen mitta voidaan määrittää etukäteen. Jokaisen iteroinnin aikana algoritmi valitsee yhden ominaisuuden luokittelijan (yhteisesti luokiteltavia ominaisuuksia suositellaan). Tämä voidaan tehdä muuntamalla moniluokkainen luokitus binääriseksi (joukko kategorioita/muita luokkia) [17] tai rankaisemalla luokkia, joissa ei ole luokittelijan tunnistamia ominaisuuksia [18] .

Visuaalisten ominaisuuksien jakaminen moniluokkaisten ja moninäkymäobjektien havaitsemiseen A. Torralba ym. käytti GentleBoostia tehostamiseen ja osoitti, että jos harjoitustietoja on rajoitetusti, oppiminen jaettujen käytettyjen ominaisuuksien avulla tekee työn paljon paremmin kuin ilman jakamista. Lisäksi tietyllä suorituskykytasolla ominaisuuksien jakamisen havaitsemiseen tarvittavien ominaisuuksien kokonaismäärä (ja siten luokittimen ajoaika) kasvaa likimäärin logaritmisesti luokkien määrän kanssa, eli hitaammin kuin lineaarinen , joka esiintyy ei jakamista. Samanlaisia ​​tuloksia on esitetty artikkelissa "Kohteiden havaitsemisen asteittainen oppiminen visuaalisten kuvien aakkosilla", mutta kirjoittajat käyttivät AdaBoostia tehostamiseen .

Kupera ja ei-kupera tehostusalgoritmi

Tehostusalgoritmit voivat perustua kuperaan tai ei-kuperaan optimointialgoritmeihin. Kuperat algoritmit, kuten AdaBoost ja LogitBoost, voivat kaatua satunnaisen kohinan vuoksi, koska ne eivät voi opettaa heikkojen hypoteesien perus- ja opittavia yhdistelmiä [19] [20] . Long ja Servedo huomauttivat tämän rajoituksen vuonna 2008. Kuitenkin vuonna 2009 useat kirjoittajat osoittivat, että ei-kuperaan optimointiin perustuvia tehostusalgoritmeja, kuten BrownBoost , voidaan opettaa kohinaisista tiedoista ja taustalla olevaa aineiston Long-Servedio-luokittajaa voidaan kouluttaa. .

Katso myös

• adaboost
• satunnainen metsä
• Limitetty päätöspuu
• Pussittaminen
• CSS-luokittelut
• brownboost
• CoBoosting
• LPBoost_
• Logistinen regressio
• Maksimientropiamenetelmät
• Keinotekoiset neuroverkot
• Tuki Vector-koneita
• Gradientin tehostaminen
• Jakonauhalla varustettu luokitin
• Ristivahvistus
• Koneoppiminen

Toteutus

• Scikit-learn , avoimen lähdekoodin koneoppimiskirjasto Python-kielelle
• Orange , ilmainen data-analyysipaketti, Orange.ensemble- moduuli Arkistoitu 4. maaliskuuta 2016 Wayback Machinessa
• Weka  on koneoppimisen työkalupakki, joka sisältää useita tehostamisalgoritmeja, kuten AdaBoost ja LogitBoost.
• GBM- paketti, arkistoitu 11. marraskuuta 2018 Wayback Machinessa (Generalized Boosted Regression Models) R -kielellä toteuttaa Freundin ja Shapiren AdaBoost-algoritmin laajennuksen ja Friedmanin gradientin tehostuksen.
• jboost Arkistoitu 18. helmikuuta 2019 Wayback Machinessa ; AdaBoost, LogitBoost, RobustBoost, Boostexter ja Striped Decision Trees
• adabag Arkistoitu 17. syyskuuta 2018 Wayback Machinessa R:ssä: Käyttää AdaBoost.M1-, AdaBoost-SAMME- ja Bagging-moniluokkaalgoritmeja
• xgboost- paketti Arkistoitu 26. lokakuuta 2018 Wayback Machinessa R:ssä: Gradientin tehostuksen toteutus lineaarisissa puupohjaisissa malleissa.
• CatBoost paketti

Muistiinpanot

1. ↑ . Jotkut tehostukseen perustuvat luokitusalgoritmit itse asiassa vähentävät uudelleen väärin luokiteltujen ilmentymien painoja. Esimerkiksi dominanssin vahvistaminen ( englanniksi  boost by enemmistö ) ja BrownBoost

1. ↑ Breiman, 1996 .
2. ↑ Zhi-Hua, 2012 , s. 23.
3. ↑ 12 Kearns , 1988 .
4. ↑ Kearns, Valiant, 1989 , s. 433–444.
5. ↑ 1 2 Schapire, 1990 , s. 197-227.
6. ↑ Breiman, 1998 , s. 801–849.
7. ↑ Freund ja Schapire 1997 , s. 119-139.
8. ↑ Leo Briman ( Breiman 1998 ) kirjoittaa: "Heikon oppimisen käsitteen esittelivät Kearns ja Valiant ( 1988 , Kearns, Valiant, 1989 ), jotka esittivät kysymyksen siitä, ovatko heikko ja vahva oppiminen samanarvoisia. Kysymystä on kutsuttu tehostamisongelmaksi , koska ratkaisuna on nostaa heikon oppimisen heikko tarkkuus vahvan oppimisen korkeaksi. Shapire (1990) osoitti, että tehostaminen on mahdollista. Tehostusalgoritmi on menetelmä, joka ottaa heikon oppimismenetelmän ja muuttaa sen vahvaksi menetelmäksi. Freund ja Shapire (1997) osoittivat, että algoritmi, kuten arc-fs, tehostaa."
9. ↑ 1 2 3 Mason, Baxter, Bartlett, Frean, 2000 , s. 512-518.
10. ↑ Emer, Eric Boosting (AdaBoost-algoritmi) (linkki ei saatavilla) . MIT . Haettu 10. lokakuuta 2018. Arkistoitu alkuperäisestä 15. helmikuuta 2020. (määrätön) 
11. ↑ Sivic, Russell, Efros, Zisserman, Freeman, 2005 , s. 370-377.
12. ↑ Opelt, Pinz, Fussenegger, Auer, 2006 , s. 416-431.
13. ↑ Marszalek, Schmid, 2007 .
14. ↑ Laajamittainen visuaalinen tunnistushaaste (joulukuu 2017). Haettu 6. marraskuuta 2018. Arkistoitu alkuperäisestä 2. marraskuuta 2018. (määrätön)
15. ↑ Viola, Jones, 2001 .
16. ↑ Viola, Jones, Snow, 2003 .
17. ↑ Torralba, Murphy, Freeman, 2007 , s. 854-869.
18. ↑ Opelt, Pinz, Zisserma, 2006 , s. 3-10.
19. ↑ Long, Servedio, 2008 , s. 608-615.
20. ↑ Long, Servedio, 2010 , s. 287-304.

Kirjallisuus

• Leo Breiman . Bias, Variance ja Arcing luokittimet  // Tekninen raportti. - 1996. Arkistoitu 19. tammikuuta 2015. Ote: "Arcing [Boosting] on menestyksellisempää kuin säkitys varianssin vähentämisessä"
• Zhou Zhi Hua. Ensemble-menetelmät: perusteet ja algoritmit. - 2012. - ISBN 978-1439830031 . Ote: "Termi tehostaminen viittaa algoritmiperheeseen, joka pystyy muuttamaan heikot oppijat vahvoiksi oppijoiksi"
• Michael Kearns. Ajatuksia hypoteesien vahvistamisesta . - 1988. - (Julkaisematon käsikirjoitus (Machine Learning -luokkaprojekti)).
• Leo Breiman. Arcing Classifier (keskustelun ja kirjoittajan vastauskirjelmän kanssa)  // Annals of Statistics. - 1998. - T. 26 , nro 3 . - S. 801-849: .
• Michael Kearns, Leslie Valiant . Krytografiset rajoitukset Boolen kaavojen ja äärellisten automaattien oppimiseen  // Symposium on Theory of Computing. - ACM, 1989. - T. 21 . - doi : 10.1145/73007.73049 .
• Michael Kearns, Leslie Valiant . Boolen kaavojen tai äärellisten automaattien oppiminen on yhtä vaikeaa kuin faktorointi. Tekninen raportti TR-14-88. – 1988.
  • Artikkeli julkaistiin myöhemmin julkaisussa Journal of the Association for Computing Machinery, 41(1):67-95, tammikuu 1994.
• Robert E. Schapire. Heikon oppimisen vahvuus  // Koneoppiminen. - Boston, MA: Kluwer Academic Publishers, 1990. - V. 5 , no. 2 . - doi : 10.1007/bf00116037 . Arkistoitu alkuperäisestä 10. lokakuuta 2012.
• Leo Breiman . Valokaariluokitin (keskustelu ja tekijän vastaus)  // Ann. Tilastot .. - 1998. - T. 26 , no. 3 . - doi : 10.1214/aos/1024691079 . Ote: "Schapire (1990) osoitti, että tehostaminen on mahdollista" (Sivu 823)
• Yoav Freund, Robert E. Schapire. On-line-oppimisen päätösteoreettinen yleistys ja sovellus tehostamiseen . - 1997. - T. 55 , no. 1 .
• Andreas Opelt, Axel Pinz, Michael Fussenegger, Peter Auer. Yleinen objektintunnistus tehostamalla // IEEE Trans Pattern Anal Mach Intel. - 2006. - T. 28 . - S. 416-31 . — ISSN 0162-8828 .
• Marszalek M., Schmid C. Visuaalisen objektin tunnistamisen semanttiset hierarkiat . – 2007.
• Viola P., Jones M., Snow D. Jalankulkijoiden havaitseminen liike- ja ulkoasukuvioiden avulla  // ICCV. – 2003.
• Torralba A., Murphy KP, Freeman WT Visuaalisten ominaisuuksien jakaminen moniluokkaisten ja moninäkymäobjektien havaitsemiseen // IEEE Transactions on PAMI. - 2007. - T. 29 , no. 5 . - doi : 10.1109/TPAMI.2007.1055 .
• Andreas Opelt, Axel Pinz, Andrew Zisserma. Kohteen ilmaisimien asteittainen oppiminen visuaalisen muotoaakkoston avulla  // CVPR. - 2006. - S. 3-10 .
• Long P., Servedio R. Satunnainen luokittelukohina voittaa kaikki konveksit potentiaaliset tehostimet // 25th International Conference on Machine Learning (ICML). - 2008. - S. 608-615.
• Philip M. Long, Rocco A. Servedio. Satunnainen luokittelukohina voittaa kaikki kuperat potentiaaliset tehostimet  // Machine Learning. - Springer US, 2010. - maaliskuu ( nide 78 , numero 3 ). — S. 287–304 . - doi : 10.1007/s10994-009-5165-z .
• Pääosissa Llew Mason, Jonathan Baxter, Peter Bartlett, Marcus Frean. Algoritmien tehostaminen gradienttilaskeutumisena // Advances in Neural Information Processing Systems / SA Solla, TK Leen, K.-R. Muller. - MIT Press, 2000. - T. 12 .
• Josef Sivic, Bryan C. Russell, Alexei A. Efros, Andrew Zisserman, William T. Freeman. Objektien ja niiden sijainnin löytäminen kuvissa // ICCV 2005. Kymmenes IEEE International Conference on Computer Vision. - IEEE, 2005. - T. 1.
• Paul Viola, Michael Jeffrey Jones. Vankka reaaliaikainen objektien tunnistus // International Journal of Computer Vision. - 2001. - T. 57 , no. 2 .
• Yoav Freund ja Robert E. Schapire (1997); On-line-oppimisen päätösteoreettinen yleistys ja sovellus tehostamiseen Arkistoitu 12. lokakuuta 2008 Wayback Machinessa , Journal of Computer and System Sciences, 55(1): 119-139
• Robert E. Schapire ja Yoram Singer (1999); Parannetut tehostamisalgoritmit käyttämällä luotettavuusluokitettuja ennustajia Arkistoitu 20.8.2008 Wayback Machinessa , Machine Learning, 37(3): 297-336

Linkit

• Robert E. Schapire (2003); The Boosting Approach to Machine Learning: An Overview Arkistoitu 20. syyskuuta 2020 Wayback Machinen , MSRI:n (Mathematical Sciences Research Institute) eilineaarisen arvioinnin ja luokituksen työpajassa
• Zhou Zhi-Hua (2014) Boosting 25 vuotta Arkistoitu 20. elokuuta 2016 the Wayback Machine , CCL 2014 Keynote.
• Zhihua Zhou. Tehostusalgoritmin marginaalin selityksestä.  // Oppimisteorian 21. vuosikonferenssin (COLT'08) aineisto. - 2008. - S. 479-490 .
• Zhihua Zhou. Epäilystä lisäämisen marginaalin selityksestä.  // Tekoäly. - 2013. - T. 203 . - S. 1-18 . - doi : 10.1016/j.artint.2013.07.002 . - arXiv : 1009.3613 .
• http://www.machinelearning.ru/wiki/index.php?title=%D0%91%D1%83%D1%81%D1%82%D0%B8%D0%BD%D0%B3 Arkistoitu kopio vuodelta 24 helmikuuta 2020 Wayback Machinessa