Gradient boosting

Gradient boosting (lit: peningkatan gradien) adalah teknik pemelajaran mesin berbasis boosting dalam ruang fungsional dengan residu semu sebagai targetnya, bukan residu biasa yang biasa digunakan dalam boosting tradisional. Teknik ini mengembalikan sebuah model prediksi dalam bentuk kumpulan (ensemble) model berprediksi lemah, yaitu model memberikan sangat sedikit asumsi tentang data, yang biasanya berupa pohon keputusan (decision tree) sederhana.^[1]^[2] Jika pohon keputusan ini merupakan pemelajar yang lemah, algoritma yang dihasilkan disebut sebagai pohon dengan gradien yang ditingkatkan (gradient-boosted trees) yang biasanya performana melebihi Random forest.^[1] Gradient-boosted trees dibuat secara bertahap seperti pada metode boosting lainnya, tetapi model ini menggeneralisasi metode lain dengan memungkinkan optimasi fungsi kerugian yang terdiferensialkan secara bebas.

Sejarah

Ide gradient boosting bermula dari pengamatan Leo Breiman yang menemukan bahwa boosting dapat diinterpretasikan sebagai sebuah algoritma optimasi pada fungsi biaya yang sesuai.^[3] Secara eksplisit, algoritma ini kemudian dikembangkan oleh Jerome H. Friedman,^[4]^[2] (pada tahun 1999 dan kemudian pada tahun 2001) bersamaan dengan perspektif peningkatan gradien fungsional yang lebih umum dari Llew Mason, Jonathan Baxter, Peter Bartlett dan Marcus Frean.^[5] Dua makalah yang disebutkan di akhir memperkenalkan pandangan terkait algoritma boosting sebagai algoritma penurunan gradien fungsional berulang (functional gradient descent). Artinya, algoritma yang mengoptimalkan fungsi biaya pada ruang fungsi dengan memilih fungsi secara berulang (berhipotesis lemah) yang mengarah ke gradien negatif. Pandangan ini menyebabkan pengembangan algoritma boosting di banyak bidang pemelajaran mesin dan statistika di luar regresi dan klasifikasi.

Pengenalan informal

(Bagian ini mengikuti eksposisi peningkatan gradien oleh Cheng Li.^[6])

Seperti metode boosting lainnya, gradient boosting menggabungkan beberapa "pemelajaran" lemah menjadi satu pemelajar yang kuat secara iteratif. Cara paling mudah untuk menjelaskannya adalah dengan pengaturan regresi kuadrat terkecil, yang tujuannya adalah untuk "mengajarkan" suatu model $F$ untuk memprediksi nilai bentuk ${\hat {y}}=F(x)$ dengan meminimalkan rata-rata kuadrat galat ${\tfrac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2}$ dengan indeks $i$ pada beberapa himpunan ukuran pelatihan $n$ dari nilai sebenarnya dari variabel keluaran $y$ :

${\hat {y}}_{i}=$ nilai prediksinya $F(x_{i})$
$y_{i}=$ nilai yang diamati
$n=$ jumlah sampel yang masuk $y$

Sekarang, pertimbangkan algoritma gradient boosting dengan $M$ tahap. Di setiap tahap $m$ ( $1\leq m\leq M$ ) gradient boosting, misalkan beberapa model yang tidak sempurna $F_{m}$ (dengan $m$ kecil, model ini mungkin mengembalikan ${\hat {y}}_{i}={\bar {y}}$ , saja dengan RHS adalah rerata dari $y$ ). Untuk meningkatkan $F_{m}$ , algoritma ini harus menambahkan beberapa estimator baru, $h_{m}(x)$ . Sedemikian sehingga

F_{m+1}(x_{i})=F_{m}(x_{i})+h_{m}(x_{i})=y_{i}

atau, dapat ditulis ulang sebagai,

h_{m}(x_{i})=y_{i}-F_{m}(x_{i})

.

Oleh karena itu, gradient boosting akan menyesuaikan (fit) $h_{m}$ ke residu $y_{i}-F_{m}(x_{i})$ . Seperti pada varian boosting lainnya, masing-masing $F_{m+1}$ berupaya untuk memperbaiki galat $F_{m}$ sebelumnya. Generalisasi ide ini digunakan pada fungsi kerugian, selain kesalahan kuadrat, dan pada masalah klasifikasi dan pemeringkatan yang mengikuti pengamatan bahwa residu $h_{m}(x_{i})$ untuk model tertentu sebanding dengan gradien negatif dari fungsi kerugian mean squared error (MSE) (sehubungan dengan $F(x_{i})$ ):

L_{\rm {MSE}}={\frac {1}{n}}\sum _{i=1}^{n}\left(y_{i}-F(x_{i})\right)^{2}

-{\frac {\partial L_{\rm {MSE}}}{\partial F(x_{i})}}={\frac {2}{n}}(y_{i}-F(x_{i}))={\frac {2}{n}}h_{m}(x_{i})

.

Oleh karena itu, gradient boosting dapat juga digunakan pada algoritma penurunan gradien dengan "memasukkan" kerugian yang berbeda dan gradiennya.

Referensi

^ ^a ^b Hastie, T.; Tibshirani, R.; Friedman, J. H. (2009). "10. Boosting and Additive Trees". The Elements of Statistical Learning (edisi ke-2nd). New York: Springer. hlm. 337–384. ISBN 978-0-387-84857-0. Diarsipkan dari versi asli tanggal 2009-11-10.
^ ^a ^b Friedman, J. H. (March 1999). "Stochastic Gradient Boosting" (PDF). Diarsipkan dari versi asli (PDF) tanggal 2014-08-01. Diakses tanggal 2013-11-13.
^ Breiman, L. (June 1997). "Arcing The Edge" (PDF). Technical Report 486. Statistics Department, University of California, Berkeley.
^ Friedman, J. H. (February 1999). "Greedy Function Approximation: A Gradient Boosting Machine" (PDF). Diarsipkan dari versi asli (PDF) tanggal 2019-11-01. Diakses tanggal 2018-08-27.
^ Mason, L.; Baxter, J.; Bartlett, P. L.; Frean, Marcus (May 1999). "Boosting Algorithms as Gradient Descent in Function Space" (PDF). Diarsipkan dari versi asli (PDF) tanggal 2018-12-22.
^ Cheng Li. "A Gentle Introduction to Gradient Boosting" (PDF).

Lihat juga

AdaBoost
Hutan acak
peningkatan kucing
GBM ringan
XGBoost
Pembelajaran pohon keputusan

Referensi

Boehmke, Bradley; Greenwell, Brandon (2019). "Gradient Boosting". Hands-On Machine Learning with R. Chapman & Hall. hlm. 221–245. ISBN 978-1-138-49568-5.

[hastie-1] Hastie, T.; Tibshirani, R.; Friedman, J. H. (2009). "10. Boosting and Additive Trees". The Elements of Statistical Learning (edisi ke-2nd). New York: Springer. hlm. 337–384. ISBN 978-0-387-84857-0. Diarsipkan dari versi asli tanggal 2009-11-10.

[Friedman1999b-2] Friedman, J. H. (March 1999). "Stochastic Gradient Boosting" (PDF). Diarsipkan dari versi asli (PDF) tanggal 2014-08-01. Diakses tanggal 2013-11-13.

[Breiman1997-3] Breiman, L. (June 1997). "Arcing The Edge" (PDF). Technical Report 486. Statistics Department, University of California, Berkeley.

[Friedman1999a-4] Friedman, J. H. (February 1999). "Greedy Function Approximation: A Gradient Boosting Machine" (PDF). Diarsipkan dari versi asli (PDF) tanggal 2019-11-01. Diakses tanggal 2018-08-27.

[MasonBaxterBartlettFrean1999b-5] Mason, L.; Baxter, J.; Bartlett, P. L.; Frean, Marcus (May 1999). "Boosting Algorithms as Gradient Descent in Function Space" (PDF). Diarsipkan dari versi asli (PDF) tanggal 2018-12-22.

[6] Cheng Li. "A Gentle Introduction to Gradient Boosting" (PDF).

[1]

[2]

[3]

[4]

[5]

[6]