Novel swarm intelligence algorithms for structure learning of bayesian networks and a comparative evalnation

Abstract

Bayesian networks are useful analytical models for designing the structure ofknowledge in machine learning which can represent probabilistic dependencyrelationships among the variables. A Bayesian network depends on; 1.the parametersof the network and 2.the structure. Parameters represent conditional probabilities whilethe structure represents dependencies between the random variables. The structure ofa Bayesian network is a directed acyclic graph (DAG). Learning the structure of aBayesian network is NP-hard but still extensive work have been done to optimizeapproximate solutions. In this thesis, we have conducted research for structure learningto develop algorithms to find a solution to the problem. There are two approaches forlearning the structure of Bayesian networks. The first is a constraint-based approach,and the second is a score and a search approach. One common type of method forBayesian network structure learning is the score-based search. Score-based methodsrely on a function to test how well the network model matches the data, and they searchfor a structure that produces high scores on this function. There are two types ofscoring functions: Bayesian score and information-theoretic score. The Bayesian andinformation-theoretic scores have been implemented in several structure learningmethods. In this thesis, we focused on the score based search for testing the structurelearning of Bayesian network using heuristic methods for searching and BDeu as ascore function. In this thesis we proposed five algorithms for the search part and usedBDeu as a score function. We also proposed a sixth method which is also a natureinspired one. The first proposed algorithm used Pigeon Inspired Optimization as asearch method and the above mentioned score function. The proposed method hasshown a good result when compared with default methods like Simulated Annealing iiiand greedy search. This algorithm is a novel approach applied for structure learning ofBayesian network. The second proposed algorithm used Bee optimization andSimulated Annealing as a hybrid algorithm, which used Bee optimization as a localsearch and Simulated Annealing as a global search. The third proposed algorithm alsoused bee optimization and Simulated Annealing as a hybrid but used Bee optimizationas a global search and Simulated Annealing as a local search. The fourth proposedalgorithm used Bee optimization and Greedy search as a hybrid algorithm. It used Beeoptimization as local search and Greedy as global search. The fifth algorithms alsoused bee optimization and Greedy as a hybrid algorithm, but it used Bee optimizationas a global search and Greedy as a local search Our last proposed algorithm usedElephant Swarm Water Search Algorithm (ESWSA). The thesis presents the results ofextensive evaluations of these algorithms based on common benchmark data sets.Applications of ESWSA in Structure learning of Bayesian Network and comparisonswith the Simulated Annealing and Greedy Search, show that this proposed method isbetter than the default Simulated Annealing and Greedy search methods.Keywords: Bayesian network, structure learning, Pigeon Inspired Optimization, BeeOptimization, greedy, Simulated Annealing, elephant swarm search, water search,global search, local search, search and score.

Bayes ağları, makina öğrenmesinde değişkenler arasındaki rassal ilişkileri temsil edenbilgi yapısının tasarımında kullanılan yararlı analitik modellerdir. Genel olarak Bayesağı Ağın Parametreleri ve Ağın yapısına bağlıdır.Parametreler şartlı olasılıkları,yapıise şans değişkenleri arasındaki bağımlılıkları temsil eder. Bir Bayes ağının yapısıyönlü çevrimsel olmayan bir çizgedir.Bayes ağının yapısını öğrenmek bir NP-zorproblem olmasına ragmen,yaklaşık çözümlerin eniyilenmesi için çok sayıda genişkapsamlı çalışmalar yapılmıştır.Bu tezde yapı öğrenme problemine çözüm bulmayıamaçlayan algoritmalar geliştirmek için araştırmalar yürütülmüştür.Bayes ağlarınyapısın öğrenmek için iki yaklaşım vardır.Birinci yaklaşım kısıtlamalı diğeri ise skorve arama temellidir.Skor temelli yaklaşımlar genel yaklaşımlardır.Bu yaklaşımlar ağmodelinin verilere nasıl uyum gösterdiğni ölçen bir fonksiyonu esas alırlar ve bufonıksiyonun değerini daha iyileştirecek yapıyı üretmeye çalışırlar.İki tür skorfonksiyonu vardır :Bayesçi skor ve bilgi teorisi skoru. Her iki skor da yapı öğrenmeyöntemlerinde uygulanmıştır.Bu tezde Bayes ağın yapısını öğrenmede skor temelliarama için sezgisel yötemler kullanılmış ve skor fonksiyonu olarak BDeu metriğikullanılmıştır.Bu amaçla,BDeu yu kullanan altı algoritma önerimiştir.Önerilen ilkalgoritma güvercinlerin yön bulmasından esinlenen eniyileme algoritmasıdır ve BDeuskorunu kullanmaktadır.Önerilen yöntemin yaygın kullanılan yöntemlerden daha iyisonuçlar verdiği görülmüştür.Bu algoritma bu alanda ilk defa kullanılmaktadır.İkinciönerilen algoritma arı eniyilemesi algoritmasına ve benzetilmiş tavlama algoritmasınadayanmakta ve ilkini global ikincisini de yerel arama için kullanmaktadır.Üçüncüönerilen yöntem gene önceki ikisini esas almakta fakat bu defa arı eniyilemesi global,vibenzetilmiş tavlama algoritması yerel arama için kullanılmıştır. Dördüncü önerilenyöntemde melez bir yöntem olup arı eniyilemesi ve açgözlü amayı esas almakta ve arıeniyilemesini yerel ve açgözlüyü de global arama için kullnmaktadır.Beşinci yöntemde melezdir ve arı eniyilemesini global,açgözlü yöntemi yerel arama içinkullanmaktadır.Son önerimiz Fil sürülerinin su kaynağı arama algoritmasınadayanmaktadır.Tezde genel kıyaslama veri setleri kullanılarak BDeu metriği vekarışıklık matrislerine dayanan değerlendirmeler tartışılmış, sonuçta güvercin yönbulma ve fil sürüleri su arama yöntemlerine dayanan algoritmaların diğerlerindan dahabaşarılı olduğu gösterimiştir.Anahtar sözcükler: Bayes ağı,yapı öğrenme,Güvercinden Esinlenen Algoritma,ArıEniyilemesi,açgözlü,Benzetilmiş Tavlama,,Fil sürü araması,su araması,globalarama,yerel arama, arama ve skor.