Yazan : Şadi Evren ŞEKER

Toplam çarpım algoritmaları (sum-product algorithms), çeşitli istatistiksel ve hesaplamalı çalışmalarda, birden fazla varlığın ürettiği verilerin işlenmesi için kullanılır. Buradaki amaç, birbiri üzerinde etkisi bulunan bayez ağı (bayesian network) veya markof rastgele alanı (markov random field) gibi yapıları modellemek ve mesaj geçirmek (message passing) aracılığı ile çözümlemektir. Yapısal olarak bir şekil (graph) üzerinde çalışan bu algoritmaların üzerinde çalıştığı şekillere çarpan şekli (factor graph) ismi de verilmektedir.

Konuyu anlamak için, aşağıdaki fonksiyonu ele alalım:

Bu fonksiyonun çarpan şekli aşağıda verilmiştir:

Şekilde görüldüğü üzere fonksiyonun parametreleri ve fonksiyonu oluşturan alt fonksiyon çarpımları arasındaki ilişkiler modellenmiştir.

Öncelikle mesaj geçirme işlemini anlamamız gerekir. Bunun için yukarıdaki fonksiyon üzerine yani f(a,b,c,d) fonksiyonu üzerine toplam çarpım yöntemini uyguluyoruz. Burada kullanacağımız ilk formül:

Kısaca anlatacak olursak, her i. elemena mesaj geçirme işlemi için i. elemanı dışlar şekilde bütün fonksiyonların toplamıdır. Yani f(a,b,c,d) fonksiyonunu oluşturan çarpanların hepsi için ayrı ayrı parametrelerin etkileri toplanır.

Yukarıdaki denklemde bulunan çarpım kısmını da açmakta yarar var:

olarak yazılan kısımda, her parametre için, o parametrenin ilgili olduğu fonksiyonların çarpımı alınır. Diğer bir deyişle örneğin f(a,b,c) fonksiyonunda b parametresi ile ilgileniyorsak, b parametresi bulunmayan çarpan fonksiyonları ile ilgilenmeyiz.

Şimdi yukarıdaki gösterimler ışığında f(a,b,c) fonksiyonu üzerinde mesaj geçirimini göstermeye çalışalım. Örneğin gösteriminin açık halini yazarak başlayalım:

olacaktır ve fonksiyonu bu denklemde bulunmayacaktır çünkü a parametresini içermemektedir. Benzer şekilde diğer fonksiyonları yazacak olursak:

olarak yazılabilir. Şimdi bu fonksiyon çarpanlarının toplam değerlerini alacak olursak:

yukarıdaki şekile yazılabilir. Burada dikkat edilirse, d geçen terimler (ki sadece f1’dir) toplandıktan sonra bu fonksiyon içerisinde b de geçtiği için b toplamına dahil edilmiştir. Benzer şekilde içerisinde a geçtiği için c,b ve d toplamlarının tamamı, a toplamına dahil edilirken, c toplamına b ve d toplamları alınmamıştır. Bunun sebebi b ve d toplamlarında bulunan fonksiyonlarda c değeri geçmiyor olmasıdır.

Buradaki algoritma aşağıdaki şekilde yazılabilir:

Çarpma Kuralı:

Bir değişken düğümünde, çocukların çarpımını al

Toplama Kuralı:

Bir fonksiyon düğümünde, f fonksiyonunun çocuklarının çarpımını al ve f’in atası üzerinde eksik-toplam kuralını uygula.

Bu modellemede bir mesaj geçirme (message passing) işlemi yapılmak istenirse, ve örneğin a parametresinde mesaj toplanacak olursa, aşağıdaki şekilde bir ağaç elde etmek mümkündür:

Yukarıdaki bu ağaca toplam-çarpım algoritmasını uygulayacak olursak durum aşağıdaki şekilde gösterilebilir (toplam kuralı):

Öncelikle her parametreye taşınan eksik toplamlar hesaplanır. Yukarıdaki şekilde b ve d parametreleri için de benzer bir taşıma yapılmıştır. Ancak şayet bu değerler yoksa, yani b ve d parametrelerini etkileyen başka fonksiyonlar yoksa bu değerler alınmaz. Yukarıdaki f(a,b,c) fonksiyonumuz için böyle bir durum söz konusu değildir dolayısıyla bu değerler yok hükmündedir ancak konunun anlaşılması açısından bu değerler şekilde gösterilmiştir.

Ardından her parametre için ilgili fonksiyonun çarpım değerleri hesaplanır (çarpım kuralı):

Sonuçta elde edilen değer kırmızı okla gösterilen çıkış değeridir. Bu değer a parametresi için hesaplanmışıtr. Hesaplanan parametre değişmesi halinde çıkış bu parametreden alınacaktır.


Bir cevap yazın

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