Structural learning of Bayesian networks using local algorithms based on the space of orderings

Structural learning of Bayesian networks (BNs) is an NP-hard problem which is generally addressed by means of heuristic search algorithms. Despite the fact that earlier proposals for dealing with this task were based on searching the space of Directed Acyclic Graphs (DAGs), there are some alternativ...

Full description

Saved in:
Bibliographic Details
Published in:Soft computing (Berlin, Germany) Germany), 2011-10, Vol.15 (10), p.1881-1895
Main Authors: Alonso-Barba, Juan I., delaOssa, Luis, Puerta, Jose M.
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Bayesian analysis
Climbing
Computational Intelligence
Control
Efficiency
Engineering
Focus
Graph theory
Heuristic methods
Iterative methods
Machine learning
Mathematical Logic and Foundations
Mechatronics
Neighborhoods
Probability distribution
Robotics
Search algorithms
Variables
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Structural learning of Bayesian networks (BNs) is an NP-hard problem which is generally addressed by means of heuristic search algorithms. Despite the fact that earlier proposals for dealing with this task were based on searching the space of Directed Acyclic Graphs (DAGs), there are some alternative approaches. One of these approaches for structural learning consists of searching the space of orderings, as given a certain topological order among the problem variables, it is relatively easy to build (and evaluate) a BN compatible with it. In practice, the latter methods make it possible to obtain good results, but they are still costly in terms of computation. In this article, we prove the correctness of the method used to evaluate each ordering, and we propose some efficient learning algorithms based on it. Our first proposal is based on the Hill-Climbing algorithm, and uses an improved neighbourhood definition. The second algorithm is an extension of the first one, and is based on the well-known Variable Neighbourhood Search metaheuristic. Finally, iterative versions of both algorithms are also proposed. The algorithms have been tested over a set of different domains, and have been compared with other methods such as Hill-Climbing in the space of DAGs or Greedy Equivalent Search , in order to study their behaviour in practice.
ISSN:1432-7643
1433-7479
DOI:10.1007/s00500-010-0623-x