Two-Way Greedy Search: Learning Bayesian Network With Diverged Path
Loading...
Date
2017-07
Authors
Chua, Chong Yong
Journal Title
Journal ISSN
Volume Title
Publisher
Universiti Sains Malaysia
Abstract
Learning the best structure of a Bayesian network (BN) is a difficult task. Though optimal result is not guaranteed, heuristic search specifically greedy search algorithm is commonly being used in BN structural learning due to its efficiency. Due to certain characteristics, common scoring functions used in score-based algorithm are unable to distinguish between two equivalent networks and often trapped in local maxima. Despite equivalent networks generate the same score, the difference in direction of arcs of final solution can be interpreted differently. This characteristic has the potential in improving the exploration of BN structural learning algorithm. In this research, we propose an improved greedy search algorithm, two-way greedy search (2-WGS) that is able to distinguish between equivalent networks while learning the structure of BN. This algorithm consists of two phases with Phase 1 generating two networks regardless of network equivalency, and later on used as an initial network to perform hill climbing in order to obtain the final network in the second phase. An experimental evaluation is conducted to compare the accuracy between our proposed algorithm and benchmark algorithms. The results of simulation show that the proposed method gives relatively good performance compared to existing methods. Furthermore, an extension study is done to further improve 2-WGS into a hybrid-based algorithm which shows improvement in terms of running time. Lastly, a real life application using our proposed method is shown to prove the performance not only theoretically but also practically.
Description
Keywords
Heuristic search specifically greedy search algorithm , commonly being used in BN structural learning due to its efficiency.