• Coursera’daki Accelerated Computer Science kurs serisinin, ucuncu dersi Underordered Data Structures, ikinci haftasiyla devam. Bu hafta, baglamini henuz pek cozemedigim disjoint sets veri yapisi ile ugrastik. Anladiigm kadariyla onumuzdeki haftalarda graf yapilari icin epey bir isimize yarayacak.

    • Temelde birbirinden ayrik verileri bir arada tuttugumuz ve her bir kumeyi temsilen de o kumeden bir eleman atadigimiz yapilar. Ornegin {1,2,3} ve {4,5} gibi iki disjoint set olsun elimizde, ilkini 1 ile digerini de 4 ile adresleyebiliriz. Mesela 5 elemanini aradigimizda sonuc olarak 5’in dahil oldugu kumeyi temsil eden 4 elemanini donduruyoruz. Fakat bu sekilde adresleme, eleman arama (find) ve bu kumeler arasinda birlesim (union) icin pek etkili degil.

    • Onun yerine, up tree diye bir ust yapi icinde tutuyoruz eleman olma iliskilerini. Her kume icin bir agac var ve bu agactaki her eleman, en sonunda kumeyi temsil eden elemana baglanacak sekilde yonlu olarak bagli. Ornegin {1,2,3} kumesinde 3]u 2’ye, 2’yi de 1’e ve 1 de en ustte olacak sekilde baglayabiliriz. Sonrasinda yeni bir kumeyi bununla birlestirmek istedigimizde ekleyecegimiz kumenin agacinin yuksekligine gore, en az yukseklige sahip olan agaca, diger agacin root node’unu bagliyoruz, O(1) zamanda birlestirmis olduk. Tabi ararken tree’deki en uzun path’e bagimliyiz.

    • Bunun icin de yapabilecegimiz guzel bir trick, herhangi bir elemani bul dedigimizde tree’yi yukari dogru traverse ederken, root’u bulduktan sonra, uzerinden gectigimiz her bir node’un isaretcisini root olarak belirleyebiliriz. Buna path compression deniyor.

    • Bu implementation sayesinde bir elemana erisimi iterative log zamanina yani O(log n) zamana indirmis oluyoruz. Iterative log, bir sayinin kac kere log’unu alabilecegimiz + 1’i (sayi 1’den buyuk oldugu surece) veren bir ifade. Ornegin O(log 64) = 4. Bu sayede amortised olarak sabit zamanda (O(1)) bir erisime sahip bir veri yapisi elde etmis oldu.

    • Konu sonunda kolay bir quiz vardi, *path compression*i uyguladigimiz. O da asagida:

      #include <iostream>

class DisjointSets {
public:
    int s[256];

    DisjointSets() { for (int i = 0; i < 256; i++) s[i] = -1; }

    int find(int i);
};

int DisjointSets::find(int i) {
if ( s[i] < 0 ) {
    return i;
} else {
    s[i] = find(s[i]);
    return find(s[i]);
}
}

int main() {
DisjointSets d;

d.s[1] = 3;
d.s[3] = 5;
d.s[5] = 7;
d.s[7] = -1;

std::cout << "d.find(3) = " << d.find(3) << std::endl;
std::cout << "d.s(1) = " << d.s[1] << std::endl;
std::cout << "d.s(3) = " << d.s[3] << std::endl;
std::cout << "d.s(5) = " << d.s[5] << std::endl;
std::cout << "d.s(7) = " << d.s[7] << std::endl;

return 0;
}

Output:
d.find(3) = 7
d.s(1) = 3
d.s(3) = 7
d.s(5) = 7
d.s(7) = -1

  • Applied Machine Learning dersinde Linear Model‘lere, siniflandirma yontemleri Logistic Regression (LR) ve Support Vector Machines (SVM) ile devam ediyoruz.

    • Lineer model kullanarak siniflandirma yaptigimizda, temel olarak w ve b olarak tanimlanan model parametrelerini bulmaya calisiyoruz ki bu oarametreler siniflari ayiran bir hyper-plane tanimlasinlar (decision boundry) ve w‘da bu hyper-plane‘in normali olsun. Bu anlamda mantik olarak LR ve SVM’in birbirinden farki yok.

    • LR ve SCM’i birbirinden ayiran sey ise kullandiklari *loss function**‘lar. Aslinda siniflandirma probleminde ideal olarak minimize etmek isteyecegimiz sey, yanlis tahmin ettigimiz sinif sayisi, fakat bunu formule ederken kullanacak indicator function malum, optimize edilmesi cok guc. Onun yerine buna upper-bound olacak, convex fonksiyonlar olan, SMV icin “Hinge Loss”, LR icin “logistic loss (categoric cross entropy)” kullaniyoruz.

    • LR’in 0-1 araliginda sonuc vermesi, dogal bir olasilik dagilimi interpretation’i sagliyor. Bu anlamda model ciktisi p(y|x) ile elimizdeki veri setinin bu model altinda olasiligini maksimize etmeye calisiyoruz seklinde dusunulebilir (maximum likelihood).

    • LR’i l1 ve l2 regularizasyonla kisitlayabiliyoruz. scikit-learn‘de bunu C parametresi ile ayarliyoruz. Fakat buradaki C parametresi linear regresyondan farkli olarak dogrudan regularisation factor‘u vermiyor! Formule bakildiginda, regularizasyon terimini degil de, model loss degerini carptigini goruyoruz. Dolayisiyla aslinda model’i penalize eden bir terim bu. Kisacasi, C‘nin buyuk degerleri, daha az regularizasyona, kucuk degerleri ise daha fazla regularizasyona denk geliyor. Bu cok kritik!

    • Bu derste, regularizasyonun gercek etkisini cok guzel gosteren ornekler vardi. Temelde fikir su: regularizasyon, veri setindeki tekil noktalara ne kadar onem verileceginin bir gostergesi. Eger yuksek tutarsak, tekil noktalarin tek tek buyuk etkisi olmayacak, daha genis kapsamli bir model elde etmis olacagiz; dusuk tutarsak, tek tek her bir noktaya buyuk bir katki verecek ve sonunda her bir noktaya uymaya calisan, cogunlukla “overfit” bir model elde etmis olacagiz.

    • SVM’de yaptigimiz sey, yine iki veri setini birbirinden ayiran “hyper-plane”i bulmaya calisiyoruz; bunu yaparken decision boundry‘yi olustururken, support vektor‘ler yani veri noktalari belirliyoruz ve bunlara uzakliklari maksimize ediyoruz. Gunun sonunda, model tahminini belirleyen seyler bu support vektor‘ler.

    • Regularizasyon ile siniflari birbirinden ayiran margin‘in ne kadar dar ve genis olacagini, veri noktalarinin bu margin icine ne kadar girebilecegini belirliyoruz. Yuksek regularizasyon (dusuk C)‘da margin genis ve iceride veriler olabilirker, dusuk regularizasyon (yuksek C)‘da oldukca dar bir margin olusuyor.

    • SVM ve LR’dan hangisini kullanacagimiz cogu zaman cikti olarak “olasilik” gosterimi isteyip istemedigimize bagli oluyor.

    • Multi-class classification olayi cok asina olmadigim bir durum. scikit-learn‘de bu uc sekilde implement ediliyor: One-versus-Rest (OvR), One-versus-One (OvO) ve Multinomial.

      • One-versus-Rest ile her bir sinifi digerlerine karsi olacak sekilde, kac sinif varsa (n diyelim) o kadar ayri model olusturup, gunun sonunda tahmin ederken en yuksek skora karsilik gelen sinif veriliyor.

      • One-versus-One‘da ise her bir sinif diger her bir sinif ile birebir olacak sekilde ayri model kuruluyor. Dolayisiyla n’in 2’li kombinasyonu kadar model demek bu. Ayrica verinin sadece belirli kismi ile train edebiliyorsunuz. Tahminde, ilgili sinifi kac model tahmin olarak verdigina bakip, bunlar arasinda oylama yapiyoruz.

      • LR icin bir baska secenek de Multinomial yontemini kullanmak. Bununla, skoru verirken her bir sinif icin softmax uygulayip, her bir sinif icin ayri bir olasilik degeri cikti olarak veriliyor.

      • Implement ederken LR’da multi-class opsiyonu ile belirleyebiliyoruz. SVC default olarak OvO kullaniyormus ve bu dogal olarak performansi epey azaltiyor. Bir de SVC’yi probability=True olarak kullanilmasi onerilmiyormus.

    • LR’daki model weight‘lerin degiskenlerin agirlikliklarini estimate etmek icin de kullanildigini gordum (tipki linear regression’daki gibi) link.

    • SVC’yi linear kernel ile kullanmak yerine, ayni isi yapan LinearSVC‘yi kullanmak oneriliyor.

    • Ayrica

      • “LinearSVC, LogisticRegression: dual=False if n_samples >> n_features”
      • LogisticRegression(solver=“sag”) for n_samples large.
      • Stochastic Gradient Descent for n_samples really large

    • SVM’de kernel‘ler linear modellemeden, non-linear decision boundry’ye gecis. Problemin konveksligini koruyor. Aslinda en temelde yaptigi, yeni bir feature space tanimlayip, bir nevi feature engineering.

      • Ornegin, elimizde iki feature olsun x0, x1. Bunlari kullanip uc tane daha yeni feature olusturabiliriz elle: x0^2, x0.x1, x1^2. Benzer donusumu, polynomial kernel kullanarak da olusturabiliyoruz. Kernel ile yeni bir dual uzayda bir inner product tanimliyoruz ve skoru burada elde ediyoruz.

      • Kritik olan, positive-definite ve simetrik kernel fonksiyonlari kullandigimizda elde ettigimiz donusumleri, ilk bastaki feature’lara uygulayarak da elde edeilecegimizin garantisi (fakat bu donusum fonksiyonu) genelde sonsuz boyutlu).

      • Gaussian yapida olan rbf kernel en etkili kernel’lerden biri. gamma parametresini optimize etmek gerek!

    • SVM mevzusunu uzerinden birkac kez daha gecmem gereken, gereginden fazla zor gelen bir kavram oldu hep benim icin. Bu kez uzerinden gecerken, implementation’a dair epey sey ogrendim, o kesin!