Geekly articles weekly

Apa yang ada di dalam XGBoost, dan apa yang harus dilakukan Go dengan itu?

Dalam dunia pembelajaran mesin, salah satu jenis model yang paling populer adalah pohon yang menentukan dan ansambel berdasarkan pada mereka. Kelebihan pohon adalah: kemudahan interpretasi, tidak ada batasan pada jenis ketergantungan awal, persyaratan lunak pada ukuran sampel. Pohon juga memiliki kelemahan utama - kecenderungan untuk berlatih kembali. Oleh karena itu, hampir selalu pohon digabungkan menjadi ansambel: hutan acak, peningkatan gradien, dll. Tugas teoritis dan praktis yang kompleks adalah menyusun pohon dan menggabungkannya menjadi ansambel.

Dalam artikel yang sama, kami akan mempertimbangkan prosedur untuk menghasilkan prediksi dari model ansambel pohon yang sudah terlatih, fitur implementasi dalam gradien meningkatkan XGBoost populer XGBoost dan LightGBM . Dan juga pembaca akan berkenalan dengan perpustakaan leaves untuk Go, yang memungkinkan Anda membuat prediksi untuk ansambel pohon tanpa menggunakan API C dari perpustakaan asli.

Dari mana pohon itu tumbuh?


Pertimbangkan dulu ketentuan umum. Mereka biasanya bekerja dengan pohon, di mana:

  1. partisi dalam sebuah node terjadi sesuai dengan satu fitur
  2. pohon biner - setiap node memiliki keturunan kiri dan kanan
  3. dalam kasus atribut material, aturan keputusan terdiri dari membandingkan nilai atribut dengan nilai ambang batas

Saya mengambil ilustrasi ini dari dokumentasi XGBoost



Di pohon ini kami memiliki 2 node, 2 aturan keputusan, dan 3 lembar. Di bawah lingkaran, nilai ditunjukkan - hasil menerapkan pohon ke beberapa objek. Biasanya, fungsi transformasi diterapkan pada hasil komputasi pohon atau ansambel pohon. Misalnya, sigmoid untuk masalah klasifikasi biner.

Untuk mendapatkan prediksi dari ansambel pohon yang diperoleh dengan gradient boosting, Anda perlu menambahkan hasil prediksi semua pohon:

 double pred = 0.0; for (auto& tree: trees) pred += tree->Predict(feature_values);

Selanjutnya, akan ada C++ , sebagai dalam bahasa inilah XGBoost dan LightGBM ditulis. Saya akan menghilangkan detail yang tidak relevan dan mencoba memberikan kode yang paling ringkas.

Selanjutnya, pertimbangkan apa yang disembunyikan di Predict dan bagaimana struktur data pohon terstruktur.

Pohon XGBoost


XGBoost memiliki beberapa kelas (dalam arti OOP) pohon. Kita akan berbicara tentang RegTree (lihat include/xgboost/tree_model.h ), yang, menurut dokumentasi, adalah yang utama. Jika Anda hanya meninggalkan detail yang penting untuk prediksi, maka anggota kelas terlihat sesederhana mungkin:

 class RegTree { // vector of nodes std::vector<Node> nodes_; };

Aturan GetNext diimplementasikan dalam fungsi GetNext . Kode sedikit dimodifikasi, tanpa mempengaruhi hasil perhitungan:

 // get next position of the tree given current pid int RegTree::GetNext(int pid, float fvalue, bool is_unknown) const { const auto& node = nodes_[pid] float split_value = node.info_.split_cond; if (is_unknown) { return node.DefaultLeft() ? node.cleft_ : node.cright_; } else { if (fvalue < split_value) { return node.cleft_; } else { return node.cright_; } } }

Dua hal mengikuti dari sini:

  1. RegTree hanya berfungsi dengan atribut nyata (tipe float )
  2. nilai-nilai karakteristik yang dilewati didukung

Pusatnya adalah kelas Node . Ini berisi struktur lokal pohon, aturan keputusan dan nilai lembar:

 class Node { public: // feature index of split condition unsigned SplitIndex() const { return sindex_ & ((1U << 31) - 1U); } // when feature is unknown, whether goes to left child bool DefaultLeft() const { return (sindex_ >> 31) != 0; } // whether current node is leaf node bool IsLeaf() const { return cleft_ == -1; } private: // in leaf node, we have weights, in non-leaf nodes, we have split condition union Info { float leaf_value; float split_cond; } info_; // pointer to left, right int cleft_, cright_; // split feature index, left split or right split depends on the highest bit unsigned sindex_{0}; };

Fitur-fitur berikut dapat dibedakan:

  1. sheet direpresentasikan sebagai node yang cleft_ = -1
  2. bidang info_ direpresentasikan sebagai union , mis. dua jenis data (dalam hal ini sama) berbagi satu keping memori tergantung pada jenis simpul
  3. bit paling signifikan dalam sindex_ bertanggung jawab atas objek yang nilai atributnya dilewati

Agar dapat melacak lintasan dari memanggil metode RegTree::Predict hingga menerima jawabannya, saya akan memberikan dua fungsi yang hilang:

 float RegTree::Predict(const RegTree::FVec& feat, unsigned root_id) const { int pid = this->GetLeafIndex(feat, root_id); return nodes_[pid].leaf_value; } int RegTree::GetLeafIndex(const RegTree::FVec& feat, unsigned root_id) const { auto pid = static_cast<int>(root_id); while (!nodes_[pid].IsLeaf()) { unsigned split_index = nodes_[pid].SplitIndex(); pid = this->GetNext(pid, feat.Fvalue(split_index), feat.IsMissing(split_index)); } return pid; }

Dalam fungsi GetLeafIndex kita turun simpul pohon dalam satu lingkaran sampai kita menekan daun.

Pohon LightGBM


LightGBM tidak memiliki struktur data untuk node. Sebagai gantinya, struktur data pohon Tree ( include/LightGBM/tree.h file include/LightGBM/tree.h ) berisi array nilai, di mana nomor simpul digunakan sebagai indeks. Nilai dalam daun juga disimpan dalam array yang terpisah.

 class Tree { // Number of current leaves int num_leaves_; // A non-leaf node's left child std::vector<int> left_child_; // A non-leaf node's right child std::vector<int> right_child_; // A non-leaf node's split feature, the original index std::vector<int> split_feature_; //A non-leaf node's split threshold in feature value std::vector<double> threshold_; std::vector<int> cat_boundaries_; std::vector<uint32_t> cat_threshold_; // Store the information for categorical feature handle and mising value handle. std::vector<int8_t> decision_type_; // Output of leaves std::vector<double> leaf_value_; };

LightGBM mendukung fitur-fitur kategorikal. Dukungan diberikan menggunakan bidang bit, yang disimpan di cat_threshold_ untuk semua node. Dalam cat_boundaries_ menyimpan ke simpul mana bagian dari bidang bit yang sesuai. Bidang threshold_ untuk kasus kategorikal dikonversi ke int dan sesuai dengan indeks dalam cat_boundaries_ untuk mencari awal bidang bit.

Pertimbangkan aturan yang menentukan untuk atribut kategorikal:

 int CategoricalDecision(double fval, int node) const { uint8_t missing_type = GetMissingType(decision_type_[node]); int int_fval = static_cast<int>(fval); if (int_fval < 0) { return right_child_[node];; } else if (std::isnan(fval)) { // NaN is always in the right if (missing_type == 2) { return right_child_[node]; } int_fval = 0; } int cat_idx = static_cast<int>(threshold_[node]); if (FindInBitset(cat_threshold_.data() + cat_boundaries_[cat_idx], cat_boundaries_[cat_idx + 1] - cat_boundaries_[cat_idx], int_fval)) { return left_child_[node]; } return right_child_[node]; }

Dapat dilihat bahwa, tergantung pada missing_type nilai NaN secara otomatis menurunkan solusi di sepanjang cabang kanan pohon. Jika tidak, NaN diganti dengan 0. Mencari nilai dalam bidang bit cukup sederhana:

 bool FindInBitset(const uint32_t* bits, int n, int pos) { int i1 = pos / 32; if (i1 >= n) { return false; } int i2 = pos % 32; return (bits[i1] >> i2) & 1; }

mis., misalnya, untuk atribut kategorikal int_fval=42 diperiksa apakah bit ke-41 (penomoran dari 0) diatur dalam array.

Pendekatan ini memiliki satu kelemahan signifikan: jika atribut kategorikal dapat mengambil nilai besar, misalnya 100500, maka untuk setiap aturan keputusan untuk atribut ini bidang bit akan dibuat hingga ukuran 12564 byte!

Oleh karena itu, diinginkan untuk memberi nomor baru pada nilai atribut kategorikal sehingga mereka terus menerus dari 0 ke nilai maksimum .

Untuk bagian saya, saya membuat perubahan jelas ke LightGBM dan menerimanya .

Berurusan dengan atribut fisik tidak jauh berbeda dari XGBoost , dan saya akan melewatkan ini untuk singkatnya.

leaves - library untuk prediksi di Go


XGBoost dan LightGBM perpustakaan LightGBM sangat kuat untuk membangun model LightGBM gradien pada pohon keputusan. Untuk menggunakannya dalam layanan backend, di mana algoritma pembelajaran mesin diperlukan, perlu untuk menyelesaikan tugas-tugas berikut:

  1. Pelatihan berkala model offline
  2. Pengiriman model dalam layanan backend
  3. Model jajak pendapat online

Untuk menulis layanan backend yang dimuat, Go adalah bahasa yang populer. XGBoost atau LightGBM melalui API C dan cgo bukan solusi termudah - pembuatan program ini rumit, karena penanganan yang ceroboh, Anda dapat menangkap SIGTERM , masalah dengan jumlah utas sistem (OpenMP di dalam perpustakaan vs utas runtime utas).

Jadi saya memutuskan untuk menulis perpustakaan di Go murni untuk prediksi menggunakan model yang dibangun di XGBoost atau LightGBM . Ini disebut leaves .

pergi

Fitur utama perpustakaan:

  • Untuk model LightGBM
    • Membaca model dari format standar (teks)
    • Dukungan untuk atribut fisik dan kategorikal
    • Dukungan Nilai Hilang
    • Optimalisasi kerja dengan variabel kategori
    • Optimasi Prediksi dengan Struktur Data Hanya-Prediksi

  • Untuk model XGBoost
    • Membaca model dari format standar (biner)
    • Dukungan Nilai Hilang
    • Optimasi Prediksi


Berikut adalah program Go minimal yang memuat model dari disk dan menampilkan prediksi:

 package main import ( "bufio" "fmt" "os" "github.com/dmitryikh/leaves" ) func main() { // 1.     path := "lightgbm_model.txt" reader, err := os.Open(path) if err != nil { panic(err) } defer reader.Close() // 2.   LightGBM model, err := leaves.LGEnsembleFromReader(bufio.NewReader(reader)) if err != nil { panic(err) } // 3.  ! fvals := []float64{1.0, 2.0, 3.0} p := model.Predict(fvals, 0) fmt.Printf("Prediction for %v: %f\n", fvals, p) }

API perpustakaan minimal. Untuk menggunakan model XGBoost cukup panggil metode leaves.XGEnsembleFromReader alih-alih yang di atas. Prediksi dapat dibuat dalam batch dengan memanggil metode PredictDense atau PredictDense . Lebih banyak skenario penggunaan dapat ditemukan dalam tes daun .

Terlepas dari kenyataan bahwa Go berjalan lebih lambat daripada C++ (terutama karena pemeriksaan runtime dan runtime yang lebih berat), berkat sejumlah optimisasi, dimungkinkan untuk mencapai tingkat prediksi yang sebanding dengan memanggil API C dari perpustakaan asli.


Rincian lebih lanjut tentang hasil dan metode perbandingan ada di repositori di github .

Lihat akarnya


Saya harap artikel ini membuka pintu bagi implementasi pohon di XGBoost dan LightGBM . Seperti yang Anda lihat, konstruksi dasarnya cukup sederhana, dan saya mendorong pembaca untuk memanfaatkan open source - untuk mempelajari kode ketika ada pertanyaan tentang cara kerjanya.

Bagi mereka yang tertarik pada topik menggunakan model meningkatkan gradien dalam layanan mereka dalam bahasa Go, saya sarankan Anda membiasakan diri dengan perpustakaan daun . Dengan menggunakan leaves Anda dapat dengan mudah menggunakan solusi terdepan dalam pembelajaran mesin di lingkungan produksi Anda, hampir tanpa kehilangan kecepatan dibandingkan dengan implementasi C ++ asli.

Semoga beruntung

Source: https://habr.com/ru/post/id423495/

More articles:


All Articles