Yazan : Şadi Evren ŞEKER

Bu yazının amacı, günümüzde sıkça internet bağlantısı için tercih edilen ADSL teknolojisini açıklamaktır. ADSL kelimesi, ingilizce Asymmetric Digital Subscriber Line kelimelerinin baş harflerinden oluşmaktadır ve Türkçede asimetrik dijital üye hattı gibi bir terim ile karşılanabilir.

Teknolojinin en belirgin özelliği, giden ve gelen verilere ayrılan bant genişliklerinin simetrik olmamasıdır. Yani örneğin indirme (download) için 1Mbit hat tahsisi yapılırken yükleme (upload) için 256Kbit hat tahsisi yapılıyor olabilir. Bu açıdan, genelde indirme (download) ağırlıklı kullanıcılardan oluşan ev kullanıcıları için oldukça cazip bir teknolojidir.

Teknoloji basitçe bakır telefon hatları üzerinden çalışabilir. Frekans paylaşımlı bir ortamda (frequency division multiplexing (FDM)) veri iletimi olduğu için, telefon hattı üzerinde, aynı anda hem telefon konuşmaları hem de veri iletimi gerçekleştirilebilmektedir. Yani veri iletişimi için ayrılan bant genişliğinin farklı frekansları veri ve ses için farklı olarak tahsis edilir. Bu durumu, aynı anda farklı frekanslardan yayın yapan radyo sinyallerine benzetmek mümkündür. Aslında herhangi bir FM alıcısı radyo, bütün frekansları o anda almaktadır ancak sadece ayarlanmış olduğu frekanstaki gelen sinyalleri sese dönüştürerek dinlememize imkan sağlar. Diğer frekansları almak istiyorsak, diğer frekanslara ayarlı farklı radyolara ihtiyaç duyarız.

Benzer durum telefon hattı üzerinden taşınan veriler için de geçerlidir. Uygun alıcı ayarı yapıldıktan sonra, hatta taşınan ses veya veri kısmı ayrıştırılabilir. Bu ayrıştırma işlemi ayırıcı (splitter) ismi verilen özel bir donanım ile yapılmaktadır.

Yukarıdaki şekilde görüldüğü üzere tek bir bakır kablo hattıyla taşınan veri ve ses hatları, splitter marifeti ile iki ayrı hatta bölünmekte ve hatlardan birisi telefona diğeri ise veri iletişimi için bilgisayara veya ADSL MODEM’e yönlendirilmektedir.

Santral tarafında, hem ses hem de veri birleştirilerek aynı hatta indirgenir. Yani evimize kadar gelen bakır kabloların aynı anda hem internet verisi hem de konuşma verisini taşıması için, ses verilerinin geldiği telefon santrali ile internet verilerinin geldiği yönlendirici (router) aynı hatta ve farklı frekanslarda birleştirilmelidir. Bu birleştirme işlemi DSLAM (Digital Subscriber Line Access Multiplexer) ismi verilen ve Türkçede “dijital abone hat erişimi çoklayıcısı” olarak çevrilebilecek bir ilave cihaz ile yapılmaktadır.

Yukarıdaki resimde, bir DSLAM sunucusu ve üzerinde bağlı olan modemler görülmektedir.

Bu işlem, genelde telefon firması tarafından telefon hattının bağlı bulunduğu santralde yapılmaktadır. Ayrıca her telefon hattı için santral kısmında ilave bir modem bulundurulmaktadır.

ADSL teknolojisi

Yukarıdaki giriş kısmından sonra teknolojinin çalışma detaylarına girebiliriz. Teknoloji basit olarak FDM veya TDM yaklaşımlarından birsini kullanır. Yani veri farklı frekans aralığından kesintisiz olarak veya farklı zamanlarda paylaşımlı olarak iletilmektedir.

Her iki teknoloji tercihi için de yükleme akışı (upstream) için ayrılan aralık, indirme akışı (downstream) için ayrılan aralıktan çok daha azdır (genelde ¼ oranında).

Örneğin frekans paylaşımı yapılan bir ortamda, annex A tipi iletişim için yükleme akışına 26,000 ile 137,825kHz arasındaki frekans bandı ayrılırken, indirme akışı için çok daha geniş bir aralık olan 138kHz ile 1104kHz arasındaki bant ayrılmaktadır.

ADSL teknolojisi, bu alanları da daha küçük parçalara bölmektedir. Yaklaşık 4.3kHz genişliğindeki bu alt kanallara terminolojide kutu anlamında “bin” ismi verilmektedir.

ADSL teknolojisi, iletişim kurma aşamasında her bini ayrı ayrı test etmekte ve SNR (signal to noise ratio, sinyal gürültü oranı) değerlerine göre bu binleri kullanıp kullanmamaya karar vermektedir. Genelde mesafeye bağlı olarak gürültünün artacağını düşünürsek, ADSL teknolojisinin neden mesafeye bağlı olarak hızının değiştiği anlaşılabilir. Yani mesafe arttıkça bazı binler daha gürültülü olduğu için kullanıma kapatılacak ve neticede de kullanılabilir bant genişliği düşecektir.

Ayrıca ADSL MODEM’ler, gönderim veya alım için bant genişliğini farklı değerlerle bu binlere dağıtabilmektedir. Örneğin bir bin’in taşıyacağı veri diğerine göre 2 veya 3 misli fazla olabilir. ADSL MODEM bu değerlere yapmış olduğu SNR testlerine göre karar vermektedir.

ADSL2+ teknolojisinde ise her binde tek bit taşıma yaklaşımı kullanılmaktadır. Bu yaklaşımda gürültülü binler hiç kullanılmaz.

Bu aşamada ADSL teknolojisi muhafazakar bir yaklaşımla bit per bin (bin başına bit) değerini düşük tutabilir. Bu yaklaşımda veri iletişiminin yavaşlaması baştan kabul edilmiş olunur ancak amaç, iletişim sırasındaki veri kaybını asgariye indirmektir. Öte yandan biraz daha cesur bir yaklaşımla daha yüksek bin başına bit değeri ile daha fazla veri transferi ve dolayısıyla daha hızlı bir iletişim hedeflenebilir. Ancak bu durumda verinin kaybolma riski daha da artacaktır. İşte bu durumda daha üstte çalışan TCP/IP gibi protokoller paket kayıpları yaşayacağından verinin tekrar ve tekrar yollanması yüzünden hızın yine yavaşlaması söz konusu olabilecektir. Burada iki uç arasında dengeli bir seçim yapılması en hızlı çözümü getirecektir.

ADSL2+ teknolojisi burada dikişsiz oran uyumu (seamless rate adaptation (SRA)) ismi verilen bir çözüm önermektedir. Bu çözüme göre iki taraf arasındaki bin başına bit haberleşmesi çok daha az iletişim ile çözülebilmektedir. Yani ADSL teknolojisi üzerinden iletişim halinde olan taraflar (ev kullanıcısı ve ADSL sunucusu) ilgili bin başına ayrılan bit değerini değiştirmeye karar verdiklerinde bu bilginin iki taraf tarafından da bilinmesi gerekmekte ve bu bilginin taraflar arasında taşınması çok daha az haberleşme aşamasında sağlanmaktadır.

ADSL teknolojisini iyileştirmek için denenen yollardan birisi de, ADSL için ayırlmış olan özel frekans aralıklarının ötesindeki frekansların kullanılmasıdır. Bu yaklaşımda birinci problem, iki tarafta da (ADSL kullanıcısı tarafında da) özel bir cihaz bulunması ve bu yüksek frekans değerlerini algılaması gerekliliğidir. Bu ilave bir maliyet getirir.

Ayrıca ADSL verisinin telefon hatları üzerinden taşındığı unutulmamaldır. Dolayısıyla çoğu yerde birbirine yakın geçen telefon hatları üzerinden yüksek frekans değerlerinde veri iletimi, çoğu zaman çarpraz konuşma (crosstalk) ismi verilen ve bir kablodaki veri iletişimi sırasında oluşan manyetik alanın diğer hatta etkilemesi olarak anlaşılabilecek problemin doğmasına sebep olur.

42 views

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.

51 views

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.

30 views

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, şekil teorisinde (graph theory) kullanılan sargısız ağaç (unwrapped tree) kavramını açıklamaktır. Şekil teorisi üzerine kurulu pek çok çalışmada sıkça geçmekte olan bu kavram, basitçe şeklin ifade ettiği değerlerin sadeleştirilmesi ve şekildeki döngülerin açılarak şeklin bir ağaca dönüştürülmesinden ibarettir.

Konuyu basit bir döngüyü (cycle) açarak anlamaya başlayalım:

Yukarıdaki şekli sargısız hale getirmek için öncelikle bir düğüm seçilerek işe başlanır. Biz örneğimizde A düğümünü (node) kök düğüm (root) olarak seçerek başlayalım ve bu düğümün komşuluk ilişkisini bir ağaç şeklinde gösterelim:

Şekilde görüldüğü üzere A düğümü ve bu düğümün komşuları ile olan ilişkisi modellenmiştir. Bu ilişkide daha sonra tekrar edecek düğümleri karıştırmamak için düğümlere isimlerinin yanında bir de sayılar ekleyelim:

Şimdi yukarıda, komşuluk ilişkileri henüz işaretlenmemiş olan D1 ve B1 düğümlerinin de komşularını işaretleyelim. Bu işaretleme sırasında dikkat edeceğimiz bir husus, orjinal şeklimizde olan ve D-A ve B-A bağlantılarının geldiğimiz yön itibariyle şeklin son halinde ifade ediliyor olduğudur. Yani zaten D ve B düğümlerine, D-A ve B-A kenarlarını dolaşarak geldik. Bu gelinen kenarlardan bir kere daha geçmiyoruz. Dolayısıyla bu ilişkiler ikinci kere gösterilmez. Bunun yerine henüz gösterilmemiş olan D-C ve B-C ilişkilerini gösteriyoruz.

Şekilde iki farklı C değeri bulunduğu için ikisini de farklı sayılar ile ifade ettik. Zaten bu noktada dikkat edilirse bir şeklin nasıl sargısız hale getirildiği anlaşılır. Yani her farklı komşuluk düğüm kopyalaması ile farklı bir ilişki olarak ifade edilmiştir. Aynı yaklaşımla devam edersek, aşağıdaki şekli elde ederiz:

Şeklin bu son halinde iki yolu sırasıyla yazacak olursak,

A-D-C-B yolu solda

A-B-C-D yolu ise sağda görülmektedir. Devam edelim:

Son halinde şekil yeniden A düğümüne ulaşmıştır. Bu noktada bazı kaynaklar durarak bu sargısız hale getirmenin yeterli olduğunu savunur ve bu açılmış şekil üzerinden işlem yapar. Bazı kaynaklar ise sonsuza kadar giden bir zincir (yol, path, chain) oluştuğunu kabul eder.

Kısacası, şekil, başlangıç düğümüne gelinene kadar iki farklı yönde dönülüyor:

Yukarıdaki şekilde görülen saat yönündeki dönme neticesinde, sargısız düğümün sağ kolu ve bu yönün tam tersi istikametteki dönme neticesinde de sargısız şeklin sol kolundaki yol (path) ortaya çıkmaktadır.

Yukarıdaki açılımı basit bir döngü (single cycle) için yaptık ancak birden fazla döngü bulunması hali de incelemeye değer. Örneğin aşağıdaki şekli ele alalım:

Bu yeni şekilde, tahmin edileceği üzere oldukça büyük bir ağaç çıkacaktır. Bu yüzden bir iki seviye ilerleyerek ağacın nasıl açılıdğını gösterip bırakacağım. Başlangıç düğümü olarak (kök düğüm, root) A seçiyorum. Bu düğümün farklı şekillerde seçilebileceğini hatırlayınız:

Şekli ilerletirsek, aşağıdaki gibi bir durum ile devam ederiz:

Elbette şeklin, bundan sonra da ilerletilmesi mümkündür ancak şekil bir iki seviyede çok hızlı bir şekilde genişlemektedir, konunun anlaşıldığını düşünerek bu seviyede kesiyorum.

12 views

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, hesaplama algoritmaları ve istatistiksel çalışmalara temel teşkil eden çarpan şekillerini (factor graph) açıklamaktır.

Çarpan şekilleri, özel bir şekil (graph) tipidir ve özellikle toplam çarpım algoritmalarının (sum-product algorithms) temelini oluşturur. Ayrıca hata düzeltme (error correction) konusunda da önemli bir yere sahiptir.

Tanım itibariyle iki parçalı şekillerin (bipartite graph) bir hali olan çarpan graflarının (factor graphs) göstermeye çalıştıkları esas unsur bir fonksiyonun çarpanlarıdır.

Örnek olarak bir fonksiyon ve bu fonksiyonun çarpanlarını ve bu çarpanların şekilde nasıl gösterildiğini açıklayalım:

Örneğin elimizde 3 parametre alan bir fonksiyon bulunsun:

şeklinde bu fonksiyonu gösterelim. Bu fonksiyonun çarpanları da aşağıdaki şekilde olsun:

Yani fonksiyonumuz 4 ayrı farklı fonksiyonun çarpımı şeklinde yazılabiliyor olsun.

Yukarıdaki bu durum aşağıdaki şekildeki gibi gösterilebilir:

Yukarıdaki şekilde görüldüğü üzere, graf hem iki parçalı (bipartite) hem de yönsüz olma özelliği taşır. Ayrıca her fonksiyon kendi parametreleri veya ters bir bakış açısıyla her parametre, kendi fonksiyonları ile ilişkilendirilmiştir.

Daha somut bir örnek olarak aşağıdaki klasik fonksiyonu ele alalım:

Yani g(x,y) fonksiyonu iki ayrı fonksiyon olan aşağıdaki fonksiyonların çarpımı şeklinde yazılmıştır:

Yukarıdaki bu fonksiyonun, çarpan grafiği aşağıdaki şekilde çizilebilir:

Yukarıdaki bu gösterimin toplam-çarpım ağlarında (sum product nets) kullanılmasının sebebi de bütün elemanların işlenebilir olmasıdır.

Buradaki gösterimde anlatılmak istenen verilen parametredeki g fonksiyonunun verilen parametre dışındaki bütün elemanların çalıştırılarak toplanmasından ibaret olduğudur. Yani bu toplam işleminde verilen parametre ile ilgili fonksiyonlar dışındaki bütün fonksiyonlar çalışacaktır.

Çarpan şekillerinin önemli bir özelliği ise, Hammersley-Clifford teoremi tarafından gösterilmiştir. Bu teoreme göre herhangi bir markof rastgele alanı (markov random field) veya bayez ağı (bayesian network), bir çarpan şekli (factor graph) ile gösterilebilir.

26 views

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, fizik ve istatistik konularında sıkça geçen ve çoğu bilgisayar bilimleri konusuna temel teşkil eden Markof Rastgele Alanlarını (Markov Random Field) anlatmaktır.

Esas itibariyle markof rastgele alanları, markof ağının (markov network), bir yönsüz şekil üzerine (undirected graph) uygulanmış halidir.

Markof rastgele alanları, bu anlamda bayes ağlarına (bayesian network) benzetilebilir. Bayes ağlarında, bulunan şekiller (graph) yapısal olarak yönlüdür. Markof rastgele ağları ise yönsüz şekillerden oluşmaktadır. Bununla birlikte, bayes ağlarında gösterilemeyen bazı özellikler markof rastgele ağlarında gösterilebilir. Örneğin markof rastgele ağları dairesel (cyclic) olabilmektedir. Ancak bayes ağları ağaç yapısında olup yönlü ve dairesel olmayan (directed acyclig grapch) özelliği göstermektedir.

Buna karşılık bayes ağları yönlü olmalarından dolayı tümden gelim (reduction) veya tüme varım (induction) gibi yönler belirtebilir. Ancak markof rastgele ağlarında bu imkan yoktur.

Olasılık dağılımının artı olması durumu da özel olarak Gibbs rast gele ağı (gibbs random field) olarak isimlendirilir. Bu anlamda Gibbs rastgele ağları, markof rastgele ağlarının özel bir halidir.

Yapay zeka (artificial intelligence) çalışmaları açısından markof rastgele ağları çeşitli düşük ve orta seviye işleri ifadede kullanılabilir. Örneğin bir problemin parçalara ayrılması, problemin olasılıksal olarak modellenmesi, arama ağaçlarının oluşturulması gibi durumlarda kullanılabilir.

İstatistiksel Tanımı:

İstatistiksel olarak alanın tanımı aşağıdaki şekilde yapılabilir:

G= (D,K) olarak tanımlı bir graf için bir rastgele olay A = ( A _D) _{D ∈ K}

olarak tanımlı olsun. (Buradaki D, düğüm(vertex), K, kenar(edge) olarak tanımlanmış olsun).

Yukarıdaki tanıma ilave olarak aşağıdaki markof özelliklerinin bulunması gerekir:

Çifte Markof Özelliği (Pairwise Markov Property): Herhangi iki komşu olmayan olay, koşullu bağımsızlık (conditionally independent) göstermelidir.

Yerel Markof Özelliği (Local Markov Property) : Bir olay, komşularının tamamyla koşullu bağımsız (conditionally independent) olmalıdır.

Genel Markof Özelliği (Global Markov Property) : Olaylardan oluşan iki alt küme için birbiri ile koşullu bağımsız (conditionally independent) olma zorunluluğu vardır.

Örnek:

Yukarıda açıklananları bir örnek markof rastgele alanı tanımlayarak açıklayalım:

Örnğein yukarıdaki şekilde bir alan verilmiş olsun. Bu alanın özellikleri aşağıdaki şekilde yazılabilir:

Görüldüğü üzere markof rastgele alanı, yönsüz olarak tanımlanmıştır ve ilişki içerisinde bulunan düğümler (node) arasındaki olasılık tanımları yukarıdaki olasılık fonksiyonunda ifade edilmiştir. Yukarıdaki bu basit alanı biraz daha ilerletelim ve farklı bir örnek üzerinden konuyu anlatalım:

Yukarıdaki şekilde, örnek bir alan gösterilmiştir. Bu alanda, birden fazla eleman bir hipergraf (hypergraph, ileri şekil) olarak bağlanmıştır. Buna göre üç bağlantı kümesi aşağıdaki şekilde listelenebilir:

K1 = {A,D,C}

K2 = {B,C}

K3 = {B}

Yukarıdaki kümeler için tanımlı olan markof alanının olasılık özelliği aşağıdaki şekilde yazılabilir:

Görüldüğü üzere üç farklı ilişki kümesi için üç farklı fonksiyon tanımı ve her fonksiyon tanımı için ilgili düğümlerin parametre geçirilmesi yeterlidir.

İkili Markof Rastgele Alanları (Pairwise Markov Random Fields)

Markof rastgele alanlarının özel bir hali olan bu alanlarda, sadece ikili ilişkilere veya tekli ilişkilere izin verilir. Buna göre iki grupta öğe bulunduran alanların olasılık fonksiyonlarını aşağıdaki şekilde modellemek mümkündür.

Yukaırdaki gösterimde, g fonksiyonu tekli elemanları, f fonksiyonu ise ikili elemanları ifade etmektedir. Buna göre bütün elemanların (ikili veya tekli) çarpımı, olasılık fonksiyonunu oluşturmaktadır. Burada dikkat edilmesi gereken ilişkisi bulunan elemanların fonksiyon değerlerinin çarıpldığıdır.

Ayrıca dikkat edilmesi gereken bir özellik, markof rastgele alanlarının yönsüz olduğudur. Diğer bir deyişle şayet ikili ilişki (pairwise) bulunuyorsa, bu durumda aşağıdaki eşitlik geçerli olur:

Yani fonksiyonun taınm sırası önemli değildir. Bu özellik aşağıdaki şekilde de yazılaiblir.

Yani fonksiyonlardaki sıranın bir önemi yoktur.

26 views

Bu yazının amacı, matrislerin determinantını (masfuf muheddedad, matrix determinant) nasıl hesaplandığını anlatmaktır.

Konuya basit matrisler ile başlayalım. Örneğin 2×2 boyutundaki bir matris için:

basitçe det(A) = ad – bc şeklinde hesaplanabilir buradaki hesap aşağıda gösterilen iki ok yönünden sağı göstereni + ve solu göstereni – alarak hatırlanabilir:

Şekilde görüldüğü üzere mavi okun üzerinden geçtiği elemanlar ad ve kırmızı okun üzerinden geçtiği elemanlar cb olmaktadır ve determinant ad-cb şeklinde hesaplanmaktadır.

Determinant hesaplanırken matrisin köşeli parantezleri yani [] sembolleri yerine düz parantezler yani || sembolleri kullanılır.

olarak yazılabilir.

3×3 boyutundaki bir matrisin determinantı yine benzer şekilde oklar kullanılarak hesaplanabilir.

Genel olarak herhangi boyuttaki bir matrisin determinantı ise aşağıdaki formül ile hesaplanabilir:

Yukarıdaki gösterimde, kısaca bir matrisin nxn boyutunda olduğu kabul edilmiş ve öncelikle y sembolü kullanılmıştır. Buradaki y sembolü yer değiştirmeyi (permutation) ifade etmektedir. Yani y_i demek, i.nci değiştirme (permütasyon) demektir. Örnek olarak elemanlarımız 1,2,3 ise ve yerdeğiştirme dizilimi aşağıdaki şekildeyse:

1,2,3

2,3,1

3,1,2

2,1,3

1,3,2

3,2,1

Bu dizilimdeki her elemana bir numara verildiğinde yi gösterimindeki i değerine göre bir gösterim ifade ediliyor demektir. Örneğin i=5 için yukarıdaki gösterimlerden 5. sıradakini anlayabiliriz ki bu da 1,3,2 gösterimidir.

Denklemde yer alan diğer bir gösterim ise yön() fonksiyonudur. Basitçe +1 veya -1 döndüren bir fonksiyondur ve aşağıdaki şekilde ifade edilebilir:

Kısacası aldığı parametrenin teklik/çiftliğine göre + veya – döndüren fonksiyondur.

Çarpım sembolü ile ifade edilen terim ise yukarıdaki 2×2 veya 3×3 boyutlu matrislerde gösterilen ve çarpılarak daha sonra toplanan veya çıkarılan her bir terim için kullanılmıştır.

Örnek olarak yukarıdaki dizilimleri ele alacak olursak aşağıdaki şekilde 3×3 boyutundaki bir matirisin determinantını hesaplayabiliriz:

Yukarıdaki yaklaşımda, ilk satırda bulunan sayılar kapatılıp kalan alandaki matrislerin determinantı ile çarpılmıştır. Ayrıca çarpma işlemi sırasında bir artı bir de eksi yönde ilerlenmiştir.

Örneğin 5 çarpanı için:

5 sayısının bulunduğu satır ve sütun kapatılıp kalan satır ve sütunlardaki matris alınmıştır. Benzer şekilde 3 sayısı için:

3 sayısının bulunduğu satır ve sütundaki sayılar kapatılır ve geri kalan sayılardan oluşan matris okunur.

Bu şekilde alt matrisler elde edilir ve bu alt matrisler ise kapanan sayı sabit çarpıma (scalar multiplication) tabi tutulur.

Neticede çıkan sonuç toplanır. Yani yukarıdaki örnekten devam edilecek olursa

5( 4 . 4 – 9 . 6 ) – 3( 2 . 4 – 9 . 3 ) + 7 ( 2 . 6 - 4 . 3)

olur Bu işlemin sonucu da

-133

olarak bulunur.

Yukarıdaki bu genel hesaplama formülüne göre kodlaması aşağıdaki şekilde yapılabilir:

Yukarıdaki kodun ekran çıktısı aşğaıdaki şekildedir:

Kabaca kodu açıklayacak olursak. Determinant fonksiyonu bir integer matris parametre olarak almaktadır. Koddaki ilk 2 if (4. ve 8. satırlardaki) özel matris determinantı için kullanılır. Yani matrisin boyutunun 1×1 veya 2×2 olması durumları içindir. Bu hesaplar doğrudan yukarıdaki yazıda anlatıldığı şekliyle yapılır. Yani 1×1 için matrisin yegane elemanı döndürülürken 2×2 için köşegen ve ters köşegendeki sayılar çarpılıp çıkarılarak döndürülür.

Şayet matrisin boyutu 2×2′den daha fazla ise (örneğin 3×3 veya 4×4 gibi) bu durumda matris, yukarıdaki örnek çözümünde olduğu gibi küçük matrislere bölünür ve her eleman için artı ve eksi şekilde sayısal değerler denkleme dahil edilerek hesaplanır.

Kodun 15. satırından başlayan döngü ilk satırı ve ilgili sütunu kapatmakta ve kalan küçük matrisi 25. satırdaki işlem ile özyineli (recursive) olarak tekrar denkleme sokmaktadır. Ayrıca -1 sayısının üstü alınarak yön fonksiyonu kodlanmıştır (-1 sayısının çift üstlerinin + ve tek üstlerinin – olduğunu hatırlayınız).

Kodu indirmek için tıklayınız.

166 views

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, hipergraf (ileri şekil, hypergraph) konusunu anlatmaktır. Matematiksel bir terim olan hipergraf kavramı, bilgisayar bilimlerinin çeşitli alanlarında kullanılmaktadır.

Tanım itibariyle bir kenarın (edge) çok sayıdaki düğüme (node) bağlanabildiği özel şekillerdir. Yani, normalde bir şekilde (graph) bir kenar (edge), iki düğüm (node) arasında tanımlıyken ve bu iki düğümü birleştiriyorken, hipergraflarda istenilen sayıdaki düğümü birleştirebilir. Burada istenilen sayı ile kast edilen normal şekillerde olduğu gibi iki düğüm olabilirken tek bir düğüm de olabilir. Normal şekillerde bir kenar tek bir düğüme bağlı olamaz, mutlaka iki düğüme bağlı olmalıdır ama hipergraflarda tek bir düğüme, üç ayrı düğüme veya yirmi ayrı düğüme bağlı olabilir.

Yukarıdaki şekilde, 5 düğüm (node) ve 3 kenar (edge) verilmiştir. Bu şekildeki kenar kümeleri aşağıdaki şekildedir:

K1: { A, B}

K2: { A, C, E}

K3: { A, B, D, E}

Görüldüğü üzere, bir kenar klasik graftan farklı olarak çok sayıda düğüm içerebilmektedir. Bu durumda M adet düğüm ve I adet kenar içeren bir hipergrafın tanımı aşağıdaki şekilde yapılabilir:

H ( D , K)

Buradaki X, düğümler kümesi ve K ise kenarlar kümesidir. Ancak belirtmek gerekir ki K, aslında bir kümeler kümesidir. Yani K’nın her elemanı D’nin alt kümesinden oluşan bir kümedir.

Normal bir şekilde (graph)

G ( D, K)

şeklinde yapılan tanımda, K kümesi ikili elemanlardan oluşan bir kümeyken, bir hiper graf için eleman sayısı asgari 1 ve azami M olan kümelerden oluşan bir kümedir.

Bu durum aşağıdaki şekilde taınmlanabilir:

H ( D , K ) için

Yani diğer bir deyişle, D kümesindeki elemanlar M düğüm için 1′den M’e kadar dm ile gösterilirken, K kümesindeki elemanlar 1′den I’ye kadar ki ile gösterilmektedir. Ayrıca hiper grafın en önemli özelliği olan ki’lerden oluşan küme, D kümesinin herhangi bir alt kümesi olabilir.

Klasik şekillerde (graph) alt şekil (subgraph) tanımı yapılabildiği gibi, hiper graflar için de benzer tanımlamalar yapmak mümkündür. Ancak ancak, hipergraflarda, kenarların belirlediği sayısallık (cardinality) değerleri farklılık gösterdiği için birden fazla alt şekil (subgrah) tanımına ihtiyaç duyulmuştur. Bu tanımlar aşağıda, başlıklar halinde sunulmuştur.

Alt HiperGraf (Sub HyperGraph):

Ayrıca literatürde geçen alt hiper graf ( sub-hypergraph) kavramı, bir hiper grafın düğümlerinin bir kısmının içerilmediği hiper graftır. Örneğin yukarıda verilen hiper grafa H1 diyecek olursak ve bu hipergraftan C düğümünü çıkardığımız yeni hiper grafa H2 diyecek olursak. H2 hipergrafı, H1 hipergrafının bir alt hiper grafıdır denilebilir:

Şekilde görülen yeni hiper graf için kenar kümelerinin yeni tanımı aşağıdaki şekilde olacaktır:

K1: { A, B}

K2: { A, E}

K3: { A, B, D, E}

Bu yeni hipergrafta, normal bir hipergrafın taşıdığı bütün özellikler bulunmaktadır. Buna göre bir althipergraf aşağıdaki şekilde tanımlanabilir:

Yukarıdaki tanımda, normal bir hipergrafın düğümlerini gösteren D kümesinin bir alt kümesi olan A kümesi tanımlanmıştır ( ) ve buna göre kenarlar kümesi bu A alt kümesinde bulunan düğümleri bir şekilde ilgilendiren alt küme olmaktadır. Öyleki, şayet bu kenarlar alt kümesi D\A için boş kümeye dönüşüyorsa, bu küme alınmaz. Yani D kümesinden çıkarılan düğümlerden sonra herhangi bir kenar kümesi boş küme oluyorsa, bu kenar alt hipergrafta bulundurulmaz.

Kısmi HiperGraf (partial hyper graph):

Bir hiper grafın bazı kenarlarının olmadığı hiper graflara verilen isimdir.

Örneğin yukarıdaki yeni hipergrafta, K1 kenarı bulunmamaktadır. Bununla birlikte bütün düğümler (nodes) tam olarak yer almaktadır. Yukarıdaki hiper grafa H3 ismini verecek olursak, H3, H1′in bir kısmi hipergrafıdır denilebilir. Bu hiper grafta bulunan kenar kümeleri aşağıdaki şekilde tanımlanabilir:

K2 = {A, C , E }

K3 = {A, B , D , E}

Bu tanıma göre, şayet tanımı yapılırsa,

şeklinde bir kısmi hiper graf tanımlanabilir.

Bölgesel Hiper Graf ( Section Hyper Graph):

Bu kavram, hem kısmi hem de alt hipergraf kavramlarının birleşimidir. Yani hem kenar hem de düğümler, Orijinal hiper grafın alt kümesi olarak kabul edilebilir.

Yukarıdaki şekilde, hem bir düğüm eksik ( C düğümü) hem de bir kenar eksiktir (K1 kenarı) bu durumda bu hiper graf, Orijinal hiper grafın ne kısmi ne de alt hiper grafıdır. Bunun yerine bölgesel hipergrafıdır terimi kullanılır.

İki parçalı graflar (bipartite graph)

Herhangi bir H hipergrafı, iki parçalı graf (bi-partite graph) olarak gösterilebilir. Bunun için D ve K kümelerinin iki parçalı graftaki bölümleri ifade etmesi gerekir.

Herhangi bir düğüm d için, sadece tek bir kenar k tarafından içerilmelidir.

40 views

Yazan : Şadi Evren ŞEKER

Vurma zamanı (hitting time) kavramı, rastsal süreçlerin (stochastic processes, stokastik olaylar), verilen bir alt küme ile birleştiği zamanı işaret eder.

Örneğin yazı tura oynayan bir tarafın, ilk yazı gelmesi haline bir vurma zamanı, yani gelebilecek olasılıkların bir alt kümesini ilk defa yakalama zamanı olarak tanımlayabiliriz.

Bu zamanlara bazı kaynaklarda, çıkış zamanı veya dönüş zamanı (exit time, returning time) isimleri de verilmektedir.

Diğer bir örnek zar atarken zarın ilk defa 3 gelmesi olabilir. Veya zar atarken, zarın 4′ten büyük gelmesi de olabilir. Yani, bir rastsal sürecin tanımlı olduğu etki alanında (domain) bir alt küme tanımlanır ve bu alt kümeye ulaştığı ilk ana, vurma zamanı ismi verilir.

İstatistiksel olarak tanımı aşağıda verilmiştir:

T bir sıralı fihrist kümesi (index set) olmak üzere herhangi bir t∈ T durumunu sağlayan pozitif reel sayılar için yani [0,+∞) kümesi için, bir S olasılık uzayı tanımlanır. Bu uzay, (Ω,Σ,Pr) şeklinde gösterilebilir ve bu uzaydaki rastsal süreç, X:Ω× T→ S şeklinde yazılabilir. Şimdi bu S uzayında A isminde bir alt uzay ııtanmlayalm. Bu alt uzaydaki ilk vurma zamanı (hit time) τ _A:Ω→[0,+∞] şeklinde tanımlanabilir.

Yani rastsal sürecin bizim tanımladığımız alt kümeye girdiği ilk zamandır.

İlk çıkış zamanı (first exit time) ise yine tanımlı olan alt küme için (yukarıdaki tanıma göre A), yukaırdaki tanımın eşleniğidir (tersi, complement). Yani A kümesinin S kümesinden farkı (ki S kümesinde tanımlı A kümesi dışındaki kümedir) için yukarıdaki tanımın aynısı geçerlidir. B: A\S olarak tanımlanırsa,

31 views

Yazan: Şadi Evren ŞEKER

Bu yazının amacı, istatistikte geçen ve bilgisayar bilimlerinin çeşitli konularının anlaşılması için gereken koşullu olasılık dağılımını (conditional probability distribution) açıklamaktır.

Koşullu olasılık dağılımı iki rast gele değişken (random variable) üzerinde tanımlıdır.

Tek cümle ile tanımlanacak olursa, A olayının B olayına koşullu olasılık dağılımı (probability distribution) olarak tanımlanabilir.

Diğer bir deyişle A ve B olayları için, B olayı biliniyorken, A olayının olasılık dağılımıdır.

Şayet olayların dağılımı kesikli ise (discrete) bu durumda olasılık yoğunluk fonksiyonu (probability density function) şayet sürekli ise (continous) bu durumda da koşullu yoğunluk fonksiyonu (conditional density function) hesaplanabilir.

Örnek:

Örneğin eşit sayıda kırmızı ve mavi toplar olan iki torbadan top çekilecek olsun, bu olaylardan birisi A diğeri B olayı olarak düşünülebilir. A olayı için %50 ihtimalle kırmızı ve %50 ihtimalle mavi gelme olasılığı vardır. Aynı durum B olayı için de geçerlidir. Dolayısıyla A ve B olayları için aşağıdaki durum söylenir:

A=kırmızı, B=kırmızı : %25

A=mavi, B=kırmızı : %25

A=kırmızı, B=mavi : %25

A=mavi, B=mavi : %25

Ancak yukarıdaki olaylardan birisi biliniyorsa. Örneğin B’nin kırmızı geldiğini biliyorsak, bu durumda olasılıklar aşağıdaki şekilde değişir:

A=kırmızı, B=kırmızı : %50

A=mavi, B=kırmızı : %50

Diyelim ki yukarıdaki top çekme olayını binlerce kere tekrar ettik. Bu durumda A’nın koşullu olasılık dağılımı normal dağılım şeklinde çıkacaktır .

Özellikler:

Kesikli olaylar

Kesikli olaylar için koşullu olasılık formülünü hatırlayalım:

Bu tanımda sıfıra bölünme tanımsızlığını engellemek için P(A=a)>0 olması gerektiğini de hatırlayalım.

Olasılık dağılım fonksiyonunun özellikleri aşağıdaki şekilde yazılabilir:

Buna göre B olayının A olayı verilmesi durumundaki dağılımı gösterilmiş olur.

37 views