Sebagai contoh, ambil fungsi objektif dari model XGBoost pada iterasi :$t$

$$\mathcal{L}^{(t)}=\sum_{i=1}^n\ell(y_i,\hat{y}_i^{(t-1)}+f_t(\mathbf{x}_i))+\Omega(f_t)$$

di mana adalah fungsi kerugian, adalah keluaran pohon ke - dan adalah regularisasi. Salah satu (banyak) langkah utama untuk perhitungan cepat adalah perkiraan:$\ell$$f_t$$t$$\Omega$

$$\mathcal{L}^{(t)}\approx \sum_{i=1}^n\ell(y_i,\hat{y}_i^{(t-1)})+g_tf_t(\mathbf{x}_i)+\frac{1}{2}h_if_t^2(\mathbf{x}_i)+\Omega(f_t),$$

di mana dan adalah turunan pertama dan kedua dari fungsi loss.$g_i$$h_i$

Yang saya minta adalah argumen yang meyakinkan untuk menghilangkan mitos mengapa pendekatan di atas bekerja:

1) Bagaimana XGBoost dengan perkiraan di atas dibandingkan dengan XGBoost dengan fungsi objektif penuh? Apa yang berpotensi menarik, perilaku tingkat tinggi yang hilang dalam aproksimasi?

2) Agak sulit untuk memvisualisasikan (dan tergantung pada fungsi kerugian) tetapi, jika fungsi kerugian memiliki komponen kubik yang besar, maka perkiraan kemungkinan akan gagal. Bagaimana ini tidak menyebabkan masalah untuk XGBoost?

Ini pertanyaan yang sangat menarik. Untuk memahami sepenuhnya apa yang sedang terjadi, saya harus melakukan apa yang XGBoost coba lakukan, dan metode apa lagi yang kami miliki di kotak alat untuk mengatasinya. Jawaban saya melampaui metode tradisional, dan bagaimana / mengapa XGBoost merupakan peningkatan. Jika Anda hanya menginginkan poin-poin, ada ringkasan di bagian akhir.

Meningkatkan Gradien Tradisional

Pertimbangkan Algoritma Peningkat Gradien tradisional (Wikipedia) :

• Hitung model dasar$H_0$
• Untuk$m \leftarrow 1:M$
  • Hitung residu semu$r_{im} = -\frac{\partial \ell(y_i, H_{m-1}(x_i))}{\partial H_{m-1}(x_i)}$
  • Pasang pembelajar dasar ke pseudo-residual$h_m(x)$
  • Hitung pengganda yang meminimalkan biaya, , (menggunakan pencarian baris)$\gamma$$\gamma = \arg \min_\gamma \sum_{i=1}^N \ell(y_i, H_{m-1}(x_i) + \gamma h_m(x_i))$
  • Perbarui model .$H_m(x) = H_{m-1}(x) + \gamma h_m(x)$
• Anda mendapatkan model yang dikuatkan Anda .$H_M(x)$

Perkiraan fungsi penting untuk bagian berikut,

Pasang pembelajar dasar ke pseudo-residual.$h_m(x)$

Bayangkan Anda di mana membuat Algoritma Gradient Boosting Anda secara naif. Anda akan membangun algoritma di atas menggunakan pohon regresi yang ada sebagai pelajar yang lemah. Anggaplah Anda tidak diizinkan untuk men-tweak implementasi yang ada dari pembelajar yang lemah. Dalam Matlab , kriteria split standar adalah Mean Square Error. Hal yang sama berlaku untuk belajar scikit .

Anda mencoba menemukan model terbaik yang meminimalkan biaya . Tetapi untuk melakukannya, Anda menyesuaikan model regresi sederhana dengan residu menggunakan MSE sebagai fungsi objektif. Perhatikan bahwa Anda tidak secara langsung meminimalkan apa yang Anda inginkan, tetapi menggunakan residu dan MSE sebagai proxy untuk melakukannya. Bagian yang buruk adalah bahwa itu tidak selalu menghasilkan solusi optimal. Bagian yang baik adalah itu bekerja.$h_m(x)$$\ell(y_i, H_{m-1}(x_i) + h_m(x_i))$

Keturunan Gradien Tradisional

Ini analog dengan Gradient Descent (Wikipedia) tradisional , di mana Anda mencoba meminimalkan fungsi biaya dengan mengikuti gradien fungsi (negatif dari), pada setiap langkah.$f(x)$$-\nabla f(x)$

$$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

Itu tidak memungkinkan Anda untuk menemukan minimum yang tepat setelah satu langkah, tetapi setiap langkah membuat Anda lebih dekat ke minimum (jika fungsinya cembung). Ini adalah perkiraan, tetapi berfungsi dengan sangat baik dan ini adalah algoritma yang biasanya kami gunakan untuk melakukan regresi logistik, misalnya.

Selingan

Pada titik ini, hal yang perlu dipahami adalah bahwa algoritma peningkatan gradien umum tidak menghitung fungsi biaya untuk setiap pemisahan yang mungkin, ia menggunakan fungsi biaya dari pembelajar yang lemah regresi agar sesuai dengan residu.$\ell$

Apa yang tampaknya disiratkan oleh pertanyaan Anda adalah "true XGBoost" harus menghitung fungsi biaya untuk setiap pemisahan, dan bahwa "perkiraan XGBoost" menggunakan heuristik untuk memperkirakannya. Anda dapat melihatnya seperti itu, tetapi secara historis, kami memiliki algoritma peningkatan gradien umum, yang tidak menggunakan informasi tentang fungsi biaya, kecuali turunan pada titik saat ini. XGBoost adalah ekstensi untuk Gradient Boosting yang mencoba menjadi lebih pintar tentang menumbuhkan pohon regresi yang lemah dengan menggunakan perkiraan yang lebih akurat daripada hanya gradien.

Cara lain untuk memilih model terbaik$h_m(x)$

Jika kita melihat AdaBoost sebagai kasus peningkatan gradien khusus, ia tidak memilih regressor tetapi classifier sebagai pembelajar yang lemah. Jika kita menetapkan , cara AdaBoost memilih model terbaik adalah dengan menemukan$h_m(x) \in \{-1,1\}$

$$h_m = \arg \max_{h_m} \sum_{i=1}^N w_i h_m(x_i)$$

di mana adalah residual ( sumber, dimulai pada slide 20 ). Alasan untuk penggunaan fungsi objektif ini adalah bahwa jika dan bergerak ke arah yang sama / memiliki tanda yang sama, titik tersebut bergerak ke arah yang benar, dan Anda mencoba untuk memaksimalkan jumlah maksimum gerakan di arah yang benar.$w_i$$w_i$$h_m(x_i)$

Tetapi sekali lagi, ini tidak secara langsung mengukur mana yang meminimalkan . Ini mengukur seberapa baik gerakan , sehubungan dengan arah keseluruhan yang harus Anda tempuh, sebagaimana diukur dengan residual , yang juga merupakan perkiraan. Sisa-sisa memberi tahu Anda ke arah mana Anda harus bergerak dengan tanda mereka, dan kira-kira dengan seberapa besar mereka, tetapi mereka tidak memberi tahu Anda dengan tepat di mana Anda harus berhenti.$h_m$$\ell(y_i, H_{m-1}(x_i) + h_m(x_i))$$h_m$$w_i$

Keturunan Gradien yang Lebih Baik

Tiga contoh berikutnya tidak penting untuk penjelasan dan hanya di sini untuk menyajikan beberapa cara untuk melakukan lebih baik daripada keturunan gradien vanilla, untuk mendukung gagasan bahwa apa yang dilakukan XGBoost hanyalah cara lain untuk meningkatkan gradient descent. Dalam pengaturan gradient descent tradisional, ketika mencoba meminimalkan , dimungkinkan untuk melakukan lebih baik daripada hanya mengikuti gradien. Banyak ekstensi telah diusulkan (Wikipedia) . Berikut adalah beberapa di antaranya, untuk menunjukkan bahwa dimungkinkan untuk melakukan yang lebih baik, mengingat lebih banyak waktu komputasi atau lebih banyak properti dari fungsi .$f(x)$$f$

• Pencarian baris / Mundur: Dalam Gradient Descent, setelah gradien dikomputasi, titik berikutnya harus$-\nabla f(x^{(i)})$

  $$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

  Tetapi gradien hanya memberikan arah di mana seseorang harus bergerak, tidak benar-benar dengan "berapa banyak", sehingga prosedur lain dapat digunakan, untuk menemukan yang terbaik sehingga$c > 0$

  $$x_c^{(i+1)} = x^{(i)} - c \nabla f(x^{(i)})$$

  meminimalkan fungsi biaya. Ini dilakukan dengan mengevaluasi untuk beberapa , dan karena fungsi harus cembung, relatif mudah dilakukan melalui Line Search (Wikipedia) atau Backtracking Line Search (Wikipedia) . Di sini, biaya utama adalah evaluasi . Jadi ekstensi ini berfungsi dengan baik jika mudah untuk dihitung. Perhatikan bahwa algoritma umum untuk meningkatkan gradien menggunakan pencarian baris, seperti yang ditunjukkan di awal jawaban saya.$f(x_c^{(i+1)})$$c$$f$$f(x)$$f$

• Metode gradien proksimal cepat: Jika fungsi untuk meminimalkan sangat cembung, dan gradiennya halus ( Lipschitz (Wikipedia) ), maka ada beberapa trik menggunakan properti tersebut yang mempercepat konvergensi.

• Stochastic Gradient Descent dan metode Momentum: Dalam Stochastic Gradient Descent, Anda tidak mengevaluasi gradien pada semua titik, tetapi hanya pada sebagian dari titik-titik tersebut. Anda mengambil langkah, lalu menghitung gradien pada kumpulan lain, dan melanjutkan. Stochastic Gradient Descent dapat digunakan karena perhitungan pada semua titik sangat mahal, atau mungkin semua titik tersebut bahkan tidak masuk dalam memori. Ini memungkinkan Anda mengambil lebih banyak langkah, lebih cepat, tetapi kurang akurat.

  Ketika melakukannya, arah gradien mungkin berubah tergantung pada titik mana yang disampel. Untuk mengatasi efek ini, metode momentum menjaga rata-rata bergerak dari arah untuk setiap dimensi, mengurangi varians di setiap gerakan.

Ekstensi yang paling relevan untuk penurunan gradien dalam diskusi kami tentang XGBoost adalah metode Newton (Wikipedia) . Alih-alih hanya menghitung gradien dan mengikutinya, ia menggunakan turunan urutan kedua untuk mengumpulkan lebih banyak informasi tentang arah yang harus dituju. Jika kita menggunakan gradient descent, kita memiliki itu pada setiap iterasi, kita memperbarui titik sebagai berikut,$x^{(i)}$

$$x^{(i+1)} = x^{(i)} - \nabla f(x^{(i)})$$

Dan karena gradien menunjuk ke arah kenaikan tertinggi dalam , titik negatifnya ke arah penurunan tertinggi, dan kami berharap bahwa . Ini mungkin tidak berlaku, karena kita mungkin melangkah terlalu jauh ke arah gradien (maka ekstensi pencarian baris), tetapi ini merupakan perkiraan yang baik. Dalam metode Newton, kami memperbarui sebagai berikut,$\nabla f(x^{(i)})$$f$$f(x^{(i+1)}) < f(x^{(i)})$$x^{(i)}$

$$x^{(i+1)} = x^{(i)} - \frac{\nabla f(x^{(i)})}{\text{Hess} f(x^{(i)})}$$

Di mana adalah Hessian dari dalam . Pembaruan ini mempertimbangkan informasi urutan kedua akun, jadi arahnya bukan lagi arah penurunan tertinggi, tetapi harus mengarah lebih tepat ke sehingga (atau titik di mana minimal, jika tidak ada nol). Jika adalah polinomial orde kedua, maka metode Newton digabungkan dengan pencarian baris harus dapat menemukan minimum dalam satu langkah.$\text{Hess} f(x)$$f$$x$$x^{(i+1)}$$f(x^{(i+1)}) = 0$$f$$f$

Metode Newton kontras dengan keturunan gradien Stochastic. Dalam Stochastic Gradient Descent, kita menggunakan lebih sedikit titik untuk mengambil lebih sedikit waktu untuk menghitung arah yang harus kita tuju, untuk membuat lebih banyak dari mereka, dengan harapan kita pergi ke sana lebih cepat. Dalam metode Newton, kita mengambil lebih banyak waktu untuk menghitung arah yang ingin kita tuju, dengan harapan kita harus mengambil langkah lebih sedikit untuk sampai ke sana.

Sekarang, alasan mengapa metode Newton bekerja adalah sama dengan mengapa pendekatan XGBoost bekerja, dan itu bergantung pada ekspansi Taylor (Wikipedia) dan teorema Taylor (Wikipedia) . Ekspansi Taylor (atau deret Taylor) dari suatu fungsi pada titik adalah$f(x + a)$

$$f(x) + \frac{\partial f(x)}{\partial x}a + \frac{1}{2}\frac{\partial^2 f(x)}{\partial x^2}a^2 + \cdots = \sum_{n=0} ^\infty \frac{1}{n!} \frac{\partial^n f(x)}{\partial x^n}a^n.$$

Perhatikan persamaan antara ekspresi ini dan perkiraan yang digunakan XGBoost. Teorema Taylor menyatakan bahwa jika Anda menghentikan ekspansi pada urutan , maka kesalahan, atau perbedaan antara dan , adalah paling , di mana adalah fungsi dengan properti yang bagus bahwa ia pergi ke nol sebagai pergi ke nol.$k$$f(x+a)$$\sum_{n=0}^k \frac{1}{n!}\frac{\partial^n f(x)}{\partial x^n}a^n$$h_k(x) a^k$$h_k$$a$

Jika Anda ingin beberapa visualisasi tentang seberapa baik perkiraan fungsi, lihat halaman wikipedia, mereka memiliki beberapa grafik untuk perkiraan fungsi non-polinom seperti , .$e^x$$\log(x)$

Hal yang perlu diperhatikan adalah aproksimasi bekerja dengan sangat baik jika Anda ingin menghitung nilai di lingkungan , yaitu, untuk perubahan yang sangat kecil . Inilah yang ingin kami lakukan dalam Meningkatkan. Tentu saja kami ingin menemukan pohon yang membuat perubahan terbesar. Jika peserta didik yang lemah yang kita bangun sangat baik dan ingin membuat perubahan yang sangat besar, maka kita dapat dengan sewenang-wenang menghalanginya dengan hanya menerapkan atau$f$$x$$a$$0.1$$0.01$efeknya. Ini adalah ukuran langkah atau tingkat pembelajaran gradient descent. Ini dapat diterima, karena jika pembelajar kita yang lemah mendapatkan solusi yang sangat baik, ini berarti bahwa masalahnya mudah, dalam hal ini kita akan berakhir dengan solusi yang baik, atau kita kelebihan, sehingga akan sedikit atau sangat banyak arah buruk ini tidak mengubah masalah mendasar.

Jadi apa yang dilakukan XGBoost, dan mengapa itu bekerja?

XGBoost adalah algoritma Gradient Boosting yang membangun pohon regresi sebagai pembelajar yang lemah. Algoritma Gradient Boosting tradisional sangat mirip dengan gradient descent dengan pencarian garis, di mana arah yang akan diambil diambil dari pelajar yang lemah yang tersedia. Penerapan Gradient Boosting yang naif akan menggunakan fungsi biaya dari pembelajar yang lemah agar sesuai dengan residu. Ini adalah proksi untuk meminimalkan biaya model baru, yang mahal untuk dihitung. Apa yang dilakukan XGBoost adalah membangun fungsi biaya khusus agar sesuai dengan pohon, menggunakan seri Taylor orde dua sebagai perkiraan untuk fungsi biaya sebenarnya, sehingga dapat lebih yakin bahwa pohon yang dipetiknya adalah yang baik. Dalam hal ini, dan sebagai penyederhanaan, XGBoost adalah untuk Gradient Meningkatkan apa Metode Newton untuk Keturunan Gradien.

Mengapa mereka membangunnya seperti itu

Pertanyaan Anda tentang mengapa menggunakan perkiraan ini menyebabkan tradeoff biaya / kinerja. Fungsi biaya ini digunakan untuk membandingkan pemisahan potensial untuk pohon regresi, jadi jika poin kami mengatakan 50 fitur, dengan rata-rata 10 nilai yang berbeda, setiap node memiliki 500 pemisahan potensial, sehingga 500 evaluasi fungsi. Jika Anda menjatuhkan fitur kontinu, jumlah split meledak, dan evaluasi split disebut semakin banyak (XGBoost memiliki trik lain untuk menangani fitur kontinu, tetapi itu di luar ruang lingkup). Karena algoritma akan menghabiskan sebagian besar waktunya mengevaluasi split, cara untuk mempercepat algoritma adalah mempercepat evaluasi pohon.

Jika Anda mengevaluasi pohon dengan fungsi biaya penuh, , itu adalah perhitungan baru untuk setiap pemisahan baru. Untuk melakukan optimasi dalam perhitungan fungsi biaya, Anda perlu memiliki informasi tentang fungsi biaya, yang merupakan inti dari Peningkatan Gradien: Ini harus bekerja untuk setiap fungsi biaya.$\ell$

Perkiraan urutan kedua adalah baik secara komputasi, karena sebagian besar istilah adalah sama dalam iterasi yang diberikan. Untuk iterasi yang diberikan, sebagian besar ekspresi dapat dihitung satu kali, dan digunakan kembali sebagai konstanta untuk semua pemisahan:

$$\mathcal{L}^{(t)}\approx \sum_{i=1}^n \underbrace{\ell(y_i,\hat{y}_i^{(t-1)})}_{\text{constant}}+\underbrace{g_i}_{\text{constant}}f_t(\mathbf{x}_i)+\frac{1}{2}\underbrace{h_i}_{\text{constant}}f_t^2(\mathbf{x}_i)+\Omega(f_t),$$

Jadi satu-satunya hal yang harus Anda hitung adalah dan , dan yang tersisa kebanyakan adalah penambahan, dan beberapa perkalian. Selain itu, jika Anda melihat kertas XGBoost (arxiv) , Anda akan melihat bahwa mereka menggunakan fakta bahwa mereka sedang membangun pohon untuk lebih menyederhanakan ekspresi ke sekelompok penjumlahan indeks, yang sangat, sangat cepat.$f_t(x_i)$$\Omega(f_t)$

Ringkasan

Anda dapat melihat XGBoost (dengan perkiraan) sebagai regresi dari solusi yang tepat, perkiraan "XGBoost sejati", dengan evaluasi yang tepat. Tetapi karena evaluasi yang tepat sangat mahal, cara lain untuk melihatnya adalah bahwa pada kumpulan data besar, perkiraannya adalah yang dapat kita lakukan secara realistis, dan perkiraan ini lebih akurat daripada perkiraan urutan pertama yang akan dilakukan oleh algoritma peningkatan gradien "naif" .

Perkiraan yang digunakan mirip dengan Metode Newton , dan dibenarkan oleh Taylor Series (Wikipedia) dan Taylor Theorem (Wikipedia) .

Informasi urutan tinggi memang tidak sepenuhnya digunakan, tetapi itu tidak perlu, karena kami ingin pendekatan yang baik di sekitar titik awal kami .

Untuk visualisasi, periksa halaman Wikipedia dari Taylor Series / Teorema Taylor , atau Khan Academy tentang pendekatan Taylor Series , atau halaman MathDemo tentang perkiraan polinomial non-polinomial