Formulasi Matematis XGBoost

Jul 19, 2024

Formulasi Matematis XGBoost - Catatan Kuliah

Prasyarat

  • Matematika Adaboost (dibahas di Bagian 5)
  • Matematika Gradient Boost (dibahas di Bagian 6)
  • Konsep-konsep XGBoost (dibahas di Bagian 7)

Ikhtisar

  • XGBoost: Implementasi pohon pendorong gradien yang dioptimalkan
  • Berdasarkan algoritme peningkatan gradien 8 langkah dengan perbaikan tambahan
  • Model yang diregulasi: Mengukur kompleksitas pohon dengan dua komponen:
    • Kehilangan Pelatihan: Mengukur kesesuaian data dengan model
    • Komponen Regulasi: Mengukur kompleksitas pohon

Fungsi Kehilangan

  • Menggunakan kehilangan kuadrat: Jumlah perbedaan kuadrat antara nilai prediksi dan nilai aktual
  • Optimasi trade-off antara kehilangan pelatihan dan kehilangan regulasi
    • Optimasi Kehilangan Pelatihan: Akurasi yang lebih tinggi pada data latihan
    • Optimasi Regulasi: Model yang lebih sederhana untuk produksi

Parameter Regulasi

  • Jumlah Daun
  • Norma L2 dari Bobot Daun
  • Hiperparameter: Gamma dan Lambda
  • Rumus regulasi termasuk:
    • Jumlah daun yang dibobotkan oleh gamma
    • Norma L2 bobot yang dibobotkan oleh lambda

Contoh

  • Pohon sampel dengan 2 node dan 3 daun:
    • Bobot: Daun 1 = +2, Daun 2 = 0,1, Daun 3 = -1
    • Regulasi: Gamma * 3 + 0.5 * Lambda * (W1^2 + W2^2 + W3^2)

Komponen Kehilangan Pelatihan

  • Diwakili sebagai model aditif karena peningkatan
  • Mengikuti konstruksi yang mirip dengan Adaboost dan Gradient Boost
  • Rumus: Model akhir Y_hat(t) = Model sebelumnya Y_hat(t-1) + Model baru

Aproksimasi Taylor

  • Mengaproksimasi fungsi yang dapat dibedakan
  • Rumus: F(x + deltaX) ≈ F(x) + F'(x) * deltaX + 0,5 * F''(x) * deltaX^2
  • Diterapkan pada fungsi objektif XGBoost untuk aproksimasi kuadrat
  • Pengenalan istilah Gi dan Hi: Diferensiasi orde pertama dan kedua

Fungsi Objektif yang Disederhanakan

  • Menggabungkan kehilangan pelatihan dan regulasi
  • Menggunakan jumlah G dan H untuk notasi
  • Fungsi objektif baru: Jumlah persamaan kuadrat
  • Bobot daun optimal Wj diturunkan sebagai -Gi / (Hi + Lambda)
  • Menulis kembali fungsi objektif tanpa W: Fungsi Objektif Minimum

Proses Pembangunan Pohon

  • Algoritma pertumbuhan pohon serakah
  • Dimulai dengan kedalaman pohon nol
  • Coba tambahkan pembagian untuk setiap node daun (pendekatan serakah)
  • Fungsi objektif "sebelum" dan "sesudah" pembagian
  • Fungsi Gain menghitung keuntungan dari pembagian:
    • Gain = (Skor anak kiri + Skor anak kanan) - (Skor agregat jika tidak dibagi) - Gamma
  • Menghentikan pembagian jika node pembagian terbaik memiliki keuntungan negatif
  • Menggunakan algoritma yang menyadari kelangkaan

Ringkasan Algoritma

  1. Mulai dengan pembelajar lemah F(xi)
  2. Untuk loop: Bangun T pohon menggunakan algoritma pembelajaran pohon
  3. Gunakan fungsi objektif minimum untuk setiap pohon yang dibangun
  4. Secara aditif menggabungkan model
  5. Pelatihan berhenti ketika T tercapai atau tingkat akurasi yang dapat diterima tercapai
  6. Model akhir: Kombinasi aditif dari semua model dalam loop

Ringkasan

  • Fungsi objektif umum dan kehilangan kuadrat
  • Optimasi trade-off
  • Pengukuran kompleksitas pohon
  • Dekonstruksi menjadi metode aditif
  • Aproksimasi Taylor untuk formulir kuadrat
  • Menurunkan bobot optimal dan fungsi objektif minimum
  • Proses pembangunan pohon dan pembelajaran struktur

Langkah Selanjutnya

  • Video berikutnya: Contoh ilustratif pembangunan pohon XGBoost berdasarkan formulasi yang telah dibahas