Boosting Algoritmaları Nasıl Çalışır?
Görsel bir anlatım denemesi
Eğer Kaggle yarışmalarını takip ediyorsanız, “structured data” sınıfındaki yarışmaları büyük oranda boosting algoritmalarının kazandığını farketmişsinizdir. Bu yazımda boosting algoritmalarının nasıl çalıştığını ve gücünün nereden geldiğini görsel olarak ve basit bir şekilde anlatmaya çalışacağım.
Genel prensip olarak boosting algoritmaları her iterasyonda elde edilen zayıf öğrenicileri (weak learner), belli kurallar çerçevesinde birleştirerek güçlü bir öğrenici (strong learner) elde etmeye çalışır. Bunun ne demek olduğunu önce Adaboost algoritması üstünden bir sınıflandırma probleminde gösterelim. Ardından da Gradient Boosting ile bir regresyon problemine bakacağız.
Burada paylaşılan grafik ya da kodları detaylı olarak incelemek ve denemeler yapmak isterseniz github üzerinden hepsine ulaşabilirsiniz.
ADABOOST
1996 yılında Robert Schapire ve Yoav Freund tarafından geliştirilen Adaboost, ilk başarılı boosting algoritması olarak prestijli Gödel ödülünü kazanmıştır.
Elimizde soldaki şekilde mavi ve kırmızı noktaları ayırmaya çalıştığımız bir sınıflandırma (classification) problemi olduğunu varsayalım.
Görselleştirebildiğimizde çözüm çok kolay görünüyor ancak çoğu zaman bu şekilde 2 boyutlu görselleştirilebilen bir veri ile uğraşma şansımız olmuyor.
Algoritma bütün noktaların eşit ağırlıkta olduğu ilk iterasyonda en iyi çözümünü çizecektir. Bu durumda soldaki şekilde bir ayrım oluşacaktır. Görebileceğiniz üzere sarı ile işaretlediğim 3 nokta yanlış tarafta duruyorlar. Bu sebeple 2. iterasyon için bunların ağırlığını arttırmamız gerekiyor. Ancak nasıl?
1. iterasyonda 7 doğruya karşı 3 hatalı sınıflandırmamız var. Eğer çözümümüzün %50–50 dağılımunda bir sonuca getirmek istersek hatalı sınıflandırdığımız noktaların ağırlığını (doğru adet / yanlış adet) yani (7/3 ≈ 2.33) ile çarpmamız gerekecektir. Hatalı sınıflandırılan 3 noktanın ağırlığını 2.33 yaparsak modelimiz %50–50 ağırlığında olacaktır. 1. iterasyonun sonucunu hafızamıza kaybedip yeni ağırlıklar ile 2. iterasyona gidiyoruz.
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.
Modeli bir kez daha %50–50 eşitliğine getirmek için, sarı ile işaretlenmiş hatalı sınıflandırılan ağırlığını (11/3 ≈ 3.66) ile çarpmamız gerekiyor.
Yeni ağırlıklar ile modelimizi 3. iterasyona götürebiliriz.
3. iterasyonun en iyi çözümü ise soldaki şekilde olmaktadır. Doğru noktaların ağırlığı 19 iken, yanlış sınıflandırılan noktaların ağırlığı 3 olmuştur.
İterasyonlara devam edebiliriz ancak burada sona erdirdiğimizi farzedelim.
Şimdi 3 iterasyonda elde ettiğimiz zayıf öğrenicileri (weak learner) birleştirme aşamasına geldik. Ancak bunu nasıl yapacağız?
ln(doğru/yanlış) formülü bize istediğimiz katsayıları verecek gibi duruyor.
Eğer biraz düşünürsek, eşit sayıda doğru ve yanlış veren bir çözüm bizim işimize yaramayacaktır. ln(1)→0 olduğu için bu isteğimizi karşılıyor.
Doğru sayısı arttıkça formülün katsayısı pozitif sonsuza doğru giderek artacak, bütün sonuçları doğru veren bir çözümün ağırlığı sonsuz olacaktır - ln(∞)→∞.
Doğrudan çok yanlış veren bir model de işimize yarar. Sadece modeli ters çevirmemiz gerekmektedir. Hiç doğru sonuç vermeyen bir modelin ağırlığı ln(0)→-∞ olduğu için negatif sonsuz olacaktır.
Eğer modellerin mavi olarak belirlediği bölgeyi pozitif, kırmızı bölgeyi de negatif olarak değerlendirirsek; 3 iterasyonun sonucunu soldaki şekilde birleştirebiliriz.
Oluşan bölümlerin her bir iterasyonda aldığı değeri, ağırlıkları ile topladığımızda sonuç yavaş yavaş çıkmaya başlıyor. Toplamı pozitif olan bölümleri mavi, negatifleri de kırmızı yaparsak algoritmamızın sonucunu görebiliriz.
Adaboost’un çalışma mantığını gösterdiğimiz bu örnek, görülebileceği üzere elimizdeki problemi harika şekilde çözdü.
Bu örneği oluştururken Udacity Machine Learning Engineer Nanodegree’deki Adaboost öğretiminden yola çıktım. Çözümde 3 iterasyonlu AdaBoostClassifier’ı, maksimum derinliği 1 olan DecisionTreeClassifier ile kullanıyoruz. Kodumuz aşağıdaki gibidir.
Gradient Boosting
Bu algoritma Leo Breiman’ın çalışmaları üstüne kurulmuştur.
Elimizde soldaki şekilde hedef değerleri tahmin etmeye çalıştığımız bir regresyon problemi olduğunu farzedelim.
Gradient Boosting ilk iterasyonda tahminleri üreten bir “F” fonksiyonu oluşturur. Tahminler ile hedef değer arasındaki farkı hesaplar ve bu farklar için de “h” fonksiyonunu oluşturur. İkinci iterasyonda “F” ve “h” fonksiyonlarını birleştirir ve tekrar tahminler ile hedefler arasındaki farkı hesaplar. Bu sayede sürekli üstüne ekleyerek “F” fonksiyonunun başarısını arttırmaya, dolayısıyla da tahminler ile hedefler arasındaki farkı sıfıra indirmeye çalışır.
Aşağıdaki görselde modelin 1. iterasyondaki tahminini soldaki grafikte kırmızı çizgi olarak görebilirsiniz. Her x değeri için tahminler ile hedef değer arasındaki farkı da sağdaki grafikte gösterdim.
İterasyonlar ilerledikçe modelin başarısı artacaktır. Aşağıda 10. iterasyon sonucunda aynı grafiği görebilirsiniz.
25. ve 50. iterasyon sonuçlarında artık modelin tahmin ile hedef farkının sıfıra yaklaştığını görebilirsiniz. Aslında 50. iterasyon sonuçları modelin biraz overfit etmeye başlamış gibi olduğunu gösteriyor. Overfit’i önlemek için ayrı bir validasyon kümesi ile sonuçları karşılaştırmak ve sizin için uygun iterasyon sayısını bulmak faydalı olacaktır.
Tianqi Chen ve Carlos Guestrin tarafından Gradient Boosting mantığı üstüne bazı gelişmiş özelliklerin eklenmesi ile oluşturulmuş olan XGBoost şu anda Kaggle yarışmacılarının en çok kullandığı algoritma olarak ün yapmıştır. Uber, Airbnb, Amazon and Google Cloud gibi şirketlerin bazı ürünlerinde kullanılmaktadır.
