Monday, September 15, 2014

Python Profilleme (Profiling)

sudo pip install line_profiler

Komut satirindan isletmek

import time

@profile
def f():
    for i in range(100): print i
    g()
  
def g():
    time.sleep(1)

if __name__ == "__main__":
 f()


Komut satirinda

python -m kernprof -l -v test.py > /tmp/prof1.txt

Sonuc

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     3                                           @profile
     4                                          
     5                                           def f():
     6       101          233      2.3      0.0      for i in range(100): print i
     7         1      1001139 1001139.0    100.0      g()

 

Sonuca bakarsak zamanin yuzde yuzunun g() icinde gecirildigini goruyoruz. Bu normal cunku icinde sleep ibaresi var! Hits bu satirin kac kez isletildigini gosterir, time bu satirda toplam ne kadar zaman gecirildigini gosterir. Per hit satirin her isletildiginde ne kadar zaman harcandigini belirtir. Yuzde ise tum isletim icinde bu satirda yuzde kac zaman harcandigini belirtir.

Not: Eger  ustteki kodu python test.py olarak isletirseniz @profile dekoratorunun import edilmedigi hakkinda sikayet gelecektir.

Bir diger yontem, (sudo pip install profilehooks yaptiktan sonra),

from profilehooks import profile

ile dekaratoru import etmek. O zaman normal komut satirindan python test.py ile isletim olur. Ya da herhangi bir sekilde kod isletimi olur, mesela Flask icinden yuklenip ayni kodun isletilmesi gibi. Bu durumda sonuc raporlari bu modulu import eden surec "bir sekilde bittigi" zaman ekrana basilir.

Bizim tercihimiz ilk gosterilen secenek. Calisma seklimiz soyle: sonuclara bakip, duzeltme yapiyoruz, tekrar isletiyoruz, daha sonra @profile dekatorunu kod icinde cagrim zinciri acisindan daha derin noktalara koyuyoruz, mesela a ->b -> c cagrimi var, a ile basliyoruz, sonra dekorator b, c uzerine konanabiliyor. Ilk yontemin onemli bir avantaji sonuclarin bir dosyaya hemen yazilabiliyor olmasi.

Bu profilleme yontemi "satir profillemesi (line profiler)" olarak biliniyor.

Wednesday, September 10, 2014

Numba, LLVM, ve SVD

Numerik hesaplarda, ya da diger konularda Python nasil daha hizli isletilir? Numpy durumunda tum islemleri matrisler, ve kutuphane cagrilari uzerinden olacak sekilde yapmak bu hizli isletimin bir yolu. Bu durumda mesela pur Python dongulerinden kacinilir. Fakat illa dongu kullanilacaksa ve pur Python tipleri kullanilacaksa, Cython hizlandirma yapmanin yollarindan biri. Ya da Continuum tarafindan gelistirilen Numba.

http://numba.pydata.org

Kurmak icin

apt-get install llvm-dev
pip install llvmpy


Numba ile dekorator kullanarak Python kodumuzun belli kisimlarini LLVM uzerinden isletilebilmesini sagliyoruz. LLVM'i isledik, son zamanlarda cok populer bir yaklasim, bir tur sanal kod isleticisi + derleyici alet cantasi + araclari birlesimi.

Ilk ornek

Ornekte goruldugu gibi bir metot @jit ile isaretlenirse, hizli olarak isletilebilir. Eger @jit(nopython=True) secilirse bu hizli yerel mod demektir, bu durumda Python API cagrilari yapilamaz, nopython=False ile obje moduna gireriz.

Ogrendigimiz bazi dersler (Numba 0.13.2 uzerinden edinilen bilgiler): 

Projemizde ogrendik ki obje modu digerine nazaran cok daha yavastir, yerel mod tavsiye edilir. Yerel modda sadece temel tipler ve Numpy matrisleri  / vektorleri kullanilabilir.

Bazen bir dongude kullandiginiz bir degiskeni tekrar mesela baska bir dongude kullanamiyorsunuz (bir acaiplik aslinda, bir hata dogal olarak). Mesela for i in range(..) sonrasi tekrar for i in range(...) yapamamak.. Eger problem cikarsa sac yolmak yerine nereden kaynaklandigini bilmek faydali olabilir :) Bu yuzden emin olmak icin bir fonksiyon icinde hep degisik indis ismi kullanmak en iyisi.

Yerel modda fonksiyona disaridan gecilen ya da fonsiyon icinde yaratilan vektorlerin icerigini vektorsel / toptan erisim ile degistiremiyorsunuz (yani tum bir satirin icerigini degistirebilmek gibi mesela). Sadece tekil oge (element) degisimi yapabiliyorsunuz. Bu demektir ki indisler yaratip, for donguleri uzerinde vs. ogelere erisip onlari degistirebiliyorsunuz. Simdi bu bir yetenegi kazanip digerini kaybetmek demek oluyor, ne guzel tam np.dot(...) yapabiliyorken birdenbire onu kaybediyoruz! Bu dogru.. Tabii diger yandan for donguleri artik dehset hizli isleyecek (cunku Numba icindeyiz), fakat bir kolayligi kaybetmek te ufak bir dezavantaj, evet. Not: Ustteki durum obje modunda problem degil, ama obje modu daha once soyledigimiz gibi cok daha yavas.

Seyrek matrisler nasil islenir? Dikkat, jit ile isaretlenmis fonksiyonlar seyrek matris objeleri alamazlar, sadece Numpy matrisleri ve vektorleri gonderebiliriz. O zaman seyrek matris icinden "sifir olmayan" tum degerlerini surekli bir vektor olarak almaliyiz, mesela altta bir seyrek matrisin tum degerlerini toplayan bir fonksiyon,

from numba import jit
import numpy as np
from scipy.sparse import coo_matrix, lil_matrix

@jit
def sum(A_rows, A_cols, A_data):
    res = 0.
    for j in range(len(A_data)):
        u = A_rows[j]
        i = A_cols[j]
        res += A_data[j]
    return res

A = lil_matrix([[3,4,5,5],
                [5,4,5,0],
                [0,0,0,0]])

print A
A = coo_matrix(A)
print sum(A.row, A.col, A.data.astype(np.float32))


Indisler u ve i icinde baktigimiz degerin satir ve kolon indislerini elde edebiliyoruz. Ustteki ornekte bu lazim degildi ama alinabilecegini gostermek icin ekledik. Not: ufak bir ornek oldugu icin hiz farki gorulmeyebilir, ama alttaki gibi cagrilirsa fark kesinlikle gorulecektir,

k = 3000
A = coo_matrix(np.random.randint(2, size=(k,k)))
print sum(A.row, A.col, A.data.astype(np.float32))


Bir ornek daha, SVD kodlamasinin Numba ile yapilmis halini gorelim. Not: Alttaki gibi bir SVD kodlamasinin, bu arada, piyasadaki neredeyse tum diger SVD kodlamalarindan farkli oldugunu belirtelim, olmayan degerleri olmayan deger olarak kabul ediyor yani onlari atliyor. Bu bir "matris tamamlama" problemidir, ki tavsiye algoritmalari icin ozellikle bu yaklasim gerekir. Paket SVD'lerin cogu (ki buna scipy svds, sparsesvd paketleri dahil) olmayan degerleri "sifir" kabul ediyor, bu biraz farkli bir problem kabul edilir. Konu hakkinda D. Gleich adli profosorun bir blog yazisi surada.

import numpy as np
from scipy.sparse import coo_matrix
from numba import jit

@jit(nopython=True)
def pred(u, i, P, Q):
    dot = 0.
    for f in range(P.shape[1]):
        dot += P[u, f] * Q[i, f]
    return dot

@jit
def sgd_mult(rows, cols, vals, P, Q, gam, rlam):

    q = np.empty(Q.shape[1]).astype(np.float32)
    p = np.empty(P.shape[1]).astype(np.float32)

    for j in range(len(vals)):
        u = rows[j]
        i = cols[j]
        value = vals[j]

        dev = value - pred(u, i, P, Q)

        for r in range(Q.shape[1]):
            q[r] = gam * (P[u, r]* dev - rlam*Q[i, r])
            p[r] = gam * (Q[i, r]* dev - rlam*P[u, r])

        for l in range(Q.shape[1]):
            Q[i, l] += q[l]
            P[u, l] += p[l]


def svds(A, k, it=20, rlam=0.1, gam=0.1):
    P = 1./k * np.random.randn(A.shape[0], k).astype(np.float32)
    Q = 1./k * np.random.randn(A.shape[1], k).astype(np.float32)

    for it in range(it):
        sgd_mult(A.row, A.col, A.data.astype(np.float32), P, Q, gam, rlam)

    return P, Q.T

@jit(nopython=True)
def rmse(rows, cols, vals, P, Q):
    dev = 0.

    for j in range(len(vals)):
        u = rows[j]
        i = cols[j]
        val = vals[j]

        dev += (val - pred(u, i, P, Q))**2

    return np.sqrt(dev/len(rows))


Gradyan Destekli Regresyon Agaclari (Gradient Boosted Regression Trees -GBRT-)

Yapay Ogrenimde agac teknigini ilerleten yaklasimlardan biri: bu arada artik kimse tek agac egitmiyor (mesela ID3'te oldugu gibi), Rasgele Ormanlar (Random Forests) tekniginde pek cok agac, degisik kolon altgruplari uzerinde egitilir, ya da diger teknikler diger sekillerde cok agacli ortamda is gorur.

GBRT ile her agac bir once egitilen agacin egitim verisindeki etiketleri tahmin etmekteki hatasi uzerinde (on the residuals) egitilir, yani onceki agacin hatalari bir nevi yeni etiketler haline gelir. Bu niye yapilir? Boylece takip eden yeni agaclarin onceki agaclarin hatalarini "duzeltebilecegi" ongorulur.

Konu hakkinda kaynaklar

http://www.slideshare.net/DataRobot/gradient-boosted-regression-trees-in-scikitlearn

GBRT icin en iyi kod

https://github.com/tqchen/xgboost

Kod C++ ile yazilmistir ve hizli islemektedir. Bizim icin en onemli ozelligi scipy kutuphanesinin seyrek matris formatlari ile calisabilmesi (kiyasla scikit-learn kutuphanesindeki mesela rasgele orman algoritmasi bunu yapmamiza izin vermiyor). Kurmak icin unzip, xgboost altinda make yeterli. Ornek olarak xgboost/demo/binary_classification altinda sh runexp.sh ile ornek kod isletebilirsiniz. Kod isledikten sonra sonuc dump.raw.txt icinde, oge isimleri ise featmap.txt icinde. Mesela

0    cap-shape=bell    i
1    cap-shape=conical    i
2    cap-shape=convex    i
3    cap-shape=flat    i
..


Eger numerik bir oge var ise, bu oge "i" yerine "q" ile isaretlenir. GBRT algoritmasi ikisel degerlerle oldugu gibi numerik degerlerle de gayet guzel (ve ayni anda) calisabilir. Mesela numerik boy ogesi secilmis ise agac mesela 160'dan kucuk olma / olmama sarti uzerinden bir dallanma yaratmis olabilir. Bu numerik degerin hangi noktasindan bolunecegi de dal yaratma karar mekanizmasinin bir parcasidir.

https://github.com/tqchen/xgboost/wiki/Binary-Classification

https://archive.ics.uci.edu/ml/datasets/Mushroom

Makina ogreniminde metotlarin hiperparametreleri ile oynanir, en optimal olani bulunmaya ugrasilir, mesela KMeans ile bu kume sayisidir, xgbrt ile, ya da herhangi bir agac algoritmasi icin "agac derinligi" bu parametrelerden biri. Bu derinligi bst:max_depth parametresi kontrol eder. Bir digeri, ozellikle xgbrt icin, "kac tane agac olacagi" parametresi (altta num_round). Ornek bazi ayarlar altta,

num_round = 10
param = {}
param['scale_pos_weight'] = 10.
param['bst:eta'] = 0.4
param['bst:max_depth'] = 3
param['eval_metric'] = 'auc'
param['bst:nthread'] = 4
param['silent'] = 1

bst = xgb.train( param, [egitim verisi], num_round, [....] )

Parametre scale_pos_weight ile eger 1 etiketi 0 etiketinden cok daha az ise, bunu dengelemek icin 1'lerin onemini suni olarak arttirabilme sansini elde ediyoruz.

Simdi bazi taklalara gelelim: biz bir proje icin bu kodun icinde bazi degisiklikler yaptik. Mesela eger 1. seviyede isminde vs metni olan ogeler olsun, 2. seviyede sunlar, 3. seviyede sunlar olsun gibi bazi ek kurallar gerekirse, bunlari kodun icine sokusturmak mumkundur. Bu tur kolon kurallari icin xgboost/booster/tree/xgboost_col_treemaker.hpp icinde, tum #include ibarelerinden sonra,

#include <iostream>
#include <sstream>
#include <string>
#include <fstream>
#include <vector>
#include <map>
using namespace std;

typedef std::map<std::string, std::string> TStrStrMap;
typedef std::pair<std::string, std::string> TStrStrPair;

TStrStrMap create_map()
{
    TStrStrMap tMap;

    ifstream infile("[DIZIN]/featmap.txt");

    string line = "";
    vector<string> all_words;
    while (getline(infile, line))
    {
        stringstream strstr(line);
        string word = "";
        int i = 0; string key; string val;
        while (getline(strstr,word, '\t'))
        {
          if (i == 0) key = word;
          if (i == 1) val = word;
          i++;
        }
        if (val.find("[filan]") != std::string::npos) {
          tMap.insert(TStrStrPair(key, "[filan]"));
        }
        else if (val.find("[falan]") != std::string::npos) {
          tMap.insert(TStrStrPair(key, "[falan]"));
        }
        else if (val.find("[fisman]") != std::string::npos) {
          tMap.insert(TStrStrPair(key, "[fisman]"));
        }

    }

    return tMap;
}

Daha sonra FindSplit() metodu icinde

for( unsigned i = 0; i < nsize; ++ i ){
   const unsigned fid = feat_index[i];


dongusu icinde

if (depth == 0 && tMap[std::to_string(fid)] !=      "[falan]") continue;
else if (depth == 1 && tMap[std::to_string(fid)] != "[filan]") continue;
...


eklenir. Ne yapmis olduk? Ilk once, en basta featmap.txt icindeki oge isimlerini aldik. Bu oge isimlerini taradik, ve icinde belli bir metni tasiyanlari bir map uzerine koyduk, bu baslangica sahiptir diye isaretlemis olduk. Daha sonra agac algoritmasinin bolme noktasi arayan algoritmasina kod sokusturduk, burada dedik ki, mesela ilk seviyede sadece "falan" etiketi tasiyan kolonu bolmek icin kullan, yani agacin bu seviyesinde sadece o tur kolonlari kullanabilirsin kurali getirdik. 

Bu sayede diyoruz ki, mesela elde bir musteri kaydi var diyelim, ve bu kayitlarda lokasyana ait bilgiler belli kolonlarda, finansla alakali bilgiler diger kolonlarda (ve yine diyelim ki bu kolonlarin isminde bu farkliligi isaretledik, "lokasyon_" ya da "finans_" gibi..), ustteki gibi bir degisiklik ile agacin ilk seviyesi lokasyon, ikincisi finans, ucuncusu vs. kolon tipinde olsun gibi bir yonlendirmeyi ekleyebiliriz.

Ustteki degisiklikleri derlemek icin hem ana xgboost dizini hem de xgboost/python altindaki Makefile dosyasina girip export CFLAGS listesine  -std=c++11 eklemeniz lazim, cunku bizim ek kodlar yeni C++ standardindaki bazi yenilikleri kullaniyor (to_string metodu gibi). 

Wednesday, September 3, 2014

Esle / Indirge Anlatimi (Map / Reduce)


Bu da isin esprili tarafi

Monday, September 1, 2014

Pig ve Spark

Apache Spark Buyuk Veri dunyasinda Hadoop'un yerine gecmeye talip. Spark Hadoop'un disk bazli esle / indirge mimarisi yerine hafiza bazli transform ve aksiyon mimarisi getiriyor ve bu urune en son ek Hadoop'ta iyi bilinen Pig dilinin aktarilmasi [link].

Bu buyuk bir haber: Pig dilini isledik, bu dil mesela birlestirim (JOIN) yapilmasini saglayan komutlara sahipti, Hadoop versiyonu diyelim ki JOIN komutunu aldiginda bunu arka planda pek cok makinaya esle / indirge progamciklari olarak tercume ediyordu. Bu sayede 100 GB'lik bir dosyayi bir diger 100 GB'lik dosyaya birlestirebiliyorsunuz (bu islemi tek makinalik RDBMS uzerinde yapmanin ne kadar zor oldugunu tahmin edebiliriz). Buyuk Veri dunyasi genelde denormalize edilmis (surekli tekrar edilen) veri ile is yapsa da bazen JOIN'e ihtiyac olur.

Yani simdi ayni dili (Pig) kullanarak arka planda Spark'a is yaptirmak, Spark'a Pig sonuclarini aktarip, ya da oradan veri almak kolay olacak. 

Pig Spark surumu daha cok yeni, su anda Spork adi altinda gelismeye devam ediyor

https://github.com/sigmoidanalytics/spork/