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

1. iterasyonda 7 doğruya karşı 3 hatalı sınıflandırmamız var. (7/3 ≈ 2.33)  Hatalı sınıflandırılan 3 noktanın ağırlığını 2.33 ile çarpar bu sonucu kaydeder bir sonraki adıma geçeriz.

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.

Doğru noktaların ağırlığı 19 iken, yanlış sınıflandırılan noktaların ağırlığı 3 olmuştur.

Ş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.

Gradient Descent optimizasyon algoritmasının genel yaklaşımı hakkında bilgi vermesi için bu iki grafiği paylaştım. Global min/max noktalırını araştırırken fonksiyonun gradyanı bize bu noktalara olan yönleri verir.

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.

Kullacağımız kayıp fonksiyonu

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.

Bu şekilde türevi alınarak; gradyan artırma iteratif olarak yapılır

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..

Görüldüğü gibi iterasyon sayısının artırılması overfitting’ e sebep olmaktadır


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

ilgili makalede verilen algoritma

  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 özelliği parametriktir, bu özellik yerine random forest veya klasik gbdt gibi yaklaşımlarda tercih edilebilir..

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.

ilgili makalede geçen algoritma

Ö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 🙂

Last modified: 1 Şubat 2020

Comments

Long time supporter, and thought I’d drop a comment.

Your wordpress site is very sleek – hope you don’t mind
me asking what theme you’re using? (and don’t mind if I steal
it? :P)

I just launched my site –also built in wordpress like yours– but the theme slows (!) the site down quite a bit.

In case you have a minute, you can find it by searching for
“royal cbd” on Google (would appreciate any feedback) – it’s still in the works.

Keep up the good work– and hope you all take care of yourself during the coronavirus scare!

Its like you learn my thoughts! You appear to grasp so much approximately this, such as you wrote the guide in it or something.

I think that you simply could do with a few percent to power
the message house a bit, however instead of that, that is excellent blog.
An excellent read. I’ll definitely be back.

Write a Reply or Comment

Your email address will not be published.