Bu yazı genel olarak gradient boosting machine ve onun geliştirilmiş hali olan lightGBM ile birlikte gelen GOOS ve EFB’nin ne olduğu üzerine olacak. GOOS ve EFB algoritmaları için lightGBM’in orjinal olan olan LightGBM: A Highly Efficient Gradient Boosting Decision TreeMicrosoft (2017-Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu) kullanılmıştır.

• LightGBM, sıralama, sınıflandırma ve diğer birçok machine learning alanlarında kullanılan decision tree algoritmasına dayanan hızlı, dağıtılmış, yüksek performanslı bir gradient boosting framework’üdür.
• LightGBM, XGBoost’un eğitim süresi performansını artırmaya yönelik geliştirilen bir GBM türüdür.
• Level-wise büyüme stratejisi yerine Leaf-wise büyüme stratejisi kullanır
• Breadth-first search (BFS) yerine depth-first search (DFS) kullanır.

 

Genel Formül Şöyledir:

GBM = Desicion Tree + Boosting + Gradient Descent

LightGbm = GBM + GOSS + EFB

Yani klasik GBM yaklaşımıyla birlikte GOOS ve EFB isimli iki iyileştirme eklenmiştir. Framework’te iki yaklaşımda parametrik olarak gelir. Default olarak EFB aktifken GOOS pasif olarak gelir. Bu özellikleri açıp kapamak öğrenme modelini kuracak kişinin inisiyatifindedir. Yazının sonlarında derinlemesine anlatacağımız bu iki özellik için kısaca değinecek olursak; GOOS verinin öğrenilmesi (fit) aşamasında çalışırken EFB bellek tüketimini en aza indirmek için geliştirilmiştir.

Şimdi GOOS ve EFB’ye gelmeden önce kısaca GBM yaklaşımının kavranması için Desicion Tree, Boosting Machine, ve Gradient artırma aşamalarına  bakalım (kısaca anlatılmıştır).

 

Desicion Tree (Karar Ağacı)

‘ Heterojen veri setleri belirlenmiş bir hedef değişkene göre homojen alt gruplara ayrılır ‘ — Leo Breiman, 1984

1. Desicion tree’ nin temeli Morgan ve Sonquist’ in 1970’ lerde kullandıkları AID (Automatic Detector)’ dayanır.
2. Karar Agaçları tümevarımlı mantığın programlama ortamına taşındıgı basit fakat çok yaygın bir metoddur.
3. Ayrık değerli parametrelerle çalışır. Gürültüye karşı dayanıklı bir algoritmadır. (Overfitting)
4. Karar ağacı algoritmalarının dayandığı tümevarımlı felsefeye dair temel sezgi öğrenme özellikleriyle oluşturulacak karar ağacının olabildiğince küçük olmasının iyi olacağı yönündedir.
5. Ağacın optimum olması için, hangi değişkenlere göre nasıl bir sırada dallanma yapılacağının seçilmesi algoritmanın kalitesini gösterir (information gain, gain ratio, gini index)
6. Overfitting’ i önlemek için ağaç oluşturulurken ya da daha sonra budama yapılır

Boosting

• Boosting, zayıf öğrenicileri (weak learner) bir araya getirip, güçlü bir öğrenici (strong learner) ortaya çıkarma fikrine dayanır. — Kearns ve Valiant, 1990
• Bu yaklaşım daha sonra (1996–1999) Schapires ve Freund tarafından hayata geçirilmiştir. (Adaptive Boosting-AdaBoost)
• Bu işlem iteratif olarak ağırlık artırılarak yapılır.

Algoritma bütün noktaların eşit ağırlıkta olduğu bir şekilde başlar

2. iterasyonda en iyi çözüm soldaki şekilde olmaktadır. Doğru sınıflandırılan ağırlığı 11 iken, hatalı sınıflandırılanların ağırlığı 3 olarak oluşmuştur.  Hatalı sınıflandırılan ağırlığını (11/3 ≈ 3.66) ile çarpmamız gerekiyor.

Şimdi 3 iterasyonda elde ettiğimiz zayıf öğrenicileri (weak learner) birleştirme aşamasına geldik.

ln(doğru/yanlış) formülü ile bölgeleri (+ ,— )şeklinde işaretleyeceğiz.

Gradient Descent (Gradyan Artırma)

• Boosting, sadece sınıflandırma problemleri için kullanılabilir; diğer problemlere uyarlanamaz.
• ‘Boosting, bir optimizasyon problemi olarak görülebilir.’ — Breiman, 1997
• Friedman 2001’de bu fikir üzerine GBM’ i ortaya çıkardı.
• Boosting uygun bir cost fonksiyonu üzerinde çalışan bir optimizasyon algoritması haline geldi.
• GBM, diferansiyellenebilen herhangi bir kayıp fonksiyonunu optimize edebilen Gradient Descent algoritmasını kullanır.
• GBM,tek bir tahminsel model formunda olan modeller serisi oluşturur. Seri içindeki bir model serideki bir önceki modelin tahmin atıklarının (residuals) üzerine kurularak (fit) oluşturulur.

Bu, zayıf tahmin modellerinin bir araya gelmesiyle tipik olarak karar ağaçlarının oluşturduğu bir model oluşturur. Denetlenen herhangi bir öğrenme algoritmasının amacı, bir kayıp fonksiyonu tanımlamak ve en aza indirmektir.

Tahminlerimizi, kayıp fonksiyonumuzu (MSE) minimum olacak şekilde istiyoruz. Gradyan iniş kullanarak ve tahminlerimizi öğrenme oranına göre güncelleyerek, MSE’nin minimum olduğu değerleri bulabiliriz.

Gradyan artırma algoritmasının ardındaki sezgi, artıklardaki örüntüleri tekrar tekrar kullanmak ve zayıf tahminlerle bir modeli güçlendirmek ve daha iyi hale getirmektir. Daha iyi anlaşılması için aşağıdaki örneği incelemede fayda var..

---

GOSS (Gradient Based One Side Sampling-Tek Taraflı Örnekleme)

1. GOSS önce verilerin degradelerinin mutlak değerlerini sıralar
2. En üstteki örnekleri seçer (a)
3. Daha sonra b örnekleri için kalan verilerde rastgele örnekler alır
4. Bilgi kazancını hesaplayarak örneklenmiş küçük Gradyan verilerini çarpar ((1-a) / b)
5. Algoritma yetersiz eğitim örneklerine daha fazla dikkat edecek ve orijinal veri setinin dağılımını çok fazla değiştirmeyecektir. Daha iyi anlaşılması için aşağıdaki tablo GOSS hakkında genel yaklaşımı veriyor.

Max gradyanlı iki örnek alındı. Kalanlar içinde(min olanlar) rastgele 2 örnek alındı ve başlangıç ağırlıkları 1 olarak atanmış bu örneklerde büyük gradyanlar korundu ve küçük gradyanlara 4/2 ile çarpıldı yani küçük gradyanlar/aldığımız küçük gradyan sayısı

GOSS sayesinde büyüme soldaki gibi değil sağdaki gibi küçük gradyanlar(daha iyi eğitilmiş örnekler) kullanılarak inşa edilir.

---

EFB (Exclusive Feature Bundling)

• LightGBM, özellikleri bir araya getirerek öğrenmeyi hızlandırır. Genellikle yüksek boyutlu veriler ile çalışılır. Bu tür veriler, birbirini dışlayan birçok özelliğe sahiptir. LightGBM karmaşıklığı azaltmak için bazı özellikleri tek bir özellik haline getirir.
• Ele alınması gereken iki konu vardır. Birincisi, hangi özelliklerin birlikte paketlenmesi gerektiğini belirlemektir. İkincisi, paketin nasıl oluşturulacağıdır.

Önce birbirini dışlayan özellik değişkenleri bulunur(soldaki) daha sonra özellikler birleştirilerek tek özellik haline getirilir. Bu sayede öğrenme süresi hızlanır ve bellek kullanımı azaltılır. Birbirini dışlayandan kasıt: Özelliklerden biri bir değere sahipken(non-zero) diğer özellik(ler) sıfırdır.(0)

Birleştirme işlemi ise şöyle yapılır: Featur1 [0, 4]aralığındadır ve Feature2 ise [0, 2] o halde feture_bundle [0, 6 aralığında olur]; yani feature2, feature1 üzerine kaydırıldı. Örneğin; feature_bundle(5), feature(1) demektir veya feature_bundle(3), feature1(3) demektir.

---

DATA’ ya EFB uygulandıktan sonra ağaç oluşturmak için XGBoost da kullanılan histogram tabanlı yaklaşım ile özelliklere göre ağaç oluşturulur ve klasik GBM deki mantık ile öğrenme başlar lakin gradient artırma işleminde GOSS yaklaşımı uygulanır. Yaptıkları bu iyileştirmelerle 20 kat daha hızlı ve aynı sonuçları verdiğini iddia etmekteler 🙂