Karar Ağacı ve Belirsizlikler

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ıf_i) . log₂p(sınıf_i) = – p(sınıf₁) . log₂p(sınıf₁) – p(sınıf₂) . log₂p(sınıf₂) – … – p(sınıf_n) . log₂p(sınıf_n)

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.

 

Entropi(Karar) =  – p(hayır) . log₂p(hayır) – p(evet) . log₂p(evet) = – (5/14).log₂(5/14) – (9/14).log₂(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.

 

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

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

 

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.

 

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 . log₂x idi. Bu fonksiyonun çarpan x’i payda’ya taşıyacak şekilde yeniden düzenleyelim. Bu değişiklik ifadenin sonucunu değiştirmeyecektir.

x . log₂x = log₂x / (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 log₂x / (1/x)

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

log₂0 / (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 log₂x / (1/x) = (log₂x)’ / (1/x)’ = (log₂x)’ / (x^-1)’

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

(log₂x)’ / (x^-1)’ = [1/(x.ln(2))] / (-x^-2) = [1/(x.ln(2))] / (-1/x²)

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

– x² / x.ln(2)

Pay ve paydaki x’leri sadeleştirebiliriz.

x / ln(2)

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

lim _x->0 x . log₂x = 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 . log₂x ya da daha basit ifade ile (0 . log₂0) 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.

 

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

 

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.