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 XGBoost (dibahas di Bagian 7)

Tinjauan

  • XGBoost: Implementasi pohon gradient booster yang dioptimalkan
  • Berdasarkan algoritma boosting gradient 8-langkah dengan perbaikan tambahan
  • Model teratur: Mengukur kompleksitas pohon dengan dua komponen:
    • Kerugian Pelatihan: Mengukur kecocokan data dengan model
    • Komponen Regularisasi: Mengukur kompleksitas pohon

Fungsi Kerugian

  • Menggunakan kerugian kuadrat: Jumlah perbedaan kuadrat antara nilai prediksi dan aktual
  • Pengoptimalan trade-off antara kerugian pelatihan dan kerugian regularisasi
    • Pengoptimalan Kerugian Pelatihan: Akurasi lebih tinggi pada data pelatihan
    • Pengoptimalan Regularisasi: Model lebih umum dan sederhana untuk produksi

Parameter Regularisasi

  • Jumlah Daun
  • L2 Norm dari Berat Daun
  • Hiperparameter: Gamma dan Lambda
  • Formula regularisasi meliputi:
    • Jumlah daun yang diberi bobot oleh gamma
    • Lambda berbobot L2 norm dari skor daun

Contoh

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

Komponen Kerugian Pelatihan

  • Diwakili sebagai model aditif karena boosting
  • Mengikuti konstruksi serupa dengan Adaboost dan Gradient Boost
  • Formula: Model akhir Y_hat(t) = Model sebelumnya Y_hat(t-1) + Model baru

Aproksimasi Taylor

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

Fungsi Objektif yang Disederhanakan

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

Proses Membangun Pohon

  • Algoritma penumbuhan pohon yang serakah
  • Memulai dengan kedalaman pohon nol
  • Mencoba menambahkan split untuk setiap node daun (pendekatan serakah)
  • Fungsi objektif "sebelum" dan "sesudah" split
  • Fungsi gain menghitung keuntungan dari split:
    • Gain = (Skor anak kiri + Skor anak kanan) - (Skor agregat jika tidak split) - Gamma
  • Menghentikan split jika node split terbaik memiliki gain negatif
  • Menggunakan algoritma kesadaran-sparse

Ringkasan Algoritma

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

Ulasan Kembali

  • Fungsi objektif umum dan kerugian kuadrat
  • Pengoptimalan trade-off
  • Ukuran kompleksitas pohon
  • Dekonstruksi ke metode aditif
  • Aproksimasi Taylor untuk bentuk kuadratik
  • Menentukan bobot optimal dan fungsi objektif minimum
  • Proses membangun pohon dan pembelajaran struktur

Langkah Selanjutnya

  • Video selanjutnya: Contoh ilustratif dari pembangunan pohon XGBoost berdasarkan formulasi yang dibahas