Belief Propogation (İnanç Yayılımı)

Yazan : Şadi Evren ŞEKER

Türkçede inanç yayılması (veya iman neşri) olarak çevrilebilecek belief propagation konusu, bilgisayar bilimlerinde, makine öğrenmesi (machine learning) konusunun altında değerlendirilebilir.

Algoritma ilk olarak Judea Pearl tarafından 1982 yılında yayınlanan makalesinde duyurulmuştur. Pearl, Judea (1982). “Reverend Bayes on inference engines: A distributed hierarchical approach”. Proceedings of the Second National Conference on Artificial Intelligence. AAAI-82: Pittsburgh, PA. Menlo Park, California: AAAI Press. pp.133–1 36.)

Yapı olarak mesaj geçirme (message passing) algoritmalarının bir örneği olarak görülebilir. Buradaki yayılma (neşr etmek, propagation) aslında varlıklar arasında bir mesajın geçişi anlamını taşımaktadır. Literatürde farklı kaynaklarda, toplam-çarpım mesaj geçirimi (sum-product message passing) olarak da geçmektedir. Buradaki mesaj geçişi yapılan varlıklar genelde bir şekil (Graph) üzerinde ifade edilen ve aralarında ilişkiler bulunan varlıklardır.

Esas itibariyle Markov Rastgele Alanları (markov random fields) üzerine kurulu olan inanç yayılımı konusunu bir şekil (graph) üzerindeki varlıkların birbirlerine belirli oranlarla mesaj geçirdikleri bir alan sunmaktadır.

İnanç neşriyatı için öncelikle bir problemin bir ağaç şeklinde nasıl çözülüdüğüne bakalım. Öncelikle bir çarpım şekli (factor graph) ele alıyoruz:

Bu şekilde, diyelim ki a parametresi üzerine inanç neşriyatı uygulayacağız. Bu durumda yukarıdaki şekli, aşağıdaki gibi bir ağaca (tree) dönüştürmek mümkündür:

Yukarıdaki yeni şekilde, dikkat edileceği üzere, bir doğrusal ve dairesel olmayan şekil (directed acyclic graph) elde edilmiştir. Yani şekil, yönsüz şekilden (undirected graph) bir yönlü şekle (directed graph) çevrilmiştir. Bu anlamda şekli bir ağaç (tree) şeklinde ele almak mümkündür. Ayrıca şekilde b parametresi, iki ayrı fonksiyona parametre olduğu için kopyalanarak gösterilmiştir (aslında buna gerek yoktur ancak sadece konu anlaşılsın diye böyle bir yol izledim). Ayrıca sonuca etkisi olmayan f3 fonksiyonu sistemden çıkarılmıştır.

Netice olarak şekildeki 3 fonksiyonun sonuçları a parametresine birer etki olarak taşınacaktır (mesaj geçişi).

Bu anlamda, inanç neşriyatı problemini bir ağaç şeklinde düşünmek ve verilen parametreye göre problemi alt problemlere bölmek mümkündür. Hatta bu alt problemlerin birbirinden bağımsız (independent) olduğunu da söyleyebiliriz.

Yukarıdaki ağaç yaklaşımı üzerinden inanç neşriyatını (belief propagation) açıklamak istersek. Öncelikle iki düğüm (node) ve bir kenar (edge) üzerinde yaklaşımın nasıl çalıştığını göstermemiz gerekir:

Burada anlatılmak istenen, ağ üzerinde varlık gösteren her düğümün sonucunu döndüren bir fonksiyon ve her ilişkinin (kenar) tanımlı olduğu düğümleri aynı anda parametre olarak alan bir fonksiyonun varlığıdır. Yukarıda gösterilmemiştir ancak yine f(b) şeklinde b değerini parametre alan bir fonksiyonun varlığından da bahsedilebilir.

Aslında kenarlar üzerinde ağırlık tanımlanması halinde (ki benzer durumlar yapay sinir ağı (artificial neural network) çalışmalarında veya bayez ağlarında (bayesian network) kullanılmaktadır) bu ağarılık da bir fonksiyon olarak düşünülebilir. Örneğin f(a,b) = 0.2 gibi.

Yukardaki gösterimi biraz daha ilerletecek ve işin içerisine bir de mesaj ekleyecek olursak:

Yukarıdaki yeni şekilde eklenen m değeri, a’dan b’ye geçirilen mesajı ifade etmektedir.

Bu mesaj değeri aşağıdaki şekilde hesaplanabilir:

Buradaki gösterimde kabaca tanımlı olan f fonksiyonlarından yararlanılmış ve şekildeki gösterim bir toplam-çarpım algoritması (sum-product algorithm) olarak ele alınmıştır. Hesaplamada kullanılan geçici p değeri, yukarıdaki a düğümüne etki eden herhangi bir p hesaplamasını ifade etmektedir. Yani a düğümüne kadar gelen etkiler çarpım sembolü ile hesaplanmıştır. Bu durum aşağıdaki şekilde düşünülebilir:

Yani denklemin çarpım sembolü kısmında bu p düğümünün etkisi ile a’ya bağlanan kenardan gelen fonksiyon değerinin a üzerindeki etkisi alınmıştır. Bu şekilde, a’ya etki eden bütün düğüm ve kenar bağlantıları (ki a’ya bağlı sadece p gösterilmiştir ancak başkaları da olabilir) a üzerinde çarpım sembolü ile ifade edildikten sonra geriye a gibi b üzerinde etkisi bulunan bütün düğümlerin toplamlarını hesaplamak kalmıştır. Denklemin toplam sembolü ile gösterilen kısmı da bu toplamayı yapmaktadır.

Yukarıdaki yaklaşımı toplamdan çıkarıp azami değeri alacak şekle getirirsek:

Yeni yaklaşımımızda azami değerler alınarak parametrelerin arasında en büyük değeri yani en aykırı değeri (marginal) bulmak amaçlanmıştır. Bu değerlere aykırı değer veya azami-aykırı değer ( marginal veya max-marginal) ismi verilir. Kısaca aşağıdaki şekilde de gösterilebilir:

Bu anlamda, önce çarpım sembolünü işletmek (iterate) ve bütün değişkenler için bir bir çalıştırmak mümkündür. Her çalışan değişken için aslında sistemden bir değişkenin kaldırıldığını söyleyebiliriz.

Paralel Mesaj Geçirimi

Bu parametre kaldırma işlemini paralel hale getirmek de mümkündür. Yazının başında verilen şekli hatırlayalım:

Bu şekilde bulunan f2 ve f3 fonksiyonları veya f1 ve f3 fonksiyonları, birbirinden bağımsız olarak hesaplanabilir. F1 ve f2 fonksiyonları ise aynı değişkene (b) bağlı oldukları için bazı durumlarda birbirini beklemek zorundadır.

Bu paralel işleme işine de paralel mesaj geçirme (parallel message passing) ismi verilir.

Döngüsel İnanç Neşriyatı (Loopy Belief Propagation)

Gelelim döngüsel inanç neşriyatına (döngüsel inanç yayılımı). Bu yaklaşımda, şekilde bir dairesel (cyclic) özellik olacağı kabulü bulunur. Ancak döngüsel olarak yapılan yaklaşımın her zaman bir noktada toplanması/birleşmesi garanti edilemez.

Hatta bir noktada toplanması mümkün olsa bile, doğru marjinal değerlerde toplanması garanti edilemez.

Örneğin tek döngü içeren aşağıdaki şekli ele alalım:

Bu markof rastgele alanından aşağıdaki sargısız şekli (unwrapped graph) elde etmek mümkündür (okuyucu detayları için http://www.bilgisayarkavramlari.com/2012/05/05/unwrapped-graphs-sargisiz-sekiller/ bağlantısındaki yazıya başvurabilir):

Dolayısıyla yukarıdaki yaklaşım kullanılarak mesaj güncellemesi iki farklı yönde işletilebilir. Buradaki amaç inanç ağının, döngüsel bir markof alanında çalıştırılmasıdır. Çalışmanın başarılı olması için yukarıda gösterildiği gibi sargısız şekil (unwrapped graph) elde edilip üzerinde çalışılabileceği gibi, orjinal markof rastgele alanında da bir yön belirlenerek çalışılınabilir:

Örneğin yukarıdaki ağaç şekili çıkarılırken, A düğümünden başlanarak saat yönünde dönülen bir kol (ağacın sağ kolu) ve bu yönün tam tersi istikamette dönülen diğer bir kol (ağacın sol kolu) çizilmiştir.

Yukarıdaki şekilde bir döngü içeren inanç ağı, kararlı hale (steady state) ulaşana kadar parametre güncellemesi ile işlenir. Yani ağda yayılım (neşriyat, propagation) sürekli devam eder. Neticede kararlı bir hal alır ve durulur.