This article is cited in 5 papers

Algebraic Bayesian Network Tertiary Structure Synthesis Algorithms

A. A. Fil'chenkov


Abstract: Algebraic Bayesian network (ABN) tertiary structure represented as a clique graph is important for synthesizing and analyzing the ABN secondary structure, as well as for an analysis of the ABN primary structure. Two tertiary structure synthesis algorithms are proposed: clique tree synthesis descendants algorithm, and clique tree synthesis bottom-up algorithm, their validity is proved and their computational complicity is estimated in the article. Both the algorithms synthesize two ordered sets containing the set of vertices and the set of sons of each clique for given maximal knowledge pattern set Examples of the ABN primary structures for which the first algorithm works faster than the second one, and vice versa, the second one works faster than the first one, are given. Also ABN tertiary structure existence and uniqueness for every ABN primary structure are stated.

Keywords: algebraic Bayesian networks, tertiary structure, machine learning, probabilistic graphical models, global structure.

UDC: 004.8

MSC: 68

Received: 08.07.2011
Accepted: 29.09.2011