Boosting Nedir? Adım Adım AdaBoost Algoritması
Bu yazıda bir önceki yazımda bahsettiğim Kolektif Öğrenme (Ensemble Learning) yöntemlerinden boosting nasıl çalışılır ve boosting yöntemlerden AdaBoost algoritmasınin gerçek bir problemde eğitim kümesi üzerinde nasıl eğitildiğinin matematiğini ve kodlamasını anlatmaya çalışacağım.
Boosting Nedir?
Boosting (Arttırma), bir çok zayıf öğreniciyi (weak learner) bir araya getirerek bir güçlü öğrenici (strong learner) oluşturmaktır. Bir çok boosting metodunun temel yaklaşımı, tahmin edicileri kümülatif olarak eğitmektir. Genelde tahminleyici model olarak karar ağaçları kullanılır. Her ağaç orijinal bir veri kümesinin değiştirilmiş bir versiyonu ile eğitilir ve sonunda güçlü bir sınıflandırıcı oluşturulur. En sık kullanılan boosting modelleri: AdaBoost (1995, Y. Freund), Gradient Boosting (2001, Friedman), XGBoost (2016, Washington Ünv.), LightGBM (2017, Microsoft) ve CatBoost (2018, Yandex).
AdaBoost
AdaBoost, ilk boosting algoritması olarak sayılır ve bilgisayar dünyasında önemli ödüllerden biri olan Gödel ödülünü kazanmıştır. Bu modelde eğitim kümesi önce bir zayıf öğrenici ile eğitilir. Eğitim sonrası yanlış olarak tahminlenen örnekler bu algoritma için önemlidir. Bir sonraki eğitimde ilk tahminlemede yanlış öğrenilen eğitim verilerine daha fazla öncelik verilerek yani ağırlıkları artırarak tekrar eğitilir.
Bu şekilde zayıf öğrenici çıkışı diğer öğreniciye giriş olacak şekilde eğitilerek devam edilir ve en sonunda sonuçlar birleştirilerek nihai karar sınırları oluşturulur.
Eğitim kümesinden eğitilmiş maksimum derinliğe sahip karar ağaçları kullanılmaz. Bunun yerine zayıf öğrenici olarak AdaBoost ile bir nod ve iki yapraktan oluşan derinliği bir olan karar ağaçları kullanılır. Kümülatif bir yapı olduğu için sıralama önemlidir. İlk karar ağacının yaptığı hata, ikinci ağacın ağırlıklarını etkiler. Bagging yönteminin aksine parelel bir hesaplama yapmaz bunun yerine ardışık bir hesaplama yapılır.
Örnek Problem: Gaussian dağılımı ile üretilen 12 adet, 2 boyutlu ve 2 sınıflı bir veri kümesi üzerinde Adaboost algoritmasının kodlanması ve matematiğine bakmaya çalışalım. Veri kümesini üreten kod parçacığı aşağıdaki gibidir.
from sklearn.datasets import make_gaussian_quantiles
# 2 farkli gaussian dagilimi ile data uretimi
X1, y1 = make_gaussian_quantiles(cov=2., n_samples=6, n_features=2, n_classes=2, random_state=16)X2, y2 = make_gaussian_quantiles(mean=(3, 3), cov=1.5, n_samples=6, n_features=2, n_classes=2, random_state=16)# 2 kolonu birlestirme, 2 boyutlu 12 adet veri elde edilir
X = np.concatenate((X1, X2))# Etiket bilgilerini birlestirme
y = np.concatenate((y1, - y2 + 1))
Üretilen sentetik veri aşağıdaki gibidir:
Karar ağaçları veri kümesinin tüm boyutlarına ve etiket bilgilerine tek tek bakarak ve veri kümesini en iyi bölecek şekilde ağaç yapısı kurar. Bu yapıyı kurar iken entropi denilen belirsizlik ölçütü ile bulunur. Bilgi kazancı en çok olan öznitelik ağaçın en üsütünde konumlanır.
Entropiyi bulan bilim adamı Shannon’dur. Shannon’a göre entropi, iletilen bir mesajın taşıdığı bilginin beklenen değeridir. Diğer bir deyişle entropi düzensizlik olarak tanımlanabilir. Minumum düzensizlikte maksimum bilgi kazancı vardır. O zaman bizim örneğimizdeki en minumum entropiye sahip değeri bulabilirsek belirsizlik azalacak ve karar ağacının en fazla bilgi değerini taşıyan kök node değerini belirlemiş oluruz. Karar ağaçlarında bu belirleme her iterasyonda kümeyi azaltarak requirsive olarak tekrar tekrar entropi yani bilgi kazancı hesaplanarak maksimum derinlikli ağaçlar elde edilir.
AdaBoost Algoritması:
Yukarıdaki algoritma 3 adımı problemimize uygulamaya çalışalım. Problemizde adaboost algoritması için toplam 4 adet zayıf öğrenici (karar ağacı) kullanacağız.
1.Adımda: Başlangıcta tüm örneklerin ağırlıkları 1/N (N=Örnek sayısı) olarak atanır.
1/12 olarak tüm noktaların ağırlık(weight) değeri olur.
2. Adımda: Karar ağacı sayısı(M = 4) kadar bir döngü ile modeller örneklerin ağırlıkları kullanarak eğitilir daha sonra modellerin yani karar ağaçlarının α degerleri, hata oranı ve örneklerin yeni ağırlık hesaplaması yapılır. Adım adım bu işlemleri yapalım:
2.a) Örneklerin ağırlıkları ile zayıf karar ağaçlarının oluşturulması
Örneklerimizi 2 boyutlu uzayda gösterelim ve 1. karar ağacı için minumum entropiye sahip ilk node değerini hesaplayalım. Ağaçlar maksimum 1 derinlikte olmalıdır.
X ekseni için:
Öncelikli olarak x ekseni yani 1. sütün üzerinden en iyi karar sınırını ağaçın kök node değerini hesaplamak için ara noktalarından yani yatay eksende tarama yapılarak entropi hesaplamalıyız.
X eksenlerine göre sıralarsak:
-1.74725, -1.25716, -1.11284, -1.07036, -0.84070, 0.18094, 1.48683, 1.91126, 2.03625, 2.07303, 2.27192, 3.15670
Elimizde 12 nokta var ve bu noktalara ait 11 adet her bir iki noktanın tam ortasındaki noktalar bulunur.
(-1.74725 + -1.25716)/2 = -1.50220
( -1.25716 + -1.11284 )/2 = -1.18500
(-1.11284 + -1.07036)/2 = -1.09160
(-1.07036 + -0.84070)/2 = -0.95553
(-0.84070 + 0.18094)/2= -0.32988
(0.18094 + 1.48683)/2 = 0.83388
( 1.48683 + 1.91126 )/2 = 0.169905
(1.91126 + 2.03625)/2 = 0.197376
(2.03625 + 2.07303)/2 = 0.205464
( 2.07303 + 2.27192)/2 = 0.217248
(2.27192 + 3.15670)/2 =0.271431
Bu orta noktalardan aşağıdaki entropi förmülünü ve yaprakların olasılıklarınıda dahil ederek bilgi değerlerini hesaplamamız gerekemektedir.
Yukarıdakine benzer şekilde diğer X eksenindeki 10 orta nokta için de bilgi değeri hesaplanır. X eksenindeki en küçük bilgi değeri bizim için karar sınırı yani ağacın en iyi bölündüğü değer olacaktır.
Y ekseni için:
Y ekseni yani 2. sütün üzerinden en iyi karar sınırını ağaçın kök node değerini hesaplamak için ara noktalarından yani dikey eksende tarama yapılarak aynı şekilde entropi ve bilgi değerlerini yukarıdaki gibi hesaplamalıyız.
Y eksenindeki noktalar küçükten büyüğe doğru sıralanmalı:
- -2.16159, -0.87875, 0.09381, 0.16793, 0.69773, 0.70557, 1.12801, 2.23898, 3.08124, 3.14543, 3.60425, 3.61104
Sıralanan 12 ardışıl noktaların orta noktaları bulunur. Elimizde 11 adet orta nokta için bilgi değerleri yukarıdaki X eksenindeki gibi aynı şekilde hesaplanır.
En küçük X veya Y noktalarındaki bilgi değerleri sıralanır ve en küçük bilgi değeri en iyi bilgi kazancını verir. Yani X ekseninde -1.18500 noktası en iyi bölünme noktası olacaktır. Oluşan karar ağacı aşağıdaki gibi olacaktır.
Oluşan karar ağacı:
Sol kısımda 2 örnek, sağ kısımda 10 örnekli ve X = -1.185 noktasından bölünmüş(kök değer) olur. Problemiz regresyon olursa yapraklardaki değerler örneklerin ortalamaları alınarak, problemiz sınıflandırma olur ise en çok hangi sınıftan var ise yaprak değeri o sınıf etiketi olur.
2.b) Oluşan karar ağacına göre hata değerinin hesaplanması
Yukarıdaki karar sınırlarına bakılırsa 4 kırmızı etiketli örnek mavi olarak yanlış tanınmıştır. Yukarıdaki formüle uygulanılırsa:
Hata = (1/12+1/12+1/12+1/12) / 12*1/12 = 4 / 12
2.c) Oluşan hata değerine göre alfa değerinin hesaplanması
Yukarıdaki denkleme göre karar ağacının alfa değeri hesaplanırsa.
α = ln((1–(4/12))/(4/12)) = 0.693147
2.d) Örneklerin yeni ağırlıklarının hesaplaması
Hata yapan tüm örneklerin ağırlıkları yeniden hesaplanır.
Wyeni= 1/12 * exp(0.693147) = 0.1666
Yani yanlış tahmin edilen noktaların 1/12 (0.0833) olan ağırlığı 0.1666'ya çıkarılmış oldu.
Bu şekilde bu örnekte toplamda 4 ağaç kullanacağımız için 4 kere 2. adımdaki işlemler hesaplanır. Her bir karar ağacının alfa değerleri ve örneklerin yeni ağırlıkları hesaplanır.
3. Çıkış değeri hesaplama
Örneklerin çıkış değerini yani etiket bilgisini hesaplamak için 4 karar ağacının hesaplanan alfa değerileri ile ilgili ağaçtaki karar değerleri çarpılır ve bu sonuçların toplamları alınarak işaret fonksiyonundan geçirilerek etiketler bulunur.
Böylece problemimizde hesaplanan 4 ağacın kümülatif karar sınırları aşağıdaki gibi olur.
Yukarıda görüldüğü gibi 12 adet eğitim verisi ile 4 karar ağacı eğitilmiş ve tüm örnekler doğru şekilde karar sınırları içerisine alınmıştır. Test için yeni gelen örnekler tahminlenmek istendiğinde, karar ağaçlarının alfa değerleri ve sonuçları kullanılarak test örnekleri doğru karar bölgelerine düşürülecek ve etiket bilgileri tahminlemiş olacaktır.
Bu çalışmanın Python kodları:
import numpy as np
import matplotlib.pyplot as plt
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_gaussian_quantiles
X1, y1 = make_gaussian_quantiles(cov=2.,
n_samples=6, n_features=2,
n_classes=2, random_state=16)
X2, y2 = make_gaussian_quantiles(mean=(3, 3), cov=1.5,
n_samples=6, n_features=2,
n_classes=2, random_state=16)
X = np.concatenate((X1, X2))
y = np.concatenate((y1, - y2 + 1))
bdt = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1), n_estimators=4)
bdt.fit(X, y)
plot_colors = "br"
plot_step = 0.02
class_names = "AB"
plt.figure(figsize=(5, 5))
plt.subplot(111)
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step), np.arange(y_min, y_max, plot_step))
Z = bdt.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
cs = plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)
plt.axis("tight")
for i, n, c in zip(range(2), class_names, plot_colors):
idx = np.where(y == i)
plt.scatter(X[idx, 0], X[idx, 1],
c=c, cmap=plt.cm.Paired,
s=60, edgecolor='k',
label="Sınıf %s" % n)
plt.xlim(x_min, x_max)
plt.ylim(y_min, y_max)
plt.legend(loc='lower right')
plt.xlabel('x')
plt.ylabel('y')
plt.title('Karar Sınırları')
plt.tight_layout()
plt.subplots_adjust(wspace=0.35)
plt.show()Bu yazıda boosting algoritmalarının ilki ve temeli olan AdaBoost algoritmasını örnek bir problemde, matematiği ile beraber anlatmaya çalıştım. Sonraki yazılarda diğer boosting algoritmalarını anlatmaya çalışacağım.
Teşekkürler.
