Markof Modeli (Markov Model)

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ğmıyorsa -> yarın yağmur yağma ihtimali = 0.2
Bugün yağmur yağmı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 p² 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:

Yukarıdaki hesapta öncelikle 3. satın alma işlemi sırasında stokastik matrisin değeri hesaplanmıştır. Yani P³ 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.

« Hamilton Yolu (Hamiltonian Path,hamiltonian circuit) | Dinamik Markof Kodlaması ile Sıkıştırma (Data Compression Using Dynamic Markov Coding) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Markof Modeli (Markov Model)' isimli yazı 17 Jun 2009 tarihinde, saat: 14:19 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 632 defa okunmuştur.

Benzer yazıları Automata (otomatlar, özdevinirler), Bilgisayar Matematiği, Temel Bilimler, algoritma analizi (teory of algorithms), graf teorisi (graph theory, çizge kuramı) kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar