|
| << previous |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 5 of 5 found articles
| Title: |
On Decision Trees for (1,2)-Bayesian Networks |
| Author: |
Mikhail Ju. Moshkov |
| Appeared in: |
Fundamenta informaticae |
| Paging: | Volume 50 (2003) nr. 1 pages 57-76 |
| Year: |
2003-07-11 |
| Contents: |
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. |
| Publisher: |
IOS Press |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 5 of 5 found articles
| << previous |