Karar Ağacı ve Belirsizlikler

409

Karar ağacı algoritmaları uygulamalı makine öğrenme çalışmalarının en çok ses getirenlerinden. Öyle ki Kaggle tarafından düzenlenen yarışmaların kazanan çözümlerinin yarısından fazlası karar ağaçlarını kullanmakta. Başarısının yanı sıra bu makine öğrenmesi algoritmalarının benimsenmesinin önemli bir nedeni de verdiği kararların insanlar tarafından anlaşılabilmesi.

En popüler karar ağacı algoritmaları ID3 ve C4.5 bilgi yitimi (entropy) ve bilgi kazancı metrikleri ile veri setindeki en dominant niteliği hesaplamakta. Tipik entropi hesabı karar bilgisi n sınıflı bir veri seti için her sınıfa ait olasılık ve olasılığın logaritma 2 tabanındaki değer ile kümültif olarak çarpılmasıyla hesaplanıyor.

Entropi = – Σ (i=0 to n) p(sınıfi) . log2p(sınıfi) = – p(sınıf1) . log2p(sınıf1) – p(sınıf2) . log2p(sınıf2) – … – p(sınıfn) . log2p(sınıfn)

Formülün anlaşılması için somut bir örnek üzerinde uygulayalım. Örneğin elimizdeki veri seti 14 örneklemden oluşsun ve 5 hayır kararına karşılık 9 evet kararını içersin.

Hava, Sıcaklık, Nem ve Rüzgar nitelikleri için Golf oynama kararı veri seti

 

Entropi(Karar) =  – p(hayır) . log2p(hayır) – p(evet) . log2p(evet) = – (5/14).log2(5/14) – (9/14).log2(9/14)

Günümüzdeki hesaplama gücümüz göz önüne alındığında çokça basit bir hesaplama olacağı belli.

Alt veri kümeleri için entropi

Karar ağacı algoritmaları aç gözlü yaklaşım ile parça ve fethet yöntemini uygularlar. Veri setini ilerleyen adımlarda alt veri setlerine bölerek entropi hesaplamasına devam edilir. Öyle bir noktaya geldiğimizi var sayalım ki alt veri setindeki örneklem 4’e insin ve bunların hepsi de evet kararı olsunlar.

Bir alt küme için tüm örneklemler evet kararına aitse

 

Entropy(Karar) = – p(hayır) . log2p(hayır) – p(evet) . log2p(evet) = – (0/6) . log2(0/6) – (6/6) . log2(6/6) = – 0 . log2(0) – 1 . log2(1)

Burada log2(1) ifadesinin 0’a eşit olduğunu biliyoruz. Ancak asıl problem log2(0) ifadesi çünkü bunun değeri -∞’dur. Sıfır ile sonsuz ifadesinin çarpımı peki nedir?

Logaritma 2 tabanı

 

Hadi bu soruyu python’a soralım.

Bu programı çalıştırdığımızda ValueError: math domain error hatasını alıyorsunuz. Aynı hesaplamayı Java’da denerseniz NaN, excel’de denerseniz ise #NUM! hataları belirmekte.

Python ile sıfır kere eksi sonsuz değerinin hesaplanması

 

Görüldüğü üzere bu işlem programlama dili bağımsız olarak hesaplanamıyor. Peki bu durumda karar ağacı algoritması çalışmayak mı? Peki ya üst seviye programlama dilleri hesaplamasını bilmiyorlarsa?

Programlama dilleri yüksek matematik biliyor mu?

Bizi bu hesaplamada sıkıntıya sokan ifade x . log2x idi. Bu fonksiyonun çarpan x’i payda’ya taşıyacak şekilde yeniden düzenleyelim. Bu değişiklik ifadenin sonucunu değiştirmeyecektir.

x . log2x = log2x / (1/x)

Bu ifadede x, 0’a eşit iken problem yaşamıştık. Fonksiyonun limiti sıfıra yaklaşırken incelememizde fayda olacak.

lim x->0 log2x / (1/x)

Şimdi ifadede x yerine 0 koyduğumuzda ise ∞/∞ belirsizliği ile karşılaşacağız.

log20 / (1/0) = -∞ / (1/0) = – ∞/∞

L’Hospital Kuralı

Lise yıllarına geri dönelim. L’Hospital kuralı belirsizliklerin çözümü için uygulanan bir teoremdi. Konunun ispatı için Nesin Matematik Köyü’ne ait bu müthiş videoyu izlemenizi şiddetle tavsiye ederim.

Limit herhangi bir c noktasına giderken f ve g fonksiyonlarının her ikisi de 0 veya ∞’a eşit ise

lim(x->c) f(x) = lim(x->c) g(x) = 0 (veya ∞)

Bu durumda f bölü g aynı zamanda f fonksiyonun türevi bölü g fonksiyonunun türevine eşittir.

lim(x->c) f(x)/g(x) = lim(x->c) f'(x)/g'(x)

Burada, f ve g fonksiyonlarının c noktasında türevi olması gerekiyor.

Entropi Belirsizliği

Ne tesadüftür ki bizim de problem yaşadığımız ifade ∞/∞ belirsizliğini içeriyordu. Bu durumda L’Hospital kuralını uygulamamıza bir engel bulunmuyor.

lim x->0 log2x / (1/x) = (log2x)’ / (1/x)’ = (log2x)’ / (x-1)’

Burada log2x ifadesinin türevinin 1/(x.ln(2)) olduğunu hatırlayalım. (x-1) ifadesinin türevi de (-1).(x-2) ‘dir.

(log2x)’ / (x-1)’ = [1/(x.ln(2))] / (-x-2) = [1/(x.ln(2))] / (-1/x2)

Paydadaki (-1/x2) ifadesini paya taşıyalım

– x2 / x.ln(2)

Pay ve paydaki x’leri sadeleştirebiliriz.

x / ln(2)

Özetle x / ln(2) ifadesi, lim x->0 x . log2x ifadesine eşittir.

lim x->0 x . log2x = lim x->0 x / ln(2)

ln(2)’nin sabit bir sayı olduğunu zaten biliyoruz. Artık ifadede x yerine 0 koyabiliriz.

lim x->0 x / 0.693 = 0 / 0.693 = 0

Sonuç görüldüğü gibi 0 olacaktır. Bu da demek oluyor ki lim x->0 x . log2x ya da daha basit ifade ile (0 . log20) python, java gibi programlama dillerin hesaplayamadığı gibi belirsiz bir ifade değil 0’a eşittir.

x.log(x) fonksiyonu

Dolayısıyla xlog(x) denklemi [0, +∞) aralığında aşağıda gösterildiği gibi tanımlıdır. Sürpriz bir şekilde fonksiyonun 0 noktasında tanımsız olmadığını ispatlamış olduk.

xlog(x)

 

Bu anlattığım durum karar ağaçlarının inşası sırasında çokça karşılaşılan bir durumdur. Bu problemi ancak calculus kullanarak aşabiliyoruz. Henüz üst seviye programlama dilleri bu hesaplamayı yapacak kadar akıllı değiller. Bu örnekten çıkarım ile programlama dillerinin calculus bilmediğini söylersek yanlış olmayacaktır.

Skynet

Skynet, Terminator

 

Katil robotlar ve bir çeşit şeytani yapay zeka tarafından insan hegemonyasının devir alınması senaryosunu tekrar düşünmenizde fayda var. Sahip oldukları derleyiciler basit bir matematik işlemini bile uygulamaktan aciz. Yer yüzündeki en vahşi avcıların hiç biri, katil balina, aslan, büyük beyaz köpek balığı, sibirya kaplanı ve katil kobranın, sayı saymayı bile bilmemekte (Alper Özpınar). Ama bu türlerin hiç biri insan hegemonyasını devir alabilmiş değiller. Kaba kuvvet kimseyi besin zincirinin tepesine çıkarmayacaktır.

Bu yazı Indeterminate Forms and L’Hospital Rule in Decision Trees yazısından Türkçe’ye çevrilmiştir.

Yorum yaz

Email adresiniz yayınlanmayacaktır.