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: Belirtilmemiş.
- 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ı: 107
Ö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ÜÇ
- Çok sınıflı medikal görüntü sınıflandırması için melez derin öğrenme yaklaşımları
Hybrid deep learning approaches for the multi class medical image classification
ZELİHA KAYA AKÇELİK
Yüksek Lisans
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFatih Sultan Mehmet Vakıf ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ GÖNÜL ULUDAĞ
- 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
- Performance prediction of implicitly defined estimators of non-random parameters
Rastgele olmayan parametreli örtülü tanımlanan kestirimciler için performans tahmini
ERDAL MEHMETCİK
Doktora
İngilizce
2023
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ÇAĞATAY CANDAN
PROF. DR. UMUT ORGUNER
- 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Ğ