Yazan : Şadi Evren ŞEKER

Bilgisayar bilimleri de dahil olmak üzere pekçok bilim ve mühendislik alanında kullanılan markof modelleri aslında graf teorisinin (graph theory) bir uygulamasıdır.

Basitçe düğümleri (nodes) durumlardan oluşan ve bu durumlar arasında istatistiksel geçişi modelleyen kenarları (edges) bulunan graflardır.

Markof modellerine (markof zinciri (markov chain) ismi de kullanılmaktadır) göre bir durum belirli bir istatistiksel değere göre değişir veya değişmeden aynı kalır. Ayrıca geçmiş durumların mevcut durum üzerinde bir etkisi söz konusu değildir. Ancak şimdiki durum gelecek durumları etkileyebilir.

Markof modelinin tanımı

Markof modellerinin istatistiksel olma özelliğinden dolayı her bir stokastik olayın (Stochastic Event) olasılık değerini modelleyen bir gösterimi mümkündür.

Bu olasılıkların gösterildiği formül

markov

Yukarıdaki formülde t+1 zamanındaki olayların t zamanına bağlı olması söz konusudur. Yukarıdaki bu zaman bağlamında bağımlılıktan dolayı markov modellerinin yönlü graf olmaları gerekir.

markovzinciri

Yukarıdaki şekilde bu olaylar arası bağlantı yönlü graf (directed graph) olarak görülmektedir. Elbette yukarıdaki graf sadece bir örnek olup olayların doğrusal olarak bağlanmaları gerekemez ancak yukarıdaki graftan anlaşılması gereken her olayın bir sonraki olaya belirli bir olasılık değeriyle devam edebileceği veya aynı kalacağıdır. Örneğin t anında X1 olayı oluyor olsun. t+1 zamanında X1 devam edebilir veya X2 olayına geçilebilir.

Yukarıdaki bu gösterimlere ilave olarak markov zincileri birer masfuf (matrix) ile de gösterilebilir.

markovmatrix

Örneğin yukarıdaki matriste 4 olay arasındaki geçiş değerleri gösterilmiştir. Matrisin tek yönlü olmasına dikkat edilebilir. Yani köşegen simetriği (diagonal symmetry) mutlaka 0 olmalıdır. Örneğin C’den B’ye olasılık değeri 0.2 iken B’den C’ye 0 olmaktadır. Ayrıca satır bazında ihtimallerin toplamları 1 olmalıdır. Yani satırın ifade ettiği stokastik olaydan farklı bir stokastik olaya geçişin veya aynı olayda kalmanın ihtimalleri toplamı 1 olmalıdır.

Markof zincirlerine hava durumu örneği

Markof zincirleri tahmin (forecasting) için oldukça kullanışlıdırlar. Örneğin hava durumu tahmini için markof zinciri kullanmak isteyelim ve iki olayımız olsun:

  • bugünkü hava
  • yarınki hava

şimdi elimizde bugünkü havanın durumu bulunmakta. Bu olaydan yola çıkarak yarınki hava olayını (tahminini) yapmaya çalışalım ve olayı markof modeli ile modelleyelim.

  • Bugün yağmur yağıyorsa -> yarın yağmur yağma ihtimali = 0.4
  • Bugün yağmur yağıyorsa -> yarın yağmur yağmama ihtimali = 0.6
  • Bugün yağmur yağyorsa -> yarın yağmur yağma ihtimali = 0.2
  • Bugün yağmur yağyorsa -> yarın yağmur yağmama ihtimali = 0.8

olarak verilmiş olsun. Bu bilgiyi geçmiş tecrübelerden edindiğimizi ve markof modeli ile modellemek istediğimizi düşünelim.

stokastikmatris

Sonuç olarak yukarıdaki şekilde bir olasılık matrisi elde edilir. Bu matrise, stokastik matris (stokhastic matrix) ismi de verilmektedir.

Markof zincirleri ile Kola ve Pepsi örneği

Markof zincirlerinin anlatımı sırasında kullanılan meşhur örneklerden birisi de kola ve pepsi örneğidir. Bu örnekte bir kişinin en son aldığı içeceğin kola ( coca cola ) olması veya pepsi olması durumuna göre bir sonraki içeceğinin tahmin edilmesine çalışılır.

markovkola

Örneğin bu iki içecek arasındaki ilişki ve karar olasılıkları yukarıdaki şekilde verilmiş olsun. Yani pepsi alan bir kişinin bir sonraki içceğinin yine pepsi olma olasılığı 0.8 ve kola olma olasılığı 0.2, benzer şekilde kola içen birisinin bir sonraki içeceğinin yine kola olma olasılığı 0.9 ve pepsi olma olasılığı 0.1 olarak verilsin.

Şimdi sorumuzu soralım:

Pepsi içen bir kişinin ikinci alış verişinde kola alma olsaılığı nedir?

Bu sorunun cevabı için stokastik matrise başvurarak basit bir matris çarpım işlemi yapabiliriz:

markovkolastokastik

Önce yukarıdaki şekilde stokastik matrisimizi çıkaralım ve olasılıkları yerleştirelim. Şimdi sorumuza dönecek olursak bize ikinci alış verişteki ihtimal sorulmuşt. Bu durumda matrisin karesini alalım (kendisi ile çarpalım)

markovkolastokastik2

Yukarıdaki p2 matrisinden anlaşılacağı üzere markof modelimizdeki bir olayın tekrar etme olasılığını bulmuş olduk. Kişinin ikinci alışverişinde pepsiden kolaya geçme olasılığı yukarıdaki şekilde 0.34 olarak bulunmuş olur.

Örneğin yukarıdaki bu bilgiler ışığında bize şöyle bir soru da sorulabilir di:

Mevcut durumda insanların %60’nın kola ve %40’ının pepsi içtiklerini düşünelim. Bu insanların haftalık olarak içecek aldıklarını düşünürsek üç hafta sonra insanların ne kadarı kola içiyor olacaktır?

Şimdi bu soruyu çözerken 3 satın alma işlemi yani 3 kere markof modelde değişim işlemi yapılacağını hatırlayalım. Ardından mevcut durumun etkisini de ekleyerek hesabımızı aşağıdaki şekilde yapalım:

markof

Yukarıdaki hesapta öncelikle 3. satın alma işlemi sırasında stokastik matrisin değeri hesaplanmıştır. Yani P3 için matris 3 kere kendisi ile çarpılmıştır. Ayrıca matristen elde edilen katsayılar 0.6 ve 0.4 mevcut durum oranıyla çarpılmıştır. Sonuçta 0.6438 oranında kişinin kola içeceği bulunmuş olunur.

Yorumlar

  1. BilgisayarMühendisi

    İyi günler Hocam. Markov zincirleri ile ilgili anlatım çok güzel olmuş elinize sağlık. Daha fazla kaynağa nasıl ulaşabiliriz. Şimdiden teşekkür ederim.

    1. Şadi Evren ŞEKER

      Merhaba, genelde site bilgisayar bilimleri ve bilişim teknolojileri gibi konuları hedeflediği için vakit buldukça bu konulara öncelik veriyorum. Markof zincirleri için genelde istatistik kitaplarından temel kavramları öğrenmeniz mümkün. Konu hakkında mutlaka bahsedilmesi gereken iki kaynak:

      A.A. Markov. “Rasprostranenie zakona bol’shih chisel na velichiny, zavisyaschie drug ot druga”. Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp. 135–156, 1906.
      A.A. Markov. “Extension of the limit theorems of probability theory to a sum of variables connected in a chain”. reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.

      ilki Markov’un orjinal yayını (ki ben ne yazık ki dil farkı yüzünden anlayamıyorum). İkincisi ise yayının ingilizceye çevrilmiş halinin yeniden baskısı.

      Bilgisayar bilimlerinde genelde ayrık zamanlı markof zincirleri (discrete time markov chains) kullanıldığı için aşağıdaki yayını da tavsiye edebilirim:

      Norris, James R. (1998). Markov chains. Cambridge University Press.

      Ancak belki ihtiyacınız olan özel bir uygulama alanı varsa bununla ilgili özel kaynaklar da bulmak mümkün olabilir.

      Başarılar

  2. tlg

    Hocam “Ayrıca geçmiş durumların mevcut durum üzerinde bir etkisi söz konusu değildir. Ancak şimdiki durum gelecek durumları etkileyebilir.” dedik ama sonuçta durumlar P matrisi ile birbirine bağlandığına göre örneğin 4. durum P^3 matrisi ile ilişkili olsa da 3. durum da aynı şekilde 2. durumla ilişkili olduğundan bütün durumlar birbiriyle ilişkilidir diyemez miyiz?

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir