Learning probabilistic decision graphs.

*(English)*Zbl 1096.68704Summary: Probabilistic Decision Graphs (PDGs) are a representation language for probability distributions based on binary decision diagrams. PDGs can encode (context-specific) independence relations that cannot be captured in a Bayesian network structure, and can sometimes provide computationally more efficient representations than Bayesian networks. In this paper we present an algorithm for learning PDGs from data. First experiments show that the algorithm is capable of learning optimal PDG representations in some cases, and that the computational efficiency of PDG models learned from real-life data is very close to the computational efficiency of Bayesian network models.

##### MSC:

68T05 | Learning and adaptive systems in artificial intelligence |

PDF
BibTeX
XML
Cite

\textit{M. Jaeger} et al., Int. J. Approx. Reasoning 42, No. 1--2, 84--100 (2006; Zbl 1096.68704)

Full Text:
DOI

##### References:

[1] | M. Bozga, O. Maler, On the representation of probabilities over structured domains, in: Proceedings of CAV-99, no. 1633 in Lecture Notes in Computer Science, 1999. · Zbl 1046.68581 |

[2] | M. Jaeger, Probabilistic decision graphs: Combining verification and AI techniques for probabilistic inference, in: Proceedings of the first European Workshop on Probabilistic Graphical Models (PGM), 2002, pp. 81-88. |

[3] | Bryant, R.E., Graph-based algorithms for Boolean function manipulation, IEEE transactions on computers, 35, 8, 677-691, (1986) · Zbl 0593.94022 |

[4] | () |

[5] | Jaeger, M., Probabilistic decision graphs-combining verification and AI techniques for probabilistic inference, International journal of uncertainty, fuzziness and knowledge-based systems, 12, 19-42, (2004) · Zbl 1087.68111 |

[6] | C. Boutilier, N. Friedman, M. Goldszmidt, D. Koller, Context-specific independence in Bayesian networks, in: Proceedings of the Twelfth Annual Conference on Uncertainty in Artificial Intelligence (UAI-96), 1996, pp. 115-123. |

[7] | Cowell, R.G.; Dawid, A.P.; Lauritzen, S.L.; Spiegelhalter, D.J., Probabilistic networks and expert systems, (1999), Springer · Zbl 0937.68121 |

[8] | Myllymaki, P.; Silander, T.; Tirri, H.; Uronen, P., B-course: A web-based tool for Bayesian and causal data analysis, International journal on artificial intelligence tools, 11, 3, 369-387, (2002) |

[9] | Huang, C.; Darwiche, A., Inference in belief networks: A procedural guide, International journal of approximate reasoning, 15, 225-263, (1996) · Zbl 0941.68767 |

[10] | Cover, T.M.; Thomas, J., Elements of information theory, (1991), Wiley · Zbl 0762.94001 |

[11] | F. Provost, T. Fawcett, Analysis and visualization of classifier performance: Comparison under imprecise class and cost distribution, in: Proceedings of the Third International Conference on Knowledge Discovery and Data Mining (KDD-97), 1997, pp. 43-48. |

[12] | A. Darwiche, A differential approach to inference in Bayesian networks, in: Proceedings of the Sixteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-2000), 2000, pp. 123-132. |

[13] | A. Darwiche, A logical approach to factoring belief networks, in: Proceedings of the Eighth International Conference on Principles and Knowledge Representation and Reasoning (KR-2002), 2002, pp. 409-420. |

[14] | M. Collins, D. McAllester, F. Pereira, Case-factor diagrams for structured probabilistic modeling, in: Proceedings of the Twentieth Annual Conference on Uncertainty in Artificial Intelligence (UAI-2004), 2004, pp. 382-391. · Zbl 1161.68784 |

[15] | Provost, F.; Domingos, P., Tree induction for probability-based ranking, Machine learning, 52, 199-215, (2003) · Zbl 1039.68105 |

[16] | Chickering, D.M.; Heckerman, D.; Meek, C., A Bayesian approach to learning Bayesian networks with local structure, (), 80-89 |

[17] | Friedman, N.; Goldszmidt, M., Learning Bayesian networks with local structure, () · Zbl 0910.68176 |

[18] | Fujita, M.; McGeer, P.C.; Yang, J.-Y., Multi-terminal binary decision diagrams: an efficient data structure for matrix representation, Formal methods in system design, 10, 149-169, (1997) |

[19] | L.M. de Campos, J.F. Huete, Algorithms for learning decomposable models and chordal graphs, in: Proceedings of the Thirteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI-97), 1997, pp. 46-53. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.