Inference in polytrees with sets of probabilities

José Carlos Ferreira da Rocha, Fabio Gagliardi Cozman, Cassio P. de Campos

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

Inferences in directed acyclic graphs associated with probability intervals and sets of probabilities are NP-hard, even for polytrees. We propose: 1) an improvement on Tessem’s A/R algorithm for inferences on polytrees associated with probability intervals; 2) a new algorithm for approximate inferences based on local search; 3) branch-and-bound algorithms that combine the previous techniques. The first two algorithms produce complementary approximate solutions, while branch-and-bound procedures can generate either exact or approximate solutions. We report improvements on existing techniques for inference with probability sets and intervals, in some cases reducing computational effort by several orders of magnitude.
Original languageEnglish
Title of host publicationProceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)
PublisherMorgan Kaufmann Publishers, Inc.
Pages217-224
Number of pages8
ISBN (Print)0-127-05664-5
Publication statusPublished - 2003
Externally publishedYes
Event19th Conference on Uncertainty in Artificial Intelligence - Acapulco, Mexico
Duration: 7 Aug 200310 Aug 2003

Conference

Conference19th Conference on Uncertainty in Artificial Intelligence
Abbreviated titleUAI-03
CountryMexico
CityAcapulco
Period7/08/0310/08/03

Bibliographical note

(Double blind reviewed by multiple reviewers. plenary presentation)

Cite this

da Rocha, J. C. F., Cozman, F. G., & de Campos, C. P. (2003). Inference in polytrees with sets of probabilities. In Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03) (pp. 217-224). Morgan Kaufmann Publishers, Inc..