Hellävarainen johdatus koneoppimisen Gradient Boosting-algoritmiin

Viimeisin päivitetty 15.8.2020

Gradient Boosting on yksi tehokkaimmista tekniikoista ennakoivien mallien rakentamiseen.

Tässä postauksessa tutustut gradient boosting-koneoppimisalgoritmiin ja saat lempeän johdatuksen siihen, mistä se on peräisin ja miten se toimii.

Tämän postauksen luettuasi tiedät:

• Boostingin alkuperä oppimisteoriasta ja AdaBoostista.
• Miten gradient boosting toimii, mukaanlukien häviöfunktio, heikot oppijat (weak learners) ja additiivinen malli.
• Miten parantaa suorituskykyä perusalgoritmiin verrattuna erilaisilla regularisointijärjestelmillä.

Käynnistä projektisi uudella kirjallani XGBoost With Python, joka sisältää vaiheittaiset opetusohjelmat ja Python-lähdekooditiedostot kaikille esimerkeille.

Aloitetaan.

• Tarvitsetko apua XGBoostin kanssa Pythonissa?
• Boostingin alkuperä
• AdaBoost the First Boosting Algorithm
• AdaBoostin yleistäminen Gradient Boostingiksi
• How Gradient Boosting Works
• Häviöfunktio
• Heikko oppija
• Additiivinen malli
• Improvements to Basic Gradient Boosting
• Puiden rajoitukset
• 2. Painotetut päivitykset
• Stochastic Gradient Boosting
• Penalized Gradient Boosting
• Gradient Boosting Resources
• Gradient Boosting Videot
• Gradient Boosting in Textbooks
• Gradient Boosting Papers
• Gradient Boosting Slides
• Gradient Boosting Web Pages
• Yhteenveto
• Tutustu kilpailuja voittaneeseen algoritmiin!
• Kehitä omat XGBoost-mallisi minuuteissa
• Naaputa XGBoostin teho omiin projekteihisi

Tarvitsetko apua XGBoostin kanssa Pythonissa?

Tule mukaan ilmaiselle 7 päivän sähköpostikurssilleni ja tutustu xgboostiin (esimerkkikoodin kera).

Klikkaa ilmoittautuaksesi nyt ja saat myös ilmaisen PDF-kirjaversion kurssista.

Aloita ILMAINEN MINIKURSSI NYT!

Boostingin alkuperä

Boostingin idea syntyi ajatuksesta, että voidaanko heikkoa oppijaa muokata paremmaksi.

Michael Kearns artikuloi tavoitteen ”Hypothesis Boosting Problemiksi” toteamalla tavoitteen käytännön näkökulmasta seuraavasti:

… tehokas algoritmi suhteellisen huonojen hypoteesien muuntamiseksi erittäin hyviksi hypoteeseiksi

– Thoughts on Hypothesis Boosting , 1988

Heikko hypoteesi tai heikko oppija määritellään hypoteesiksi tai heikoksi oppijaksi, jonka suorituskyky on ainakin hieman parempi kuin satunnainen mahdollisuus.

Nämä ajatukset perustuivat Leslie Valiantin työhön jakaumavapaasta tai Probably Approximately Correct (PAC) -oppimisesta, joka on kehys koneoppimisongelmien monimutkaisuuden tutkimiseen.

Hypoteesien lisääminen (hypothesis boosting) oli ajatus havaintojen suodattamisesta siten, että jätetään ne havainnot, joita heikko oppija pystyy käsittelemään, ja keskitytään kehittämään uusia heikkoja oppijoita käsittelemään jäljelle jääviä vaikeita havaintoja.

Ajatuksena on käyttää heikkoa oppimismenetelmää useaan kertaan saadakseen peräkkäin useita hypoteeseja, joista jokainen on kohdennettu uudestaan esimerkeille, jotka aiemmat havaitsivat hankaliksi ja jotka ne luokittelivat väärin. … Huomaa kuitenkin, ettei ole lainkaan selvää, miten tämä voidaan tehdä

– Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World, sivu 152, 2013

AdaBoost the First Boosting Algorithm

Boostingin ensimmäinen toteutus, joka näki suurta menestystä sovelluksissa, oli Adaptive Boosting eli lyhyesti Adaptive Boosting eli AdaBoost.

Boosting viittaa tähän yleiseen ongelmaan tuottaa erittäin tarkka ennustussääntö yhdistämällä karkeat ja kohtalaisen epätarkat nyrkkisäännöt.

– A decision-theoretic generalization of on-line learning and an application to boosting , 1995

Heikot oppijat AdaBoostissa ovat päätöspuita, joissa on yksi jako, joita kutsutaan päätöspuiksi lyhyytensä vuoksi.

AdaBoost toimii painottamalla havaintoja, jolloin vaikeasti luokiteltaville tapauksille annetaan enemmän painoarvoa ja jo hyvin käsitellyille tapauksille vähemmän. Uusia heikkoja oppijoita lisätään peräkkäin, jotka keskittyvät harjoittelussaan vaikeampiin malleihin.

Tämä tarkoittaa, että vaikeasti luokiteltavat näytteet saavat yhä suurempia painoja, kunnes algoritmi löytää mallin, joka luokittelee nämä näytteet oikein

– Applied Predictive Modeling, 2013

Ennusteet tehdään heikkojen oppijoiden ennusteiden enemmistöäänestyksellä, joka on painotettu niiden yksilöllisellä tarkkuudella. AdaBoost-algoritmin menestyksekkäin muoto oli binäärisille luokitusongelmille ja sitä kutsuttiin nimellä AdaBoost.M1.

AdaBoost-algoritmista voi lukea lisää postauksesta:

• Boosting and AdaBoost for Machine Learning.

AdaBoostin yleistäminen Gradient Boostingiksi

AdaBoostin ja siihen liittyvät algoritmit muotoili uudelleen tilastolliseen viitekehykseen ensimmäisenä Breiman kutsumalla niitä ARCing-algoritmeiksi.

Arcing on lyhenne sanoista Adaptive Reweighting and Combining. Jokainen askel arcing-algoritmissa koostuu painotetusta minimoinnista, jota seuraa uudelleenlaskenta ja .

– Prediction Games and Arching Algorithms , 1997

Tätä kehystä kehitti edelleen Friedman ja sitä kutsuttiin Gradient Boosting Machines. Myöhemmin sitä kutsuttiin vain gradienttiboostingiksi tai gradienttipuuboostingiksi.

Tilastollinen viitekehys heitti boostingin numeeriseksi optimointiongelmaksi, jossa tavoitteena on minimoida mallin häviö lisäämällä heikkoja oppijoita gradienttilaskeutumista muistuttavalla menettelyllä.

Tämä luokka algoritmeja kuvattiin vaiheittaisena additiivisena mallina. Tämä johtuu siitä, että yksi uusi heikko oppija lisätään kerrallaan ja mallin olemassa olevat heikot oppijat jäädytetään ja jätetään ennalleen.

Huomaa, että tämä vaiheittain etenevä strategia eroaa vaiheittain etenevistä lähestymistavoista, jotka uudelleensovittavat aiemmin syötettyjä termejä, kun uusia termejä lisätään.

– Ahne funktioapproksimaatio: A Gradient Boosting Machine , 1999

Yleistäminen mahdollisti mielivaltaisten differentioituvien häviöfunktioiden käytön, mikä laajensi tekniikan binääristen luokitusongelmien ulkopuolelle tukemaan regressiota, moniluokkaista luokittelua ja muuta.

How Gradient Boosting Works

Gradient Boosting sisältää kolme osatekijää:

1. Tappiofunktio, jota halutaan optimoida.
2. Heikko oppija, joka tekee ennusteita.
3. Additiivinen malli, johon lisätään heikkoja oppijoita häviöfunktion minimoimiseksi.

Häviöfunktio

Käytettävä häviöfunktio riippuu ratkaistavan ongelman tyypistä.

Häviöfunktion on oltava eroteltavissa, mutta monia vakiohäviöfunktioita tuetaan, ja voit myös määritellä oman.

Regressiossa voidaan esimerkiksi käyttää neliövirhettä ja luokittelussa logaritmista häviötä.

Gradienttiboosting-kehyksen etuna on se, että uutta boosting-algoritmia ei tarvitse johtaa jokaiselle tappiofunktiolle, jota mahdollisesti halutaan käyttää, vaan se on tarpeeksi yleinen kehys, jotta mitä tahansa differentioituvaa tappiofunktiota voidaan käyttää.

Heikko oppija

Päätöspuita käytetään gradienttiboostingissa heikkona oppijana.

Erityisesti käytetään regressiopuita, jotka antavat todellisia arvoja jaoille ja joiden ulostulot voidaan laskea yhteen, jolloin myöhempien mallien ulostulot voidaan lisätä ja ”korjata” jäännökset ennusteissa.

Puut rakennetaan ahneesti valitsemalla parhaat jakopisteet puhtauspisteiden, kuten Ginin, perusteella tai minimoimalla häviö.

Aluksi, kuten AdaBoostin tapauksessa, käytettiin hyvin lyhyitä päätöspuita, joissa oli vain yksi jako, jota kutsuttiin päätöksentekokannaksi. Yleisesti voidaan käyttää suurempia puita, joissa on 4-8 tasoa.

On tavallista rajoittaa heikkoja oppijoita tietyillä tavoilla, kuten maksimimäärällä kerroksia, solmuja, jakoja tai lehtisolmuja.

Tämän tarkoituksena on varmistaa, että oppijat pysyvät heikkoina, mutta ne voidaan silti rakentaa ahneella tavalla.

Additiivinen malli

Puut lisätään yksi kerrallaan, eikä mallin olemassa olevia puita muuteta.

Puita lisättäessä käytetään gradienttilaskeutumismenetelmää häviön minimoimiseksi.

Traditionaalisesti gradienttilaskeutumista käytetään parametrien joukon minimoimiseen, kuten regressioyhtälön kertoimet tai neuroverkon painot. Virheen tai tappion laskemisen jälkeen painot päivitetään kyseisen virheen minimoimiseksi.

Parametrien sijasta meillä on heikon oppijan alamallit tai tarkemmin sanottuna päätöspuut. Häviön laskemisen jälkeen gradienttilaskeutumismenettelyn suorittamiseksi meidän on lisättävä malliin puu, joka pienentää häviötä (eli seuraa gradienttia). Teemme tämän parametrisoimalla puun, sitten muokkaamme puun parametreja ja siirrymme oikeaan suuntaan (pienentämällä jäännöshäviötä.

Yleisesti tätä lähestymistapaa kutsutaan funktionaaliseksi gradienttilaskeutumiseksi tai gradienttilaskeutumiseksi funktioiden avulla.

Yksi tapa tuottaa luokittelijoiden painotettu yhdistelmä, joka optimoi, on gradienttilaskeutuminen funktioavaruudessa

– Boosting Algorithms as Gradient Descent in Function Space , 1999

Uuden puun ulostulot lisätään sitten olemassa olevan puujakson ulostuloihin, jotta mallin lopullista ulostuloa voidaan korjata tai parantaa.

Kiinteä määrä puita lisätään tai harjoittelu lopetetaan, kun häviö saavuttaa hyväksyttävän tason tai ei enää paranna ulkoista validointitietokokonaisuutta.

Improvements to Basic Gradient Boosting

Gradient Boosting on ahne algoritmi, ja se voi sovittaa harjoittelutietokokonaisuuden nopeasti liikaa.

Se voi hyötyä regularisointimenetelmistä, jotka rankaisevat algoritmin eri osia ja yleensä parantavat algoritmin suorituskykyä vähentämällä ylisovittamista.

Tässä osiossa tarkastelemme 4 parannusta perusgradienttiboostingiin:

1. Puiden rajoitukset
2. Shrinkage
3. Satunnainen näytteenotto
4. Penalized Learning

Puiden rajoitukset

Tärkeää on se, että heikoilla oppijoilla on taitoa, mutta ne pysyvät heikkoina.

Puita voidaan rajoittaa monella eri tavalla.

Hyvä yleinen heuristiikka on, että mitä enemmän puiden luomista rajoitetaan, sitä enemmän puita tarvitaan mallissa, ja päinvastoin, jossa vähemmän rajoitettuja yksittäisiä puita, sitä vähemmän puita tarvitaan.

Alhaalla on joitain rajoituksia, joita voidaan asettaa päätöspuiden rakentamiselle:

• Puiden lukumäärä, yleensä useamman puun lisääminen malliin voi olla hyvin hidasta ylisovittamista. Neuvona on jatkaa puiden lisäämistä, kunnes parannusta ei enää havaita.
• Puiden syvyys, syvemmät puut ovat monimutkaisempia puita ja lyhyempiä puita suositaan. Yleensä parempia tuloksia saadaan 4-8 tasolla.
• Solmujen tai lehtien lukumäärä, kuten syvyys, tämä voi rajoittaa puun kokoa, mutta se ei sido symmetriseen rakenteeseen, jos käytetään muita rajoituksia.
• Havaintojen määrä per jako asettaa minimirajoituksen koulutusdatan määrälle koulutussolmussa ennen kuin jakoa voidaan harkita
• Minimiparannus häviöön on rajoitus minkä tahansa puuhun lisätyn jaon parannukselle.

2. Painotetut päivitykset

Kunkin puun ennusteet lasketaan yhteen peräkkäin.

Kunkin puun osuus tähän summaan voidaan painottaa algoritmin oppimisen hidastamiseksi. Tätä painotusta kutsutaan kutistukseksi tai oppimisnopeudeksi.

Jokaista päivitystä yksinkertaisesti skaalataan ”oppimisnopeusparametrin v” arvolla.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Vaikutuksena on, että oppiminen hidastuu, mikä puolestaan edellyttää useampien puiden lisäämistä malliin, jolloin harjoittelu kestää pidempään, mikä tarjoaa konfiguraatiokompromissin puiden lukumäärän ja oppimisnopeuden välille.

Vähentämällä v:n arvoa kasvatetaan M:n parasta arvoa.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

Yleisesti käytetään pieniä arvoja välillä 0,1-0,3 sekä arvoja, jotka ovat alle 0,1.

Samankaltainen kuin oppimisnopeus stokastisessa optimoinnissa, kutistaminen vähentää jokaisen yksittäisen puun vaikutusta ja jättää tilaa tuleville puille parantaa mallia.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

Suuri oivallus säkkikokoonpanoissa ja satunnaismetsissä oli se, että puita voitiin luoda ahnaasti koulutustietokannan osaotoksista.

Tätä samaa etua voidaan käyttää vähentämään sekvenssin puiden välistä korrelaatiota gradient boosting -malleissa.

Tätä boostingin variaatiota kutsutaan stokastiseksi gradient boostingiksi.

kussakin iteraatiossa poimitaan sattumanvaraisesti (ilman korvausta) osaotos harjoitteluaineistosta koko harjoitteluaineistosta. Satunnaisesti valittua osaotosta käytetään sitten koko otoksen sijasta perusoppijan sovittamiseen.

– Stochastic Gradient Boosting , 1999

Muutamia stokastisen boostingin muunnelmia, joita voidaan käyttää:

• Lisäotanta riveistä ennen jokaisen puun luomista.
• Lisäotanta sarakkeista ennen jokaisen puun luomista
• Lisäotanta sarakkeista ennen jokaisen jaon tarkastelemista.

Yleisesti aggressiivinen osanäytteenotto, kuten vain 50 %:n valitseminen aineistosta, on osoittautunut hyödylliseksi.

Käyttäjiltä saadun palautteen mukaan sarakkeiden osanäytteenoton käyttäminen estää liiallisen sovittamisen jopa enemmän kuin perinteinen rivien osanäytteenotto

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Parametrisoituihin puihin voidaan niiden rakenteen lisäksi asettaa lisärajoituksia.

Klassisia päätöspuita, kuten CART:ia, ei käytetä heikkoina oppijoina, vaan sen sijaan käytetään muunneltua muotoa, jota kutsutaan regressiopuuksi ja jonka lehtisolmupisteissä (joita sanotaan myös terminaalisolmupisteiksi) on numeerisia arvoja. Puiden lehdissä olevia arvoja voidaan kutsua joissain kirjallisuudessa painoiksi.

Siten puiden lehtien painoarvoja voidaan regularisoida käyttämällä suosittuja regularisointifunktioita, kuten:

• L1-painojen regularisointi.
• L2-painojen regularisointi.

Lisäsukulaarisointitermi auttaa tasoittamaan lopullista opittua painotusta liiallisen sovittamisen välttämiseksi. Intuitiivisesti regularisoitu tavoite pyrkii valitsemaan mallin, joka käyttää yksinkertaisia ja ennustavia funktioita.

– XGBoost: A Scalable Tree Boosting System, 2016

Gradient Boosting Resources

Gradient Boosting on kiehtova algoritmi, ja olen varma, että haluat mennä syvemmälle.

Tässä osiossa luetellaan erilaisia resursseja, joiden avulla voit oppia lisää gradient Boosting -algoritmista.

Gradient Boosting Videot

• Gradient Boosting Machine Learning, Trevor Hastie, 2014
• Gradient Boosting, Alexander Ihler, 2012
• GBM, John Mount, 2015
• Learning: Boosting, MIT 6.034 Artificial Intelligence, 2010
• xgboost: R-paketti nopeaan ja tarkkaan Gradient Boostingiin, 2016
• XGBoost: A Scalable Tree Boosting System, Tianqi Chen, 2016

Gradient Boosting in Textbooks

• Section 8.2.3 Boosting, page 321, An Introduction to Statistical Learning: with Applications in R.
• Kohta 8.6 Boosting, sivu 203, Applied Predictive Modeling.
• Kohta 14.5 Stochastic Gradient Boosting, sivu 390, Applied Predictive Modeling.
• Kohta 16.4 Boosting, sivu 556, Machine Learning: A Probabilistic Perspective
• Luku 10 Boosting and Additive Trees, sivu 337, The Elements of Statistical Learning: Data Mining, Inference, and Prediction

Gradient Boosting Papers

• Thoughts on Hypothesis Boosting , Michael Kearns, 1988
• A decision-theoretic generalization of on-line learning and an application to boosting , 1995
• Arcing the edge , 1998
• Stochastic Gradient Boosting , 1999
• Boosting Algorithms as Gradient Descent in Function Space , 1999

Gradient Boosting Slides

• Introduction to Boosted Trees , 2014
• A Gentle Introduction to Gradient Boosting, Cheng Li

Gradient Boosting Web Pages

• Boosting (koneoppiminen)
• Gradient Boosting
• Gradient Tree Boosting in scikit-learn

Yhteenveto

Tässä postauksessa tutustuttiin Gradient Boosting-algoritmiin, joka on tarkoitettu ennakoivaan mallintamiseen koneoppimisessa.

Kohtaisesti opit:

• Boostingin historiaa oppimisteoriassa ja AdaBoostissa.
• Miten gradienttiboosting-algoritmi toimii häviöfunktion, heikkojen oppijoiden ja additiivisen mallin kanssa.
• Miten parantaa gradienttiboostingin suorituskykyä regularisoinnilla.

Onko sinulla kysyttävää gradienttiboosting-algoritmista tai tästä postauksesta? Kysy kysymyksesi kommenteissa ja teen parhaani vastatakseni.