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


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.
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


Conference19th Conference on Uncertainty in Artificial Intelligence
Abbreviated titleUAI-03

Bibliographical note

(Double blind reviewed by multiple reviewers. plenary presentation)


Dive into the research topics of 'Inference in polytrees with sets of probabilities'. Together they form a unique fingerprint.

Cite this