×

Local search methods for learning Bayesian networks using a modified neighborhood in the space of DAGs. (English) Zbl 1036.68555

Garijo, Francisco J. (ed.) et al., Advances in artificial intelligence – IBERAMIA 2002. 8th Ibero-American conference on AI, Seville, Spain, November 12–15, 2002. Proceedings. Berlin: Springer (ISBN 3-540-00131-X/pbk). Lect. Notes Comput. Sci. 2527, 182-192 (2002).
Summary: The dominant approach for learning Bayesian networks from data is based on the use of a scoring metric, that evaluates the fitness of any given candidate network to the data, and a search procedure, that explores the space of possible solutions. The most efficient methods used in this context are (Iterated) Local Search algorithms. These methods use a predefined neighborhood structure that defines the feasible elementary modifications (local changes) that can be applied to a given solution in order to get another, potentially better solution. If the search space is the set of directed acyclic graphs (dags), the usual choices for local changes are arc addition, arc deletion and arc reversal. In this paper we propose a new definition of neighborhood in the dag space, which uses a modified operator for arc reversal. The motivation for this new operator is the observation that local search algorithms experience problems when some arcs are wrongly oriented. We exemplify the general usefulness of our proposal by means of a set of experiments with different metrics and different local search methods, including Hill-Climbing and Greedy Randomized Adaptive Search Procedure (GRASP), as well as using several domain problems.
For the entire collection see [Zbl 1007.00051].

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: Link