Perlu bantuan untuk memahami proposal poin split perkiraan xgboost

Latar Belakang:

di xgboost yang iterasi mencoba untuk menyesuaikan pohon atas segala contoh yang meminimalkan tujuan berikut:f t$t$$f_t$$n$

$$\sum_{i=1}^n[g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)]$$

di mana adalah urutan pertama dan kedua, di atas estimasi terbaik kami sebelumnya (dari iterasi ):y t - $g_i, h_i$$\hat{y}$$t-1$

• $g_i=d_{\hat{y}}l(y_i, \hat{y})$
• $h_i=d^2_{\hat{y}}l(y_i, \hat{y})$

dan adalah fungsi kerugian kita.$l$

---

Pertanyaannya (akhirnya):

Ketika membangun dan mempertimbangkan fitur spesifik dalam pemisahan tertentu, mereka menggunakan heuristik berikut untuk menilai hanya beberapa kandidat yang terpecah: Mereka mengurutkan semua contoh dengan mereka , melewati daftar yang diurutkan dan menjumlahkan turunan kedua . Mereka menganggap kandidat yang terbelah hanya ketika jumlah berubah lebih dari . Mengapa demikian??? k x k h i$f_t$$k$$x_k$$h_i$$\epsilon$

Penjelasan yang mereka berikan membuat saya terhindar:

Mereka mengklaim kita dapat menulis ulang persamaan sebelumnya seperti ini:

$$\sum_{i=1}^n\frac{1}{2}h_i[f_t(x_i) - g_i/h_i]^2 + constant$$

dan saya gagal mengikuti aljabar - dapatkah Anda menunjukkan mengapa itu sama?

Dan kemudian mereka mengklaim bahwa "ini persis kerugian kuadrat tertimbang dengan label dan bobot " - pernyataan yang saya setujui, tapi saya tidak mengerti bagaimana kaitannya dengan algoritma calon split yang mereka gunakan ...h $gi/hi$$h_i$

Terima kasih dan maaf jika ini terlalu lama untuk forum ini.

Saya tidak akan merinci tetapi berikut ini akan membantu Anda memahami ide itu.

Mereka menggunakan Quantiles (Wikipedia) untuk menentukan tempat untuk membagi. Jika Anda memiliki 100 kemungkinan titik perpecahan, (diurutkan), Anda dapat mencoba titik perpecahan kuantil dan sudah memiliki perkiraan yang baik. Inilah yang dilakukan parameter . Mereka menganggap titik perpecahan saat split memiliki lebih banyak poin di bawahnya daripada titik split terakhir. Jika , Anda akan berakhir dengan titik perpecahan, lebih besar dari dari poin lainnya. Mereka tidak mempertimbangkan pemisahan baru ketika "jumlah berubah lebih dari$\{x_1, \cdots, x_{100}\}$$10$$\{x_{10}, x_{20}, \cdots, x_{90}\}$$\epsilon$$\sim \epsilon N$$\epsilon = 0.01$$\sim 100$$\{1\%, 2\%, ..., 99\%\}$$\epsilon$ "tetapi ketika jumlah titik di bawah titik saat ini lebih besar dengan daripada yang terakhir.$\epsilon$

Sekarang, jika Anda memiliki banyak titik kontinu yang sudah diklasifikasikan dengan baik, mungkin tidak berguna untuk membagi di antara mereka. Anda ingin membagi bagian-bagian dari kumpulan data Anda yang sangat salah, yang sulit dipelajari. Untuk melakukannya, mereka menggunakan kuantil tertimbang. Di sinilah bobot berperan. kuantil pertama tidak akan menjadi titik pertama yang lebih besar dari dari poin, tetapi titik pertama yang lebih besar dari dari bobot.$10$$10\%$$10\%$

Hanya menambahkan bagian aljabar ke jawaban @Winks:

Persamaan kedua harus memiliki tanda terbalik, seperti pada:

$$\sum_{i=1}^n\frac{1}{2}h_i[f_t(x_i) - (-g_i/h_i)]^2 + constant = \sum_{i=1}^n\frac{1}{2}h_i[f_t^2(x_i) + 2\frac{f_t(x_i)g_i}{h_i} + (g_i/h_i)^2] = \sum_{i=1}^n[g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i) + \frac{gi^2}{2h_i}]$$

Istilah terakhir memang konstan: ingat bahwa dan ditentukan oleh iterasi sebelumnya, jadi mereka konstan ketika mencoba untuk mengatur .$g_i$$h_i$$f_t$

Jadi, sekarang kita dapat mengklaim "ini persis kerugian kuadrat tertimbang dengan label dan bobot "$-gi/hi$$h_i$

Penghargaan untuk Yaron dan Avi dari tim saya karena menjelaskan hal ini kepada saya.

Dan kemudian mereka mengklaim bahwa "ini persis kerugian kuadrat tertimbang dengan label gi / higi / hai dan bobot hihi" - pernyataan yang saya setujui, tapi saya tidak mengerti bagaimana kaitannya dengan algoritma calon split yang mereka gunakan .. .

1. Jika hanya ada satu sampel, dan Anda mengoptimalkan pada iterasi , mudah untuk melihat bahwa nilainya akan menjadi , menjelaskan$w$$t-t_h$$w* = -gi/hi$$(ft - -(gi/hi))^2$

2. Sekarang Anda memiliki seluruh kumpulan data. Dalam kasus di mana fungsi kerugian memiliki turunan kedua yang identik, akan menjadi bukan . Saya menulisnya dengan cara ini karena dalam kasus itu, tidak akan relevan dengan perbedaan antara sampel, karena tidak ada perbedaan. Namun, pada kenyataannya, ketika menjaga tidak berubah, berfluktuasi dengan distribusi .$w*$$-avg(gi)/const$$-sigma(gi)/sigma(hi)$$w*$$hi$$gi$$w*$i w ∗ $hi$

Saya pikir itu menjelaskan mengapa ia bekerja karena tertimbang oleh .$hi$