Discrete Stochastic Processes - I

Matematik Köyü'nde Kış döneminde takip ettiğim Arif Mardin hocanın 'Discrete Stochastic Processes' dersinin notlarnı gün gün tutmaya çalışıyorum. Elimdeki notlardan kendi anladığım şekliyle burada da bir seri şeklinde kısa kısa yazmayı planlıyorum. İlk yazı ile başlayalım o halde.

İlk derse 'Basit Rastgele Yürüyüş' (Simple Random Walk) ile başladık ve sonrasında onun Markov özelliklerinden yola çıkarak Markov Zincir'lerini inceledik. Rastgele yürüyüşü elindeki bir miktar parası olup, kumar masasında her oyunda $p$ olasılıkla parasını $1$ arttıran, $1-p$ olasılıkla da 1 azaltan bir kumarbazın durumu için değerlendirebiliriz. Bu durumda $n$ oyun/adım sonrasında kumarbazın elindeki parayı şu şekilde yazabiliriz: $$S_n = S_0 + \sum_{i = 1}^n X_i$$ Burada $S_0$ başlangıçtaki para ve $X_i$'ler de her oyunda kazanıp kaybettiğimiz parayı gösteren rassal değişken. $X_i$ rassal değişkeni yalnızca $+1$ ve $-1$ değerleri alabilen bir 'Bernouilli rassal değişkeni'. $X_0, X_1, ... , X_n$ serisi $p$ olasılıkla $+1$, $1-p$ olasılıkla da $-1$ değerleri alabilen Bernoulli rassal değişkenlerinden oluşan bir dizidir.

Bu tip basit bir kurala dayalı olarak kurgulanmış bu oyuna dair birçok ilginç  soru sorulabilir. Örneğin:

- $n$ oyun sonrasında ne kadar kazanmayı bekleriz?
- Kazancımızın ya da kaybımızın yeteri kadar oynadığımızda sonsuz olmasını bekler miyiz? Hangi koşulda böyle bir durum oluşur?
- Herhangi bir zamanda cebimizdeki bir para değerine sonra tekrar dönmeyi bekler miyiz? Kaç kere döneriz? Bu durum tüm para değerleri için gerçekleşir mi?

Rastgele yürüyüş problemi bunlar gibi birbirinden ilginç ve çoğu zaman çözümü epey uğraştırıcı birçok probleme kaynaklık yapıyor. İlerleyen zamanda daha detaylıca inceleyeceğiz. Birkaç özelliğine göz atalım şimdi.

Lemma 1: Basit rastgele yürüyüş uzayda homojendir. Yani: $$\mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}(S_ n = j +b | S_0 = a+b)$$
Kanıt: $ \mathbb{P}(S_n = j  |  S_0 = a) =  \mathbb{P}( \sum_i^n X_i = j - a) = \mathbb{P}(S_n = j +b | S_0 = a + b)$

Lemma 2: Basit rastgele yürüyüş zamanda homojendir. Yani: $$\mathbb{P}(S_n = j | S_0 = a) =  \mathbb{P}(S_{n+m} = j | S_m= a) $$
Kanıt: $ \mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}( \sum_i^n X_i = j - a) =  \mathbb{P}( \sum_{i = m+1}^{m+n} X_i = j - a) = \mathbb{P}(S_{n+m}  = j | S_m = a)$

Lemma 3 (Markov Özelliği): Rastgele yürüyüşün belirli bir andan sonraki adımları sadece bulunduğu adımdan bir önceki adımına bağlıdır, ondan öncekilerden tamamen bağımsızdır. $$\mathbb{P} = (S_{m+n} = j | S_0,S_1, ..., S_m) = \mathbb{P}(S_{m+n} = j | S_m)$$ Yukarıdaki şartlı olasılık ifadesindeki $S_0,S_1, ..., S_m$, 0. adımda $S_0$, 1. adımdaki $S_1$, $...$ m. adımda $S_m$ olayının gerçekleştiğini gösteriyor. Rastgele yürüyüş'ün bu özelliği ona birçok ilginç davranış kazandırıyor. Bunları anlayabilmek için öncelikle Markov Zincir'lerine kısaca bir göz atalım.

MARKOV ZİNCİRLERİ

Belirli bir sayılabilir (countable) durumu barındıran bir 'durum uzayı' $\mathcal{S}$ üzerinde tanımlı, bu durumları $n$ ile gösterilen adımlarda dolaşan bir proses olarak tanımlayabiliriz.

$\mathbb{X} = (X_n, n \in \mathbb{N}$, $\mathcal{S}$'den değerler alan birer rassal değişkenler dizisi olsun.

Tanım: $\mathbb{X}$ dizisi tüm $\forall n \in \mathbb{N}$ ve $\forall i_0, i_1, ..., i_n \in \mathcal{S}$ için Markov özelliği $$ \mathbb{P} (X_{n+1} = i_{n+1} | X_0 = i_0, X_1= i_1, ... , X_n = i_n) = \mathbb{P}(X_{n+1} = i_{n+1} | X_n = i_n)$$ sağlıyorsa Markov Zinciri (Markov Chain - MC) olarak adlandırılır.

Markov Zinciri eğer $\forall i, j \in \mathcal{S}$ için $\mathbb{P} ( X_{n+1} = j|X_n = 1)$ $n$'e bağlı değilse homojen olarak adlandırılır.

Olasılıkları hesaplamak için iki şeyi bilmemiz gerekir:

a) Geçiş matrisi (Transition Matrix) $P = (p_{ij} \hspace{0.5cm} i,j \in \mathcal{S})$ aşağıdaki gibi verilir: $$ P_{ij} = \mathbb{P}(X_1 = j| X_0 = i)$$
b) Başlangıç olasılık dağılımı $\lambda = (\lambda_i, i \in \mathcal{S})$

Homojenlik varsayımı gereği şunu yazabiliriz: $$\mathbb{P} (X_{n+1} = j | X_n  = i) = P_{ij}$$

Önermeler:
a)$\lambda$ vektörü bir olasılık dağılımıdır. $$ \lambda_i \geqslant 0 \hspace{0.5cm} \forall i \in \mathcal{S} \hspace{0.3cm} \text{ve} \sum_{i \in \mathcal{S}}\lambda_i = 1$$
b) $P = (p_{ij}\hspace{0.3cm}; i,j \in \mathcal{S})$ matrisi bir 'stochastic matris'tir.

   i) $P_{ij} \geqslant 0 \forall i,j \in \mathcal{S}$

   ii)$\sum_{j \in \mathcal{S}} P_{ij} = 1 \forall i \in \mathcal{S} $ ($P$'nin  satır toplamları $1$'e eşit.

Önermelerin kanıtları:
a) $\lambda_i$'ler bir olasılık olduğundan sıfırdan büyük eşit olmalılar. $$\sum_{i \in \mathcal{S}} \lambda_i = \sum_{i \in \mathcal{S} } \mathbb{P} (X_0 = i) = 1 \hspace {1.5cm} \square$$
b)$P_{ij}$'ler olasılık değerleri olduğundan dolayı sıfırdan büyük eşit olmalılar. $$ \sum_{j \in \mathcal{S}}P_{i,j} = \sum_{i \in \mathcal{S}}\mathbb{P} (X_1 = j |X_0 = i) = \mathbb{P}(X_1 \in \mathcal{S} | X_0 = i) = 1 \hspace{1.5cm} \square$$

Haftanın Makalesi (III): "Simulating Physics with Computers"

"...and I'm not happy with all the analyses that go with just the classical theory, becouse nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical and by golly it is  a wonderful problem, because it doesn't look so easy." 

Richard P. Feynman

1980'lerin başında bilgisayarda hesaplama ve simulasyona dair fiziğin üstadı Feynman'ın Caltech'de yaptığı bir konuşmaya dayalı klasik bir makale bu haftanın seçimi: "Simulating Physics with Computers". Doğanın en temelde klasik yasaları olarak bildiğimiz klasik fizikten birçok yönden devrimsel olarak ayrılan kuantum mekaniği (ve en genel anlamda kuantum alan teorileri) tarafından açıklanıyor olması, birçok yönden klasik özelliklere sahip görünen bilgisayarlar tarafından benzetiminin (simulasyon) gerçekten yapılıp yapılamayacağı sorununu doğuruyor. Eğer [kuantum mekaniğine dayalı] doğayı tam olarak modelleyip, elimizdeki bilgisayarlarla simule etmek istiyorsak en temelde olasılıkların yattığı farklı tipte bir 'evrensel hesaplayıcıya' ihtiyacımız olduğunu dile getiriyor Feynman makalede.

Makalenin başında, klasik fizikteki uzay ve zamanın, yerel (local), nedensel (causal) ve tersinebilir (reversible) özellikleri  dolayısıyla aşina olduğumuz bilgisayarlarda simulasyona elverişli olduğu tartışmasını yürütüyor. Sonrasında bilgisayarlarda olasılığının simulasyonunun nasıl yapılacağına değinip, birden fazla parçacıklı kuantum sistemlerindeki olasılık sayısının çok büyümesiyle ilişkili olarak bu tip bir hesabın mümkün olmayacağını dile getiriyor. (Aklıma, bu duruma Monte Carlo yaklaşımları ile nasıl girişilir acaba? sorusu geliyor...)

Makalenin temel noktası dördüncü bölümde ele aldığı konu, büyük ölçekli kuantum mekanik sistemleri simule etmek için işe yarayacak, tıpkı simule etmeye çalıştığı fenomenler gibi kendisinin de kuantum mekaniğinin prensiplerine dayanan bir evresel hesaplayıcı yani bir 'kuantum bilgisayar'. Bu bölümde kuantum alan teorisinden ödünç aldığı fikirlerle parçacıkların spin özelliklerini kullanarak bu tip sistemler oluşturulabileceğini ifade ediyor ama aralarda birçok belirsizlikler ve boşluklar bırakıyor. Makalenin ilerleyen kısmında klasik bir bilgisayarla kuantum sistemlerinin simule edilemeyeceğinin teknik analizini yapıp ortaya çıkacak problemlerden bahsediyor.

Makalenin sonunda bilgisayarlarla doğanın kendisini birebir simule ederek fiziğe dair yeni birçok şey keşfedeceğimizi ve bu amacın peşinden gidilmeyi fazlasıyla hak ettiğini dile getiriyor Feynman. Günümüzdeki kuantum bilgisayarlar için atılan adımlar ve son zamanlardaki gelişmeler bu fikrin birçok insan tarafından paylaşıldığını gösteriyor. Fizikte her zaman yeni ve farklı yaklaşımları geliştirip çocuk merakı ve kurcalama hissiyle doğaya yaklaştığı bilinen Feynman'ın o dönemde hızla gelişen bilgisayarlarla ilgilenmemesi şaşırtıcı olurdu. Kendisinin ayrıca hesaplamaya dair güzel de bir ders serisi var 'Feynman Lectures on Computation' adında. Kuantum bilgisayarların gündemde olduğu fakat bilinenler çok kısıtlı olması sebebiyle alandaki belirsizliklerin bir o kadar büyük olduğu bir dönemde, bu tip bir bilgisayarın fizik için ne anlam ifadeceğini ele alan, temel kuantum mekaniği bilgisiyle okunabilecek güzel bir makale.

Makaleyi okumak için: "Simulating Physics with Computers"(PDF)
Makale üzerine açıklamalara ve detaylı incelemeye yer veren şu makaleyi de tavsiye ederim: 'Richard Feynman: Simulating Physics with Computers' (M.Demmer ve ark.)

Haftanın Makalesi (I): "Best Practices for Scientific Computing"

Uzun bir süredir tez çalışmalarımda, kendi araştırmalarımda, aldığım derslerin projelerinde ve verdiğim derslerin uygulamalarında bilgisayar kodu yazıyorum. Çoğu zaman fiziksel/bilimsel bir problemi çözmek üzerine olan bu kodların yapısı genelde "günü kurtaran", bir şekilde çalışıp bir sonuç üreten tipte oluyor. Bu haliyle çoğu zaman içinde kendini tekrar eden kod kümeleri barındıran, nerede-ne yaptığı belli olmayan, iyi belgelenmemiş ve başka birisi aldığında bırakın tekrar çalıştırıp aynı sonuçları üretebilmeyi kodu okuyup ne yaptığını dahi anlaşılmayacak kadar karmaşık türde kodlar yazdığını fark ediyor insan. Küçük çaplı çalışmalarda "iş gören" kodlar, problem biraz karmaşıklığında tam bir baş belasına dönüşebiliyor ve o anda artık biraz "iyi alışkanlıklar" (best practices) takip edip hayatı kolaylaştıran yöntem ve araçlara yönelmek durumunda kalınıyor. Bu hafta okuyup kısaca özetleyeceğim  G. Wilson ve arkadaşları tarafından 2014'de yayınlanan "Best Practices for Scientific Computing" makalesinin temel fikri de tam olarak bu.

Yazarlar öncelikle bilimsel amaçla yazılan programların bir bilim insanı için başka bir tür "deney aracı" olduğunu ve tıpkı fiziksel bir deney aracı gibi yapılandırılıp, kontrol edilerek dikkatli bir şekilde kullanılması gerektiğini belirterek başlıyorlar. Sonrasında da  bilimsel kod yazımında dikkat edilmesi önerilen sekiz maddeyi sıralıyorlar:

1- Yazdığınız kodu bilgisayarlar için değil, insanlar için yazın.

• Yazılan kodu başkalarının veya özellikle gelecek bir zamanda kendisinin anlayabilmesi için insanların anlık hafızalarının kısıtlılığı, örüntü tanıma becerilerinin hassas bir şekilde ayarlanmış olduğu ve dikkat sürelerinin kısa oluşunu göz önüne alarak yazmak gerektiği vurgulanıyor. Bunun için verilen temel öneri kodu tıpkı bir makaledeki bölümler gibi, belirli amaçlar için oluşturulmuş fonksiyonlara bölmek.
• Programda kullanılan isim ve etiketleri ayırdedilebilir, tutarlı ve anlamlı bir şekilde vermeli.
• Kodun her bölümünde stil ve formatı koruyarak ilerlemeli.

2- Bırakın bilgisayarlar işi yapsın.

• Gerçekleştirilmesi hedeflenen prosedürü tekrar tekrar elle yapmak yerine bir script ile çalıştırılacak komutları otomatize etmeyi ve "build tool"lar kullanmayı öneriyorlar.

3- Değişiklikleri ufak ufak yapın.

• Küçük adımlarla, sık sık geri bildirim alarak düzenlemeler yapıp ilerlemeyi öneriyorlar. Her iterasyonda çalışan bir program yazmak amaç ve her iterasyondaki değişiklikleri kaydedip gerektiğinde geriye almak için de GitHub gibi versiyon kontrol sistemleri kullanmayı öneriyorlar.

4- Kendinizi (ya da başkalarını) tekrar etmeyin.

• Bu prensip hem veri için hem de kod için geçerli. Sistemdeki her bir verinin tek bir temsili bulunması gerek; yani kodun bir yerinde değişiklik yapıldığında bu değişiklik tüm her yere paralel olarak yansıması gerek. 
• Kopya-yapıştır yapmak yerine kodu modüler hale getirmek, fonksiyonlar ve class'lar ile ilerlemek en sağlıklısı.

5- Hatalar için önceden plan yapın.

• Hatalar kaçınılmaz, sadece onlara karşı "hazırlıklı" olmak gerekiyor. Bunun için "savunmacı programlama" yöntemi geliştirmeyi öneriyorlar. Kodun içine yanlış gitmesi muhtemel durumları kontrol amaçlı "assertion"lar ekleyip gerektiği durumda müdehale etmek gerekiyor. Assertion'lar program içinde örneğin belirli değişkeni, bir fonksiyon çıktısını kontrol edip programın devamını sağlayan mantıksal ifadeler. Bu ifadeleri kullanmanın kodun bölümlerine açıklama yazmaktan daha fazla anlaşılırlık kattığını söylüyorlar.
• Otomatik testler uygulamak için standart test kütüphaneleri kullanmayı ve bugları bulmak için sembolik debugger'lar kullanmayı öneriyorlar.

6- Programı ancak doğru çalıştıktan sonra optimize edin.

• Araştırmalarda kod yazan kişilerin kullandıkları dilden bağımsız olarak birim zamanda neredeyse aynı satır sayısında kod yazdığını gözlemişler. Buradan yola çıkarak kodu öncelikle daha az satır kodla yazılabilecek Python, R gibi "yüksek-seviyeli" dillerde prototipleyip ardından daha iyi performans için C, Java gibi düşük seviye dillere geçmeyi öneriyorlar.

7- Tasarım ve amacı dokümante edin, çalışma prensibini değil.

• Yazılan kodu açıklamak için bir paragraf adım adım nasıl çalıştığını anlatmak yerine, kullanılan arayüzleri açıklayıp amaç ve nedenlerini açıklamak gerektiğini vurguluyorlar. Nasıl çalıştığının adım adım anlatılması gereken kodun tekrar geri dönülüp buna ihtiyaç kalmayacak şekilde tekrar düzenlenmesi gerektiğini söylüyorlar.
• Dokümantasyonu yazılımın içine gömmeyi öneriyorlar ayrı bir yerde tutmak yerine (örneğin Jupyter Notebook'larda olduğu gibi); böylece program başkaları tarafından modifiye edildiğinde paralel olarak dokumantasyonun da güncellenebileceğini ekliyorlar.

8- Birlikte çalışın.

• Yazılan programları proje üzerine çalışan kişiler arasında incelenip, gözden geçirilmesini öneriyorlar. Hatayı çok daha aza indirmek için aynı kod üzerinde beraber çalışmayı öneriyorlar.

Araştırmalarda bu tip "iyi alışkanlıkları" edinmek için gerekli öğrenme ve bunları uygulama sürelerinin, sonunda elde edilen verimlilik ile fazlasıyla karşılandığı belirtiliyor. Makalenin başında tıpkı laboratuardaki deneylerde olduğu gibi standartları birebir uygulamanın her zaman mümkün olmadığını ve bu alışkanlıkların hepsini bir anda uygulamaya çalışmaktansa teker teker çalışma rutinlerine entegre edilmesi gerektiğini ifade ediyorlar.

Bu yazıyı okuyup, konuyla uğraşan kişilerin bu tip "iyi alışkanlıklar" önerileri varsa da duymayı çok isterim!

Makaleyi okumak için:  "Best Practices for Scientific Computing" (PLOS Biology - Open Access)