Ensemble Methods and Gradient boosting

1. Ensemble Yöntemlerine Giriş

Tek bir karar ağacı, eğitim verisini iyi öğrenebilir; ancak temel bir zayıflığı vardır: kararsızlık. Eğitim verisinde küçük bir değişiklik bile ağacın tamamıyla farklı bir yapıya bürünmesine yol açabilir. Budama bu sorunu kısmen hafifletse de kökten çözmez.

Single Decision Tree nedir?
Bir decision tree, veriyi sorularla bölen bir modeldir. Örneğin elimizde ev fiyatlarını tahmin eden bir model olsun. Ağaç şu şekilde çalışır:

"Evin alanı 100 m²'den büyük mü?" → Evet: "Merkeze uzaklık 5 km'den az mı?" → ... → Hayır: "Kat sayısı 3'ten fazla mı?" → ...

Her soru bir node, her dal bir branch, en uçtaki sonuçlar ise leaf olur. Yani ağaç, veriyi ardışık sorularla parçalara ayırarak bir tahmin üretir.

Eğitim verisindeki küçük bir değişiklik ağacın yapısını tamamıyla değiştirebilir.

Peki neden?
Decision tree eğitilirken her node'da "hangi soruyu sorarsam veriyi en iyi bölerim?" diye hesap yapılır. Bu hesap, eğitim verisinin tamamına bağlıdır.

Şöyle düşünün: ilk node'daki soru "alan > 100 m² mi?" olarak belirlendi diyelim. Eğitim verisine 10 yeni ev eklersen bu soru artık en iyi bölme olmayabilir, yerini "alan > 120 m² mi?" alabilir. İlk soru değişince tüm dallar yeniden şekillenir, çünkü her dal bir önceki sorunun cevabına göre oluşur. Yani ağaç kademeli değil, zincirleme bir yapıya sahiptir. 

Buna high variance denir. Model veriye aşırı duyarlıdır.

Pruning nedir?
Decision tree eğitildiğinde eğer durdurulmazsa sonunda her leaf'te tek bir örnek kalacak şekilde büyür. Bu durumda model eğitim verisini ezberler ama yeni veriyle karşılaşınca başarısız olur. Buna overfitting denir.

Pruning, bu aşırı büyümüş ağacı geri budamak demektir. "Bu dal gerçekten işe yarıyor mu, yoksa eğitim verisindeki gürültüyü mü öğrendi?" diye sorularak gereksiz dallar kırpılır.

Pruning overfitting'i azaltır ama variance sorununu tamamen çözmez. Çünkü ağaç hâlâ tek bir modeldir ve eğitim verisindeki küçük değişikliklere duyarlılığı devam eder.

2. Random Forest

İlk kısımda gördüğümüz temel problem şuydu: tek bir decision tree veriye aşırı duyarlı. Peki çözüm ne?

Random Forest'ın fikri şu: tek bir kararsız ağaca güvenmek yerine, yüzlerce farklı ağaç eğit ve hepsinin kararını ortala.

Ama burada kritik bir soru var — eğer hepsi aynı veriyle eğitilirse, hepsi aynı ağacı üretir. O zaman 100 ağacın ortalaması yine tek ağaçla aynı olur. Bunu çözmek için Random Forest iki farklı rastgelelik mekanizması kullanır.

Birinci mekanizma: Bagging
Bir bankada çalıştığınızı ve bir müşteriye "Kredi verilmeli mi, verilmemeli mi?" sorusuna yanıt arayan bir yapay zeka modeli geliştirdiğini düşünün. Elinizde geçmişteki 1000 müşterinin verisi var. Bu veri setine göre her müşteri için de 10 farklı özellik (Gelir, Yaş, Kredi Skoru, Mevcut Borç, Ev Sahibi Olma Durumu vb.) tutuluyor. Bu özelliklere göre 1000 müşteriye kredi verilmiş ve bazıları bu krediyi sorunsuz geri öderken bazıları ödememiştir.

Bagging ile şunu yapıyoruz: 

• Torbadan Çekiliş: İçinde 1000 müşterinin ismi yazan bir torba hayal edin. Torbadan rastgele bir isim çekiyoruz, bakıp listemize yazıyoruz ve o ismi tekrar torbaya geri atıyoruz . Bu işlemi 1000 kez tekrarlıyoruz.

• Sonuç: Yeni oluşturduğumuz bu yapay listede bazı müşterilerin isimleri şans eseri 3 kez yazılmışken, bazılarınınki hiç yazılmamış oluyor.

• Ağaçları Eğitme: Bu işlemi 50 kez tekrarlayarak 50 farklı "çakma" veri seti üretiyoruz ve her biriyle ayrı bir karar ağacı eğitiyoruz.

  Karar anı: Bankaya yeni bir müşteri geldi. 50 ağacın 38 tanesi geçmişteki kendi farklı deneyimlerine dayanarak "Bu adam kredi ödemez, onaylama" diyor. 12 tanesi "Onayla" diyor. Modelimiz çoğunluğun dediğini seçiyor (38 oy) ve krediyi reddediyor. Tek bir ağacın hata yapma riskini, 50 ağacın ortak kararıyla sıfırlamış olduk.

İkinci Mekanizma: Feature Randomization (Öznitelik Rastgeleselliği)
Bu kavramı anlamak için önce şunu sormak lazım: bagging yeterli değil mi?

Değil. Çünkü Elimizdeki 10 özellik arasından "Kredi Skoru" o kadar güçlü bir belirleyici ki, yukarıda ürettiğimiz 50 farklı ağacın 50'si de ilk soruyu "Müşterinin kredi skoru yüksek mi?" diye sormaya başlar.

Eğer bütün ağaçlar aynı soruyla başlarsa, temelde hepsi birbirinin kopyası olur. Birinin yaptığı hatayı hepsi yapar ve bagging yapmamın bir anlamı kalmaz. İşte Feature Randomization burada devreye girer. 

Birinci ağaç ilk ayrımını (split) yapacağı zaman, onun önüne 10 özelliğin hepsini koymuyoruz. Bilgisayar rastgele 3 özellik seçiyor: Diyelim ki bunlar yaş, ev sahibi olma ve mevcut borç olsun.

Ağaç mecburen Kredi Skoru'na bakamıyor ve mevcut borç durumu üzerinden bir mantık geliştirmeye zorlanıyor. İkinci ağaç kök düğümü oluştururken bilgisayar yine rastgele 3 özellik seçiyor: gelir, kredi skoru, medeni durum. Bu sefer liste farklı.

Sonuç: Ağaçların her birini verinin farklı boyutlarına bakmaya zorlamış olduk. Ağaç 1 "Borç/Yaş" uzmanı olurken, Ağaç 2 "Gelir/Kredi Skoru" uzmanı oldu. Birbirinden bağımsız (uncorrelated) hale geldiler. Biri yanılsa bile diğeri kendi uzmanlık alanından doğruyu yakalar.

İşte bu iki örneği aynı anda uyguladığımızda elimizde bir Random Forest modeli oluyor.

3. Bagging

Bagging'in tam adı bootstrap aggregating'dir. Mantığı şu: aynı öğrenme algoritmasını, verinin farklı bootstrap sample'larıyla defalarca çalıştır ve sonuçları birleştir.

Random Forest'tan farkı şu: Random Forest sadece decision tree'lerle çalışır ve feature randomization ekler. Bagging ise herhangi bir algoritmayla kullanılabilir — decision tree, k-nearest neighbors, hatta linear regression. Ve feature randomization yapmaz, sadece veriyi farklılaştırır.

Yani Random Forest, "bagging + decision tree + feature randomization" demektir. Bagging ise daha genel bir çerçevedir.

Bagging'de modellerin çıktıları iki şekilde birleştirilir. Sınıflandırma problemlerinde çoğunluk oylaması yapılır — hangi sınıf daha çok oy aldıysa o seçilir. Regression problemlerinde ise tahminlerin ortalaması alınır.

Ne zaman işe yarar?
Bagging, yüksek variance'lı modellerde işe yarar. Yani veriye aşırı duyarlı, küçük değişikliklerde yapısı değişen modellerde. Decision tree bunun klasik örneği. Ama düşük variance'lı, zaten stabil olan modellerde bagging pek bir şey kazandırmaz.

4. Boosting

Boosting'in mantığı şu soruya dayanıyor: "Modelim nerede hata yapıyor? Bir sonraki modeli tam oraya odaklayayım."

Yani boosting sıralı bir süreçtir. Önce zayıf bir model eğitilir. Bu model bazı örnekleri yanlış tahmin eder. Sonraki model, yanlış tahmin edilen örneklere daha çok odaklanır. Bu süreç tekrarlanır. Her yeni model, önceki modellerin toplu hatasını azaltmaya çalışır.

Sonunda bu zayıf modellerin hepsi birleştirilir ve güçlü bir model elde edilir.

Weak learner nedir?
Boosting'de kullanılan modeller kasıtlı olarak basit tutulur. Bunlara weak learner denir. Genellikle sadece tek bir sorudan oluşan, yani derinliği 1 olan bir decision tree kullanılır — buna decision stump denir.

Tek başına bir decision stump çok zayıftır, rastgele tahminden biraz daha iyidir. Ama boosting bunu bir avantaja dönüştürür: yüzlerce zayıf modeli doğru sırayla birleştirince güçlü bir model ortaya çıkar.

5. AdaBoost

AdaBoost, boosting fikrinin ilk somut uygulamasıdır. "Adaptive Boosting" kelimesinin kısaltmasıdır — "adaptive" yani uyarlanabilir, çünkü her adımda hataya göre kendini ayarlıyor.

Mekanizma

AdaBoost şu adımlarla çalışır:

Başlangıçta her eğitim örneğine eşit ağırlık verilir. Diyelim ki 100 örnek var, her birinin ağırlığı 1/100.

İlk weak learner eğitilir. Bazı örnekleri doğru, bazılarını yanlış tahmin eder. Yanlış tahmin edilen örneklerin ağırlığı artırılır, doğru tahmin edilenlerin ağırlığı azaltılır.

İkinci weak learner bu yeni ağırlıklarla eğitilir. Artık zor örneklere daha çok "dikkat eder" çünkü onlar daha ağır basmaktadır.

Bu süreç tekrarlanır. Her turda bir önceki modelin zorlandığı noktalar daha fazla önem kazanır.

Sonuçları birleştirme

Bagging'de tüm modeller eşit oylanıyordu. AdaBoost'ta ise her weak learner'ın bir ağırlığı vardır — buna alpha denir. Daha az hata yapan model daha yüksek alpha alır, yani son kararda daha fazla söz hakkı olur. Tahmin, bu ağırlıklı oylamayla üretilir.

6. Gradient Boosting

AdaBoost'ta "hata" şu anlama geliyordu: bu örneği doğru sınıfladım mı, yanlış mı? Yani binary bir kavram.

Gradient Boosting'de ise "hata" çok daha nüanslı. Model bir tahmin üretiyor, gerçek değerden ne kadar uzak olduğuna bakılıyor. Bu farka residual denir. Ve bir sonraki model, ham veriyi değil, bu residual'ları tahmin etmeye çalışıyor.

Adım adım ne oluyor?

Önce çok basit bir başlangıç tahmini yapılır — mesela tüm örneklerin ortalaması.

Sonra bu tahminin residual'ları hesaplanır: gerçek değer eksi tahmin.

İkinci model bu residual'ları tahmin etmek için eğitilir. Yani "ilk model ne kadar yanıldı?" sorusunu cevaplamaya çalışır.

İkinci modelin tahmini ilk modelin tahminine eklenir — ama doğrudan değil, learning rate adı verilen küçük bir katsayıyla ölçeklenerek. Bu adım aşırı düzeltme yapmayı engeller.

Yeni residual'lar hesaplanır ve süreç tekrarlanır.

"Gradient" kelimesi nereden geliyor?

Gradient Boosting aslında bir optimizasyon problemi çözüyor. Elimizde bir loss function var — modelin ne kadar hata yaptığını ölçen bir fonksiyon. Amacımız bu fonksiyonu minimize etmek.

Bunu yapmak için gradient descent kullanılıyor. Gradient descent şunu söyler: "Hatanın en hızlı azaldığı yönde küçük adımlar at." Gradient ise tam olarak bu yönü gösteriyor — loss function'ın hangi yönde en hızlı arttığının tersi.

Normal gradient descent'te model parametrelerini güncellersin. Gradient Boosting'de ise her yeni ağaç, bu gradienti tahmin etmek için eğitilir. Yani ağaç bir optimizer görevi görüyor — "hatayı en çok nerede ve nasıl azaltabilirim?" sorusunu cevaplıyor.

Residual'ların tam olarak bu gradientin bir özel hali olduğu görülebilir. Yani residual'ları tahmin etmek, aslında gradienti takip etmek demektir.

7. XGBoost

XGBoost, Gradient Boosting'in aynı fikri çok daha akıllıca uygulayan bir versiyonu.

Gradient Boosting her adımda şunu soruyordu: "Hatam hangi yönde azalıyor?" Ve o yönde bir adım atıyordu.

Bu gradient'i kullanmak demek — yani birinci türevi kullanmak. Hatanın hangi yönde değiştiğini biliyorsun, ama ne kadar hızlı değiştiğini bilmiyorsun. Yani eğimi biliyorsun ama eğimin eğimini bilmiyorsun.

XGBoost burada şunu soruyor: "Neden sadece birinci türevle yetinelim? İkinci türevi de kullanalım."

İkinci türev ne kazandırıyor?

Bunu somutlaştırmak için şöyle düşünün. Bir dağdan aşağı iniyorsunuz ve amacınız en hızlı şekilde en dibe ulaşmak.

Gradient Boosting: "Ayağımın altındaki zemin hangi yöne eğimli?" diye bakıyor ve o yönde adım atıyor. Ama adım boyutunu bilmiyor.

XGBoost: "Zemin hangi yöne eğimli ve bu eğim ne kadar hızlı değişiyor?" diye bakıyor. Eğer önündeki zemin giderek dikleşiyorsa küçük adım atıyor, düzleşiyorsa büyük adım atıyor. Bu Newton'ın yöntemi olarak biliniyor — hem yönü hem de eğriliği kullanarak çok daha verimli adımlar atıyor.

Pratikte bu şu anlama geliyor: Gradient Boosting'in 100 ağaca ihtiyaç duyduğu bir problemde XGBoost çok daha az ağaçla aynı doğruluğa ulaşabiliyor.

Regularization

XGBoost'un bir diğer kritik farkı: ağaçların karmaşıklığını doğrudan cezalandırıyor.

Gradient Boosting sadece "hatayı azalt" diyordu. XGBoost ise "hatayı azalt, ama ağaçları gereksiz yere karmaşıklaştırma" diyor. Bunu loss function'a bir regularization terimi ekleyerek yapıyor. Ağaçtaki fazla node'lar ve büyük değerler cezalandırılıyor. Bu overfitting'e karşı çok güçlü bir koruma sağlıyor.