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

• Autorzy: Moshkov, M.Ju.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Bayesian networks; decision tree; complexity; simulation

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 50, nr 1
• Strony: 57-76
• Opis fizyczny: bibliogr. 3 poz.

Twórcy

autor

Moshkov, M.Ju.

• Faculty of Computing Mathematics and Cybernetics of Nizhni Novgorod State University, 23, Gagarina Av., Nizhni Novgorod, 603600, Russia,