Analysis of a class of random approximation algorithms for belief networks
Olasılık ağlarının çözümlenmesinde bir rassal yaklaşık algoritma sınıfının incelenmesi
- Tez No: 129372
- Danışmanlar: DOÇ. DR. TANER BİLGİÇ
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Algoritmalar, Olasılık ağları, Yaklaşık çözüm, Algorithms, Probability networks, Approximate solution
- Yıl: 2002
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET OLASILIK AĞLARININ ÇÖZÜMLENMESİNDE BİR RASSAL YAKLAŞIK ÇÖZÜM ALGORİTMASI SINIFININ ANALİZİ Literatürde olasılık ağlarının çözülmesi ile ilgili pek çok kesin çözüm algorit ması vardır. Ancak yüzlerce değişkene sahip gerçek hayat problemlerinin çözülmesi sırasında kesin çözümlere ulaşılması bazen olası değildir. Şartlı olasılıkların kesin çözümünün hesaplanmasının NP-zor olduğu da ispatlanmıştır. Yaklaşık çözüm algo ritmalarının polinomsal derecede kompleks oldukları kabulü ile araştırmacılar verimli yaklaşık çözüm algoritmaları geliştirmeye çalışmaktadırlar. Ancak yaklaşık çözümün uç olasılık değerlerine rastlanması durumunda NP-zor olduğu da ispatlanmıştır. Diğer taraftan pek çok yaklaşık çözüm algoritmasının uç olasılık değerleri olmaması halinde de tökezledikleri görülmektedir. Bu araştırmada bir rassal algoritma (AA Algorit ması) üzerinde çalışılmaktadır. Bu algoritmanın daha önce varolan algoritmalara göre daha geniş ağ çeşitleri için daha iyi yaklaşım gösterdiği ispatlanmıştır. Ancak bu çözümün optimal olduğu koşulun bir sabit c katsayısına bağlı olduğu söylenmektedir. Bu sabit evrensel bir sabit olarak tanımlanmıştır. Ancak bu araştırma c katsayısının ağ özelliklerine bağlı olduğu kabulünü yapmaktadır. Dolayısıyla bu araştırmanın amacı ağ özelliklerine bağlı olan bir c katsayısının bulunmasıdır. Çünkü daha küçük c kat sayılarının kullanımıyla çözüme ulaşmak daha kısa süre alacaktır. Yapılan calşmadaki deneylerin ise yüzde 90'a yakın bir kısmı literatürde önerildiği gibi c için iki yer ine, bir kullanılarak çözülebilmiştir. Dolayısıyla pek çok problem daha kısa sürelerde çözülebilir. Araştırmanın sonucu olarak ise istenen yaklaşım özelliklerine ve de ağ özelliklerine bağlı olarak kullanılabilecek bir c katsayısı hesaplama prosedürü verilmiştir.
Özet (Çeviri)
IV ABSTRACT ANALYSIS OF A CLASS OF RANDOM APPROXIMATION ALGORITHMS FOR BELIEF NETWORK INFERENCE There exist many exact solution algorithms to the inference problem of Belief networks. However, with real life problems having size of hundreds of variables, it is hard to obtain a feasible inference. It is known that the exact computation of con ditional probabilities is NP-hard. Assuming that the approximation of inference can be of polynomial complexity, many researchers try to produce effective approximation algorithms. However, it has also been shown that the solution to the approximate inference problem is NP-hard, when having extreme conditional probabilities. On the other hand, many approximate inference algorithms fail to approximate efficiently even without extreme conditional probabilities. In this research, we are working on a stochastic sampling algorithm, which is called the AA algorithm. This algorithm is shown to guarantee polynomial convergence for a larger class of networks than the previous ones could provide. The approximation is proven to be optimal using a con stant c. This variable is defined as a universal constant, which is dependent on the network properties. Therefore, we aim to find the optimal value of c depending on the network properties. The less the value of c is, the shorter the computation time. The experimental results show that about 90 per cent of the experiments could be solved by using c is equal to one, instead of c is equal to two, as suggested in the literature. So, many experiments can be solved in shorter time periods. Finally, we are describing a procedure to obtain the optimal c value for any given network and approximation conditions based on network and the query properties.
Benzer Tezler
- Markov zincirleri ile pazar payı tahmini ve renkli televizyon pazarına ilişkin bir uygulama
Market share estimation of colored TV with markov chains for the period of 1990-1995
BÜLENT MENGÜÇ
- Uyarlamalı süzgeçler
Adaptive filters
RIDVAN AYSEL
Yüksek Lisans
Türkçe
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. AHMET H. KAYRAN
- Yeni iki global karma optimizasyon algoritması ve bu algoritmaların mikrodalga devrelerin tasarımına uygulanması
New two global hybrid optimization algorithms and their applications to the design of microweve circuits
M.TAYFUN GÜNEL
Doktora
Türkçe
1993
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. BİNGÜL YAZGAN
- Optimal lop kontrol
Başlık çevirisi yok
FÜSUN DEDE
Yüksek Lisans
Türkçe
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. LEYLA GÖREN
- AVO analizi ile deniz tabanının modellenmesi
Modelling of the sea floor by AVO analysis
NESLİHAN OCAKOĞLU
Yüksek Lisans
Türkçe
1997
Jeofizik Mühendisliğiİstanbul Teknik ÜniversitesiJeofizik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. EMİN DEMİRBAĞ