Decomposing Bayesian networks

Triangulation of the moral graph with genetic algorithms

P. Larrañaga, Cindy Kuijpers, M. Poza, R.H. Murga

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this paper we consider the optimal decomposition of Bayesian networks. More concretely, we examine empirically the applicability of genetic algorithms to the problem of the triangulation of moral graphs. This problem constitutes the only difficult step in the evidence propagation algorithm of Lauritzen and Spiegelhalter (1988) and is known to be NP-hard (Wen, 1991). We carry out experiments with distinct crossover and mutation operators and with different population sizes, mutation rates and selection biasses. The results are analysed statistically. They turn out to improve the results obtained with most other known triangulation methods (Kjærulff, 1990) and are comparable to results obtained with simulated annealing (Kjærulff, 1990; Kjærulff, 1992).
Original languageEnglish
Pages (from-to)19-34
JournalStatistics and Computing
Volume7
Issue number1
DOIs
Publication statusPublished - Mar 1997
Externally publishedYes

Fingerprint

Bayesian networks
Triangulation
Bayesian Networks
Genetic algorithms
Genetic Algorithm
Mutation
Graph in graph theory
Simulated annealing
Population Size
Decomposition
Simulated Annealing
Crossover
NP-complete problem
Propagation
Distinct
Decompose
Experiments
Operator
Experiment
Genetic algorithm

Cite this

@article{24566bd6ebd8439dacad4ab8174b5ecf,
title = "Decomposing Bayesian networks: Triangulation of the moral graph with genetic algorithms",
abstract = "In this paper we consider the optimal decomposition of Bayesian networks. More concretely, we examine empirically the applicability of genetic algorithms to the problem of the triangulation of moral graphs. This problem constitutes the only difficult step in the evidence propagation algorithm of Lauritzen and Spiegelhalter (1988) and is known to be NP-hard (Wen, 1991). We carry out experiments with distinct crossover and mutation operators and with different population sizes, mutation rates and selection biasses. The results are analysed statistically. They turn out to improve the results obtained with most other known triangulation methods (Kj{\ae}rulff, 1990) and are comparable to results obtained with simulated annealing (Kj{\ae}rulff, 1990; Kj{\ae}rulff, 1992).",
author = "P. Larra{\~n}aga and Cindy Kuijpers and M. Poza and R.H. Murga",
year = "1997",
month = "3",
doi = "10.1023/A:1018553211613",
language = "English",
volume = "7",
pages = "19--34",
journal = "Statistics and Computing",
issn = "0960-3174",
publisher = "Springer Netherlands",
number = "1",

}

Decomposing Bayesian networks : Triangulation of the moral graph with genetic algorithms. / Larrañaga, P.; Kuijpers, Cindy; Poza, M.; Murga, R.H.

In: Statistics and Computing, Vol. 7, No. 1, 03.1997, p. 19-34.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Decomposing Bayesian networks

T2 - Triangulation of the moral graph with genetic algorithms

AU - Larrañaga, P.

AU - Kuijpers, Cindy

AU - Poza, M.

AU - Murga, R.H.

PY - 1997/3

Y1 - 1997/3

N2 - In this paper we consider the optimal decomposition of Bayesian networks. More concretely, we examine empirically the applicability of genetic algorithms to the problem of the triangulation of moral graphs. This problem constitutes the only difficult step in the evidence propagation algorithm of Lauritzen and Spiegelhalter (1988) and is known to be NP-hard (Wen, 1991). We carry out experiments with distinct crossover and mutation operators and with different population sizes, mutation rates and selection biasses. The results are analysed statistically. They turn out to improve the results obtained with most other known triangulation methods (Kjærulff, 1990) and are comparable to results obtained with simulated annealing (Kjærulff, 1990; Kjærulff, 1992).

AB - In this paper we consider the optimal decomposition of Bayesian networks. More concretely, we examine empirically the applicability of genetic algorithms to the problem of the triangulation of moral graphs. This problem constitutes the only difficult step in the evidence propagation algorithm of Lauritzen and Spiegelhalter (1988) and is known to be NP-hard (Wen, 1991). We carry out experiments with distinct crossover and mutation operators and with different population sizes, mutation rates and selection biasses. The results are analysed statistically. They turn out to improve the results obtained with most other known triangulation methods (Kjærulff, 1990) and are comparable to results obtained with simulated annealing (Kjærulff, 1990; Kjærulff, 1992).

U2 - 10.1023/A:1018553211613

DO - 10.1023/A:1018553211613

M3 - Article

VL - 7

SP - 19

EP - 34

JO - Statistics and Computing

JF - Statistics and Computing

SN - 0960-3174

IS - 1

ER -