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. 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]]*. *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. Secara eksplisit, algoritma ini kemudian dikembangkan oleh Jerome H. Friedman, (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. 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.)

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 \le m \le 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 *[[Galat|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

## Lihat juga

* AdaBoost
* Hutan acak
* peningkatan kucing
* GBM ringan
* XGBoost
* Pembelajaran pohon keputusan

## Referensi

* 

* Bagaimana menjelaskan peningkatan gradien
* Pohon Regresi yang Didorong Gradien
* GBM ringan