On decision trees for (1,2)-bayesian networks

Mikhail Moshkov*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)57-76
Number of pages20
JournalFundamenta Informaticae
Volume50
Issue number1
StatePublished - Mar 1 2002

Keywords

  • Bayesian networks
  • Complexity
  • Decision trees
  • Simulation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Information Systems
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On decision trees for (1,2)-bayesian networks'. Together they form a unique fingerprint.

Cite this