On Decision Trees for (1,2)-Bayesian Networks

Article type: Research Article

Authors: Moshkov, Mikhail Ju.

Affiliations: Faculty of Computing Mathematics and Cybernetics of Nizhny Novgorod State University, 23, Gagarina Av., Nizhny Novgorod, 603950, Russia

Abstract: Bayesian Networks (BN) are convenient tool for representation of probability distribution of variables. We study time complexity of decision trees which compute values of all observable variables from BN. We consider (1,2)-BN in which each node has at most 1 entering edge, and each variable has at most 2 values. For an arbitrary (1,2)-BN we obtain lower and upper bounds on minimal depth of decision tree that differ not more than by a factor of 4, and can be computed by an algorithm which has polynomial time complexity. The number of nodes in considered decision trees can grow as exponential on number of observable variables in BN. We develop an polynomial algorithm for simulation of the work of decision trees which depth lies between the obtained bounds.

Keywords: Bayesian networks, decision trees, complexity, simulation

Journal: Fundamenta Informaticae, vol. 50, no. 1, pp. 57-76, 2002