Physarum Learner: a novel structure learning algorithm for Bayesian Networks inspired by Physarum polycephalum

URN to cite this document:: urn:nbn:de:bvb:355-epub-284154
DOI to cite this document:: 10.5283/epub.28415

Schön, Torsten

Preview

License: Publishing license for publications including print on demand
PDF
(8MB)

Date of publication of this fulltext: 12 Jul 2013 11:09

Details

Item type:	Thesis of the University of Regensburg (PhD)
Date:	12 July 2013
Referee:	Prof. Dr. Elmar W. Lang
Date of exam:	12 July 2013
Institutions:	Biology, Preclinical Medicine > Institut für Biophysik und physikalische Biochemie
Keywords:	Physarum Polycephalum, Bayesian Network, Structure Learning, C-Phyl, SO-Phyl
Dewey Decimal Classification:	000 Computer science, information & general works > 004 Computer science 500 Science > 570 Life sciences 600 Technology > 610 Medical sciences Medicine
Status:	Published
Refereed:	Yes, this version has been refereed
Created at the University of Regensburg:	Yes
Item ID:	28415

Preview

Export bibliographical data

Abstract (English)

Abstract (English)

Two novel algorithms for learning Bayesian network structure from data based on the true slime mold Physarum polycephalum are introduced. The first algorithm called CPhyL calculates pairwise correlation coeffcients in the dataset. Within an initially fully connected Physarum-Maze, the length of the connections is given by the inverse correlation coeffcient between the connected nodes. Then, the shortest indirect path between each two nodes is determined using the Physarum Solver. In each iteration, a score of the surviving edges is increased. Based on that score, the highest ranked connections are combined to form a Bayesian network. The novel C-PhyL method is evaluated with different configurations and compared to the LAGD Hill Climber, Tabu Search and Simulated Annealing on a set of artificially generated and real benchmark networks of different characteristics, showing comparable performance regarding quality of training results and increased time efficiency for large datasets. The second novel algorithm called SO-PhyL is introduced and shown to be able to outperform common score based structure learning algorithms for some benchmark datasets. SO-PhyLfirst initializes a fully connected Physarum-Maze with constant length and random conductivities. In each Physarum Solver iteration, the source and sink nodes are changed randomly and the conductivities are updated. Connections exceeding a predefined conductivity threshold are considered as Bayesian network arcs and score of nodes included in selected connections is examined in both directions. A positive or negative feedback is given to conductivity values based on calculated scores. Due to randomness in initializing conductivities and selecting connections for evaluation, an ensemble of SOPhyL is used to search thefinal best Bayesian network structure. First, a detailed analysis of the influence of configuration parameters on learning quality of SO-PhyL is presented, before the novel algorithm is compared to state of the art structure learning methods using a set of artificially generated benchmark networks. Next, seven real benchmark networks are used to further analyse the performance of SO-PhyL compared to other algorithms. It is observed that SO-PhyL is a competitive structure learning method that outperforms Simulated Annealing in most datasets, Tabu Search in some datasets and even LAGD for specific networks. A newly generated medical dataset collecting clinical parameters of liver biopsy proven Non-alcoholic Fatty Liver Disease (NALFD) patients delivered from the Medical University of Graz is analysed using common feature selection and classification methods in order tofind novel biomarker candidates for NAFLD. Magnesium is identified as promising biomarker and is forwarded to medical experts where a mouse model is used to verify the novel biomarker candidate. In addition, both Physarum based algorithms are used to learn a Bayesian network structure from the NAFLD dataset to get deeper understanding of parameter interactions.

Translation of the abstract (German)

In dieser Arbeit werden zwei neu entwickelte Strukturlernalgorithmen für Bayesische Netzwerke vorgestellt, welche von dem echten Schleimpilz Physarum polycephalum inspiriert sind. Der erste, C-PhyL genannte, Algorithmus berechnet paarweise Korrelationskoeffizienten in dem Datensatz. Ein Initial voll verbundenes Phyasarum-Maze wird generiert, in welchem die Distanzen zwischen den einzelnen Knoten den inversen Korrelationswerten gleichgesetzt werden. Anschließend wird mit Hilfe des Physarum Solvers der kürzeste indirekte Pfad zwischen zwei Knoten ermittelt. In jeder Iteration wird ein Score der verbleibenden Verbindungen erhöht. Basierend auf diesen Score-Werten wird ein Bayesisches Netzwerk aus diesen Verbindungen abgeleitet. Dieser neue entwickelte Algorithmus wird mit verschiedenen Konfigurationen auf künstlich generierten und echten Testdatensätzen angewandt und mit LAGD Hill Climber, Tabu Search und Simulated Annealing verglichen. Hierbei zeigt C-PhyL vergleichbar gute Ergebnisse und kürzere Rechenzeiten für sehr große Datensätze.
Ein weiterer, SO-PhyL genannter, Algorithmus wird vorgestellt und es wird gezeigt, dass diese in der Lage ist, herkömmliche Strukturlernalgorithmen für bestimme Datensätze zu übertreffen. SO-Phyl generiert zuerst ein voll verbundenes Physarum-Maze in welchen die Distanzen zwischen allen Knoten gleich sind und die Leitfähigkeiten der Verbindungen zufällig initialisiert werden. In jeder Physarum-Solver Iteration wird ein Start- und ein Endknoten zufällig bestimmt, und die Leitfähigkeiten werden neu berechnet. Verbindungen deren Leitfähigkeit einen vorher bestimmten Schwellenwert überschreiten, werden als möglichen Kanten für ein Bayesisches Netzwerk in Betracht gezogen und es wird ein Score für beide Richtungen berechnet. Basierend auf diesem Score wird den Leitfähigkeiten ein positives oder negatives Feedback gegeben. Da die Initialisierung der Leitfähigkeiten zufällig erfolgt, wird eine Gruppe von SO-PhyLs verwendet um das endgültige Bayesische Netzwerk zu ermitteln. Zuerst wird eine ausführliche Untersuchung der beeinflussenden Parameter des Algorithmus durchgeführt. Anschließend wird die neue Methode mit herkömmlichen Algorithmen verglichen. Hierzu werden sowohl eine Reihe künstlich erzeugter Netzwerke herangezogen, als auch sieben echte Testdatensätze. Es wird beobachtet, dass SO-PhyL ein vergleichbar guter Lernalgorithmus ist, welcher für bestimmte Datensätze sogar bessere Ergebnisse liefert.
Weiter wird ein an der Medizinischen Universität Graz (MUG) neu ermittelter Datensatz analysiert, welcher verschiedene Parameter von an Nicht-alkoholischer Fettleber erkrankten Patienten beinhaltet. Hierzu werden Standardmethoden der Datenanalyse verwenden um mögliche Biomarker Kandidaten zu bestimmen. Die Analyse zeigt, dass Magnesium ein vielversprechender Kandidat hierfür ist, und ein Maus-Modell wurde von den Medizin-Experten der MUG eingeleitet um dies zu überprüfen. Zudem wurden die beiden neu vorgestellten Strukturlernalgorithmen dazu benutzt, ein Netzwerk des Datensatzes zu generieren um einen tieferen Einblick in die Beziehungen der Parameter zu erlangen.

Owner only: item control page

Download Statistics

More literature (via CORE)

Details

Preview

Export bibliographical data

Abstract (English)

Abstract (English)

Translation of the abstract (German)

Translation of the abstract (German)

Download Statistics

Downloads

More literature (via CORE)

University Library