„Boosterele de gradient”

Vechea creștere a gradientului

Un instructaj de matematică pentru creșterea gradului

În 2001, Jerome H. Friedman a scris o lucrare fundamentală - Greedy function approximation: A gradient boosting machine. Nu știa el că va evolua într-o clasă de metode care amenință „teorema fără prânz gratuit” a lui Wolpert în lumea tabelară. Gradient Boosting și verii săi (XGBoost și LightGBM) au cucerit lumea oferind performanțe excelente în clasificare, precum și probleme de regresie în domeniul datelor tabulare.

Să începem prin a înțelege metodologia clasică de creștere a gradului propusă de Friedman. Chiar dacă acest lucru este greu de matematică, nu este atât de dificil. Și oriunde a fost posibil, am încercat să ofer intuiție pentru ceea ce se întâmplă.

Configurarea problemei

Să existe un set de date D cu n mostre. Fiecare eșantion are m set de caracteristici într-un vector x și o țintă cu valoare reală, y. Formal, este scris ca

Acum, algoritmii de creștere a gradului sunt o metodă de ansamblu care ia o formă aditivă. Intuiția este că o funcție complexă, pe care încercăm să o estimăm, poate fi formată din funcții mai mici și mai simple, adunate.

Să presupunem că funcția pe care încercăm să o aproximăm este

Putem descompune această funcție ca:

Aceasta este ipoteza pe care o luăm atunci când alegem un model de ansamblu aditiv, iar ansamblul Tree despre care vorbim de obicei când vorbim despre Gradient Boosting poate fi scris după cum urmează:

unde M este numărul de elevi de bază și F este spațiul arborilor de regresie.

Funcția de pierdere

unde l este funcția de pierdere convexă diferențiabilă f(x).

Deoarece ne uităm la o formă funcțională aditivă pentru f(x), putem înlocui yᵢ cu

Deci, funcția de pierdere va deveni:

Algoritm

  1. Inițializați modelul cu o valoare constantă reducând la minimum funcția de pierdere

  • b₀ este predicția modelului care minimizează funcția de pierdere la a 0-a iterație
  • Pentru pierderea erorii pătrate, se pare că este media pentru toate mostrele de antrenament
  • Pentru pierderea cu cea mai mică abatere absolută, se pare că este mediana pentru toate eșantioanele de antrenament

2. pentru m=1 la M:

2.1 Calculați

  • rᵢₘ nu este altceva decât derivata funcției de pierdere (între adevărat și rezultatul din ultima iterație) w.r.t. F(x) de la ultima iterație
  • Pentru pierderea de eroare pătrată, aceasta rezultă a fi reziduul(Observat — Predict)
  • Se mai numește pseudo rezidual deoarece acționează ca rezidual și este rezidual pentru funcția de pierdere a erorii pătrate.
  • Calculăm rᵢₘpentru toate probele de n

2.2 Potriviți un arbore de regresie la valorile rᵢₘ folosind Impuritatea Gini sau Entropia (modul obișnuit)

  • Fiecare frunză a copacului se notează cu Rⱼₘ pentru j = 1 … Jₘ, unde Jₘ este numărul de frunze din arborele create în iterația m

2.3 Pentru j = 1 … Jₘ, se calculează

  • bⱼₘ este funcția de bază sau coeficienții cei mai mici pătrați. Aceasta rezultă în mod convenabil a fi media pentru toate eșantioanele din orice frunză pentru pierderea erorii pătrate și mediana pentru pierderea deviației absolute minime
  • ρₘ este factorul de scalare sau greutățile frunzelor.
  • Însumarea interioară peste b poate fi ignorată din cauza naturii disjunctive a arborilor de regresie. O mostră anume va fi doar într-una dintre aceste frunze. Deci ecuația se simplifică la:

  • Deci, pentru fiecare dintre frunze, Rⱼₘ, calculăm valoarea optimă ρ, atunci când adăugată la predicția ultimei iterații minimizează pierderea pentru probele care rezidă în frunză.
  • Pentru funcțiile de pierdere cunoscute, cum ar fi pierderea erorii pătrate și pierderea deviației absolute minime, factorul de scalare este 1. Și, din această cauză, implementarea standard GBM ignoră factorul de scalare.
  • Pentru unele pierderi, cum ar fi pierderea Huber, ρ este estimat folosind o căutare pe linie pentru a găsi pierderea minimă.

2.4 Actualizare

  • Acum adăugăm cel mai recent arbore optimizat la rezultatul iterației anterioare.
  • η este contracția sau rata de învățare
  • Însumarea din ecuație este utilă numai în cazul în care un anumit eșantion ajunge în mai multe noduri. În caz contrar, este doar scorul optimizat al arborelui de regresie b.

Regularizare

În implementarea standard (Sci-kit Learn), termenul de regularizare în funcția obiectiv nu este implementat. Singura regularizare care este implementată acolo sunt următoarele:

  • Regularizare prin contracție — în formularea aditivă, fiecare nou cursant slab este „strâns” de un factor, η. Această scădere se mai numește și rata de învățare în unele implementări, deoarece seamănă cu rata de învățare din rețelele neuronale.
  • Eșantionarea pe rânduri— Fiecare dintre arborii candidați din ansamblu utilizează un subset de eșantioane. Aceasta are un efect de regularizare.
  • Eșantionarea pe coloană— Fiecare dintre arborii candidați din ansamblu utilizează un subset de caracteristici. Acest lucru are, de asemenea, un efect de regularizare și este de obicei mai eficient. Acest lucru ajută și la paralelizare.

Creșterea gradului și coborârea gradientului

Asemănarea

Știm că Gradient Boosting este un model aditiv și poate fi prezentat după cum urmează:

unde F este modelul de ansamblu, f este cel care învață slab, η este rata de învățare și X este vector de intrare.

Înlocuind F cu y^, obținem ecuația familiară,

Acum, deoarece fₘ(X)se obține la fiecare iterație prin minimizarea funcției de pierdere, care este o funcție a gradienților de ordinul întâi și al doilea (derivate), putem intuitiv să ne gândim la asta ca la un vector direcțional îndreptat către cea mai abruptă coborâre. Să numim acest vector direcțional rₘ₋₁. Indicele este m-1 deoarece vectorul a fost antrenat pe etapa m-1 a iterației. Sau, intuitiv rezidualul

.Deci ecuația devine acum:

Întorcând semnele, obținem:

Acum să ne uităm la ecuația standard de coborâre a gradientului:

Putem vedea clar asemănarea. Și acest rezultat este ceea ce ne permite să folosim orice funcție de pierdere diferențiabilă.

Diferența

Când antrenăm o rețea neuronală folosind Gradient Descent, aceasta încearcă să găsească parametrii optimi (greutăți și părtiniri), w, care minimizează funcția de pierdere. Și acest lucru se face folosind gradienții pierderii în raport cu parametrii.

Dar în Gradient Boosting, gradientul ajustează doar modul în care este creat ansamblul și nu parametrii cursantului de bază subiacent.

În timp ce în rețeaua neuronală, gradientul ne oferă direct vectorul de direcție al funcției de pierdere, în Boosting, obținem doar aproximarea acelui vector de direcție de la elevul slab. În consecință, pierderea unui GBM este probabil să se reducă monoton. Este cu totul posibil ca pierderea să sară puțin pe măsură ce iterațiile continuă.

Implementarea

„GradientBoostingClassifier” și „GradientBoostingRegressor” din Sci-kit Learn sunt una dintre cele mai vechi implementări din ecosistemul python. Este o implementare simplă, fidelă lucrării originale. Urmăresc destul de mult discuția pe care am avut-o până acum. Și a implementat pentru o varietate de funcții de pierdere pentru care Aproximarea funcției Greedy: A gradient boosting machine[1] de Friedman avea algoritmi derivați.

Pierderi de regresie

  • „ls” → Cele mai mici pătrate
  • „flacă” → Abatere absolută minimă
  • „huber” → Pierdere Huber
  • ‘quantile’ → Quantile Pierdere

Pierderi de clasificare

  • „devianță” → Pierdere de regresie logistică
  • „exponential” → Pierdere exponentiala

Referințe

  1. Friedman, Jerome H. Greedy function aproximation: A gradient boosting machine. Ann. Statisticist. 29 (2001), nr. 5, 1189–1232.

Publicat inițial la http://deep-and-shallow.com pe 2 februarie 2020.