Wednesday, September 20, 2017

Surucusuz Arabalar, Derin Ogrenme

Derin yapay sinir aglari her turlu fonksiyonu temsil edebilirse, ve araba kullanirken insanlarin karar mekanizmasi da boyle bir fonksiyonsa, bir DYSA bu hesap mekanizmasini ornek veriye bakarak bulamaz mi? Egitim verisi yol goruntusu, etiket pedal, direksiyon kontrolu olur, DYSA egitiriz, abrakadabra araba otomatik olarak kullanilmaya baslanir. Surada comma.ai diye bir sirketin kurucusu bu tur bir seyden bahsediyor, genc heyecanli bir arkadas ama buyuk bir ihtimalle yanlis yolda.

Suradaki makale de yanlisligin nerede oldugunu soyluyor. Goruntu ile direksiyon arasinda birebir iliski yok. Bunu tespit ettigimiz anda zaten DYSA'nin niye bu sekilde kullanilamayacagini anliyoruz. YSA fonksiyonlari yaklasik temsil eder demistik. Foksiyon nedir? Matematigin temeli sayi teorisi, sayi teorisinin temeli kume teorisi ise, fonksiyonlarin kumelere dayali tarifini hatirlamak iyi olur, fonksiyon kumeler arasinda coka-bir (many-to-one), ya da bire-bire (one-to-one) esleme yapan bir seydir. Fakat goruntu / direksiyon eslemesi bu tanima uymuyor. Diyelim bir yonu uc seritli olan yolda orta seritte gidiyorum, onumde bir araba var. Bu arabayi soldan gecebilirim, sagdan gecebilirim, yani ayni goruntu iki farkli direksiyon kontrolune eslesmis olur. Egitim verisinde bu tur durumlar muhakkak olacaktir ve DYSA buradan optimal bir sinir agi cikartamayabilir. Daha basit bir ornek, f(x,y)=x+y fonksiyonu, f(3,2)=5 olabilir, f(4,1)=5 olabilir (coka-bir) fakat f(4,1) bazen 5 bazen 15 olamaz. Fakat yine de yeterince veriyle pek cok sartta isleyen bir YSA egitebilirsiniz muhakkak, ama ortaya cikan surucusuz araba ne kadar optimal isler, her turlu ortamda ne kadar guvenilir olur?

Paylastigimiz makale farkli bir secenek veriyor. Yol goruntusunu (input image) kontrol mekanizmasi (driving control) ile degil, arabanin diger arabalara olan mesafesiyle (direct perception) ile esliyorlar. Bu veri farkli sekillerde gelmesi daha zor olan bir veri, birebir esleme olusturmak icin daha uygun. 

Mesafeler elde edildikten sonra isin araba kullanma kismi, gaz, direksiyon kontrolu daha kolay hale gelir, o kisim artik elle kodlanmis bazi kurallarla bile halledilebilir.

Monday, September 18, 2017

Yapay Ogrenme, Danismanlik

Google bugunlerde hizli bir sekilde danismanlik tarafini gelistiriyor, G. teknolojilerini kullanan danismanlar, aynen IT durumunda oldugu gibi, sirketlere gidip YO servisleri sunuyorlar, bu is daha da gelisecek. Google bilindigi gibi derin ogrenme problemlerini cozmek icin TensorFlow'u gelistirdi, bu urun acik yazilim, boylece gelistirici kendini bir sirkete  "baglanmis" hissetmiyor, istedigi zaman kendisi istedigi sekilde kodunu isletebilir, ama Google TF kodlarini paralel, buyuk olcekte isletmek icin bulut servisi hazirlamis, bu sekilde musteri cekiyor. TF kodunu buluta verin, gerekirse 1000 makina uzerinde isletsin. Google TF icin ozel bir cip bile gelistirdi, CPU yerine TPU (tensor processing unit). Bu cipler su anda kendi bulut servisi makinalarinda, ama Android telefonlarinda da gorulmeye baslanir yakinda.

Google danismanlik servislerinde neredeyse her YO problemi icin derin ogrenme kullaniliyor bu arada (SVM, karar agaci vs modasi gecti), optimizasyon gerekirse takviyeli ogrenme (DO bu yaklasimlarin bir parcasi), zaman serileri (siniflama, gelecek tahmini -regresyon-) icin LSTM, ki bu da geriye yayilma (backprop) ile egitilen bir tur yapay sinir agi yaklasimi, ve derin sekilde genisletmek mumkun.

Peki YO sirketlerin ne isine yarar? Yapay sinir aglari bilindigi evrensel yaklasiklayici (universal approximator), herhangi bir foksiyon f(\theta)'yi sadece girdi ve ciktilarina bakarak yaklasik sekilde temsil edebiliyor. Bir anlamda geriye muhendislik yapiyor. Ek olarak derin ogrenme ile ne kadar cok cok veri varsa bu geriye muhendislik o kadar iyi oluyor. 

Tipik bir sirketin her tarafi fonksiyonlarla dolu; mesela "musterilerim sadik degil vs sayida musteri beni her ay terkediyor". Burada bir fonksiyon var, musteri kisisel, aksiyon verisini gir, fonksiyon "terkedecek" diye evet / hayir olasiligi versin. Bu fonksiyon tabii ki bilinmiyor, eger sosyoloji, psikoloij alaninda uzman matematiksel modelciye sorsak, belki bu f(\theta)'yi bulurlar, ama o kadar modelci bulunamaz, zaten bilim o kadar ilerlememis olabilir. Daha hizli sonuc  girdi / ciktilari verip geriye muhendislik, YSA ile f'i bulmak (musteri sadakati icin su arkadas aynen bunu yapmis). Yaklasim ayrica esnek, musteri sadakati f bulmak icin kullanilan benzer metot, is makinasinin ne zaman bozulacagini veren g hesabi icin de kullanilabilir.

Eger f bilinirse sadik olmayacak musteri onceden tahmin edilebilir, onlara donuk kampanya yapilir, o musteri kaybedilmemis olur. 

Yani YO danismanliginin gelecegi cok iyi. Su siralar TensorFlow bilen YO programcilari icin yogun talep var. O zaman tavsiye 1) Python ogrenmeli, hesapsal programlar, veri bilim icin unlu (Matlab'in isi bitti, zaten ticari, gelistiriciler icin bu kisitlayici bir faktor ve o yuzden sevilmiyor ) 2) TensorFlow ile yapay ogrenme saglikli bir sekilde buyuyor.

Su an pur IT danismanligi veren sirketler, YO muhendisleri ile servis yelpazelerini genisletebilirler. Programcilar TensorFlow ile bilgi dagarcigini gelistirebilir.

Not: NVidia GPU kartlari uzerinden derin ogrenmeye bir giris yapmisti, ve gelistiricileri kendine cekme alaninda etkili olmaya cabaliyor, fakat buyuk bir ihtimalle Amazon, Google onlari golgede birakacak. NVidia'nin bulut servisleri yok, sadece grafik karti donanimi ile bilinen bir sirket. Derin YSA altyapi / kodlama ortami secimi onemli cunku hem saglam hem yaygin teknolojiyi kullanmak o teknolojiyi bilen programci bulabilmek, o programcinin is bulabilmesi, programci sorun yasadiginda forumlarda sorusuna cevap verecek kisilerin mevcudiyeti, egitim materyellerinin yayginligina kadar her seye etki ediyor.

Wednesday, September 13, 2017

OpenAI Gym, Pong, Derin Takviyeli Ogrenme (Deep Reinforcement Learning)

Otomatik oyun oynamak ve alakali diger problemler icin son zamanlarda yapay zeka'nin alt dallarindan takviyeli ogrenme (reinforcement learning) revacta. Go sampiyonunu yenen Google Deepmind algoritmasi bir TO yaklasimi kullandi. TO ile algoritma bir oyundan gelen sadece ham pikselleri kullanarak oyunu kendi basina oynamayi ogrenebiliyor. En son oturumda kazanip kaybedildigi bir ceza ya da mukafat skoru ile algoritmaya bildirilir tabii, ve yuzlerce otomatik oyun sonrasi program oynamayi ogrenir.

Takviyeli ogrenim is dunyasi icin faydali olabilir, YZ etrafinda danismanlik servisi veren sirketler eskiden endustriyel muhendisligin semsiyesi altina dusen ve simplex, lineer programlama ile cozulen problemleri TO ile cozmeye basladilar. TO ile bir ilke gradyani (policy gradient) hazirlanir, ilkeler her adimda atilabilecek adimlari tanimlarlar; bir fabrikada bir aletin uzerindeki ayarlar, ya da hangi kaynaklara oncelik verilmesi gerektigi (hangi gun, kac isci, vs), bir anlamda bu ilkelerden gelebilecek aksiyonlar olarak gorulebilir, ve TO en "basarili" olacak ayarlari ogrenebilir.

Oyunlara donelim, simulasyon ortamlarindan OpenAI Gym uzerinden

sudo pip install  gym[atari]

ile unlu oyun Pong ortami kurulur. Oyundan gelen pikseller matris olarak arayuzden alinabiliyor. Alttaki ornekte Pong baslatiyoruz, alinan her kareyi bir imaj png dosyasina yaziyoruz, bu arada rasgele hareketle yapiyoruz, kayip ya da basari var ise donguden cikiyoruz. Her step cagrisi bizim attigimiz bir adimi oyuna bildiriyor, bilgisayar karsilik veriyor, ve oyunun son hali bize step donus parametreleri ile bildiriliyor. Bizim step ile kontrol ettigimiz sagdaki raket, bilgisayar soldakini kontrol ediyor. Pong'u fazla anlatmaya gerek yok herhalde, basit bir oyun, raketler yukari ya da asagi gidiyor, step ile verdigimiz hareket parametresi 0,1 etkisiz, 2,4 yukari, 3,5 asagi demek. Bilgisayar oynarken tabii ki bilgiyi "iceriden" aliyor, diger tahtanin, topun nerede oldugunu ic arayuz ile anliyor. Disaridan piksellere bakarak oynamaya ugrasmak cok daha zor bir is.

import gym, random, time
import pandas as pd
import numpy as np
from PIL import Image

env = gym.make("Pong-v0")
n_outputs = env.action_space.n
print 'kac hereket', n_outputs
env.reset()

# ilk kismi atla
for i in range(20): obs, reward, done, info = env.step(0)

while True:
    obs, reward, done, info = env.step(random.choice([0,1,2,3,4,5]))
    if np.abs(reward) > 0.0: break
    im = Image.fromarray(obs)
    im.save('out.png')
    time.sleep(0.4) # zaman arasi

Imaj kaydi yerine direk ekranda gostermek icin env.render() cagrisi da yapilabilir.


TO baglaminda ogrenim rutini ustteki donguyu yuzlerce, binlerce kez isletebilir, her oturum sonundaki basari / kayip ilke gradyani ile guncelleme icin kullanilir.

Detaylar icin su blog guzel.

Alinan imaj uzerinde bazi onislemler mumkun, mesela en ustteki skor bolumu oyun icin gerekli mi? Bunlar kirpilabilir. Ayrica renk gerekli olmayabilir, 3 renk kanali 1 kanala iner. Kucultme yapilarak 210x160 boyutu mesela 80x80'e indirilebilir. Bir diger onislem su: Karpathy (ustteki baglanti) ardi ardina gelen iki oyun karesinin farkini aliyor, boylece hareket bilgisini yakalamak istemis herhalde. Alternatif bir yaklasim Stanford Universite'sindeki RL dersinin yaklasimi, bu arkadaslar ardi ardina 4 karenin uzerinden bir maxpool hesabi yapiyorlar, yani 4 karede birbirine tekabul eden piksellerden en yuksek degeri olan nihai sonuca aliniyor. Boylece 4 kare 1 kareye indirgeniyor, bu hem hareketi verir, hem de egitim algoritmasinin 4 kat daha hizli islemesini saglar (kod yazinin altinda)


Kontrol Problemleri

Gym sadece gorsel ciktiyla sinirli degil, mesela sadece alttan tutarak dik tutmaya ugrastigimiz bir cubugu dusunelim, bunu belki cocukken yapmisizdir, agir olan dik bir cismi parmak uzerinde tutmaya ugrasmak. Tabii saga sola giderek dengelemeye ugrasilir, oldukca zor bir istir, vs. Gym icinde bu ortam da var,

import gym, time
import numpy as np

env = gym.make("CartPole-v0")
env.reset()
obs, reward, done, info = env.step(0)
print obs
print obs.shape
env.render()

deyince alttaki resim cikar,

Fakat aslinda step cagrilari bize Pong'da oldugu gibi resim degil, cubuk hakkinda 4 tane parametre donduruyor, render cagrisi bu parametreleri kullanarak bir temsili resim ortaya cikartmis. Ustteki durum icin parametreler

[ 0.02585672 -0.17299761  0.030009    0.29081285]

Parametrelerin ne oldugunun detayi surada. Soldan 3. cubugun durus acisi, -45 ile +45 arasinda, arti acilar saga dogru yatik demek, eksiler sola dogru. 

Eger cubugu dengede tutmayi ogrenmek istersek step ile alt kismi saga ya da sola kaydirabiliriz, cubuk sola dusecek gibi olsa mesela sola gidip dengeyi tekrar bulmaya ugrasiriz, vs. Sistem bize hangi durumda oldugunu ustteki 4 sayiyla soyler. Bu yeterli, Pong ile oldugu gibi tum ekrani gormemize gerek yok. Mukafat (ya da ceza) basarili gecen her adim icin verilir, oyun eger cubuk belli bir acidan fazla yatiksa biter, o zaman cubuk "dusmus" demektir. Ekran disina cikmak ayni sekilde oyunu bitirir.

CartPole kontrol problemlerini anlamak acisindan faydali bir ornek.  Kontrol Muhendisligi'nde bu tur durumlar yogun sekilde gorulur. 

Ekler

Pong icin tarif edilen her 4 karede bir imaj veren max pool kodu

import gym

from collections import deque

def greyscale(state):
    state = np.reshape(state, [210, 160, 3]).astype(np.float32)
    state = state[:, :, 0] * 0.299 + state[:, :, 1] * 0.587 + state[:, :, 2] * 0.114
    state = state[35:195]  # crop
    state = state[::2,::2] # downsample by factor of 2
    state = state[:, :, np.newaxis]
    return state.astype(np.uint8)

class MaxAndSkipEnv(gym.Wrapper):
    def __init__(self, env=None, skip=4):
        super(MaxAndSkipEnv, self).__init__(env)
        self._obs_buffer = deque(maxlen=2)
        self._skip       = skip

    def _step(self, action):
        total_reward = 0.0
        done = None
        for _ in range(self._skip):
            obs, reward, done, info = self.env.step(action)
            self._obs_buffer.append(obs)
            total_reward += reward
            if done:
                break

        max_frame = np.max(np.stack(self._obs_buffer), axis=0)
max_frame = greyscale(max_frame)
        return max_frame, total_reward, done, info

    def _reset(self):
        self._obs_buffer.clear()
        obs = self.env.reset()
        self._obs_buffer.append(obs)
        return obs

Kullanmak icin tek bir imaj basalim

from PIL import Image

env = gym.make("Pong-v0")
m = MaxAndSkipEnv(env)
m._reset()
for i in range(20): obs, reward, done, info = env.step(0)
max_frame, total_reward, done, info = m._step(0)
im = Image.fromarray(max_frame[:,:,0], 'L')
im.save('out.png')

Wednesday, September 6, 2017

Meteoroloji Verileri - ECMWF, NOAA

Hava verisi uzerinde yapay ogrenim ile tahminler yapmak isteyenler ham veriyi almak icin alttaki siteye basvurabilir.

https://www.ecmwf.int/

Bu bir Avrupa bilim organizasyonu, ayrica hava tahmini modellerini isletip tahmin de uretiyorlar (Harvey kasirgasinin nereye vuracagini ABD NOAA'dan daha iyi tahmin ettiler). Python ile veri indirmek mumkun, 

sudo pip install ecmwf-api-client

Burada "Register" ile kullanici bilgileri, email, vs. verilip kaydolunur. Bir aktivasyon email'i sonra bir tane daha email geliyor, ve kayit bitiyor.  Login yapilir. Simdi API'ye erismek icin anahtar lazim,


Burada gosterilen 

{
    "url"   : "https://api.ecmwf.int/v1",
    "key"   : "[ANAHTAR]",
    "email" : "[email]"
}

formundaki anahtar $HOME/.ecmwfapirc dosyasina yazilir. 

Verilere erismeden once veri turune gore bazi lisans sayfalarinda bir lisans kabuluna "evet" demek gerekiyor, mesela alttaki tur bir script icin

from ecmwfapi import ECMWFDataServer
   
server = ECMWFDataServer()
   
server.retrieve({
    'dataset' : "tigge",
    'step'    : "24/to/120/by/24",
    'number'  : "all",
    'levtype' : "sl",
    'date'    : "20071001/to/20071003",
    'time'    : "00/12",
    'origin'  : "all",
    'type'    : "pf",
    'param'   : "tp",
    'area'    : "70/-130/30/-60",
    'grid'    : "2/2",
    'target'  : "data.grib"
    })

Su lisansa


evet demis olmak lazim. Bir tane daha


Eger lisans kabul edilmemisse hata mesaji hangi sayfaya gidilecegini soyler.

NOAA

https://www.ncdc.noaa.gov/orders/qclcd/

adresinde gunluk dosyalar var.

Yapay Ogrenim

Hava tahmini icin gunluk (saatlik, vs) hava verisi cok boyutlu bir zaman serisi olarak gorulebilir, mesela her t aninda sicaklik, nem, ruzgar hizi cok boyutlu bir zaman serisi olarak geliyor, egitim icin N tane gorulen veri kullanilir, bu veri N+1, N+2, . anlarindaki gelecek zaman serisini tahmin icin kullanilir. Bu sekilde hava tahmininin ornegi alttaki kodlarda bulunabilir,

https://github.com/mouradmourafiq/tensorflow-lstm-regression/blob/master/lstm_weather.ipynb

Wednesday, June 28, 2017

Disk Temizliği

Arada sırada Ubuntu / Unix'imizde "bahar temizliği" iyi olabilir; ardı ardına kurulan paketler, işletilen programların yarattığı onbellek (cache) dosyaları arkada kalıp diski bitirebilir. Temizlik için bazı programlar:

En basiti komut satırında du,

sudo du -hx --max-depth=1 /

Dizin bazında kullanım raporu verir. Benzer bir raporu görsel araç üzerinden dosya idarecisi Nemo ile görebiliriz, herhangi bir dizin üzerinde sağ tıklama ve Open With | Disk Usage Analyzer.

Otomatik temizleme icin bleachbit: Kurulum apt-get install bleachbit ile, gksudo ile başlatıp solda temizlenecek şeyler seçilir. APT temizliği iyi oluyor, diğer bir sürü seçenek te var.

Thursday, June 8, 2017

GraphHopper: Pür Java ile Haritada Yol Bulmak

Yol bulmak için OSRM projesinden bahsettik. OSRM çok hızlı çalışır, sonuçları kullanışlı, fakat C++ ile yazılmış, eğer pür Java bazlı bir çözüm istiyorsak (ki böylece kodları mesela Android'e rahatça koyabilelim) o zaman Graphhopper projesi var. GH ismi bir kelime oyunu, grasshopper bilinebileceği gibi çekirge demek, graph (yani çizit) hopper "bir çizitte sağ sola zıplayan" bir görüntü zihinde canlandırıyor, ki bu görüntü pek gerçekten uzak değil, haritada yol bulma algoritmaları hakikaten bilgisayar bilimdeki çizit yapısını temel alıyorlar. Kod şurada,

https://github.com/graphhopper/graphhopper

Kodun derleme sistemi gradle / Maven bazlı, fakat o kadar çetrefil derleme işlemlerine gerek yok, önce GH içinden gerekli java kodlarını çıkartalım, sonra çok baz bir derleme sistemi ile ve ek birkaç jar ile derlemeyi kendimiz dışarıda halledelim. Alternatif bir proje / dizin yaratılır, altında lib, src, resources dizinleri olur. GH indirilir, şimdi alternatif dizin altında

cp -r [GH]/core/src/main/java/* src/
cp -r [GH]/core/src/main/resources/* resources
cp -r [GH]/reader-osm/src/main/java/* src/

ile sadece gerekli Java kodlarını alırız. Şimdi gereken jarları alalım, 


Bu jarları nasıl bulduk? Ya derlerken olmayan jar için gelen hata mesajlara bakıp bu class ismini "vs.vs.Class maven jar" ile Google'da ararız, ya da [GH]/pom.xml ya da hangi pom.xml var ise versiyon sayısını oradan buluruz ve yine Google'da ararız. Mesela jackson-databind lazım, "jackson-databind maven jar" bize gerekli bağlantıyı verir. Zaten görüldüğü gibi bağlantılarda belli bir kalıp da var, class ismi ve versiyon ile bağlantı tahmin de edilebilir.

Jar'lar lib altına gidiyor tabii. Derleme için Ant build.xml

<project name="gh" default="dist" basedir=".">
  <property name="src" location="src"/>
  <property name="build" location="build"/>
  <property name="dist" location="bin"/>
  <target name="init">
    <tstamp/>
    <mkdir dir="${build}"/>
  </target>
  <path id="build.classpath">
    <fileset dir="lib">
      <include name="**/*.jar"/>
    </fileset>
  </path>
  <path id="compile.classpath">
    <pathelement location ="${build}"/>
    <fileset dir="lib">
      <include name="**/*.jar"/>
    </fileset>
  </path>
  <target name="compile" depends="init"
        description="compile the source">
    <javac destdir="${build}">
      <src path="${src}"/>
    <classpath refid="build.classpath"/>
  </javac>
  </target>
  <target name="resources">
    <copy todir="${build}" includeEmptyDirs="no">
      <fileset dir="resources">
        <patternset>
          <include name="**/*.*"/>
        </patternset>
      </fileset>
    </copy>
  </target>
  <target name="dist" depends="compile" description="generate the distribution">
    <mkdir dir="${dist}"/>
    <jar jarfile="${dist}/ghopper.jar" basedir="${build}"/>
  </target>
    <target name="test" depends="compile">
      <java fork="yes" classname="Test" failonerror="true">
        <classpath refid="compile.classpath"/>
      </java>
  </target>
  <target name="clean"
        description="clean up">
    <delete dir="${build}"/>
    <delete dir="${dist}"/>
  </target>
</project>

Bu kadar, ant ile derleriz. Kodların işleyişi için OSM harita dosyaları gerekli, bu dosyalar daha önce de bahsedilen 


sitesinden alınabiliyor. Mesela Türkiye için 


Bu dosyayı bunzip2 ile açıp gzip ile tekrar zipleyelim, çünkü GH .gz dosyası istiyor. Ya da .osm dosyası olduğu gibi bırakılır, GH onu da işler.

GH sürekli direk .gz dosyasını da kullanmaz bu arada, onu işleyip bazı ara dosyalar üretmesi lazım (daha önce bahsedilen çizit dosyaları bunlar, GH OSM formatını alıp daha hızlı işleyiş için çizit yapısına geçiyor). Ara dosyaların üretilmesi ve yol bulma testi çin src altında Test.java yaratalım, 

import com.graphhopper.*;
import com.graphhopper.routing.util.EncodingManager;
import com.graphhopper.reader.osm.GraphHopperOSM;

public class Test {

    static String tmpGraphFile = "/tmp/gh";

    public static void createGraph() {
        String fin = "[DB DIZINI]/turkey-latest.osm.gz";
        GraphHopper gh = new GraphHopperOSM().setStoreOnFlush(true).
            setEncodingManager(new EncodingManager("foot")).setCHEnabled(false).
            setGraphHopperLocation(tmpGraphFile).
            setDataReaderFile(fin);
        gh.importOrLoad();
    }

    public static void testPath() {
        GraphHopper gh = new GraphHopperOSM().
            setEncodingManager(new EncodingManager("foot")).setCHEnabled(false).
            setGraphHopperLocation(tmpGraphFile);
        gh.importOrLoad();
        GHResponse res = gh.route(new GHRequest(40.987659, 29.036428, 
                                                40.992186, 29.039228).
                                 setVehicle("foot"));
        System.out.println(""+res );
    }

    public static void main(String[] args) throws Exception{
        createGraph();
        testPath();
        testPath();
    }
}

Isletmek icin ant test. Araba tarifleri için setEncodingManager ve setVehicle çağrılarında car kullanılır. Kodda createGraph'ın sadece bir kez çağırılması yeterli, bu çağrı /tmp/gh altında gerekli çizit dosyalarını yaratır (çağrı birkaç dakika sürebilir), diğer tüm yol bulma çağrıları bundan sonra çizit dosyalarını kullanıp hızlı şekilde cevabı üretir. Artık elimizde pür Java bazlı, çok hızlı işleyen, mobilde İnternet bağlantısız çalışabilecek harita tarif kodları var. Üstteki kodların kendisi fazla yer tutmuyor zaten (biraz da bunun için daha büyük GH içinden sadece gerekli java ve jar dosyalarını çekip çıkardık, az sayıda java ve 10 tane jar dosyasi ile elimize yol tarifi yapabilen çekirdek bir kod geçti), çizit dosyaları ise bir şehrin büyüklüğüne göre 10-20 MB arasında olur.

Kodun teorik, algoritmik yapısını merak edenler için: kısa yol algoritmaları çoğunlukla Dijkstra algoritmasını kullanırlar (Dijkstra'yı bilgisayar bilim notlarında isledik), OSRM ve Graphhopper da böyle yapıyor, yanlız Dijkstra yaklaşımına bazı ekler yapıyorlar, yaklaşımın adı "kısalan hiyerarşiler (contracting hierarchies)"; yol ağ yapısına bazı noktalarda haritaya dışarıdan kısa yol / zıplamalar ekliyorlar, böylece Dijkstra daha hızlı, verimli işliyor.

Dil, derleme hakkında bazı bilgiler:  

Monday, June 5, 2017

Zaman Serilerinde Tepe Noktası Bulmak (Peak Detection)

Matlab / Octave kullananlar zaman serisi tepe noktası analizinde peakutils adlı bir aracı kullanıyorlar. Bu kod Python'a taşınmış,

https://github.com/atjacobs/PeakUtils

Kod içinden gerekli fonksiyonu çıkarttık,

import numpy as np

def indexes(y, thres, min_dist):
    thres *= np.max(y) - np.min(y)
    dy = np.diff(y)
    peaks = np.where((np.hstack([dy, 0.]) < 0.)
                     & (np.hstack([0., dy]) > 0.)
                     & (y > thres))[0]

    if peaks.size > 1 and min_dist > 1:
        highest = peaks[np.argsort(y[peaks])][::-1]
        rem = np.ones(y.size, dtype=bool)
        rem[peaks] = False

        for peak in highest:
            if not rem[peak]:
                sl = slice(max(0, peak - min_dist), peak + min_dist + 1)
                rem[sl] = True
                rem[peak] = False

        peaks = np.arange(y.size)[~rem]

    return peaks

Parametreler tepe noktalarının arasında en az ne kadar mesafe, ayrıca noktaların en az ne kadar genliğe (y yönünde) sahip olmaları gerektiği. Eldeki bir veri üzerinde indexes(d,thres=0.3,min_dist=3) çağrısı sonrası

Java için benzer bir çağrı, alttaki kütüphaneden,

https://github.com/JorenSix/TarsosDSP

import java.util.*;

public static LinkedList<Integer> indexes(double[] data,
                                          int width,
                                          double threshold,
                                          double decayRate,
                                          boolean isRelative) {

    LinkedList<Integer> peaks = new LinkedList<Integer>();
    int maxp = 0;
    int mid = 0;
    int end = data.length;
    double av = data[0];
    while (mid < end) {
        av = decayRate * av + (1 - decayRate) * data[mid];
        if (av < data[mid])
            av = data[mid];
        int i = mid - width;
        if (i < 0)
            i = 0;
        int stop = mid + width + 1;
        if (stop > data.length)
            stop = data.length;
        maxp = i;
        for (i++; i < stop; i++)
            if (data[i] > data[maxp])
                maxp = i;
        if (maxp == mid) {
            if (overThreshold(data, maxp, width, threshold, isRelative,av)){
                peaks.add(new Integer(maxp));
            }
        }
        mid++;
    }
    return peaks;
}

public static boolean overThreshold(double[] data, int index, int width,
                                    double threshold, boolean isRelative,
                                    double av) {

    int pre = 3;
    int post = 1;

    if (data[index] < av)
        return false;
    if (isRelative) {
        int iStart = index - pre * width;
        if (iStart < 0)
            iStart = 0;
        int iStop = index + post * width;
        if (iStop > data.length)
            iStop = data.length;
        double sum = 0;
        int count = iStop - iStart;
        while (iStart < iStop)
            sum += data[iStart++];
        return (data[index] > sum / count + threshold);
    } else
        return (data[index] > threshold);
}

Güzel. Fakat bu tepe noktası çağrıları toptan şekilde çalışıyor, verinin tamamını alıyorlar, fonksiyon verinin tamamına bakiyor. Soru şu: canlı zamanda, sürekli akan veri üzerinde tepe noktası nasıl buluruz? En son N tane noktayı hatırlamak mümkün olsun diyelim (ama verinin tamamı değil).

İlk akla gelebilecek basit çözüm bir genlik alt limiti ymin'i aşan tepe noktasını seçmek, bu nokta ardından xmin kadar bekleriz, ylim'den üstte yeni bir tepe nokta var ise, bunu da alırız, böyle devam ederiz. Fakat basit çözüm biraz aceleci aslında, belki xmin sonrası bulunan tepe noktasına çok yakın "daha iyi (yani daha yukarıda)" bir nokta daha var, tipik olarak hemen bir önceki noktanın üzerine atlamak istemiyoruz, daha yukarıdaki noktayı istiyoruz.

Bu durum için yine ilk akla gelen çözüm xmin'i arttırmak olabilir, fakat global bir parametreyle bu şekilde oynamak çoğunlukla iyi sonuç vermez, büyük ihtimalle analizin diğer yerlerinde başka yanlışlara yol açar.

Çözüm yaklaşımı değiştirip veriler için bir kayan pencere kullanmak. Tepe noktası "en son N öğenin içinde orta noktanın maksimum olması demek" diye bir tanım getirebiliriz. Kayan pencere  için CircularFifoQueue kullanılabilir, bu bir org.apache.commons sınıfı, bir tür sınırlandırılmış kuyruk (queue). N öğe tutsun diye tanimlarsak N öğe ardından verilen N+1'inci öğe için 1. öğe dışarı atılır. O zaman tepe noktası bulan kod şöyle olabilir

import java.io.*;
import java.util.*;
import java.util.Queue;
import org.apache.commons.collections4.queue.CircularFifoQueue;

public class TestPeak {

    public static class PeakFinder {
        double xmin = 0;
        double ymin = 0;
        int mid = 0;
        CircularFifoQueue idxs = null;
        CircularFifoQueue vals = null;
        // "null" olmayan degeri temsil etmek icin kullaniyoruz
        // elinde process'e verecek id'si olmayan cagrilar icin
        // kullanisli olabilir
        public static int DUMMY = 1; 
        public PeakFinder(int xmin, double ymin){
            this.xmin = xmin;
            this.ymin = ymin;
            idxs = new CircularFifoQueue(xmin);
            vals = new CircularFifoQueue(xmin);
            this.mid = (int)vals.size() / 2;
        }
        // process hem id hem deger aliyor, fakat id aslinda
        // tutulup oldugu gibi geri veriliyor, cagri yapana
        // yardimci olmasi icin bunu yapiyoruz, fonksiyonun ic
        // isleyisi icin onemli degil.
        public int process(double val, int idx) {
            vals.add(new Double(val));
            idxs.add(new Integer(idx));
            if (vals.size() < xmin) {
                return Integer.MIN_VALUE;
            }
            if (vals.get(mid) > this.ymin && vals.get(mid) == Collections.max(vals)) {
                return idxs.get(mid);
            }

           // Integer.MIN_VALUE null degeri yerine kullanildi, 
           // cunku int yerel tip, obje degil
            return Integer.MIN_VALUE;
        }
    }
        
    public static void main(String[] args) throws Exception{
        java.util.Random r = new java.util.Random();
        r.setSeed(0);
        double samples[] = new double[1024];
        for ( int n = 0; n < samples.length; n++ )
            {
                double noise = r.nextGaussian() * Math.sqrt(10);
                samples[n] = Math.sin( n * Math.PI / 18. ) + noise;
            }
            
        // uretilen veriyi dosyaya yazalim, ustteki Python kodu ayni veriyi
        // kullanacak.
        PrintWriter writer = new PrintWriter("out.txt");
        for (int i = 0; i < samples.length; i++) writer.println(samples[i]);
        writer.close();

        ArrayList res = new ArrayList();
        PeakFinder pf = new PeakFinder(6, 6.0);
        for ( int n = 0; n < samples.length; n++ ) {
            int idx = pf.process(samples[n], n);
            if (idx > Integer.MIN_VALUE) res.add(idx);
        }

        System.out.println(""+res );
    }
}

Sonuc,
Tekrarlamak gerekirse: tepe noktası "sağında ve solunda vadiler olan orta noktadır" tanımı üzerinden  sonucu aldık. Pencereyi sürekli kaydırıyoruz (daha doğrusu her yeni veriyi N tane sınırlı öğe içerebilen bir kuyruğa sürekli sondan ekliyoruz), ve bu sırada orta noktanın maksimum olup olmadığına bakıyoruz. 

JAMA - Java ile Matris Islemleri

Python ile prototip hatta servis tarafı sayısal işlem kodları rahatça yazılıyor; fakat bazen lineer cebir yapan kodları Java'ya çevirmek gerekebilir, mesela Android üzerinde işlemesi gereken kodlar. Pür Java ile yazılmış kullanışlı liner cebir kütüphanelerinden biri JAMA:

http://math.nist.gov/javanumerics/jama/#Package

Matrix Class Doc


İhtiyaç olan en önemli özellikler temel işlemler, toplama, çıkartma, ve matris arası çarpım, matris tersi (matrix inversion) ve devriği (transpose) Ek iyi olabilecek özellikler en az kareler (least squares) çözümü, SVD, LU, Cholesky ayrıştırması, vs. Bu özelliklerin hepsi Jama'da var.

Üstteki ilk bağlantıdan jar indirilir, altta kısa bir test,

import Jama.*;

public class Test {

    public static void main(String[] args) throws Exception{

        Matrix A = new Matrix(3, 3);

        A.set(1,0,10.0);
        A.set(1,1,10.0);
        A.set(1,2,10.0);

        System.out.println("A\n"+toString(A));

        System.out.println("A get\n"+A.get(1,1));

        double[][] bvals = {{1.,2.,3},{4.,5.,6.},{7.,8.,10.}};
        Matrix B = new Matrix(bvals);
        System.out.println("B\n"+toString(B));

        Matrix C = A.times(B);

        System.out.println("Carpim\n"+toString(C));

        Matrix D = A.plus(B);

        System.out.println("Toplam\n"+toString(D));

    }

    public static String toString(Matrix m) {
        String s = "";
        for (int i=0;i<m.getRowDimension(); i++){
            for (int j=0;j<m.getColumnDimension(); j++) s += "" + m.get(i,j) + " ";
            s += "\n";
        }
        return s;
    }
}

Sonuclar

A
0.0 0.0 0.0 
10.0 10.0 10.0 
0.0 0.0 0.0 

A get
10.0
B
1.0 2.0 3.0 
4.0 5.0 6.0 
7.0 8.0 10.0 

Carpim
0.0 0.0 0.0 
120.0 150.0 190.0 
0.0 0.0 0.0 

Toplam
1.0 2.0 3.0 
14.0 15.0 16.0 
7.0 8.0 10.0 

Bazı püf noktaları:

Android ortamı her ne kadar tam gömülü (embedded) bir ortam sayılmasa da, servis tarafı kodlanıyormuş gibi davranmaktan kaçınmak iyi olur, mesela telefon ivmeölçerinden gelen verileri hızlı bir şekilde işlemek gerekiyor, her işlem için bir matris çarpımı lazım, bu durumda her yeni veri iletimi için yeni matrisler yaratıp onları çarpmaya gerek yok, her seferinde hafızaya obje ekleme, onun çöp toplayıcısı tarafından silinmesi işleri ağırlaştırır. En iyisi sadece iki Matrix objesi yaratıp ama değerlerini her seferinde değiştirip çarpımı bu aynı objeler üzerinde yapmak.

Ek kodlar, mesela Jama kodlarında çapraz çarpım verilmemiş, bu benzeri ekler,

import Jama.Matrix;
import java.net.*;
import java.util.*;
import java.io.*;
import java.text.*;

public class Util {

    // Helper class hidden here to provide additional matrix methods
    // taken from https://github.com/thorstenwagner/ij-ellipsesplit
    public static class Matrix2  {
        private double[][] A;
        private int m, n;
        public Matrix2(int m, int n) {
            this.m = m;
            this.n = n;
            A = new double[m][n];
        }
        public Matrix2(double[][] A) {
            m = A.length;
            n = A[0].length;
            for (int i = 0; i < m; i++) {
                if (A[i].length != n) {
                    throw new IllegalArgumentException("All rows must have the same length.");
                }
            }
            this.A = A;
        }

        public Matrix2 crossProduct(Matrix2 B) {
            if (m != B.m || n != B.n) {
                throw new IllegalArgumentException("Matrix dimensions must agree");
            }
            Matrix2 X = new Matrix2(m, n);
            if (m == 1 && n == 3) {
                X.A[0][0] = A[0][1] * B.A[0][2] - A[0][2] * B.A[0][1];
                X.A[0][1] = A[0][2] * B.A[0][0] - A[0][0] * B.A[0][2];
                X.A[0][2] = A[0][0] * B.A[0][1] - A[0][1] * B.A[0][0];
            } else if (m == 3 && n == 1) {
                X.A[0][0] = A[1][0] * B.A[2][0] - A[2][0] * B.A[1][0];
                X.A[1][0] = A[2][0] * B.A[0][0] - A[0][0] * B.A[2][0];
                X.A[2][0] = A[0][0] * B.A[1][0] - A[1][0] * B.A[0][0];
            } else {
                throw new IllegalArgumentException(
                                                   "Matrix must be a 3-element row or column vector");
            }
            return X;
        }

        public double[][] getArray() {
            return A;
        }
    }

    public static String toString(Matrix m) {
        String s = "";
        for (int i=0;i<m.getRowDimension(); i++){
            for (int j=0;j<m.getColumnDimension(); j++){
                s += "" + m.get(i,j) + " ";
            }
            s += "\n";
        }
        return s;
    }

    // project u onto plane with normal n
    public static Matrix proj (double[] u, double[] n) {
        Matrix um = new Matrix(u, 3);
        Matrix un = new Matrix(n, 3);
        Matrix tmp1 = um.transpose().times(un);
        Matrix tmp2 = un.transpose().times(un);
        Matrix tmp3 = un.times(tmp1.get(0,0) / tmp2.get(0,0));
        Matrix res = um.minus(tmp3);
        return res;
    }

    public static Matrix cross(Matrix a, Matrix b) {
        Matrix2 aa = new Matrix2(a.getArray());
        Matrix2 bb = new Matrix2(b.getArray());
        Matrix2 res = aa.crossProduct(bb);
        return new Matrix(res.getArray());
    }
}