Analysis of a class of random approximation algorithms for belief networks

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye

Tezin Onay Tarihi: 2002

Tezin Dili: İngilizce

Öğrenci: ATALAY ATASU

Danışman: TANER BİLGİÇ

Ö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.