Ordering Estimation for Bayesian Network Structure Learning
Author
Pacekajus, Saulius
Term
10. Term
Education
Publication year
2009
Abstract
At lære strukturen i et Bayesiansk netværk handler om at finde ud af, hvilke variable der påvirker hinanden, og i hvilken retning. Bayesianske netværk er sandsynlighedsmodeller, der repræsenterer disse relationer som en rettet acyklisk graf. Trods årtiers forskning er strukturindlæring stadig vanskelig, og mange metoder afhænger af at have en god variabelrækkefølge (den rækkefølge, hvori variable behandles). Denne afhandling introducerer rækkefølgeestimering: at udlede en nyttig variabelrækkefølge direkte fra data til at understøtte rækkefølgebaserede eller rækkefølgeafhængige algoritmer til strukturindlæring. Vi præsenterer tre forskellige tilgange til at estimere en rækkefølge og evaluerer dem i en række eksperimenter. Resultaterne indikerer, at søgeprocedurer, der er afhængige af en variabelrækkefølge, kan drage fordel af at få en estimeret rækkefølge. Vi undersøger også den velkendte K2-algoritme, som traditionelt kræver en forudbestemt, ideelt set optimal, variabelrækkefølge. Vores resultater tyder på, at K2 kan anvendes uden kendskab til den optimale rækkefølge, når der anvendes rækkefølgeestimering.
Learning the structure of a Bayesian network means discovering which variables influence each other and in what direction. Bayesian networks are probabilistic models that represent these relations as a directed acyclic graph. Despite decades of research, structure learning remains difficult, and many methods depend on having a good variable ordering (the sequence in which variables are considered). This thesis introduces ordering estimation: inferring a helpful variable ordering directly from data to support ordering-based or ordering-dependent structure learning algorithms. We present three different approaches to estimating an ordering and evaluate them in a series of experiments. The results indicate that search procedures that rely on a variable ordering can benefit from being given an estimated ordering. We also explore the well-known K2 algorithm, which traditionally requires a predetermined, ideally optimal, variable ordering. Our results suggest that K2 can be applied without knowing the optimal order when ordering estimation is used.
[This abstract was generated with the help of AI]
Documents